Λειτουργικά Συστήματα — Σεπτέμβριος 2020 (Θέματα 3)

Μεταγραφή από το αρχείο Themata3-OS-Final-Sept-2020.pdf (2 σελίδες), ελεγμένη με τις σελίδες του πρωτοτύπου.

Themata3-OS-Final-Sept-2020.pdf

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

ΛΕΙΤΟΥΡΓΙΚΑ ΣΥΣΤΗΜΑΤΑ 2019-2020 ΕΞΕΤΑΣΕΙΣ ΣΕΠΤΕΜΒΡΙΟΥ 2020 ΔΙΔΑΣΚΟΝΤΕΣ: Σ. ΣΙΟΥΤΑΣ, Χ. ΜΑΚΡΗΣ, Α. ΗΛΙΑΣ ΔΙΑΡΚΕΙΑ:1:30 ΩΡΑ

ΕΡΩΤΗΜΑ 1 [4Μ]

Σε ένα πάρκο δύο διαβάτες βαδίζουν προς την ίδια άκρη μιας γέφυρας, η οποία χωράει δύο άτομα. Καθένας από τους δύο διαβάτες αναπαρίσταται, αντίστοιχα, από τις διαδικασίες Διαβάτης_1 και Διαβάτης_2, ο κώδικας των οποίων εμφανίζεται ακολούθως.

Κάθε διαβάτης πραγματοποιεί τα εξής: (i) βαδίζει μέχρι την άκρη της γέφυρας (αυτό αναπαρίσταται με τη συνάρτηση Βαδίζει_προς_τη_Γέφυρα() στον κώδικα), (ii) αν ο άλλος διαβάτης δεν έχει φτάσει στην άκρη της γέφυρας τότε τον περιμένει εκεί (αυτό αναπαρίσταται από το σημείο ??Περιμένει?? στον κώδικα) και (iii) εισέρχεται και βαδίζει πάνω στη γέφυρα μαζί με τον άλλο διαβάτη (αυτό αναπαρίσταται με τη συνάρτηση Βαδίζει_πάνω_στη_Γέφυρα() στον κώδικα).

Διαβάτης_1	Διαβάτης_2
{	{
Βαδίζει_προς_τη_Γέφυρα();	Βαδίζει_προς_τη_Γέφυρα();
??Περιμένει??	??Περιμένει??
Βαδίζει_πάνω_στη_Γέφυρα();	Βαδίζει_πάνω_στη_Γέφυρα();
}	}

Συμπληρώστε τον κώδικα των δύο ανωτέρω διαδικασιών (στο σημείο ??Περιμένει??) με κατάλληλες εντολές Signal (up / V) και Wait (down / P) σε σημαφόρους που πρέπει να αρχικοποιήσετε κατάλληλα. Θα πρέπει να εξασφαλιστεί ότι οι δύο διαβάτες εισέρχονται και βαδίζουν πάνω στη γέφυρα μόνο όταν και οι δύο έχουν φτάσει στην άκρη της γέφυρας.

ΕΡΩΤΗΜΑ 2 [3Μ]

Θεωρείστε τέσσερις (4) διαδικασίες με χρόνους άφιξης, χρόνους εκτέλεσης και προτεραιότητες όπως φαίνονται στον ακόλουθο πίνακα:

Διαδικασία	Χρόνος Άφιξης	Προτεραιότητα	Χρόνος Εκτέλεσης
P1	0	2	3
Ρ2	1	3	3
Ρ3	4	1	5
Ρ4	5	2	5

Υποθέτοντας ότι ο χρόνος που απαιτείται για κάθε εναλλαγή θέματος (context switch) είναι αμελητέος και πως μεγαλύτερη είναι η προτεραιότητα που αντιστοιχεί στον μικρότερο αριθμό, ποια από τις παρακάτω προτάσεις είναι σωστή;

• [ ] (Α) Ο προεκχωρητικός αλγόριθμος προτεραιοτήτων κατά την \(6^{\eta}\) χρονική στιγμή θα εκτελεί τη διαδικασία P4.

• [ ] (Β) Ο αλγόριθμος χρονοδρομολόγησης SRTF (Shortest-Remaining-Time-First) κατά την \(5^{\eta}\) χρονική στιγμή θα εκτελεί τη διαδικασία P1.

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

Πολυτεχνική Σχολή

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

• [ ] (Γ) Ο αλγόριθμος FIFO (First-In-First-Out) κατά τη χρονική στιγμή 18 θα εκτελεί τη διαδικασία P4

• [ ] (Δ) Ο αλγόριθμος RR (Round-Robin) με κβάντο 2 χρονικές μονάδες κατά την \(3^{\eta}\) χρονική στιγμή θα εκτελεί τη διαδικασία P2.

