Mamalis Hypertext Links

1

1. Παράδειγμα 1 Θεωρείστε ένα σύστημα διαχείρισης μνήμης Μεταβλητών Διαιρέσεων (χωρίς συμπίεση) με συνολική φυσική μνήμη 1024Κ. Εστω επίσης ότι σε κάποια χρονική στιγμή (αφού π.χ. έχει εισέλθει, εκελεσθεί, εξέλθη κ.λ.π., ένας μεγάλος αριθμός διεργασιών) η φυσική μνήμη εμφανίζει την ακόλουθη εικόνα (οι δειργασίες Δ1 και Δ2 παραμένουν στο σύστημα για εκτέλεση και υπάρχουν επίσης και 3 τμήματα κενά όπως φαίνονται στο σχήμα): 0

Free = 60Κ Δ1 = 120 Κ Free = 54Κ Δ2 = 670 Κ Free = 120Κ

1024Κ-1 Ερώτηση: Εστω ότι στην ουρά διεργασιών έχει καταφτάσει μία διεργασία Δ3 προς εκτέλεση η οποία απαιτεί μνήμη 150Κ. Μπορεί να εκτελεστεί άμεσα ; Απάντηση: Δεν μπορεί να εκτελεστεί άμεσα γιατί δεν υπάρχει συνεχόμενος ελεύθερος χώρος στη μνήμη για να της εκχωρηθεί (υπάρχουν ελέυθερα μεν 120Κ+54Κ+60Κ= 234Κ – πολύ περισσότερα από τα 150Κ που απαιτεί η Δ3 αλλά επειδή δεν είναι σε συνεχόμενο χώρο δεν μπορούν να εκχωρηθούν στην Δ3 – έτσι η Δ3 θα πρέπει να περιμένει μέχρι να ολοκηρώσει την εκτέλεσή της κάποια από τις Δ1,Δ2). Αντίθετα αν είχαμε σύστημα Σελιδοποίησης με 16 πλαίσια/σελίδες των 64Κ το κάθε ένα τότε δεν θα υπήρχε πρόβλημα και η Δ3 θα μπορούσε να εκτελεστεί κανονικά: - Η Δ1 θα απαιτούσε και θα καταλάμβανε 2 σελίδες/πλαίσια (=128Κ) - Η Δ2 θα απαιτούσε και θα καταλάμβανε 11 σελίδες/πλαίσια (=704Κ) Αρα θα έμεναν διαθέσιμες 3 σελίδες (συνολικά 192 bytes) οι οποίες θα μπορούσαν να εκχωρηθούν άμεσα στην Δ3.

2

1. Παράδειγμα 2 Θεωρείστε ένα σύστημα διαχείρισης μνήμης Μεταβλητών Διαιρέσεων (χωρίς συμπίεση) με συνολική φυσική μνήμη 1024Κ. Εστω επίσης ότι σε κάποια χρονική στιγμή (αφού π.χ. έχει εισέλθει, εκελεσθεί, εξέλθη κ.λ.π., ένας μεγάλος αριθμός διεργασιών) η φυσική μνήμη εμφανίζει την ακόλουθη εικόνα (οι δειργασίες Δ1 και Δ2 παραμένουν στο σύστημα για εκτέλεση και υπάρχουν επίσης και 3 τμήματα κενά όπως φαίνονται στο σχήμα): 0

Free = 60Κ Δ1 = 120 Κ Free = 54Κ Δ2 = 670 Κ Free = 120Κ

