The Incremental Garbage Collection of Processes
Key Words and Phrases: garbage collection, multiprocessing systems, processor scheduling. "lazy evaluation, "eager" evaluation. CR Categories: 3.60, 3.80, 4.13, 4.22, 4.32. This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute o...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
MIT Artificial Intelligence Laboratory
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/41969 |
| _version_ | 1826203463689699328 |
|---|---|
| author | Hewitt, Carl Baker, Henry G. Jr. |
| author_facet | Hewitt, Carl Baker, Henry G. Jr. |
| author_sort | Hewitt, Carl |
| collection | MIT |
| description | Key Words and Phrases: garbage collection, multiprocessing systems, processor scheduling. "lazy evaluation, "eager" evaluation.
CR Categories: 3.60, 3.80, 4.13, 4.22, 4.32.
This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-75-C-0522.
This paper was presented at the AI*PL Conference at Rochester, N.Y. in August, 1977. |
| first_indexed | 2024-09-23T12:37:28Z |
| format | Working Paper |
| id | mit-1721.1/41969 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:37:28Z |
| publishDate | 2008 |
| publisher | MIT Artificial Intelligence Laboratory |
| record_format | dspace |
| spelling | mit-1721.1/419692019-04-12T09:43:50Z The Incremental Garbage Collection of Processes Hewitt, Carl Baker, Henry G. Jr. "eager" evaluation "lazy" evaluation processor scheduling multiprocessing systems garbage collection Key Words and Phrases: garbage collection, multiprocessing systems, processor scheduling. "lazy evaluation, "eager" evaluation. CR Categories: 3.60, 3.80, 4.13, 4.22, 4.32. This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-75-C-0522. This paper was presented at the AI*PL Conference at Rochester, N.Y. in August, 1977. This paper investigates some problems associated with an argument evaluation order that we call "future" order, which is different from both call-by-name and call-by-value. In call-by-future, each formal parameter of a function is bound to a separate process (called a "future") dedicated to the evaluation of the corresponding argument. This mechanism allows the fully parallel evaluation of arguments to a function, and has been shown to augment the expressive power of a 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 being ignored in the body of the expression where they were bound. 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, stopped, and re-assigned to more useful tasks. The solution we propose is that of garbage collection. We propose that the goal structure of the solution plan be explicitly represented in memory as part of the graph memory (like Lisp's 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. MIT Artificial Intelligence Laboratory Department of Defense Advanced Research Projects Agency 2008-08-26T14:51:54Z 2008-08-26T14:51:54Z 1977-06 Working Paper http://hdl.handle.net/1721.1/41969 en_US MIT Artificial Intelligence Laboratory Working Papers, WP-149; application/pdf MIT Artificial Intelligence Laboratory |
| spellingShingle | "eager" evaluation "lazy" evaluation processor scheduling multiprocessing systems garbage collection Hewitt, Carl Baker, Henry G. Jr. The Incremental Garbage Collection of Processes |
| title | The Incremental Garbage Collection of Processes |
| title_full | The Incremental Garbage Collection of Processes |
| title_fullStr | The Incremental Garbage Collection of Processes |
| title_full_unstemmed | The Incremental Garbage Collection of Processes |
| title_short | The Incremental Garbage Collection of Processes |
| title_sort | incremental garbage collection of processes |
| topic | "eager" evaluation "lazy" evaluation processor scheduling multiprocessing systems garbage collection |
| url | http://hdl.handle.net/1721.1/41969 |
| work_keys_str_mv | AT hewittcarl theincrementalgarbagecollectionofprocesses AT bakerhenrygjr theincrementalgarbagecollectionofprocesses AT hewittcarl incrementalgarbagecollectionofprocesses AT bakerhenrygjr incrementalgarbagecollectionofprocesses |