Διαχείριση μνήμης

Απλή διαχείριση μνήμης

Σε συστήματα που εξυπηρετούν μια διεργασία η μνήμη μπορεί να οργανωθεί ως εξής:

Πρόγραμμα χρήστη

Λειτουργικό σύστημα στη RAM

Λειτουργικό σύστημα σε ROM

Πρόγραμμα χρήστη

Οδηγοί συσκευών σε ROM (BIOS)

Πρόγραμμα χρήστη

Λειτουργικό σύστημα σε RAM

• Προλυπρογραμματιστικά συστήματα μπορούν να διαχειριστούν τη μνήμη σε σταθερά τμήματα.
• Η αύξηση της μνήμης αυξάνει την αξιοποίηση του επεξεργαστή αυξάνοντας το βαθμό πολυπρογραμματισμού.
• Η διαχείριση της μνήμης μπορεί να επιτευχθεί με το διαχωρισμό της σε σταθερά τμήματα. Οι εργασίες για τα τμήματα αυτά μπορούν να επιλέγονται:
  • από μια ουρά για όλα τα τμήματα.
  • από μια ουρά ανά τμήμα ανάλογα με το μέγεθός του.
• Η μετατόπιση (relocation) επιτρέπει σε προγράμματα και δεδομένα να εκτελούνται αδιάφορα από το τμήμα της μνήμης στο οποίο έχουν φορτωθεί.
• Η προστασία (protection) απομονώνει τις διαφορετικές διεργασίες. Το λειτουργικό σύστημα διασφαλίζει ότι κάθε διεργασία απαγορεύει σε άλλες διεργασίες την πρόσβαση στη μνήμη της. Αυτό μπορεί να επιτευχθεί με τη χρήση ειδικών καταχωρητών:
  • του καταχωρητή βάσης (base register) και
  • του καταχωρητή ορίου (limit register)

Εναλλαγή

Σε συστήματα που βασίζονται σε εναλλαγή η διαχείριση της μνήμης γίνεται με βάση μεταβλητά τμήματα.

Καταμερισμός μνήμης

• συμπίεση μνήμης (memory compaction)
• χάρτη δυαδικών ψηφίων (bit map)
• συνδεδεμένη λίστα (linked list)
• το σύστημα των φίλων (buddy system)

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

Ιδεατή μνήμη

• Ο χώρος των ιδεατών διευθύνσεων διαιρείται σε ίσα μέρη: τις σελίδες (pages).
• Ο χώρος της φυσικής μνήμης (physical memory) διαιρείται αντίστοιχα σε πλαίσια σελίδας (page frames).
• Ένα bit παρουσίας (present bit) για κάθε ιδεατή σελίδα δηλώνει αν η αντίστοιχη σελίδα βρίσκεται στην πραγματική μνήμη.
• Αν δεν υπάρχει καλείται το λειτουργικό σύστημα με αιτία το λάθος παρουσίας (page fault).
• Το λειτουργικό σύστημα πρέπει να αντικαταστήσει τη σελίδα με βάση τον πίνακα σελίδων (page table).
• Αυτός μπορεί να οργανωθεί σε πολλαπλά επίπεδα ή και αντεστραμμένα για οικονομία μνήμης.
• Η πρόσβαση σε αυτόν γίνεται με τη βοήθεια της ενδιάμεσης μνήμης μετάφρασης (translation lookaside buffer) που είναι υλοποιημένη με συσχετιστική μνήμη (associative memory).
• Η αποδοτικότητά της μετράται με βάση το ποσοστό επιτυχιών (hit ratio)

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

• με αλγόριθμο βέλτιστης αντικατάστασης σελίδας (optimal page replacement algorithm) με βάση το χρόνο της μελλοντικής χρήσης της.
  Ο θεωρητικά βέλτιστος αυτός αλγόριθμος είναι αδύνατο να υλοποιηθεί στην πράξη αφού προϋποθέτει πρόβλεψη της μελλοντικής συμπεριφοράς των διεργασιών.
