Accession Number:

ADA052445

Title:

The Incremental Garbage Collection of Processes.

Descriptive Note:

Memorandum rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB

Personal Author(s):

Report Date:

1977-12-01

Pagination or Media Count:

13.0

Abstract:

This paper investigates some problems associated with an expression evaluation order that we call future order, which is different from call-by-name, call-by-value, and call-by-need. In future order evaluation, an object called a future is created to serve as the value of each expression that is to be evaluated and separate process is dedicated to its evaluation. This mechanism allows the fully parallel evaluation of the expressions in a programming language. We discuss an approach to a problem that arises in this context futures which were thought to be relevant when they were created become irrelevant through not being needed later in the computation. The problem of irrelevant processes also appears in multiprocessing problem-solving systems which start several processors working on the same problem but with different methods, and return with the solution which finishes first. This parallel method strategy has the drawback that the processes which are investigating the losing methods must be identified, cleanly stopped, and the processors they are using re-assigned to more useful tasks. The solution we propose is that of incremental garbage collection. The goal structure of the solution plan should be explicitly represented in memory as part of the graph memory like Lisps heap so that a garbage collection algorithm can discover which processes are performing useful work, and which can be recycled for a new task. An incremental algorithm for the unified garbage collection of storage and processes is described. Author

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE