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

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

Ιστορικά

Το πρόβλημα με τα μεγαλύτερα από την μνήμη προγράμματα εμφανίστηκε από την αρχή της ύπαρξης των ηλεκτρονικών υπολογιστών. Μια λύση που υιοθετήθηκε το 1960 ήταν να χωρίσουν τα προγράμματα σε τμήματα, τα οποία ονομάστηκαν υπερθέματα. Όταν ξεκινούσε η εκτέλεση ενός προγράμματος, το μόνο που φορτώνονταν στην μνήμη ήταν ο διαχειριστής υπερθεμάτων, ο οποίος φόρτωνε και εκτελούσε αμέσως το υπέρθεμα 0 (μηδέν). Εν συνεχεία φορτώνονταν γραμμικά και τα υπόλοιπα υπερθέματα (1, 2, 3, ...) είτε αντικαθιστώντας τα προηγούμενα είτε στοιβάζοντάς τα (εφόσον υπήρχε διαθέσιμος χώρος). Αν και την πραγματική δουλειά της εναλλαγής των υπερθεμάτων από και προς την μνήμη την αναλάμβανε το λειτουργικό σύστημα, η διαίρεση των προγραμμάτων σε τμήματα ήταν στην ευθύνη του προγραμματιστή. Η διαίρεση των προγραμμάτων σε μικρά αυτόνομα τμήματα απαιτούσε πολύ χρόνο και παράλληλα ήταν επιρρεπής σε σφάλματα. Ένα χρόνο αργότερα, ο Fotheringham (Manchester University) ανέθεσε εξ ολοκλήρου την διαίρεση των προγραμμάτων σε τμήματα στο λειτουργικό σύστημα. Η μέθοδος αυτή είναι πλέον γνωστή ως εικονική μνήμη.

Εισαγωγή

Η εκτέλεση πολλών προγραμμάτων ταυτόχρονα έκανε αναγκαία την ύπαρξη εικονικής μνήμης στους Η/Υ διότι το μέγεθός των πρώτων ξεπερνούσε αυτό της φυσικής μνήμης (RAM). Έτσι χρησιμοποιήθηκε ένα κομμάτι του σκληρού δίσκου για να μπορούν να εκτελεστούν όλα τα προγράμματα ταυτόχρονα. Το κόστος της φυσικής μνήμης είναι πολύ μεγαλύτερο από αυτό ενός σκληρού δίσκου κάτι που εξηγεί γιατί αυτοί είναι πολύ μεγαλύτερης χωρητικότητας από τις μνήμες. Σήμερα το κόστος της μνήμης RAM έχει μειωθεί κατά πολύ και οι σύγχρονοι H/Y είναι εξοπλισμένοι με RAM άνω των 2GB. Καθώς όμως αυξάνεται το μέγεθος της μνήμης και οι αποδόσεις των Η/Υ, αυξάνονται και οι απαιτήσεις των εφαρμογών που εκτελούνται. Έτσι ακόμη και σήμερα είναι αναγκαία η ύπαρξη εικονικής μνήμης ακόμα και σε συστήματα που διαθέτουν 3-4GB φυσικής μνήμης. Σε ισχυρά συστήματα που διαθέτουν άνω των 4GB μνήμης RAM δεν είναι πάντα αναγκαία η ύπαρξη εικονικής μνήμης διότι ένας σκληρός δίσκος έχει πολύ χαμηλότερη ταχύτητα ανάγνωσης από την φυσική μνήμη, είτε πρόκειται για μηχανικό σκληρό δίσκο HDD (Hard Disk Drive) είτε για SSD (Solid State Drive). Έτσι η χρήση του ως εικονική μνήμη έχει σαν συνέπεια την καθυστέρηση στην επεξεργασία των δεδομένων.

Σελιδοποίηση