• με βάση τη σελίδα που δε χρησιμοποιήθηκε πρόσφατα (Not Recently Used).
  • Κάθε σελίδα διαθέτει δύο bit τα οποία περιέχουν 1 αν η σελίδα αυτή έχει διαβαστεί ή γραφεί.
  • Περιοδικά τα bit αυτά τίθενται σε 0 και με τον τρόπο αυτό μπορούν να βρεθούν σελίδες που δεν έχουν πρόσφατα χρησιμοποιηθεί.
  • Η εγγραφή των bit μπορεί να γίνεται από τον επεξεργαστή, ή από το λειτουργικό σύστημα με τη χρήση του λάθους σελίδας σε κάθε πρώτη πρόσβαση μετά την εκκαθάρισή τους.
• με βάση την αρχή πρώτη σελίδα μέσα πρώτη σελίδα έξω (first page in first page out) (FIFO)
• με τον αλγόριθμο αντικατάστασης δεύτερης ευκαιρίας (second chance replacement algorithm).
  Τροποποίηση του παραπάνω αλγορίθμου έτσι ώστε σελίδες που έχουν χρησιμοποιηθεί πρόσφατα όταν είναι υποψήφιες για αντικατάσταση να μεταφέρονται πάλι στην αρχή της ουράς.
• με τον αλγόριθμο του ρολογιού.
  Τροποποίηση του παραπάνω αλγορίθμου έτσι ώστε ο έλεγχος για τις σελίδες που έχουν χρησιμοποιηθεί να γίνεται κυκλικά και να μη μεταφέρονται στην αρχή της ουράς.
• με βάση την αρχή λιγότερο πρόσφατα χρησιμοποιούμενης σελίδας (least recently used)
  Κάθε σελίδα σχετίζεται με έναν μετρητή χρόνου ο οποίος περιέχει το χρόνο της τελευταίας πρόσβασης. Οι σελίδες με την παλιότερη πρόσβαση είναι αυτές που απομακρύνονται.
• με βάση την αρχή λιγότερο συχνά χρησιμοποιούμενης σελίδας (not frequently used)
  Κάθε σελίδα σχετίζεται με έναν μετρητή ο οποίος μετράει τον αριθμό των προσβάσεων στη σελίδα. Η σελίδες με τις λιγότερες προσβάσεις είναι αυτές που απομακρύνονται. Ο αλγόριθμος μπορεί να τροποποιηθεί με την προσθήκη της έννοιας της γήρανσης (aging) όπου οι μετρητές διαιρούνται με το 2 σε τακτικά χρονικά διαστήματα.

Σχεδιασμός σελιδοποίησης

• Σύνολο εργασίας (working set) είναι το σύνολο των σελίδων που χρησιμοποιούνται από μια διεργασία μια δεδομένη χρονική στιγμή.
• Όταν η διαθέσιμη μνήμη μιας διεργασίας είναι σημαντικά μικρότερη από το σύνολο εργασίας της τότε σημειώνεται απότομη πτώση της απόδοσης (thrashing)
• Η προσέγγιση με βάση το μοντέλο συνόλου εργασίας (working set model) έχει την εξής βάση: πριν εκτελεστεί μια διεργασία καταβάλλεται προσπάθεια έτσι ώστε να βρίσκεται το σύνολο εργασίας της στη μνήμη.
• Για το σκοπό αυτό φορτώνονται οι σελίδες στη μνήμη με τη διαδικασία της προσελιδοποίησης (prepaging).
• H επιλογή της σελίδας που θα αντικατασταθεί μπορεί να γίνει είτε λαμβάνοντας υπόψη μόνο τις σελίδες της διαδικασίας στην οποία ανήκει το σφάλμα σελίδας υλοποιώντας δηλαδή έναν τοπικό αλγόριθμο αντικατάστασης σελίδων (local page replacement algorithm) ή κοιτάζοντας όλες τις σελίδες του λειτουργικού συστήματος υλοποιώντας δηλαδή έναν ολικό αλγόριθμο αντικατάστασης σελίδων (global page replacement algorithm).
• Το μέγεθος της σελίδας είναι ευθέως ανάλογο με τη μνήμη που σπαταλάται σε σελίδες που είναι μερικώς μόνο γεμάτες και αντιστρόφως ανάλογο με το χώρο που απαιτείται για τη φύλαξη των πινάκων σελίδων και την ενδιάμεση μνήμη μνήμη μετάφρασης.

