Ποιος είναι ο αλγόριθμος αντικατάστασης σελίδας που χρησιμοποιήθηκε λιγότερο πρόσφατα;

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

Για την υλοποίηση του LRU, μια δομή δεδομένων που ονομάζεται ουρά χρησιμοποιείται. Κάθε φορά που γίνεται πρόσβαση σε μια σελίδα, αυτή μετακινείται στο μπροστινό μέρος της ουράς. Όταν μια σελίδα πρέπει να αντικατασταθεί, επιλέγεται η σελίδα στο τέλος της ουράς (η παλαιότερη σελίδα).

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

Ακολουθούν τα βήματα του αλγόριθμου αντικατάστασης σελίδας LRU:

1. Όταν γίνεται πρόσβαση σε μια σελίδα, αυτή μετακινείται στο μπροστινό μέρος της ουράς.

2. Όταν μια σελίδα πρέπει να αντικατασταθεί, επιλέγεται η σελίδα στο τέλος της ουράς.

3. Η επιλεγμένη σελίδα αφαιρείται από την ουρά και από τη φυσική μνήμη.

4. Η σελίδα που φορτώνεται τοποθετείται στο μπροστινό μέρος της ουράς.