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

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

Σε έναν υπολογιστή με κύρια μνήμη μεγέθους 4 ενοτήτων εκτελείται η διεργασία δα, η οποία απαιτεί 7 σελίδες μνήμης (α0, α1, α2, α3, α4, α5, και α6). Όταν ξεκινά η διεργασία, στην κύρια μνήμη δεν είναι αποθηκευμένη καμιά σελίδα της. Στη συνέχεια η ζήτηση σελίδων από τη διεργασία είναι: α0, α2, α6, α5, α2, α1, α0, α3, α4, α0, α6. Υποθέτουμε ότι οι σελίδες ζητούνται σε διαδοχικές χρονικές στιγμές, δηλαδή τη χρονική στιγμή 0 ζητείται η σελίδα α0, τη χρονική στιγμή 1 ζητείται η σελίδα α2 κ.ο.κ.

Στη μία στρατηγική, αυτή της αντικατάστασης με βάση το χρόνο παραμονής (First In First Out, FIFO), επιλέγεται η σελίδα που βρίσκεται για το μεγαλύτερο χρονικό διάστημα στην κύρια μνήμη και αντικαθίσταται με τη νέα. Για να εντοπίζεται η παλαιότερη σελίδα, κάθε φορά που μια σελίδα μεταφέρεται στην κύρια μνήμη σημειώνεται με τον τρέχοντα χρόνο (από το ρολόι του υπολογιστή). Η σελίδα που είναι σημειωμένη με το μικρότερο χρόνο είναι η παλαιότερη.

Τις τέσσερις πρώτες χρονικές στιγμές (0, 1, 2, 3), που ζητούνται οι σελίδες α0, α2, α6 και α5 αντίστοιχα, οι τέσσερις σελίδες της μνήμη είναι κενές, οπότε οι σελίδες τοποθετούνται απευθείας. Στη συνέχεια, οι αντικαταστάσεις των σελίδων φαίνονται στο ακόλουθο σχήμα που παριστάνει τον πίνακα σελίδων. Στη στήλη φαίνονται οι σελίδες της εικονικής μνήμης με την αντίστοιχη ενότητα κύριας μνήμης (ή «-» αν η σελίδα δε βρίσκεται στην κύρια μνήμη), και στη στήλη φαίνεται ο χρόνος με τον οποίο έχουν σημειωθεί όσες σελίδες βρίσκονται στην κύρια μνήμη. Για κάθε χρονική στιγμή, δίνεται η σελίδα που ζητά η διεργασία και εξηγείται η αντικατάσταση που θα γίνει, αν είναι απαραίτητη. Η σελίδα που θα αντικατασταθεί κάθε φορά είναι σκιασμένη.

Η δεύτερη στρατηγική είναι αυτή της αντικατάστασης με βάση το χρόνο της τελευταίας προσπέλασης (Least Recently Used, LRU), οπότε επιλέγεται για αντικατάσταση εκείνη η σελίδα που έχει τον περισσότερο χρόνο να προσπελαστεί. Για να είναι αυτό δυνατόν, πρέπει κάθε φορά που μια σελίδα προσπελάζεται, είτε μεταφέρεται στην κύρια μνήμη είτε ήδη βρίσκεται εκεί, να σημειώνεται με τον τρέχοντα χρόνο του υπολογιστή. Όταν πρέπει να αντικατασταθεί μια σελίδα, το ΛΣ διαλέγει εκείνη που είναι σημειωμένη με το μικρότερο (δηλαδή τον παλαιότερο) χρόνο.

Και με την τεχνική της αντικατάστασης με βάση το χρόνο προσπέλασης, οι τέσσερις πρώτες προσπελάσεις σελίδων, οπότε ζητούνται οι σελίδες α0, α2, α6 και α5, έχουν σαν αποτέλεσμα την απευθείας τοποθέτηση των σελίδων στην κύρια μνήμη. Στη συνέχεια, οι αντικαταστάσεις των σελίδων γίνονται ως εξής: [pic]