Λειτουργικά Συστήματα — Ιανουάριος 2025¶
Μεταγραφή από τις φωτογραφίες IMG-f69f32d5618a43e601647231e11112ab-V.jpg και IMG-eb65e16b0fe7f00f1b27e22933d83545-V.jpg.
IMG-f69f32d5618a43e601647231e11112ab-V.jpg¶
Πολυτεχνική Σχολή
Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών & Πληροφορικής
ΛΕΙΤΟΥΡΓΙΚΑ ΣΥΣΤΗΜΑΤΑ 2024-2025, ΓΡΑΠΤΕΣ ΕΞΕΤΑΣΕΙΣ ΙΑΝΟΥΑΡΙΟΥ 2025¶
ΔΙΔΑΣΚΟΝΤΕΣ: Σ. ΣΙΟΥΤΑΣ, Χ. ΜΑΚΡΗΣ, Π. ΧΑΤΖΗΔΟΥΚΑΣ, Α. ΗΛΙΑΣ
ΘΕΜΑ 1 [2Μ]: (α) Ζητείται να συμπληρώσετε τα σημεία όπου εμφανίζονται '???', στον παρακάτω αλγόριθμο συγχρονισμού Ν διεργασιών Process_Pi (\(1 \le i \le N\)), με τη χρήση της μεθόδου test&set().
Process_Pi
shared boolean lock; /* κοινή μεταβλητή, αρχικά, FALSE */
int tmp; /* τοπική μεταβλητή της εκάστοτε διεργασίας */
repeat
begin
tmp = ???;
while (tmp == ???) do ???;
<κρίσιμο τμήμα>
???;
<μη-κρίσιμο τμήμα>
end
forever;
boolean Test&Set(boolean lock)
shared boolean lock; /* κοινή μεταβλητή, αρχικά, FALSE */
int tmp; /* τοπική μεταβλητή */
begin
??? = lock; lock = ???; return(tmp);
end
Παρατηρήστε ότι η Test&Set() είναι μια σύνθετη εντολή που εκτελεί δύο προσπελάσεις στη διαμοιραζόμενη μεταβλητή lock.
Παρόλα αυτά υποθέτουμε ότι το υλικό υποστηρίζει την ατομική εκτέλεση της εντολής αυτής (π.χ. με χρήση registers).
(β) Ζητείται να συμπληρώσετε τον κώδικα κάθε διεργασίας δίνοντας, στα σημεία όπου εμφανίζονται '?', κατάλληλες εντολές P (ή wait ή down) / V (ή signal ή up) σε σημαφόρους (που πρέπει να αρχικοποιήσετε κατάλληλα) ώστε εξασφαλιστεί ότι κατά την εκτέλεση των διεργασιών θα εμφανίζεται επαναληπτικά η ακολουθία '1 2 3', ως εξής: 1 2 3 1 2 3 1 2 3 ... κοκ...
| Διεργασία P1 | Διεργασία P2 | Διεργασία P3 |
|---|---|---|
| while (TRUE) | while (TRUE) | while (TRUE) |
ΘΕΜΑ 2 [2Μ]: Το παρακάτω πρόγραμμα εκτελείται ακολουθιακά (σειριακά) και περιλαμβάνει επτά εντολές (Ε1, Ε2, ..., Ε7) εκχώρησης τιμής σε μεταβλητές. Κάθε εντολή του προγράμματος εκτελείται ατομικά – αδιαίρετα.
begin
E1: M := (D + E); E2: N := (F - G); E3: P := M * N; E4: Q := A / B;
E5: R := C * P; E6: S := 5 - Q; E7: Z := S + R;
end
Σχεδιάστε τον γράφο προτεραιότητας (precedence graph), που υλοποιεί το πιο πάνω πρόγραμμα με τη μέγιστη δυνατή παραλληλία. Δημιουργήστε επτά θυγατρικές διεργασίες (με χρήση fork()) που να αντιστοιχούν στις παραπάνω επτά εντολές. Συγχρονίστε τις διεργασίες αυτές κατάλληλα, χρησιμοποιώντας εντολές σημαφόρων signal() και wait(). Η γονική διεργασία, θα περιμένει να περατωθούν οι θυγατρικές, για να τυπώσει το τελικό αποτέλεσμα Z.
Καλή Επιτυχία!!!
IMG-eb65e16b0fe7f00f1b27e22933d83545-V.jpg¶
Πολυτεχνική Σχολή
Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών & Πληροφορικής
ΘΕΜΑ 3 [2Μ]: Θεωρήστε ένα σύστημα διαχείρισης μνήμης με τμηματοποίηση (segmentation), και μια διεργασία που έχει τον παρακάτω πίνακα τμημάτων (δίνεται μέρος αυτού – όλοι οι αριθμοί δίνονται στο δεκαεξαδικό σύστημα και τα δεκαδικά ισοδύναμα αυτών μέσα σε παρενθέσεις):
| Αριθμός Τμήματος | Διεύθυνση Βάσης | Μήκος Τμήματος |
|---|---|---|
| ... | ... | ... |
| 4 | 6000 (24576) | 1000 (4096) |
| 5 | 5000 (20480) | 500 (1280) |
| 6 | 55F0 (22000) | 7D0 (2000) |
| ... | ... | ... |
| A (10) | 59D8 (23000) | 100 (256) |
| B (11) | 4A38 (19000) | 7D0 (2000) |
| ... | ... | ... |
| 2001 (8193) | 2001 (8193) | 500 (1280) |
Η λογική διεύθυνση στο σύστημα αυτό έχει εύρος 28 bits και το μέγιστο μέγεθος ενός τμήματος μπορεί να είναι 32KB.
1. Με βάση τα παραπάνω δεδομένα, βρείτε τυχόν λάθη που υπάρχουν στο ανωτέρω απόσπασμα του πίνακα τμημάτων.
2. Βρείτε σε ποια φυσική διεύθυνση αντιστοιχεί η λογική διεύθυνση 2111E16. Η απάντησή σας πρέπει να δοθεί στο δεκαεξαδικό σύστημα.
ΘΕΜΑ 4 [2Μ]: (α) Δίνεται η παρακάτω ουρά (0 – 199) από αιτήσεις Ε/Ε (disk I/O requests):
Queue [0 – 199]: 98, 182, 36, 121, 14, 123, 64, 66 με Head pointer: 52
Δώστε όλα τα ενδιάμεσα βήματα εξυπηρέτησης (servicing) της ουράς, για κάθε έναν από τους παρακάτω αλγορίθμους δρομολόγησης (Disk Scheduling Algorithms): SSTF, SCAN, C-SCAN και C-LOOK.
(β) Περιγράψτε όλα τα ενδιάμεσα βήματα της διαδικασίας pathname translation που εκτελεί ένα σύστημα αρχείων (file system), το οποίο δέχεται σαν είσοδο το pathname ../d1/d2/d3/hash.c και παράγει σαν έξοδο το Inode# του αρχείου hash.c
ΘΕΜΑ 5 [2Μ]: Υπολογίστε τους μέσους χρόνους διεκπεραίωσης (ΜΧΔ) και αναμονής (ΜΧΑ) για τους αλγορίθμους χρονοδρομολόγησης: (α) PP(Preemptive-Priority: προεκχωρητικός αλγόριθμος προτεραιότητας βάσει αύξουσας τιμής), με χρήση αλγορίθμου FCFS στις περιπτώσεις που έχουμε ίσες προτεραιότητες (β) RR (Round Robin) με κβάντο χρόνου 8 χρονικές μονάδες. Θεωρήστε πως αν τη χρονική στιγμή που μια νέα διεργασία έρχεται στο σύστημα, διακόπτεται η εκτέλεση μιας διεργασίας (γιατί τελειώνει το κβάντο χρόνου της), τότε η νέα διεργασία εισέρχεται πριν από αυτήν που διακόπτεται στην ουρά των έτοιμων διεργασιών. (Σημ.: Θεωρήστε το χρόνο εναλλαγής (context switch) αμελητέο. Επίσης η σχεδίαση διαγραμμάτων Gantt θα σας βοηθούσε...).
| Όνομα Διεργασίας | Χρονική Στιγμή Άφιξης | Απαιτήσεις Χρόνου Εκτέλεσης | Προτεραιότητα |
|---|---|---|---|
| P1 | 0 | 12 | 3 |
| P2 | 5 | 19 | 3 |
| P3 | 8 | 21 | 5 |
| P4 | 11 | 13 | 2 |
| P5 | 15 | 15 | 3 |
Καλή Επιτυχία!!!
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2025-01.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):IMG_20260120_115021.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία λύσης φοιτητή (Ιανουάριος 2026)
Προσοχή
Η λύση διασπά τη λογική διεύθυνση 2111E16 σε s = 4 και d = 111E (20 bit)· η εκφώνηση αναφέρει λογική διεύθυνση 28 bit, άρα η διάσπαση πρέπει να ελεγχθεί. Η λύση δίνει παγίδευση (trap) επειδή d > 1000_16 για το τμήμα 4· συνεπές με τον πίνακα τμημάτων της εκφώνησης (6000_16, μέγιστο 1000_16).
Λύσεις — Λειτουργικά Συστήματα — Ιανουάριος 2025 (Θέμα 3)¶
IMG_20260120_115021.jpg¶
Πολυτεχνική Σχολή
Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών & Πληροφορικής
α) Κατ' αρχάς μετατρέπεται η λογική διεύθυνση 2111E στο δυαδικό σύστημα και υπολογίζεται το \(s\) και το \(d\)
Το \(s = 0010\ 0 = 4\) και το \(d = 001\ 0001\ 0001\ 1110 = 111\text{E}\)
Από τον πίνακα τμημάτων βλέπουμε πως το τμήμα 4 αρχίζει από τη φυσική διεύθυνση \(6000_{16}\) και έχει μέγιστο μέγεθος \(1000_{16}\).
Το \(d = 111\text{E} > 1000\) και επομένως υπάρχει λάθος διευθυνσιοδότησης και γίνεται παγίδευση (trap) στο ΛΣ.