ΗΥ-225: Οργάνωση Υπολογιστών
Άνοιξη 2021		 Τμ. Επ. Υπολογιστών
© Πανεπιστήμιο Κρήτης

Σειρά Ασκήσεων 12:
Εικονική Μνήμη (Virtual Memory)

Προθεσμία έως Παρασκευή 14 Μαΐου 2021 (βδ. 11.3) ώρα 23:59 (από βδ. 10.4)
[Up - Table of Contents]
[Prev - 11. Cache Memories] 		[printer version - PDF]
[13. I/O and DMA - Next]


Βιβλίο (Ελληνικό, έκδοση 4) - διαβάστε τα εξής:
• Χειρισμός Εξαιρέσεων και Διακοπών στο υλικό ενός επεξεργαστή: §4.9, σελ. 448 - 455 (το μεσαίο κομάτι, σελ. 452-454, μπορείτε να το περάσετε "στα γρήγορα").
• Εικονική Μνήμη: §5.4, σελ. 571 - 602,
• §5.5, σελ. 602-611 (ένα κοινό πλαίσιο γιά ιεραρχίες μνήμης): χρήσιμο θέμα γιά περαιτέρω κατανόηση, αλλά εκτός ύλης αυτού του μαθήματος.
• Εικονικές Μηχανές (Virtual Machines) - §5.6, σελ. 611-617: μπορείτε να τις περάσετε "στα γρήγορα", αν και είναι σημαντικό θέμα της σημερινής τεχνολογίας που πρέπει να ξέρετε περί τίνος πρόκειται γιά την περαιτέρω σταδιοδρομία σας.
Διαφάνειες από το Αγγλικό βιβλίο γιά το κεφάλαιο 5: βρίσκονται (PPT) στο www.elsevier.com/__data/assets/powerpoint_doc/0005/273713/Chapter_05-RISC-V.ppt

12.1   Εικονική Μνήμη: Στόχοι της

Δείτε τη Διαφάνεια 68 του (Αγγλικού) βιβλίου.
Ο πρώτος και βασικότερος σκοπός του μηχανισμού της Εικονικής Μνήμης (Virtual Memory) είναι να δίνει την εντύπωση σε πολλαπλούς "χρήστες" ("προγράμματα") ότι έχουν "όλη τη μηχανή δική τους". Το βασικότερο χαρακτηριστικό του ότι το κάθε πρόγραμμα "νομίζει ότι έχει όλη τη μηχανή δική του" είναι ότι το κάθε πρόγραμμα θεωρεί ότι δικαιούται να χρησιμοποιήσει την οιαδήποτε διεύθυνση μνήμης, σαν να ήταν όλη η μνήμη δική του, και σαν να μην υπήρχαν άλλα προγράμματα που τρέχουν (σχεδόν) ταυτόχρονα. Ο μηχανισμός της Εικονικής Μνήμης κάνει ώστε ο Χώρος Διευθύνσεων (Address Space) του κάθε προγράμματος να είναι διαφορετικός και χωριστός από το χώρο διευθύνσεων του άλλου.

Η μονάδα "προγράμματος ή χρήστη" που θεωρεί ότι έχει όλη τη μηχανή δική της ομομάζεται Διεργασία (Process) (ή καμιά φορά και "πεδίο προστασίας" - "protection domain"), και αποτελεί "ένα πρόγραμμα". Διαφορετικές διεργασίες μπορεί να ανήκουν σε διαφορετικούς ανθρώπους-χρήστες, οπότε και θέλουμε να προστατεύονται η μία από την άλλη διότι ο κάθε χρήστης μπορεί να θέλει να έχει ιδιωτικές (εμπιστευτικές) πληροφορίες που να μην μπορεί να τις βλέπει ή υποκλέπτει ο άλλος. Μπορεί όμως επίσης διαφορετικές διεργασίες να ανήκουν στον ίδιο άνθρωπο-χρήστη, αλλά και πάλι να θέλουμε να τις προστατέψουμε τη μία από την άλλη, π.χ. γιά σκοπούς modularity (τακτοποίηση των πληροφοριών κατά ομάδες) και debugging: εάν "χαλάσει" η μία διεργασία, να συνεχίσει να δουλεύει η άλλη. Στην ίδια περίπτωση ανήκουν και διαφορετικά προγράμματα, που ο προγραμματιστής τους θεωρούσε ότι το καθένα τρέχει μόνο του, και κατέληξαν να τρέχουν μαζί. Παραπλήσια –αν και διαφορετική από άποψη δικαιωμάτων και προστασίας– είναι και η περίπτωση μιάς "διεργασίας χρήστη" αφ' ενός, και του Λειτουργικού Συστήματος (Operating System) από την άλλη: το λειτουργικό σύστημα είναι σαν μιά άλλη διεργασία, που έχει σαν σκοπό να βοηθά και να συγχρονίζει όλες τις διάφορες διεργασίες των χρηστών. Άλλη περίπτωση είναι δύο διαφορετικές διεργασίες να είναι το ίδιο μεν πρόγραμμα, που όμως τρέχει σε διαφορετικά δεδομένα κάθε φορά –π.χ. ξεκινάμε έναν compiler γιά να μεταφράσουμε ένα πρόγραμμα, και πριν τελειώσει ξαναξεκινάμε ένα άλλο "instance" του ίδιου compiler γιά να μεταφράσει ένα άλλο πρόγραμμα.

