Λειτουργικά Συστήματα — Σεπτέμβριος 2020 (Θέματα 1)¶
Μεταγραφή από το αρχείο Themata1-OS-Final-Sept-2020.pdf (2 σελίδες), ελεγμένη με τις σελίδες του πρωτοτύπου. Το σχήμα του Ερωτήματος 1 περιγράφεται ως [Σχήμα].
Themata1-OS-Final-Sept-2020.pdf¶
Πολυτεχνική Σχολή Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών & Πληροφορικής
ΛΕΙΤΟΥΡΓΙΚΑ ΣΥΣΤΗΜΑΤΑ 2019-2020 ΕΞΕΤΑΣΕΙΣ ΣΕΠΤΕΜΒΡΙΟΥ 2020 ΔΙΔΑΣΚΟΝΤΕΣ: Σ. ΣΙΟΥΤΑΣ, Χ. ΜΑΚΡΗΣ, Α. ΗΛΙΑΣ ΔΙΑΡΚΕΙΑ:1:30 ΩΡΑ¶
ΕΡΩΤΗΜΑ 1 [4Μ]¶
Έστω ο παρακάτω γράφος προτεραιότητας (precedence graph) που περιγράφει την εκτέλεση των εργασιών Ε1 έως Ε8. Να δώσετε χρησιμοποιώντας σημαφόρους ένα «παράλληλο» πρόγραμμα εκτέλεσης των ανωτέρω εργασιών (μη ξεχάσετε να αρχικοποιήσετε τις σημαφόρους που θα χρησιμοποιήσετε). [4]
[Σχήμα: γράφος προτεραιότητας με κόμβους Ε1 έως Ε8· ακμές Ε1 → Ε3, Ε3 → Ε4, Ε4 → Ε5, Ε2 → Ε5, Ε5 → Ε8, Ε6 → Ε8, Ε7 → Ε8]
ΕΡΩΤΗΜΑ 2 [3Μ]¶
Θεωρείστε τέσσερις (4) διεργασίες με χρόνους άφιξης (XA) και εκτέλεσης (XE) όπως δίνονται στον ακόλουθο πίνακα (οι χρόνοι στον πίνακα αναφέρονται στην ίδια χρονική μονάδα π.χ. ms):
| Διεργασία | Χρόνος άφιξης (ΧΑ) | Διάρκεια εκτέλεσης (ΧΕ) |
|---|---|---|
| Α | 0 | 6 |
| Β | 0 | 4 |
| Γ | 2 | 1 |
| Δ | 3 | 3 |
(α) Σχεδιάστε το διάγραμμα Gantt για τον αλγόριθμο χρονοδρομολόγησης SJF (Shortest Job First). [1]
(β) Σχεδιάστε για τις ίδιες διεργασίες το διάγραμμα Gantt για τον αλγόριθμο χρονοδρομολόγησης Round Robin (RR) με κβάντο 3 χρονικές μονάδες. Σημ.1.: Θεωρείστε πώς αν μια χρονική στιγμή μια διεργασία αφήνει την ΚΜΕ και την ίδια χρονική στιγμή καταφθάνει μια νέα διεργασία στο σύστημα, τότε η διεργασία που αφήνει την ΚΜΕ εισέρχεται πρώτη στην ουρά των διεργασιών. Σημ.2.: Μεταξύ των Α και Β στην αρχή (χρονική στιγμή 0) θεωρείστε ότι προηγείται η Α. [1]
(γ) Υπολογίστε το ποσοστό βελτίωσης του μέσου χρόνου διεκπεραίωσης που φέρνει ο SJF σε σχέση με το μέσο χρόνο διεκπεραίωσης του αλγόριθμου RR. [1]
ΕΡΩΤΗΜΑ 3 [3Μ]¶
Σε ένα σύστημα απλής σελιδοποίησης (paging) αντιστοιχίζονται λογικές διευθύνσεις των Λ bits σε φυσικές διευθύνσεις των Φ bits. Εάν Λ=16 και ο πλήρης πίνακας σελίδων της μονάδας διαχείρισης μνήμης κατά την εκτέλεση μίας διεργασίας Δ1 είναι ο παρακάτω:
Καλή Επιτυχία!!!
Πολυτεχνική Σχολή
Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών & Πληροφορικής
| Αριθμός λογικής σελίδας |
Αριθμός πλαισίου φυσικής μνήμης |
Έγκυρο/άκυρο (V/I) bit |
|---|---|---|
| 15 | 000 | I |
| 14 | 000 | I |
| 13 | 000 | I |
| 12 | 000 | I |
| 11 | 111 | V |
| 10 | 000 | Ι |
| 9 | 101 | V |
| 8 | 000 | Ι |
| 7 | 000 | Ι |
| 6 | 000 | Ι |
| 5 | 011 | V |
| 4 | 100 | V |
| 3 | 000 | V |
| 2 | 110 | V |
| 1 | 001 | V |
| 0 | 010 | V |
(α) Υπολογίστε για τις λογικές διευθύνσεις ACCD16 και 3F6E16 τις αντίστοιχες φυσικές. [1.5]
(β) Ποια είναι η λογική διεύθυνση που αντιστοιχεί στη φυσική διεύθυνση 3E5916; [1.5]
Καλή Επιτυχία!!!
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-09-a¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Ακμές του γράφου: Ε1→Ε3, Ε3→Ε4, Ε4→Ε5, Ε2→Ε5, Ε5→Ε8, Ε6→Ε8, Ε7→Ε8. Μία δυαδική σημαφόρος (αρχική τιμή 0) ανά ακμή που ενώνει διαφορετικά νήματα εκτέλεσης: \(s_{45}\) (Ε4→Ε5), \(s_{25}\) (Ε2→Ε5), \(s_{58}\), \(s_{68}\), \(s_{78}\). Οι αλυσίδες Ε1→Ε3→Ε4 και Ε5→Ε8 εκτελούνται σειριακά μέσα στην ίδια διεργασία, άρα δεν χρειάζονται σημαφόρους.
semaphore s45=0, s25=0, s58=0, s68=0, s78=0;
cobegin
begin E1; E3; E4; V(s45); end
begin E2; V(s25); end
begin P(s45); P(s25); E5; V(s58); end
begin E6; V(s68); end
begin E7; V(s78); end
begin P(s58); P(s68); P(s78); E8; end
coend
Έτσι η Ε5 ξεκινά μόνο μετά τις Ε4 και Ε2 και η Ε8 μόνο μετά τις Ε5, Ε6, Ε7. (Δεκτή είναι και η εκδοχή με μία σημαφόρο ανά ακμή.)
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
(α) SJF (μη προεκχωρητικός). Τη στιγμή 0 είναι έτοιμες οι Α (6) και Β (4) → τρέχει η Β. Στο 4 είναι έτοιμες Α(6), Γ(1), Δ(3) → Γ, μετά Δ, μετά Α.
Gantt: | Β 0–4 | Γ 4–5 | Δ 5–8 | Α 8–14 |
Χρόνοι διεκπεραίωσης (finish − άφιξη): Β=4, Γ=5−2=3, Δ=8−3=5, Α=14. Μέσος = \(26/4=6{,}5\).
(β) RR, κβάντο 3 (στο 3 η Α που αφήνει την ΚΜΕ μπαίνει πριν τη Δ που καταφθάνει). Ουρά: Α, Β | Γ(2) | Α και Δ(3).
Gantt: | Α 0–3 | Β 3–6 | Γ 6–7 | Α 7–10 | Δ 10–13 | Β 13–14 |
Χρόνοι διεκπεραίωσης: Α=10, Β=14, Γ=7−2=5, Δ=13−3=10. Μέσος = \(39/4=9{,}75\).
(γ) Βελτίωση \(=\dfrac{9{,}75-6{,}5}{9{,}75}=\dfrac{1}{3}\), δηλαδή ≈ 33,3%.
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Λογική διεύθυνση 16 bits, 16 σελίδες → 4 bits αριθμού σελίδας, 12 bits μετατόπιση (σελίδα 4 KB). Αριθμός πλαισίου 3 bits → φυσική διεύθυνση \(3+12=15\) bits.
(α) - \(\text{ACCD}_{16}\): σελίδα \(\text{A}_{16}=10\), bit = I (άκυρη) → σφάλμα σελίδας, δεν υπάρχει φυσική διεύθυνση. - \(\text{3F6E}_{16}\): σελίδα 3 (V, πλαίσιο 000), μετατόπιση \(\text{F6E}\) → φυσική = \(000\,\text{F6E}\) = \(\text{0F6E}_{16}\).
(β) \(\text{3E59}_{16}=011\,1110\,0101\,1001_2\) (15 bits): πλαίσιο \(011_2=3\), μετατόπιση \(\text{E59}\). Το πλαίσιο 3 ανήκει στη σελίδα 5 (εγγραφή 5 → 011, V). Λογική = σελίδα 5, μετατόπιση E59 → \(\text{5E59}_{16}\).