Δυναμική δέσμευση μνήμης

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

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

Λεπτομέρειες 
Η διεκπεραίωση μιας αίτησης για δέσμευση μνήμης γίνεται με την εύρεση μιας ενότητας μνήμης που δε χρησιμοποιείται και έχει το απαραίτητο μέγεθος.

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

Συνήθως, η μνήμη δεσμεύεται από ένα μεγάλο τμήμα αχρησιμοποίητης μνήμης που ονομάζεται ο σωρός (the heap) ή ελεύθερος χώρος(free store). Επειδή η ακριβής θέση της δεσμευμένης μνήμης δεν είναι γνωστή εκ των προτέρων, η μνήμη προσπελαύνεται έμμεσα, συνήθως μέσω μιας αναφοράς δείκτη. Ο ακριβής αλγόριθμος που χρησιμοποιείται για να οργανώνεται ο χώρος της μνήμης και να δεσμεύονται και να αποδεσμεύονται τμήματα αυτής είναι συνήθως δε φαίνεται και η υλοποίησή του μπορεί να γίνεται με οποιαδήποτε από τις παρακάτω μεθόδους.

Απόδοση 
Ο αλγόριθμος δυναμικής δέσμευσης μνήμης που χρησιμοποιείται μπορεί να επηρεάσει σημαντικά την απόδοση του κώδικα και μια μελέτη που έγινε το 1994 από τη Digital Equipment Corporation δείχνει την υπολογιστική επιβάρυνση που συνδέεται με κάθε κώδικα που αναλαμβάνει τη δέσμευση. Το ελάχιστο μήκος μονοπατιού εντολών που χρειάστηκε για να δεσμευτεί ένας μοναδικός χώρος μνήμης ήταν 52 (όπως μετρήθηκε από έναν profiler για μια ποικιλία λογισμικού).

Υλοποιήσεις

Δέσμευση τμημάτων σταθερού μεγέθους 

Η δέσμευση τμημάτων σταθερού μεγέθους, γνωστή και σαν δέσμευση χώρου μνήμης (memory pool allocation), χρησιμοποιεί μια ελεύθερη λίστα από τμήματα μνήμης σταθερού μεγέθους (συχνά όλα είναι του ίδιου μεγέθους). Αυτό δουλεύει καλά για ενσωματωμένα συστήματα.

Buddy blocks 

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

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

Κατηγορίες μνήμης του προγράμματος 
Το πρόγραμμα μπορεί να χρησιμοποιεί διάφορα τμήματα στη μνήμη, όπως για παράδειγμα:
 μνήμη όπου αποθηκεύεται ο κώδικας του προγράμματος
 μνήμη όπου αποθηκεύονται οι μεταβλητές που δεσμεύονται με στατική (καθολικές) ή αυτόματη (τοπικές) διαχείριση μνήμης (στη δεύτερη περίπτωση συχνά η μνήμη ονομάζεται στοίβα ή stack)
 μνήμη όπου αποθηκεύονται οι μεταβλητές που δεσμεύονται με δυναμική διαχείριση μνήμης (σωρός, heap)

Δείτε επίσης 
 Δυναμικός πίνακας
 Αυτόματη δέσμευση μνήμης
 Επικίνδυνος δείκτης
 Υπερχείλιση σωρού
 Hoard memory allocator
 malloc
 mmap
 Δέσμευση μνήμης με στοίβα
 new (C++)

Εξωτερικοί σύνδεσμοι 
 Παράδειγμα bit-mapped arena memory allocator σε C 
 TLSF: κώδικας που δεσμεύει χώρο σε σταθερό χρόνο για χρήση σε συστήματα πραγματικού χρόνου (real-time) 
 Διαφάνειες για τη δυναμική δέσμευση μνήμης 
 Στο εσωτερικό της δέσμευσης μνήμης 
 Οπτικοποιημένη Δυναμική Δέσμευση Μνήμης, από τον Herbert Glarner, που περιγράφει αποδοτικές τεχνικές 
 Simple Memory Allocation Algorithms στην OSDEV Community

Περαιτέρω διάβασμα 
 "Dynamic Storage Allocation: A Survey and Critical Review", Department of Computer Sciences University of Texas at Austin
 Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.5: Dynamic Storage Allocation, pp. 435–456.

Παραπομπές 

Διαχείριση μνήμης
en:Memory management#Dynamic memory allocation