Η δυνατότητα του επεξεργαστή (εννοούμε τον κάθε ένα πυρήνα, όταν μιλάμε γιά πολυπύρηνους (multicore) επεξεργαστές) να δίνει την εντύπωση ότι τρέχει (σχεδόν) "ταυτόχρονα" πολλαπλές διεργασίες λέγεται Πολυπρογραμματισμός (Multi-Programming), και στηρίζεται στο ότι οι επεξεργαστές είναι πολύ γρηγορότεροι από τους ανθρώπους: τρέχει πότε τη μία και πότε την άλλη διεργασία, από λίγο την κάθε μία, αλλά τις εναλλάσει τόσο γρήγορα που ο ανθρώπινος χρήστης δεν βλέπει την εναλλαγή και νομίζει ότι αυτές τρέχουν ταυτόχρονα. Γιά να εναλλάσονται μεταξύ τους οι διεργασίες χρησιμοποιείται βασικά ο μηχανισμός των Εξαιρέσεων/Διακοπών (Exceptions/Interrupts) –βλ. §4.9 του βιβλίου.

Η εικονική μνήμη, σαν τρόπος να δίνει την εντύπωση στην κάθε διεργασία ότι έχει τη "μηχανή δική της", αποτελεί ειδική περίπτωση του γενικότερου μηχανισμού της Εικονικοποίησης (Virtualization) –βλ. §5.6 του βιβλίου. Η γενικότερη αυτή περίπτωση των "εικονικών μηχανών" (virtual machines) δίνει τη δυνατότητα στην κάθε διεργασία όχι μόνο να (νομίζει ότι) έχει τη μηχανή δική της, αλλά επιπλέον και να έχει το δικό της Λειτουργικό Σύστημα, ανεξάρτητο και ενδεχομένως διαφορετικό από το λειτουργικό σύστημα που έχουν οι άλλες διεργασίες - εικονικές μηχανές που τρέχουν ταυτόχρονα πάνω στον ίδιο επεξεργαστή.

Ο δεύτερος και διαφορετικός σκοπός της εικονικής μνήμης είναι να λειτουργεί σαν ένα επιπλέον επίπεδο της Ιεραρχίας Μνήμης μεταξύ κεντρικής μνήμης (DRAM) και μόνιμης (non-volatile - μη πτητικής) μνήμης (σκληρού δίσκου ή μνήμης flash). Με άλλα λόγια, η εικονική μνήμη δίνει τη δυνατότητα στην κάθε διεργασία να "βλέπει" χώρο μνήμης μεγαλύτερο από το κομμάτι της φυσικής μνήμης (DRAM) που όντως της διατίθεται. Παρ' ότι ο σκοπός αυτός είναι εντελώς διαφορετικός από τον πρώτο (πολλαπλές διεργασίες), τυχαίνει όμως οι ίδιοι μηχανισμοί υλικού (hardware) να μπορούν ταυτόχρονα να υλοποιήσουν και τους δύο σκοπούς.

Μιά συνέπεια των δύο προηγουμένων σκοπών είναι το πρόβλημα του τεμαχισμού (fragmentation) της μνήμης, το οποίο –και αυτό– το λύνουν οι ίδιοι μηχανισμοί της εικονικής μνήμης. Ο τεμαχισμός της μνήμης προκύπτει από το ότι διάφορες διεργασίες ξεκινάνε και τελειώνουν σε διαφορετικές στιγμές, και κάθε μιά που τελειώνει αφήνει και κάμποσες "τρύπες" από αχρησιμοποιήτη (πλέον) μνήμη εκεί που προηγουμένως αυτή κατείχε και χρησιμοποιούσε μνήμη. Επίσης, όταν πηγαινοέρχονται στο δίσκο (η στην flash) κομάτια μνήμης μιάς διεργασίας που δεν χωράνε στην DRAM, δημιουργούνται "τρύπες" στη DRAM από τα κομάτια που μετακομίζουν στο δίσκο. Οι μηχανισμοί της εικονικής μνήμης δίνουν τη δυνατότητα γιά εκχώρηση μνήμης (π.χ. μέσω malloc()) που μοιάζει να αποτελείται από συνεχόμενες διευθύνσεις ενώ στην πραγματικότητα αποτελείται από κομάτια που βρίσκονται κατεσπαρμένα "εδώ κι εκεί" στη φυσική μνήμη.

12.2   Τοποθέτηση και Ανεύρεση Σελίδων: Πίνακες Μετάφρασης