Επανεκκίνηση εντολής

• μπορεί να αναλάβει ο επεξεργαστής από το σημείο στο οποίο σταμάτησε ή
• το λειτουργικό σύστημα από την αρχική της κατάσταση.

Θέματα υλοποίησης

Κλείδωμα σελίδων

Σελιδοποίηση κώδικα και δεδομένων

Διαμοιραζόμενες σελίδες

Διεργασία σελιδοποίησης

Κατάτμηση

• Τον κώδικα
• Τη στοίβα
• Τα αρχικοποιημένα δεδομένα
• Το χώρο ανάπτυξης της δυναμικής μνήμης

Η κατάτμηση επιτρέπει:

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

  Κώδικας	Μόνο εκτέλεση
  Αρχικοποιημένα δεδομένα	Μόνο ανάγνωση
  Σωρός	Ανάγνωση και εγγραφή
  Δυναμική μνήμη	Ανάγνωση και εγγραφή

• Την υλοποίηση διαμοιραζομένων βιβλιοθηκών (shared libraries)

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

Βιβλιογραφία

• Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 103-198 Εκδόσεις Παπασωτηρίου, 1993.

• Maurice J. Bach. The Design of the UNIX Operating System, pages 271–352. Prentice-Hall, 1986.

• Bruce Javob and Trevor Mudge. Virtual memory: Issues of implementation. Computer, 31(6):33–43, June 1998.

• Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System, pages 109–163. Addison-Wesley, 1988.

• Andrew S. Tanenbaum. Operating Systems: Design and Implementation, pages 191–247. Prentice-Hall, 1987.

Εργασία στο εργαστήριο

vmstat 1
 procs                  memory    swap        io    system         cpu
 r b w  swpd  free  buff cache  si  so   bi   bo   in   cs  us  sy  id
 1 0 0     0   300  6572  9032   0   0   17    3  106   17   1   1  99
 1 0 0     0   272  6372  8892   0   0    0   73  145   25  94   5   1
 1 0 0     0  1552  6284  8784   0   0   74   47  141  153  54  43   3
 1 0 0     0  1228  6284  8784   0   0    0    0  105    9  97   3   0
 1 0 0     0   852  6284  8784   0   0    0    0  105   13  97   3   0
 1 0 0     0  2552  6284  8768   0   0    0   45  139  133  73  23   4
 1 0 0     0   960  6348  8768   0   0    1   77  130   55  74  13  14
 1 0 0     0   952  6348  8768   0   0    0   12  113   63  81  19   0
 1 0 0     0   964  6348  8772   0   0    2   24  123   82  73  25   2
 1 0 0     0  1052  6348  8772   0   0    0   24  122   83  83  16   2
 1 0 0     0  2484  6348  8772   0   0    0   36  131  120  67  32   1
 1 0 0     0  2416  6348  8772   0   0    0  113  136   68  80  15   6
 2 0 0     0  2404  6348  8772   0   0    0   48  141  164  57  40   3         

kerkis:/proc$ more /proc/meminfo
        total:    used:    free:  shared: buffers:  cached:
Mem:  31559680 31137792   421888 15089664  3870720  7208960
Swap:        0        0        0
MemTotal:     30820 kB
MemFree:        412 kB
MemShared:    14736 kB
Buffers:       3780 kB
Cached:        7040 kB
SwapTotal:        0 kB
SwapFree:         0 kB    

• Περιεχόμενα

 Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:27 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».