Project 1 OPERATING SYSTEMS

Author : TSVETOMIR IVANOV/ sdi1115201900066
Documentation:

α) Σχεδιαστικές Επιλογές/Παραδοχές:

Δομή Κοινής Μνήμης:

Για την υλοποίηση του μοντέλου Clients-Server, στο οποίο πολλοί πελάτες ζητάνε κάποιες γραμμές απο τον server χρησιμοποιείται:

SystemV Shared Memory με Posix Unnamed Semaphores

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

Ειδικότερα ως "κοινή μνήμη" ορίζουμε ένα struct shared_memory το οποίο περιέχει:

shared_memory {

sem_t client_to_other_clients; // ο σημαφόρος που συγχρονίζει τον πελάτη που εξυπηρετείται με τους υπόλοιπους πελάτες.
sem_t client_to_server; // ο σημαφόρος που συγχρονίζει τον πελάτη που εξυπηρετείται με τον server
sem_t server_to_client; // ο σημαφόρος που συγχρονίζει τον server με τον πελάτη που εξυπηρετεί
pid_t id; // σε αυτον τον ακέραιο αποθηκεύεται το child ID που υποβάλει το αίτημα του, έτσι ώστε να ξέρει ο γονιός σε ποιον απαντάει
int line_number // σε αυτόν τον ακέραιο θα αποθηκεύει ο κάθε client την γραμμή που ζητάει κάθε φορά.
char line[100] // σε αυτη την συμβολοσειρα θα αποθηκεύει ο server την γραμμή που του ζητάνε.
int child_counter }

Επίσης στο shared memory θα αποθηκευτεί και ο πίνακας των μέσων χρόνων αναμονής (float average_time[]) που υπολογίζονται για κάθε παιδι, μαζί με έναν πίνακα με πληροφορία προσδιορισμού των διεργασιών (unsigned int childIDs[]).

Επειδή ο αριθμός των παιδιών ειναι μεταβλητή (Κ) και επειδή δεν μπορούμε να δηλώσουμε δεικτες (pointers) στην κοινή μνήμη καθώς αυτοί θα ειναι ξεχωριστοί για κάθε παιδι (virtual memory address) ώστε να δημιουργήσουμε δυναμικα (malloc) πίνακα και να αποθηκεύσουμε τους χρόνους, πρέπει να κατασκευάσουμε αυτους τους πίνακες στην κοινή μνημη κατα την διαδικασία δημιουργίας της μεσω της shmget(). Οι θέσεις των πινάκων είναι αμέσως μετά τις μεταβλητές που ορίζονται ήδη στο shared_memory και με κατάλληλη αριθμητική δεικτών έχουμε την πρόσβαση σε αυτους.

Διαδικασία Επικοινωνίας clients-server:

Ζητούμενο της εργασίας ειναι το inter-process communication (IPC) δηλαδή η επικοινωνία διεργασίων που διαχειρίζονται καποιο shared data και ο κατάλληλος συγχρονισμόως τους ώστε να μην εμφανιστούν λάθη. Θεωρούμε οτι δεν ζητείται υλοποίηση κάποιας παραλληλίας με την έννοια ότι πολλοι πελάτες θα ζητάνε 'ταυτόχρονα' αιτήματα (εμφανίζοντας μήνυμα) και μόνο ένα απο αυτά απαντάται απο τον server. Η υλοποίηση έχει την εξής λογική: Καποιος πελάτης προλαβαίνει να μπει στο critical sectiont του, οπότε μπλοκάρει ολα τα άλλα, υποβάλει το αίτημα του (εμφανίζοντας κατάλληλο μήνυμα) και περιμένει απάντηση. Στο μεταξύ όλοι οι αλλοι πελάτες ειναι blocked, δεν κάνουν καμία ενέργεια, ούτε εχουν υποβάλει αίτημα και απλά περιμένουν ένας ένας να προλάβει να μπει στο critical section και να υποβάλει το αίτημα του. Επομένως τα αποτελέσματα έχουν την εξής μορφή:

Child 111 reuqesting line 4... Server delivering line to child 111... Child 111 printing line: " "

Child 113 reuqesting line 14... Server delivering line to child 113... Child 113 printing line: " "

Αρα πρέπει να εξασφαλίσουμε ότι καθε φορά μονο ενας πελάτης θα έχει πρόσβαση στην κοινή μνήμη και επομένως στο critical section του πράγμα που επιτυγχάνεται με τους 3 σημαφόρους που στην κοινή μνήμη.

