Ιεραρχίες μνήμης

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Εικονική μνήμη

Η εικονική μνήμη (virtual memory) παρουσιάζει στις διεργασίες παραπάνω μνήμη από αυτή που διαθέτει το σύστημα. Αυτό γίνεται χρησιμοποιώντας εικονικές διευθύνσεις (virtual addresses) οι οποίες μεταφράζονται σε πραγματικές από τη μονάδα διαχείρισης μνήμης (memory management unit).

Ο χώρος των εικονικών διευθύνσεων διαιρείται σε ίσα μέρη: τις σελίδες (pages).
Ο χώρος της φυσικής μνήμης (physical memory) διαιρείται αντίστοιχα σε πλαίσια σελίδας (page frames).
Ένα bit παρουσίας (present bit) για κάθε εικονική σελίδα δηλώνει αν η αντίστοιχη σελίδα βρίσκεται στην πραγματική μνήμη.
Αν δεν υπάρχει καλείται το λειτουργικό σύστημα με αιτία το λάθος παρουσίας (page fault).
Το λειτουργικό σύστημα πρέπει να αντικαταστήσει τη σελίδα με βάση τον πίνακα σελίδων (page table).
Αυτός μπορεί να οργανωθεί σε πολλαπλά επίπεδα ή και αντεστραμμένα για οικονομία μνήμης.
Η αποδοτικότητά της μετράται με βάση το ποσοστό επιτυχιών (hit ratio)

Πρόσβαση σε γραμμική μνήμη με βάση τις σελίδες στην αρχιτεκτονική του επεξεργαστή Pentium

Πεδία του κατάλογου σελίδων

Αντικατάσταση σελίδων

Η αντικατάσταση των σελίδων μπορεί να γίνει:

με αλγόριθμο βέλτιστης αντικατάστασης σελίδας (optimal page replacement algorithm) με βάση το χρόνο της μελλοντικής χρήσης της.
Ο θεωρητικά βέλτιστος αυτός αλγόριθμος είναι αδύνατο να υλοποιηθεί στην πράξη αφού προϋποθέτει πρόβλεψη της μελλοντικής συμπεριφοράς των διεργασιών.
με βάση τη σελίδα που δε χρησιμοποιήθηκε πρόσφατα (Not Recently Used).
- Κάθε σελίδα διαθέτει δύο bit τα οποία περιέχουν 1 αν η σελίδα αυτή έχει διαβαστεί ή γραφεί.
- Περιοδικά τα bit αυτά τίθενται σε 0 και με τον τρόπο αυτό μπορούν να βρεθούν σελίδες που δεν έχουν πρόσφατα χρησιμοποιηθεί.
- Η εγγραφή των bit μπορεί να γίνεται από τον επεξεργαστή, ή από το λειτουργικό σύστημα με τη χρήση του λάθους σελίδας σε κάθε πρώτη πρόσβαση μετά την εκκαθάρισή τους.
με βάση την αρχή πρώτη σελίδα μέσα πρώτη σελίδα έξω (first page in first page out) (FIFO)
με τον αλγόριθμο αντικατάστασης δεύτερης ευκαιρίας (second chance replacement algorithm).
Τροποποίηση του παραπάνω αλγορίθμου έτσι ώστε σελίδες που έχουν χρησιμοποιηθεί πρόσφατα όταν είναι υποψήφιες για αντικατάσταση να μεταφέρονται πάλι στην αρχή της ουράς.
με τον αλγόριθμο του ρολογιού.
Τροποποίηση του παραπάνω αλγορίθμου έτσι ώστε ο έλεγχος για τις σελίδες που έχουν χρησιμοποιηθεί να γίνεται κυκλικά και να μη μεταφέρονται στην αρχή της ουράς.
με βάση την αρχή λιγότερο πρόσφατα χρησιμοποιούμενης σελίδας (least recently used)
Κάθε σελίδα σχετίζεται με έναν μετρητή χρόνου ο οποίος περιέχει το χρόνο της τελευταίας πρόσβασης. Οι σελίδες με την παλιότερη πρόσβαση είναι αυτές που απομακρύνονται.
με βάση την αρχή λιγότερο συχνά χρησιμοποιούμενης σελίδας (not frequently used)
Κάθε σελίδα σχετίζεται με έναν μετρητή ο οποίος μετράει τον αριθμό των προσβάσεων στη σελίδα. Η σελίδες με τις λιγότερες προσβάσεις είναι αυτές που απομακρύνονται. Ο αλγόριθμος μπορεί να τροποποιηθεί με την προσθήκη της έννοιας της γήρανσης (aging) όπου οι μετρητές διαιρούνται με το 2 σε τακτικά χρονικά διαστήματα.

Σχεδιασμός σελιδοποίησης

Σύνολο εργασίας (working set) είναι το σύνολο των σελίδων που χρησιμοποιούνται από μια διεργασία μια δεδομένη χρονική στιγμή.
Όταν η διαθέσιμη μνήμη μιας διεργασίας είναι σημαντικά μικρότερη από το σύνολο εργασίας της τότε σημειώνεται απότομη πτώση της απόδοσης (thrashing)
Η προσέγγιση με βάση το μοντέλο συνόλου εργασίας (working set model) έχει την εξής βάση: πριν εκτελεστεί μια διεργασία καταβάλλεται προσπάθεια έτσι ώστε να βρίσκεται το σύνολο εργασίας της στη μνήμη.
Για το σκοπό αυτό φορτώνονται οι σελίδες στη μνήμη με τη διαδικασία της προσελιδοποίησης (prepaging).
H επιλογή της σελίδας που θα αντικατασταθεί μπορεί να γίνει είτε λαμβάνοντας υπόψη μόνο τις σελίδες της διαδικασίας στην οποία ανήκει το σφάλμα σελίδας υλοποιώντας δηλαδή έναν τοπικό αλγόριθμο αντικατάστασης σελίδων (local page replacement algorithm) ή κοιτάζοντας όλες τις σελίδες του λειτουργικού συστήματος υλοποιώντας δηλαδή έναν ολικό αλγόριθμο αντικατάστασης σελίδων (global page replacement algorithm).
Το μέγεθος της σελίδας είναι ευθέως ανάλογο με τη μνήμη που σπαταλάται σε σελίδες που είναι μερικώς μόνο γεμάτες και αντιστρόφως ανάλογο με το χώρο που απαιτείται για τη φύλαξη των πινάκων σελίδων και την ενδιάμεση μνήμη μνήμη μετάφρασης.

