Μπορούμε να φανταστούμε έναν αφηρημένο διερμηνευτή ο οποίος ενημερώνει μία εσωτερική στοιχειοσειρά Μ που παρακολουθεί την κατάσταση της μνήμης. Η στοιχειοσειρά αυτή:
* Περιέχει τόσα στοιχεία, όσες είναι και οι ιδεατές σελίδες της διεργασίας, τα οποία συμβολίζουμε με @@n@@.
* Διαιρείται σε δύο τμήματα.
** Το πάνω τμήμα με @@m@@ εγγραφές, περιέχει όλες τις σελίδες που βρίσκονται τη συγκεκριμένη χρονική στιγμή στη μνήμη. Αυτά είναι τα πλαίσια της φυσικής μνήμης.
** Το κάτω τμήμα, με @@n-m@@ εγγραφές, περιέχει όλες τις σελίδες στις οποίες έχει γίνει αναφορά τουλάχιστον μία φορά, αλλά έχουν απομακρυνθεί και δεν βρίσκονται πλέον στην μνήμη.
* Αρχικά η Μ είναι ένα κενό σύνολο, από τη στιγμή που δεν έχει γίνει καμία αναφορά σε σελίδες, ενώ καμία σελίδα δε βρίσκεται ακόμη στην μνήμη.

Ο διερμηνευτής δουλεύει ως εξής:
* Διαβάζει μία μία τη στοιχειοσειρά αναφορών
* Αν η ζητούμενη σελίδα δεν υπάρχει στη μνήμη (στις @@m@@ εγγραφές) τότε
** Δημιούργησε σφάλμα σελίδας (page fault - P)
** Αν υπάρχει κενό πλαίσιο στην μνήμη (το άνω τμήμα της Μ έχει λιγότερες από @@m@@ εγγραφές), τότε
*** Τοποθέτησε τη ζητούμενη σελίδα στο άνω τμήμα της Μ
** Αλλιώς
*** Χρησιμοποίησε τον αλγόριθμο αντικατάστασης σελίδων για να αφαιρέσει μία σελίδα από την μνήμη και να τοποθετήσει την νέα.
* Αν η ζητούμενη σελίδα υπήρχε στη μνήμη, απλά διαβάζεται από τη διεργασία

Η διεργασία έχει 8 ιδεατές σελίδες στο διάστημα διευθύνσεών της. Υπολογίστε τα διανύσματα C και F για αυτή τη διεργασία. Πόσα λάθη σελίδας δημιούργησε;

Η μνήμη έχει 5 πλαίσια, άρα τα λάθη δίνονται από το F'_5_', δηλαδή 9 λάθη.

Conceptually, we can imagine an abstract interpreter that works as follows. It maintains an internal array, M, that keeps track of the state of memory. It has as many elements as the process has virtual pages, which we will call n. The array M is divided into two parts. The top part, with m entries, contains all the pages that are currently in memory. The bottom part, with n − m pages, contains all the pages that have been referenced once but have been paged out and are not currently in memory. Initially, M is the empty set, since no pages have been referenced and no pages are in memory.

As execution begins, the process begins emitting the pages in the reference string, one at a time. As each one comes out, the interpreter checks to see if the page is in memory (i.e., in the top part of M). If it is not, a page fault occurs. If there is an empty slot in memory (i.e., the top part of M contains fewer than m entries), the page is loaded and entered in the top part of M. This situation arises only at the start of execution. If memory is full (i.e., the top part of M contains m entries), the page replacement algorithm is invoked to remove a page from memory. In the model, what happens is that one page is moved from the top part of M to the bottom part, and the needed page entered into the top part. In addition, the top part and the bottom part may be separately rearranged.

{- Οι θέσεις 1 ως 4 αντιστοιχούν σε πλαίσια της φυσική μνήμης, οι σελίδες δηλαδή που βρίσκονται σε αυτές τις θέσεις είναι στη φυσική μνήμη. Οι θέσεις 5-8 αντιστοιχούν σε σελίδες της εικονικής μνήμης και όσες σελίδες βρίσκονται σε αυτές τις θέσεις δεν είναι στη φυσική μνήμη (συνήθως βρίσκονται στο δίσκο). Οι τιμές αυτές (1-4, 5-8) καθορίζονται από την εκφώνηση. -}

!! Άσκηση

Ένα υπολογιστικό σύστημα παρέχει στους χρήστες χώρο διευθύνσεων στην εικονική μνήμη των 2'^32^' bytes. Ο υπολογιστής έχει 2'^18^' bytes φυσικό χώρο διευθύνσεων. Η εικονική μνήμη χρησιμοποιεί σελιδοποίηση με μέγεθος σελίδας 4096 bytes. Μια διεργασία χρήση ζητάει την εικονική διεύθυνση 11123456. Εξηγείστε πως το σύστημα θα βρει την φυσική διεύθυνση για την παραπάνω εικονική.

Για τον χώρο των εικονικών διευθύνσεων χρησιμοποιούνται 32bit. Από αυτά τα 12bit είναι για το μέγεθος της σελίδας (4096=2'^12^'). Τα υπόλοιπα 20bit χρησιμοποιούνται για τον πίνακα σελίδων.

Η εικονική διεύθυνση σε δυαδική μορφή είναι: 0001 0001 0001 0010 0011 0100 0101 0110

Τα 20 πρώτα bit μας δίνουν τον αριθμό σελίδας και τα υπόλοιπα 12 την μετατόπιση.

Αριθμός Σελίδας: 0001 0001 0001 0010 0011 = 69923'_(10)_'
Μετατόπιση: 0100 0101 0110 = 1110'_(10)_'

Το σύστημα από τον πίνακα σελίδων θα βρει σε πιο πλαίσιο αντιστοιχεί η σελίδα. Το πλαίσιο αυτό θα αποτελέσει (σε δυαδική μορφή) τα πρώτα bits της φυσική διεύθυνσης και τα 12 τελευταία bits θα είναι αυτά της μετατόπισης.

>><<

----

!! Exercise

Για κάθε μία από τις παρακάτω εικονικές διευθύνσεις (οι οποίες είναι σε δεκαδική μορφή), υπολόγισε την εικονική σελίδα και τη μετατόπιση (offset) για μέγεθος σελίδας 4Κ και 8Κ: 20000, 32768, 60000.

>>answer<<

!! Απάντηση