1024Κ-1 Ερώτηση 1: Εστω ότι στην ουρά διεργασιών έχει καταφτάσει μία διεργασία Δ3 προς εκτέλεση η οποία απαιτεί μνήμη 1250Κ. Μπορεί να εκτελεστεί άμεσα ; Απάντηση: Δεν μπορεί να εκτελεστεί ούτε άμεσα ούτε γενικότερα γιατί ο χώρος που απαιτει είναι μεγαλύτερος του συνολικού χώρου φυσικής μνήμης του συστήματος. Αντίθετα αν είχαμε σύστημα Σελιδοποίησης με 16 πλαίσια/σελίδες των 64Κ το κάθε ένα και με υποστήριξη ‘εικονικής μνήμης’ (βλ. κεφάλαιο 5 του βιβλίου), θα απαιτούσε μεν πάλι μεγαλύτερο χώρο από τη φυσική μνήμη του συστήματος (20 σελίδες), ωστόσο θα μπορούσε να αρχίσει η εκτέλεσή της με την εκχώρηση σε αυτήν 3 αρχικά μόνο σελίδων (αυτές που θα ήταν αρχικά ελεύθερες – καθώς οι Δ1,Δ2 θεωρούμε ότι καταλαμβάνουν τις υπόλοιπες 13 σελίδες) κ.ο.κ. Ερώτηση 2: Εστω ότι στην ουρά διεργασιών έχουν καταφτάσει δύο διεργασίες Δ3 και Δ4 προς εκτέλεση οι οποίες απαιτούν μνήμη 120Κ και 120Κ αντίστοιχα. Μπορούν να εκτελεστούν και οι δύο άμεσα ; Απάντηση: Η πρώτη διεργασία των 120Κ (Δ3) μπορεί μεν να εκτελεστεί άμεσα (αφού μπορεί να της εκχωρηθεί άμεσα το τελευταίο ‘free’ κομμάτι των 120Κ, η δεύτερη ωστόσο διεργασία (Δ4) δεν μπορεί να εκτελεστεί καθώς απαιτεί συνολικά 120K ενώ πλέον θα υπάρχουν ελεύθερα μόνο 114Κ. Επειδή επίσης ούτε γενικότερα γιατί ο χώρος που απαιτει είναι μεγαλύτερος του συνολικού χώρου φυσικής μνήμης του συστήματος. Ούτως ή άλλως (εξετάζοντάς τις από την αρχή) και οι δύο μαζί απαιτούν 240Κ ενώ υπάρχει ελεύθερος χώρος στη μνήμη (διασκορπισμένος) μόνο 234Κ. Αντίθετα αν είχαμε σύστημα Σελιδοποίησης με 16 πλαίσια/σελίδες των 64Κ το κάθε ένα και με υποστήριξη ‘εικονικής μνήμης’ (βλ. κεφάλαιο 5 του βιβλίου), θα απαιτούσαν μεν και οι δύο μαζί πάλι χώρο μεγαλύτερο από τον ελεύθερο χώρο της φυσικής μνήμης (4 σελίδες ενώ ο ελεύθερος χώρος είναι 3 σελίδες - καθώς οι Δ1,Δ2 θεωρούμε ότι καταλαμβάνουν τις υπόλοιπες 13 σελίδες), ωστόσο θα μπορούσαν να εκχωρηθούν 2 σελίδες στη μία (Δ3) και 1 σελίδα στην άλλη (Δ4) και να αρχίσει έτσι η εκτέλεσή και των δύο κ.ο.κ.

3

3. Ασκηση 1 Εστω ένα σύνολο τεσσάρων διεργασιών οι οποίες αφίκνυνται σε ένα υπολογιστικό σύστημα με συνολικό χώρο μνήμης (για διεργασίες χρηστών) 512Κ. Στον ακόλουθο πίνακα φαίνονται οι στιγμές άφιξης των τεσσάρων διεργασιών, η διάρκειά τους (απαιτούμενος χρόνος εκτέλεσης της κάθε μίας στη CPU) και ο χώρος μνήμης που απαιτεί η κάθε μία για την εκτέλεσή της. Θεωρείστε επίσης ότι για τη χρονοδρομολόγηση των διεργασιών (που βρίσκονται κάθε χρονική στιγμή μαζί στην κύρια μνήμη του συστήματος) ακολουθείται αλγόριθμος Round-Robin με κβάντο χρόνου ‘1’. Διεργασίες P1 P2 P3 P4

Στιγμή Άφιξης 0 1 2 2

Διάρκεια 2 3 2 4

Μνήμη 120Κ 340Κ 360Κ 160Κ

Ερώτημα Α: Θεωρείστε ότι έχουμε ένα σύστημα σελιδοποιημένης μνήμης με μέγεθος πλαισίου/σελίδας 32Κ. Αναπαραστείστε σε έναν πίνακα (π.χ. της μορφής που δίνεται ενδεικτικά παρακάτω) την εικόνα της CPU και της μνήμης του συστήματος κάθε χρονική στιγμή (ποιες διεργασίες βρίσκονται στην ‘ουρά της CPU’ και ποια εκτελείται σε αυτήν κάθε χρονική στιγμή, ποια τμήματα μνήμης έχουν εκχωρηθεί σε κάθε διεργασία και ποια είναι ελεύθερα/‘εικόνα μνήμης’, ποιες διεργασίες περιμένουν για εκχώρηση μνήμης/ ‘ουρά μνήμης’ κ.λ.π.). Χρονική Στιγμή 0 1 2

Αφιξη

Εικόνα Μνήμης

CPU

Ουρά Μνήμης

P1 ...... ......

<Οπή 512Κ> ..................................... ....................................

... ...

P1 ...... ......

Ουρά CPU ... ....

Τέλος -

Ερώτημα Β: Στη συνέχεια με βάση τον παραπάνω πίνακα, υπολογίστε το μέσο χρόνο διεκπεραίωσης και τον μέσο χρόνο αναμονής των 4 διεργασιών . Απάντηση Ερωτήματος Α: Θεωρώντας σύστημα σελιδοποιημένης μνήμης 512Κ με μέγεθος πλαισίου/σελίδας 32Κ, σημαίνει ότι θα έχουμε συνολικά 16 πλαίσια σελίδων (32Kx16=512K) τα οποία θα μπορούν να κατανεμηθούν καθ’ οιονδήποτε τρόπο (και όχι μόνο ακολουθιακά) στις εισερχόμενες διεργασίες. Αν συμβολίσουμε τα 16 αυτά πλαίσια ως Σ1........Σ16, θα έχουμε τελικά τον ακόλουθο πίνακα (εικόνες CPU, μνήμης κ.λ.π.): [H P1 (120Κ) απαιτεί συνολικά 4 πλαίσια = 128Κ / H P2 (340Κ) απαιτεί συνολικά 11 πλαίσια = 352Κ H P3 (360Κ) απαιτεί συνολικά 12 πλαίσια = 384Κ / H P4 (160Κ) απαιτεί συνολικά 5 πλαίσια = 160Κ ] [πρώτα μπαίνει η P1 και καταλαμβάνει 4 πλαίσια, μετά η P2 και καταλαμβάνει άλλα 11 πλαίσια, στη συνέχεια φεύγει η P1 και μπαίνει στη θέση της η P4 καταλαμβάνοντας συνολικά 5 πλαίσια (η P3 δεν χωράει να μπει), στη συνέχεια φεύγει η P2 αλλά η P3 πάλι δεν χωράει να μπει (γιατί θέλει 12 πλαίσια ενώ έχουμε διαθέσιμα 11 πλαίσια), τελικά φεύγει και η P4 και τότε μπαίνει η P3 η οποία εκτελείται μόνη της μέχρι το τελος] Χρον. Στιγμή

Εικόνα Μνήμης

CPU

0

<Οπή 512Κ – Σ1ωςΣ16>

1

< P1-Σ1έωςΣ4>, <οπή-Σ5ωςΣ16>

Ρ1

P2

2

, <Ρ2-Σ5έωςΣ15>, <οπή-Σ16>

Ρ1

P3, P4

P2

3

, <Ρ2-Σ5έωςΣ15>, <Ρ4-Σ16>

P2

P3

P4

4

, <Ρ2-Σ5έωςΣ15>, <Ρ4-Σ16>

Ρ4

P3

P2

-

Ουρά Μνήμης

Ουρά CPU

P1

-

Τέλος

P1

4

5

, <Ρ2-Σ5έωςΣ15>, <Ρ4-Σ16>

Ρ2

P3

P4

6

, <Ρ2-Σ5έωςΣ15>, <Ρ4-Σ16>

Ρ4

P3

P2

7

, <Ρ2-Σ5έωςΣ15>, <Ρ4-Σ16>

Ρ2

P3

P4

8

, <οπή-Σ5έωςΣ15>, <Ρ4-Σ16>

Ρ4

P3

-

9

, <οπή-Σ5έωςΣ15>, <Ρ4-Σ16>

Ρ4

P3

-

10

, <οπή-Σ13έωςΣ16>

Ρ3

-

-

11

, <οπή-Σ13έωςΣ16>

Ρ3

-

-

<Οπή 512Κ – Σ1ωςΣ16>

Απάντηση Ερωτήματος Β: Χρόνος Διεκπεραίωσης

Χρόνος Αναμονής

(στιγμή ολοκλήρωσης – στιγμή άφιξης)

(χρόνος διεκπεραίωσης – διάρκεια)

P1

2-0 = 2

2-2 = 0

P2

7-1 = 6

6-3 = 3

P3

11-2 = 9

9-2 = 7

P4

9-2 = 7

7-4 = 3

Μέσοι Χρόνοι

24/4 = 6

13/4 = 3,25

P2

P4

P3

5

4. Ασκηση 2 Εστω ένα σύνολο έξι διεργασιών οι οποίες αφίκνυνται σε ένα υπολογιστικό σύστημα με συνολικό χώρο μνήμης (για διεργασίες χρηστών) 1024Κ. Στον ακόλουθο πίνακα φαίνονται οι στιγμές άφιξης των έξι διεργασιών, η διάρκειά τους (απαιτούμενος χρόνος εκτέλεσης της κάθε μίας στη CPU) και ο χώρος μνήμης που απαιτεί η κάθε μία για την εκτέλεσή της. Θεωρείστε επίσης ότι για τη χρονοδρομολόγηση των διεργασιών (που βρίσκονται κάθε χρονική στιγμή μαζί στην κύρια μνήμη του συστήματος) ακολουθείται αλγόριθμος Round-Robin με κβάντο χρόνου ‘1’. Διεργασίες P1 P2 P3 P4 P5 P6

Στιγμή Αφιξης 0 0 1 1 2 2

Διάρκεια 2 10 1 10 1 1

Μνήμη 120Κ 190Κ 125Κ 440Κ 160Κ 170Κ

(α) Αναπαραστείστε σε έναν πίνακα (π.χ. της μορφής που δίνεται ενδεικτικά παρακάτω) την εικόνα της CPU και της μνήμης του συστήματος κάθε χρονική στιγμή (ποιες διεργασίες βρίσκονται στην ‘ουρά της CPU’ και ποια εκτελείται σε αυτήν κάθε χρονική στιγμή, ποια τμήματα μνήμης έχουν εκχωρηθεί σε κάθε διεργασία και ποια είναι ελεύθερα/‘εικόνα μνήμης’, ποιες διεργασίες περιμένουν για εκχώρηση μνήμης/‘ουρά μνήμης’ κ.λ.π.), θεωρώντας ότι έχουμε: (α1) ένα σύστημα μνήμης μεταβλητών διαιρέσεων χωρίς συμπίεση (α2) ένα σύστημα σελιδοποιημένης μνήμης με μέγεθος πλαισίου/σελίδας 64Κ Χρονική Στιγμή 0 1 2

Αφιξη

Εικόνα Μνήμης

CPU

Ουρά Μνήμης

P1,P2 ...... ......

<Οπή 1024Κ> ..................................... ....................................

... ...

P1,P2, ...... ......

Ουρά CPU ... ....

Τέλος -

(β) Στη συνέχεια με βάση τους παραπάνω πίνακες, υπολογίστε για κάθε μία από τις παραπάνω περιπτώσεις (α1,α2): (β1) το μέσο χρόνο διεκπεραίωσης και μέσο χρόνο αναμονής των έξι διεργασιών (β2) το βαθμό πολυπρογραμματισμού (πόσες διεργασίες βρίσκονται ταυτόχρονα στη μνήμη κάθε χρονική στιγμή) που επιτυγχάνεται (κατασκευάστε μία καμπύλη που να αναπαριστά τον βαθμό πολυπρογραμματισμού ανά χρονική στιγμή για κάθε περίπτωση). (γ) Εξηγείστε-αναλύστε σύντομα τις διαφορές που διαπιστώσατε στους παραπάνω υπολογισμούς (β1,β2) για κάθε περίπτωση (α1,α2). Εξηγείστε επίσης σύντομα πώς θα διαμορφώνονταν οι παραπάνω διαφορές αν η ‘διάρκεια’ (χρόνος εκτέλεσης) των διεργασιών P5 και P6 ήταν 10 χρονικές μονάδες. Σημείωση: Συμβουλευτείτε αντίστοιχα θέματα της Προαιρετικής Εργασίας και των Επαναληπτικών Εξετάσεων του έτους 2001-02 (προσέξτε ωστόσο ότι εδώ ζητείται να αντιμετωπίσετε το θέμα και με χρήση σελιδοποιημένης μνήμης – όχι μόνο με μεταβλητές διαιρέσεις). Απάντηση Ερωτήματος Α: (α1) Μεταβλητές Διαιρέσεις Χρονική Στιγμή

Εικόνα Μνήμης

0

<Οπή 1024Κ>

1

< P1-120>, <Ρ2-190>, <οπή-714>

2

CPU

Ουρά Μνήμης

Ουρά CPU

P1,P2,

-

Ρ1

P3, P4

P2

< P1-120>, <Ρ2-190>, <Ρ3-125>,,<οπή-149>

Ρ2

P5, P6

P1,P3,P4

3

< P1-120>, <Ρ2-190>, <Ρ3-125>,,<οπή-149>

P1

P5, P6

P3,P4,P2

P1

4

< οπή-120>, <Ρ2-190>, <Ρ3-125>,,<οπή-149>

Ρ3

P5, P6

P4,P2

P3

-

Τέλος

6

5

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

6

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

7

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

8

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

9

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

10

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

11

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

12

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

13

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

14

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

15

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

16

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

17

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

18

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

19

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

20

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

21

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ4

P5, P6

P2

22

< οπή-120>, <Ρ2-190>, <οπή-125>,,<οπή-149>

Ρ2

P5, P6

P4

P2

23

< P5-160>,,<οπή-105>,,<οπή-149>

Ρ4

-

P5, P6

P4

24

< P5-160>,,<οπή-694>

P5

-

P6

P5

25

< οπή-160>,,<οπή-694>

P6

-

-

P6

< οπή-1024Κ>

(α2) Σελιδοποιημένη Μνήμη Θεωρώντας σύστημα σελιδοποιημένης μνήμης με μέγεθος πλαισίου/σελίδας 64Κ, σημαίνει ότι θα έχουμε συνολικά 16 πλαίσια σελίδων (64Kx16=1024K) τα οποία θα μπορούν να κατανεημηθούν καθ’ οιονδήποτε τρόπο (και όχι μόνο ακολουθιακά) στις εισερχόμενες διεργασίες. Αν συμβολίσουμε τα 16 αυτά πλαίσια ως Σ1........Σ16 ο παραπάνω πίνακας (εικόνες CPU, μνήμης κ.λ.π.) γίνονται πλέον όπως περιγράφεται παρακάτω (αυτό που κερδίζουμε είναι ότι αν π.χ. υπάρχουν σε κάποια χρονική στιγμή 3 ελεύθερα πλαίσια έστω και διεσπαρμένα – και όχι συνεχόμενα – σε διάφορα σημεία της φυσικής μνήμης) αυτά μπορούν να εκχωρηθούν κανονικά σε οποιαδήποτε διεργασία μεγέθους έως 3x64=192Κ με η βοήθεια ενός αντίστοιχου πίνακα σελίδων // ενώ στην περίπτωση των μεταβλητών διαιρέσεων χωρίς συμπίεση αυτό θα μπορούσε να γίνει μόνο για ακολουθαικά-συνεχόμενα κομμάτια της φυσικής μνήμης): Χρον. Στιγμή

Εικόνα Μνήμης

0

<Οπή 1024Κ – Σ1ωςΣ16>

1

< P1-Σ1Σ2>, <Ρ2-Σ3Σ4Σ5>, <οπή-Σ6ωςΣ16>

2

CPU

Ουρά Μνήμης

Ουρά CPU

P1,P2,

-

Ρ1

P3, P4

P2

,<Ρ2-Σ3Σ4Σ5>,<Ρ3-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

P5, P6

P1,P3,P4

3

,<Ρ2-Σ3Σ4Σ5>,<Ρ3-Σ6Σ7>,,<οπή-Σ15Σ16>

P1

P5, P6

P3,P4,P2

P1

4

,<Ρ2-Σ3Σ4Σ5>,<Ρ3-Σ6Σ7>,,,<οπή-Σ16>

Ρ3

P6

P4,P2,P5

P3

5

,<Ρ2-Σ3Σ4Σ5>,<Ρ6-Σ6Σ7>,,,

Ρ4

-

P2,P5,P6

6

,<Ρ2-Σ3Σ4Σ5>,<Ρ6-Σ6Σ7>,,,

Ρ2

-

P5,P6,P4

7

,<Ρ2-Σ3Σ4Σ5>,<Ρ6-Σ6Σ7>,,,

Ρ5

-

P6,P4,P2

-

Τέλος

P5

7

8

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<Ρ6-Σ6Σ7>,,<οπή-Σ15>,

Ρ6

-

P4,P2

9

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

10

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

-

P4

11

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

12

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

-

P4

13

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

14

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

-

P4

15

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

16

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

-

P4

17

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

18

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

-

P4

19

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

20

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

-

P4

21

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

22

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ2

-

P4

23

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

Ρ4

-

P2

24

<οπή-Σ1Σ2>,<Ρ2-Σ3Σ4Σ5>,<οπή-Σ6Σ7>,,<οπή-Σ15Σ16>

P2

-

P4

P2

25

<οπή-Σ1ωςΣ7>,,<οπή-Σ15Σ16>

P4

-

-

P4

< οπή-1024Κ – Σ1-Σ16>

Απάντηση Ερωτήματος Β: (β1) Μέσοι Χρόνοι Διεκπεραίωσης και Αναμονής Με βάση τους παραπάνω πίνακες (και ειδικότερα την τελευταία στήλη τους στην οποία φαίνεται ποια στιγμή εξέρχεται/τελειώνει κάθε διεργασία), οι χρόνοι διεκπεραίωσης και αναμονής αναπαρίστανται στον ακόλουθο πίνακα:

Μεταβλητές Διαιρέσεις

Σελιδοποίηση

Χρ. Διεκπερ.

Χρ. Αναμονής

Χρ. Διεκπερ.

Χρ. Αναμονής

(στιγμή ολοκλήρωσης – στιγμή άφιξης)

(χρόνος διεκπεραίωσης – διάρκεια)

(στιγμή ολοκλήρωσης – στιγμή άφιξης)

(χρόνος διεκπεραίωσης – διάρκεια)

P1

3-0 = 3

3-2 = 1

3-0 = 3

3-2 = 1

P2

22-0 = 22

22-10 = 12

24-0 = 24

24-10 = 14

P3

4-1 = 3

3-1 = 2

4-1 = 3

3-1 = 2

P4

23-1 = 22

22-10 = 12

25-1 = 24

24-10 = 14

P5

24-2 = 22

22-1 = 21

7-2 = 5

5-1 = 4

P6

25-2 = 23

23-1 = 22

8-2 = 6

6-1 = 5

95/6 = 15,83

70/6 = 11,66

65/6 = 10,83

40/6 = 6,66

Μέσοι Χρόνοι

(β2) Βαθμός Πολυπρογραμματισμού (multiprogramming degree) Με βάση τους παραπάνω πίνακες ο βαθμός πολυπρογραμματισμού σε κάθε περίπτωση μπορεί να αναπαρασταθεί ως ακολούθως: (i) Μεταβλητές Διαιρέσεις

P6

8

5 4 3 2 1 1

2

3

4

5

6

7

8

9

1 0

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

5

6

7

8

9

1 0

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

(ii) Σελιδοποίηση 5 4 3 2 1 1

2

3

4

Απάντηση Ερωτήματος Γ: Τα αποτελέσματα του ερωτήματος (β) είναι εμφανώς καλύτερα στην περίπτωση χρήσης σελιδοποιημένης μνήμης, τόσο όσον αφορά τους μέσους χρόνους διεκπεραίωσης και αναμονής όσο και σε σχέση με τον βαθμό πολυπρογραμματισμού που επιτυγχάνεται. -

οι χρόνοι διεκπεραίωσης και αναμονής είναι 10,83 και 6,66 στην περίπτωση σελιδοποίησης έναντι 15,83 και 11,66 στην περίπτωση των μεταβλητών διαιρέσεων χωρίς συμπίεση.

-

αντίστοιχα στην περίπτωση της σελιδοποίησης επιτυγχάνεται βαθμός πολυπρογραμματισμού 4 (4 διεργασίες ταυτόχρονα στη μνήμη) για αρκετές παραπάνω χρονικές στιγμές (και πιο συγκεκριμένα για όσες χρονικές στιγμές αυτό είναι δυνατόν – στιγμές δηλαδή κατά τις οποίες υπάρχουν στις ουρές διεργασίες για να εκτελεστούν) από ότι στην περίπτωση των μεταβλητών διαιρέσεων χωρίς συμπίεσης (6 έναντι 2)

Ο βασικός λόγος στον οποίον οφείλονται οι παρατηρούμενες διαφορές στη συγκεκριμένη περίπτωση είναι ότι λόγω της σελιδοποίησης είναι δυνατόν άμεσα (κατά τις χρονικές στιγμές 4-8) να αξιοποιηθούν/εκχωρηθούν διεσπαρμένα (όχι συνεχόμενα) τμήματα μνήμης (πλαίσια σελίδων) στις διεργασίες P5 και P6 ώστε να μπορούν στη συνέχεια να εκτελεστούν αυτές μαζί με τις P4 και P2 (round-robin) – πράγμα το οποίο δεν είναι δυνατόν να γίνει στην περίπτωση των μεταβλητών διαιρέσεων (παρά μόνο αν είχαμε συμπίεση). Ο επιπλέον βασικός λόγος στον οποίον οφείλονται οι παρατηρούμενες διαφορές όσον αφορά ειδικότερα (και μόνο) τους μέσους χρόνους διεκπεραίωσης και αναμονής είναι ότι οι διεργασίες που μπαίνουν να εκτελεστούν νωρίτερα στην περίπτωση της σελιδοποίησης (P5 και P6) είναι διεργασίες πολύ πιο ‘μικρού χρόνου εκτέλεσης’ από τις υπόλοιπες ταυτόχρονες (P2 και P4) και έτσι είναι σαν εκτελείται ουσιαστικά για τις 4 αυτές πλέον αλγόριθμος SJF (παρότι στην πραγματικότητα roundrobin) οπότε μοιραία έχουμε μικρότερους χρόνους διεκπεραίωσης και αναμονής (αντίθετα στην περίπτωση των μεταβλητών διαιρέσεων είναι σαν να εκτελείται ουσιαστικά για τις P2, P4, P5, P6 αλγόριθμος FCFS (παρότι στην πραγματικότητα round-robin). Αντίθετα με τα παραπάνω, Αν η διάρκεια (χρόνος εκτέλεσης) των διεργασιών P5 και P6 ήταν π.χ. 10 χρονικές μονάδες (αντίστοιχος δηλαδή του χρόνου εκτέλεσης των P4 και P6) τότε: -

ως προς το βαθμό πολυπρογραμματισμού μεν (πόσες διεργασίες βρίσκονται κάθε χρονική στιγμή στη μνήμη, αξιοποίηση CPU κ.λ.π.) το αποτέλεσμα-διαφορές θα ήταν ίδια και ακόμα πιο ενισχυμένα υπέρ της σελιδοποίησης (και πιο συγκεκριμένα οι χρονικές στιγμές που θα είχαμε 4 διεργασίες ταυτόχρονα στη μνήμη θα ήταν πολύ περισσότερες στην περίπτωση της σελιδοποίησης – καθώς θα εκτελούντο σε αυτήν την περίπτωση 4 διεργασίες των 10 χρονικών μονάδων ταυτόχρονα στη μνήμη με round-robin),

-

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

9 Αυτό θα συνέβαινε γιατί σε αυτήν την περίπτωση, με τη χρήση σελιδοποίησης (έναντι των μεταβλητών διαιρέσων) θα έμπαιναν νωρίτερα για εκτέλεση (μαζί με τις P2 και P4) δύο επίσης μεγάλες σε διάρκεια διεργασίες με αποτέλεσμα -

αφενός ο χρόνος διεκπεραίωσης των διεργασιών αυτών (P5, P6) να μην μειώνεται ουσιαστικά (καθώς θα εκτελούνται εκ περιτροπής με τις P2 και P4 καθόλη τη διάρκεια της εκτέλεσης των τελευταίων – αφού έχουν περίπου ίσους χρόνους εκτέλεσης/διάρκεια), αλλά να σύρεται περίπου στο τέλος δηλαδή προς το μέγιστο χρόνο εκτέλεσης όλων των διεργασιών – όπως ακριβώς και αν χρησιμοποιούνταν μεταβλητές διαιρέσεις και δεν έμπαιναν αυτές οι διεργασίες νωρίτερα αλλά μετα τις P4 και P2.

-

αφετέρου να ο χρόνος διεκπεραίωσης των διεργασιών P2 και P4 να αυξάνεται έναντι της περίπτωσης χρήσης μεταβλητών διαιρέσεων (καθώς καθόλη τη διάρκεια αυτών πλέον εκτελούνται μαζί/εκ περιτροπής και δύο άλλες διεργασίες/P5,P6 και να σύρεται και αυτός περίπου στο τέλος δηλαδή προς το μέγιστο χρόνο εκτέλεσης όλων των διεργασιών // πράγμα που δεν θα συνέβαινε αν χρησιμοποιούσαμε μεταβλητές διαιρέσεις – και οι P4,P2 θα τελείωναν νωρίτερα).

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

10

5. Σχήμα 1

p

KME

+

PTR

d

f

1

f

d

Φυσική Μνήμη

11

6. Παράδειγμα 3 Ενα σύστημα υποστηρίζει λογικό χώρο διευθύνσεων μεγέθους 2 24 bytes. Το μέγεθος των σελίδων είναι 256 bytes. Εστω η λογική διεύθυνση CB8F42 (σε δεκαεξαδική μορφή): ποιός είναι ο αριθμός σελίδας (page number) σε δεκαεξαδική μορφή; [επιλέξτε τη μοναδική σωστή απάντηση και αιτιολογείστε σύντομα] (Α) CB8F4 (Β) CB8

(Γ) CB8F

(Δ) 8F42

(Ε) 42

Απάντηση: Από εκφώνηση: - Μέγεθος λογικού χώρου διευθύνσεων = 224 bytes σημαίνει ότι το μήκος κάθε «λογικής διεύθυνσης» είναι ίσο με 24 bits ή αλλοιώς ίσο με 6 δεκαεξαδικά ψηφία - Μέγεθος σελίδας = 256 bytes = 28 bytes σημαίνει ότι σε κάθε «λογική διεύθυνση» απαιτούνται 8 bits για την αναπαράσταση της μετατόπισης (offset) μέσα στη σελίδα (δηλαδή 2 δεκαεξαδικά ψηφία) – και από θεωρία αυτά τα bits είναι πάντα τα ‘δεξιότερα’ (low order) bits της «λογικής διεύθυνσης» Επομένως (συνέχεια από θεωρία): - Τα ‘αριστερότερα’ (high order) 16 bits (24-8=16) που απομένουν (δηλαδή τα 4 αριστερότερα δεκαεξαδικά ψηφία) αντιστοιχούν στην αναπαράσταση του «αριθμού σελίδας» (page number) – τα οποία για τη συγκεκριμένη δοθείσα διεύθυνση (CB8F42) είναι τα ‘CB8F’ Η σωστή απάντηση είναι η (Γ)

12

7. Παράδειγμα 4 Θεωρούμε ένα χώρο λογικών διευθύνσεων που αποτελείται από 8 σελίδες των 512 bytes η κάθε μία και αντιστοιχίζεται σε φυσική μνήμη με 32 πλαίσια μνήμης. Ποια από τις παρακάτω προτάσεις είναι η μοναδική σωστή; Αιτιολογείστε σύντομα την απάντησή σας. (Α) Η λογική διεύθυνση έχει 14 bits και η φυσική διεύθυνση έχει 12 bits (Β) Η λογική διεύθυνση έχει 12 bits και η φυσική διεύθυνση έχει 14 bits (Γ) Η λογική διεύθυνση έχει 13 bits και η φυσική διεύθυνση έχει 13 bits (Δ) Η λογική διεύθυνση έχει 17 bits και η φυσική διεύθυνση έχει 5 bits (Ε) Καμία από τις παραπάνω προτάσεις δεν είναι σωστή Απάντηση: Από εκφώνηση: - Λογικός χώρος διευθύνσεων = 8 σελίδες των 512 bytes η κάθε μία = 23 σελίδες των 29 bytes η κάθε μία σημαίνει ότιγια την αναπαράσταση της λογικής διεύθυνσης απαιτούνται συνολικά 9+3=12 bits - Φυσική μνήμη = 32 πλαίσια μνήμης των 512 bytes το κάθε ένα (το μέγεθος λογικής σελίδας είναι εξ’ ορισμού ίσο πάντα με το μέγεθος φυσικού πλαισίου μνήμης) = 2 5 σελίδες των 29 bytes το κάθε ένα σημαίνει ότι για την αναπαράσταση της φυσικής διεύθυνσης απαιτούνται συνολικά 9+5=14 bits Επομένως: Η σωστή απάντηση είναι η (Β)

13

8. Ασκηση 3 Θεωρείστε ένα σύστημα σελιδοποιημένης μνήμης στο οποίο η ‘φυσική μνήμη’ αποτελείται από 140 σελίδες των 1024 bytes. Έστω επίσης μία διεργασία 12 σελίδων της οποίας μόνο κάποιες σελίδες είναι φορτωμένες στη φυσική μνήμη. Ο ακόλουθος πίνακας δείχνει τους αριθμούς πλαισίων της φυσικής μνήμης στα οποία είναι φορτωμένες οι σελίδες αυτές. Αρ. Πλαισίου Φυσικής Μνήμης

Αριθμός Λογικής Σελίδας Διεργασίας

----------------------------------------------------------------------------------------------0

6

1

8

2

9

3

0

4

4

5

5

6

3

7

7

Ερωτήσεις: (α) Από πόσα bits αποτελείται κάθε ‘φυσική διεύθυνση’; (β) Σε ποιές ‘φυσικές διευθύνσεις’ αντιστοιχούν οι ακόλουθες ‘λογικές’ (δίνονται στο ‘οκταδικό’ σύστημα): (i) 00030, (ii) 06122, (iii) 26271, (iv) 23456 Τις απαντήσεις σας θα πρέπει να τις δώσετε στο ‘δεκαεξαδικό’ σύστημα. Απαντήσεις: (α) Εφόσον η ‘φυσική μνήμη’ αποτελείται από 140 σελίδες των 1024 bytes απαιτούνται,  8 bits για τη δυαδική αναπαράσταση του Αριθμού Πλαισίου της φυσικής μνήμης (καθώς το 140 βρίσκεται ανάμεσα στα 128=27 και 256=28) και  10 bits (1024=210) για τη δυαδική αναπαράσταση του Αριθμού Θέσης μέσα στο πλαίσιο (μετατόπιση). Αρα κάθε ‘φυσική διεύθυνση’ αποτελείται από 8+10=18bits. (β) Αρχικά κατασκευάζουμε τον Πίνακα Σελίδων της διεργασίας, ο οπόιος έχει ως ακολούθως (χρησιμοποιείται ένα Valid/Invalid-bit το οποίο υποδηλώνει για κάθε σελίδα της διεργασίας αν βρίσκεται ή όχι στη φυσική μνήμη): Αριθμός Λογικής Σελίδας 0 1 2 3 4 5 6 7 8 9 10 11

Valid/ Invalid V I I V V V V V V V I I

Αριθμός Πλαισίου Μνήμης 3 6 4 5 0 7 1 2 -

14 Απλά δηλαδή με βάση τον πίνακα ‘αντίστροφης αντιστοίχισης’ που μας δίνεται σημειώνουμε με τη σειρά για κάθε μία από τις 12 σελίδες της διεργασίας (0...11) σε πιο πλαίσιο μνήμης είναι αντιστοιχισμένη (αν είναι – και θέτουμε το valid/invalid bit στο valid) και αφήνουμε κενά για αυτές που δεν είναι αντιστοιχισμένες σε κανένα πλαίσιο μνήμης (θέτοντας το valid/invalid bit στο invalid) Στη συνέχεια για να μεταρέψουμε τις δοθείσες διευθύνσεις, αρχικά θα πρέπει να σημειωθεί ότι (ακολουθώντας την ίδια λογική όπως παραπάνω για τον υπολογισμό των bits της κάθε ‘φυσικής διεύθυνσης’) για κάθε ‘λογική διεύθυνση’ απαιτούνται (με αναφορά στη συγκεκριμένη διεργασία/πρόγραμμα),



οπωσδήποτε 10 bits (1024=210) για τη δυαδική αναπαράσταση του Αριθμού Θέσης μέσα στη σελίδα (μετατόπιση), και



τουλάχιστον 4 bits για τη δυαδική αναπαράσταση του Αριθμού Λογικής Σελίδας (καθώς η διεργασία για την οποία μας δίνουν πληροφορία αποτελείται από 12 σελίδες – και ο αριθμός 12 βρίσκεται ανάμεσα στο 8=23 και το 16=24).

Αρα για κάθε ‘λογική διεύθυνση’ απαιτούνται τουλάχιστον 4 + 10 = 14 bits, ή αλλοιώς 5 ψηφία στο οκταδικό σύστημα για την αναπαράστασή της. Από τον αριθμό των bits επίσης των διευθύνσεων που μας δίνονται για μετάφραση (5 οκταδικά ψηφία – ή 3x5=15 bits) αντιλαμβανόμαστε ότι οι λογικές διευθύνσεις (λογικός χώρος διευθύνσεων του συστήματος) αποτελούνται από 14 έως15 bits (το υψηλότερης τάξης οκταδικό ψηφίο θα είναι απαραίτητο είτε τα δύο μόνο από τα bits στα οποία αντιστοιχεί είναι χρήσιμα είτε και τα τρία), πράγμα που συνάγει με τα παραπάνω. Αν μας δίνονταν διευθύνσεις για μετάφραση στο δυαδικό (αντί του οκταδικού) σύστημα, μόνο τότε θα μπορούσαμε να υπολογίσουμε (από το μέγεθος/μήκος αυτών) ακριβώς και εκ του ασφαλούς το πλήθος των bits που αναπαριστούν την κάθε ‘λογική διεύθυνση’ για οποιαδήποτε διεργασία του συστήματος (λογικός χώρος διευθύνσεων του συστήματος). Αρα έχουμε: (i) 00030 = 000 00 - 0 000 011 000 άρα εξετάζουμε τη θέση 0 του πίνακα σελίδων και λαμβάνουμε τον αντίστοιχο αριθμό πλαισίου (3) και καταλήγουμε σε φυσική διεύθυνση: δυαδικό: 000 000 11 - 0 000 011 000 = 000000110000011000 δεκαεξαδικό: 00C18 (ii) 06122 = 000 11 - 0 001 010 010 άρα εξετάζουμε τη θέση 3 του πίνακα σελίδων και λαμβάνουμε τον αντίστοιχο αριθμό πλαισίου (6) και καταλήγουμε σε φυσική διεύθυνση: δυαδικό: 000 001 10 - 0 001 010 010 = 000001100001010010 δεκαεξαδικό: 01852 (iii) 26271 = 010 11 - 0 010 111 001 άρα εξετάζουμε τη θέση 11 του πίνακα σελίδων όπου όμως βλέπουμε ότι δεν αντιστοιχίζεται πουθενά η συγκεκριμένη σελίδα (δεν βρίσκεται στη μνήμη) – έχουμε δηλαδή σφάλμα αναφοράς σελίδας (page fault) (iv) 23456 = 010 01 - 1 100 101 110 άρα εξετάζουμε τη θέση 9 του πίνακα σελίδων και λαμβάνουμε τον αντίστοιχο αριθμό πλαισίου (2) και καταλήγουμε σε φυσική διεύθυνση: δυαδικό: 000 000 10 - 1 100 101 110 = 000000101100101110 δεκαεξαδικό: 00B2E

15

9. Σχήμα 2

SEGMENTED PAGING (τμηματοποίηση του Πίνακα Σελίδων

KME

p

d

s

p'

s

p'

d

Φυσική Μνήμη

f + Μήκος

STΒR

ΒάσηΠΣ

s 1

+

f

p' Πίνακας Τμημάτων Τμήμα του Πίνακα Σελίδων

d

16

10. Παράδειγμα 5 Θεωρείστε μία λογική διεύθυνση των 36 bits σε ένα σύστημα διαχείρισης μνήμης με Τμηματοποιημένη Σελιδοποίηση (segmented paging). Σε αυτή τη διεύθυνση, τα 4 πιο αριστερά bits σηματοδοτούν τον αριθμό τμήματος του πίνακα σελίδων, τα επόμενα 10 σηματοδοτούν τη μετατόπιση στο συγκεκριμένο τμήμα, και τα υπόλοιπα 22 προσδιορίζουν τη λέξη μέσα στη σελίδα. (i) απαντήστε αιτιολογημένα στις ακόλουθες ερωτήσεις: -

Ποιο είναι το μέγεθος σελίδας του συστήματος σε λέξεις; Ποιο είναι το μέγιστο μέγεθος τμήματος ενός πίνακα σελίδων σε θέσεις; Ποιος είναι ο μέγιστος αριθμός σελίδων που μπορεί να υποστηρίξει το σύστημα; Ποιος είναι ο μέγιστος αριθμός τμημάτων ενός πίνακα σελίδων; Ποιο είναι το μέγιστο μέγεθος λογικού προγράμματος που μπορεί να υποστηρίξει το σύστημα σε λέξεις;

(ii) Εστω ότι δίνονται τα ακόλουθα στοιχεία: η λογική διεύθυνση 700022222222 (στο οκταδικό σύστημα) στις τελευταίες 2 θέσεις του Πίνακα Τμημάτων του Πίνακα Σελίδων της διεργασίας περιέχονται οι διευθύνσεις βάσης ‘Α’ και ‘Β’ αντίστοιχα στις θέσεις Α, Α+1, Α+2 περιέχονται αντίστοιχα οι αριθμοί ‘1116’, ‘7701’, ‘3411’ (οκταδικό), ενώ στις θέσεις Β, Β+1, Β+2 περιέχονται αντίστοιχα οι αριθμοί ‘1777’, ‘6600’, ‘0401’ (οκταδικό) Απαντήστε αιτιολογημένα στις ακόλουθες ερωτήσεις: -

Ποια είναι η ‘φυσική’ διεύθυνση (οκταδικό) που αντιστοιχεί στην παραπάνω λογική; Ποιο είναι το μέγεθος της φυσικής μνήμης του συστήματος σε λέξεις;

Απαντήσεις: -

Ποιο είναι το μέγεθος σελίδας του συστήματος σε λέξεις; 222 Ποιο είναι το μέγιστο μέγεθος τμήματος ενός πίνακα σελίδων σε θέσεις; 210 Ποιος είναι ο μέγιστος αριθμός σελίδων που μπορεί να υποστηρίξει το σύστημα; 24 x 210 = 214 Ποιος είναι ο μέγιστος αριθμός τμημάτων ενός πίνακα σελίδων; 24 Ποιο είναι το μέγιστο μέγεθος λογικού προγράμματος που μπορεί να υποστηρίξει το σύστημα σε λέξεις; 24 x 210 x 222 = 236

Εχουμε τη λογική διεύθυνση 700022222222 (οκταδικό) = 111 0 - 00 000 000 01 - 0 010 010 010 010 010 010 010 (δυαδικό): - Σύμφωνα με την εκφώνηση τα πρώτα 4 bits σηματοδοτούν τον αριθμό τμήματος του πίνακα σελίδων, άρα αυτός αντιστοιχεί στο τμήμα ‘Ε’. Αντιστοιχεί δηλαδή στην προτελευταία θέση του πίνακα τμημάτων του πίνακα σελίδων (η τελευταίες δύο θέσεις είναι οι ‘E’ και ‘F’), άρα μας παραπέμπει στη διεύθυνση βάσης ‘Α’. - Στη συνέχεια πρέπει να πάμε στη θέση εκείνη του Πίνακα Σελίδων (που αρχίζει στη διεύθυνση ‘Α’) που μας δείχνουν τα 10 επόμενα bits της αρχικής λογικής διεύθυνσης. Τα επόμενα αυτά 10 bits της αρχικής λογικής διεύθυνσης αντιστοιχούν στον αριθμό/θέση ‘1’. - Πηγαίνουμε λοιπόν στη θέση ‘1’ του Πίνακα Σελίδων ο οποίος αρχίζει από τη διεύθυνση ‘Α’, δηλαδή στην θέση ‘Α+1’ αυτού και παίρνουμε τον αριθμό που περιέχεται εκεί (7701 - οκταδικό). Αυτός είναι και ο τελικός αριθμός σελίδας της τελικής ‘φυσικής διεύθυνσης’. - Σε αυτόν τέλος προσθέτουμε (κολλάμε στο τέλος) τα τελευταία 22 bits της αρχικής λογικής διεύθυνσης και καταλήγουμε στην τελική ‘φυσική διεύθυνση’ που είναι η 7701 - 0 010 010 010 010 010 010 010 = 111 111 000 001 - 0 010 010 010 010 010 010 010 (δυαδικό) = 1 111 110 000 010 010 010 010 010 010 010 010 = 176022222222 (οκταδικό) Επειδή ο τελικός αριθμός σελίδας μας δίνεται με 4 οκταδικά ψηφία, δηλαδή 12 bits – εξάγουμε το συμπέρασμα ότι το σύστημα μπορεί να υποστηρίξει μέχρι και 212 σελίδες. Αρα (δεδομένου ότι το μέγεθος μίας σελίδας/πλαισίου) του συστήματος είναι ίσο με 222 λέξεις, το συνολικό μέγεθος της φυσικής μνήμης του συστήματος σε λέξεις είναι 212 χ 222 = 234

17

11. Ασκηση 4 Εστω ένα σύστημα τμηματοποιημένης σελιδοποίησης το οποίο υποστηρίζει λογικό χώρο διευθύνσεων της τάξεως των 220 σελίδων των 212 bytes η κάθε μία (μέγεθος σελίδας) και παρέχει τη δυνατότητα τμηματοποίησης του πίνακα σελίδων έως και σε 2 4 τμήματα. Εστω επίσης ότι το μέγεθος φυσικής μνήμης του συστήματος αποτελείται επίσης από 220 πλαίσια σελίδων (των 212 bytes το καθένα) – δηλαδή συνολικά φυσική μνήμη των 232 bytes (4GB). Εστω επίσης οι ακόλουθοι πίνακες (ο εξωτερικός πίνακας τμημάτων και μέρος των εσωτερικών/ επιμέρους πινάκων σελίδων): Πίνακας Τμημάτων (στα οποία έχει χωριστεί ο πίνακας σελίδων) 0 xxx0 xxxx xxxx xxxx 1 0001 0000 2 0000 0000 3 4 xxxx xxxx xxxx xxxx 5 xxxx xxxx 6 xxxx xxxx 7 8 xxx1 xxxx xxxx xxxx 9 10 0000 1111 11 1111 1111 12 0000 0000 13 0000 0000 14 0000 1111 15 1111 0000 16 xxx1 xxxx 17 xxxx xxxx 18 0000 1111 19 1111 0000 20 0000 0000 21 0000 0000 22 0000 1111 23 0000 0000 24 xxxx xxxx 25 xxxx xxxx 26 0000 0000 27 0000 0000 28 0000 0000 29 0000 0000 30 0000 0000 31 0000 0000 ...... ................. ...... ................. ...... ................. ...... ................. ...... ................. ...... ................. ...... ................. ...... .................

Μέρος της Μνήμης (που αρχίζει στη διεύθυνση 00000EF8) 00000EF8 xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 00000F00 xxx0 xxxx xxxx 1000 0010 0000 1011 1110 xxx0 xxxx xxxx 1100 0010 1111 1011 1110 xxx1 xxxx xxxx 1000 0010 0000 1011 1110 xxx1 xxxx xxxx 1100 0010 0000 1011 1110 ................. ................. ................. ................. ................. ................. ................. ................. ...... ................. ...... ...... ................. ...... ................. ................. ...... ...... ................. ...... ...... ................. ................. .................

Μέρος της Μνήμης (που αρχίζει στη διεύθυνση 00000FE8) 00000FE8 xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 00000FF0 xxx1 xxxx xxxx 1110 1110 1111 1011 0000 xxx0 xxxx xxxx 1110 1110 1111 1011 0000 xxx1 xxxx xxxx 1111 1010 1111 1010 0101 xxx1 xxxx xxxx 1110 0011 1111 1010 0000 ................. ................. ................. ................. ................. ................. ................. ................. ...... ................. ...... ...... ................. ...... ................. ................. ...... ................. ...... ...... ................. ...... ................. .................

Για κάθε εγγραφή του πίνακα τμημάτων υποθέστε ότι απαιτούνται 64 bits (8 bytes) εκ των οποίων (α) τα πρώτα (high-order) 16 bits χρησιμοποιούνται για την αποθήκευση βοηθητικών πληροφοριών

18

ελέγχου (και ακόμα πιο συγκεκριμένα το 4ο στη σειρά από αυτά αποτελεί το valid/invalid bit για το συγκεκριμένο τμήμα (γ) τα επόμενα 16 bits αναπαριστούν το μήκος του συγκεκριμένου τμήματος σε εγγραφές, και (γ) τα τελευταία (low-order) 32 bits αναπαριστούν τη βάση (διεύθυνση) φυσικής μνήμης όπου αρχίζει η αποθήκευση του συγκεκριμένου τμήματος. Για κάθε εγγραφή του κάθε τμήματος του πίνακα σελίδων αντίστοιχα,υποθέστε ότι απαιτούνται 32 bits (4 bytes) εκ των οποίων (α) τα πρώτα (high-order) 12 bits χρησιμοποιούνται για την αποθήκευση βοηθητικών πληροφοριών ελέγχου (και ακόμα πιο συγκεκριμένα το 4ο στη σειρά από αυτά αποτελεί το valid/invalid bit για την συγκεκριμένη σελίδα), ενώ (β) τα επόμενα (low-order) 20 bits αναπαριστούν τον αριθμό πλαισίου της μνήμης όπου είναι αποθηκευμένη η συγκεκριμένη σελίδα. Ερώτηση: Εστω ότι για το παραπάνω σύστημα μας δίνεται (σε δεκαεξαδική μορφή) οι ακόλουθες «λογικές διευθύνσεις»: (α) 10001F27 (β) 20003FF3 (γ) 20001FF2 (δ) 00002FFF Απαντήσεις: (α) Η διεύθυνση 10002F27 μεταφράζεται στο δυαδικό σύστημα ως ακολούθως: 0001 0000 0000 0000 0010 1111 0010 0111 = 0001 - 0000 0000 0000 0010 - 1111 0010 0111 Αρα αρχικά (λαμβάνοντας τα πρώτα 4 bits της ανωτέρω διεύθυνσης) πρέπει να προσπελάσουμε την εγγραφή ‘1’ (‘0001’ – ή αλλοιώς την 2η στη σειρά εγγραφή) του πίνακα τμημάτων (δηλαδή ουσιαστικά τη θέση/byte ‘1000’/‘8’ καθώς κάθε εγγραφή απαιτεί 8 bytes για την αποθήκευσή της). Από την εγγραφή αυτή (διαβάζοντας δηλαδή συνεχόμενα 8 bytes μνήμης αρχίζοντας από τη θέση ‘1000’) λαμβάνουμε (α) το μήκος τμήματος και (β) τη βάση (διεύθυνση φυσικής μνήμης) ‘Β’ όπου αρχίζει η αποθήκευση του συγκεκριμένου τμήματος σελίδων (τα τελευταία 32 bits της εγγραφής): 0000 0000 0000 0000 0000 1111 1111 0000 (στο δυαδικό) = 00000FF0 (στο δεκαεξαδικό) Αφού προσπελάσουμε τη διεύθυνση μνήμης αυτής πρέπει να μετακινηθούμε (μετατόπιση μέσα στο τμήμα – προσθέτοντας δηλαδή στη βάση ‘Β’ τον αριθμό που μας υπαγορεύουν τα επόμενα 16 bits της αρχικής διεύθυνσης) στην εγγραφή ‘2’ (‘10’ – ή αλλοιώς την 3 η στη σειρά εγγραφή) του τμήματος αυτού του πίνακα σελίδων (δηλαδή ουσιαστικά τη θέση/byte ‘1000’/‘8’ – διεύθυνση 00000FF8 – καθώς κάθε εγγραφή απαιτεί 4 bytes για την αποθήκευσή της). Από την εγγραφή αυτή (διαβάζοντας δηλαδή συνεχόμενα 4 bytes μνήμης αρχίζοντας από τη θέση ‘1000’) λαμβάνουμε τον αριθμό πλαισίου ‘f’ στο οποίο είναι αποθηκευμένη η ‘σελίδα’ την οποία ψάχνουμε στη φυσική μνήμη: 1111 1010 1111 1010 0101 (στο δυαδικό) = FAFA5 (στο δεκαεξαδικό) Στον αριθμό αυτό ‘f’ δεν έχουμε πλέον παρά να προσθέσουμε στο τέλος (concatanation) τα 12 τελαυταία bits της αρχικής λογικής διεύθυνσης (offset) για να καταλήξουμε στην τελική «φυσική διεύθυνση» την οποία αναζητούμε, δηλαδή στη διεύθυνση: 1111 1010 1111 1010 0101 - 1111 0010 0111 (δυαδικό) = FAFA5F27 (δεκαεξαδικό) (β) Η διεύθυνση 20003FF3 μεταφράζεται στο δυαδικό σύστημα σε 0010 0000 0000 0000 0011 1111 1111 0011 = 0010 – 0000 0000 0000 0011 – 1111 1111 0011 και με την ίδια διαδικασία καταλήγουμε σε τελική φυσική διεύθυνση: 1100 0010 0000 1011 1110 - 1111 1111 0011 = C20BEFF3 (γ) Η διεύθυνση 20001FF2 μεταφράζεται στο δυαδικό σύστημα σε 0010 0000 0000 0000 0001 1111 1111 0010 = 0010 – 0000 0000 0000 0001 – 1111 1111 0010 και με την ίδια διαδικασία πηγαίνουμε μεν στη διεύθυνση 00000F00 αλλά μετά πηγαίνοντας στην υπαγορευόμενη θέση ‘1’ αυτού (2η εγγραφή) διαπιστώνουμε ότι το αντίστοιχο valid/invalid bit / 4ο bit είναι ‘0’ οπότε έχουμε page fault. (δ) Η διεύθυνση 00002FFF αντίστοιχα μεταφράζεται σε δυαδικό σε 0000 0000 0000 0000 0010 1111 1111 1111 = 0000 – 0000 00 00 0000 0010 – 1111 1111 1111 και με την ίδια διαδικασία διαπιστώνουμε ότι (πηγαίνοντας στη θέση ‘0’ – 1η εγγραφή του αρχικού πίνακα τμημάτων), το αντίστοιχο valid/invalid bit / 4ο bit είναι ‘0’ οπότε έχουμε segment fault.

19

12. Σχήμα 3

TWO-LEVEL PAGING (σελιδοποίηση του Πίνακα Σελίδων

KME

p1

p

d

p1

p2

d

Φυσική Μνήμη

f1

+ 1

OPTR

p2

f

p2

f1

p1 1

f

p2 Outer Page Table (εξ. πίνακας σελίδων) Σελίδα του Πίν. Σελίδων (πλαίσιο f1 της μνήμης)

d

20

13. Παράδειγμα 6 Θεωρείστε μία λογική διεύθυνση των 32 bits σε ένα σύστημα διαχείρισης μνήμης με Σελιδοποίηση Δύο Επιπέδων (Two-level Paging). Σε αυτή τη διεύθυνση, τα 10 πιο αριστερά bits σηματοδοτούν τη μετατόπιση στον ‘εξωτερικό πίνακα σελίδων’ (outer page table), τα επόμενα 10 σηματοδοτούν τη μετατόπιση στην επιμέρους σελίδα του πραγματικού πίνακα σελίδων, και τα υπόλοιπα 12 προσδιορίζουν τη λέξη μέσα στη σελίδα που αναζητούμε. Εστω επίσης ότι για κάθε εγγραφή του πίνακα σελίδων (είτε του outer page table είτε του πραγματικού πίνακα σελίδων) υποθέστε ότι απαιτούνται 32 bits (4 bytes) εκ των οποίων (α) τα πρώτα (high-order) 12 bits χρησιμοποιούνται για την αποθήκευση βοηθητικών πληροφοριών ελέγχου (και ακόμα πιο συγκεκριμένα το 4ο στη σειρά από αυτά αποτελεί το valid/invalid bit για την συγκεκριμένη σελίδα), ενώ (β) τα επόμενα (low-order) 20 bits αναπαριστούν τον αριθμό πλαισίου της μνήμης όπου είναι αποθηκευμένη η συγκεκριμένη σελίδα. Απαντήστε αιτιολογημένα στις ακόλουθες ερωτήσεις: -

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

Απαντήσεις: -

Ποιο είναι το μέγεθος σελίδας του συστήματος σε bytes; 212 Ποιο είναι το μέγεθος του εξωτερικού πίνακα σελίδων σε θέσεις (εγγραφές); 210 Ποιο είναι το μέγεθος του εξωτερικού πίνακα σελίδων σε bytes; 212 Ποιο είναι το μέγεθος του συνολικού πίνακα σελίδων σε θέσεις (εγγραφές); 220 Ποιο είναι το μέγεθος του συνολικού πίνακα σελίδων σε bytes; 224 Ποιο είναι το μέγεθος του κάθε εσωτερικού πίνακα σελίδων (ο οποίος δεικτοδοτείται από τον εξωτερικό) σε θέσεις (εγγραφές); [οι εγγραφές που χωρούν σε 1σελίδα] = 210 Ποιο είναι το μέγεθος του κάθε εσωτερικού πίνακα σελίδων (ο οποίος δεικτοδοτείται από τον εξωτερικό) σε bytes; [τα bytes που αποτελούν 1 σελίδα] = 212 Ποιος είναι ο μέγιστος αριθμός σελίδων που μπορεί να υποστηρίξει το σύστημα; 220 Ποιο είναι το μέγιστο μέγεθος λογικού προγράμματος που μπορεί να υποστηρίξει το σύστημα σε bytes; 232

21

14. Ασκηση 5 Εστω ένα σύστημα σελιδοποίησης δύο επιπέδων (two-level paging) το οποίο υποστηρίζει λογικό χώρο διευθύνσεων της τάξεως των 220 σελίδων των 212 bytes η κάθε μία (μέγεθος σελίδας) και παρέχει τη δυνατότητα δεικτοδότησης του πίνακα σελίδων με κατάλογο μεγέθους έως και 2 10 εγγραφών. Εστω επίσης ότι το μέγεθος φυσικής μνήμης του συστήματος αποτελείται επίσης από 220 πλαίσια σελίδων (των 212 bytes το καθένα) – δηλαδή συνολικά φυσική μνήμη των 232 bytes (4GB). Εστω επίσης οι ακόλουθοι πίνακες σελίδων (ο εξωτερικός πίνακας σελίδων – outer page table – και μέρος των εσωτερικών/επιμέρους πινάκων σελίδων): Outer Page Table (εξ. πίνακας σελίδων) 0 xxx0 xxxx xxxx 0000 1 0001 1111 2 0101 1111 3 4 xxx1 xxxx xxxx 0000 5 0000 1111 6 0101 1010 7 8 xxx1 xxxx xxxx 0000 9 10 0000 1111 11 0101 1011 12 xxx0 xxxx 13 xxxx 0000 14 0001 1111 15 0101 1110 ...... ................. ...... ................. ...... ................. ...... ................. ...... ................. ...... ................. ...... ................. ...... .................

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...... ...... ...... ...... ...... ...... ...... ......

Μέρος της Μνήμης (πλαίσιo 00F5A) xxx1 xxxx xxxx 1000 0010 1100 1011 1110 xxx0 xxxx xxxx 1000 0010 1100 1011 0010 xxx1 xxxx xxxx 1000 0010 0000 1011 1110 xxx0 xxxx xxxx 1000 0010 0000 1011 0010 ................. ................. ................. ................. ................. ................. ................. .................

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...... ...... ...... ...... ...... ...... ...... ......

Μέρος της Μνήμης (πλαίσιo 00F5B) xxx0 xxxx xxxx 1110 0010 0000 1011 0000 xxx0 xxxx xxxx 1110 0010 1111 1011 1100 xxx1 xxxx xxxx 1110 0010 0011 1011 1100 xxx1xxxx xxxx 1110 0010 1111 1011 0000 ................. ................. ................. ................. ................. ................. ................. .................

Για κάθε εγγραφή του πίνακα σελίδων (είτε του outer page table είτε του πραγματικού πίνακα σελίδων) υποθέστε ότι απαιτούνται 32 bits (4 bytes) εκ των οποίων (α) τα πρώτα (high-order) 12 bits χρησιμοποιούνται για την αποθήκευση βοηθητικών πληροφοριών ελέγχου (και ακόμα πιο συγκεκριμένα το 4ο στη σειρά από αυτά αποτελεί το valid/invalid bit για την συγκεκριμένη σελίδα), ενώ (β) τα επόμενα (low-order) 20 bits αναπαριστούν τον αριθμό πλαισίου της μνήμης όπου είναι αποθηκευμένη η συγκεκριμένη σελίδα. Ερώτηση: Εστω ότι για το παραπάνω σύστημα μας δίνεται (σε δεκαεξαδική μορφή) οι ακόλουθες «λογικές διευθύνσεις»: (α) 0080313F (β) 00402333 (γ) 00002FFF (δ) 0080113F Απαντήσεις: (α) Η διεύθυνση 0080313F μεταφράζεται στο δυαδικό σύστημα ως ακολούθως: 0000 0000 1000 0000 0011 0001 0011 1111 = 0000 0000 10 – 00 0000 0011 – 0001 0011 1111 Αρα αρχικά (λαμβάνοντας τα πρώτα 10 bits της ανωτέρω διεύθυνσης) πρέπει να προσπελάσουμε την εγγραφή ‘2’ (‘10’ – ή αλλοιώς την 3η στη σειρά εγγραφή) του εξωτερικού πίνακα σελίδων (δηλαδή

22

ουσιαστικά τη θέση/byte ‘1000’/‘8’ καθώς κάθε εγγραφή απαιτεί 4 bytes για την αποθήκευσή της). Από την εγγραφή αυτή (διαβάζοντας δηλαδή συνεχόμενα 4 bytes μνήμης αρχίζοντας από τη θέση ‘1000’) λαμβάνουμε τον αριθμό πλαισίου ‘f1’ στο οποίο είναι αποθηκευμένη η ‘σελίδα’ του συνολικού πίνακα σελίδων που αντιστοιχεί στην εγγραφή αυτή: 0000 0000 1111 0101 1010 (στο δυαδικό) = 00F5Β (στο δεκαεξαδικό) Αφού προσπελάσουμε το πλαίσιο αυτό πρέπει να μετακινηθούμε στην εγγραφή ‘3’ (‘11’ – ή αλλοιώς την 4η στη σειρά εγγραφή) της σελίδας αυτής του πίνακα σελίδων (δηλαδή ουσιαστικά τη θέση/byte ‘1100’/‘12’ καθώς κάθε εγγραφή απαιτεί 4 bytes για την αποθήκευσή της). Από την εγγραφή αυτή (διαβάζοντας δηλαδή συνεχόμενα 4 bytes μνήμης αρχίζοντας από τη θέση ‘1100’) λαμβάνουμε τον αριθμό πλαισίου ‘f’ στο οποίο είναι αποθηκευμένη η ‘σελίδα’ την οποία ψάχνουμε στη φυσική μνήμη: 1110 0010 1111 1011 0000 (στο δυαδικό) = Ε2FΒ0 (στο δεκαεξαδικό) Στον αριθμό αυτό ‘f’ δεν έχουμε πλέον παρά να προσθέσουμε στο τέλος (concatanation) τα 12 τελαυταία bits της αρχικής λογικής διεύθυνσης (offset) για να καταλήξουμε στην τελική «φυσική διεύθυνση» την οποία αναζητούμε, δηλαδή στη διεύθυνση: 1110 0010 1111 1011 0000 - 0001 0011 1111 (δυαδικό) = Ε2FΒ013F (δεκαεξαδικό) (β) Η διεύθυνση 00402333 αντίστοιχα μεταφράζεται σε δυαδικό σε 0000 0000 0100 0000 0010 0011 0011 0011 = 0000 0000 01– 00 0000 0010 – 0011 0011 0011 και με την ίδια διαδικασία καταλήγουε σε φυσική διεύθυνση: 1000 0010 0000 1011 1110 0011 0011 0011 = 820ΒΕ333 (γ) Η διεύθυνση 00002FFF αντίστοιχα μεταφράζεται σε δυαδικό σε 0000 0000 0000 0000 0010 1111 1111 1111 = 0000 0000 00 – 00 0000 0010 1111 1111 1111 και με την ίδια διαδικασία διαπιστώνουμε ότι (πηγαίνοντας στη θέση ‘0’ – 1η εγγαρφή του outer page table), το αντίστοιχο valid/invalid bit / 4ο bit είναι ‘0’ οπότε έχουμε page fault (δ) Η διεύθυνση 0080113F αντίστοιχα μεταφράζεται σε δυαδικό σε 0000 0000 1000 0000 0001 0001 0011 1111 = 0000 0000 10 – 00 0000 0001 – 0001 0011 1111 και με την ίδια διαδικασία πηγαίνουμε μεν στο πλαίσιο 00F5B αλλά μετά πηγαίνοντας στην υπαγορευόμενη θέση ‘1’ αυτού (2η εγγραφή) διαπιστώνουμε ότι το αντίστοιχο valid/invalid bit / 4ο bit είναι ‘0’ οπότε έχουμε page fault.