Οι ανιχνευτικοί συλλέκτες απορριμμάτων (tracing garbage collectors) είναι ο συνηθέστερος τύπος συλλεκτών απορριμμάτων. Αρχικά εντοπίζουν τα αντικείμενα που είναι προσιτά (reachable) ή αυτά που θα μπορούσαν να είναι προσιτά, και στη συνέχεια αποδεσμεύουν όλα τα υπόλοιπα αντικείμενα.
Πρακτικά, ένα αντικείμενο είναι προσιτό αν αναφέρεται σε αυτό τουλάχιστον μια μεταβλητή του προγράμματος, είτε άμεσα, είτε μέσω αναφορών από άλλα προσιτά αντικείμενα. Ακριβέστερα, τα αντικείμενα μπορεί να είναι προσιτά με δύο μόνο τρόπους:
- Τα αντικείμενα ενός συγκεκριμένου συνόλου θεωρούνται προσιτά και ονομάζονται ρίζες (roots). Συνήθως είναι τα αντικείμενα στα οποία υπάρχουν αναφορές οπουδήποτε στη στοίβα κλήσεων (δηλαδή όλες οι τυπικές μεταβλητές και οι παράμετροι των συναρτήσεων που καλούνται), καθώς και όλες οι καθολικές (global) μεταβλητές.
- Κάθε αναφορά από ένα προσιτό αντικείμενο δείχνει και αυτή σε προσιτό αντικείμενο. Τυπικά, η προσιτότητα είναι μεταβατικό κλείσιμο (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). Το μαρκάρισμα τριών χρωμάτων δουλεύει ως εξής:
- Αρχικά δημιουργεί άσπρα, γκρίζα και μαύρα σύνολα, τα οποία θα χρησιμοποιηθούν για να κρατείται πληροφορία για την πρόοδο ενός κύκλου.
- Το άσπρο σύνολο αρχικά είναι το σύνολο των αντικειμένων που είναι υποψήφια για να αποδεσμευτεί η μνήμη τους.
- Το μαύρο σύνολο είναι το σύνολο των αντικειμένων που μπορεί εύκολα να δειχτεί ότι δεν δείχνουν σε αντικείμενα στο άσπρο σύνολο (σε πολλές υλοποιήσεις αρχικά είναι το κενό σύνολο).
- Το γκρίζο σύνολο είναι όλα τα αντικείμενα που είναι προσιτά από αναφορές στις ρίζες αλλά τα αντικείμενα στα οποία δείχνουν τα γκρίζα αντικείμενα δεν έχουν ανιχνευτεί ακόμα. Τα γκρίζα αντικείμενα είναι γνωστό ότι είναι προσιτά από τις ρίζες, άρα δε μπορούν να θεωρηθούν απορρίμματα: τελικά τα γκρίζα αντικείμενα θα καταλήξουν στο μαύρο σύνολο. Το γκρίζο χρώμα σημαίνει ότι δεν έχουν ελεγχθεί ακόμα όλα τα αντικείμενα στα οποία δείχνει ένα αντικείμενο.
- Το γκρίζο σύνολο αρχικά περιέχει τα αντικείμενα προς τα οποία υπάρχουν αναφορές από το επίπεδο των ριζών ενώ συνήθως όλα τα υπόλοιπα αντικείμενα τοποθετούνται αρχικά στο άσπρο σύνολο.
- Τα αντικείμενα μπορούν να αλλάζουν χρώμα από άσπρο σε γκρίζο ή από γκρίζο σε άσπρο, ποτέ προς την άλλη κατεύθυνση.
- Επιλέγεται ένα αντικείμενο από το γκρίζο σύνολο. Το αντικείμενο μετακινείται στο μαύρο σύνολο και τα άσπρα αντικείμενα στα οποία αναφέρεται άμεσα γίνονται γκρίζα. Αυτό σημαίνει ότι το αντικείμενο δε μπορεί θεωρηθεί απόρριμμα και το ίδιο ισχύει και για τα αντικείμενα στα οποία δείχνει.
- Το προηγούμενο βήμα επαναλαμβάνεται μέχρι να αδειάσει το γκρίζο σύνολο.
- Όταν δεν υπάρχουν άλλα αντικείμενα στο γκρίζο σύνολο, όλα τα αντικείμενα που μένουν στο άσπρο σύνολο είναι προφανώς μη προσιτά και ο χώρος που καταλαμβάνουν αποδεσμεύεται.
Τα 3 σύνολα χωρίζουν τη μνήμη, με κάθε αντικείμενο του συστήματος, συμπεριλαμβανομένων των ριζών, να ανήκει ακριβώς σε ένα από αυτά τα σύνολα.
Ο αλγόριθμος του μαρκαρίσματος τριών χρωμάτων διατηρεί την εξής σημαντική αναλλοίωτη (invariant):
- Κανένα μαύρο αντικείμενο δεν δείχνει απευθείας σε άσπρο αντικείμενο.
Αυτό εγγυάται την ασφαλή καταστροφή των άσπρων αντικειμένων όταν αδειάσει το γκρίζο σύνολο. (Υπάρχουν εκδοχές του αλγορίθμου που δεν διατηρούν την παραπάνω αναλλοίωτη αλλά εξακολουθούν να ισχύουν οι βασικές ιδιότητες.)
Η μέθοδος των τριών χρωμάτων έχει ένα σημαντικό πλεονέκτημα: μπορεί να χρησιμοποιηθεί χωρίς το σύστημα να σταματά για μεγάλα χρονικά διαστήματα. Αυτό επιτυγχάνεται με το μαρκάρισμα αντικειμένων όταν αυτά δημιουργούνται και δεσμεύεται ο χώρος τους στη μνήμη, και κατά τη διάρκεια της τροποποίησής τους από το πρόγραμμα, διατηρώντας τα σύνολο. Το σύστημα μπορεί να παρακολουθεί το μέγεθος των συνόλων και να κάνει συλλογή απορριμμάτων περιοδικά, και όχι μόνο όταν χρειάζεται. Επίσης με αυτόν τον τρόπο αποτρέπεται η ανίχνευση όλου του χώρου εργασίας στη μνήμη σε κάθε κύκλο.
Για την υλοποίηση του βασικού αλγορίθμου τριών χρωμάτων πρέπει να ληφθούν κάποιες σημαντικές σχεδιαστικές αποφάσεις, οι οποίες επηρεάζουν σημαντικά την ταχύτητα της συλλογής απορριμμάτων.
Όταν προσδιοριστεί το σύνολο των προσιτών αντικειμένων, η συλλογή απορριμμάτων μπορεί απλά να αποδεσμεύσει τη μνήμη που καταλαμβάνουν τα απρόσιτα αντικείμενα, και να αφήσουν όλη την υπόλοιπη μνήμη ως έχει, ή να αντιγράψει μερικά (ή όλα) τα προσιτά αντικείμενα σε έναν νέο χώρο στη μνήμη, ενημερώνοντας όλες τις αναφορές προς αυτά τα αντικείμενα. Αυτοί οι τρόποι συλλογής απορριμμάτων ονομάζονται «μη μετακινούντες» και «μετακινούντες» αντίστοιχα ("non-moving" και "moving", ή εναλλακτικά, "non-compacting" και "compacting").
Εκ πρώτης όψεως, μια στρατηγική συλλογής απορριμμάτων με μετακίνηση μπορεί να μοιάζει μη αποδοτική και αργή σε σχέση με τη στρατηγική που δεν μετακινεί, γιατί σε κάθε κύκλο κάνει παραπάνω δουλειά. Στην πράξη όμως η στρατηγική συλλογής απορριμμάτων με μετακίνηση οδηγεί σε πολλά πλεονεκτήματα όσον αφορά την ταχύτητα, τόσο κατά την ίδια τη συλλογή απορριμμάτων, όσο και κατά τη διάρκεια της εκτέλεσης του προγράμματος:
- Δεν χρειάζεται επιπλέον προσπάθεια για την αποδέσμευση του χώρου που καταλαμβάνουν τα νεκρά αντικείμενα: όλος ο χώρος της μνήμης, από τον οποίο μετακινήθηκαν αντικείμενα, θεωρείται ελεύθερος χώρος. Αντίθετα, η συλλογή απορριμμάτων χωρίς μετακίνηση πρέπει να επισκεφτεί κάθε απρόσιτο αντικείμενο και με κάποιον τρόπο να αποδεσμεύσει τη μνήμη του.
- Για τον ίδιο λόγο με παραπάνω, χώρος για νέα αντικείμενα μπορεί να δεσμευτεί πολύ γρήγορα. Επειδή η συλλογή απορριμμάτων με μετακίνηση δημιουργεί μεγάλους συνεχείς χώρους μνήμης, τα νέα αντικείμενα μπορούν να δεσμευτούν, αυξάνοντας απλά κατά ένα κάποιον δείκτη που δείχνει σε 'ελεύθερη μνήμη'. Αντίθετα, η συλλογή απορριμμάτων χωρίς μετακίνηση μπορεί μετά από κάποιο χρονικό διάστημα να οδηγήσει σε κατακερματισμό (fragmentation) του σωρού, με αποτέλεσμα να πρέπει να χρησιμοποιηθούν δαπανηρές «ελεύθερες λίστες» ("free lists"), που δείχνουν ποια μπλοκ μνήμης είναι διαθέσιμα για δέσμευση νέων αντικειμένων.
- Αν χρησιμοποιηθεί η κατάλληλη σειρά επίσκεψης των περιεχομένων της μνήμης (για παράδειγμα, στην περίπτωση των λιστών, η επίσκεψη σε κάθε κόμβο πριν τον προηγούμενο), τα αντικείμενα που αναφέρονται σε άλλα αντικείμενα συχνά μπορούν να μετακινηθούν πολύ κοντά το ένα στο άλλο στη μνήμη, αυξάνοντας την πιθανότητα να ανήκουν στην ίδια γραμμή κρυφής μνήμης (cache line), ή στην ίδια σελίδα εικονικής μνήμης (virtual memory). Αυτό μπορεί να κάνει την πρόσβαση σε αυτά τα αντικείμενα πολύ γρήγορη, μέσω αυτών των αναφορών.
Ένα μειονέκτημα της συλλογής απορριμμάτων με μετακίνηση είναι ότι επιτρέπει πρόσβαση μόνο μέσω αναφορών που διαχειρίζεται το περιβάλλον της συλλογής απορριμμάτων, και δεν επιτρέπει αριθμητική δεικτών. Αυτό συμβαίνει γιατί κάθε δείκτης προς ένα αντικείμενο δεν θα είναι έγκυρος όταν πια η συλλογή απορριμμάτων έχει μετακινήσει το αντικείμενο, και γίνεται αιωρούμενος δείκτης (dangling pointer). Για την επικοινωνία με τον κώδικα μηχανής, η συλλογή απορριμμάτων πρέπει να αντιγράψει τα περιεχόμενα του αντικειμένου σε μια θέση εκτός της μνήμης που συλλέγεται. Μια άλλη προσέγγιση είναι το αντικείμενο να είναι αμετακίνητο (pin), απαγορεύοντας στη συλλογή απορριμμάτων να το μετακινήσει και επιτρέποντας στη μνήμη να μοιράζεται μέσω απλών δεικτών (πιθανόν επιτρέποντας και την αριθμητική δεικτών).[3]
Συλλογή με αντιγραφή, μαρκάρισμα-και-σκούπισμα και μαρκάρισμα-χωρίς-σκούπισμα
Επεξεργασία
Οι συλλέκτες απορριμμάτων μπορούν να κατηγοριοποιηθούν ανάλογα με τον τρόπο που κρατούν τα τρία σύνολα αντικειμένων (άσπρα, γκρίζα και μαύρα) κατά τη διάρκεια ενός κύκλου συλλογής.
Η πιο ευθεία προσέγγιση είναι αυτή του συλλέκτη αντιγραφής (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) στην περίπτωση των προσθετικών συλλεκτών
- αναζήτηση καλύτερου/πρώτου-κατάλληλου μπλοκ και διατήρηση της λίστας ελεύθερου χρόνου στην περίπτωση των συλλεκτών χωρίς αντιγραφή
Είναι δύσκολο να συγκριθούν οι δύο παραπάνω προσεγγίσεις απευθείας, γιατί η συμπεριφορά τους εξαρτάται από το εκάστοτε περιβάλλον εκτέλεσης. Για παράδειγμα, στην καλύτερη περίπτωση συλλογής απορριμμάτων, η δέσμευση μνήμης απλά αυξάνει έναν δείκτη, ενώ στην καλύτερη περίπτωση ρητής δέσμευσης χώρου στον σωρό, ο μηχανισμός δέσμευσης μνήμης διατηρεί λίστες ελεύθερης μνήμης διαφόρων μεγεθών, με αποτέλεσμα η δέσμευση μνήμης απλά να ακολουθεί έναν δείκτη. Η κατηγοριοποίηση όμως αυτή της μνήμης σε χώρους διαφορετικών μεγεθών συχνά προκαλεί εξωτερικό κατακερματισμό σε σημαντικό βαθμό, κάτι που μπορεί να επηρεάσει αρνητικά την συμπεριφορά της κρυφής μνήμης. Η δέσμευση μνήμης σε μια γλώσσα με συλλογή απορριμμάτων μπορεί να υλοποιηθεί με δέσμευση στον σωρό στο παρασκήνιο (και όχι με την αύξηση ενός δείκτη), επομένως τα παραπάνω πλεονεκτήματα όσον αφορά την ταχύτητα μπορεί να μην ισχύουν πια. Σε κάποιες περιπτώσεις, όπως τα ενσωματωμένα συστήματα, η επιβάρυνση της συλλογής απορριμμάτων και της διαχείρισης του σωρού μπορεί να αποφευχθεί με δέσμευση μνήμης από πριν και χρήση ενός πιο ελαφρού συστήματος για δέσμευση/αποδέσμευση.[4]
Η επιβάρυνση των συνόρων εγγραφής (write barriers) είναι πιο πιθανό να είναι εμφανής σε προγράμματα σε προστακτικό στυλ, τα οποία συχνά γράφουν δείκτες σε υπάρχουσες δομές δεδομένων, σε αντίθεση με τα προγράμματα σε συναρτησιακό στυλ, που κατασκευάζουν κάθε δεδομένο μια φορά και ποτέ δεν το αλλάζουν.
Οι εξελίξεις στη συλλογή απορριμμάτων συχνά σχετίζονται με ζητήματα ταχύτητας. Οι πρώτοι συλλέκτες απορριμμάτων ήταν τύπου stop-the-world, αλλά η ταχύτητα αυτής της προσέγγισης δεν ήταν κατάλληλη για εφαρμογές που αλληλεπιδρούσαν με τον χρήστη ή το περιβάλλον. Η προσθετική συλλογή απορριμμάτων απέφυγε αυτό το πρόβλημα, με το μειονέκτημα ότι είχε μικρότερη αποδοτικότητα λόγω της χρήσης συνόρων. Οι τεχνικές γενεαλογικής συλλογής απορριμμάτων χρησιμοποιούνται στους συλλέκτες stop-the-world και στους προσθετικούς για να αυξηθεί η ταχύτητά τους, με την παραδοχή ότι κάποια απορρίμματα θα αργήσουν να εντοπιστούν.
- Η ανιχνευτική συλλογή απορριμμάτων δεν είναι ντετερμινιστική όσον αφορά τον χρόνο της λήξης ζωής των αντικειμένων (finalization). Ένα αντικείμενο που θεωρείται απόρριμμα, τελικά θα εκκαθαριστεί, αλλά δεν παρέχεται καμία εγγύηση για το πότε (ή ακόμα και το αν) αυτό θα γίνει. Αυτό έχει επιπτώσεις στην ορθότητα προγράμματος, όταν τα αντικείμενα συνδέονται με πόρους που δεν ανήκουν στη μνήμη, και η αποδέσμευση των οποίων αποτελεί εξωτερική συμπεριφορά του προγράμματος, όπως η διακοπή μιας σύνδεση δικτύου, η απελευθέρωση μιας συσκευής ή το κλείσιμο ενός αρχείου. Μια τεχνική συλλογής απορριμμάτων που παρέχει ντετερμινισμό σε αυτές τις περιπτώσεις είναι το καταμέτρηση αναφορών (reference counting).
- Η συλλογή απορριμμάτων μπορεί να έχει μη ντετερμινιστική επίδραση στον χρόνο εκτέλεσης, εισάγοντας κάποιες φορές παύσεις στην εκτέλεση του προγράμματος, οι οποίες δεν σχετίζονται με τον αλγόριθμο που εκτελείται. Στην ανιχνευτική συλλογή απορριμμάτων, μια αίτηση για δέσμευση χώρου στη μνήμη μπορεί να επιστρέψει κάποιο αποτέλεσμα αμέσως ή να οδηγήσει σε μια χρονοβόρα συλλογή απορριμμάτων. Στην καταμέτρηση αναφορών, αν και η δέσμευση μνήμης για αντικείμενα είναι συνήθως γρήγορη, η μείωση ενός μετρητή μιας αναφοράς είναι μη ντετερμινιστική, γιατί μπορεί να γίνει μηδέν και να οδηγήσει σε αναδρομική διάσχιση της μνήμης ώστε να μειωθούν και οι μετρητές των αναφορών των άλλων αντικειμένων στα οποία δείχνει το αντικείμενο.
Συλλογή απορριμμάτων σε πραγματικό χρόνο
Επεξεργασία
Αν και η συλλογή απορριμμάτων είναι γενικά μη ντετερμινιστική, μπορεί να χρησιμοποιηθεί σε συστήματα αυστηρά πραγματικού χρόνου (hard real-time). Ένας συλλέκτης πραγματικού χρόνου μπορεί να εγγυηθεί ότι, στη χειρότερη περίπτωση, θα παραχωρήσει έναν συγκεκριμένο αριθμό υπολογιστικών πόρων στο τμήμα του προγράμματος που χρειάζεται τη μνήμη. Οι περιορισμοί που ακολουθεί ένας συλλέκτης πραγματικού χρόνου βασίζονται συνήθως είτε στον φόρτο εργασίας (work based), είτε στον χρόνο (time based). Ένας περιορισμός στον χρόνο θα μπορούσε να είναι ο εξής: σε κάθε χρονικό παράθυρο διάρκειας T, το πρόγραμμα θα πρέπει να εκτελείται τουλάχιστον για χρόνο Tm. Στην περίπτωση της ανάλυσης του φόρτου εργασίας, χρησιμοποιείται συνήθως το μέγεθος MMU (minimal mutator utilization).[5]
Μια από τις πρώτες υλοποιήσεις συλλογής απορριμμάτων πραγματικού χρόνου για την JVM αφορούσε τον αλγόριθμο Metronome.[6] Υπάρχουν επίσης άλλες εμπορικές υλοποιήσεις.[7]
