Λειτουργικά Συστήματα — Ιανουάριος 2022

Μεταγραφή από τις φωτογραφίες IMG_20220126_121626.jpg και IMG_20220126_121636.jpg.

IMG_20220126_121626.jpg

Τετάρτη, 26/01/2022
12:00-15:00
Διάρκεια Εξέτασης: 2 Ώρες

ΘΕΜΑ 1 (2 μονάδες)
Σε μια εστία προσέρχονται οι ένοικοι στο εστιατόριο για το γεύμα και κάθονται γύρω από ένα μοναδικό και μεγάλο τραπέζι. Όποιος πεινάει βάζει στο πιάτο του μια μερίδα φαγητό από μια μεγάλη κατσαρόλα προετοιμασίας του φαγητού και σερβιρίσματος η οποία είναι τοποθετημένη στο κέντρο του τραπεζιού και από τους συνδαιτημόνες, μόνο ένας μπορεί να σερβίρεται κάθε φορά. Η κατσαρόλα αυτή χωράει μέχρι \(X+5\) μερίδες φαγητό. Εάν η κατσαρόλα αδειάσει ενημερώνεται ο μάγειρας να ετοιμάσει πάλι φαγητό και για να γεμίσει η κατσαρόλα χρειάζεται \(Y+3\) κιλά φασόλια και \(Y\) κιλά καρότα και στην κουζίνα δεν έχει απόθεμα των υλικών, τα οποία πρέπει να έρθουν από την κατάλληλη- για κάθε υλικό- αποθήκη της εστίας. Ο μάγειρας έχει δυο βοηθούς, καθένας από τους οποίους ενημερώνεται να πάει σε διαφορετική αποθήκη για να φέρει τα υλικά που χρειάζονται για το μαγείρεμα και κάθε βοηθός μπορεί να μεταφέρει από την αποθήκη ευθύνης του μέχρι \(Y\) κιλά υλικών, ενώ η κάθε αποθήκη έχει απεριόριστη ποσότητα από κάθε υλικό. Ο μάγειρας για να ετοιμάσει το φαγητό πρέπει να έχει όλα τα υλικά για να γεμίσει η κατσαρόλα και μέχρι να συγκεντρωθούν τα υλικά αυτά περιμένει.

Να γράψετε ψευδοκώδικα που να υλοποιεί και να συγχρονίζει τη διαδικασία εστίασης που περιγράφηκε για τους σητιζόμενους, τη δουλειά του μάγειρα και των βοηθών του.

Ο αριθμός \(X\) αντιστοιχεί στο τελευταίο ψηφίο του επταψήφιου (νέου για τους παλιούς φοιτητές) αριθμού μητρώου σας και ο \(Y\) στο τρίτο από δεξιά προς τα αριστερά ψηφίο, δηλαδή εάν έχετε ΑΜ [αφαιρέθηκε] τότε \(X=7\) και \(Y=5\) (1234Y6X).

Υπόδειγμα: Θα υλοποιήσετε τόσες διεργασίες όσες είναι οι οντότητες που συμμετέχουν στην εστίαση για να ολοκληρωθεί σωστά. Εντός των διεργασιών, η συνάρτηση που υλοποιεί το σερβίρισμα κάθε συνδαιτημόνα θα ονομάζεται take_food(), η συνάρτηση για το μαγείρεμα θα ονομάζεται cook_food(), και για τη μεταφορά των υλικών από τους βοηθούς helper(), και θα τις καλείτε μέσα από τις διεργασίες χωρίς να χρειάζεται να υλοποιήσετε το περιεχόμενο της.

ΘΕΜΑ 2 (3 μονάδες)
Θεωρούμε έναν αλγόριθμο χρονοδρομολόγησης διεργασιών, ο οποίος θα εξυπηρετεί πρώτες αυτές με το μεγαλύτερο χρόνο που απομένει με προεκχώρηση. Η προεκχώρηση πραγματοποιείται λαμβάνοντας υπόψη τις προτεραιότητες που έχουν οι διεργασίες. Τον αλγόριθμο τον ονομάζουμε Longest Remaining Time First Preemptive- LRTFP. Ο αλγόριθμος εξετάζει το LRTF για την προεκχώρηση και έπειτα ενεργοποιείται η προτεραιότητα εφόσον χρειάζεται δίνοντας προτεραιότητα στη διαδικασία με το μικρότερο αναγνωριστικό διεργασίας (PID- Process ID).

