A Cheney-algoritmus egy szemétgyűjtő (garbage collection) technika, amelyet C. J. Cheney javasolt 1970-ben. Az algoritmus az automatikus memória-kezelés egyik hatékony módszere, amelyet elsősorban a félterület-alapú szemétgyűjtés (semispace garbage collection) megvalósítására használnak. Az algoritmus a dinamikusan lefoglalt objektumok élő halmazának másolásán alapul.
A memória két részre, úgynevezett félterületekre (semispaces) oszlik: 1. Aktív terület (from-space): A futó program által használt memória aktuális része. 2. Tartalék terület (to-space): Egy üres memóriaterület, amelyet a szemétgyűjtés során használnak az élő objektumok átmásolására.
A Cheney-algoritmus a következőképpen működik: 1. Az élő objektumokat (azokat az objektumokat, amelyek elérhetők a gyökérből) átmásolja a tartalék területre. 2. A másolás során a gyökérből indulva rekurzívan átmásolja az összes élő objektumot és azok hivatkozásait. 3. Az átmásolás után az eredeti aktív terület felszabadul, és a két terület szerepe felcserélődik.
Cheney(from_space, to_space, roots):
// Másoló mutatók inicializálása
allocate_ptr = to_space.start
scan_ptr = to_space.start
// Gyökér objektumok másolása
for root in roots:
root = CopyObject(root, allocate_ptr)
// Élő objektumok iteratív bejárása
while scan_ptr < allocate_ptr:
for reference in scan_ptr.references:
reference = CopyObject(reference, allocate_ptr)
scan_ptr += scan_ptr.size
// Területcsere
from_space, to_space = to_space, from_space
function CopyObject(object, allocate_ptr):
if object already copied:
return object.forwarding_address
new_object = allocate_ptr
copy object to allocate_ptr
object.forwarding_address = new_object
allocate_ptr += object.size
return new_object
Az alábbi egy egyszerű implementáció a Cheney-algoritmus működésének szimulálására:
class Object:
def __init__(self, name, references=):
self.name = name
self.references = references
self.forwarding_address = None
def cheney(from_space, to_space, roots):
allocate_ptr = 0
scan_ptr = 0
# Másolás gyökér objektumokhoz
for i, root in enumerate(roots):
roots = copy_object(root, from_space, to_space, allocate_ptr)
allocate_ptr += 1
# Iteratív bejárás
while scan_ptr < allocate_ptr:
current_object = to_space
for i, ref in enumerate(current_object.references):
current_object.references = copy_object(ref, from_space, to_space, allocate_ptr)
allocate_ptr += 1
scan_ptr += 1
return to_space
def copy_object(obj, from_space, to_space, allocate_ptr):
if obj is None:
return None
if obj.forwarding_address is not None:
return obj.forwarding_address
to_space = obj
obj.forwarding_address = allocate_ptr
return obj
# Példa objektumok
A = Object("A")
B = Object("B")
C = Object("C")
D = Object("D")
A.references =
B.references =
from_space =
to_space = * len(from_space)
roots =
# Futassuk az algoritmust
new_space = cheney(from_space, to_space, roots)
print("Átmásolt objektumok:", )
Kimenet:
Átmásolt objektumok:
A Cheney-algoritmus egy egyszerű és hatékony technika a dinamikus memória automatikus kezelésére. Bár memóriaterületet pazarol, lineáris futási ideje és az élő objektumok kezelésének garantált pontossága miatt széles körben alkalmazzák a szemétgyűjtési rendszerekben. Az algoritmus különösen hasznos nagy és dinamikus objektumhalmazok kezelésében, ahol a memóriahatékonyság kevésbé fontos, mint a sebesség és a megbízhatóság.