Συλλογή απορριμμάτων (υπολογιστές)

Στην πληροφορική, η συλλογή απορριμμάτων (αγγλ. garbage collection ή GC) είναι μια μορφή αυτόματης διαχείρισης μνήμης η οποία λειτουργεί στο υπόβαθρο, κατά την εκτέλεση ενός προγράμματος. Ο συλλέκτης απορριμμάτων (garbage collector), η απλώς συλλέκτης, είναι συνήθως ένα νήμα του συστήματος (π.χ. του λειτουργικού συστήματος ή μιας εικονικής μηχανής επί της οποίας εκτελείται το βασικό πρόγραμμα) σχεδιασμένο κάθε φορά που ενεργοποιείται να απελευθερώνει τα τρέχοντα απορρίμματα: τη μνήμη την οποία καταναλώνουν τα αντικείμενα που το πρόγραμμα δεν χρησιμοποιεί πια. Η συλλογή απορριμμάτων εφευρέθηκε από τον Τζον Μακάρθι το 1959 για να λύσει προβλήματα της γλώσσας προγραμματισμού Lisp.

Η συλλογή απορριμμάτων συχνά εμφανίζεται σαν το αντίθετο της χειροκίνητης διαχείρισης μνήμης, η οποία απαιτεί από τον προγραμματιστή να ορίζει ποια αντικείμενα μπορούν να απομακρυνθούν από τη μνήμη. Πολλά συστήματα όμως συνδυάζουν τις δύο προσεγγίσεις, μαζί με άλλες τεχνικές όπως η δέσμευση μνήμης στη στοίβα και η εξαγωγή περιοχών (region inference).

Περιορισμένοι πόροι εκτός της μνήμης, όπως π.χ. οι δικτυακές υποδοχές, τα χειριστήρια βάσεων δεδομένων (database handles), τα παράθυρα για αλληλεπίδραση με τον χρήστη και οι περιγραφείς αρχείων και συσκευών, δεν επηρεάζονται από τη συλλογή απορριμμάτων. Υπάρχουν άλλες μέθοδοι για τη διαχείριση αυτών των πόρων, όπως οι καταστροφείς, που μπορούν να διαχειριστούν ακόμα και τη μνήμη, με αποτέλεσμα να μην χρειάζεται συλλογή απορριμμάτων. Κάποια συστήματα συλλογής απορριμμάτων επιτρέπουν σε αυτούς τους άλλους πόρους να σχετίζονται με μια περιοχή στη μνήμη, η οποία, όταν συλλεχθεί, να προκαλέσει την αποδέσμευση των πόρων, κάτι που ονομάζεται οριστικοποίηση (finalization). Αυτό όμως μπορεί να προκαλέσει περιπλοκές, όπως οι σημαντικές καθυστερήσεις μεταξύ της παύσης της χρήσης και της αποδέσμευσης σημαντικά περιορισμένων πόρων, ή η έλλειψη ελέγχου σχετικά με το ποιο νήμα θα κάνει την αποδέσμευση.

Αρχές

Οι βασικές αρχές της συλλογής απορριμμάτων είναι:

1. Βρες τα δεδομένα του προγράμματος που δεν πρόκειται να προσπελαστούν στο μέλλον
2. Αποδέσμευσε τους πόρους που χρειάζονταν από τα αντικείμενα

