Λειτουργικά Συστήματα (ΗΥ-345)
Χειμερινό Εξάμηνο 2014-2015
Άσκηση 2
Φροντιστήριο: 24/10/2014
Παράδοση: 7/11/2014
Meeting Room Simulation
Σε αυτήν την άσκηση θα εξοικειωθείτε με τη δημιουργία και το χειρισμό threads, με shared memory με signals και με UNIX
sockets για την επικοινωνία μεταξύ διαφορετικών διεργασιών, καθώς επίσης με semaphores/mutexes για τον συγχρονισμό διαφορετικών
διεργασιών και τον αμοιβαίο αποκλεισμό.
Συγκεκριμένα, σε αυτήν την άσκηση θα χρειαστεί να κατασκευάσετε ένα απλό πρόγραμμα που θα προσoμοιώνει την λειτουργία μίας αίθουσας συνεδριάσεων
φοιτητών του πανεπιστημίου.
O προσομοιωτής αυτός θα έχει τα εξής χαρακτηριστικά:
- Οι εγκαταστάσεις του πανεπιστημίου αποτελούνται απο 1000 αίθουσες. Η γραμματεία μπορεί να διαθέσει μόνο μία αίθουσα για τις όλες συνεδριάσεις όλων των φοιτητών και των δύο τμημάτων.
- Η κάθε αίθουσα χωρά απεριόριστο αριθμό φοιτητών.
- Στην αίθουσα μπορούν να βρίσκονται και να συνεδριάζουν την ίδια στιγμή είτε μόνο φοιτητές του τμήματος μαθηματικών (Μ) είτε
μόνο φοιτητές του τμήματος επιστήμης υπολογιστών (C).
Θα πρέπει να υλοποιήσετε τρία διαφορετικά προγράμματα - διεργασίες.
- uoc_desk: το πρώτο πρόγραμμα θα αφορά την γραμματεία του πανεπιστημίου. Συγκεκριμένα η γραμματεία είναι
υπεύθυνη όταν οι φοιτητές ζητήσουν αίθουσα για την συνάντησή τους, να ελέγξει την διαθέσιμότητα της κάθε
αίθουσας και να δώσει στους φοιτητές την πρώτη διαθέσιμη αίθουσα
- math_students: το δεύτερο θα αφορά τους φοιτητές του τμήματος μαθηματικών
- csd_students: το τρίτο θα αφορά τους φοιτητές του τμήματος επιστήμης υπολογιστών.
Και τα δύο προγράμματα που αφορούν τους φοιτητές θα δέχονται ως όρισμα τον αριθμό N των νημάτων (threads). Κάθε ένα νήμα αναπαριστά έναν φοιτητή.
Για παράδειγμα, στην παρακάτω περίπτωση το math_students θα δημιουργεί 100 νήματα-φοιτητές μαθηματικών:
./math_students 100
Υλοποίηση του uoc_desk:
Για να ξεκινήσει η προσομοίωση χρειάζεται να εκτελεσθεί πρώτα η διεργασία της γραμματείας. Η διεργασία αυτή μόλις ξεκινήσει θα δημιουργεί
ένα UNIX socket και θα περιμένει τα αιτήματα των φοιτητών (χρησιμοποιώντας τις κλήσεις συστήματος socket(), bind(), listen() και accept()).
Όταν ο υπεύθυνος μιας ομάδας φοιτητών ζητήσει μία αίθουσα για την πραγματοποιήση συνάντησης, τότε η διεργασία θα επιλέγει τυχαία
έναν αριθμό μεταξύ 1-1000. Αυτός ο αριθμός αναπαριστά τον αριθμό της αίθουσας που είναι διαθέσιμη εκείνη την στιγμή. Έπειτα θα δημιουργεί ένα
κοινόχρηστο κομμάτι μνήμης (shared memory segment) με τις κλήσεις συστήματος shmget() και shmat(). Για να δημιουργήσει το memory segment αυτό, η
διεργασία χρησιμοποιεί ως κλειδί τον αριθμό της αίθουσας. Αν για κάποιο κλειδί αποτύχει η δημιουργία του shared memory segment, τότε η γραμματεία
θα πρέπει να διαλέξει μία άλλη αίθουσα με τον τυχαίο τρόπο που αναφέρθηκε προηγουμένως.
Ύστερα η διεργασία απαντά στον υπεύθυνο φοιτητή μεσω του UNIX socket στέλνοντας τον αριθμό της αίθουσας. Η διεργασία σε περίπτωση που έρθει έπειτα
άλλος φοιτητής για να ζητήσει αίθουσα, θα πρέπει να απαντά στέλνοντας τον ίδιο αριθμό της αίθουσας που έδωσε και στην πρώτη ομάδα.
Τέλος, η διεργασία θα δημιουργεί ένα thread (καλώντας την pthread_create()) το οποίο thread θα τυπώνει την κατάσταση της αίθουσας κάθε 1 second.
Στο παρακάτω παράδειγμα κάθε γραμμή αφορά την κατάσταση της αίθουσας το συγκεκριμένο second:
1) C (=ένας φοιτητής του τμήματος επιστήμης υπολογιστών είναι εντός της αίθουσας)
2) CC (=δύο φοιτητές του τμήματος επιστήμης υπολογιστών είναι εντός της αίθουσας)
3) CCC
4) CC
5) C
6) M (=ένας φοιτητής του τμήματος μαθηματικών είναι εντός της αίθουσας)
7) MM
8) MMM
9) MMMM
10) C
11) CC
...
Η διεργασία θα τερματίζει με CTRL-C (υλοποιώντας τον κατάλληλο signal handler για τα signals SIGINT και SIGTERM). Πριν τερματιστεί όμως θα πρέπει
να κλείνει το UNIX socket της καθώς και να αποδεσμεύει σωστά τα το shared memory segment.
Υλοποίηση των math_students και csd_students:
Κατά την διεργασία μιας διεργασίας φοιτητών (math_students ή csd_students) ο υπεύθυνος φοιτητής θα συνδέεται με ένα UNIX socket με την γραμματεία
(με κλήσεις συστήματος socket() και connect()) για να ζητήσει μία αίθουσα για συνεδρίαση. Αφού λάβει την απάντηση της γραμματείας από το
socket (κλήση συστήματος recv()) τότε θα πρέπει να κάνει attach το shared memory (επίσης με τις κλήσεις σε shmget() και shmat()) χρησιμοποιώντας
και πάλι τον αριθμό της αίθουσας ως κλειδί. Στην συνέχεια, η διεργασία θα δημιουργεί Ν νήματα-φοιτητές καλώντας την pthread_create() αντίστοιχες
φορές. Έπειτα το κάθε thread θα παράγει 2 τυχαίους αριθμούς Α,Β μεταξύ 1-10. Τέλος, θα περιμένει για Α seconds και έπειτα θα προσπαθεί να είσέλθεί
στην αίθουσα, ύστερα θα περιμένει για Β seconds και θα εξέρχεται απο αυτήν. Η διεργασία θα τελειώνει όταν έχουν εξέλθει όλα τα νήματα-φοιτητές από
την αίθουσα.
Συγχρονισμός των διεργασιών φοιτητών:
Προσεξτε ότι δεν θα πρέπει να μπορούν να υπάρχουν την ίδια στιγμή στην αίθουσα φοιτητές και από τα δύο τμήματα, αλλά μπορεί να υπάρχει ένας
απεριόριστος αριθμός από φοιτητικές ομάδες που να θέλουν να κάνουν συνεδρίαση την ίδια στιγμή. Αυτό σημαίνει ότι μπορεί να τρέχουν παράλληλα
ένας μεγάλος αριθμός απο διεργασίες math_students και csd_students. 'Ετσι, θα πρέπει όταν τρέχουν και οι δυο αυτές οι διεργασίες φοιτητών και
προσπαθούν να μπούν στην αίθουσα, να συγχρονίζονται σωστά έτσι ώστε να έχει τελειώσει η συνεδρίαση της μίας ομάδας φοιτητών πριν
εισέλθουν στην αίθουσα οι φοιτητές της άλλης ομάδας. Γιαυτό το λόγο οι δυο διεργασίες θα χρησιμοποιούν έναν αριθμό από semaphores/mutexes
που θα βρίσκονται αποθηκευμένα στην κοινόχρηστη μνήμη.
Σημειώσεις:
- Δεν υπάρχει μόνο ένας τρόπος συγχρονισμού των διεργασιών φοιτητών. Μπορείτε να τον υλοποιήσετε με όποιον τρόπο σας βολεύει αρκεί να είναι
υποστηρίζει σωστά τις συγκεκριμένες συνθήκες:
- θα πρέπει υπάρχει δικαιοσύνη ανάμεσα στις ομάδες φοιτητών και άρα η υλοποίηση σας θα πρέπει να εγγυάται ότι οι συνεδριάσεις των ομάδων
φοιτητών θα γίνονται εν'αλλάξ, π.χ. αν εκτελείται συνεδρίαση φοιτητών του μαθηματικού και περιμένουν έξω από την αίθουσα παράλληλα 1 ομάδα
φοιτητών επιστήμης υπολογιστών και 1 ομάδα φοιτητών μαθηματικού τοτε οι επόμενοι για συνεδρίαση θα πρέπει να είναι οι φοιτητές του τμήματος
επιστήμης υπολογιστών.
- θα πρέπει να έχει ολοκληρωθεί μία συνεδρίαση (δηλαδή να έχουν εισέλθει και έπειτα εξέλθει από την αίθουσα όλοι οι φοιτητές) πριν μπεί η
επόμενη ομάδα φοιτητών ακόμα κι αν η επόμενη ομάδα φοιτητών ανήκει στο ίδιο τμήμα.
- Προσέξτε να ελευθερώνετε όσα shared memory segments έχετε δεσμεύσει στα μηχανήματα που θα τρέχετε τις ασκήσεις σας.
Είναι σημαντικό να μην αφήνετε στα μηχανήματα που δουλεύετε shared memory segments, επειδή όταν αυτά φτάσουν ενα συγκεκριμένο όριο δεν θα μπορείτε
να δεσμεύσετε άλλα και το πρόγραμμά σας δεν θα δουλεύει. Με την εντολή ipcs -m μπορείτε να δείτε αν έχετε αφήσει memory segments στο μηχάνημα. Με
την εντολή ipcrm -m [id] μπορείτε να σβήσετε τα segments με το συγκεκριμένο id, αν έχετε permissions.
Reference - man pages
Ένα man page περιγράφει τον τρόπο λειτουργίας
ενός προγράμματος, ενός system call ή μιας library function. Η εμφάνιση ενός man page
γίνεται με τη χρήση της εντολής:
man(1)
Για να δείτε το man page (σε Linux) που αναφέρεται στη foo(N), κάνετε:
% man -S N foo
Ο συμβολισμός foo(N) αναφέρεται στο man page που περιγράφει τη foo στη κατηγορία (section)
'Ν'.
Λίστα με χρήσιμα man pages για την Aσκηση 1
Σας παραθέτουμε man pages με system calls που μπορεί να χρειαστείτε για την υλοποίηση της άσκησης.
Η παρακάτω λίστα δεν είναι δεσμευτική. Μπορείτε να χρησιμοποιήσετε και εναλλακτικούς τρόπους.
Shared Memory
shmget(2)
shmat(2)
shmctl(2)
shmdt(2)
POSIX Semaphores
sem_init(3RT)
sem_wait(3RT)
sem_post(3RT)
POSIX Threads
pthread_create(3THR)
pthread_join(3THR)
pthread_setconcurrency(3THR)
Προσοχή! Η μεταγλώττιση πρέπει να γίνει με την παραμέτρο -lrt ώστε να συμπεριλάβει και την βιβλιοθήκη των σημαφόρων.
Κάποιες από τις βιβλιοθήκες που θα πρέπει να χρησιμοποιήσετε είναι οι παρακάτω:
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <unistd.h>
#include <semaphore.h>
#include <pthread.h>
Παρατηρήσεις
- Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα
από κατάλληλο πρόγραμμα και θα μηδενιστούν. Συμπεριλάβετε το όνομα σας και
το λογαριασμό σας (account) σε όλα τα αρχεία.
- Κατασκευάστε ένα αρχείο Makefile, έτσι ώστε
πληκτρολογώντας make all να γίνεται η μεταγλώττιση
(compilation) του προγράμματος και να παράγεται το εκτελέσιμο
αρχείο. Επίσης πληκτρολογώντας make clean να καθαρίζονται
όλα τα περιττά αρχεία, και να μένουν μόνο τα αρχεία που χρειάζονται
για τη μεταγλώττιση.
- Επιπλέον, γράψτε και ένα αρχείο readme.txt το πολύ 30 γραμμών που να
περιέχει επεξηγήσεις για τον τρόπο υλοποίησης και παραδείγματα
για τη χρήση του mysh που υλοποιήσατε.
- Τοποθετήστε σε ένα κατάλογο όλα τα
αρχεία που χρειάζονται για την άσκηση 2. Παραδώστε τα
παραπάνω αρχεία χρησιμοποιώντας το πρόγραμμα turnin (πληκτρολογήστε
turnin assignment_2@hy345 directory_name από τον κατάλογο
που περιέχει τον κατάλογο directory_name με τα αρχέια της άσκησης).
- Σε πολλές περιπτώσεις τα ονόματα των συναρτήσεων βιβλιοθήκης είναι
ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.