@@C'_1_'=4, C'_2_'=3, C'_3_'=3, C'_4_'=3, C'_5_'=2, C'_6_'=1, C'_7_'=0, C'_8_'=0, C'_∞_'=8@@

Η διεργασία έχει 8 ιδεατές σελίδες στο διάστημα διευθύνσεών της. Υπολογίστε τα διανύσματα C και F για αυτή τη διεργασία.

>>answer<<

!! Απάντηση

@@C'_1_'=1, C'_2_'=8, C'_3_'=6, C'_4_'=6, C'_5_'=2, C'_6_'=1, C'_7_'=0, C'_8_'=0, C'_∞_'=8@@

@@F'_1_' = C'_2_' + C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 31@@\\
@@F'_2_' = C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 23@@\\
@@F'_3_' = C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 17@@\\
@@F'_4_' = C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 11@@\\
@@F'_5_' = C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 9@@\\
@@F'_6_' = C'_7_' + C'_8_' + C'_∞_' = 8@@\\
@@F'_7_' = C'_8_' + C'_∞_' = 8@@\\
@@F'_8_' = C'_∞_' = 8@@

>><<

[@

@@F'_8_' = C'_∞_' = 8@@
@]

@@F'_1_' = C'_2_' + C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 20@@\\
@@F'_2_' = C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 17@@\\
@@F'_3_' = C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 14@@\\
@@F'_4_' = C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 11@@\\
@@F'_5_' = C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 9@@\\
@@F'_6_' = C'_7_' + C'_8_' + C'_∞_' = 8@@\\
@@F'_7_' = C'_8_' + C'_∞_' = 8@@\\
@@F'_8_' = C'_∞_' = 8@@\\

Το διάνυσμα C έχει το πλήθος των εμφανίσεων της κάθε θέσης μνήμης στην στοιχειοσειρά αποστάσων. Το C'_1_' έχει το πλήθος των σελίδων που ζητήθηκαν και βρίσκονταν στην 1η θέση μνήμης. Έτσι, από τη στοιχειοσειρά αποστάσεων έχουμε:

@@F'_1_' = C'_2_' + C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 20@@

F_m=sum_(k=m+1)^n=C_k+C_oo

@@F'_1_' = C'_2_' + C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 20

F'_8_' = C'_∞_' = 8@@

C'_1_'=4, C'_2_'=3, C'_3_'=3, C'_4_'=3, C'_5_'=2, C'_6_'=1, C'_7_'=0, C'_8_'=0, C'_∞_'=8

Το διάνυσμα F δίνεται από τον τύπο

(:eqn :) [=
F_m=sum_(k=m+1)^n=C_k+C_∞
=]
->n: ο αριθμός των σελίδων της ιδεατής μνήμης

Έχουμε, λοιπόν:

@@
F'_1_' = C'_2_' + C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 20
F'_2_' = C'_3_' + C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 17
F'_3_' = C'_4_' + C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 14
F'_4_' = C'_5_' + C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 11
F'_5_' = C'_6_' + C'_7_' + C'_8_' + C'_∞_' = 9
F'_6_' = C'_7_' + C'_8_' + C'_∞_' = 8
F'_7_' = C'_8_' + C'_∞_' = 8
F'_8_' = C'_∞_' = 8
@@

Το κάθε F'_x_' δηλώνει εκτίμηση για τον αριθμό των λαθών σελίδας που θα έχουμε με βάση τη στοιχεισειρά αποστάσεων αν χρησιμοποιήσουμε x σελίδες. Δηλαδή, αν χρησιμοποιήσουμε 5 σελίδες, η εκτίμηση είναι F'_5_'=9 λάθη σελίδας.

>><<

----

!! Ερώτηση

>>center<<

>><<

# Βρείτε το διάνυσμα C

Ο αλγόριθμος LRU μπορεί να εξομοιωθεί με την ακόλουθη λογική:
# Όταν γίνεται αναφορά σε μια σελίδα, αυτή μεταφέρεται στην πρώτη σελίδα
##%alpha% Αν δεν υπήρχε στα πλαίσια της φυσική μνήμης ούτε στις σελίδες της εικονικής, τότε δημιουργείται λάθος σελίδας (Ρ) και στη στοιχειοσειρά αποστάσεων αναφέρεται ως άπειρο (∞)
## Αν δεν υπήρχε στα πλαίσια της φυσική μνήμης αλλά υπήρχε στις σελίδες της εικονικής, τότε δημιουργείται λάθος σελίδας (Ρ) και στη στοιχειοσειρά αποστάσεων αναφέρεται ο αριθμός σελίδας στον οποίο βρισκόταν
## Αν υπήρχε στα πλαίσια της φυσικής μνήμης, τότε δεν έχουμε λάθος σελίδας και στη στοιχειοσειρά αποστάσεων αναφέρεται ο αριθμός σελίδας στον οποίο βρισκόταν
# Οι σελίδες που βρίσκονταν κάτω από τη σελίδα στην οποία έγινε αναφορά, δεν μετακινούνται.

3: | | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 3 | 4 | 4 | 7 | 7 | 7 | 5 | 5 | 5 | 3 | 3 | 7 | 1 | 3 |
4: | | | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 6 | 6 | 6 | 4 | 4 | 4 | 7 | 7 | 7 | 5 | 5 | 5 | 7 | 7 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
5: | | | | | | 0 | 2 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 |
6: | | | | | | | 0 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
7: | | | | | | | | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
8: | | | | | | | | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

Στοιχειοσειρά αποστάσεων: ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞ 4 2 3 1 5 1 2 6 1 1 4 2 3 5 3

Οι θέσεις 1 ως 4 αντιστοιχούν σε πλαίσια της φυσική μνήμης, οι σελίδες δηλαδή που βρίσκονται σε αυτές τις θέσεις είναι στη φυσική μνήμη. Οι θέσεις 5-8 αντιστοιχούν σε σελίδες της εικονικής μνήμης και όσες σελίδες βρίσκονται σε αυτές τις θέσεις δεν είναι στη φυσική μνήμη (συνήθως βρίσκονται στο δίσκο). Οι τιμές αυτές (1-4, 5-8) καθορίζονται από την εκφώνηση.