Δίνονται πέντε διεργασίες προς εκτέλεση με τον LRTFP, των οποίων τα δεδομένα είναι αυτά που φαίνονται στον ακόλουθο πίνακα:

Διεργασία	Χρόνος Άφιξης	Διάρκεια	PID
Α	0	8	3
Β	3	4	1
Γ	4	4	2
Δ	5	5	5
Ε	7	7	4

1. Ποια θα είναι η σειρά ολοκλήρωσης των διεργασιών; (0,5 Μονάδα)
2. Σε ποια χρονική στιγμή θα ολοκληρωθεί η εκτέλεση και των πέντε διεργασιών; (0,5 Μονάδα)
3. Υπολογίστε

Καλή Επιτυχία!

IMG_20220126_121636.jpg

[Λείπει από τη φωτογραφία: επάνω μέρος κεφαλίδας («Πολυτεχνική Σχολή»)]

Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών & Πληροφορικής

i. το μέσο χρόνο αναμονής (0,5 Μονάδα)
ii. μέσο χρόνο απόκρισης (0,5 Μονάδα)
iii. μέσο χρόνο ολοκλήρωσης (0,5 Μονάδα) και
iv. το πλήθος των θεματικών εναλλαγών των διεργασιών. (0,5 Μονάδα)

Θεωρήστε αμελητέο το χρόνο θεματικών εναλλαγών (context switch).

ΘΕΜΑ 3 (2,5 μονάδες)

Σε ένα σύστημα με σελιδοποιημένη μνήμη θεωρήστε μέγεθος σελίδας 32 KB. Η φυσική μνήμη αποτελείται από 4096 πλαίσια σελίδων ενώ ο πίνακας σελίδων μιας διεργασίας αποτελείται από 2048 εισόδους (δηλαδή γραμμές). Έστω επίσης το ακόλουθο τμήμα του πίνακα σελίδων μιας διεργασίας (όλοι οι αριθμοί του πίνακα δίνονται στο δεκαεξαδικό σύστημα).

Αριθμός Σελίδας	Αριθμός Πλαισίου	V/I
…	…	…
303	12	1
410	1B	1
54D	A1	0
…	…	…

(i) Βρείτε τη δομή της λογικής και της φυσικής διεύθυνσης του συγκεκριμένου συστήματος σελιδοποίησης (πρέπει να βρείτε αρχικά το μέγεθος (σε bits) του «αριθμού σελίδας» (p), της «μετατόπισης σελίδας» (d) και του «αριθμού πλαισίου» (f), και με βάση αυτά να απαντήσετε στη συνέχεια το ζητούμενο). (1,5 Μονάδες)

(ii) Έστω η λογική διεύθυνση 18193FF16. Σε ποια φυσική διεύθυνση αντιστοιχεί; (δώστε την απάντηση σας στο δεκαεξαδικό σύστημα) (1 Μονάδα)

ΘΕΜΑ 4 (2,5 μονάδες)

Έστω οι παρακάτω δύο διεργασίες Α και Β, οι οποίες εκτελούνται «παράλληλα» (δηλ. εκτελούνται με βάση το σχήμα "cobegin A; B; coend"). Στον κώδικα της κάθε διεργασίας κάθε εντολή εκχώρησης τιμής (:=) εκτελείται ατομικά - αδιαίρετα. Οι X, Y, Z είναι ακέραιες μεταβλητές, κοινές και για τις δύο διεργασίες, και η αρχική τιμή της μεταβλητής X είναι ίση με 10.

Διεργασία A	Διεργασία B
Y := X + 1;	Z := X * 2;
X := Y;	X := Z;

