SRAM, DRAM, Προσπελάσεις Συνεχόμενων Λέξεων, Διαφύλλωση (Interleaving)

Μέσα στο chip της μνήμης, το κάθε block είναι ένας περίπου τετράγωνος πίνακας από στοιχεία μνήμης, με γύρω στις 64 έως 512 γραμμές επί 64 έως 512 στήλες. Γιά να διαβάσουμε ένα στοιχείο μνήμης επιλέγουμε πρώτα τη γραμμή στην οποία ανήκει αυτό, δίνοντας τη διεύθυνση γραμμής (row address) στον αποκωδικοποιητή γραμμής, ο οποίος ανάβει ένα σύρμα (word line) που διατρέχει και ενεργοποιεί την επιθυμητή γραμμή. Οταν ανάψει το σύρμα αυτό, όλα τα στοιχεία μνήμης (bits) πάνω στη γραμμή αυτή διαβάζονται, δηλαδή τοποθετούν το καθένα την τιμή του (περιεχόμενό του) στο αντίστοιχο σύρμα στήλης (bit line) που διατρέχει τη στήλη του. Ετσι, στο κάτω μέρος του block της μνήμης, στις απολήξεις των συρμάτων στήλης, εμφανίζεται το περιεχόμενο όλων των bits που είναι αποθηκευμένα στην επιλεγείσα γραμμή. Ενας μεγάλος πολυπλέκτης επιλέγει τότε το bit που εμείς θέλαμε, βάσει της διεύθυνσης στήλης (column address), και το δίνει προς τα έξω. Η όλη αυτή διαδικασία, από την είσοδο της διεύθυνσης γραμμής μέχρι να βγεί το τελικό bit στην έξοδο, διαρκεί αρκετό χρόνο (γύρω στα 60 ns γιά τις σημερινές DRAM).

Εάν μετά την παραπάνω διαδικασία, όμως, θέλουμε να διαβάσουμε και μερικά από τα "διπλανά" bits αυτού που μόλις διαβάσαμε, τότε αυτό μπορεί να γίνει πολύ γρηγορότερα: τα bits αυτά είναι "έτοιμα", στις απολήξεις των συρμάτων στήλης, και το chip της μνήμης μπορεί να τα αποστείλει στον αιτούντα την ανάγνωση (π.χ. τον επεξεργαστή) πολύ γρήγορα το ένα μετά το άλλο (περίπου 1 bit κάθε 4-5 ns σε καθένα από τα σύρματα δεδομένων (data) γιά τις σημερινές DRAM). Εκμεταλλευόμενοι τη δυνατότητα αυτή, πετυχαίνουμε να προσπελαύνουμε μεγάλες ομάδες γειτονικών λέξεων (π.χ. cache lines (blocks)) με πολύ μικρή επιπλέον επιβάρυνση σε σχέση με την αρχική καθυστέρηση προσπέλασης της πρώτης λέξης της ομάδας.

Η άλλη τεχνική που χρησιμοποιείται γιά την αύξηση της παροχής (throughput) μιάς μνήμης --κυρίως γιά προσπελάσεις σε τυχαίες διευθύνσεις και όχι τόσο γιά συνεχόμενες διευθύνσεις-- είναι η Διαφύλλωση Μνήμης (Memory Interleaving). Με την τεχνική αυτή, όταν οι διευθύνσεις που αποστέλονται σε ένα σύστημα μνήμης (π.χ. ένα chip) αναφέρονται σε διαφορετικά από τα blocks (memory banks) που αυτό περιέχει, τότε ο ρυθμός αποστολής τέτοιων διευθύνσεων --και ο αντίστοιχος ρυθμός έναρξης προσπελάσεων-- είναι πολύ ψηλότερος από τον ρυθμό προσπελάσεων σε κάθε ένα block (bank), δεδομένου ότι τα blocks (banks) δουλεύουν εν παραλλήλω, μ' ένα τρόπο που θυμίζει ομοχειρία (pipelining).

Ασκηση 10.1: Εικονική Μνήμη, Πίνακες Μετάφρασης

