Διαχείριση εικονικής μνήμης με σελιδοποίηση

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

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

Για να μεταφραστεί μια εικονική διεύθυνση (ΕΔ), πρώτα βρίσκεται η σελίδα (Σ) στην οποία ανήκει. Το ΛΣ αναζητά τη σελίδα αυτή στον πίνακα αντιστοίχισης, και βρίσκει ότι αντιστοιχεί στην ενότητα Ε. Η φυσική διεύθυνση (ΦΔ) θα ανήκει στην ενότητα αυτή, και θα βρίσκεται σε αντίστοιχη θέση με αυτή της ΕΔ μέσα στη σελίδα Σ.

Σε έναν υπολογιστή η εικονική μνήμη έχει μέγεθος 100 (εικονικές διευθύνσεις από Ο ως 99) και χωρίζεται σε 10 σελίδες ενώ η φυσική μνήμη έχει μέγεθος 50 (φυσικές διευθύνσεις από Ο ως 49) και διαιρείται σε 5 ενότητες. Το μέγεθος σελίδων και ενοτήτων είναι 10. Έτσι π.χ. οι εικονικές διευθύνσεις από 0 ως 9 ανήκουν στη σελίδα με αριθμό 0, ενώ οι φυσικές διευθύνσεις από 30 ως 39 ανήκουν στην ενότητα με αριθμό 3.

Στον πίνακα αντιστοίχισης του σχήματος, η σελίδα 0 αντιστοιχεί στην ενότητα 1, δηλαδή οι εικονικές διευθύνσεις 0-9 αντιστοιχούν στις φυσικές διευθύνσεις 10-19. Η εικονική διεύθυνση 2 τελικά θα μεταφραστεί στη φυσική διεύθυνση 12.

Παρατηρούμε ότι κάθε διεύθυνση μπορεί να χωριστεί σε δυο τμήματα: οι δεκάδες της διεύθυνσης δείχνουν τη σελίδα ή την ενότητα στην οποία ανήκει η διεύθυνση, και οι μονάδες δείχνουν τη θέση της διεύθυνσης μέσα στη σελίδα ή την ενότητα. Έτσι για να υπολογίσουμε τη φυσική διεύθυνση ΦΔ από την εικονική διεύθυνση ΕΔ, ακολουθούμε τα εξής βήματα: 1. Βρίσκουμε τον αριθμό σελίδας Σ, που είναι οι δεκάδες της ΕΔ. 2. Βρίσκουμε τη θέση Θ της διεύθυνσης μέσα στη σελίδα, που είναι οι μονάδες της ΕΔ. 3. Από τον πίνακα αντιστοίχισης, βρίσκουμε τον αριθμό ενότητας Ε για τη φυσική μνήμη. 4. Η ΦΔ έχει για δεκάδες τον αριθμό ενότητας Ε και για μονάδες τη θέση Θ μέσα στην ενότητα.

Για την εικονική διεύθυνση ΕΔ = 5, ο αριθμός Σ της σελίδας είναι 0 και η θέση Θ είναι 5. Από τον πίνακα βρίσκουμε ότι η αντίστοιχη ενότητα Ε είναι η 1, έτσι η φυσική διεύθυνση θα είναι 15.

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

Ας δούμε πώς μεταφράζεται μια εικονική διεύθυνση σε φυσική: Ο πίνακας αντιστοίχισης της διεργασίας βρίσκεται στην κύρια μνήμη, και η διεύθυνση όπου αρχίζει κρατείται σε μια μονάδα αποθήκευσης της ΚΜΕ που ονομάζεται καταχωρητής πίνακα σελίδων (ΚΠΣ, page table register). Κάθε «θέση» του πίνακα σελίδων κρατά τον αριθμό ενότητας για την αντίστοιχη σελίδα. Έτσι, αν στην αρχική διεύθυνση του πίνακα σελίδων προσθέσουμε ένα αριθμό σελίδας, θα πάρουμε τη θέση του πίνακα που αντιστοιχεί στη σελίδα αυτή, και θα βρούμε τον αντίστοιχο αριθμό ενότητας για τη σελίδα.

Αν ο πίνακας σελίδων αρχίζει στη διεύθυνση 10 της μνήμης, ο αριθμός ενότητας για τη σελίδα 0 βρίσκεται στη διεύθυνση 10, ο αριθμός ενότητας για τη σελίδα 1 βρίσκεται στη διεύθυνση 11, κλπ. Γενικά ο αριθμός ενότητας για τη σελίδα κ βρίσκεται στη διεύθυνση 10+κ.

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

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

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

Το κυριότερο μειονέκτημα της σελιδοποίησης είναι ότι κάθε διεργασία καταλαμβάνει περισσότερο χώρο από ό,τι χρειάζεται. Συνήθως η μνήμη που απαιτεί μια διεργασία δεν είναι πολλαπλάσιο του μεγέθους της σελίδας, αλλά χρειάζεται π.χ. 10 σελίδες ολόκληρες και 20 λέξεις επιπλέον. Επειδή ο χώρος εικονικών διευθύνσεων που της δίνεται έχει μέγεθος που είναι πολλαπλάσιο της σελίδας, θα της δοθούν 11 σελίδες· από την 11η θα χρησιμοποιηθούν μόνο οι 20 πρώτες λέξεις. Η τελευταία σελίδα κάθε διεργασίας έτσι έχει ένα τμήμα, μικρότερο ή μεγαλύτερο, το οποίο μένει αχρησιμοποίητο. Αυτό το φαινόμενο ονομάζεται εσωτερικός κατακερματισμός (internal fragmentation).