Αλγόριθμοι Συλλογής Σκουπιδιών Για Αυτόματη Διαχείριση Μνήμης

Abstract

Αν και αρχικά περιοριζόταν στη γλώσσα Lisp και τις συναρτησιακές γλώσσες προγραμματισμού, σήμερα η συλλογή σκουπιδιών αποτελεί σημαντικό κομμάτι του συστήματος διαχείρισης μνήμης πολλών σύγχρονων γλωσσών, τόσο προστακτικών όσο και δηλωτικών. Παρά τη φήμη πως επιβραδύνει και διαταράσσει την εκτέλεση διαδραστικών εφαρμογών, οι σύγχρονες τεχνικές υλοποίησης της συλλογής σκουπιδιών έχουν μειώσει την επιβάρυνση σημαντικά, σε τέτοιο σημείο ώστε να αποτελεί ρεαλιστική επιλογή ακόμη και για παραδοσιακές γλώσσες προγραμματισμού όπως η C.Παρά την ταχεία ανάπτυξη του μεγέθους μνήμης ακόμη και των πιο φθηνών υπολογιστών, ο αποθηκευτικός χώρος δεν είναι ανεξάντλητος. Όπως όλοι οι περιορισμένοι πόροι απαιτεί προσεκτική συντήρηση και ανακύκλωση. Πολλές γλώσσεςπρογραμματισμού σήμερα επιτρέπουν την εκχώρηση και την ανάκτηση μνήμης από τονπρογραμματιστή για δεδομένα των οποίων η διάρκεια ζωής δεν καθορίζεται από την λεκτική εμβέλεια τους. Λέμε πώς τα δεδομένα αυτά εκχωρούνται δυναμικά. Η διαχείριση της δυναμικής μνήμης μπορεί να γίνεται ρητώς από τον προγραμματιστή, μέσω κλήσεων διαδικασιών ενσωματωμένων στο σύστημα εκτέλεσης ή διαδικασιώνβιβλιοθήκης που εκχωρούν αποθηκευτικό χώρο και τον ελευθερώνουν όταν αυτός δεν είναι πλέον απαραίτητος.Η χειρωνακτική ανάκτηση της δυναμικά διαχειριζόμενης μνήμης συχνά δεν είναι ικανοποιητική. Εναλλακτικά, η ευθύνη αυτής της διαχείρισης μπορεί να μεταβιβασθεί στο σύστημα εκτέλεσης του προγράμματος. Ο προγραμματιστής εξακολουθεί να πραγματοποιεί δυναμικά αιτήματα εκχώρησης μνήμης, χωρίς όμως πλέον να χρειάζεται να καθορίσει πότε αυτή η μνήμη δεν είναι πλέον απαραίτητη: αυτή ανακυκλώνεται αυτόματα. H \emph{συλλογή σκουπιδιών}, που αποτελεί το κεντρικό θέμα αυτής της εργασίας, είναι ακριβώς η αυτόματη διαχείριση δυναμικά εκχωρούμενου χώρου αποθήκευσης.Σκοπός αυτής της εργασίας είναι να αποτελέσει σημείο αναφοράς για τους αναγνώστες που ενδιαφέρονται να μάθουν σχετικά με την αυτόματη διαχείριση μνήμης. Το εισαγωγικό κεφάλαιο αρχικά εξετάζει και συγκρίνει την αυτόματη διαχείριση μνήμης και τη ρητή διαχείριση μνήμης, στη συνέχεια παρουσιάζει τις μετρικές με βάση τις οποίες συγκρίνονται τα διάφορα σχήματα συλλογής σκουπιδιώνκαι τέλος ορίζει τις έννοιες του εκχωρητή, του συλλέκτη και τουτροποποιητή. Το υπόλοιπο της εργασίας οργανώνεται σε δύο τμήματα. Στο πρώτο αρχικά συζητώνται οι κλασσικές προσεγγίσεις συλλογής σκουπιδιών: σήμανση και εκκαθάριση, σήμανση και συμπύκνωση, αντιγραφή και καταμέτρηση αναφορών, και στη συνέχεια γίνεται μία σύγκριση μεταξύ αυτών. Το δεύτερο μέρος επικεντρώνεται σε πιο προηγμένες τεχνικές συλλογής σκουπιδιών: γενεαλογική, παράλληλη και ταυτόχρονη συλλογή σκουπιδιών. Τέλος εισάγουμε τη συλλογή σκουπιδιών πραγματικού χρόνου.Η εργασία αυτή βασίζεται σε μετάφραση και προσαρμογή στα ελληνικά τμημάτωντου βιβλίου "The Garbage Collection Handbook: The Art of Automatic Memory Management", των R. Jones, A. Hosking και E. Moss.