Ο βασικός τρόπος λειτουργίας της εικονικής μνήμης είναι ο εξής. Κάθε διεύθυνση μνήμης που γεννά ο επεξεργαστής --δηλαδή το πρόγραμμα που τρέχει-- θεωρείται ως "εικονική διεύθυνση", και μεταφράζεται σε μιάν άλλη, "φυσική διεύθυνση", προτού δοθεί στη μνήμη γιά να επιλέξει τη λέξη που τελικά θα προσπελάσει το πρόγραμμα. Η μετάφραση αυτή φροντίζει (i) να ελέγχει ότι η διεργασία που τρέχει έχει δικαίωμα να κάνει την προσπέλαση που ζητά (ανάγνωση/εγγραφή/εκτέλεση) στη διεύθυνση που ζητά, (ii) να μεταφράζει τις εικονικές διευθύνσεις της κάθε διεργασίας σε διαφορετικές φυσικές διευθύνσεις γιά την κάθε διεργασία, εκτός των περιπτώσεων που θέλουμε οι διεργασίες να επικοινωνούν μεταξύ τους μέσω κοινόχρηστης μνήμης (shared memory), και (iii) να μεταφράζει τις πιό συχνά (επί του παρόντος) χρησιμοποιούμενες εικονικές διευθύνσεις στις φυσικές διευθύνσεις όπου αυτές "χωράνε", ενώ όσες δεν χωράνε στην υπάρχουσα φυσική μνήμη προκαλούν σφάλμα σελίδας (page fault) (άσκηση 8.2), ώστε να φροντίσει το λειτουργικό σύστημα να τις φέρει (συνήθως από το δίσκο).

Η μετάφραση διευθύνσεων γίνεται απεικονίζοντας ολόκληρες "σελίδες (pages)" εικονικής μνήμης σε ολόκληρες φυσικές σελίδες. Το μέγεθος της σελίδας είναι αρκετά KBytes σήμερα, και η τάση είναι να μεγαλώνει με τα χρόνια. Γιά να γίνεται η μετάφραση γρήγορα, χρησιμοποιείται συνήθως ένας μικρός κατάλογος ζευγών εικονικής-φυσικής σελίδας γιά τις πιό συχνά χρησιμοποιούμενες σελίδες --ο " TLB (Translation Lookaside Buffer)", οργανωμένος σαν μιά μικρή κρυφή μνήμη, συνήθως πλήρως προσεταιριστική. Οταν μιάν εικονική σελίδα δεν την βρίσκουμε στον TLB, τότε την αναζητάμε στους Πίνακες Μετάφρασης, που βρίσκονται στη μνήμη.

Θεωρείστε το εξής μικρό (εξωπραγματικό σήμερα) σύστημα εικονικής μνήμης, σαν απλό παράδειγμα.

• Οι εικονικές διευθύνσεις έχουν μέγεθος 20 bits (δηλ. είναι πενταψήφιες στο δεκαεξαδικό σύστημα), άρα ο χώρος εικονικών διευθύνσεων είναι 1 MByte ανά διεργασία.
• Το μέγεθος σελίδας είναι 4 KBytes, άρα τα 12 LS bits κάθε διεύθυνσης (3 LS δεκαεξαδικά ψηφία) επιλέγουν 1 byte μέσα στη σελίδα, ενώ τα υπόλοιπα MS bits υποδηλώνουν γιά ποιά σελίδα μιλάμε. Ετσι, η κάθε διεργασία έχει 256 εικονικές σελίδες (= 1 MByte / 4 KBytes).
• Η φυσική μνήμη είναι 64 KBytes, άρα οι φυσικές διευθύνσεις αποτελούνται από 16 bits (4 δεκαεξαδικά ψηφία), επομένως υπάρχουν 16 φυσικές σελίδες (= 16 KBytes / 4 KBytes).

