Λειτουργικά Συστήματα — Αύγουστος 2022 (Θέμα 3)¶
Μεταγραφή από τη φωτογραφία 2022-08-18_5.png.
2022-08-18_5.png¶
Πολυτεχνική Σχολή
Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών & Πληροφορικής
ΘΕΜΑ 3 [4M]
(α) Κατασκευάστε ένα σκαρίφημα του τρόπου με τον οποίο ένα λειτουργικό σύστημα που μπορεί να απενεργοποιεί τις διακοπές θα μπορούσε να υλοποιήσει τις σηματοφόρους.
(β) Υποθέστε ότι έχουμε τρεις εργασίες A, B, C, με την A να απαιτεί 10 λεπτά χρόνου CPU, την B 13 λεπτά χρόνου CPU, και την C 15 λεπτά χρόνου CPU και οι οποίες ξεκινούν ταυτόχρονα. Πόσο θα χρειαστεί η τελευταία για να ολοκληρωθεί αν εκτελεστούν σειριακά; Πόσο θα χρειαστεί αν εκτελεστούν παράλληλα; Υποθέστε ότι η A έχει 20% αναμονή χρόνου για E/E, η B 25% αναμονή χρόνου για E/E και η Γ 30% αναμονή χρόνου για E/E.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2022-08.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):Screenshot_33.png,gttttttttttttttttttt.png,IMG_7437.png
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2022-08¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
(α) Υλοποίηση σημαφόρων με απενεργοποίηση διακοπών. Η σημαφόρος είναι δομή με μετρητή και ουρά αναμονής. Οι πράξεις P και V πρέπει να είναι ατομικές, άρα εκτελούνται ως κρίσιμη περιοχή του πυρήνα με απενεργοποιημένες διακοπές (σε μονοεπεξεργαστή· σε πολυεπεξεργαστή απαιτείται επιπλέον spinlock/TSL).
struct semaphore { int value; queue Q; };
P(S): V(S):
disable_interrupts(); disable_interrupts();
S.value--; S.value++;
if (S.value < 0) { if (S.value <= 0) {
put current process in S.Q; remove a process p from S.Q;
block(); /* scheduler */ wakeup(p); /* -> ready queue */
} }
enable_interrupts(); enable_interrupts();
(Όταν ο scheduler εκτελεί άλλη διεργασία μετά το block, οι διακοπές ξανα-ενεργοποιούνται από τη διεργασία που θα τρέξει.) Η περιοχή με απενεργοποιημένες διακοπές είναι πολύ σύντομη, ώστε να μη χαθούν διακοπές.
(β) Υποθέσεις (η εκφώνηση είναι ασαφής): οι 10, 13, 15 λεπτά είναι καθαρός χρόνος CPU· το ποσοστό E/E είναι το ποσοστό του χρόνου που η εργασία περιμένει για E/E όταν τρέχει μόνη της (η Γ ≡ C).
Σειριακά: κάθε εργασία διαρκεί CPU/(1−p): A: \(10/0{,}8=12{,}5\), B: \(13/0{,}75=17{,}33\), C: \(15/0{,}7=21{,}43\) λεπτά. Η τελευταία (C) τελειώνει μετά ≈ 51,3 λεπτά (σύνολο).
Παράλληλα (πολυπρογραμματισμός): χρησιμοποιώ το απλό πιθανοτικό μοντέλο χρήσης ΚΜΕ \(1-\prod p_i\), με την ΚΜΕ να μοιράζεται ανάλογα με το \((1-p_i)\) των ενεργών εργασιών (προσέγγιση, όχι ακριβής λύση): - και οι 3 ενεργές: χρήση \(1-0{,}2\cdot0{,}25\cdot0{,}3=98{,}5\%\) → η A τελειώνει στα ≈ 28,6 λεπτά· - B, C: χρήση \(1-0{,}25\cdot0{,}3=92{,}5\%\) → η B τελειώνει στα ≈ 36,1· - μόνο η C: χρήση 70% → τελειώνει στα ≈ 40,2 λεπτά.
Άρα παράλληλα ≈ 40 λεπτά για την τελευταία (έναντι ≈ 51 σειριακά). Η τιμή εξαρτάται από το μοντέλο· αν ο διδάσκων περιμένει άλλο μοντέλο, η λογική (σειριακά: άθροισμα CPU/(1−p), παράλληλα: επικάλυψη E/E με την ΚΜΕ) παραμένει, οι αριθμοί μπορεί να διαφέρουν.