Η αίτηση για τη σελίδα 0 την εισάγει στην θέση ένα (1). Η σελίδα δεν υπήρχε σε καμία θέση, έτσι έχουμε λάθος σελίδας και ∞ στην στοιχειοσειρά αποστάσεων. Το ίδιο γίνεται και για τις σελίδες 2, 1, 3, 5, 4 και 6. Όταν γίνεται αίτηση για τη σελίδα 3, αυτή βρισκόταν στη θέση 4 η οποία ανήκει στη φυσική μνήμη (η οποία έχει 4 πλαίσια σύμφωνα με την εκφώνηση), έτσι δεν έχουμε λάθος σελίδας και στη στοιχειοσειρά αποστάσεων την τιμή 4. Η σελίδα μπαίνει στην θέση 0 και όσες βρίσκονταν από πάνω της ολισθένουν μία θέση κάτω. Οι επόμενες αιτήσεις εξυπηρετούνται όπως φαίνεται παραπάνω. Η δεύτερη αίτηση για τη σελίδα 5 τη βρίσκει στη θέση 5 η οποία δεν αντιστοιχεί σε πλαίσιο της φυσική μνήμης. Αυτό δημιουργεί λάθος σελίδας και στη στοιχειοσειρά αποστάσεων μπαίνει η τιμή 5. Οι υπόλοιπες αιτήσεις ακολουθούν την ίδια λογική.

Το διάνυσμα C έχει το πλήθος των εμφανίσεων της κάθε θέσης μνήμης στην στοιχειοσειρά αποστάσων. Το C'_1_' έχει τις εμφανίσεις τη Έτσι, από τη στοιχειοσειρά αποστάσεων έχουμε:
C'_1_'=4, C'_2_'=3, C'_3_'=3, C'_4_'=3, C'_5_'=2, C'_6_'=1, C'_7_'=0

Στοιχειοσειρά αναφορών: 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 1 3 4 1
1: | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 7 | 4 | 7 | 3 | 3 | 5 | 5 | 3 | 1 | 1 | 1 | 7 | 1 | 3 | 4 | 1 |
2: | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 7 | 4 | 7 | 7 | 3 | 3 | 5 | 3 | 3 | 3 | 1 | 7 | 1 | 3 | 4 |
3: | | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 3 | 4 | 4 | 7 | 7 | 7 | 5 | 5 | 5 | 3 | 3 | 7 | 1 |
4: | | | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 6 | 6 | 6 | 4 | 4 | 4 | 7 | 7 | 7 | 5 | 5 | 5 | 7 |

5: | | | | | | 0 | 2 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 4 | 4 | 4 | 4 | 4 | 4 | 5 |
6: | | | | | | | 0 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
7: | | | | | | | | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
8: | | | | | | | | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Λάθη σελίδας: P P P P P P P P P P P
Στοιχειοσειρά αποστάσεων: ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞ 4 2 3 1 5 1 2 6 1 1 4 2 3 5

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

>>center<<
@@0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 1 3 4 1@@
>><<

Ο αλγόριθμος αντικατάστασης σελίδων που χρησιμοποιείται είναι ο LRU.

# Βρείτε τα λάθη σελίδας που δημιουργούνται
# Ποια είναι η στοιχειοσειρά αποστάσεων;
# Βρείτε το διάνυσμα F
# Βρείτε το διάνυσμα C

>>answer<<

!! Απάντηση

[@
Στοιχειοσειρά αναφορών: 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 1 3 4 1
| | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | 7 | | | | | | | | | | | | | | |
| | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | 3 | | | | | | | | | | | | | | |
| | | | 0 | 2 | 1 | 3 | 5 | 4 | 6 | | | | | | | | | | | | | | |
| | | | | 0 | 2 | 1 | 3 | 5 | 4 | | | | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | 0 | 2 | 1 | 1 | 5 | | | | | | | | | | | | | | |
| | | | | | | 0 | 2 | 2 | 1 | | | | | | | | | | | | | | |
| | | | | | | | 0 | 0 | 2 | | | | | | | | | | | | | | |
| | | | | | | | | | 0 | | | | | | | | | | | | | | |
Λάθη σελίδας: P P P P P P P P
Στοιχειοσειρά αποστάσεων: ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞

@]

∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 2 2 4 3 4 3 5 2 3 2 4 2 4 3 2 3 2 4 6 1 2 3 5

>><<

----

!! Ερώτηση

Στον παρακάτω πίνακα σελίδων ποια σελίδα θα αντικατασταθεί με βάση τον αλγόριθμο Working Set αν τ=400 και ο τρέχον εικονικός χρόνος είναι 2204;

||border=1px
||! Σελίδα ||! Χρόνος τελευταίας προσπέλασης ||! R bit ||
|| 0 || 2084 || 1 ||
|| 1 || 2003 || 1 ||
|| 2 || 1980 || 1 ||
|| 3 || 1213 || 0 ||
|| 4 || 2014 || 1 ||
|| 5 || 2020 || 1 ||
|| 6 || 2032 || 1 ||
|| 7 || 1620 || 0 ||

>>answer<<

!! Απάντηση

Ο αλγόριθμος αφαιρεί σελίδα η οποία έχει R=0 και ηλικία > τ (ηλικία = Τρέχον εικονικός χρόνος - Χρόνος τελευταίας προσπέλασης).

Η σελίδα με τον μικρότερο χρόνο και R=0 είναι η 3. Η ηλικία της είναι 2204-1213=991>400 άρα αφαιρείται.

>><<

----

!! Ερώτηση

Μια διεργασία παράγει την ακόλουθη στοιχειοσειρά αποστάσεων για μια μνήμη 5 πλαισίων και με τη χρήση του αλγόριθμου LRU:

|| border=1

!! Άσκηση

Ένας υπολογιστής παρέχει σε κάθε διεργασία χώρο διευθύνσεων 65536 bytes που διαιρείται σε σελίδων των 4096 bytes. Ένα συγκεκριμένο πρόγραμμα έχει ένα κείμενο μεγέθους 32768 bytes, δεδομένα μεγέθους 16386 bytes και μια στοίβα μεγέθους 15870 bytes. Θα μπορέσει αυτό το πρόγραμμα να χωρέσει στην μνήμη; Αν το μέγεθος της σελίδας ήταν 512 bytes, θα ταιριάζει; Θυμηθείτε ότι μια σελίδα δεν μπορεί να περιέχει κομμάτια δύο διαφορετικών τμημάτων.

