Τι είναι μια δωρεάν λίστα;

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

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

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

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

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

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

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