Δείτε τις Διαφάνειες 69-74 του (Αγγλικού) βιβλίου.
Επειδή οι αστοχίες της DRAM –ειδωμένης σαν βαθμίδα της ιεραρχίας μνήμης– εξυπηρετούνται από το σκληρό δίσκο, και άρα κοστίζουν τραγικά πολύ (εκατομμύρια κύκλους ρολογιού του επεξεργαστή), πρέπει το ποσοστό αστοχίας να γίνει πάρα πολύ χαμηλό. Γιά να επιτευχθεί αυτό, πρέπει η τοποθέτηση των σελίδων να είναι πολύ ευέλικτη –δεν μας κάνει ο τρόπος που είναι οργανωμένες οι κρυφές μνήμες, σαν συσχετιστικές μερικών δρόμων, διότι αυτό θα έδινε πολύ μικρή ευελιξία στην επιλογή του "θύματος" που θα αντικατασταθεί γιά να φέρουμε ένα νέο "μπλόκ" λέξεων, με αποτέλεσμα συχνά να διώχνουνται "μπλόκς" που τα χρειαζόμαστε. Έτσι, αντίθετα από τις συνηθισμένες κρυφές μνήμες, η εικονική μνήμη λειτουργεί σαν "πλήρως συσχετιστική", δηλαδή το οιοδήποτε "μπλοκ" λέξεων από το δίσκο μπορεί να τοποθετηθεί οπουδήποτε στην DRAM. Αυτό, φυσικά, θα έκανε την αναζήτηση εξαιρετικά δαπανηρή εάν έπρεπε να αναζητούμε το "μπλόκ" παντού, γι' αυτό η αναζήτηση γίνεται αλλοιώς: με "πίνακες μετάφρασης" που καταγράφουν πού βρίσκεται το κάθε "μπλόκ".