Για σελίδες των 4096 bytes, χρειάζονται:
* Κείμενο: 32768 / 4096 = 8 σελίδες
* Δεδομένα: 16386 / 4096 = 4,000488281 = 5 σελίδες (για το λίγο ακόμη που χρειάζεται παίρνει ολόκληρη την επιπλέον σελίδα)
* Στοίβα: 15870 / 4096 = 3,874511719 = 4 σελίδες

Συνολικά χρειάζεται 17 σελίδες. Στη μνήμη είναι διαθέσιμες 65536 / 4096 = 16 σελίδες. Άρα το πρόγραμμα δεν χωράει.

Για σελίδες των 512 bytes, χρειάζονται:
* Κείμενο: 32768 / 512 = 64 σελίδες
* Δεδομένα: 16386 / 512 = 32,00390625 = 33 σελίδες
* Στοίβα: 15870 / 512 = 30,99609375 = 31 σελίδες

Συνολικά χρειάζεται 128 σελίδες. Στη μνήμη είναι διαθέσιμες 65536 / 512 = 128 σελίδες. Άρα το πρόγραμμα χωράει.

>><<

----

!! Exercise

A computer whose processes have 1024 pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is 5 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (virtual page, physical page frame) pairs, and can do a look up in 1 nsec. What hit rate is needed to reduce the mean overhead to 2 nsec?

>>answer<<

!! Απάντηση

'''1ο Τρόπος:''' Ξεκινάμε τους μετρητές από την αρχική κατάσταση (00000000) και για κάθε 4δα R bits, βάζουμε τα bit στους αντίστοιχους μετρητές

|| 0 || 00000000 || 00000000 || 10000000 || 11000000 || 11100000 || 01110000 || 10111000 || 11011100 || 01101110 ||

'''2ος Τρόπος:''' Μπορούμε να βάλουμε τα R bits το ένα κάτω από το άλλο με αντίστροφη σειρά (από το τελευταίο προς το πρώτο). Τα bits της πρώτης στήλης αντιστοιχούν στη σελίδα 0, της δεύτερης στην 1 κ.ο.κ.

-----

!! Ερώτηση

Ένας υπολογιστής έχει τέσσερα πλαίσια σελίδας. Ο χρόνος φόρτωσης και τελευταίας προσπέλασης καθώς και οι τιμές των R μαι Μ bits. Δίνονται παρακάτω.

|| border=1px
||! Σελίδα ||! Φόρτωση ||! Προσπέλαση ||! R ||! M ||
|| 0 || 126 || 280 || 1 || 0 ||
|| 1 || 230 || 265 || 0 || 1 ||
|| 2 || 140 || 270 || 0 || 0 ||
|| 3 || 110 || 285 || 1 || 1 ||

Ποια σελίδα θα αντικατασταθεί σύμφωνα με τους αλγόριθμους:
#%alpha% NRU
# LRU
# FIFO
# LRU
# Δεύτερης ευκαιρίας

>>answer<<

!! Απάντηση

#%alpha% NRU: Αντικαθιστά σελίδα από την κατηγορία 0 (R=0, M=0), άρα τη σελίδα 2
# FIFO: Με βάση την φόρτωση θα αφαιρέσει εκείνη με το μικρότερο χρόνο, δηλαδή, τη σελίδα 3
# LRU: Με βάση την τελευταία προσπέλαση θα αφαιρέσει εκείνη με το μικρότερο χρόνο, δηλαδή, τη σελίδα 1
# Δεύτερης ευκαιρίας: Με βάση την φόρτωση, υποψήφια είναι η σελίδα 3. Έχει, όμως, R=1, οπότε γίνεται R=0 και βρίσκει την αμέσως επόμενη που είναι η 0. Και αυτή έχει R=1, το οποίο γίνεται 0 και βρίσκει την επόμενη η οποία είναι η 2. Αυτή έχει R=0 οπότε και αφαιρείται.

>><<

Υπάρχουν δύο τρόποι για να βρούμε τους μετρητές.

# Ξεκινάμε τους μετρητές από την αρχική κατάσταση (00000000) και για κάθε 4δα R bits, βάζουμε τα bit στους αντίστοιχους μετρητές

|| 0 || 00000000 || 00000000 || 10000000 || 11000000 || 11000000 || 01100000 || 10110000 || 11011000 || 01101100 ||
|| 1 || 00000000 || 10000000 || 01000000 || 00100000 || 10010000 || 01001000 || 00100100 || 10010010 || 01001001 ||
|| 2 || 00000000 || 10000000 || 11000000 || 11100000 || 01110000 || 10111000 || 11011100 || 01101110 || 00110111 ||
|| 3 || 00000000 || 10000000 || 11000000 || 01100000 || 10110000 || 01011000 || 00101100 || 00010110 || 10001011 ||

# Μπορούμε να βάλουμε τα R bits το ένα κάτω από το άλλο με αντίστροφη σειρά (από το τελευταίο προς το πρώτο). Τα bits της πρώτης στήλης αντιστοιχούν στη σελίδα 0, της δεύτερης στην 1 κ.ο.κ.

|| border=1px
|| ||! Μετρητές ||||||||
||! Σελίδα ||! 0 ||! 1 ||! 2 ||! 3 ||
||! R bits || 0 || 0 || 0 || 1 ||
|| || 1 || 1 || 0 || 0 ||
|| || 1 || 0 || 1 || 0 ||
|| || 0 || 0 || 1 || 0 ||
|| || 1 || 1 || 0 || 1 ||
|| || 1 || 0 || 1 || 0 ||
|| || 1 || 0 || 1 || 1 ||
|| || 0 || 1 || 1 || 1 ||

>><<

||! Σελίδα ||! Αρχική κατάσταση ||! R bits: 0111 ||! R bits: 1011 ||! R bits: 1010 ||! R bits: 1101 ||! R bits: 0010 ||! R bits: 1010 ||! R bits: 1100 ||! R bits: 0001 ||
|| 0 || 00000000 || 00000000 || 10000000 || 11000000 || 11000000 || 01100000 || 10110000 || 11011000 || 01101100
|| 1 || 00000000 || 10000000 || 01000000 || 00100000 || 10010000 || 01001000 || 00100100 || 10010010 || 01001001
|| 2 || 00000000 || 10000000 || 11000000 || 11100000 || 01110000 || 10111000 || 11011100 || 01101110 || 00110111
|| 3 || 00000000 || 10000000 || 11000000 || 01100000 || 10110000 || 01011000 || 00101100 || 00010110 || 10001011

>><<

----

!! Exercise

