Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική

Εισαγωγικά

Εισαγωγή στα Λ.Σ. Βασικές Δομές Η/Υ Βασικές Δομές Λ.Σ

Διεργασίες

Διεργασίες Χρονοπρογραμματισμός Συγχρονισμός

Αδιέξοδα

Μνήμη

Μονοπρογραμματισμός Εναλλαγή Εικονική Μνήμη Κατάτμηση

Είσοδος / Έξοδος

Σύστημα Αρχείων

Διεπαφή Υλοποίηση

 Ιστορικό Πρόσφατες αλλαγές Εκτύπωση Αναζήτηση

Ιστορικό: OS.VirtualMemory

Απόκρυψη μικρών αλλαγών - Αλλαγές κώδικα

15-08-2008 (18:53) από Άρης -
Αλλαγή σειρών 1036-1039 από:

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.

σε:

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

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

Ο διερμηνευτής δουλεύει ως εξής:

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

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

Αλλαγή σειρών 1113-1114 από:

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

σε:

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

Πρόσθεση σειράς 1130:

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

14-08-2008 (09:41) από Άρης -
Πρόσθεση σειρών 1036-1039:

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.

Αλλαγή σειρών 1062-1063 από:

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

σε:

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

12-08-2008 (15:41) από Άρης -
Αλλαγή σειρών 629-632 από:

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.

σε:

Άσκηση

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

Πρόσθεση σειρών 637-659:

Για τον χώρο των εικονικών διευθύνσεων χρησιμοποιούνται 32bit. Από αυτά τα 12bit είναι για το μέγεθος της σελίδας (4096=212). Τα υπόλοιπα 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.

Απάντηση

09-08-2008 (14:00) από Άρης -
07-08-2008 (19:31) από Άρης -
Αλλαγή σειρών 1040-1041 από:

C1=4, C2=3, C3=3, C4=3, C5=2, C6=1, C7=0, C8=0, C=8

σε:

C1=4, C2=3, C3=3, C4=3, C5=2, C6=1, C7=0, C8=0, C=8

Διαγραφή σειράς 1050:

[@

Αλλαγή σειρών 1059-1060 από:

@]

σε:
Πρόσθεση σειρών 1075-1092:

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

Απάντηση

C1=1, C2=8, C3=6, C4=6, C5=2, C6=1, C7=0, C8=0, C=8

F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C = 31
F2 = C3 + C4 + C5 + C6 + C7 + C8 + C = 23
F3 = C4 + C5 + C6 + C7 + C8 + C = 17
F4 = C5 + C6 + C7 + C8 + C = 11
F5 = C6 + C7 + C8 + C = 9
F6 = C7 + C8 + C = 8
F7 = C8 + C = 8
F8 = C = 8

07-08-2008 (19:25) από Άρης -
Αλλαγή σειράς 1051 από:
σε:

[@

Αλλαγή σειρών 1059-1060 από:

F8 = C = 8

σε:

F8 = C = 8 @]

07-08-2008 (19:22) από Άρης -
Αλλαγή σειρών 1052-1060 από:

F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C = 20 F2 = C3 + C4 + C5 + C6 + C7 + C8 + C = 17 F3 = C4 + C5 + C6 + C7 + C8 + C = 14 F4 = C5 + C6 + C7 + C8 + C = 11 F5 = C6 + C7 + C8 + C = 9 F6 = C7 + C8 + C = 8 F7 = C8 + C = 8 F8 = C = 8@@

σε:

F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C = 20
F2 = C3 + C4 + C5 + C6 + C7 + C8 + C = 17
F3 = C4 + C5 + C6 + C7 + C8 + C = 14
F4 = C5 + C6 + C7 + C8 + C = 11
F5 = C6 + C7 + C8 + C = 9
F6 = C7 + C8 + C = 8
F7 = C8 + C = 8
F8 = C = 8

07-08-2008 (19:21) από Άρης -
Αλλαγή σειράς 1039 από:

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

σε:

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

Αλλαγή σειράς 1052 από:

@@F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C = 20

σε:

F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C = 20

07-08-2008 (19:19) από Άρης -
Αλλαγή σειράς 1045 από:

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

σε:

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

Αλλαγή σειρών 1051-1052 από:

