| dbo:abstract
|
- Cheney's algorithm, first described in a 1970 ACM paper by C.J. Cheney, is a stop and copy method of tracing garbage collection in computer software systems. In this scheme, the heap is divided into two equal halves, only one of which is in use at any one time. Garbage collection is performed by copying live objects from one semispace (the from-space) to the other (the to-space), which then becomes the new heap. The entire old heap is then discarded in one piece. It is an improvement on the previous stop and copy technique. Cheney's algorithm reclaims items as follows:
* Object references on the stack. Object references on the stack are checked. One of the two following actions is taken for each object reference that points to an object in from-space:
* If the object has not yet been moved to the to-space, this is done by creating an identical copy in the to-space, and then replacing the from-space version with a forwarding pointer to the to-space copy. Then update the object reference to refer to the new version in to-space.
* If the object has already been moved to the to-space, simply update the reference from the forwarding pointer in from-space.
* Objects in the to-space. The garbage collector examines all object references in the objects that have been migrated to the to-space, and performs one of the above two actions on the referenced objects. Once all to-space references have been examined and updated, garbage collection is complete. The algorithm needs no stack and only two pointers outside of the from-space and to-space: a pointer to the beginning of free space in the to-space, and a pointer to the next word in to-space that needs to be examined. The data between the two pointers represents work remaining for it to do (those objects are gray in the tri-color terminology, see later). The forwarding pointer (sometimes called a "broken heart") is used only during the garbage collection process; when a reference to an object already in to-space (thus having a forwarding pointer in from-space) is found, the reference can be updated quickly simply by updating its pointer to match the forwarding pointer. Because the strategy is to exhaust all live references, and then all references in referenced objects, this is known as a breadth-first list copying garbage collection scheme. (en)
- Algorytm Cheneya, opisany po raz pierwszy w 1970 w artykule stowarzyszenia ACM przez , jest metodą odśmiecania pamięci w systemach softwarowych. W tym schemacie sterta jest podzielona na dwie połowy, z których w danym momencie tylko jedna jest w użyciu. Odśmiecanie pamięci odbywa się poprzez kopiowanie żywych obiektów z pierwszej połowy do drugiej, która następnie staje się nową stertą. Cała stara sterta zostaje odrzucona w jednym kawałku. Algorytm Cheneya odzyskuje elementy w następujący sposób:
* Referencje do obiektów na stosie. Sprawdzane są referencje do obiektów na stosie. Zostaje podjęte jedno z dwóch następujących działań dla każdej referencji do obiektu, która wskazuje na obiekt na starej stercie:
* Jeśli obiekt nie został jeszcze przeniesiony do nowej sterty, jest to realizowane poprzez stworzenie identycznej kopii na nowej stercie, a następnie zastąpienie wersji ze starej sterty przekierowującym wskaźnikiem do kopii. Następnie aktualizowana jest referencja obiektu aby odnosiła się do nowej wersji w nowej stercie.
* Jeśli obiekt został już przeniesiony do nowej sterty, po prostu aktualizuje się odwołanie według przekierowującego wskaźnika ze starej sterty.
* Obiekty w nowej stercie. Garbage collector sprawdza wszystkie odniesienia do obiektów w obiektach, które już zostały przeniesione do nowej sterty i wykonuje na nich jedno z dwóch powyższych działań. Gdy wszystkie odniesienia z nowej sterty zostały sprawdzone i zaktualizowane, odśmiecanie pamięci jest ukończone. Algorytm nie potrzebuje stosu i tylko dwa wskaźniki: wskaźnik do początku wolnego miejsca i wskaźnik następnego obiektu potrzebującego sprawdzenia, oba w nowej stercie. Z tego powodu jest on czasem nazywany „kolektorem o dwóch palcach” – wymaga jedynie „dwóch palców” wskazujących na nową stertę aby śledzić swój stan. Dane między dwoma palcami reprezentują pozostałą do zrobienia pracę. Kiedy jest już znalezione odniesienie do obiektu w nowej stercie (więc mające przekierowujący wskaźnik w starej stercie), odniesienie może być zaktualizowane szybko i prosto przez aktualizację wskaźnika według wskaźnika przekierowującego. (pl)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5608 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Cheney's algorithm, first described in a 1970 ACM paper by C.J. Cheney, is a stop and copy method of tracing garbage collection in computer software systems. In this scheme, the heap is divided into two equal halves, only one of which is in use at any one time. Garbage collection is performed by copying live objects from one semispace (the from-space) to the other (the to-space), which then becomes the new heap. The entire old heap is then discarded in one piece. It is an improvement on the previous stop and copy technique. Cheney's algorithm reclaims items as follows: (en)
- Algorytm Cheneya, opisany po raz pierwszy w 1970 w artykule stowarzyszenia ACM przez , jest metodą odśmiecania pamięci w systemach softwarowych. W tym schemacie sterta jest podzielona na dwie połowy, z których w danym momencie tylko jedna jest w użyciu. Odśmiecanie pamięci odbywa się poprzez kopiowanie żywych obiektów z pierwszej połowy do drugiej, która następnie staje się nową stertą. Cała stara sterta zostaje odrzucona w jednym kawałku. Algorytm Cheneya odzyskuje elementy w następujący sposób: (pl)
|
| rdfs:label
|
- Cheney's algorithm (en)
- Algorytm Cheneya (pl)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