A small computer has four page frames. At the first clock tick, the R bits are 0111 (page 0 is 0, the rest are 1). At subsequent clock ticks, the values are 1011, 1010, 1101, 0010, 1010, 1100, and 0001. If the aging algorithm is used with an 8-bit counter, give the values of the four counters after the last tick.

>>answer<<

!! Απάντηση

Αρχική κατάσταση:
|| border=1px
||! Σελίδα ||! Αρχική κατάσταση ||! R bits: 0111 ||! R bits: 1011 ||
|| 0 || 00000000 || 00000000 || 10000000 ||
|| 1 || 00000000 || 10000000 || 01000000 ||
|| 2 || 00000000 || 10000000 || 11000000 ||
|| 3 || 00000000 || 10000000 || 11000000 ||

* FIFO

[@
0 1 7 2 3 2 7 1 0 3
| | 0 | 1 | 7 | 2 | 3 | 3 | 3 | 3 | 0 | 0 |
| | | 0 | 1 | 7 | 2 | 2 | 2 | 2 | 3 | 3 |
| | | | 0 | 1 | 7 | 7 | 7 | 7 | 2 | 2 |
| | | | | 0 | 1 | 1 | 1 | 1 | 7 | 7 |
P P P P P P
@]

Συνολικά 6 λάθη σελίδας.

* LRU

* FIFO

[@
0 1 7 2 3 2 7 1 0 3
| | 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| | | 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 |
| | | | 0 | 1 | 7 | 7 | 3 | 2 | 7 | 1 |
| | | | | 0 | 1 | 1 | 1 | 3 | 2 | 7 |
P P P P P P P
@]

Συνολικά 7 λάθη σελίδας.

>><<

||! Λογική Διεύθυνση || || || || || || || ||! Φυσική Διεύθυνση ||
||! v || ||! p ||! d || ||! f ||! d || ||! a ||
|| 0 || => || 0 || 0 || => || 1 || 0 || => || 1024 ||
|| 3728 || => || 3 || 656 || => || - || 656 || => || page fault ||
|| 1023 || => || 0 || 1023 || => || 1 || 1023 || => || 2047 ||
|| 1024 || => || 1 || 0 || => || 0 || 0 || => || 0 ||
|| 1025 || => || 1 || 1 || => || 0 || 1 || => || 1 ||
|| 7800 || => || 7 || 632 || => || - || 632 || => || page fault ||
|| 4096 || => || 4 || 0 || => || - || 0 || => || page fault ||

!! Άσκηση

Ένα σύστημα χρησιμοποιεί ως εικονικές διευθύνσεις 2048 σελίδες μεγέθους 256 bytes η κάθε μία και αντιστοιχείται σε μια φυσική μνήμη 512 πλαισίων. Η μικρότερη μονάδα προσπέλασης είναι 1 byte.
* μια διεργασία Δ1 χρησιμοποιεί 1053 bytes. Πόσα πλαίσια σελίδων θα απαιτήσει από την MMU ( Memory Management Unit – μονάδα διαχείρισης μνήμης);
* μια άλλη διεργασία Δ2 απαιτεί 4000 bytes. Θεωρείστε ότι η Δ2 έχει ήδη αποκτήσει μέγεθος φυσικής μνήμης 2048 bytes, που αντιστοιχεί στις εικονικές διευθύνσεις από 0 έως 2047. Έστω ότι o επεξεργαστής χρειάζεται να προσπελάσει τη διεύθυνση: 10η σελίδα, offset 34, στο πρόγραμμα της διεργασίας Δ2. Μπορεί να υπάρξει σφάλμα σελίδας; Δικαιολογείστε την απάντησή σας.

* Έχουμε 1053 = 4*256 + 29 , συνεπώς η Δ1 απαιτεί 4 σελίδες (των 256 bytes η κάθε μια) + 29 bytes επί πλέον, άρα συνολικά 5 σελίδες. Οπότε θα διεκδικήσει από την MMU 5 πλαίσια για να χωρέσουν όλες οι σελίδες της. Στην 5η σελίδα μόνο τα 29 από τα 256 bytes θα χρησιμοποιηθούν. Τα υπόλοιπα 227 bytes μένουν άχρηστα (εσωτερικός κατακερματισμός).

* Η σελίδα p=10 σε συνδυασμό με το offset d=34 αντιστοιχούν στην εικονική διεύθυνση v = p*256 + 34 = 2594 > 2047. Άρα η συγκεκριμένη εικονική διεύθυνση βρίσκεται έξω από τα όρια των διευθύνσεων που βρίσκονται στην φυσική μνήμη και άρα θα υπάρξει page fault.

----

!! Άσκηση

Σε ένα σύστημα που χρησιμοποιεί απλή σελιδοποίηση μία σελίδα αποτελείται από 1024 bytes. Το σύστημα έχει 8 εικονικές σελίδες και 4 πλαίσια. Ο πίνακας σελίδων σε κάποια χρονική στιγμή είναι :

|| border=1 width=30%
||! Αριθμός Σελίδας ||! Αριθμός Πλαισίου ||
|| 0 || 1 ||
|| 1 || 0 ||
|| 2 || 3 ||
|| 3 || - ||
|| 4 || - ||
|| 5 || 2 ||
|| 6 || - ||
|| 7 || - ||

#%alpha% πόσα bits σχηματίζουν μια εικονική διεύθυνση;
# πόσα bits σχηματίζουν μια φυσική διεύθυνση;
# ποιες είναι οι φυσικές διευθύνσεις που αντιστοιχούν στις παρακάτω λογικές διευθύνσεις: 0, 3728, 1023, 1024, 1025, 7800, 4096;

>>answer<<

!! Απάντηση

#%alpha% Η εικονική διεύθυνση αποτελείται από δύο πεδία: p = "αριθμός της σελίδας" και d = "offset ". Αφού υπάρχουν 8 εικονικές σελίδες ο αριθμός της σελίδας, p, είναι μεταξύ 0 και 7 και συνεπώς αρκούν 3 bits για να τον περιγράψουμε. Αφού μια σελίδα περιέχει 1024 bytes το offset, d, είναι ένας αριθμός μεταξύ 0 και 1023 οπότε αρκούν 10 bits για να το περιγράψουμε. Συνολικό μήκος εικονικής διεύθυνσης = 3+10 = 13 bits