@@ F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C = 20

σε:

@@F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C = 20

Αλλαγή σειρών 1059-1061 από:

F8 = C = 8 @@

σε:

F8 = C = 8@@

07-08-2008 (19:16) από Άρης -
Αλλαγή σειρών 1040-1041 από:

C1=4, C2=3, C3=3, C4=3, C5=2, C6=1, C7=0

σε:
Πρόσθεση σειράς 1072:
Αλλαγή σειρών 1074-1075 από:
σε:
07-08-2008 (18:55) από Άρης -
Πρόσθεση σειράς 1006:
  1. Βρείτε το διάνυσμα C
Αλλαγή σειρών 1008-1009 από:
  1. Βρείτε το διάνυσμα C
σε:
Πρόσθεση σειρών 1013-1019:

Ο αλγόριθμος LRU μπορεί να εξομοιωθεί με την ακόλουθη λογική:

  1. Όταν γίνεται αναφορά σε μια σελίδα, αυτή μεταφέρεται στην πρώτη σελίδα
    1. Αν δεν υπήρχε στα πλαίσια της φυσική μνήμης ούτε στις σελίδες της εικονικής, τότε δημιουργείται λάθος σελίδας (Ρ) και στη στοιχειοσειρά αποστάσεων αναφέρεται ως άπειρο (∞)
    2. Αν δεν υπήρχε στα πλαίσια της φυσική μνήμης αλλά υπήρχε στις σελίδες της εικονικής, τότε δημιουργείται λάθος σελίδας (Ρ) και στη στοιχειοσειρά αποστάσεων αναφέρεται ο αριθμός σελίδας στον οποίο βρισκόταν
    3. Αν υπήρχε στα πλαίσια της φυσικής μνήμης, τότε δεν έχουμε λάθος σελίδας και στη στοιχειοσειρά αποστάσεων αναφέρεται ο αριθμός σελίδας στον οποίο βρισκόταν
  2. Οι σελίδες που βρίσκονταν κάτω από τη σελίδα στην οποία έγινε αναφορά, δεν μετακινούνται.
Αλλαγή σειρών 1024-1030 από:
                       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 |
σε:
                       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 |
Αλλαγή σειρών 1032-1033 από:

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

σε:

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

Αλλαγή σειρών 1035-1036 από:
σε:

Οι θέσεις 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 έχει το πλήθος των εμφανίσεων της κάθε θέσης μνήμης στην στοιχειοσειρά αποστάσων. Το C1 έχει τις εμφανίσεις τη Έτσι, από τη στοιχειοσειρά αποστάσεων έχουμε: C1=4, C2=3, C3=3, C4=3, C5=2, C6=1, C7=0

07-08-2008 (17:41) από Άρης -
Αλλαγή σειρών 1014-1018 από:
  Στοιχειοσειρά αναφορών:       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   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 |
Αλλαγή σειρών 1020-1026 από:
                          |   |   |   |   |   | 0 | 2 | 1 | 1 | 5 | | | | | | | | | | | | | | |
                          |   |   |   |   |   |   | 0 | 2 | 2 | 1 | | | | | | | | | | | | | | |
                          |   |   |   |   |   |   |   | 0 | 0 | 2 | | | | | | | | | | | | | | |
                          |   |   |   |   |   |   |   |   |   | 0 | | | | | | | | | | | | | | |
            Λάθη σελίδας:       P   P   P   P   P   P   P       P

Στοιχειοσειρά αποστάσεων: ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4 ∞

σε:
                       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

07-08-2008 (17:31) από Άρης -
Πρόσθεση σειρών 996-1030:

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

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.

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

Απάντηση

  Στοιχειοσειρά αναφορών:       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   ∞

Πρόσθεση σειρών 1033-1034:

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

07-08-2008 (14:18) από Άρης -
Αλλαγή σειρών 963-997 από:
σε:

Ερώτηση

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

ΣελίδαΧρόνος τελευταίας προσπέλασηςR bit
020841
120031
219801
312130
420141
520201
620321
716200

Απάντηση

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

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


Ερώτηση

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

07-08-2008 (13:37) από Άρης -
Αλλαγή σειράς 764 από:
σε:
Αλλαγή σειρών 804-807 από:

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?