• Χωρίζουμε την εικονική διεύθυνση σε 12 LS bits, που υποδηλώνουν το byte μέσα στη σελίδα (εδώ: 210), και στα 8 MS bits, που ορίζουν την εικονική σελίδα (εδώ: FE).
• Τα 12 LS bits (210) δεν χρειάζονται μετάφραση, αφού απεικονίζουμε ολόκληρες εικονικές σελίδες σε ολόκληρες φυσικές σελίδες, και αφού όλες οι σελίδες είναι ευθυγραμμισμένες στα φυσικά όριά τους.
• Τα 8 MS bits, δηλαδή ο αριθμός εικονικής σελίδας (FE), χρησιμοποιούνται σαν index στον πίνακα μετάφρασης. Υπάρχει ένας πίνακας μετάφρασης γιά κάθε διεργασία, και ο πίνακας αυτός έχει μέγεθος 256 θέσεις --όσες και οι εικονικές σελίδες ανά διεργασία.
• Η (φυσική) διεύθυνση βάσης του πίνακα μετάφρασης της διεργασίας που τρέχει αυτή τη στιγμή είναι γραμμένη (από το λειτουργικό σύστημα) σ' έναν ειδικό καταχωρητή του συστήματος διαχείρισης μνήμης (όχι στην κανονική register file). (Οταν ο επεξεργαστής τρέχει σε user mode, δεν επιτρέπεται να γράψει αυτόν τον καταχωρητή, ούτως ώστε να μην μπορεί να υποκριθεί ότι είναι άλλη διεργασία, δηλαδή να μην μπορεί να αποκτήσει πρόσβαση στη μνήμη άλλων διεργασιών).
• Κάθε θέση του πίνακα μετάφρασης περιέχει: 1 "valid" bit που υποδεικνύει αν η εικονική σελίδα που μας έφερε εδώ υπάρχει ή όχι στη φυσική μνήμη (μπορεί να μην υπάρχει είτε διότι είναι παράνομη, είτε διότι είναι νόμιμη μεν αλλά έχει "εκδιωχθεί" στο δίσκο), τον αριθμό της φυσικής σελίδας (4 bits) όπου απεικονίζεται αυτή η εικονική σελίδα (όταν αυτή υπάρχει στη φυσική μνήμη), τα bits προστασίας (π.χ. 3 bits: "rwx") που δηλώνουν τι επιτρέπεται να κάνει η παρούσα διεργασία στις λέξεις αυτής της σελίδας, 1 "dirty" bit που δείχνει αν ο επεξεργαστής άλλαξε ή όχι τα περιεχόμενα αυτής της σελίδας από τότε που την διαβάσαμε από το δίσκο, και 1 "reference" bit που το χρησιμοποιεί το λειτουργικό σύστημα γιά να προσεγγίσει τον αλγόριθμο αντικατάστασης "LRU" (σε κάθε προσπέλαση στη σελίδα, ο επεξεργαστής θέτει αυτό το bit, ενώ το λειτουργικό σύστημα περιοδικά διαβάζει αυτά τα bits γιά να δεί ποιές σελίδες χρησιμοποιήθηκαν πρόσφατα, και στη συνέχεια τα μηδενίζει).
• Μετά τον έλεγχο ότι η εικονική σελίδα FE που θέλουμε υπάρχει στη φυσική μνήμη, και έχουμε δικαίωμα να την προσπελάσουμε όπως ζητά ο επεξεργαστής, παίρνουμε τα 4 bits της φυσικής σελίδας από τον πίνακα μετάφρασης --έστω ότι είναι η σελίδα A, τους κολάμε και τα 12 αμετάφραστα LS bits (210), και φτιάχνουμε έτσι τα 16 bits της φυσικής διεύθυνσης --A210, εδώ.

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

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

• Εικονική σελίδα 00: παράνομη (περιέχει τον NULL pointer).
• Εικονική σελίδα 01: περιέχει κώδικα (r-x), και βρίσκεται στη φυσική σελίδα 7.
• Εικονική σελίδα 02: περιέχει κώδικα (r-x), και βρίσκεται στη φυσική σελίδα C.
• Εικονική σελίδα 03: περιέχει στατικά δεδομένα (rw-), και βρίσκεται στη φυσική σελίδα 0, dirty.
• Εικονικές σελίδες 04 έως και 9F: δεν βρίσκονται στη φυσική μνήμη αυτή τη στιγμή.
• Εικονική σελίδα A0: περιέχει δυναμικά δεδομένα (r--), και βρίσκεται στη φυσική σελίδα D.
• Εικονική σελίδα A1: περιέχει δυναμικά δεδομένα (rw-), και βρίσκεται στη φυσική σελίδα E, dirty.
• Εικονικές σελίδες A2 έως και FD: δεν βρίσκονται στη φυσική μνήμη αυτή τη στιγμή.
• Εικονική σελίδα FE: περιέχει δεδομένα στοίβας (rw-), και βρίσκεται στη φυσική σελίδα A, dirty.
• Εικονική σελίδα FF: περιέχει δεδομένα στοίβας (rw-), και βρίσκεται στη φυσική σελίδα 1, clean.

(γ) Σε ποιά φυσική διεύθυνση μεταφράζονται οι παρακάτω εικονικές διευθύνσεις, ή ποιές από αυτές προκαλούν σφάλμα σελίδας: 02038 (fetch), 03FF4 (read), A001C (write), 01920 (fetch), 00000 (read), 92FC0 (read), FE5D8 (write), 03FF4 (fetch), A1FFC (read), A2000 (read), 01E40 (write).

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

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

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

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

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