# Η φυσική διεύθυνση αποτελείται από δύο πεδία: f = "αριθμός πλαισίου" και d = "offset ". Αφού υπάρχουν 4 πλαίσια ο αριθμός πλαισίου, f, είναι μεταξύ 0 και 3 και συνεπώς αρκούν 2 bits για να τον περιγράψουμε. Το offset, d, όπως είπαμε και παραπάνω απαιτεί 10 bits. Συνολικό μήκος φυσικής διεύθυνσης = 2+10 = 12 bits

# Η μετάφραση μιας λογικής (εικονικής) διεύθυνσης v σε μια φυσική διεύθυνση a γίνεται ως εξής: βρίσκουμε την σελίδα p = (v div 1024), όπου x div y = το πηλίκο της ακέραιας διαίρεσης x/y, και το offset d = (v - 1024*p). Από τον πίνακα σελίδων βρίσκουμε το πλαίσιο f που αντιστοιχεί στην σελίδα p, και αφήνουμε το offset ίδιο. Αν η σελίδα αντιστοιχεί σε κάποιο πλαίσιο τότε η τελική φυσική διεύθυνση είναι a = (d + 1024*f). Αν η σελίδα δεν αντιστοιχεί σε κάποιο πλαίσιο τότε έχουμε page fault.

|| border=1
|| ! Λογική Διεύθυνση || || || || || || || || ! Φυσική Διεύθυνση ||
|| ! v || || ! p || ! d || || ! f || ! d || || ! a ||


>><<

----

!! Exercise

A computer whose processes have 1024 pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is 5 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (virtual page, physical page frame) pairs, and can do a look up in 1 nsec. What hit rate is needed to reduce the mean overhead to 2 nsec?

>>answer<<

!! Απάντηση

Ο τύπος που δίνει το μέσο χρόνο επίδοσης στη συσχετιστική μνήμη (TBL) δίνεται από τον τύπο:

(:eqn height=100px:) [=
t_mu=h/100*t_c+(1-h/100)*(t_c+t_p)
=]

->t'_μ_': Χρόνος μέσης επίδοσης
->t'_p_': Χρόνος προσπέλασης στον πίνακα σελίδων
->t'_c_': Χρόνος προσπέλασης στη συσχετιστική μνήμη (TBL)
->h: Ποσοστό επιτυχίας

Εδώ έχουμε: t'_p_'=5nsec, t'_c_'=1nsec, t'_μ_'=2nsec
Κάνουμε αντικατάσταση:

(:eqn height=100px:) [=
2=h/100*1+(1-h/100)*6 => 2=0.01h+6-0.06h => 0.05h=4 => h=80
=]

Άρα το ποσοστό επιτυχίας πρέπει να είναι 80%.

>><<

----

!! Exercise

If FIFO page replacement is used with four page frames and eight pages, how many page faults will occur with the reference string 0172327103 if the four frames are initially empty? Now repeat this problem for LRU.

>>answer<<

!! Απάντηση

|| border=1px width=50%

A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8 KB. How many entries are needed for the page table?

!! Answer

With 8-KB pages and a 48-bit virtual address space, the number of virtual pages is 2'^48^'/2'^13^', which is 2'^35^' (about 34 billion).

>><<

----

!! Exercise

A computer whose processes have 1024 pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is 5 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (virtual page, physical page frame) pairs, and can do a look up in 1 nsec. What hit rate is needed to reduce the mean overhead to 2 nsec?

>>answer<<

t_mu=h/100*t_c+(1-h/100)*(t_c+t_p)
=]

->t'_μ_': Χρόνος μέσης επίδοσης
->t'_p_': Χρόνος προσπέλασης στον πίνακα σελίδων
->t'_c_': Χρόνος προσπέλασης στη συσχετιστική μνήμη (TBL)
->h: Ποσοστό επιτυχίας

Εδώ έχουμε: t'_p_'=5nsec, t'_c_'=1nsec, t'_μ_'=2nsec
Κάνουμε αντικατάσταση:

(:eqn height=100px:) [=
2=h/100*1+(1-h/100)*6 => 2=0.01h+6-0.06h => 0.05h=4 => h=80
=]

Άρα το ποσοστό επιτυχίας πρέπει να είναι 80%.

>><<

----

To prevent a newly swapped-in page from being swapped out before it can be used. The danger is that the bit may never get turned off, and the frame could become unusable.

>><<

----

!! Question

What is the difference between a physical address and a virtual address?

>>answer<<

!! Answer

Real memory uses physical addresses. These are the numbers that the memory chips react to on the bus. Virtual addresses are the logical addresses that refer to a process’ address space. Thus a machine with a 16-bit word can generate virtual addresses up to 64K, regardless of whether the machine has more or less memory than 64 KB.

>><<

----

!! Exercise

For each of the following decimal virtual addresses, compute the virtual page number and offset for a 4-KB page and for an 8 KB page: 20000, 32768, 60000.

>>answer<<

!! Απάντηση

Για αναπαράσταση σελίδων των 4Κ χρειάζονται 12bit (2'^12^'=4096). Οι σελίδες που δίνονται δεν ξεπερνούν το νούμερο 65536 το οποίο ισούτε με 2'^16^'. Συμπεραίνουμε, λοιπόν, ότι οι διευθύνσεις έχουν 16bit εκ' των οποίων τα 4 χρησιμοποιούνται για τον αριθμό σελίδας και τα 12 για την μετατόπιση (offset). Με 4bit για τις σελίδες έχουμε συνολικά 2'^4^'=16 σελίδες.

Η εικονική διεύθυνση 20000 δίνει:
->αριθμός σελίδας = 20000 div 4096 = 4 (div το ακέραιο μέρος της διαίρεσης)
->μετατόπιση = 20000 - (αριθμός σελίδας)*4096 = 20000 - 4*4096 = 20000 - 16384 = 3616

Η εικονική διεύθυνση 32768 δίνει:
->αριθμός σελίδας = 32768 div 4096 = 8
->μετατόπιση = 32768 - (αριθμός σελίδας)*4096 = 32768 - 8*4096 = 32768 - 32768 = 0

Η εικονική διεύθυνση 60000 δίνει:
->αριθμός σελίδας = 60000 div 4096 = 14
->μετατόπιση = 60000 - (αριθμός σελίδας)*4096 = 60000 - 14*4096 = 60000 - 57344 = 2656

Για σελίδες των 8K χρειάζονται 13bit (2'^13^'=8192). Έτσι, για τις σελίδες έχουμε 3bit (16 - 13) και συνολικά 2'^3^'=8 σελίδες.