Επανεκκίνηση εντολής

Μια εντολή μηχανής μπορεί να διακοπεί στη μέση της εκτέλεσής της. Την επανεκκίνηση της εντολής

μπορεί να αναλάβει ο επεξεργαστής από το σημείο στο οποίο σταμάτησε ή
το λειτουργικό σύστημα από την αρχική της κατάσταση.

Θέματα υλοποίησης

Κλείδωμα σελίδων

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

Σελιδοποίηση κώδικα και δεδομένων

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

Διαμοιραζόμενες σελίδες

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

Διεργασία σελιδοποίησης

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

Βελτιστοποίηση

Η πρόσβαση στον κατάλογο σελίδων είναι ακριβή μια και αυτός βρίσκεται στην κύρια μνήμη. Για βελτιστοποίηση της ταχύτητας πρόσβασης πολλές αρχιτεκτονικές υλοποιούν έναν ενδιάμεσο ενταμιευτή μετάφρασης (translation lookaside buffer). Αυτός αποτελεί μια κρυφή μνήμη ειδικού τύπου για τους πίνακες των σελίδων που χρησιμοποιούνται συχνότερα. Ο τρόπος πρόσβασης στον ενδιάμεσο ενταμιευτή μετάφρασης είναι βελτιστοποιημένος για τις ανάγκες του συστήματος της σελιδοποίησης. Έτσι η πρόσβαση στις θέσεις του πίνακα βασίζεται μόνο στο τμήμα τις διεύθυνσης που απεικονίζει τη βάση της σελίδας.

Τμηματοποίηση

Μια αρχιτεκτονική μπορεί να υποστηρίξει πολλαπλά ανεξάρτητα γραμμικά τμήματα (segments) διευθύνσεων. Τα τμήματα αυτά μπορούν να χρησιμοποιηθούν για να ορίσουν ξεχωριστά:

κώδικα
στατικά δεδομένα
δυναμικά δεδομένα
στοίβα
βιβλιοθήκες κώδικα
πυρήνα του λειτουργικού συστήματος

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

Η προστασία ενός τμήματος μπορεί στις περισσότερες περιπτώσεις να ορίσει άδεια για:

εκτέλεση
ανάγνωση
εγγραφή

Ορισμός τμημάτων στην αρχιτεκτονική Pentium

Προστασία

Στενά συνδεδεμένο με την πρόσβαση στη μνήμη είναι το θέμα της προστασίας. Μερικοί τύποι προστασίας που υλοποιούνται σε αρχιτεκτονικές είναι οι παρακάτω:

Όρια πρόσβασης σε περιοχές της μνήμης

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

Πρόσβαση σε τύπους δεδομένων

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

Επίπεδα προστασίας

Για την αποδοτική υλοποίηση λειτουργικών συστημάτων ορίζονται επίπεδα προστασίας. Τυπικά το επίπεδο προστασίας Ν έχει πρόσβαση στα δεδομένα και τον κώδικα των επιπέδων Μ όπου Μ > Ν αλλά όχι και το αντίστροφο. Ένα παράδειγμα χρήσης πολλαπλών επιπέδων προστασίας παρουσιάζεται στην παρακάτω εικόνα:

Η μετάβαση ανάμεσα σε επίπεδα προστασίας γίνεται μέσω παγίδων, διακοπών, ή ειδικών δομών δεδομένων (π.χ. call gates).

Έλεγχος εντολών

Ορισμένα επίπεδα προστασίας μπορούν να επιτρέπουν ή να απαγορεύουν την εκτέλεση συγκεκριμένων εντολών. Μερικές κατηγορίες εντολών είναι οι παρακάτω:

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

Με την παγίδευση της εκτέλεσης συγκεκριμένων εντολών μπορεί το λειτουργικό σύστημα να υλοποιήσει εικονικές μηχανές (virtual machines).

Διαχείριση κρυφής μνήμης

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

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

Για όλες τις παραπάνω περιπτώσεις υπάρχουν συχνά ειδικές εντολές (π.χ. WBINVD στον Pentium) ή τύποι σελίδων ή τμημάτων που επιτρέπουν τον άμεσο έλεγχο της κρυφής μνήμης.

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

Andrew S. Tanenbaum Η αρχιτεκτονική των υπολογιστών: μια δομημένη προσέγγιση. Τρίτη αμερικάνικη έκδοση. σ. 375-465. Κλειδάριθμος 1995.
Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 103-198 Εκδόσεις Παπασωτηρίου, 1993.

Maurice J. Bach. The Design of the UNIX Operating System, pages 271–352. Prentice-Hall, 1986.
Bruce Javob and Trevor Mudge. Virtual memory: Issues of implementation. Computer, 31(6):33–43, June 1998.
Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System, pages 109–163. Addison-Wesley, 1988.
Andrew S. Tanenbaum. Operating Systems: Design and Implementation, pages 191–247. Prentice-Hall, 1987.

Περιεχόμενα