• Οι εικονικές διευθύνσεις έχουν μέγεθος 64 bits. Ομως, γιά πρακτικούς λόγους, μονο τα 46 LS από αυτά χρησιμοποιούνται (χώρος εικονικών διευθύνσεων 16 TeraBytes ανά διεργασία...). Γιά να μην μπουν οι χρήστες στο πειρασμό να "εκμεταλλευτούν" τα 18 MS bits του κάθε pointer που περισεύουν γιά άλλο σκοπό, χάνοντας έτσι το portability των προγραμμάτων τους σε μελλοντικές γενιές συστημάτων με περισσότερα υλοποιημένα bits εικονικής διεύθυνσης, το σύστημά μας ελέγχει κάθε προσπέλαση μνήμης γιά να σιγουρευτεί ότι αυτά τα 18 MS bits της διεύθυνσης ισούνται όλα με το MS bit των 46 LS bits, δηλαδή αποτελούν επέκταση προσήμου (sign extension) του υλοποιημένου μέρους της εικονικής διεύθυνσης (έτσι, μπορεί η στοίβα να συνεχίσει να τοποθετείται στο άνω άκρο του εικονικού χώρου μνήμης (διευθύνσεις FFFFFF...).
• Μέγεθος σελίδας 64 KBytes. Επομένως τα 16 LS bits της εικονικής διεύθυνσης δεν χρειάζονται μετάφραση.
• Τρία επίπεδα πινάκων μετάφρασης ανά διεργασία.
• Κάθε πίνακας μετάφρασης έχει μέγεθος 1024 θέσεις, άρα "κοιτάζει" 10 από τα bits του αριθμού εικονικής σελίδας.

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

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

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

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

• Την εικονική σελίδα 01 της διεργασίας 3B (περιέχει κώδικα), και την εικονική σελίδα 01 της διεργασίας B4 (περιέχει data r/w), οι οποίες αναφέρονται σε εντελώς διαφορετικές, ανεξάρτητες φυσικές σελίδες.
• Η διεργασία 3B και η διεργασία 3C αποτελούν διαφορετικές ενεργοποιήσεις του ιδίου προγράμματος, π.χ. ο ίδιος web browser τρεγμένος από δύο διαφορετικούς χρήστες. Γιά οικονομία (φυσικής) μνήμης, το λειτουργικό σύστημα κρατά μόνο ένα αντίτυπο του κώδικα αυτής της εφαρμογής στη μνήμη, και κάνει όλες τις διεργασίες που το τρέχουν να "βλέπουν" αυτό το μοναδικό κοινόχρηστο αντίτυπο στη δική της εικονική μνήμη η κάθε μία. Βάλτε λοιπόν στο TLB και την εικονική σελίδα 01 της διεργασίας 3C, που περιέχει τον ίδιο κώδικά με τη σελίδα 01 της 3B.
• Την εικονική σελίδα FF της διεργασίας 3B, και την εικονική σελίδα FF της διεργασίας 3C, που περιέχουν δεδομένα στοίβας. Οπως είπαμε, αυτές οι δύο διεργασίες αποτελούν διαφορετικές ενεργοποιήσεις του ιδίου προγράμματος. Παρά το γεγονός ότι ο κώδικας των δύο αυτών διεργασιών είναι κοινός, τα δεδομένα τους όμως είναι διαφορετικά, αφού π.χ. άλλα κάνει ο ένας χρήστης με τον web browser του, και άλλα ο άλλος.
• Οι διεργασίες D2 και D3 συνεργάζονται μεταξύ τους, και επικοινωνούν μέσω κοινόχρηστης μνήμης: Η διεργασία D2 παράγει δεδομένα προς επεξεργασία, και τα γράφει στην εικονική σελιδα της A0 (προστασία -w-). Η διεργασία D3 καταναλώνει τα δεδομένα που παράγει η D2, και τα επεξεργάζεται. Η D3 διαβάζει τα δεδομένα αυτά από την εικονική σελίδα της C0 (προστασία r--), η οποία όμως, μέσω του συστήματος εικονικής μνήμης, αντιστοιχεί στην ίδια φυσική σελίδα στην οποία αντιστοιχεί και η A0 της D2, ώστε να επιτυγχάνεται η συνεργασία παραγωγού-καταναλωτή των δύο διεργασιών. Βάλτε στο TLB σας και αυτές τις δύο εικονικές σελίδες.

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

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

        tar -cvf ask10.tar   ask10.[xyz]
        gzip ask10.tar
        ~hy225/bin/submit 10