σε:

Άσκηση

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

Πρόσθεση σειρών 812-837:

Για σελίδες των 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?

Απάντηση

Διαγραφή σειράς 951:
  1. LRU
07-08-2008 (13:23) από Άρης -
Αλλαγή σειρών 884-885 από:
  1. Ξεκινάμε τους μετρητές από την αρχική κατάσταση (00000000) και για κάθε 4δα R bits, βάζουμε τα bit στους αντίστοιχους μετρητές
σε:

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

Αλλαγή σειράς 888 από:
0000000000000000010000000110000001100000001100000101100001101100001101100
σε:
0000000000000000010000000110000001110000001110000101110001101110001101110
Αλλαγή σειρών 893-894 από:
  1. Μπορούμε να βάλουμε τα R bits το ένα κάτω από το άλλο με αντίστροφη σειρά (από το τελευταίο προς το πρώτο). Τα bits της πρώτης στήλης αντιστοιχούν στη σελίδα 0, της δεύτερης στην 1 κ.ο.κ.
σε:

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

Πρόσθεση σειρών 908-938:

Ερώτηση

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

ΣελίδαΦόρτωσηΠροσπέλασηRM
012628010
123026501
214027000
311028511

Ποια σελίδα θα αντικατασταθεί σύμφωνα με τους αλγόριθμους:

  1. NRU
  2. LRU
  3. FIFO
  4. LRU
  5. Δεύτερης ευκαιρίας

Απάντηση

  1. NRU: Αντικαθιστά σελίδα από την κατηγορία 0 (R=0, M=0), άρα τη σελίδα 2
  2. FIFO: Με βάση την φόρτωση θα αφαιρέσει εκείνη με το μικρότερο χρόνο, δηλαδή, τη σελίδα 3
  3. LRU: Με βάση την τελευταία προσπέλαση θα αφαιρέσει εκείνη με το μικρότερο χρόνο, δηλαδή, τη σελίδα 1
  4. Δεύτερης ευκαιρίας: Με βάση την φόρτωση, υποψήφια είναι η σελίδα 3. Έχει, όμως, R=1, οπότε γίνεται R=0 και βρίσκει την αμέσως επόμενη που είναι η 0. Και αυτή έχει R=1, το οποίο γίνεται 0 και βρίσκει την επόμενη η οποία είναι η 2. Αυτή έχει R=0 οπότε και αφαιρείται.
07-08-2008 (12:53) από Άρης -
Πρόσθεση σειρών 882-885:

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

  1. Ξεκινάμε τους μετρητές από την αρχική κατάσταση (00000000) και για κάθε 4δα R bits, βάζουμε τα bit στους αντίστοιχους μετρητές
Αλλαγή σειρών 888-893 από:
0000000000000000010000000110000001100000001100000101100001101100001101100
1000000001000000001000000001000001001000001001000001001001001001001001001
2000000001000000011000000111000000111000010111000110111000110111000110111
3000000001000000011000000011000001011000001011000001011000001011010001011
σε:
0000000000000000010000000110000001100000001100000101100001101100001101100
1000000001000000001000000001000001001000001001000001001001001001001001001
2000000001000000011000000111000000111000010111000110111000110111000110111
3000000001000000011000000011000001011000001011000001011000001011010001011
  1. Μπορούμε να βάλουμε τα R bits το ένα κάτω από το άλλο με αντίστροφη σειρά (από το τελευταίο προς το πρώτο). Τα bits της πρώτης στήλης αντιστοιχούν στη σελίδα 0, της δεύτερης στην 1 κ.ο.κ.
 Μετρητές
Σελίδα0123
R bits0001
 1100
 1010
 0010
 1101
 1010
 1011
 0111
06-08-2008 (19:17) από Άρης -
Διαγραφή σειρών 858-859:
  • FIFO
06-08-2008 (19:15) από Άρης -
06-08-2008 (19:14) από Άρης -
Διαγραφή σειράς 883:

Αρχική κατάσταση:

