Μετάβαση στο περιεχόμενο

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

Μεταγραφή από τις φωτογραφίες IMG_20260122_152138_386.jpg (σελ. 1) και IMG_20260122_152140_456.jpg (σελ. 2).

IMG_20260122_152138_386.jpg

ΘΕΜΑ 1 [2Μ]: Εξηγείστε τι κάνουν οι 2 παρακάτω κώδικες. Ποιο είναι το βασικό σημείο στο οποίο διαφέρουν?

Κώδικας 1 (αριστερά):

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void)
{
    int i, tmp;

    pid_t pid[4];

    for (i=0; i<4; i++) {
        pid[i] = fork();
        if (pid[i] == 0) {
            break;
        }
    }

    if (pid[0] != 0 && pid[1] != 0 && pid[2] != 0 && pid[3] != 0) {
        // That's the father, it waits for all the childs
        printf("I'm the father [pid: %d, ppid: %d]\n", getpid(), getppid());
        for(i=0; i<4; i++) {
            wait(&tmp);
        }
    } else {
        // That's the child, it print its pid, its parent pid and exits
        printf("I'm one of the children [pid: %d, ppid: %d]\n", getpid(), getppid());
    }

    return 0;
}

Κώδικας 2 (δεξιά):

#include <stdio.h>
#include <stdlib.h>

#define N 4

int main()
{
    int i;
    int pid;

    for (i=0; i<N; i++)
    {
        pid = fork();
        if (pid > 0)
        {
            printf(" Father = %5i, Id = %5i\nChild = %5i\n", getppid(), getpid(), pid);
            wait(NULL);
            break;
        }
    }

    return (0);
}