Η βασική ιδέα πίσω από την εικονική μνήμη είναι ότι κάθε πρόγραμμα έχει τον δικό του χώρο διευθύνσεων, ο οποίος διαιρείται σε μικρά κομμάτια που ονομάζονται σελίδες (pages). Κάθε σελίδα είναι ένα συνεχές εύρος διευθύνσεων. Οι σελίδες της εικονικής μνήμης χαρτογραφούνται στην φυσική μνήμη, αλλά δεν χρειάζεται να βρίσκονται όλες οι σελίδες στη μνήμη για να εκτελεστεί ένα πρόγραμμα. Οι διευθύνσεις που δημιουργούνται από τα προγράμματα ονομάζονται εικονικές διευθύνσεις και συνθέτουν τον χώρο εικονικών διευθύνσεων. Σε υπολογιστές που δεν υποστηρίζουν εικονική μνήμη, οι διευθύνσεις που παράγουν τα προγράμματα τοποθετούνται απευθείας στο δίαυλο της μνήμης και προκαλούν την ανάγνωση ή την εγγραφή της λέξης στη φυσική μνήμη με την ίδια διεύθυνση. Σε υπολογιστές με εικονική μνήμη οι εικονικές διευθύνσεις δεν τοποθετούνται αμέσως στον δίαυλο αλλά τοποθετούνται στη Μονάδα Διαχείρισης Μνήμης (MMU, Memory Management Unit) η οποία αναλαμβάνει την χαρτογράφηση των εικονικών διευθύνσεων σε διευθύνσεις φυσικής μνήμης.

Ακολουθεί ένα πολύ απλό παράδειγμα του τρόπου λειτουργίας αυτής της χαρτογράφησης. Ο χώρος των εικονικών διευθύνσεων διαιρείται σε μονάδες σταθερού μεγέθους οι οποίες ονομάζονται σελίδες (pages). Οι αντίστοιχες μονάδες στην φυσική μνήμη ονομάζονται πλαίσια σελίδας (page frames). Οι σελίδες και τα πλαίσια σελίδας έχουν, ως επί το πλείστον, το ίδιο μέγεθος. Όταν ένα πρόγραμμα καλεί μια εικονική διεύθυνση η μονάδα που ανέλαβε την χαρτογράφηση (MMU) ελέγχει αν η συγκεκριμένη διεύθυνση αντιστοιχίζεται στην φυσική μνήμη. Αν βρίσκεται τότε με βάση την αντιστοίχηση προσκομίζεται η ζητούμενη διεύθυνση. Τι θα συμβεί όμως αν το πρόγραμμα προσπαθήσει να αναφερθεί σε μια σελίδα που δεν έχει χαρτογραφηθεί στην φυσική μνήμη; Η MMU διαπιστώνει ότι η ζητούμενη σελίδα δεν αντιστοιχίζεται στην φυσική μνήμη και αναγκάζει την ΚΜΕ (Κεντρική Μονάδα Επεξεργασίας) να καταφύγει σε παγίδευση (trap) του λειτουργικού συστήματος. Η παγίδευση αυτή ονομάζεται σφάλμα σελίδας (page fault). Το λειτουργικό σ’ αυτή την περίπτωση επιλέγει ένα πλαίσιο σελίδας που έχει χρησιμοποιηθεί ελάχιστα και αποθηκεύει τα περιεχόμενά του στον δίσκο. Εν συνεχεία, προσκομίζει από τον δίσκο την ζητούμενη σελίδα και την τοποθετεί στο πλαίσιο σελίδας που μόλις ελευθερώθηκε. Τέλος επαναχαρτογραφείται η MMU και επανεκκινεί την εντολή που προκάλεσε την παγίδευση.

Μονάδα Διαχείρισης Μνήμης (MMU)

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

Πίνακες σελίδων

Η λειτουργία της MMU υλοποιείται με την χρήση των πινάκων σελίδων (page tables). Σε μία απλή υλοποίηση, η χαρτογράφηση των εικονικών διευθύνσεων σε φυσικές διευθύνσεις μπορεί να συνοψιστεί ως εξής: η εισερχόμενη εικονική διεύθυνση διαιρείται σε έναν αριθμό εικονικής σελίδας (bit υψηλής τάξης) και μια σχετική διεύθυνση (bit χαμηλής τάξης). Ο αριθμός της εικονικής σελίδας χρησιμοποιείται ως αριθμοδείκτης θέσης στον πίνακα σελίδων προκειμένου να εντοπίζεται η καταχώριση της συγκεκριμένης εικονικής σελίδας. Από την καταχώρηση του πίνακα σελίδων υπολογίζεται ο αριθμός του πλαισίου σελίδας (αν υπάρχει). Ο αριθμός πλαισίου σελίδας προσαρτάται στα αριστερά της σχετικής διεύθυνσης (πιο σημαντικά bit) αντικαθιστώντας τον αριθμό εικονικής σελίδας, ώστε να σχηματίσει μια φυσική διεύθυνση που μπορεί πλέον να σταλεί στη μνήμη. Από μαθηματική σκοπιά, ο πίνακας σελίδων είναι μια συνάρτηση, με όρισμα τον αριθμό εικονικής σελίδας και αποτέλεσμα τον αριθμό φυσικού πλαισίου.

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

