Τοποθέτηση σελίδων

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

Οι στρατηγικές τοποθέτησης σελίδων που χρησιμοποιούνται περισσότερο είναι η στρατηγική του πρώτου ταιριάσματος (first fit), η στρατηγική του καλύτερου ταιριάσματος (best fit) και η στρατηγική του χειρότερου ταιριάσματος (worst fit).

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

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

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

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

Αρχικά ο κατάλογος ελεύθερων τμημάτων περιέχει δυο τμήματα φυσικής μνήμης, ένα με μέγεθος 3000 και ένα με μέγεθος 1600 λέξεις. Στη συνέχεια ζητούνται διαδοχικά τέσσερα τμήματα μνήμης, με μεγέθη 1100, 400, 100 και 2000 λέξεις, αντίστοιχα.

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