Αλλαγή σειρών 885-890 από:
ΣελίδαΑρχική κατάστασηR bits: 0111R bits: 1011
0000000000000000010000000
1000000001000000001000000
2000000001000000011000000
3000000001000000011000000
σε:
ΣελίδαΑρχική κατάστασηR bits: 0111R bits: 1011R bits: 1010R bits: 1101R bits: 0010R bits: 1010R bits: 1100R bits: 0001
0000000000000000010000000110000001100000001100000101100001101100001101100
1000000001000000001000000001000001001000001001000001001001001001001001001
2000000001000000011000000111000000111000010111000110111000110111000110111
3000000001000000011000000011000001011000001011000001011000001011010001011
06-08-2008 (19:08) από Άρης -
Πρόσθεση σειρών 872-891:

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.

Απάντηση

Αρχική κατάσταση:

ΣελίδαΑρχική κατάστασηR bits: 0111R bits: 1011
0000000000000000010000000
1000000001000000001000000
2000000001000000011000000
3000000001000000011000000
06-08-2008 (18:57) από Άρης -
Αλλαγή σειρών 844-872 από:
σε:
  • 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 λάθη σελίδας.

06-08-2008 (18:45) από Άρης -
Αλλαγή σειρών 790-793 από:
! Λογική Διεύθυνση       ! Φυσική Διεύθυνση
! v ! p! d ! f! d ! a
σε:
Λογική Διεύθυνση       Φυσική Διεύθυνση
v pd fd a
0=>00=>10=>1024
3728=>3656=>-656=>page fault
1023=>01023=>11023=>2047
1024=>10=>00=>0
1025=>11=>01=>1
7800=>7632=>-632=>page fault
4096=>40=>-0=>page fault
06-08-2008 (18:38) από Άρης -
Αλλαγή σειρών 742-745 από:

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?

σε:

Άσκηση

Ένα σύστημα χρησιμοποιεί ως εικονικές διευθύνσεις 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. Μπορεί να υπάρξει σφάλμα σελίδας; Δικαιολογείστε την απάντησή σας.
Αλλαγή σειρών 752-771 από:
σε:
  • Έχουμε 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.
Αλλαγή σειρών 758-838 από:

σε:
06-08-2008 (18:24) από Άρης -
Αλλαγή σειρών 730-731 από:

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?

σε:

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?

Πρόσθεση σειρών 734-747:

Answer

With 8-KB pages and a 48-bit virtual address space, the number of virtual pages is 248/213, which is 235 (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?

06-08-2008 (18:19) από Άρης -
Αλλαγή σειρών 739-740 από:

t_μ=h/100*t_c =]

σε:
06-08-2008 (18:06) από Άρης -
Αλλαγή σειρών 609-740 από:

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.

σε:
06-08-2008 (13:39) από 194.63.239.168 -
Πρόσθεση σειρών 316-317:
06-08-2008 (13:37) από 194.63.239.168 -
Αλλαγή σειρών 314-607 από:

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.

σε:

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

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

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


Question

What is the LRU algorithm?

Answer

Least recently used page is the victim of page replacement.


Question

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

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

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


Question

What is the second-chance replacement method?

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

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

  1. Each process uses same number, “equal allocation.”
  2. 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

  • 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

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


Question

What is thrashing?

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

A set of pages which are actively used together.


Question

What is a working set?

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

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

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

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

  • 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

  • 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

  1. Never execute I/O to user memory; thus allow the waiting process’ pages to be swapped out.
  2. 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

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.

06-08-2008 (13:26) από 194.63.237.23 -
Πρόσθεση σειράς 1:
Αλλαγή σειρών 5-314 από:

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.

σε:

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

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

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

  • 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

Overlay methods have disappeared.


Question

What is demand paging?

Answer

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


Question

List advantages of demand paging.

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

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

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


Question

List six steps to process a page fault.

Answer

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

Question

Indicate states of instruction execution when a page fault occurs.

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

  • 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

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

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

Question

List ways of resolving problem of no free frames left.

Answer

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

Question

What is page replacement?

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

Two: first one out, second one in.


Question

What does the modify (dirty) bit mean?

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

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


Question

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

Answer

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


Question

Describe FIFO as a page-replacement algorithm.

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

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.

22-07-2008 (19:13) από Άρης -
Πρόσθεση σειρών 1-4:

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

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.

Τελευταία ενημέρωση: 15-08-2008 (18:53)

Copyright 2008 - Άρης Φεργάδης