szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
Cheney's algorithm (tsz. Cheney's algorithms)
- (informatika) A Cheney-féle algoritmus egy híres garbage collection (szemétgyűjtés) algoritmus. Célja: automatikusan eltakarítani azokat a dinamikusan lefoglalt memóriaterületeket, amelyeket a program már nem használ → így elkerüljük a memória szivárgást (memory leak).
Az algoritmust 1970-ben C.J. Cheney publikálta. Fő jellemzője: egyszerű, gyors copying collector (másoló szemétgyűjtő) technika.
Előzmények — Mi az a garbage collection?
A garbage collection (GC) automatikusan felszabadítja a már nem használt memóriaterületeket.
Miért fontos?
- Ha nem szabadítod fel a memóriát → memória szivárgás (memory leak) → elfogy a memória → program lelassul vagy összeomlik.
Programozási nyelvek, amik gyakran használnak GC-t:
- Java
- C#
- JavaScript
- Python (bizonyos fokig)
- Lisp
- stb.
Hogyan működik általában a garbage collection?
- Mark: megjelöljük azokat a memóriaterületeket, amik elérhetők (gyökértől indulva → pl. globális változók, verem (stack), CPU regiszterek).
- Sweep: a többi memóriaterületet (ami nincs megjelölve) felszabadítjuk → szemét.
Ez az alapvető Mark & Sweep algoritmus.
Probléma: lehet, hogy a memória fragmentálódik → sok kis szabad terület, amit nehéz jól kihasználni.
Cheney’s algorithm — a copying collector
A Cheney-féle algoritmus másképp dolgozik:
- nem csak megjelöl → másolja az elérhető objektumokat egy új memória területre → így a memória kompakt marad → nem lesz fragmentáció.
Fő lépések:
- A heap két részre van osztva: From-space és To-space.
- Eleinte az összes objektum a From-space-ben van.
- Elindítjuk a GC-t → elérhető objektumokat átmásoljuk a To-space-be.
- Amikor az összes élő objektum a To-space-ben van → To-space lesz az új From-space → a régi From-space üres lesz → újrahasználható.
Memória felosztás
+------------------------+------------------------+
| From-space | To-space |
+------------------------+------------------------+
- Csak két félt kell fenntartani.
- Éppen az egyikben dolgozunk → másikba másolunk.
Részletes működés
1️⃣ Alapötlet
- Egy GC futásnál csak a To-space-et fogjuk feltölteni.
- Nem “takarítjuk ki” a From-space-t, csak átmásolunk.
2️⃣ Elindítás
- Elindítjuk a GC-t.
- Van egy gyökérhalmaz (root set): pl. globális változók, stack referenciai, regiszterek.
3️⃣ Copy + Forwarding
- Minden elérhető objektumot átmásolunk a To-space-be.
- Az eredeti helyére egy forwarding pointert teszünk → ha másik referencia is hivatkozik rá, nem kell újra másolni → a forwarding pointerre mutatunk.
4️⃣ Breadth-first másolás
Cheney algoritmusa breadth-first (szélességi bejárású) másolást végez.
Két mutató van:
scan: amit eddig már kimásoltunk → de a benne lévő referenciákat még nem dolgoztuk fel.free: az aktuális szabad hely a To-space-ben → ide másolunk.
Lépések:
- Kezdetben a root set-et másoljuk → To-space-be →
scan és free mutatók beállítva.
- Amíg
scan < free, feldolgozzuk a scan által mutatott objektumot:
- Ha az objektum referenciát tartalmaz → a referencia által mutatott objektumot is bemásoljuk (ha még nem tettük meg).
- Előrelépünk
scan-nel.
- Ha minden kész → az összes élő objektum a To-space-ben van → kész!
5️⃣ Flip (váltás)
- Miután a To-space tele van az élő objektumokkal → a szerepeket megfordítjuk:
- To-space → From-space (innentől innen fogunk dolgozni)
- Régi From-space → To-space → üres → készen áll a következő GC-re.
Miért jó a Cheney algoritmus?
✅ Egyszerű implementáció → kevés kód.
✅ Gyors allokáció:
- Új objektumot a To-space végére teszünk → egyszerű pointer bumping → nincs bonyolult szabad lista.
✅ Nincs fragmentáció:
- Minden élő objektumot folyamatosan helyezünk el → memória “szép tömbös” marad.
✅ O(élő objektumok mérete) → a GC futási ideje csak az élő adatok méretétől függ, nem a teljes heap méretétől!
Hátrányok
❌ Dupla memória kell (From-space + To-space):
- A heap felét sosem használjuk → a memóriaigény nagyobb.
❌ Copying overhead:
- Minden élő objektumot másolni kell → ez önmagában költség.
❌ Nem ideális, ha sok nagyméretű, hosszú életű objektum van (pl. cache-ek) → ezeket folyamatosan másolgatni kell.
Összefoglaló példa (pszeudokód)
initialize To-space and From-space
copy roots to To-space
scan = To-space.begin
free = To-space.end_of_copied_area
while (scan < free) {
for each reference in object at scan {
if referenced object not yet copied:
copy referenced object to free
set forwarding pointer
update reference
advance free
else:
update reference to forwarding pointer
}
advance scan
}
flip From-space and To-space
Összefoglalás
| Cheney’s Algorithm jellemző
|
Érték
|
| GC típusa
|
Copying collector
|
| Memória fragmentáció
|
Nincs
|
| Futási idő
|
Proporcionális az élő adatok méretéhez
|
| Bonyolultság
|
Alacsony
|
| Memóriaigény
|
Kétszeres heap
|
Mikor érdemes használni?
✅ Interpreterekben (pl. Lisp, Scheme, kis runtime-ok) ✅ VM-ekben (virtual machine), ahol gyors GC kell ✅ Rövid életű objektumokkal dolgozó programoknál ✅ Oktatási célra → könnyű implementálni, könnyű megérteni
Záró gondolat
A Cheney’s Algorithm egy klasszikus, elegáns szemétgyűjtő algoritmus, amely:
- egyszerű,
- hatékony,
- fragmentációmentes memóriakezelést biztosít.
Modern rendszerekben sok GC algoritmus kombinálja a copying és más technikákat (generational GC, incremental GC, stb.), de a Cheney algoritmus alapelve máig él sok interpreter és VM tervezésében.