Η εικονική διεύθυνση 20000 δίνει:
->αριθμός σελίδας = 20000 div 8192 = 2
->μετατόπιση = 20000 - (αριθμός σελίδας)*8192 = 20000 - 2*8192 = 20000 - 16384 = 3616

Η εικονική διεύθυνση 32768 δίνει:
->αριθμός σελίδας = 32768 div 8192 = 4
->μετατόπιση = 32768 - (αριθμός σελίδας)*8192 = 32768 - 4*8192 = 32768 - 32768 = 0

Η εικονική διεύθυνση 60000 δίνει:
->αριθμός σελίδας = 60000 div 8192 = 7
->μετατόπιση = 60000 - (αριθμός σελίδας)*8192 = 60000 - 7*8192 = 60000 - 57344 = 2656

>><<

----

!! Exercise

If an instruction takes 10 nsec and a page fault takes an additional n nsec, give a formula for the effective instruction time if page faults occur every k instructions.

>>answer<<

!! Answer

A page fault every k instructions adds an extra overhead of n/k μsec to the average, so the average instruction takes 10 + n/k nsec.

>><<

----

!! Exercise

A machine has a 32-bit address space and an 8-KB page. The page table is entirely in hardware, with one 32-bit word per entry.  When a process starts, the page table is copied to the hardware from memory, at one word every 100 nsec. If each process runs for 100 msec (including the time to load the page table), what fraction of the CPU time is devoted to loading the page tables?

>>answer<<

!! Answer

The page table contains 2'^32^'/2'^13^' entries, which is 524,288. Loading the page table takes 52 msec. If a process gets 100 msec, this consists of 52 msec for loading the page table and 48 msec for running. Thus 52 percent of the time is spent loading page tables.

>><<

----

!! Exercise

A computer with a 32-bit address uses a two-level page table. Virtual addresses are split into a 9-bit top-level page table field, an 11-bit second-level page table field, and an offset. How large are the pages and how many are there in the address space?

>>answer<<

!! Answer

Twenty bits are used for the virtual page numbers, leaving 12 over for the offset. This yields a 2'^12^'=4-KB page. Twenty bits for the virtual page implies 2'^20^' pages.

>><<

----

!! Exercise

A computer has 32-bit virtual addresses and 4KB pages. The program and data together fit in the lowest page (0–4095) The stack fits in the highest page. How many entries are needed in the page table if traditional (one-level) paging is used? How many page table entries are needed for two-level paging, with 10 bits in each part?

>>answer<<

!! Answer

For a one-level page table, there are 2'^32^'/2'^12^' or 1M pages needed. Thus the page table must have 1M entries.

For two-level paging, the main page table has 2'^10^'=1K entries, each of which points to a second page table. Only two of
these are used. Thus in total only three page table entries are needed, one in the top-level table and one in each of the lower-level tables.

>><<

----

!! Exercise

A computer whose processes have 1024 pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is 5 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (virtual page, physical page frame) pairs, and can do a look up in 1 nsec. What hit rate is needed to reduce the mean overhead to 2 nsec?

>>answer<<

!! Απάντηση

Ο τύπος που δίνει το μέσο χρόνο επίδοσης στη συσχετιστική μνήμη (TBL) δίνεται από τον τύπο:

(:eqn height=100px:) [=
t_μ=h/100*t_c
=]

>><<

You’d expect that the page-fault rate would decrease as the number of frames increases; but Belady’s anomaly says this is not true in all algorithms.

----

!! Question

What is the ideal page-replacement scheme?

>>answer<<

!! Answer

OPTimal, or MINimum page-fault method. Replace the page that will not be used for the longest future time.

>><<

----

!! Question

What are the uses and disadvantages of the OPT method?

>>answer<<

!! Answer

It requires future knowledge of the reference string. It is used to compare with other methods.

>><<

----

!! Question

What is the LRU algorithm?

>>answer<<

!! Answer

Least recently used page is the victim of page replacement.

>><<

----

!! Question

List ways to implement LRU, to determine which page is victim.

>>answer<<

!! Answer

* Use hardware counter and/or clock. Page table contains time that is updated after each use. Page with oldest time is victim.
* Use stack of page numbers. On each use, page number is moved to top of stack, and rest are shifted down. Bottom number is the victim.
* Use a reference bit that is set after use, but cleared after time intervals. Victim is one with bit cleared.
* Use a reference byte. After given time interval, the byte in each page is shifted right, but page in use has sign-bit set. Victim is page with lowest-valued byte.

>><<

----

!! Question

Does LRU require extra hardware?

>>answer<<

!! Answer

Yes. Otherwise, system would spend more time selecting victims than in running programs.

>><<

----

!! Question

What is the second-chance replacement method?

>>answer<<

!! Answer

Pages are arranged in FIFO order, but have a reference bit. Oldest page is selected; if bit is clear, it is the victim. If bit is set, we clear it and look at next page.

>><<

----

!! Question

What is the LFU method?

>>answer<<

!! Answer

It keeps the number of references made to each page, and shifts the count right after regular intervals. Page with lowest count is victim.

>><<

----

!! Question

List two ways of distributing frames among processes.

>>answer<<

!! Answer

# Each process uses same number, “equal allocation.”
# Each process uses a number of frames proportional to the size of the process, “proportional allocation size.”

>><<

----

!! Question

What problems occur with the above ways of distributing frames?

>>answer<<

!! Answer

* You can’t allocate fractional parts of frames; each process uses the ceiling (number given).
* Total number of frames can’t be more than exist.
* May want to give some processes higher priority.

>><<

----

!! Question

How do global and local allocation differ?

>>answer<<

!! Answer

Local replacement: victim of replacement is in current process.
Global replacement: victim of replacement selected from any process.

>><<

----

!! Question

What is thrashing?

>>answer<<

!! Answer

State where the system spends an excessive amount of time on paging, compared to the execution of processes.

>><<

----

!! Question

What is meant by locality?

>>answer<<

!! Answer

A set of pages which are actively used together.

>><<

----

!! Question

What is a working set?

>>answer<<

!! Answer

The set of pages referenced in the most recent time period delta, called the working set window.

>><<

----

!! Question

What is the advantage of the working set model?

>>answer<<

!! Answer

It allows you to determine a near optimum size for each process, and to allocate frames to prevent thrashing, yet with high degree of multiprogramming.

>><<