(i) Με βάση την «παράλληλη» εκτέλεση των διεργασιών Α και Β, προκύπτει ένα σύνολο δυνατών ακολουθιών εκτέλεσης (αναμείξεις) των εντολών τους. Να δώσετε κάθε δυνατή τιμή που λαμβάνει τελικά η μεταβλητή X μετά το τέλος κάθε ακολουθίας εκτέλεσης των εντολών των διεργασιών. (1,5 Μονάδες)

(ii) Να χρησιμοποιήσετε δυαδικούς σημαφόρους (αρχικοποιώντας τους κατάλληλα) και να συμπληρώσετε με εντολές σημαφόρων (εντολές P (ή wait ή down) και V (ή signal ή up)) τον παραπάνω κώδικα των διεργασιών Α και Β, ώστε να εξασφαλίζεται ότι, στο τέλος της παράλληλης εκτέλεσης των διεργασιών, οι μόνες δυνατές τελικές τιμές που λαμβάνει η μεταβλητή X είναι είτε το 21, είτε το 22. (1 Μονάδα)

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2022-01.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): 2022_2.jpg, 863.png, 20230129_130729.jpg, 20230129_133050.jpg, IMG_7433.png, Screenshot_2022-09-01-11-18-19-22_be80aec1db9a2b53c9d399db0c602181.jpg

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: φωτογραφίες λύσεων φοιτητών (χειρόγραφες/στιγμιότυπα από Discord)

Προσοχή

Θέμα 2 (LRTFP): ο πίνακας της φωτογραφίας 20230129_130729.jpg δίνει διεργασία Ε με PID 5 ενώ το θέμα έχει PID 4 για την Ε· να ελεγχθεί. Θέμα 1 (συγχρονισμός εστίας): οι δύο λύσεις χρησιμοποιούν διαφορετικές τιμές για τα όρια (7 καρότα/10 φασόλια και 6/9)· πιθανώς αντιστοιχούν σε διαφορετικά δεδομένα ανά ομάδα/ΑΜ και δεν αποτελούν αντίφαση, αλλά δεν επαληθεύτηκαν. Η φωτογραφία 20230129_133050.jpg περιέχει χειρόγραφες απαντήσεις φοιτητή που δεν μεταγράφηκαν· η ενότητα περιέχει μόνο σημείωση.

Λύσεις — Λειτουργικά Συστήματα — Ιανουάριος 2022

Ανεπίσημες λύσεις φοιτητών, όπως συλλέχθηκαν· δεν έχουν ελεγχθεί από το διδακτικό προσωπικό. Κάθε φωτογραφία αντιστοιχεί σε ένα θέμα της εξέτασης.

20230129_130729.jpg

Διεργ.	Χρ. αφ.	Διαρκ.	PID
A	0	8	3
B	3	4	1
Γ	4	4	2
Δ	5	5

IMG_7433.png

var fasolia,karota,merides:shared integer; var s1,s2,s3,s4: semaphores; begin karota=fasolia=merides=0; s2=s3=s4=0; s1=1; Cobegin process servirisma repeat down(s1); if(merides>0) {take_food(); merides=merides-1; up(s1);} else{up(s2);}//semaphore mageira forever

process mageiras repeat down(s2); up(s3);up(s4);//semaphores voithwn while(!(karota==7 and fasolia==10)) {wait();} cook_food(); up(s1); forever

process voithos1 repeat down(s3); while(karota<7) {helper();} forever

process voithos2 repeat down(s4); while(fasolia<10) {helper();} forever

coend; end

Screenshot_2022-09-01-11-18-19-22_be80aec1db9a2b53c9d399db0c602181.jpg

\[S1=1;$$ $$\text{help}=\text{cook}=0$$ $$\text{καρότα}=\text{φασόλια}=1\]

| συνδειτήμονας |

down(S1);
if( food > 0)
    take_food();
    food--;
    UP(S1);
else
    UP(cook);

| μάγειρας |

down(cook);
if (καρότα==6 && φασόλια==9)
    cook_food();
    UP(S1);
else
    UP(help);

| βοηθός |

```c down(help); if (καρότα < 6) down(καρότα); helper(); UP(καρότα); else if (φασόλια < 9) down(φασόλια) helper(); UP(φασόλια); else UP(cook);

20230129_133050.jpg

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

---

✖ Βρήκα λάθος στη μεταγραφή