A Parallel Garbage Collection Algorithm and Its Application to LISP
Summary :
A new practical parallel garbage collection algorithm and its correctness proof are presented. Some results of its implementation applied to a small size LISP system are reported. The algorithm, which is constructed on the condition that all active lists are bound in the linear stack, needs only one mark bit for each node and a scan-request-flag (SREQ) for the system. The minimum utilization of critical sections, where the operations on SREQ are performed, dispenses with the need for multicolored marking, such as white, gray or black. Also marking efficiency improves since it enables applying a recursive trace-and-mark method instead of a simple scan-and-markmethod. An outline of the correctness proof is as follows : It is proned by induction that the relation, wherein the active-node-set is a subset of the mark-reachable-set, which is defined as the set of all the nodes to which some links exist from any nodes already marked, is retained during the mark propagating phase for any list processing primitives, so that the algorithm guarantees that no active nodes are reclaimed. Last, the implementation of a small size LISP system with this algorithm is reported. The comparison between the parallel system and the regular one is discussed on the basis of actual data.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E63-E No.1 pp.1-8
- Publication Date
- 1980/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Programming
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yasushi HIBINO, "A Parallel Garbage Collection Algorithm and Its Application to LISP" in IEICE TRANSACTIONS on transactions,
vol. E63-E, no. 1, pp. 1-8, January 1980, doi: .
Abstract: A new practical parallel garbage collection algorithm and its correctness proof are presented. Some results of its implementation applied to a small size LISP system are reported. The algorithm, which is constructed on the condition that all active lists are bound in the linear stack, needs only one mark bit for each node and a scan-request-flag (SREQ) for the system. The minimum utilization of critical sections, where the operations on SREQ are performed, dispenses with the need for multicolored marking, such as white, gray or black. Also marking efficiency improves since it enables applying a recursive trace-and-mark method instead of a simple scan-and-markmethod. An outline of the correctness proof is as follows : It is proned by induction that the relation, wherein the active-node-set is a subset of the mark-reachable-set, which is defined as the set of all the nodes to which some links exist from any nodes already marked, is retained during the mark propagating phase for any list processing primitives, so that the algorithm guarantees that no active nodes are reclaimed. Last, the implementation of a small size LISP system with this algorithm is reported. The comparison between the parallel system and the regular one is discussed on the basis of actual data.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e63-e_1_1/_p
Copy
@ARTICLE{e63-e_1_1,
author={Yasushi HIBINO, },
journal={IEICE TRANSACTIONS on transactions},
title={A Parallel Garbage Collection Algorithm and Its Application to LISP},
year={1980},
volume={E63-E},
number={1},
pages={1-8},
abstract={A new practical parallel garbage collection algorithm and its correctness proof are presented. Some results of its implementation applied to a small size LISP system are reported. The algorithm, which is constructed on the condition that all active lists are bound in the linear stack, needs only one mark bit for each node and a scan-request-flag (SREQ) for the system. The minimum utilization of critical sections, where the operations on SREQ are performed, dispenses with the need for multicolored marking, such as white, gray or black. Also marking efficiency improves since it enables applying a recursive trace-and-mark method instead of a simple scan-and-markmethod. An outline of the correctness proof is as follows : It is proned by induction that the relation, wherein the active-node-set is a subset of the mark-reachable-set, which is defined as the set of all the nodes to which some links exist from any nodes already marked, is retained during the mark propagating phase for any list processing primitives, so that the algorithm guarantees that no active nodes are reclaimed. Last, the implementation of a small size LISP system with this algorithm is reported. The comparison between the parallel system and the regular one is discussed on the basis of actual data.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - A Parallel Garbage Collection Algorithm and Its Application to LISP
T2 - IEICE TRANSACTIONS on transactions
SP - 1
EP - 8
AU - Yasushi HIBINO
PY - 1980
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E63-E
IS - 1
JA - IEICE TRANSACTIONS on transactions
Y1 - January 1980
AB - A new practical parallel garbage collection algorithm and its correctness proof are presented. Some results of its implementation applied to a small size LISP system are reported. The algorithm, which is constructed on the condition that all active lists are bound in the linear stack, needs only one mark bit for each node and a scan-request-flag (SREQ) for the system. The minimum utilization of critical sections, where the operations on SREQ are performed, dispenses with the need for multicolored marking, such as white, gray or black. Also marking efficiency improves since it enables applying a recursive trace-and-mark method instead of a simple scan-and-markmethod. An outline of the correctness proof is as follows : It is proned by induction that the relation, wherein the active-node-set is a subset of the mark-reachable-set, which is defined as the set of all the nodes to which some links exist from any nodes already marked, is retained during the mark propagating phase for any list processing primitives, so that the algorithm guarantees that no active nodes are reclaimed. Last, the implementation of a small size LISP system with this algorithm is reported. The comparison between the parallel system and the regular one is discussed on the basis of actual data.
ER -
English