----

!! Question

What is the page-fault frequency strategy?

>>answer<<

!! Answer

Lower and upper levels of page-fault rates are specified. If a process faults more often than upper, it is given more frames; if it faults less than lower, frames are removed from it.

>><<

----

!! Question

Why use prepaging?

>>answer<<

!! Answer

Each process needs a minimum number of pages to run initially. Bring them in immediately to reduce paging later.

>><<

----

!! Question

List factors determining the size of a page.

>>answer<<

!! Answer

* A large page size will allow the page table size to be small.
* To minimize internal fragmentation, the page size should be small.
* To minimize I/O times, page size should be large.
* The quantity of I/O is reduced for smaller pages, as locality is improved.
* To minimize the number of page faults, need large pages.

>><<

----

!! Question

Illustrate the statement: “system performance can be improved by an awareness of the underlying demand paging.”

>>answer<<

!! Answer

* If a two-dimensional array is stored by rows, it should be accessed by rows, to avoid excess paging.
* Stacks have good locality, hash tables produce poor locality.
* Writing programs in reentrant fashion will prevent pages from becoming “dirty.”
* Separating code and data allows each to be treated in a different locality and to be paged separately.

>><<

----

!! Question

List two ways to treat memory swaps while waiting for I/O.

>>answer<<

!! Answer

# Never execute I/O to user memory; thus allow the waiting process’ pages to be swapped out.
# Lock the pages waiting for I/O into memory using a lock bit.

>><<

----

!! Question

Describe another use of the lock bit. What danger is there here?

>>answer<<

!! Answer

To prevent a newly swapped-in page from being swapped out before it can be used. The danger is that the bit may never get turned off, and the frame could become unusable.

%define=answer block bgcolor=#c4d4e7 border='1px dashed #31659c' padding-left='10px' padding-right='10px'%

A simulation is probably the easiest way to allow the students to program several of the page replacement algorithms and see how they really work. If an interactive graphics display can be used to display the simulation as it works, the students may be better able to understand how paging works.

----

!! Question

What is virtual memory?

>>answer<<

!! Answer

A set of techniques and hardware allowing us to execute a program even when not entirely in memory.

>><<

----

!! Question

List cases where entire program need not be in memory, traditionally.

>>answer<<

!! Answer

Certain options of a program that are rarely used.
Many error-handling sections.
Large arrays, lists, and tables, where only a small portion is used.

>><<

----

!! Question

List benefits of having only part of a program in memory.

>>answer<<

!! Answer

* Simplifies the programming task.
* More user-programs can run concurrently in newly freed memory.
* Less swapping of entire programs, thus less I/O.

>><<

----

!! Question

What effect has virtual memory had on traditional program management?

>>answer<<

!! Answer

Overlay methods have disappeared.

>><<

----

!! Question

What is demand paging?

>>answer<<

!! Answer

Design where a page is never swapped into memory unless needed.

>><<

----

!! Question

List advantages of demand paging.

>>answer<<

!! Answer

Decreases swap time and the amount of free physical memory, allows higher degree of multiprogramming.

>><<

----

!! Question

Why is there a valid/invalid bit? Where is it kept?

>>answer<<

!! Answer

To indicate whether an address is invalid, or a page is swapped out. It is kept in the page-frame table.

>><<

----

!! Question

What is a page fault?

>>answer<<

!! Answer

An interrupt caused by program needing a specific page not yet in memory.

>><<

----

!! Question

List six steps to process a page fault.

>>answer<<

!! Answer


# Check page-frame table in PCB. If address invalid, abort program.
# If address valid, but its page not current, bring it in.
# Find free frame.
# Request I/O for the desired page.
# Update the page-frame table in PCB.
# Restart the instruction.

>><<

----

!! Question

Indicate states of instruction execution when a page fault occurs.

>>answer<<

!! Answer

* Page fault while fetching the instruction.
* Page fault while fetching the operands.
* Page fault while storing data to memory.

>><<

----

!! Question

List two ways to resolve problem of instruction or data straddling two pages.

>>answer<<

!! Answer

* Access both ends of both blocks involved to bring in all needed pages.
* Save values needed for instructions and operands in temporary registers.

>><<

----

!! Question

How do you compute the effective access time for a demand-page system?

>>answer<<

!! Answer

Let p = probability of a page fault, t = memory access time, f = page-fault time. Then effective time = (1 - p) × t + p × f.

>><<

----

!! Question

What factors determine the page-fault time?

>>answer<<

!! Answer

* Time to service interrupt.
* Time to swap page.
* Time to restart process.

>><<

----

!! Question

List ways of resolving problem of no free frames left.

>>answer<<

!! Answer

* Aborting user program (poor solution).
* Swap out an entire program, freeing its frames.
* Replacing particular existing frames.

>><<

----

!! Question

What is page replacement?

>>answer<<

!! Answer

Selecting a frame (preferably not in use) as a victim; swap it out; swap in the desired page into this frame; restarting program.

>><<

----

!! Question

How many swaps are needed for pure page replacement?

>>answer<<

!! Answer

Two: first one out, second one in.

>><<

----

!! Question

What does the modify (dirty) bit mean?

>>answer<<

!! Answer

If set, the page has been modified, and must be written back to backing store before being used as a victim.

>><<

----

!! Question

Ideally, what criteria should we use to replace pages?

>>answer<<

!! Answer

Choose the victims to achieve the lowest page-fault rate.

>><<

----

!! Question

We can judge page-replacement algorithms using what kind of data?

>>answer<<

!! Answer

Reference strings: list of memory address references made by programs.

>><<

----

!! Question

Describe FIFO as a page-replacement algorithm.

>>answer<<

!! Answer

“First-in-First-out;” oldest page is chosen as victim, as determined by its position in a queue. Easy to understand; performance not always good.

>><<

----

!! Question

What is Belady’s anomaly?

>>answer<<

!! Answer

You’d expect that the page-fault rate would decrease as the number of frames increases; but Belady’s anomaly says this is not true in all algorithms.

! Εικονική Μνήμη

Virtual memory can be a very interesting subject since it has so many different aspects: page faults, managing the backing store, page replacement, frame allocation, thrashing, page size. The objectives of this chapter are to explain these concepts and show how paging works.
A simulation is probably the easiest way to allow the students to program several of the page replacement algorithms and see how they really work. If an interactive graphics display can be used to display the simulation as it works, the students may be better able to understand how paging works.