Αλγοριθμοι αντικαταστασης σελιδας

[hellokittaki]

Παιδια καλημερα θα ηεθελα αν καποιος μπορει να μου εξηγησει πως δουλευουμε με αυτους τους αλγοριθμους,αυριο δινω μαθημα και δεν εχω ιδεα.δεν μπορω να καταλαβω πως τοποθετουμε τους αριθμους.Αν καποιος μπορουσε να με βοηθησει θα ημουν ευγνωμων!!!!

επισυναπτω και το παραδειγμα που εχω

ευχαριστω πολυ!!!!!!!

[mchatz]

Υποθέτω ότι το μάθημά σου έχει να κάνει με διαχείριση μνήμης και λειτουργικά συστήματα?

 

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

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

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

 

 

1. FIFO (First In First Out): Ο αλγόριθμος αντικατάστασης είναι απλός. Κοιτάζουμε ποια απο τις σελίδες που έχουμε ήδη φορτώσει είναι η παλιότερη στη μνήμη μας και την αντικαθιστούμε (πχ. στο βήμα 5,ζητάμε να φέρουμε τη σελίδα 4 στη μνήμη. Βλέπουμε ότι η πιο "παλιά" σελίδα είναι η 1 και επιλέγουμε τη θέση μνήμης της σελίδας 1 για να αντικαταστήσουμε. Τώρα η πιο "παλιά" σελίδα είναι η 2 και στην επόμενη αντικατάσταση, θα επιλέξουμε τη θέση μνήμης της σελίδας 2 κ.ο.κ.)

 

2. LRU (Least Recently Used): Εδώ επιλέγουμε τη σελίδα που εχει χρησιμοποιηθεί λιγότερο μέχρι τη στιγμή αντικατάστασης. Δλδ, πάλι στο βήμα 5, κοιτάζουμε ποιά σελίδα έχει χρησιμοποιθεί λιγότερο πρόσφατα.από τη γραμμή Σελ. βλέπουμε οτι η τελευταία χρήση της σελίδας 1 έγινε στο 1ο βήμα, αρα η λιγότερο πρόσφατη σελίδα είναι η 1 η οποία και θα αντικατασταθεί.Όταν έρθει η ώρα να μπεί η σελ. 5 (βήμα 8) βλέπουμε ότι η σελίδα που έχει χρησιμοποιηθεί παλιότερα είναι η 4, την οποία και αντικαθιστούμε κ.ο.κ.

 

3. OPT (Optimised): Εδώ, έχουμε και λίγη "πρόβλεψη".Κοιτάζουμε ποιά σελίδα από τις ήδη υπάρχουσες στη μνήμη θα χρησιμοποιηθεί αργότερα στο μέλλον. Απο τη σειρά Σελ. Κοιτάζουμε προς τα εμπρός αντί για πίσω. Στο βήμα 5 πάλι, βλάπουμε ότι η σελίδα 4 θα χρησιμοποιηθεί πολύ αργότερα (στο βήμα 14) απο τις άλλες που είναι ήδη στη μνήμη και την επιλέγουμε για αντικατάσταση.Όταν ζητήσουμε την σελ. 5 στο βήμα 8, βλέπουμε ότι η σελίδα που πρόκειται να χρησιμοποιηθεί αργότερα απο τις άλλεσ είναι η σελίδα 2 (στο βήμα 15) και την επιλέγουμε για αντικατάσταση κ.ο.κ.

 

4. Clock: Το βελάκι, στο παράδειγμά σου, μαρκάρει την υποψήφια θέση για αντικατάσταση. Στα βήματα 1-4 γεμίζουν οι κενές θέσεις μνήμης, ενώ το αστεράκι ειναι το reference bit που μαρκάρει τις σελίδες στις οποίες έχει γίνει πρόσφατη αναφορά (χρήση). Στο βήμα 5 έχουμε page fault και πρέπει να μπεί η σελ.6.Το βελάκι στη στήλη 4 δείχνει στη σελ. 1 στην οποία έχουμε και αστεράκι. Μηδενίζουμε το αστεράκι και προχωράμε στην επόμενη πρός τα κάτω θέση. Όσο βλέπουμε αστεράκι, το ακυρώνουμε και συνεχίζουμε κυκλικά μέχρι να βρούμε θέση χωρίς αστεράκι (επαναλαμβάνοντας τη στήλη αν χρειαστεί). Τώρα στη θέση 1 έχει ακυρωθεί το αστεράκι οπότε μπορούμε να αντικαταστήσουμε τη σελίδα 1 με την 6 και να μεταφέρουμε το βελάκι στην παρακάτω θέση.

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

 

Ελπίζω να βοήθησα......Αντε, καλή τυχη!!!

[poscaman]

πολύ καλή απάντηση. Μπράβο

[mchatz]

Ε... κάτι θυμόμαστε.... (και είναι ΠΟΛΛΑ....πάρα πολλά τα ρημάδια τα χρόνια απο το αντίστοιχο προπτυχιακό μάθημα

[hellokittaki]

ευχαριστω παρα πολυ για την απαντηση,πραγματικα με βοηθησες!!!!