Πολλές γλώσσες προγραμματισμού χρειάζονται συλλογή απορριμμάτων, είτε σαν μέρος του ορισμού της γλώσσας (για παράδειγμα η Java, η C# και οι περισσότερες γλώσσες σεναρίων) είτε στην πράξη σαν μέρος μιας ρεαλιστικής υλοποίησης (για παράδειγμα σε τυπικές γλώσσες όπως ο λ-λογισμός) – αυτές ονομάζονται γλώσσες με συλλογή απορριμμάτων (garbage collected languages). Άλλες γλώσσες έχουν σχεδιαστεί για χρήση με χειροκίνητη διαχείριση μνήμης αλλά υπάρχουν και υλοποιήσεις με συλλογή απορριμμάτων για αυτές (όπως για τη C ή τη C++). Κάποιες γλώσσες, όπως η Ada, η Modula-3 και η C++/CLI επιτρέπουν και συλλογή απορριμμάτων και χειροκίνητη διαχείριση μνήμης στην ίδια εφαρμογή, χρησιμοποιώντας διαφορετικούς σωρούς (heaps) για αντικείμενα που είτε αποδεσμεύονται αυτόματα, είτε η διαχείρισή τους γίνεται χειροκίνητα - άλλες, όπως η D, έχουν συλλογή απορριμμάτων αλλά επιτρέπουν στον χρήστη να διαγράψει χειροκίνητα ένα αντικείμενο και να απενεργοποιήσει εντελώς τη συλλογή απορριμμάτων, όταν χρειάζεται περισσότερη ταχύτητα. Αν και η ενσωμάτωση της συλλογής απορριμμάτων στον μεταγλωττιστή και στο σύστημα χρόνου εκτέλεσης (run time system ή runtime) δίνει περισσότερες επιλογές, υπάρχουν συστήματα συλλογής απορριμμάτων τύπου post hoc, με κάποια από αυτά να μην χρειάζονται επανάληψη της μεταγλώττισης. (Η Post-hoc συλλογή απορριμμάτων συνήθως ονομάζεται litter collection.) Ο συλλέκτης απορριμμάτων σχεδόν είναι στενά συνδεδεμένος με το σύστημα δέσμευσης μνήμης.

Πλεονεκτήματα

Η συλλογή απορριμμάτων απαλλάσσει τον προγραμματιστή από το να πρέπει να αποδεσμεύει ο ίδιος τη μνήμη. Αυτό έχει σαν αποτέλεσμα κάποιες κατηγορίες σφαλμάτων να αποκλείονται ή να είναι πιο δύσκολο να εμφανιστούν:

• Τα σφάλματα αιωρούμενου δείκτη (dangling pointer), που συμβαίνουν όταν μια θέση μνήμης αποδεσμεύεται αλλά εξακολουθούν να υπάρχουν δείκτες που δείχνουν σε αυτήν και ένας από αυτούς τους δείκτες χρησιμοποιείται στη συνέχεια από τον κώδικα. Τότε όμως η μνήμη μπορεί να έχει δεσμευτεί ξανά για άλλη χρήση και να περιέχει άλλα δεδομένα, με απροσδόκητα αποτελέσματα.
• Τα σφάλματα διπλής αποδέσμευσης (double free bugs), που συμβαίνουν όταν ένα πρόγραμμα προσπαθεί να αποδεσμεύσει μια περιοχή μνήμης που έχει ήδη αποδεσμευτεί (και πιθανόν να έχει δεσμευτεί πάλι για άλλο σκοπό).
• Κάποιες μορφές διαρροών μνήμης (memory leaks), στις οποίες ένα πρόγραμμα δε μπορεί να απελευθερώσει τη μνήμη που καταλαμβάνουν αντικείμενα που δεν είναι πια ορατά από τον κώδικα, με αποτέλεσμα, αν αυτό συνεχιστεί, η μνήμη να εξαντληθεί. (Η συλλογή απορριμμάτων συνήθως δεν ασχολείται με δεδομένα που είναι πολύ μεγάλα σε όγκο και το πρόγραμμα δεν τα χρησιμοποιεί αλλά μπορεί να τα δει.)

Κάποια από τα σφάλματα που αντιμετωπίζει η συλλογή απορριμμάτων μπορούν επίσης να οδηγούν και σε προβλήματα ασφάλειας.

Μειονεκτήματα

Συνήθως η συλλογή απορριμμάτων έχει κάποια μειονεκτήματα:

• Η συλλογή απορριμμάτων καταναλώνει υπολογιστικούς χώρους για να αποφασίσει ποια μνήμη θα αποδεσμεύσει, ανακαλύπτοντας πάλι πληροφορίες που μπορεί να είναι γνωστές στον προγραμματιστή. Αν δεν δοθεί ο χρόνος ζωής των αντικειμένων από τον προγραμματιστή, τότε το κόστος είναι μια υπολογιστική επιβάρυνση (overhead), που μπορεί να οδηγήσει σε αργή ταχύτητα εκτέλεσης. Η αλληλεπίδραση αυτής της επιβάρυνσης με τη μνήμη και την ιεραρχική δομή αυτής, μπορεί να οδηγήσει σε απαγορευτικές επιβαρύνσεις σε καταστάσεις που δεν αναμένονται ή δεν έχουν εντοπιστεί κατά τη δοκιμή του λογισμικού.
• Η στιγμή που γίνεται η συλλογή απορριμμάτων μπορεί να μην αναμένεται, με αποτέλεσμα να υπάρχουν καθυστερήσεις σε διάφορα χρονικά σημεία κατά την εκτέλεση του προγράμματος. Οι απρόβλεπτες καθυστερήσεις μπορεί να είναι απαράδεκτες σε περιβάλλοντα εφαρμογών πραγματικού χρόνου (real-time), στην επεξεργασία συναλλαγών ή σε προγράμματα που αλληλεπιδρούν με τον χρήστη.
• Ο προγραμματιστής δε μπορεί να χειρίζεται δείκτες (pointers), μόνο αναφορές (references).
• Η μη ντετερμινιστική συλλογή απορριμμάτων δεν είναι συμβατή με τη διαχείριση των πόρων που χρησιμοποιούνται κατά το προγραμματιστικό ιδίωμα RAII και δεν συλλέγονται αυτόματα. Αυτό έχει ως αποτέλεσμα τα αντικείμενα που δεν συλλέγονται αυτόματα να επηρεάζουν την αποδέσμευση των αντικειμένων που διαχειρίζεται η συλλογή απορριμμάτων, όταν αντικείμενα των δύο κατηγοριών συνδέονται μεταξύ τους.

Ανιχνευτική συλλογή απορριμμάτων

Οι ανιχνευτικοί συλλέκτες απορριμμάτων (tracing garbage collectors) είναι ο συνηθέστερος τύπος συλλεκτών απορριμμάτων. Αρχικά εντοπίζουν τα αντικείμενα που είναι προσιτά (reachable) ή αυτά που θα μπορούσαν να είναι προσιτά, και στη συνέχεια αποδεσμεύουν όλα τα υπόλοιπα αντικείμενα.

Προσιτότητα ενός αντικειμένου

Πρακτικά, ένα αντικείμενο είναι προσιτό αν αναφέρεται σε αυτό τουλάχιστον μια μεταβλητή του προγράμματος, είτε άμεσα, είτε μέσω αναφορών από άλλα προσιτά αντικείμενα. Ακριβέστερα, τα αντικείμενα μπορεί να είναι προσιτά με δύο μόνο τρόπους:

1. Τα αντικείμενα ενός συγκεκριμένου συνόλου θεωρούνται προσιτά και ονομάζονται ρίζες (roots). Συνήθως είναι τα αντικείμενα στα οποία υπάρχουν αναφορές οπουδήποτε στη στοίβα κλήσεων (δηλαδή όλες οι τυπικές μεταβλητές και οι παράμετροι των συναρτήσεων που καλούνται), καθώς και όλες οι καθολικές (global) μεταβλητές.
2. Κάθε αναφορά από ένα προσιτό αντικείμενο δείχνει και αυτή σε προσιτό αντικείμενο. Τυπικά, η προσιτότητα είναι μεταβατικό κλείσιμο (transitive closure).

Ο ορισμός της προσιτότητας των απορριμμάτων δεν είναι ο καλύτερος, γιατί ένα πρόγραμμα μπορεί να χρησιμοποιήσει ένα αντικείμενο για τελευταία φορά και μετά να μεσολαβήσει μεγάλο χρονικό διάστημα μέχρι την αποδέσμευσή του, επειδή δεν είναι πια ορατό στο τρέχον περιβάλλον του προγράμματος. Κάποιες φορές γίνεται διάκριση μεταξύ των συντακτικών απορριμμάτων (syntactic garbage), που είναι τα αντικείμενα που το πρόγραμμα δε μπορεί να δει, και των σημασιολογικών απορριμμάτων (semantic garbage), που είναι τα αντικείμενα που το πρόγραμμα δεν πρόκειται να χρησιμοποιήσει πάλι. Για παράδειγμα:

Object x = new Foo();
Object y = new Bar();
x = new Quux();
/* σε αυτό το σημείο γνωρίζουμε ότι το αντικείμενο Foo
 * που αρχικά δόθηκε σαν τιμή στη x δεν μπορεί πια
 * να χρησιμοποιηθεί: είναι συντακτικά απορρίμματα
 */

if(x.check_something()) {
 x.do_something(y);
}
System.exit(0);
/* στην παραπάνω ενότητα, η y *θα μπορούσε* να είναι σημασιολογικά
 * απορρίμματα, αλλά δεν το γνωρίζουμε, μέχρι η x.check_something()
 * να επιστρέψει κάποια τιμή (αν τελικά επιστρέψει)
 */

Το πρόβλημα του ακριβούς χαρακτηρισμού των σημασιολογικών απορριμμάτων μπορεί να αποδειχτεί ότι είναι μερικώς υπολογίσιμο: ένα πρόγραμμα που δεσμεύει μνήμη για ένα αντικείμενο X, εκτελεί ένα τυχαίο πρόγραμμα εισόδου P, και χρησιμοποιεί το X αν και μόνο αν το P τερματίζει θα απαιτούσε έναν συλλέκτη απορριμμάτων που θα έλυνε το πρόβλημα τερματισμού (halting problem). Αν και οι συντηρητικές ευριστικές μέθοδοι για τον εντοπισμό σημασιολογικών απορριμμάτων εξακολουθούν να αποτελούν ενεργό ερευνητικό πεδίο, οι περισσότεροι συλλέκτες απορριμμάτων στην πράξη στοχεύουν στη συλλογή συντακτικών απορριμμάτων.

Ένα άλλο θέμα είναι ότι σε γλώσσες προγραμματισμού που υπάρχουν και τύποι αναφοράς (reference types) και βασικοί τύποι τιμής (unboxed value types), ο συλλέκτης απορριμμάτων πρέπει με κάποιο τρόπο να μπορεί να ξεχωρίσει ποιες μεταβλητές της στοίβας ή ποια πεδία ενός αντικειμένου είναι τιμές και ποια είναι αναφορές: στη μνήμη μπορεί να μην υπάρχει διαφορά μεταξύ ενός ακεραίου και μιας αναφοράς. Ο συλλέκτης απορριμμάτων τότε πρέπει να γνωρίζει αν ένα στοιχείο είναι αναφοράς, ώστε να το ακολουθήσει, ή αν είναι βασική τιμή (primitive value). Μια συνηθισμένη λύση είναι η χρήση δεικτών με επιπλέον πληροφορία (tagged pointers).

Ισχυρές και ασθενείς αναφορές

Ο συλλέκτης απορριμμάτων μπορεί να αποδεσμεύει μόνο αντικείμενα προς τα οποία δεν υπάρχουν αναφορές. Μπορούν όμως να υπάρχουν κάποιες αναφορές, οι οποίες δεν εμποδίζουν την αποδέσμευση, οι οποίες ονομάζονται ασθενείς αναφορές (weak references). Όταν οι ασθενείς αναφορές συγκρίνονται με τις συνηθισμένες αναφορές, οι τελευταίες τότε μπορεί να ονομάζονται και ισχυρές αναφορές (strong references). Ένα αντικείμενο τότε συλλέγεται όταν δεν υπάρχουν ισχυρές (δηλαδή κανονικές) αναφορές, ακόμα και αν υπάρχουν ασθενείς αναφορές σε αυτό.

Μια ασθενής αναφορά δεν είναι απλά ένας οποιοσδήποτε δείκτης σε ένα αντικείμενο για το οποίο δεν ενδιαφέρεται ο συλλέκτης απορριμμάτων. Ο όρος συνήθως χρησιμοποιείται για μια ειδικά διαχειριζόμενη κατηγορία ειδικών αναφορών, που είναι ασφαλείς στη χρήση, ακόμα και όταν το αντικείμενό τους εξαφανιστεί, γιατί τότε αποκτούν κάποια ειδική και ασφαλή τιμή. Μια αναφορά που δεν είναι ασφαλής και ο συλλέτης απορριμμάτων δεν γνωρίζει για αυτήν, θα μείνει «αιωρούμενη» (dangling) γιατί θα συνεχίσει να αναφέρεται σε μια διεύθυνση μνήμης, όπου το αντικείμενο ήταν στο παρελθόν. Αυτό δεν είναι ασθενής αναφορά.

Ασθενείς συλλογές

Υπάρχουν αντικείμενα που διατηρούν δείκτες προς συλλογές από άλλα αντικείμενα και τα παρακολουθούν με ασθενή τρόπο. Για παράδειγμα, υπάρχουν ασθενείς πίνακες κατακερματισμού (weak hash tables). Όπως και σε έναν κανονικό πίνακα κατακερματισμού, σε έναν ασθενή πίνακα κατακερματισμού διατηρείται μια σχέση μεταξύ αντικειμένων σε ζεύγη, με κάθε ζεύγος να είναι ένα κλειδί και μια τιμή. Ο πίνακας κατακερματισμού όμως δε διατηρεί κάποια ισχυρή αναφορά προς αυτά τα αντικείμενα. Όταν ένα κλειδί ή μια τιμή γίνει απόρριμμα η εγγραφή στον πίνακα διαγράφεται στιγμιαία. Υπάρχουν επίσης περιπτώσεις τέτοιων πινάκων που έχουν μόνο ασθενή κλειδιά και οι αναφορές κλειδιών είναι ισχυρές ή το αντίθετο (ισχυρά κλειδιά και ασθενείς τιμές).

Οι ασθενείς πίνακες κατακερματισμού είναι σημαντικοί γιατί δίνουν τη δυνατότητα αποθήκευσης σχέσεων μεταξύ αντικειμένων, αλλά με τρόπο που τα αντικείμενα της σχέσης να μπορούν να γίνουν απορρίμματα αν τίποτα στο πρόγραμμα δεν έχει αναφορές προς αυτά (εκτός από τον ίδιο τον πίνακα). Αντίθετα, η χρήση ενός απλού πίνακα κατακερματισμού για αυτόν τον σκοπό θα οδηγούσε σε διαρροή μνήμης.

Βασικός αλγόριθμος

Η ανιχνευτική συλλογή απορριμμάτων ονομάζεται έτσι γιατί ανιχνεύει όλον τον χώρο εργασίας στη μνήμη. Η συλλογή γίνεται σε κύκλους. Ένας κύκλος αρχίζει όταν ο συλλέκτης αποφασίζει (ή λάβει ειδοποίηση) ότι χρειάζεται να αποδεσμεύσει μνήμη, κάτι που συνήθως συμβαίνει όταν το σύστημα δεν έχει μνήμη ελεύθερη. Η αρχική μέθοδος περιλάμβανε ένα απλό «μαρκάρισμα-και-σκούπισμα» (mark-and-sweep), στο οποίο όλος ο χώρος εργασίας εξετάζεται μία ή περισσότερες φορές.

Απλό μαρκάρισμα-και-σκούπισμα

Στο απλό μαρκάρισμα-και-σκούπισμα, κάθε αντικείμενο στη μνήμη έχει ένα πεδίο (συνήθως ένα bit) που προορίζεται για χρήση αποκλειστικά από τη συλλογή απορριμμάτων. Το πεδίο αυτό συνήθως είναι κενό, εκτός από τη διάρκεια του κύκλου συλλογής απορριμμάτων. Το πρώτο στάδιο της συλλογής διατρέχει ελεύθερα όλο το σύνολο των ριζών ('root set'), μαρκάροντας κάθε αντικείμενο προς το οποίο υπάρχει δείκτης, σαν σε χρήση ('in-use'). Επίσης μαρκάρονται και όλα τα αντικείμενα στα οποία δείχνουν τα αντικείμενα που ήδη μαρκαρίστηκαν, και ούτω καθεξής, μέχρι να μαρκαριστεί κάθε αντικείμενο στο οποίο μπορεί να φτάσει κανείς μέσω δεικτών από τις ρίζες. Στο τέλος, σκανάρεται όλη η μνήμη από την αρχή μέχρι το τέλος και εξετάζονται όλα τα ελεύθερα ή χρησιμοποιούμενα μέρη: όσα αντικείμενα εξακολουθούν να έχουν κενό το πεδίο 'σε χρήση', δεν είναι προσιτά από το πρόγραμμα ή τα δεδομένα του και η μνήμη που καταναλώνουν αποδεσμεύεται. (Στα αντικείμενα που έχουν μαρκαριστεί σαν 'σε χρήση', το πεδίο αυτό καθαρίζεται για τον επόμενο κύκλο συλλογής απορριμμάτων.)

Η μέθοδος αυτή έχει διάφορα μειονεκτήματα, με το κυριότερο να είναι ότι όλο το υπόλοιπο σύστημα πρέπει να σταματήσει κατά τη διάρκεια της συλλογής επειδή απαγορεύεται κάθε αλλαγή του χώρου της μνήμης. Αυτό έχει σαν αποτέλεσμα τα προγράμματα να 'παγώνουν' περιστασιακά (και απροειδοποίητα), αποκλείοντας έτσι τις εφαρμογές πραγματικού χρόνου. Επιπλέον, πρέπει να εξεταστεί όλη η μνήμη που χρησιμοποιείται, συχνά δύο φορές, κάτι που μπορεί να προκαλέσει προβλήματα σε συστήματα με μνήμη σε σελίδες (paged memory).

Μαρκάρισμα τριών χρωμάτων

Λόγω των προβλημάτων της προηγούμενης μεθόδου, οι περισσότεροι σύγχρονοι αλγόριθμοι ανιχνευτικής συλλογής απορριμμάτων υλοποιούν κάποια παραλλαγή του μαρκαρίσματος τριών χρωμάτων (tri-colour marking). Το μαρκάρισμα τριών χρωμάτων δουλεύει ως εξής:

1. Αρχικά δημιουργεί άσπρα, γκρίζα και μαύρα σύνολα, τα οποία θα χρησιμοποιηθούν για να κρατείται πληροφορία για την πρόοδο ενός κύκλου.
   • Το άσπρο σύνολο αρχικά είναι το σύνολο των αντικειμένων που είναι υποψήφια για να αποδεσμευτεί η μνήμη τους.
   • Το μαύρο σύνολο είναι το σύνολο των αντικειμένων που μπορεί εύκολα να δειχτεί ότι δεν δείχνουν σε αντικείμενα στο άσπρο σύνολο (σε πολλές υλοποιήσεις αρχικά είναι το κενό σύνολο).
   • Το γκρίζο σύνολο είναι όλα τα αντικείμενα που είναι προσιτά από αναφορές στις ρίζες αλλά τα αντικείμενα στα οποία δείχνουν τα γκρίζα αντικείμενα δεν έχουν ανιχνευτεί ακόμα. Τα γκρίζα αντικείμενα είναι γνωστό ότι είναι προσιτά από τις ρίζες, άρα δε μπορούν να θεωρηθούν απορρίμματα: τελικά τα γκρίζα αντικείμενα θα καταλήξουν στο μαύρο σύνολο. Το γκρίζο χρώμα σημαίνει ότι δεν έχουν ελεγχθεί ακόμα όλα τα αντικείμενα στα οποία δείχνει ένα αντικείμενο.
   • Το γκρίζο σύνολο αρχικά περιέχει τα αντικείμενα προς τα οποία υπάρχουν αναφορές από το επίπεδο των ριζών ενώ συνήθως όλα τα υπόλοιπα αντικείμενα τοποθετούνται αρχικά στο άσπρο σύνολο.
   • Τα αντικείμενα μπορούν να αλλάζουν χρώμα από άσπρο σε γκρίζο ή από γκρίζο σε άσπρο, ποτέ προς την άλλη κατεύθυνση.
2. Επιλέγεται ένα αντικείμενο από το γκρίζο σύνολο. Το αντικείμενο μετακινείται στο μαύρο σύνολο και τα άσπρα αντικείμενα στα οποία αναφέρεται άμεσα γίνονται γκρίζα. Αυτό σημαίνει ότι το αντικείμενο δε μπορεί θεωρηθεί απόρριμμα και το ίδιο ισχύει και για τα αντικείμενα στα οποία δείχνει.
3. Το προηγούμενο βήμα επαναλαμβάνεται μέχρι να αδειάσει το γκρίζο σύνολο.
4. Όταν δεν υπάρχουν άλλα αντικείμενα στο γκρίζο σύνολο, όλα τα αντικείμενα που μένουν στο άσπρο σύνολο είναι προφανώς μη προσιτά και ο χώρος που καταλαμβάνουν αποδεσμεύεται.

Τα 3 σύνολα χωρίζουν τη μνήμη, με κάθε αντικείμενο του συστήματος, συμπεριλαμβανομένων των ριζών, να ανήκει ακριβώς σε ένα από αυτά τα σύνολα.

Ο αλγόριθμος του μαρκαρίσματος τριών χρωμάτων διατηρεί την εξής σημαντική αναλλοίωτη (invariant):

Κανένα μαύρο αντικείμενο δεν δείχνει απευθείας σε άσπρο αντικείμενο.

Αυτό εγγυάται την ασφαλή καταστροφή των άσπρων αντικειμένων όταν αδειάσει το γκρίζο σύνολο. (Υπάρχουν εκδοχές του αλγορίθμου που δεν διατηρούν την παραπάνω αναλλοίωτη αλλά εξακολουθούν να ισχύουν οι βασικές ιδιότητες.)

Η μέθοδος των τριών χρωμάτων έχει ένα σημαντικό πλεονέκτημα: μπορεί να χρησιμοποιηθεί χωρίς το σύστημα να σταματά για μεγάλα χρονικά διαστήματα. Αυτό επιτυγχάνεται με το μαρκάρισμα αντικειμένων όταν αυτά δημιουργούνται και δεσμεύεται ο χώρος τους στη μνήμη, και κατά τη διάρκεια της τροποποίησής τους από το πρόγραμμα, διατηρώντας τα σύνολο. Το σύστημα μπορεί να παρακολουθεί το μέγεθος των συνόλων και να κάνει συλλογή απορριμμάτων περιοδικά, και όχι μόνο όταν χρειάζεται. Επίσης με αυτόν τον τρόπο αποτρέπεται η ανίχνευση όλου του χώρου εργασίας στη μνήμη σε κάθε κύκλο.

Στρατηγικές υλοποίησης

Για την υλοποίηση του βασικού αλγορίθμου τριών χρωμάτων πρέπει να ληφθούν κάποιες σημαντικές σχεδιαστικές αποφάσεις, οι οποίες επηρεάζουν σημαντικά την ταχύτητα της συλλογής απορριμμάτων.

Μετακίνηση

Όταν προσδιοριστεί το σύνολο των προσιτών αντικειμένων, η συλλογή απορριμμάτων μπορεί απλά να αποδεσμεύσει τη μνήμη που καταλαμβάνουν τα απρόσιτα αντικείμενα, και να αφήσουν όλη την υπόλοιπη μνήμη ως έχει, ή να αντιγράψει μερικά (ή όλα) τα προσιτά αντικείμενα σε έναν νέο χώρο στη μνήμη, ενημερώνοντας όλες τις αναφορές προς αυτά τα αντικείμενα. Αυτοί οι τρόποι συλλογής απορριμμάτων ονομάζονται «μη μετακινούντες» και «μετακινούντες» αντίστοιχα ("non-moving" και "moving", ή εναλλακτικά, "non-compacting" και "compacting").

Εκ πρώτης όψεως, μια στρατηγική συλλογής απορριμμάτων με μετακίνηση μπορεί να μοιάζει μη αποδοτική και αργή σε σχέση με τη στρατηγική που δεν μετακινεί, γιατί σε κάθε κύκλο κάνει παραπάνω δουλειά. Στην πράξη όμως η στρατηγική συλλογής απορριμμάτων με μετακίνηση οδηγεί σε πολλά πλεονεκτήματα όσον αφορά την ταχύτητα, τόσο κατά την ίδια τη συλλογή απορριμμάτων, όσο και κατά τη διάρκεια της εκτέλεσης του προγράμματος:

• Δεν χρειάζεται επιπλέον προσπάθεια για την αποδέσμευση του χώρου που καταλαμβάνουν τα νεκρά αντικείμενα: όλος ο χώρος της μνήμης, από τον οποίο μετακινήθηκαν αντικείμενα, θεωρείται ελεύθερος χώρος. Αντίθετα, η συλλογή απορριμμάτων χωρίς μετακίνηση πρέπει να επισκεφτεί κάθε απρόσιτο αντικείμενο και με κάποιον τρόπο να αποδεσμεύσει τη μνήμη του.
• Για τον ίδιο λόγο με παραπάνω, χώρος για νέα αντικείμενα μπορεί να δεσμευτεί πολύ γρήγορα. Επειδή η συλλογή απορριμμάτων με μετακίνηση δημιουργεί μεγάλους συνεχείς χώρους μνήμης, τα νέα αντικείμενα μπορούν να δεσμευτούν, αυξάνοντας απλά κατά ένα κάποιον δείκτη που δείχνει σε 'ελεύθερη μνήμη'. Αντίθετα, η συλλογή απορριμμάτων χωρίς μετακίνηση μπορεί μετά από κάποιο χρονικό διάστημα να οδηγήσει σε κατακερματισμό (fragmentation) του σωρού, με αποτέλεσμα να πρέπει να χρησιμοποιηθούν δαπανηρές «ελεύθερες λίστες» ("free lists"), που δείχνουν ποια μπλοκ μνήμης είναι διαθέσιμα για δέσμευση νέων αντικειμένων.
• Αν χρησιμοποιηθεί η κατάλληλη σειρά επίσκεψης των περιεχομένων της μνήμης (για παράδειγμα, στην περίπτωση των λιστών, η επίσκεψη σε κάθε κόμβο πριν τον προηγούμενο), τα αντικείμενα που αναφέρονται σε άλλα αντικείμενα συχνά μπορούν να μετακινηθούν πολύ κοντά το ένα στο άλλο στη μνήμη, αυξάνοντας την πιθανότητα να ανήκουν στην ίδια γραμμή κρυφής μνήμης (cache line), ή στην ίδια σελίδα εικονικής μνήμης (virtual memory). Αυτό μπορεί να κάνει την πρόσβαση σε αυτά τα αντικείμενα πολύ γρήγορη, μέσω αυτών των αναφορών.

Ένα μειονέκτημα της συλλογής απορριμμάτων με μετακίνηση είναι ότι επιτρέπει πρόσβαση μόνο μέσω αναφορών που διαχειρίζεται το περιβάλλον της συλλογής απορριμμάτων, και δεν επιτρέπει αριθμητική δεικτών. Αυτό συμβαίνει γιατί κάθε δείκτης προς ένα αντικείμενο δεν θα είναι έγκυρος όταν πια η συλλογή απορριμμάτων έχει μετακινήσει το αντικείμενο, και γίνεται αιωρούμενος δείκτης (dangling pointer). Για την επικοινωνία με τον κώδικα μηχανής, η συλλογή απορριμμάτων πρέπει να αντιγράψει τα περιεχόμενα του αντικειμένου σε μια θέση εκτός της μνήμης που συλλέγεται. Μια άλλη προσέγγιση είναι το αντικείμενο να είναι αμετακίνητο (pin), απαγορεύοντας στη συλλογή απορριμμάτων να το μετακινήσει και επιτρέποντας στη μνήμη να μοιράζεται μέσω απλών δεικτών (πιθανόν επιτρέποντας και την αριθμητική δεικτών).

Συλλογή με αντιγραφή, μαρκάρισμα-και-σκούπισμα και μαρκάρισμα-χωρίς-σκούπισμα

Οι συλλέκτες απορριμμάτων μπορούν να κατηγοριοποιηθούν ανάλογα με τον τρόπο που κρατούν τα τρία σύνολα αντικειμένων (άσπρα, γκρίζα και μαύρα) κατά τη διάρκεια ενός κύκλου συλλογής.

Η πιο ευθεία προσέγγιση είναι αυτή του συλλέκτη αντιγραφής (semi-space collector), η οποία ανάγεται στο 1969. Σε αυτόν τον τρόπο συλλογής απορριμμάτων με μετακίνηση, η μνήμη χωρίζεται σε δύο χώρους, στον χώρο-από ("from space") και στον χώρο-προς ("to space"). Αρχικά τα αντικείμενα βρίσκονται στον χώρο "to space" μέχρι να χρειαστεί συλλογή απορριμμάτων λόγω έλλειψης χώρου. Στην αρχή της συλλογής, ο "to space" γίνεται "from space" και αντίστροφα (εναλλάσσονται οι ρόλοι τους). Τα αντικείμενα που είναι προσιτά από το σύνολο των ριζών αντιγράφονται από τον "from space" στον "to space". Τα αντικείμενα αυτά σαρώνονται στη συνέχεια και όλα τα αντικείμενα στα οποία δείχνουν αντιγράφονται στον "to space", μέχρι όλα τα προσιτά αντικείμενα να αντιγραφούν εκεί. Όταν το πρόγραμμα συνεχίσει την εκτέλεσή του, τα νέα αντικείμενα δεσμεύονται πάλι στον "to space", μέχρι να γεμίσει και η διαδικασία να επαναληφθεί. Το πλεονέκτημα αυτής της προσέγγισης είναι η απλότητα (τα σύνολα των τριών χρωμάτων κατασκευάζονται έμμεσα κατά τη διαδικασία της αντιγραφής), αλλά έχει το μειονέκτημα ότι απαιτείται μια σχετικά μεγάλη και συνεχής περιοχή ελεύθερης μνήμης σε κάθε κύκλο συλλογής. Η τεχνική αυτή ονομάζεται και stop-and-copy. Ο αλγόριθμος του Cheney είναι βελτίωση του συλλέκτη αντιγραφής.

Ένας συλλέκτης απορριμμάτων με μαρκάρισμα και σκούπισμα (mark and sweep) κρατά ένα ή δύο bit σε κάθε αντικείμενο, τα οποία δείχνουν αν είναι μαύρο ή άσπρο. Το γκρίζο σύνολο διατηρείται είτε σαν ξεχωριστή λίστα (όπως η στοίβα της διεργασίας), είτε χρησιμοποιώντας κάποιο άλλο bit. Καθώς διατρέχεται το δέντρο των αναφορών κατά τη διάρκεια της συλλογής (η φάση του «μαρκαρίσματος»), αυτά τα bit ενημερώνονται από τον συλλέκτη για να αντικατοπτρίζουν την τρέχουσα κατάσταση. Στη συνέχεια ένα τελικό «σκούπισμα» της μνήμης αποδεσμεύει τα άσπρα αντικείμενα. Η στρατηγική μαρκαρίσματος και σκουπίσματος έχει το πλεονέκτημα ότι, όταν καθοριστεί το σύνολο των αντικειμένων που δεν είναι προσιτά, μπορεί να ακολουθηθεί μια στρατηγική μετακίνησης ή μη μετακίνησης -- η επιλογή αυτή μάλιστα μπορεί να γίνει ακόμα και κατά τον χρόνο εκτέλεσης, ανάλογα με τη διαθέσιμη μνήμη. Από την άλλη πλευρά, έχει το μειονέκτημα ότι αυξάνεται λίγο το μέγεθος των αντικειμένων.

Ένας συλλέκτης απορριμμάτων που μαρκάρει αλλά δεν σκουπίζει (mark and don't sweep) κρατά, όπως και στην προηγούμενη περίπτωση, ένα bit σε κάθε αντικείμενο για να θυμάται αν είναι άσπρο ή μαύρο -- το γκρίζο σύνολο διατηρείται είτε σαν ξεχωριστή λίστα ή με τη χρήση κάποιου άλλου bit. Υπάρχουν όμως δύο βασικές διαφορές.

• Τα χρώματα «μαύρο» και «άσπρο» σημαίνουν διαφορετικά πράγματα σε σχέση με τον συλλέκτη απορριμμάτων με μαρκάρισμα και σκούπισμα. Σε ένα σύστημα μαρκαρίσματος χωρίς σκούπισμα, όλα τα προσιτά αντικείμενα είναι πάντα μαύρα. Ένα αντικείμενο μαρκάρεται μαύρο όταν δεσμεύεται και μένει μαύρο, ακόμα και όταν δεν είναι πια προσιτό. Ένα άσπρο αντικείμενο είναι μνήμη που δε χρησιμοποιείται και μπορεί να δεσμευτεί.
• Η ερμηνεία του άσπρου/μαύρου bit μπορεί να αλλάξει. Αρχικά το άσπρο/μαύρο bit μπορεί να έχει τη σημασία (0=άσπρο, 1=μαύρο). Αν μια δέσμευση μνήμης δεν μπορέσει να βρει αρκετή (άσπρη) μνήμη, τότε αυτό σημαίνει ότι όλα τα αντικείμενα είναι μαρκαρισμένα σαν σε χρήση (μαύρα). Η σημασία του άσπρου/μαύρου bit τότε εναλλάσσεται (για παράδειγμα, 0=μαύρο, 1=άσπρο) και όλα τα αντικείμενα γίνονται άσπρα. Αυτό έχει σαν αποτέλεσμα να μην ισχύει εκείνη τη στιγμή η αναλλοίωτη ότι όλα τα προσιτά αντικείμενα είναι μαύρα, αλλά η πλήρης φάση μαρκαρίσματος που ακολουθεί τα ξανακάνει μαύρα. Όταν αυτό γίνει, όλη η μνήμη που δεν είναι προσιτή έχει γίνει άσπρη. Δεν χρειάζεται φάση «σκουπίσματος».

Συλλογή απορριμμάτων σε γενεές

Έχει παρατηρηθεί ότι σε πολλά προγράμματα, τα πρόσφατα δημιουργημένα αντικείμενα είναι και αυτά που είναι και πιο πιθανό να μην είναι προσιτά σύντομα, κάτι που είναι γνωστό και ως βρεφική θνησιμότητα (infant mortality) ή γενεαλογική υπόθεση (generational hypothesis). Η συλλογή απορριμμάτων σε γενεές (generational garbage collection ή ephemeral garbage collection) χωρίζει τα αντικείμενα σε γενεές και, στους περισσότερους κύκλους, θα τοποθετήσει μόνο τα αντικείμενα ενός υποσυνόλου των γενεών αυτών στο αρχικό άσπρο σύνολο. Επιπλέον, το σύστημα χρόνου εκτέλεσης διατηρεί πληροφορίες για τις αναφορές μεταξύ των γενεών, παρακολουθώντας τη δημιουργία και την ενημέρωση των αναφορών. Όταν εκτελείται ο συλλέκτης απορριμμάτων, μπορεί να χρησιμοποιήσει αυτήν την πληροφορία για να αποδείξει ότι κάποια αντικείμενα στο αρχικό άσπρο σύνολο δεν είναι προσιτά χωρίς να πρέπει να διατρέξει ολόκληρο το δέντρο των αναφορών. Αν η γενεαολογική υπόθεση ισχύει, αυτό έχει σαν αποτέλεσμα πιο γρήγορους κύκλους συλλογής, ενώ συλλέγονται τα πιο πολλά προσιτά αντικείμενα.

Για να υλοποιηθεί αυτή η ιδέα, πολλοί συλλέκτες απορριμμάτων αυτού του είδους χρησιμοποιούν διαφορετικές περιοχές μνήμης για αντικείμενα διαφορετικών ηλικιών. Όταν μια περιοχή γεμίσει, τα αντικείμενα στα οποία αναφέρονται περιοχές με μεγαλύτερη ηλικία αντιγράφονται στην επόμενη περιοχή, και ολόκληρη η περιοχή μπορεί τότε να χρησιμοποιηθεί για νέα αντικείμενα. Αυτή η τεχνική επιτρέπει πολύ γρήγορη σταδιακή (incremental) συλλογή απορριμμάτων, γιατί χρειάζεται μόνο συλλογή απορριμμάτων για μια περιοχή κάθε φορά.

Η συλλογή απορριμμάτων σε γενεές είναι μια ευριστική προσέγγιση και κάποια μη προσιτά αντικείμενα δε μπορούν να αποδεσμευτούν κατά τη διάρκεια κάθε κύκλου. Μπορεί επομένως σποραδικά να χρειάζεται να διενεργείται ένα πλήρες μαρκάρισμα και σκούπισμα ή μια συλλογή απορριμμάτων με αντιγραφή, για την αποδέσμευση όλου του διαθέσιμου χώρου. Τα συστήματα χρόνου εκτέλεσης των σύγχρονων γλωσσών προγραμματισμού (όπως η Java και το .NET Framework) συνήθως χρησιμοποιούν κάποια υβριδική στρατηγική που συνδυάζει τις στρατηγικές που ήδη αναφέρθηκαν. Για παράδειγμα, οι περισσότεροι κύκλοι συλλογής μπορεί να εξετάζουν μόνο κάποιες γενεές, ενώ κάποιες φορές συμβαίνει μαρκάρισμα και σκούπισμα, και ακόμα πιο σπάνια μια πλήρης αντιγραφή, ώστε να ελέγχεται ο κατακερματισμός (fragmentation). Οι όροι "minor cycle" και "major cycle" χρησιμοποιούνται κάποιες φορές για να περιγράψουν αυτά τα διαφορετικά επίπεδα συλλογής.

Stop-the-world, προσθετική και σύγχρονη συλλογή απορριμμάτων

Οι απλοί συλλέκτες απορριμμάτων σταματούν εντελώς την εκτέλεση του προγράμματος (stop-the-world) για να εκτελέσουν έναν κύκλο συλλογής, εξασφαλίζοντας ότι δεν θα δεσμευτούν νέα αντικείμενα, ούτε κάποια αντικείμενα πρόκειται να γίνουν απρόσιτα κατά τη συλλογή απορριμμάτων.

Το φανερό μειονέκτημα αυτής της τεχνικής είναι ότι το πρόγραμμα δεν μπορεί να συνεχίσει τις εργασίες του όταν γίνεται η συλλογή απορριμμάτων και προκύπτει μια παύση ("embarrassing pause"). Αυτό έχει σαν αποτέλεσμα η συλλογή απορριμμάτων τύπου stop-the-world να είναι κατάλληλη κυρίως για προγράμματα χωρίς αλληλεπίδραση με τον χρήστη. Το πλεονέκτημά της είναι ότι είναι πιο εύκολο να υλοποιηθεί και εκτελείται πιο γρήγορα σε σχέση με την προσθετική συλλογή απορριμμάτων.

Οι προσθετικοί (incremental) και οι σύγχρονοι (concurrent) συλλέκτες απορριμμάτων έχουν σχεδιαστεί έτσι ώστε να μειώνουν αυτήν την «αναστάτωση» κατά την εκτέλεση, παρεμβάλλοντας τις εργασίες τους στις δραστηριότητες του κύριου προγράμματος. Οι προσθετικοί συλλέκτες απορριμμάτων κάνουν συλλογή απορριμμάτων σε διακριτές φάσεις, επιτρέποντας την εκτέλεση του προγράμματος ανάμεσα στις φάσεις αυτές (και κάποιες φορές και κατά τη διάρκεια κάποιων από αυτές). Οι σύγχρονοι συλλέκτες απορριμμάτων δεν σταματούν καθόλου την εκτέλεση του προγράμματος, εκτός ίσως για το μικρό χρονικό διάστημα που σαρώνεται η στοίβα του προγράμματος. Όλες μαζί οι προσθετικές φάσεις όμως παίρνουν περισσότερο χρόνο για να εκτελεστούν, σε σύγκριση με ένα πέρασμα συνολικής συλλογής απορριμμάτων, επομένως οι συλλέκτες απορριμμάτων αυτού του είδους μπορεί να κάνουν λιγότερο έργο ανά μονάδα χρόνου.

Οι τεχνικές αυτές απαιτούν προσεκτική σχεδίαση ώστε να μην υπάρχουν ανεπιθύμητες αλληλεπιδράσεις μεταξύ του προγράμματος και του συλλέκτη απορριμμάτων. Για παράδειγμα, όταν το πρόγραμμα θελήσει να δεσμεύσει χώρο για κάποιο νέο αντικείμενο, το σύστημα χρόνου εκτέλεσης μπορεί να το σταματήσει μέχρι να ολοκληρωθεί η εκτέλεση, ή να ειδοποιήσει με κάποιον τρόπο τον συλλέκτη απορριμμάτων ότι υπάρχει ένα νέο, προσιτό αντικείμενο.

Ακριβής/συντηρητική συλλογή απορριμμάτων και εσωτερικοί δείκτες

Οι συλλέκτες που μπορούν να αναγνωρίσουν σωστά όλους τους δείκτες (αναφορές) σε ένα αντικείμενο ονομάζονται ακριβείς (precise, exact ή accurate), ενώ το αντίθετο είναι οι συντηρητικοί (conservative) ή μερικώς συντηρητικοί (partly conservative) συλλέκτες. Οι συντηρητικοί συλλέκτες υποθέτουν ότι κάθε αλληλουχία bit στη μνήμη μπορεί να είναι δείκτης αν, ερμηνευόμενη σαν δείκτης, θα έδειχνε σε κάποιο αντικείμενο που έχει δεσμευτεί στη μνήμη. Οι συντηρητικοί συλλέκτες μπορεί να αναγνωρίσουν σαν δείκτες λάθος δεδομένα (false positives), με αποτέλεσμα να μην αποδεσμεύεται μνήμη λόγω λάθους αναγνώρισης. Αυτό στην πράξη δεν είναι πάντα πρόβλημα, εκτός και αν το πρόγραμμα χειρίζεται πολλά δεδομένα που μπορούν να αναγνωριστούν λανθασμένα σαν δείκτες. Οι περιπτώσεις λανθασμένης αναγνώρισης προκαλούν γενικά λιγότερα προβλήματα σε συστήματα 64-bit σε σχέση με τα συστήματα 32-bit επειδή το εύρος των έγκυρων διευθύνσεων μνήμης τείνει να είναι ένα πολύ μικρό υποσύνολο του εύρους των τιμών 64-bit. Για αυτόν τον λόγο, είναι σπάνιο κάποια αλληλουχία των 64 bit να μοιάζει με κάποιον έγκυρο δείκτη. Το αν ένας ακριβής συλλέκτης απορριμμάτων εξυπηρετεί στην πράξη εξαρτάται από τις ιδιότητες ασφάλειας τύπων (type safety) της εκάστοτε γλώσσας προγραμματισμού. Ένα παράδειγμα που χρειάζεται συντηρητικός συλλέκτης απορριμμάτων είναι η γλώσσα C, η οποία επιτρέπει την μετατροπή μεταξύ δεικτών με τύπο (όχι void) και δεικτών χωρίς τύπο (void).

Ένα σχετικό θέμα είναι αυτό των εσωτερικών δεικτών (internal pointers), που είναι οι δείκτες στα πεδία ενός αντικειμένου. Αν η σημασιολογία της γλώσσας επιτρέπει εσωτερικούς δείκτες, τότε μπορούν να υπάρχουν πολλές διαφορετικές διευθύνσεις που να αναφέρονται σε μέρη του ίδιου αντικειμένου, κάτι που περιπλέκει την απόφαση αν ένα αντικείμενο είναι απόρριμμα ή όχι. Ένα παράδειγμα είναι η γλώσσα C++, στην οποία η πολλαπλή κληρονομικότητα μπορεί να δημιουργήσει δείκτες προς αντικείμενα βάσης, οι οποίοι να έχουν διαφορετικές διευθύνσεις. Ακόμα και σε γλώσσες όπως η Java, μπορούν να εμφανίζονται εσωτερικοί δείκτες κατά τον υπολογισμό, για παράδειγμα, της διεύθυνσης ενός στοιχείου ενός πίνακα. Σε ένα πρόγραμμα που έχει υποστεί βελτιστοποίηση, ο αντίστοιχος δείκτης στο ίδιο το αντικείμενο μπορεί να έχει ενημερωθεί στον καταχωρητή στον οποίο βρίσκεται – αυτό σημαίνει ότι πρέπει να γίνεται σάρωση που να βρίσκει αυτούς τους δείκτες.

Ταχύτητα εκτέλεσης

Οι ανιχνευτικοί συλλέκτες απορριμμάτων έχουν κάποια κρυμμένη επιβάρυνση κατά τον χρόνο εκτέλεσης, που δεν ελέγχεται από τον προγραμματιστή και μπορεί να οδηγήσει σε προβλήματα ταχύτητας εκτέλεσης. Για παράδειγμα, οι συλλέκτες stop-the-world που χρησιμοποιούνται συχνά, σταματούν αυθαίρετα την εκτέλεση του προγράμματος σε διάφορες χρονικές στιγμές, κάτι που μπορεί να κάνει τη συλλογή απορριμμάτων αυτού του είδους ακατάλληλη για κάποια ενσωματωμένα συστήματα, λογισμικών εξυπηρετητών υψηλής απόδοσης και εφαρμογές με απαιτήσεις πραγματικού χρόνου.

Ρητή δέσμευση μνήμης στον σωρό

• αναζήτηση καλύτερου/πρώτου-κατάλληλου μπλοκ με επαρκές μέγεθος
• διατήρηση λίστας ελεύθερου χώρου (free list)

Συλλογή απορριμμάτων

• εντοπισμός προσιτών αντικειμένων
• αντιγραφή προσιτών αντικειμένων στην περίπτωση των συλλεκτών αντιγραφής
• σύνορα ανάγνωσης/εγγραφής (read/write barriers) στην περίπτωση των προσθετικών συλλεκτών
• αναζήτηση καλύτερου/πρώτου-κατάλληλου μπλοκ και διατήρηση της λίστας ελεύθερου χρόνου στην περίπτωση των συλλεκτών χωρίς αντιγραφή

Είναι δύσκολο να συγκριθούν οι δύο παραπάνω προσεγγίσεις απευθείας, γιατί η συμπεριφορά τους εξαρτάται από το εκάστοτε περιβάλλον εκτέλεσης. Για παράδειγμα, στην καλύτερη περίπτωση συλλογής απορριμμάτων, η δέσμευση μνήμης απλά αυξάνει έναν δείκτη, ενώ στην καλύτερη περίπτωση ρητής δέσμευσης χώρου στον σωρό, ο μηχανισμός δέσμευσης μνήμης διατηρεί λίστες ελεύθερης μνήμης διαφόρων μεγεθών, με αποτέλεσμα η δέσμευση μνήμης απλά να ακολουθεί έναν δείκτη. Η κατηγοριοποίηση όμως αυτή της μνήμης σε χώρους διαφορετικών μεγεθών συχνά προκαλεί εξωτερικό κατακερματισμό σε σημαντικό βαθμό, κάτι που μπορεί να επηρεάσει αρνητικά την συμπεριφορά της κρυφής μνήμης. Η δέσμευση μνήμης σε μια γλώσσα με συλλογή απορριμμάτων μπορεί να υλοποιηθεί με δέσμευση στον σωρό στο παρασκήνιο (και όχι με την αύξηση ενός δείκτη), επομένως τα παραπάνω πλεονεκτήματα όσον αφορά την ταχύτητα μπορεί να μην ισχύουν πια. Σε κάποιες περιπτώσεις, όπως τα ενσωματωμένα συστήματα, η επιβάρυνση της συλλογής απορριμμάτων και της διαχείρισης του σωρού μπορεί να αποφευχθεί με δέσμευση μνήμης από πριν και χρήση ενός πιο ελαφρού συστήματος για δέσμευση/αποδέσμευση.

Η επιβάρυνση των συνόρων εγγραφής (write barriers) είναι πιο πιθανό να είναι εμφανής σε προγράμματα σε προστακτικό στυλ, τα οποία συχνά γράφουν δείκτες σε υπάρχουσες δομές δεδομένων, σε αντίθεση με τα προγράμματα σε συναρτησιακό στυλ, που κατασκευάζουν κάθε δεδομένο μια φορά και ποτέ δεν το αλλάζουν.

Οι εξελίξεις στη συλλογή απορριμμάτων συχνά σχετίζονται με ζητήματα ταχύτητας. Οι πρώτοι συλλέκτες απορριμμάτων ήταν τύπου stop-the-world, αλλά η ταχύτητα αυτής της προσέγγισης δεν ήταν κατάλληλη για εφαρμογές που αλληλεπιδρούσαν με τον χρήστη ή το περιβάλλον. Η προσθετική συλλογή απορριμμάτων απέφυγε αυτό το πρόβλημα, με το μειονέκτημα ότι είχε μικρότερη αποδοτικότητα λόγω της χρήσης συνόρων. Οι τεχνικές γενεαλογικής συλλογής απορριμμάτων χρησιμοποιούνται στους συλλέκτες stop-the-world και στους προσθετικούς για να αυξηθεί η ταχύτητά τους, με την παραδοχή ότι κάποια απορρίμματα θα αργήσουν να εντοπιστούν.

Ντετερμινισμός

• Η ανιχνευτική συλλογή απορριμμάτων δεν είναι ντετερμινιστική όσον αφορά τον χρόνο της λήξης ζωής των αντικειμένων (finalization). Ένα αντικείμενο που θεωρείται απόρριμμα, τελικά θα εκκαθαριστεί, αλλά δεν παρέχεται καμία εγγύηση για το πότε (ή ακόμα και το αν) αυτό θα γίνει. Αυτό έχει επιπτώσεις στην ορθότητα προγράμματος, όταν τα αντικείμενα συνδέονται με πόρους που δεν ανήκουν στη μνήμη, και η αποδέσμευση των οποίων αποτελεί εξωτερική συμπεριφορά του προγράμματος, όπως η διακοπή μιας σύνδεση δικτύου, η απελευθέρωση μιας συσκευής ή το κλείσιμο ενός αρχείου. Μια τεχνική συλλογής απορριμμάτων που παρέχει ντετερμινισμό σε αυτές τις περιπτώσεις είναι το καταμέτρηση αναφορών (reference counting).

• Η συλλογή απορριμμάτων μπορεί να έχει μη ντετερμινιστική επίδραση στον χρόνο εκτέλεσης, εισάγοντας κάποιες φορές παύσεις στην εκτέλεση του προγράμματος, οι οποίες δεν σχετίζονται με τον αλγόριθμο που εκτελείται. Στην ανιχνευτική συλλογή απορριμμάτων, μια αίτηση για δέσμευση χώρου στη μνήμη μπορεί να επιστρέψει κάποιο αποτέλεσμα αμέσως ή να οδηγήσει σε μια χρονοβόρα συλλογή απορριμμάτων. Στην καταμέτρηση αναφορών, αν και η δέσμευση μνήμης για αντικείμενα είναι συνήθως γρήγορη, η μείωση ενός μετρητή μιας αναφοράς είναι μη ντετερμινιστική, γιατί μπορεί να γίνει μηδέν και να οδηγήσει σε αναδρομική διάσχιση της μνήμης ώστε να μειωθούν και οι μετρητές των αναφορών των άλλων αντικειμένων στα οποία δείχνει το αντικείμενο.

Συλλογή απορριμμάτων σε πραγματικό χρόνο

Αν και η συλλογή απορριμμάτων είναι γενικά μη ντετερμινιστική, μπορεί να χρησιμοποιηθεί σε συστήματα αυστηρά πραγματικού χρόνου (hard real-time). Ένας συλλέκτης πραγματικού χρόνου μπορεί να εγγυηθεί ότι, στη χειρότερη περίπτωση, θα παραχωρήσει έναν συγκεκριμένο αριθμό υπολογιστικών πόρων στο τμήμα του προγράμματος που χρειάζεται τη μνήμη. Οι περιορισμοί που ακολουθεί ένας συλλέκτης πραγματικού χρόνου βασίζονται συνήθως είτε στον φόρτο εργασίας (work based), είτε στον χρόνο (time based). Ένας περιορισμός στον χρόνο θα μπορούσε να είναι ο εξής: σε κάθε χρονικό παράθυρο διάρκειας T, το πρόγραμμα θα πρέπει να εκτελείται τουλάχιστον για χρόνο Tm. Στην περίπτωση της ανάλυσης του φόρτου εργασίας, χρησιμοποιείται συνήθως το μέγεθος MMU (minimal mutator utilization).

Μια από τις πρώτες υλοποιήσεις συλλογής απορριμμάτων πραγματικού χρόνου για την JVM αφορούσε τον αλγόριθμο Metronome. Υπάρχουν επίσης άλλες εμπορικές υλοποιήσεις.

Καταμέτρηση αναφορών

Η καταμέτρηση αναφορών είναι μια μορφή συλλογής απορριμμάτων όπου κάθε αντικείμενο διατηρεί τον αριθμό των αντικειμένων που έχουν αναφορές προς αυτό. Τα απορρίμματα είναι όσα αντικείμενα έχουν μηδέν αναφορές. Ο μετρητής ενός αντικειμένου αυξάνεται όταν δημιουργείται μια αναφορά προς αυτό και μειώνεται όταν μια τέτοια αναφορά καταστρέφεται. Η μνήμη που καταλαμβάνει το αντικείμενο απελευθερώνεται όταν ο μετρητής φτάσει το μηδέν.

Η καταμέτρηση αναφορών έχει δύο σημαντικά μειονεκτήματα:

• Αν δύο ή περισσότερα αντικείμενα δείχνουν το ένα στο άλλο, μπορεί να δημιουργείται κύκλος, στον οποίο κανένας μετρητής δεν πρόκειται να φτάσει το μηδέν και η μνήμη κανενός αντικειμένου δεν πρόκειται να απελευθερωθεί. Κάποια συστήματα συλλογής απορριμμάτων με καταμέτρηση αναφορών (όπως αυτό της CPython) χρησιμοποιούν ειδικούς αλγόριθμους εντοπισμού κύκλων για να αντιμετωπίσουν αυτό το πρόβλημα. Μια άλλη στρατηγική είναι η χρήση ασθενών αναφορών (weak references) για τους δείκτες προς τα πίσω, οι οποίοι δημιουργούν τους κύκλους. Στην καταμέτρηση αναφορών, μια ασθενής αναφορά λειτουργεί όπως μια ασθενής αναφορά σε έναν ανιχνευτικό συλλέκτη απορριμμάτων. Είναι ένα ιδιαίτερο αντικείμενο-αναφορά, η ύπαρξη του οποίου δεν αυξάνει τον μετρητή αναφορών ενός αντικειμένου που δείχνει σε αυτό. Επιπλέον μια ασθενής αναφορά είναι ασθενής με την έννοια ότι όταν το αντικείμενο που αναφέρεται σε αυτήν γίνεται απόρριμμα, κάθε ασθενής αναφορά σε αυτό λήγει (lapses) αντί να μείνει αιωρούμενη, παίρνει δηλαδή κάποια προβλεπόμενη τιμή, όπως η κενή αναφορά (null).

• Στις απλές υλοποιήσεις, κάθε ανάθεση σε αναφορά και κάθε αναφορά που βγαίνει εκτός εμβέλειας, έχουν ως αποτέλεσμα την αλλαγή ενός ή περισσότερων μετρητών αναφορών. Στην πιο συνηθισμένη περίπτωση όμως, όταν μια αναφορά αντιγράφεται από μια μεταβλητή της εξωτερικής εμβέλειας σε μια μεταβλητή εσωτερικής εμβέλειας, τέτοια ώστε ο χρόνος ζωής της εσωτερικής μεταβλητής να περιλαμβάνεται στον χρόνο ζωής της εξωτερικής, δεν χρειάζεται η αλλαγή στους μετρητές. Η εξωτερική μεταβλητή «έχει» την αναφορά. Στην γλώσσα προγραμματισμού C++, η τεχνική αυτή υλοποιείται με τις αναφορές const. Η καταμέτρηση αναφορών στη C++ συνήθως υλοποιείται με τη χρήση «έξυπνων δεικτών» ("smart pointers"), που έχουν συναρτήσεις κατασκευής (constructors), καταστροφής (destructors) και ανάθεσης που χειρίζονται τις αναφορές. Ένας έξυπνος δείκτης μπορεί να περαστεί με αναφορά σε μια συνάρτηση, έτσι ώστε να μην χρειαστεί να κατασκευαστεί μια νέα αναφορά με αντιγραφή (που θα αύξανε τον μετρητή αναφορών κατά την είσοδο στη συνάρτηση και θα τον μείωνε κατά την έξοδο). Αντίθετα, η συνάρτηση δέχεται μια αναφορά στον έξυπνο δείκτη, την οποία τη δημιουργεί με μικρό κόστος.

• Οι αλλαγές αυτές (αύξηση και μείωση κατά ένα), όταν χρησιμοποιούνται σε πολυνηματικό περιβάλλον, πρέπει να είναι ατομικές λειτουργίες, όπως η compare-and-swap, όταν εμπλέκουν αντικείμενα που μπορεί να μοιράζονται ανάμεσα σε διαφορετικά νήματα. Οι ατομικές λειτουργίες έχουν κόστος στους πολυεπεξεργαστές και είναι ακόμα πιο δαπανηρές, όταν πρέπει να προσομοιωθούν από αλγόριθμους σε λογισμικό. Υπάρχουν τρόποι να βελτιωθεί αυτή η κατάσταση, όπως η χρήση αναφορών σε δύο επίπεδα, με πολλαπλούς μετρητές.

• Θεωρείται συχνά λανθασμένα ότι η καταμέτρηση αναφορών έχει ντετερμινιστική συμπεριφορά όσον αφορά το χρόνο εκτέλεσής του, σε σχέση με την ανιχνευτική συλλογή απορριμμάτων. Η καταμέτρηση αναφορών παρέχει ημι-ντετερμινιστική αποδοτικότητα όσον αφορά την αποδέσμευση σε περιπτώσεις που τα αντικείμενα προφανώς ζουν λίγο (στις ίδιες συνθήκες που και οι τεχνικές γενεαλογικής συλλογής απορριμμάτων έχουν ημι-ντετερμινιστική συμπεριφορά). Στην γενική περίπτωση, όταν μειώνεται ο μετρητής της αναφοράς ενός αντικειμένου, δεν μπορεί να μετρηθεί πόσος χρόνος θα χρειαστεί για αυτό από τον επεξεργαστή. Κάθε φορά που ένας μετρητής γίνεται μηδέν, και άρα το αντίστοιχο αντικείμενο γίνεται απόρριμμα, πρέπει να μειωθούν και όλοι οι μετρητές των αντικειμένων που ανήκουν στο αντικείμενο. Κάποιοι από αυτούς τους μετρητές μπορούν επίσης να γίνουν μηδέν, επαναλαμβάνοντας αυτήν τη διαδικασία, με αποτέλεσμα η καταμέτρηση αναφορών στην γενική περίπτωση να έχει μη ντετερμινιστικές παύσεις.

Escape analysis

Η ανάλυση διαφυγής (escape analysis) μπορεί να χρησιμοποιηθεί για να μετατρέψει τη δέσμευση χώρου στον σωρό σε δέσμευση στη στοίβα, μειώνοντας το έργο του συλλέκτη απορριμμάτων.

Συλλογή απορριμμάτων κατά τη μεταγλώττιση

Η συλλογή απορριμμάτων κατά τη μεταγλώττιση (compile-time garbage collection) είναι μια μορφή στατικής ανάλυσης που επιτρέπει στη μνήμη να επαναχρησιμοποιείται και να απελευθερώνεται με βάση αναλλοίωτες συνθήκες που είναι γνωστές από τη φάση της μεταγλώττισης. Αυτή η μορφή συλλογής απορριμμάτων μελετήθηκε στη γλώσσα προγραμματισμού Mercury.

Διαθεσιμότητα

Οι γλώσσες προγραμματισμού υψηλού επιπέδου είναι πιο πιθανό να έχουν σαν βασικό χαρακτηριστικό τη συλλογή απορριμμάτων. Οι γλώσσες που δεν περιλαμβάνουν συλλογή απορριμμάτων, μπορούν να την αποκτήσουν με τη βοήθεια εξωτερικών βιβλιοθηκών (όπως ο συλλέκτης απορριμμάτων του Boehm για τη C και τη C++). Αυτό δεν είναι πάντα χωρίς προβλήματα, αφού αλλάζουν οι μηχανισμοί δημιουργίας και καταστροφής των αντικειμένων.

Οι περισσότερες συναρτησιακές γλώσσες προγραμματισμού, όπως η ML, η Haskell και η APL, περιλαμβάνουν συλλογή απορριμμάτων. Ο ίδιος ο μηχανισμός εμφανίστηκε για πρώτη φορά στη Lisp, η οποία και εισήγαγε τον συναρτησιακό προγραμματισμό.

Άλλες δυναμικές γλώσσες, όπως η Ruby (αλλά όχι η Perl 5, ή η PHP, που χρησιμοποιούν καταμέτρηση αναφορών), τείνουν επίσης να χρησιμοποιούν συλλογή απορριμμάτων. Οι αντικειμενοστρεφείς γλώσσες όπως η Smalltalk, η Java και η ECMAScript συχνά ενσωματώνουν συλλογή απορριμμάτων. Εξαιρέσεις αποτελούν η C++ και η Delphi, οι οποίες έχουν συναρτήσεις καταστροφής (destructors). Η Objective-C στο παρελθόν δεν είχε συλλογή απορριμμάτων, αλλά η ObjC 2.0 που υλοποιήθηκε από την Apple για το Mac OS X χρησιμοποιεί έναν δικό της συλλέκτη στο χρόνο εκτέλεσης, ενώ το εγχείρημα GNUstep χρησιμοποιεί έναν συλλέκτη Boehm.

Ιστορικά, οι γλώσσες που απευθύνονταν σε αρχάριους, όπως η BASIC και η Logo, συχνά χρησιμοποιούσαν συλλογή απορριμμάτων για τύπους δεδομένων μεταβλητού μήκους που αποθηκεύονταν στον σωρό, όπως οι συμβολοσειρές και οι λίστες, ώστε να μην δυσκολεύουν τον προγραμματιστή με λεπτομέρειες διαχείρισης μνήμης. Στους πρώτους μικροϋπολογιστές, που είχαν μικρές μνήμες και αργούς επεξεργαστές, η συλλογή απορριμμάτων της BASIC συχνά προκαλούσε τυχαίες και (για τον χρήστη) ανεξήγητες παύσεις κατά την εκτέλεση του προγράμματος. Κάποιοι διερμηνείς της BASIC όπως ο Applesoft BASIC της οικογένειας των Apple II, είχαν πολύ αργούς συλλέκτες απορριμμάτων για τις συμβολοσειρές, που σάρωναν συνέχεια τις συμβολοσειρές για να τοποθετήσουν αυτές με την υψηλότερη διεύθυνση, στις υψηλότερες θέσεις μνήμης (high memory). Αυτή η επανάληψη για μια συμβολοσειρά κάθε φορά είχα σαν αποτέλεσμα πολυπλοκότητα χρόνου O(N*N) όσον αφορά τον αριθμό των συμβολοσειρών, που μπορούσε να διακόψει προσωρινά την εκτέλεση προγραμμάτων που έκαναν συχνή χρήση συμβολοσειρών, ακόμα και για ένα λεπτό. Ένας άλλος συλλέκτης απορριμμάτων για την Applesoft BASIC που δημοσιεύτηκε στο Call-A.P.P.L.E. (Ιανουάριος 1981, σελ. 40–45, Randy Wiggington) έβρισκε μια ομάδα συμβολοσειρών σε κάθε πέρασμα στον σωρό, με αποτέλεσμα μια παύση των δύο λεπτών να γίνεται ενός δευτερολέπτου, ανάλογα και με το μέγεθος της ομάδας. Δημοσιεύτηκαν και άλλες προσεγγίσεις, αλλά καμία δεν έφτασε να μπει σε κάποια νεότερη έκδοση του διερμηνέα της BASIC.

Περιορισμένα περιβάλλοντα

Η συλλογή απορριμμάτων σπάνια χρησιμοποιείται σε ενσωματωμένα συστήματα ή σε συστήματα πραγματικού χρόνου, όπου απαιτείται πολύ αυστηρός έλεγχος της χρήσης των περιορισμένων διαθέσιμων πόρων. Παρόλα αυτά, έχουν αναπτυχθεί συλλέκτες για τέτοια περιορισμένα περιβάλλοντα. Το .NET Micro Framework της Microsoft και η Java Platform, Micro Edition είναι ενσωματωμένες πλατφόρμες λογισμικού, οι οποίες, όπως και οι μεγαλύτερες εκδόσεις τους, περιλαμβάνουν συλλογή απορριμμάτων.

Βιβλιογραφία

• Jones, Richard· Hosking, Antony· Moss, Eliot (19 Αυγούστου 2011). The Garbage Collection Handbook: The Art of Automatic Memory Management. CRC Applied Algorithms and Data Structures Series. Chapman and Hall/CRC. ISBN 1420082795. 
• Jones, Richard· Lins, Rafael D. (1996). Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley. ISBN 0471941484. 
• Wilson, Paul R. (1992). «Uniprocessor Garbage Collection Techniques». IWMM '92 Proceedings of the International Workshop on Memory Management (Springer-Verlag). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2438. 

Εξωτερικοί σύνδεσμοι

• Τεχνικές Συλλογής απορριμμάτων στη Διαχείριση Μνήμης
• The Garbage Collection Handbook: The Art of Automatic Memory Management (Αγγλικά)
• Richard Jones' Garbage Collection Page, University of Kent (Αγγλικά)
• The Memory Management Reference (Αγγλικά)
• The Very Basics of Garbage Collection, by Thomas Padron-McCarthy (Αγγλικά)
• Publications by the OOPS group, University of Texas at Austin (Αγγλικά)
• A garbage collector for C and C++ by Hans Boehm (Αγγλικά)
• Expensive Explicit Deallocation: An Example by Hans Boehm (Αγγλικά)
• On-the-fly garbage collection: an exercise in cooperation by Edsger W. Dijkstra and Leslie Lamport and A.J.Martin and C.S.Scholten and E.F.M.Steffens (Αγγλικά)
• A Garbage Collection Course Curriculum at MSDN Academic Alliance (Αγγλικά)
• A Glance at Garbage Collection in Object-Oriented Languages (Αγγλικά)
• Notes on the CLR Garbage Collector (Αγγλικά)
• Understanding GC pauses in HotSpot JVM (Αγγλικά)

Υλοποιήσεις

• A Real-Time Garbage Collector Based on the Lifetimes of Objects by H. Lieberman and C. Hewitt, MIT Artificial Intelligence Laboratory (Αγγλικά)
• TinyGC - an independent implementation of the BoehmGC API (Αγγλικά)
• Conservative Garbage Collection Implementation for C Language by Yasin Hınıslıoğlu (Αγγλικά)
• MeixnerGC - an incremental mark and sweep garbage collector for C++ using smart pointers (Αγγλικά)