Παραδοχή: To αίτημα του πελάτη περιλαμβάνει τις εξής ενέργειες

εκτύπωση κατάλληλου μηνύματος που να δηλώνει την γραμμή που ζητάει: Child with ID 111 requesting line 1...
γράψιμο στην κοινή μνήμη του αριθμού της γραμμής που ζητάει

Client:

'Μπλοκάρει' down() τους υπόλοιπους πελάτες και μπαίνει στο critical section του. Σε αυτό ανακοινώνει την γραμμή που θέλει να πάρει (με κατάλληλο μήνυμα) και γράφει στην κοινή μνήμη τον αριθμό της γραμμής.
'Απελευθερώνει' up() τον Server και μπλοκάρει down() τον εαυτό του, περιμένοντας για την απάντηση από τον server.
Αφού του επιστραφεί ξανά ο έλεγχος, εκτυπώνει την γραμμή, υπολογίζει τον χρόνο αναμονής αυτού του αιτήματος και έπειτα απελευθερώνει up() τους υπόλοιπους πελάτες έτσι ώστε καποιος αλλος να υποβάλει αίτημα.

***ΣΧΟΛΙΟ : Το παιδι που θα προλάβει να κάνει πρώτο down τον σημαφόρο (client_to_other_clients) μπλοκάρει τα υπόλοιπα, υποβάλει το αίτημα τού και περιμένει τον server να του απαντήσει. Επειτα εκτυπώνει τη γραμμή και κάνει up τον σημαφόρο (client_to_other_clients). Τις περισσότερες φορές όμως (με μικρό πλήθος παιδιών και αιτημάτων) παρατηρείται οτι εξυπηρετούνται πρώτα όλα τα αιτήματα του 1ου παιδιού , μετά του 2ου κ.ο.κ Αυτό συμβαίνει διότι στην πραγματικότητα οι διεργασίες δεν τρέχουν παράλληλα. Η κάθε μια εχει καποιο μερίδιο χρόνου, όταν ομως μπλοκάρονται λόγω των σημαφόρων είναι λογικό να προλαβαίνει πάντα το current process να lock-άρει τον σημαφόρο και επομένως να συνεχίσει με τα αιτήματα του. Για αυτό χρησιμοποιείται μια usleep(1) η οποία κάνει το τρέχον παιδί να 'κοιμηθεί' για 1 milisecond έτσι ώστε να προλάβει καποιο άλλο να υποβάλει αίτημα, και να υπάρχει η τυχαιότητα στην σειρά των αιτημάτων.

Server:

Μπλοκάρει τον εαυτό του down() περιμένοντας να του έρθει κάποιο αίτημα
Αφού απελευθερωθεί απο τον πελάτη, ανοίγει το αρχείο βρίσκει την γραμμή που του ζητάει και την γράφει στην κοινή μνήμη (critical section) εκτυπώνοντας κατάλληλο μήνυμα: Server delivering line to child 111...
Τέλος απελευθερώνει τον πελάτη, πηγαίνοντας στο επόμενο loop όπου ξαναμπλοκάρει τον εαυτό του κ.ο.κ

Μετά την ολοκλήρωση των αιτημάτων όλων των πελατών, το parent process περιμένει να τελείωσουν ολα τα child processes wait(), εκτυπώνει τους μέσους χρόνους αναμονής πελατών και σβήνει την κοινή μνήμη.

β) Τεχνικές Λεπτομέρειες:

Δομή Προγράμματος: Το πρόγραμμα οργανώνεται σε ενιαίο .c αρχείο ονόματι os.c Makefile: Δίνεται ενα makefile αρχείο για την μεταγλώττιση και την παραγωγή του εκτελέσιμου. Εντολες εκτέλεσης:

Ο χρήστης καλείται να εισάγει τις εξής εντολές στο terminal

make
make run file=<αρχειο.txt> k=<αριθμός παιδιών> n=<αριθμός δοσοληψιών>
make clean: για την διαγραφή του εκτελέσιμου
make val file=<αρχειο.txt> k= <αριθμός παιδιών> k= <αριθμός δοσοληψιών> : για τρέξιμο προγράμματος με valgrind (ελεγχος μνήμης)
make time file=<αρχειο.txt> k= <αριθμός παιδιών> k= <αριθμός δοσοληψιών>: για τρέξιμο προγράμματος με time (χρόνος εκτέλεσης)