Το μέγεθος της καταχώρησης ποικίλει ανάλογα με τον υπολογιστή αλλά το πιο συνηθισμένο είναι τα 32bit. Το σημαντικότερο πεδίο και αυτό που καταλαμβάνει και τον περισσότερο χώρο είναι ο αριθμός πλαισίου σελίδας, εφόσον ο σκοπός της χαρτογράφησης είναι να ληφθεί αυτή η τιμή ως έξοδος. Το επόμενο από τα αριστερά bit είναι αυτό της παρουσίας/απουσίας, αν το συγκεκριμένο bit είναι 1 τότε η καταχώρηση είναι έγκυρη και μπορεί να χρησιμοποιηθεί. Αν είναι 0 τότε προκαλείται σφάλμα σελίδας καθώς η εικονική σελίδα στην οποία ανήκει αυτή η καταχώρηση δε βρίσκεται στη μνήμη την συγκεκριμένη χρονική στιγμή. Τα bit προστασίας δηλώνουν τα είδη πρόσβασης που επιτρέπονται. Συνήθως είναι 3 bit, καθένα από τα οποία επιτρέπει ή όχι ( 0 ή 1 ) την ανάγνωση, την εγγραφή και την εκτέλεση αντίστοιχα. Τα bit τροποποίησης διατηρούν πληροφορίες για τη χρήση της σελίδας όπου χρησιμεύουν κυρίως κατά την απόσυρση του πλαισίου από τη μνήμη και την εγγραφή του στο δίσκο. Το bit αναφοράς χρησιμοποιείται κατά την επιλογή από το λειτουργικό σύστημα της σελίδας που πρόκειται να αφαιρεθεί από τη μνήμη όταν συμβεί σφάλμα σελίδας καθώς παίρνει τιμή 1 κάθε φορά που γίνεται αναφορά στη συγκεκριμένη σελίδα, γεγονός που βοηθά στο να επιλέγονται σελίδες που δεν έχουν χρησιμοποιηθεί πρόσφατα. Το τελευταίο bit επιτρέπει την απενεργοποίηση της κρυφής μνήμης για τη σελίδα αυτή, το οποίο είναι σημαντικό για σελίδες που χαρτογραφούνται σε καταχωρητές συσκευών και όχι στη μνήμη. Κάτι σημαντικό που πρέπει να διευκρινιστεί εδώ είναι ότι η διεύθυνση στο δίσκο όπου αποθηκεύεται η σελίδα όταν δεν βρίσκεται στη μνήμη , δεν αποτελεί μέρος του πίνακα σελίδων καθώς ο πίνακας σελίδων διατηρεί μόνο πληροφορίες που χρειάζονται στο υλικό για τη μετάφραση μίας εικονικής διεύθυνσης σε φυσική, ενώ οι πληροφορίες που χρειάζονται στο λειτουργικό σύστημα για τη διαχείριση των σφαλμάτων σελίδας διατηρούνται σε πίνακες λογισμικού και είναι άχρηστες για το υλικό.

Επιτάχυνση της σελιδοποίησης

Σε οποιοδήποτε σύστημα σελιδοποίησης, υπάρχουν δύο σημαντικά ζητήματα που πρέπει να αντιμετωπιστούν:

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

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

Κρυφή μνήμη αναζήτησης μετάφρασης