[δυσανάγνωστο: τμήματα του κώδικα 2 (π.χ. η γραμμή printf και η ακριβής μορφή των #include) — η φωτογραφία είναι θολή· η μεταγραφή είναι ενδεικτική των διαφορών.]

ΘΕΜΑ 2 [2Μ]:

binary semaphore S1, S2, S3;
S1 = ?;
S2 = ?;
S3 = ?;

Διεργασία Δ1 Διεργασία Δ2 Διεργασία Δ3
begin begin begin
?? ?? ??
print("Β"); print("Α"); print("Δ");
?? ?? ??
print("Γ"); print("Ζ"); print("Ε");
?? ?? ??
end end end

Έστω τρεις διεργασίες, Δ1, Δ2 και Δ3, που εκτελούνται «παράλληλα», δηλ. εκτελούνται σύμφωνα με το σχήμα εκτέλεσης "cobegin Δ1; Δ2; Δ3; coend". Η διεργασία Δ1 εκτυπώνει αρχικά το γράμμα "Β" και μετά το γράμμα "Γ". Η διεργασία Δ2 εκτυπώνει αρχικά το γράμμα "Α" και μετά το γράμμα "Ζ". Η διεργασία Δ3 εκτυπώνει αρχικά το γράμμα "Δ" και μετά το γράμμα "Ε".

[Λείπει από τη φωτογραφία: η παράγραφος με την ζητούμενη τελική έξοδο ("ΑΒΓΔΕΖ") και η σημείωση για τα σημεία με «??».]

IMG_20260122_152140_456.jpg

ΘΕΜΑ 3 [2Μ]: Πέντε διεργασίες εισέρχονται σε ένα υπολογιστικό σύστημα με χρόνους άφιξης και εκτέλεσης οι οποίοι παρατίθενται στον παρακάτω πίνακα της επόμενης σελίδας (σε msec):

(i) Έστω ότι χρησιμοποιείται ο αλγόριθμος RR (Round Robin) με κβάντο χρόνου 8ms. Σχεδιάστε το διάγραμμα Gantt που αντιστοιχεί στην εκτέλεση των ανωτέρω διεργασιών στην ΚΜΕ και υπολογίστε το Χρόνο Αναμονής (ΧΑ) για τη διεργασία P5.

(ii) Σχεδιάστε ξανά το διάγραμμα Gantt για την εκτέλεση των ανωτέρω διεργασιών, υποθέτοντας τώρα ότι χρησιμοποιείται ο αλγόριθμος SRTF (Shortest Remaining Time First), και υπολογίστε εκ νέου το Χρόνο Αναμονής (ΧΑ) για τη διεργασία P5.

Σημείωση: Και για τους δύο αλγόριθμους θεωρήστε πως ο χρόνος εναλλαγής είναι αμελητέος.

Διεργασία Χρόνος Άφιξης Χρόνος Εκτέλεσης
\(\text{P}_1\) 0 25
\(\text{P}_2\) 4 12
\(\text{P}_3\) 7 8
\(\text{P}_4\) 10 15
\(\text{P}_5\) 12 10

ΘΕΜΑ 4 [2Μ]: Θεωρείστε ένα σύστημα διαχείρισης μνήμης με Σελιδοποίηση (Paging), στο οποίο κάθε διεργασία μπορεί να έχει 32 σελίδες λογικής μνήμης. Μια διεργασία που εκτελείται στο σύστημα διαθέτει τον παρακάτω πίνακα σελίδων (όλοι οι αριθμοί είναι εκφρασμένοι στο δεκαδικό σύστημα):

Αριθμός Σελίδας Αριθμός Πλαισίου Έγκυρο/ Άκυρο bit
0 4 0
... ... ...
7 15 1
... ... ...
[δυσανάγνωστο] [δυσανάγνωστο] [δυσανάγνωστο]
... ... ...
31 [δυσανάγνωστο] 0

Γνωρίζοντας πως το μέγεθος σελίδας στο παραπάνω σύστημα είναι 1024 bytes, ποια από τις παρακάτω προτάσεις είναι σωστή;

  • [ ] (Α) Με 14 bits καλύπτεται το εύρος των λογικών διευθύνσεων της συγκεκριμένης διεργασίας.
  • [ ] (Β) Η λογική διεύθυνση \(\text{FFFF}_{16}\) (στο δεκαεξαδικό σύστημα) είναι μια έγκυρη λογική διεύθυνση της συγκεκριμένης διεργασίας, σύμφωνα με τα ανωτέρω δεδομένα.
  • [ ] (Γ) Η λογική διεύθυνση \(\text{3CCC}_{16}\) (στο δεκαεξαδικό σύστημα) της συγκεκριμένης διεργασίας αντιστοιχεί στη φυσική διεύθυνση \(\text{9CCC}_{16}\) (στο δεκαεξαδικό σύστημα).
  • [ ] (Δ) Η λογική διεύθυνση \(\text{7CCC}_{16}\) (στο δεκαεξαδικό σύστημα) αναφέρεται σε μία σελίδα της συγκεκριμένης διεργασίας, η οποία δεν είναι φορτωμένη στη φυσική μνήμη του συστήματος.

ΘΕΜΑ 5 [2Μ]: (α) Αναπτύξτε σε ψευδοκώδικα τον αλγόριθμο του Lamport για τον συγχρονισμό [δυσανάγνωστο] διεργασιών. (β) Περιγράψτε τα ενδιάμεσα βήματα της διαδικασίας pathname translation που εκτελεί ένα σύστημα αρχείων (file system), το οποίο δέχεται σαν είσοδο το pathname /Users/[όνομα]/os/mmap.c και παράγει σαν έξοδο το inode# του αρχείου mmap.

Σημείωση: το όνομα χρήστη στο pathname έχει αντικατασταθεί με [όνομα].

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

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

Προσοχή

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

AI λύσεις — 2026-01

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

Θέμα 1

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα IMG_20260122_152138_386.jpg ο κώδικας 2 διαβάζεται καθαρά: περιέχει if (pid > 0) { ... wait(NULL); break; }.

Τι κάνει ο Κώδικας 1 (αριστερά): - Ο αρχικός πατέρας εκτελεί έναν βρόχο 4 επαναλήψεων (\(i=0, 1, 2, 3\)). Σε κάθε επανάληψη καλεί την fork(). - Αν pid[i] == 0 (το παιδί), εκτελεί break και βγαίνει αμέσως από τον βρόχο χωρίς να καλέσει άλλες fork(). - Μόνο ο αρχικός γονέας συνεχίζει στον βρόχο και δημιουργεί συνολικά 4 παιδιά. - Ο γονέας εκτυπώνει το μήνυμά του και εκτελεί 4 φορές την wait(&tmp), περιμένοντας όλα τα παιδιά του να τερματίσουν. Κάθε παιδί εκτυπώνει το pid του και το ppid του και τερματίζει. - Συνολικά δημιουργούνται 5 διεργασίες σε αστεροειδή ιεραρχία («βεντάλια»): 1 κοινός πατέρας με 4 αδέλφια-παιδιά που εκτελούνται παράλληλα.

Τι κάνει ο Κώδικας 2 (δεξιά): - Ο αρχικός γονέας καλεί την fork() στο \(i=0\) και δημιουργεί ένα παιδί (\(P_1\)). - Επειδή για τον γονέα ισχύει pid > 0, εκτυπώνει τα στοιχεία (Father = ..., Id = ..., Child = ...), καλεί wait(NULL) περιμένοντας το παιδί του και κάνει break τερματίζοντας τον βρόχο. - Το παιδί \(P_1\) έχει pid == 0, οπότε δεν μπαίνει στο if (pid > 0) και συνεχίζει στην επόμενη επανάληψη του βρόχου (\(i=1\)), όπου καλεί το ίδιο fork() δημιουργώντας ένα εγγόνι (\(P_2\)), εκτυπώνει, κάνει wait(NULL) και break. - Η διαδικασία αυτή επαναλαμβάνεται διαδοχικά για \(N=4\) φορές. - Συνολικά δημιουργούνται 5 διεργασίες σε γραμμική ιεραρχία (αλυσίδα διαδοχικών γενεών): \(P_0 \to P_1 \to P_2 \to P_3 \to P_4\).

Βασικό σημείο στο οποίο διαφέρουν: Το βασικό σημείο διαφοράς είναι η δομή/ιεραρχία των παραγόμενων διεργασιών: - Στον Κώδικα 1 το break εκτελείται από τα παιδιά (if (pid[i] == 0) break), με αποτέλεσμα ο ίδιος αρχικός γονέας να γεννά και τα 4 παιδιά (παράλληλη / αστεροειδής ιεραρχία 1 επιπέδου). - Στον Κώδικα 2 το break εκτελείται από τον εκάστοτε γονέα (if (pid > 0) break), ενώ το παιδί συνεχίζει τον βρόχο, με αποτέλεσμα κάθε διεργασία να γεννά μόνο 1 απόγονο (γραμμική ιεραρχία / αλυσίδα διεργασιών: πατέρας \(\to\) παιδί \(\to\) εγγονός \(\to\) δισέγγονος \(\to\) τρισέγγονος).

Θέμα 2

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στη φωτογραφία IMG_20260122_152138_386.jpg δεν φαίνεται το κείμενο κάτω από το πλαίσιο, ωστόσο η άσκηση είναι πανομοιότυπη με το Θέμα 1 της εξέτασης Σεπτεμβρίου 2025 (2025-09.md), όπου ζητείται η εκτύπωση των γραμμάτων σε αλφαβητική σειρά: "ΑΒΓΔΕΖ".

Τα γράμματα εκτυπώνονται από τις διεργασίες ως εξής: - \(\Delta_2\): εκτυπώνει "Α" και μετά "Ζ" - \(\Delta_1\): εκτυπώνει "Β" και μετά "Γ" - \(\Delta_3\): εκτυπώνει "Δ" και μετά "Ε"

Για να εξασφαλιστεί η αυστηρή αλφαβητική σειρά Α \(\to\) Β \(\to\) Γ \(\to\) Δ \(\to\) Ε \(\to\) Ζ: 1. Πρώτη πρέπει να εκτυπώσει η \(\Delta_2\) το "Α" (ξεκινά χωρίς αναμονή). 2. Μετά το "Α", η \(\Delta_2\) πρέπει να επιτρέψει στη \(\Delta_1\) να εκτυπώσει το "Β". Χρησιμοποιούμε σημαφόρο \(S_1\) με αρχική τιμή 0. 3. Η \(\Delta_1\) εκτυπώνει "Β" και αμέσως μετά "Γ". 4. Μετά το "Γ", η \(\Delta_1\) πρέπει να επιτρέψει στη \(\Delta_3\) να εκτυπώσει το "Δ". Χρησιμοποιούμε σημαφόρο \(S_2\) με αρχική τιμή 0. 5. Η \(\Delta_3\) εκτυπώνει "Δ" και αμέσως μετά "Ε". 6. Μετά το "Ε", η \(\Delta_3\) πρέπει να επιτρέψει στη \(\Delta_2\) να εκτυπώσει το "Ζ". Χρησιμοποιούμε σημαφόρο \(S_3\) με αρχική τιμή 0.

Αρχικοποίηση σημαφόρων: 

S1 = 0;
S2 = 0;
S3 = 0;

Συμπλήρωση κώδικα:

Διεργασία Δ1 Διεργασία Δ2 Διεργασία Δ3
begin begin begin
P(S1); P(S2);
print("Β"); print("Α"); print("Δ");
V(S1); P(S3);
print("Γ"); print("Ζ"); print("Ε");
V(S2); V(S3);
end end end

(Στα κενά κελιά δεν απαιτείται καμία εντολή σημαφόρου).

Θέμα 3

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Ίδια δεδομένα με πέντε διεργασίες (P1: 0/25, P2: 4/12, P3: 7/8, P4: 10/15, P5: 12/10).

(i) RR, κβάντο 8: | P1 0–8 | P2 8–16 | P3 16–24 | P1 24–32 | P4 32–40 | P5 40–48 | P2 48–52 | P1 52–60 | P4 60–67 | P5 67–69 | P1 69–70 |

Ουρά όταν η P2 προεκχωρείται στο 16: P3, P1, P4, P5, P2 (οι P4, P5 είχαν φτάσει νωρίτερα). Η P5 τελειώνει στο 69: ΧΑ \(=69-12-10=\) 47 ms (28 + 19). Το αποτέλεσμα είναι ίδιο όποια σύμβαση ισοπαλίας κι αν χρησιμοποιηθεί.

(ii) SRTF: | P1 0–4 | P2 4–7 | P3 7–15 | P2 15–24 | P5 24–34 | P4 34–49 | P1 49–70 |

ΧΑ(P5) \(=24-12=\) 12 ms.

Θέμα 4

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα IMG_20260122_152140_456.jpg ο πίνακας σελίδων διαβάζεται καθαρά (επιβεβαιώνεται και από την ταυτόσημη άσκηση του Σεπτεμβρίου 2025): - Σελίδα 0: Πλαίσιο 4, Bit = 0 - Σελίδα 7: Πλαίσιο 15, Bit = 1 - Σελίδα 15: Πλαίσιο 9, Bit = 1 - Σελίδα 31: Πλαίσιο 15, Bit = 0

Δεδομένα: - 32 σελίδες λογικής μνήμης \(\implies 2^5 = 32\), άρα απαιτούνται 5 bits για τον αριθμό σελίδας (\(p \in [0, 31]\)). - Μέγεθος σελίδας \(1024\text{ bytes} = 2^{10}\text{ bytes} \implies\) απαιτούνται 10 bits για το offset (\(d \in [0, 1023]\)). - Συνολικό μέγεθος λογικής διεύθυνσης: \(5 + 10 = 15\text{ bits}\). - Εύρος έγκυρων λογικών διευθύνσεων: \(0\) έως \(2^{15} - 1 = 32767 = \text{7FFF}_{16}\).

Έλεγχος των προτάσεων: - (Α) Λάθος: Με 14 bits καλύπτονται \(2^{14} = 16384\text{ bytes}\) (16 σελίδες), ενώ η διεργασία έχει 32 σελίδες και απαιτεί 15 bits. - (Β) Λάθος: Η διεύθυνση \(\text{FFFF}_{16} = 65535\) αντιστοιχεί στη σελίδα \(\lfloor 65535 / 1024 \rfloor = 63\), η οποία υπερβαίνει το μέγιστο όριο των 32 σελίδων (\(0..31\)). Άρα δεν είναι έγκυρη λογική διεύθυνση της διεργασίας. - (Γ) Λάθος: Η διεύθυνση \(\text{3CCC}_{16} = 15564_{10}\). Ο αριθμός σελίδας είναι \(\lfloor 15564 / 1024 \rfloor = 15\) και το offset είναι \(15564 \bmod 1024 = 204 = \text{0CC}_{16}\). Στον πίνακα, η σελίδα 15 έχει πλαίσιο 9 και bit 1. Η φυσική διεύθυνση είναι \(9 \times 1024 + 204 = 9216 + 204 = 9420_{10} = \text{24CC}_{16}\) (και όχι \(\text{9CCC}_{16}\)). - (Δ) Σωστή: Η διεύθυνση \(\text{7CCC}_{16} = 31948_{10}\). Ο αριθμός σελίδας είναι \(\lfloor 31948 / 1024 \rfloor = 31\) και το offset είναι \(31948 \bmod 1024 = 204 = \text{0CC}_{16}\). Η σελίδα 31 ανήκει στον λογικό χώρο της διεργασίας (\(31 < 32\)), αλλά στον πίνακα σελίδων έχει Έγκυρο/Άκυρο bit ίσο με 0. Επομένως, δεν είναι φορτωμένη στη φυσική μνήμη (θα προκαλέσει σφάλμα σελίδας / page fault).

Σωστή πρόταση: (Δ)

Θέμα 5

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

(α) Αλγόριθμος αρτοποιείου (bakery) του Lamport για N διεργασίες (το πλήθος στην εκφώνηση είναι δυσανάγνωστο, γράφεται γενικά για N). Κάθε διεργασία παίρνει «αριθμό» μεγαλύτερο από όλους τους υπάρχοντες· μπαίνει στην κρίσιμη περιοχή η διεργασία με τον μικρότερο αριθμό, με ισοπαλία να λύνεται από το μικρότερο id.

shared: boolean choosing[N] = {false};  int number[N] = {0};

process i:
  while (true) {
     choosing[i] = true;
     number[i] = 1 + max(number[0..N-1]);
     choosing[i] = false;
     for (j = 0; j < N; j++) {
        while (choosing[j]) ;                         // περίμενε να πάρει αριθμό ο j
        while (number[j] != 0 &&
               (number[j] < number[i] ||
               (number[j] == number[i] && j < i))) ;  // ο j έχει προτεραιότητα
     }
     /* ΚΡΙΣΙΜΗ ΠΕΡΙΟΧΗ */
     number[i] = 0;
     /* ΜΗ ΚΡΙΣΙΜΗ ΠΕΡΙΟΧΗ */
  }

Το \(choosing[j]\) εμποδίζει την περίπτωση να συγκριθούμε με διεργασία που ακόμα υπολογίζει τον αριθμό της.

(β) Pathname translation του /Users/[όνομα]/os/mmap.c → inode# του mmap.c (τυπική διαδικασία UNIX): 1. Ξεκινά από το inode της ρίζας (γνωστός, σταθερός αριθμός, π.χ. 2). 2. Διαβάζεται το inode της ρίζας: έλεγχος ότι είναι κατάλογος και ότι υπάρχει δικαίωμα εκτέλεσης/αναζήτησης· διαβάζονται τα data blocks του καταλόγου και αναζητείται εγγραφή με όνομα Users → βρίσκεται inode# του Users. 3. Διαβάζεται το inode του Users (έλεγχος κατάλογος + δικαιώματα), σαρώνονται τα blocks του και βρίσκεται η εγγραφή [όνομα] → inode#. 4. Το ίδιο για τον κατάλογο [όνομα] → εγγραφή os → inode#. 5. Το ίδιο για τον κατάλογο os → εγγραφή mmap.c → inode# του αρχείου mmap.c (έξοδος της διαδικασίας).

Σε κάθε βήμα γίνονται 2 προσπελάσεις δίσκου (inode + data block(s) του καταλόγου, εκτός αν είναι στην cache)· συνολικά ~4 κατάλογοι. Αν κάποιο όνομα δεν βρεθεί ή λείπει δικαίωμα, η μετάφραση αποτυγχάνει.

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

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