ΕΡΩΤΗΜΑ 3 [3Μ]

Σε ένα σύστημα ιδεατής μνήμης με Σελιδοποίηση, ο πίνακας σελίδων έχει \(2^{12}\) εγγραφές, το διάστημα των λογικών διευθύνσεων είναι των 32-bits και το διάστημα των φυσικών διευθύνσεων είναι των 24-bits.

Έστω στο παραπάνω σύστημα μία διεργασία η οποίο παράγει τις ακόλουθες λογικές διευθύνσεις (οι διευθύνσεις δίνονται στο δεκαεξαδικό σύστημα):

0072FF12, 3472F112, 3472FF11, 3472FB12, 04721F12, 14721112, 1472FF22, 3471FF12, 0072FF12, 0072FF14, 1072F342, 0472F142, 00721332, 14712212

Βρείτε αρχικά την ακολουθία αναφορών σελίδων (page reference string) της παραπάνω διεργασίας, και στη συνέχεια υπολογίστε (δίνοντας ένα σχετικό πίνακα όπου μετά από κάθε αναφορά θα φαίνονται τα περιεχόμενα των πλαισίων της μνήμης) τα αντίστοιχα σφάλματα σελίδας (page faults) που προκαλούνται για τον αλγόριθμο αντικατάστασης σελίδων LRU (Least Recently Used), αν γνωρίζετε πως για τη συγκεκριμένη διεργασία είναι διαθέσιμα 3 πλαίσια σελίδων (αρχικά όλα άδεια).

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

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2020-09-c

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Ραντεβού (rendezvous) δύο διεργασιών με δύο σημαφόρους, αρχικά 0: \(a\) = «ο Διαβάτης_1 έφτασε», \(b\) = «ο Διαβάτης_2 έφτασε».

semaphore a = 0, b = 0;

Διαβάτης_1                     Διαβάτης_2
Βαδίζει_προς_τη_Γέφυρα();      Βαδίζει_προς_τη_Γέφυρα();
V(a);                          V(b);
P(b);                          P(a);
Βαδίζει_πάνω_στη_Γέφυρα();     Βαδίζει_πάνω_στη_Γέφυρα();

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

Θέμα 2

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Μικρότερος αριθμός = μεγαλύτερη προτεραιότητα.

Προεκχωρητικός προτεραιοτήτων: P1 0–3 (ο P2 με προτ. 3 δεν την προεκχωρεί), P2 3–4, στο 4 έρχεται η P3 (προτ. 1) → P3 4–9, μετά P4 (προτ. 2) 9–14, τέλος P2 14–16. Στο 6 τρέχει η P3 → (Α) λάθος.

SRTF: P1 0–3, P2 3–6 (στο 4 έρχεται P3 με 5 > 2 υπόλοιπο της P2, στο 5 P4 με 5), P3 6–11, P4 11–16. Στο 5 τρέχει η P2 → (Β) λάθος.

FIFO: P1 0–3, P2 3–6, P3 6–11, P4 11–16. Στο 18 δεν τρέχει καμία → (Γ) λάθος.

RR κβάντο 2: P1 0–2, P2 2–4, … Στη στιγμή 3 τρέχει η P2 → (Δ) σωστή (το ίδιο ισχύει όποια σύμβαση ισοπαλίας κι αν επιλεγεί, γιατί στο 2 η P1 προεκχωρείται και η P2 είναι μόνη στην ουρά).

Σωστή η (Δ).

Θέμα 3

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Πίνακας \(2^{12}\) εγγραφές → σελίδα = τα πρώτα 12 bits = τα 3 πρώτα δεκαεξαδικά ψηφία κάθε διεύθυνσης των 32 bits (μετατόπιση 20 bits).

Ακολουθία αναφορών σελίδων (δεκαεξαδικά):

007, 347, 347, 347, 047, 147, 147, 347, 007, 007, 107, 047, 007, 147

LRU με 3 πλαίσια (πρώτο = πιο παλιά χρησιμοποιημένο, F = σφάλμα σελίδας):

#	Αναφορά	Πλαίσια (παλιότερο → νεότερο)
1	007	007	F
2	347	007, 347	F
3	347	007, 347	–
4	347	007, 347	–
5	047	007, 347, 047	F
6	147	347, 047, 147	F (εκτοπίζεται η 007)
7	147	347, 047, 147	–
8	347	047, 147, 347	–
9	007	147, 347, 007	F (εκτοπίζεται η 047)
10	007	147, 347, 007	–
11	107	347, 007, 107	F (εκτοπίζεται η 147)
12	047	007, 107, 047	F (εκτοπίζεται η 347)
13	007	107, 047, 007	–
14	147	047, 007, 147	F (εκτοπίζεται η 107)

Σύνολο σφαλμάτων σελίδας: 8.

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

---

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