Παρακάτω αναφέρονται ευρέως χρησιμοποιούμενες μέθοδοι υλοποίησης για την επιτάχυνση της σελιδοποίησης. Το βασικό για τις περισσότερες τεχνικές βελτιστοποίησης είναι ότι ο πίνακας σελίδων βρίσκεται στη μνήμη. Ο σχεδιασμός αυτός είναι σημαντικός στην απόδοση. Οι σχεδιαστές των υπολογιστών γνωρίζουν το πρόβλημα αυτό και έχουν καταλήξει σε μια λύση. Η λύση βασίζεται στην παρατήρηση ότι τα περισσότερα προγράμματα συνήθως κάνουν πολλές αναφορές σε ελάχιστο αριθμό σελίδων και όχι το αντίστροφο. Επομένως μόνο ένα μικρό κλάσμα των καταχωρίσεων του πίνακα σελίδων διαβάζονται συχνά ενώ οι υπόλοιπες χρησιμοποιούνται ελάχιστα έως καθόλου. Η λύση ήταν να εξοπλιστούν οι υπολογιστές με μια μικρή συσκευή υλικού που χρησιμεύει στη χαρτογράφηση των εικονικών διευθύνσεων σε φυσικές χωρίς να χρησιμοποιεί τον πίνακα σελίδων. Η συσκευή ονομάζεται TLB (Translation Lookaside Buffer-Κρυφή μνήμη αναζήτησης μετάφρασης) ή συνειρμική ή συσχετιστική μνήμη (associative memory).

Λειτουργία και διαχείριση της TLB

Όταν μια εικονική διεύθυνση μεταφέρεται στην MMU προκειμένου να μεταφραστεί, γίνεται έλεγχος αν ο αριθμός της εικονικής σελίδας υπάρχει στην TLB με παράλληλη σύγκριση όλων των καταχωρήσεων. Εφόσον υπάρχει και αφού η πρόσβαση δεν παραβιάζει τα bit προστασίας, το πλαίσιο σελίδας λαμβάνεται απευθείας από την TLB χωρίς να χρησιμοποιηθεί ο πίνακας σελίδων. Αν όμως ο αριθμός της εικονικής σελίδας υπάρχει στην TLB σημαίνει ότι η εντολή προσπαθεί να κάνει εγγραφή σε σελίδα όπου επιτρέπεται μόνον η ανάγνωση. Επομένως προκύπτει σφάλμα προστασίας. Στις σύγχρονες μηχανές RISC (όπως οι SPARC, MIPS και η HP PA) όλη η διαχείριση σελίδων υλοποιείται με λογισμικό, η TLB φορτώνεται από το λειτουργικό σύστημα και όταν συμβαίνει κάποια αστοχία TLB προκύπτει απλώς σφάλμα TLB. Επομένως και σ’ αυτήν την περίπτωση το πρόβλημα μεταβιβάζεται στο λειτουργικό σύστημα. Η διαχείριση της TLB με λογισμικό είναι αποδοτική εφόσον η TLB είναι αρκετά μεγάλη (π.χ με 64 καταχωρήσεις). Η αύξηση της αποδοτικότητας οφείλεται στη μείωση των αστοχιών. Για να μειώσει τις αστοχίες στην TLB το λειτουργικό σύστημα μπορεί να χρησιμοποιήσει "διαίσθηση" προκειμένου να βρει ποιες σελίδες πρόκειται να χρησιμοποιηθούν στη συνέχεια, ώστε να φορτώσει από πριν τις σελίδες αυτές στην TLB. Υπάρχουν διάφορες στρατηγικές για την βελτίωση της απόδοσης σε μηχανές που διαχειρίζονται την TLB με λογισμικό.

Παράδειγμα διαχείρισης της TLB

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

Πηγές

• William Stallings , “Computer Organization And Architecture : Designing For Performance ” , Sixth edition 2003.
• Andrew S. Tanenbaum “ Modern Operating Systems “, Third edition 2008.
• John L. Hennessy, David A. Patterson, David Goldberg, “Computer Architecture”, Third Edition 2003
• A. M. Lister, R.D. Eager, “Λειτουργικά Συστήματα», Τέταρτη Αγγλική Έκδοση
• Εικονική μνήμη Αρχειοθετήθηκε 2012-01-25 στο Wayback Machine., Διομήδης Σπινέλλης