Επειδή η κάθε προσπέλαση στο δίσκο κοστίζει πολύ (χρονικά), θέλουμε να "αποσβέσουμε" αυτό το κόστος κάνοντας πολλή δουλειά κάθε φορά που πηγαίνουμε στο δίσκο, εκμεταλλευόμενοι τη χωρική τοπικότητα καθώς και τα χαρακτηριστικά του δίσκου (προσπέλαση συνεχόμενων λέξεων είναι πολύ γρηγορότερη απ' όσο τυχαίων λέξεων). Έτσι, το "μπλόκ" της ιεραρχίας μνήμης μεταξύ DRAM και δίσκου είναι πολύ μεγαλύτερο απ' όσο το μπλόκ (γραμμή) των κρυφών μνημών. Το "μπλόκ" της ιεραρχίας DRAM-δίσκου λέγεται Σελίδα (Page) και είναι συνήθως 4 ή περισσότερα KBytes, και η τάση είναι να μεγαλώνει με τα χρόνια. Ένας δεύτερος βασικός (μάλλον και βασικότερος) λόγος γιά τον οποίο θέλουμε μεγάλα μπλόκς (σελίδες) στην εικονική μνήμη είναι ότι έτσι διευκολύνεται και επιταχύνεται ο μηχανισμός ανεύρεσης του μπλόκ που ψάχνουμε κάθε φορά, δηλαδή η μετάφραση σελίδων που θα πούμε αμέσως τώρα.

Ο βασικός τρόπος λειτουργίας της εικονικής μνήμης είναι ο εξής. Κάθε διεύθυνση μνήμης που γεννά ο επεξεργαστής –δηλαδή το πρόγραμμα που τρέχει– θεωρείται ως "εικονική διεύθυνση", και μεταφράζεται σε μιάν άλλη, "φυσική διεύθυνση", προτού δοθεί στη μνήμη γιά να επιλεγεί η λέξη την οποία τελικά θα προσπελάσει το πρόγραμμα. Η μετάφραση αυτή είναι η συνάρτηση που "ανευρίσκει" την κάθε λέξη, δηλαδή αυτή που μας λέει πού στη φυσική μνήμη έχει τοποθετηθεί η κάθε εικονική λέξη. Η συνάρτηση αυτή θα ήταν πανάκριβη εάν δούλευε πάνω σε μεμονωμένες λέξεις, αλλά έχει λογικό κόστος επειδή δουλεύει πάνω σε (μεγάλες) σελίδες. Η μέθοδος αυτή αναζήτησης και ανεύρεσης μπλόκς δεν θα δούλευε γιά την κρυφή μνήμη, λόγω του (σχετικά) μικρού μεγέθους των "γραμμών" της κρυφής μνήμης, και της εκεί απαιτούμενης ταχύτητας. Όμως, δουλεύει μιά χαρά γιά την εικονική μνήμη, λόγω του "κόλπου" του TLB και της λειτουργίας του εν παραλλήλω με την κρυφή μνήμη, όπως θα πούμε παρακάτω (§2.7). Η μετάφραση διευθύνσεων εξυπηρετεί πολλαπλούς σκοπούς ταυτόχρονα:

  1. Βρίσκει πού έχουν τοποθετηθεί στη φυσική μνήμη οι σελίδες εικονικής μνήμης που χρησιμοποιούνται περισσότερο επί του παρόντος, ενώ όσες δεν χωράνε στην υπάρχουσα φυσική μνήμη βρίσκονται στο δίσκο –δηλαδή υλοποιεί την ιεραρχία μνήμης μεταξύ DRAM και δίσκου.
  2. Μεταφράζει τις εικονικές διευθύνσεις της κάθε διεργασίας σε διαφορετικές φυσικές διευθύνσεις γιά την κάθε διεργασία, κι έτσι υλοποιεί το διαχωρισμό και την προστασία μεταξύ διεργασιών (εκτός των περιπτώσεων που θέλουμε οι διεργασίες να επικοινωνούν μεταξύ τους μέσω κοινόχρηστης μνήμης (shared memory)).
  3. Ελέγχει ότι η διεργασία που τρέχει έχει δικαίωμα να κάνει την προσπέλαση που ζητά (ανάγνωση/εγγραφή/εκτέλεση) στη διεύθυνση που ζητά, βελτιώνοντας έτσι ακόμη περισσότερο την προστασία των διεργασιών.
Η μετάφραση διευθύνσεων γίνεται απεικονίζοντας ολόκληρες "σελίδες" (pages) εικονικής μνήμης σε ολόκληρες φυσικές σελίδες. Το μέγεθος των σελίδων είναι πάντα δύναμη του 2, και αυτές είναι πάντα ευθυγραμμισμένες στα φυσικά τους όρια, δηλαδή ξεκινούν πάντα σε διευθύνσεις που είναι ακέραια πολλαπλάσια του μεγέθους τους, τόσο στο χώρο των εικονικών όσο και σ' εκείνο των φυσικών διευθύνσεων. Θεωρήστε το εξής μικρό (εξωπραγματικό σήμερα) σύστημα εικονικής μνήμης, σαν απλό παράδειγμα. Επομένως, η "σχετική" διεύθυνση μιάς ποσότητας μέσα σε μία σελίδα, το λεγόμενο page offset, είναι πάντα το υπόλοιπο της διαίρεσης της απόλυτης διεύθυνσης διά το μέγεθος της σελίδας, δηλαδή τα log2(PageSize) το πλήθος LS bits της διεύθυνσης, και αυτά είναι τα ίδια (αμετάφραστα) τόσο στο χώρο των εικονικών όσο και σ' εκείνο των φυσικών διευθύνσεων. Έτσι, θεωρήστε το εξής μικρό (εξωπραγματικό σήμερα) σύστημα εικονικής μνήμης, σαν απλό παράδειγμα: Τότε, η μετάφραση μιάς εικονικής διεύθυνσης, π.χ. της FE210, στην αντίστοιχη φυσική γίνεται ως εξής:

12.3   Προστασία Μνήμης, Λειτουργικό, Εξαιρέσεις:

Διαχωρισμός και Προστασία Διεργασιών: Κάθε διεργασία έχει το δικό της πίνακα μετάφρασης σελίδων, χωριστό και ανεξάρτητο από εκείνους των άλλων διεργασιών, και αυτός ορίζει ποιές σελίδες μπορεί να προσπελάζει η διεργασία: δεδομένου ότι κάθε προσπέλαση μνήμης περνάει από τη μετάφραση αυτή, η διεργασία είναι αδύνατον να προσπελάσει φυσικές σελίδες που δεν έχουν τοποθετηθεί στον πίνακα μετάφρασής της. Στο σχήμα φαίνονται δύο διεργασίες, Α και Β· η καθεμιά τους βλέπει το δικό της χώρο εικονικών διευθύνσεων (γαλάζιος γιά την Α, πράσινος γιά την Β). Τα βέλη δείχνουν ποιές εικονικές σελίδες της καθεμιάς τους έχουν τοποθετηθεί σε ποιές φυσικές σελίδες της μνήμης. Οι σελίδες σε χρώμα ώχρα είναι αόρατες τόσο γιά την Α όσο και γιά την Β. Επίσης φαίνεται και ο πίνακας μετάφρασης της Α (ανάλογος είναι και της Β). Η σελίδα με τις εντολές ("text", προστασία execute-only) είναι κοινή, επειδή υποτίθεται ότι οι Α και Β είναι instances του ιδίου προγράμματος. Επίσης, η φυσική σελίδα 6 είναι κοινή μεταξύ των Α και Β επειδή αυτές υποτίθεται ότι συνεργάζονται (ανταλλάσουν δεδομένα) μέσω αυτής· σε αυτό το παράδειγμα, η Α παράγει δεδομένα και τα γράφει (μόνον) εκεί, η δε Β καταναλώνει αυτά τα δεδομένα, διαβάζοντάς τα (μόνον) από εκεί.

Το hardware του επεξεργαστή βρίσκει τον πίνακα μετάφρασης της τρέχουσας διεργασίας από τη (φυσική) διεύθυνση βάσης του πίνακα αυτού, που είναι γραμμένη (από το λειτουργικό σύστημα) σ' έναν ειδικό καταχωρητή του συστήματος διαχείρισης μνήμης –όχι στο κανονικό register file. Όταν ο επεξεργαστής τρέχει σε "user mode", δεν επιτρέπεται να γράψει αυτόν τον καταχωρητή, ούτως ώστε να μην μπορεί να υποκριθεί ότι είναι άλλη διεργασία, δηλαδή να μην μπορεί να αποκτήσει πρόσβαση στη μνήμη άλλων διεργασιών.

Προστασία Λειτουργικού Συστήματος: Ο παραπάνω ειδικός καταχωρητής που καθορίζει τον τρέχοντα πίνακα μετάφρασης –δηλαδή την τρέχουσα διεργασία– είναι προσπελάσιμος από τον επεξεργαστή μόνον όταν ο επεξεργαστής βρίσκεται σε "kernel mode", δηλαδή τρέχει το λειτουργικό σύστημα. Κάθε εξαίρεση (exception) –περιλαμβανόμενου και του καλέσματος συστήματος (system call)– αποθηκεύει την παλιά κατάσταση (user/kernel) στην οποία έτρεχε ο επεξεργαστής, και φέρνει τον επεξεργαστή σε kernel mode. Έτσι, ο trap (exception) handler εκτελείται πάντα σε kernel mode, ενώ ο μόνος τρόπος γιά ένα χρήστη να φέρει τον επεξεργαστή σε kernel mode είναι να προκαλέσει εξαίρεση, εκτελώντας μιάν εντολή system (environment) call –κάτι σαν παράνομη εντολή που προκαλεί εξαίρεση, αλλά που το λειτουργικό σύστημα ξέρει ότι προορίζεται σαν system call και όχι σαν απλή παράνομη εντολή λόγω προγραμματιστικού σφάλματος. Το κάλεσμα συστήματος είναι επίτηδες φτιαγμένο να συμπεριφέρεται σαν εξαίρεση (exception), και όχι σαν απλό κάλεσμα διαδικασίας (εντολή jal), ούτως ώστε η είσοδος στο λειτουργικό σύστημα –που πρέπει να γίνει σε kernel mode– να γίνεται μόνο στην προκαθορισμένη διεύθυνση του trap handler, και όχι σε οιαδήποτε άλλη αυθαίρετη διεύθυνση θα μπορούσε να ζητήσει ένας κακόβουλος χρήστης προκειμένου να παρακάμψει το μέρος εκείνο του λειτουργικού συστήματος που κάνει τους ελέγχους του εάν ο χρήστης έχει δικαίωμα να ζητήσει αυτό που ζητά.

Παρούσες/Απούσες Σελίδες και Προστασία Σελίδων: Κάθε θέση του πίνακα μετάφρασης περιέχει:

"Παράνομες" προσπελάσεις εικονικής μνήμης είναι π.χ. οι εξής: (i) προσπάθεια εγγραφής σε σελίδα όπου δεν έχω δικαίωμα εγγραφής (π.χ. σελίδα read-only), ή (ii) προσπάθεια ανάγνωσης δεδομένων από σελίδα που είναι, π.χ. "execute-only" (δηλ. περιέχει εντολές), ή (iii) προσπάθεια ανάγνωσης με σκοπό την εκτέλεση (instruction fetch) από σελίδα που δεν περιέχει εκτελέσιμες εντολές, ή (iv) προσπάθεια προσπέλασης οιασδήποτε μορφής σε σελίδα "unallocated", δηλαδή που ούτε ο compiler έβαλε εκεί (στατικά) κάποιο μέρος του προγράμματος (εντολές ή δεδομένα), ούτε η malloc() εκχώρησε εκεί (δυναμικά) χώρο (άδεια χρήσης). Τέτοιες "παράνομες" προσπελάσεις προκαλούν πρόωρο τερματισμό της εκτέλεσης, με το οικείο σε όλους μας μήνυμα "segmentation violation - core dumped".

"Απούσες (αλλά νόμιμες)" σελίδες εικονικής μνήμης είναι εκείνες που ναι μεν το πρόγραμμα έχει νόμιμο δικαιώμα προσπέλασης σε αυτές (δηλ. δεν είναι παράνομη η προσπέλαση), αλλά όμως τυχαίνει (είτε ελλείψει επαρκούς μνήμης, είτε επειδή ποτέ μέχρι στιγμής δεν την είχε ζητήσει το πρόγραμμα) η σελίδα αυτή να μην βρίσκεται αυτή τη στιγμή στην (κεντρική) μνήμη (RAM) του υπολογιστή, αλλά στο (σκληρό) δίσκο. Προσπελάσεις σε απούσες σελίδες προκαλούν προσωρινή διακοπή της εκτέλεσης του προγράμματος (σφάλμα σελίδας - page fault exception/interrupt), ανάληψη από το λειτουργικό σύστημα να προσκομίσει την απούσα σελίδα, και επανεκκίνηση του προγράμματος "σαν να μη συνέβη τίποτα" μετά την προσκόμιση αυτή.

Εξαιρέσεις/Διακοπές (Exceptions/Interrupts):
Διαβάστε γιά αυτά τα θέματα από την §4.9 του (Ελληνικού) βιβλίου και δείτε τις Διαφάνειες 86-90, 92, και 96-97 του κεφαλαίου 4 του Αγγλικού βιβλίου.
Προσέξτε ιδιαίτερα ότι τα σφάλματα σελίδας πρέπει να τα αναγνωρίζει το υλικό και να τα χειρίζεται πρίν ολοκληρωθεί η εκτέλεση της εντολής που τα προκάλεσε: πριν γράψει η εντολή load στον καταχωρητή προορισμού ή η εντολή store στη λέξη προορισμού, μέσα στην –ανύπρακτη!– σελίδα μνήμης. Αλλοιώς, π.χ., δεν μπορούν να επανεκκινηθούν σωστά, μετά την προσκόμιση της απούσας σελίδας από το δίσκο, εντολές όπως "lw $8, 4($8)" που προκύπτουν π.χ. από συνηθισμένες εκχωρήσεις όπως: "p = p->next;".

Άσκηση 12.4:   Μονοεπίπεδος Πίνακας Μετάφρασης

(α) Θεωρήστε το παραπάνω μικρό (εξωπραγματικό) παράδειγμα εικονικής μνήμης της §12.2. Κάντε γιά αυτό ένα σχηματικό διάγραμμα που να δείχνει τον καταχωρητή που περιέχει τον pointer στον πίνακα μετάφρασης της παρούσας διεργασίας, τον πίνακα μετάφρασης, την εικονική διεύθυνση (20 bits) που γεννά ο επεξεργαστής, τα πεδία από τα οποία αυτή αποτελείται, από που προέρχεται το index στον πίνακα μετάφρασης, τι διαβάζουμε από τη θέση εκείνη του πίνακα, και πώς συνθέτουμε τη φυσική διεύθυνση (16 bits).

(β) Έστω ότι, στο παραπάνω απλό παράδειγμά μας, η διεργασία μας έχει τις εξής σελίδες:

Δείξτε τα περιεχόμενα του πίνακα μετάφρασης της διεργασίας μας, χωρίς τα reference bits αλλά με όλα τα άλλα πεδία του (256 γραμμές επί 4 πεδία ανά γραμμή –επιτρέπεται η χρήση αποσιωποιητικών...).

(γ) Ποιές από τις παρακάτω προσπελάσεις στις εικονικές διευθύνσεις που δίδονται προκαλούν σφάλμα σελίδας και γιατί; Ποιές από αυτές θα προκαλέσουν τερματισμό του προγράμματος, ως λανθασμένο, και ποιές απλώς θα κάνουν το λειτουργικό σύστημα να φέρει την αιτηθείσα σελίδα από το δίσκο και να επανεκκινήσει το πρόγραμμα; Οι υπόλοιπες, σε ποιά φυσική διεύθυνση μεταφράζονται;

01038 (fetch), 0B0F4 (read), C001C (write), 0292C (fetch), 00000 (read), 99F88 (read), FE5D8 (write), FF100 (fetch), C20CC (write), CD0CC (write), C0444 (read), 01FF4 (fetch), C1FFC (write), 008E4 (write), C7700 (read), 01E40 (write).
A 32-entry one-level page table broken down into two levels, consisting of an 8-entry root page table followed by 4-entry second-level tables

Άσκηση 12.5:   Πολυεπίπεδοι Πίνακες Μετάφρασης - Οικονομία Χώρου

Οι περισσότερες διεργασίες χρησιμοποιούν σχετικά λίγες από τις εικονικές τους σελίδες, και αυτές συνοθηλευμένες (clustered) σε μερικές "γειτονιές", όπως στην παραπάνω άσκηση 12.4 ή στο παράδειγμα του σχήματος εδώ. Εκμεταλλευόμενοι αυτή την ιδιότητα, μπορούμε να μειώσουμε το χώρο μνήμης που καταλαμβάνει ο πίνακας μετάφρασης της κάθε διεργασίας, σπάζοντας τον σε μερικούς μικρότερους πίνακες, οργανωμένους σαν μιά πολυ-επίπεδη ιεραρχία. Το σχήμα δείχνει ένα παράδειγμα ενός μονοεπίπεδου πίνακα γιά 32 εικονικές σελίδες, τις οποίες ομοδοποιούμε σε 8 ομάδες των 4 σελίδων καθεμία. Όταν μετατρέψουμε το σύστημα αυτό σε διεπίπεδο πίνακα, δεξιά στο σχήμα, ο πίνακας πρώτου επιπέδου (root page table) θα έχει μία θέση ανά ομάδα σελίδων. Πίνακες δευτέρου επιπέδου θα υπάρχουν μόνον γιά εκείνες τις ομάδες εικονικών σελίδων που δεν είναι όλες τους ανύπαρκτες.

Σαν άσκηση τώρα, θεωρήστε ότι στο σύστημα μνήμης της άσκησης 12.4 αλλάζουμε τον μοναδικό (μονοεπίπεδο) πίνακα μετάφρασης ανά διεργασία σε διεπίπεδους πίνακες, ώς εξής. Κάθε διεργασία θα έχει έναν πίνακα πρώτου επιπέδου, μεγέθους 16 θέσεων. Τον πίνακα αυτόν τον βρίσκουμε μέσω του γνωστού pointer που περιέχεται στον ειδικό καταχωρητή που αναφέραμε παραπάνω. Χρησιμοποιούμε τα 4 MS bits της εικονικής διεύθυνσης γιά να επιλέξουμε μία από τις 16 θέσεις αυτού του πίνακα. Κάθε συνδυασμός των 4 αυτών bits, επομένως και κάθε θέση αυτού του πίνακα, αντιστοιχεί σε 16 εικονικές σελίδες. Εαν καμία από αυτές τις 16 σελίδες δεν υπάρχει στη φυσική μνήμη, τότε σημειώνουμε τη θέση αυτή του πίνακα πρώτου επιπέδου σαν άκυρη (valid bit = 0). Αλλιώς, η θέση αυτή του πίνακα πρώτου επιπέδου περιέχει έναν pointer σε ένα πίνακα μετάφρασης δευτέρου επιπέδου. Εάν η εικονική μας διεύθυνση μας οδήγησε σε τέτοια θέση στον πίνακα πρώτου επιπέδου, τότε χρησιμοποιούμε τα επόμενα 4 bits της εικονικής διεύθυνσης σαν index στον πίνακα δευτέρου επιπέδου όπου μας οδήγησε ο πίνακας πρώτου επιπέδου. Εκεί, στον πίνακα δευτέρου επιπέδου, βρίσκουμε τα τελικά στοιχεία γιά τη σελίδα που ζητάμε.

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

(δ) Πόσες θέσεις μνήμης καταλαμβάνουν όλοι οι πίνακες μετάφρασης του παρόντος διεπίπεδου συστήματος γιά τη διεργασία μας και γιά τις σελίδες (β); Σε σχέση με το μονοεπίπεδο σύστημα της άσκησης 12.4(β) υπάρχει οικονομία στο χώρο μνήμης που καταλαμβάνεται;

Άσκηση 12.6:   Πολυεπίπεδοι Πίνακες Μετάφρασης σε Ρεαλιστικό Σύστημα

Επαναλάβετε την άσκηση 12.5(α) –που ήταν σαν την 12.4(α) (σχηματικό διάγραμμα πινάκων μετάφρασης)– αυτή τη φορά γιά ένα ρεαλιστικό, σημερινό, σύστημα εικονικής μνήμης:

Άσκηση 12.7:   TLB, Process ID, και Κοινόχρηστες Σελίδες

Δείτε τις Διαφάνειες 75-80 του (Αγγλικού) βιβλίου.
Γιά να γίνεται η μετάφραση γρήγορα, χρησιμοποιείται συνήθως ένας μικρός κατάλογος ζευγών εικονικής-φυσικής σελίδας γιά τις πιό συχνά χρησιμοποιούμενες σελίδες –ο "TLB" (Translation Lookaside Buffer)– οργανωμένος σαν μιά μικρή κρυφή μνήμη, συνήθως πλήρως προσεταιριστική –βλέπε σελίδες 583-590 του Ελληνικού βιβλίου. Επειδή μεταφράζονται μόνον τα αριστερά (MS) bits της εικονικής διεύθυνσης, όπως θα πούμε αμέσως παρακάτω, όταν οι σελίδες είναι αρκετά μεγάλες και η κρυφή μνήμη αρκετά μικρή, μπορούμε να πετύχουμε ώστε η προσπέλαση στην κρυφή μνήμη, που ώς γνωστόν ξεκινάει με κάμποσα από τα δεξιά (LS) bits της διεύθυνσης, να ξεκινάει με μόνον αμετάφραστα bits της διεύθυνσης, κι έτσι το TLB να δουλεύει εν παραλλήλω (ταυτόχρονα) με την κρυφή μνήμη, και άρα ολόκληρος ο μηχανισμός της εικονικής μνήμης να μην προκαλεί καμία επιπλέον καθυστέρηση στο τρέξιμο του επεξεργαστή, όσο οι σελίδες που χρησιμοποιεί ο επεξεργαστής έχουν τη μετάφρασή τους μέσα στο TLB. Οταν μιάν εικονική σελίδα δεν την βρίσκουμε στον TLB, τότε την αναζητάμε στους Πίνακες Μετάφρασης, που βρίσκονται στη μνήμη.

Ακριβέστερα, γιά την εν παραλήλλω λειτουργία TLB και level-1 (L1) cache φροντίζουμε ώστε το μέγεθος του κάθε way της L1 cache (= πλήθος sets επί line size) να είναι μικρότερο ή ίσο από το μέγεθος της σελίδας. Τότε, τα index bits –που χρειάζονται γιά να ξεκινήσει η προσπέλαση στην L1 cache– προέρχονται όλα από το αμετάφραστο κομάτι της διεύθυνσης (το page offset): το κομάτι εκείνο της φυσικής διεύθυνσης που το ξέρουμε αμέσως, αφού είναι ίσο με το αντίστοιχο κομάτι της εικονικής διεύθυνσης. Με αυτό το κομάτι ξεκινάει η πρόσβαση στην L1 cache. Ταυτόχρονα με το ξεκίνημα της πρόσβασης στην L1 cache, δίδεται και η εικονική σελίδα στο TLB γιά μετάφραση. Το TLB το κάνουμε να είναι τόσο γρήγορο όσο και η ανάγνωση των tags της L1 cache. Έτσι, με το που τελειώνει η ανάγνωση των tags στην L1 cache (όπου τα tags αυτά είναι φυσικές διευθύνσεις), έχει τελειώσει και η μετάφραση από το TLB (εάν ήταν εύστοχη), κι έτσι τα tags των lines που βρίσκονται στην cache συγκρίνονται με την μεταφρασμένη πλέον (από το TLB) φυσική διεύθυνση.

Προκειμένου να μην αναγκαζόμαστε να ακυρώνουμε τα περιεχόμενα του TLB σε κάθε αλλαγή της διεργασίας που τρέχει (context swap), θέλουμε να μπορούμε να έχουμε μέσα στο TLB, ταυτόχρονα, ζευγάρια εικονικών-φυσικών σελίδων πολλών διαφορετικών διεργασιών. Αυτό όμως απαιτεί να μπορούμε να τα ξεχωρίζουμε μεταξύ τους, αφού την κάθε ορισμένη εικονική διεύθυνση ενδέχεται να την χρησιμοποιούν πολλές διεργασίες αλλά γιά διαφορετική πληροφορία και κατά διαφορετικό τρόπο η κάθεμία. Γιά να γίνεται ο διαχωρισμός αυτός, καταγράφουμε τον αριθμό διεργασίας ("PID", Process Identifier) μαζί με τον αριθμό εικονικής σελίδας αυτής της διεργασίας σε κάθε θέση (ζευγάρι εικονικής-φυσικής σελίδας) του TLB.

(α) Θεωρήστε μιάν εικονική μνήμη με μεγέθη όπως της άσκησης 12.4, και θεωρήστε ότι το PID έχει μέγεθος 8 bits (μέχρι 256 ταυτόχρονες διεργασίες). Θεωρήστε ένα TLB μεγέθους 16 θέσεων, με πλήρως προσεταιριστική τοποθέτηση ζευγών (οιοδήποτε ζεύγος μετάφρασης μπορεί να μπεί οπουδήποτε στο TLB). Ποιά πεδία πρέπει να έχει η κάθε θέση αυτού του TLB, και τι μεγέθους το καθένα;

(β) Δώστε ένα αριθμητικό παράδειγμα του πλήρους περιεχομένου του TLB όταν αυτό περιέχει ζευγάρια μετάφρασης γιά τις παρακάτω εικονικές σελίδες· αποφασίστε μόνοι σας, αυθαίρετα (σαν να είσασταν το λειτουργικό σύστημα), σε ποιάν φυσική σελίδα θα τοποθετήστε την κάθε εικονική σελίδα που σας ζητείται να ευρίσκεται εν χρήσει:

(γ) Οι διεργασίες 3B και 3C, παραπάνω, είναι προστατευμένες η μία από την άλλη; Μπορεί η μία να διαβάσει τα δεδομένα της άλλης (κλέβοντας έτσι, π.χ., ο ένας χρήστης τον αριθμό πιστωτικής κάρτας που ο άλλος πληκτρολογεί στον browser του γιά μιάν αγορά μέσω διαδικτύου); Μπορεί η μία να αλλοιώσει (γράψει) τα δεδομένα της άλλης (παραπλανόντας έτσι, π.χ., ο ένας χρήστης τον άλλον); Μπορεί η μία να καταστρέψει (γράψει) τον κώδικα της άλλης ("κολλώντας" έτσι, π.χ., ο ένας χρήστης τον άλλον); Πώς εξασφαλίζουμε την επιθυμητή προστασία και ανεξαρτησία μεταξύ αυτών των δύο διεργασιών, ενώ ταυτόχρονα κάνουμε και οικονομία μνήμης κρατώντας ένα μόνο φυσικό αντίτυπο του κώδικα που αυτές τρέχουν;

Τρόπος Παράδοσης

Παραδώστε τη σειρά αυτή ασκήσεων on-line, σε μορφή PDF (μόνον) (μπορεί να είναι κείμενο μηχανογραφημένο ή/και "σκαναρισμένο" χειρόγραφο, αλλά μόνον σε μορφή PDF). Παραδώστε μέσω turnin ex12@hy225 [directoryName] ένα αρχείο ονόματι ex12.pdf που θα περιέχει τις απαντήσεις σας.
Θα εξεταστείτε και προφορικά για τις ασκήσεις 12, από βοηθό του μαθήματος, με διαδικασία γιά την οποία θα ενημερωθείτε μέσω ηλτά (email) στη λίστα του μαθήματος.

© copyright University of Crete, Greece. Last updated: 29 Apr. 2020 by M. Katevenis.