Wikiszótár

Cheney-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈhɛnɛiɒlɡoritmuʃ]

Főnév

Cheney-algoritmus

  1. (matematika)

Cheney-algoritmus

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.


Fő ötlet

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.


Lépések

1. Inicializálás

  • A memória két egyenlő méretű félterületre oszlik.
  • A program az aktív területet használja az objektumok allokálására.

2. Gyökérpontok mentése

  • A gyökérpontok (pl. globális változók vagy a verem lokális változói) azonosítása.

3. Másolás a tartalék területre

  • Az algoritmus a gyökérpontokból kiindulva átmásolja az objektumokat a tartalék területre.
  • A másolás során a hivatkozásokat is frissíti.

4. Iteratív bejárás

  • Egy másoló mutató (scan pointer) bejárja az összes átmásolt objektumot, és rekurzívan másolja azok hivatkozásait.

5. Területcsere

  • Miután minden élő objektum átmásolásra került, a két terület szerepe felcserélődik:
    • A tartalék terület válik az új aktív területté.
    • Az eredeti aktív terület felszabadul.


Pszeudokód

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

Példa működés

Bemenet:

  • Objektumok:
    • ( A ): gyökér objektum, hivatkozik ( B )-re és ( C )-re.
    • ( B ): hivatkozik ( D )-re.
    • ( C ): nincs hivatkozása.
    • ( D ): nincs hivatkozása.

Lépések:

  1. Gyökér átmásolása:
    • ( A ) átmásolása az új területre.
  2. Hivatkozások másolása:
    • ( B ) és ( C ) átmásolása az új területre.
    • ( D ) átmásolása az új területre ( B ) hivatkozása alapján.
  3. Területcsere:
    • A régi aktív terület felszabadul.


Python implementáció

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[i] = 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[scan_ptr]
        for i, ref in enumerate(current_object.references):
            current_object.references[i] = copy_object(ref, from_space, to_space, allocate_ptr)
            allocate_ptr += 1
        scan_ptr += 1

    return to_space[:allocate_ptr]

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[allocate_ptr] = 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, C]
B.references = [D]

from_space = [A, B, C, D]
to_space = [None] * len(from_space)
roots = [A]

# Futassuk az algoritmust
new_space = cheney(from_space, to_space, roots)
print("Átmásolt objektumok:", [obj.name for obj in new_space if obj is not None])

Kimenet: 

Átmásolt objektumok: ['A', 'B', 'C', 'D']

Előnyök

  1. Hatékonyság:
    • Az algoritmus lineáris időben fut ((O(n))), ahol (n) az élő objektumok száma.
  2. Egyszerűség:
    • A másolási szemétgyűjtés automatikusan kezeli a memóriát és felszabadítja a nem használt területet.
  3. Hivatkozások frissítése:
    • Az algoritmus automatikusan frissíti a hivatkozásokat az új memóriacímmel.


Hátrányok

  1. Memóriaigény:
    • A memória fele mindig tartalékként van fenntartva, ami növeli a memóriaigényt.
  2. Objektumok mozgatása:
    • Az objektumok átmásolása miatt a hivatkozások frissítése jelentős költséggel járhat.
  3. Csak élő objektumokra koncentrál:
    • Az algoritmus nem alkalmas nagy memóriaterületekhez, ha az objektumok nagy része szemét.


Alkalmazások

  1. Virtuális gépek:
    • Lisp, Java és más nyelvek futtatókörnyezeteiben használatos.
  2. Számítógépes grafikák:
    • Az élő objektumok hatékony kezelése animációk során.
  3. Beágyazott rendszerek:
    • Korlátozott memóriájú rendszerekben is hatékony.


Összegzés

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.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Cheney-algoritmus&oldid=3479580”