Λειτουργικά Συστήματα (ΗΥ-345)
Χειμερινό Εξάμηνο 2009
Ασκηση 2η



The Restaurant Problem

Σε αυτήν την άσκηση θα υλοποιήσετε μια λύση για μια παραλλαγή του προβλήματος παραγωγού-καταναλωτή (producer-consumer). Στόχος της άσκησης είναι να εξοικειωθείτε με βασικές έννοιες από τον χώρο του IPC (InterProcess Communication) και των threads. Ουσιαστικά, τα εργαλεία που θα χρησιμοποιήσετε σε αυτήν την άσκηση είναι: shared memory, semaphores και threads.

Περιγραφή

Το πρόβλημα αποτελείται απο τρείς producers, που φτιάχνουν 3 διαφορετικά είδη φαγητών (spaggeti, pizza και hamburger), και από πολλούς consumers που ζητούν ταυτόχρονα κάποιες ποσότητες από φαγητά. Για την άσκηση θα δημιουργήσετε δύο διεργασίες: μία για τους producers και μία για τους consumers. H κάθε διεργασία θα αποτελείται απο πολλά διαφορετικά threads, ένα για κάθε producer ή consumer αντίστοιχα. Οι δύο αυτές διεργασίες θα επικοινωνούν μέσω shared memory, στην οποία θα αποθηκεύονται 3 buffers (π.χ. στοίβες ή ουρές). Κάθε buffer αντιστοιχεί σε ένα είδος φαγητού. Όταν κάποιος consumer ζητήσει μια μερίδα φαγητού από κάποιον buffer που είναι άδειος, τότε θα πρέπει να μπλοκάρει και να περιμένει μέχρι ο αντίστοιχος producer να φτιάξει μία τουλάχιστον μερίδα του συγκεκριμένου φαγητού. Αντίστοιχα, όταν γεμίσει ένας από αυτούς τους buffers, ο producer του συγκεκριμένου φαγητού θα μπλοκάρει και θα περιμένει μέχρι κάποιος consumer να ζητήσει και να βγάλει μια μερίδα φαγητού από αυτόν τον buffer. Τέλος, πρέπει να εξασφαλίσετε οτι οι producers και οι consumers δεν προσπελαύνουν ταυτόχρονα τον ίδιο buffer (πρόβλημα αμοιβαίου αποκλεισμού). Αυτά τα προβλήματα θα πρέπει να τα λύσετε χρησιμοποιώντας σημαφόρους.

Παρακάτω ακολουθεί πιο αναλυτική περιγραφή για την υλοποίηση των δύο διεργασιών.

Producers

Η διεργασία των producers θα πρέπει αρχικά να δημιουργεί ένα shared memory segment για 3 buffers (και για τα indexes που απαιτούνται για αυτούς), έναν για κάθε είδος φαγητού. Κάθε μερίδα φαγητού αναπαρίσταται με έναν μοναδικό ακέραιο αριθμό (sequence number). Αρα, για κάθε buffer χρειαζόμαστε μνήμη ίση με το μέγεθος ενός ακεραίου επί το μέγεθος του buffer N (θα το ορίζετε με define μέσα στα προγράμματά σας).

Επίσης, η διεργασία των producers θα πρέπει να τοποθετεί σε shared memory segments τις σημαφόρους που χρειάζονται. Για κάθε buffer θα χρησιμοποιήσετε μια δυαδική σημαφόρο για αμοιβαίο αποκλεισμό, και δύο ακόμα σημαφόρους για να ελέγχετε αν ο buffer έχει αδειάσει ή έχει γεμίσει αντίστοιχα.

Στην συνέχεια, η διεργασία θα δημιουργεί τρία threads, ένα για κάθε producer. Κάθε thread θα καλεί την συνάρτηση food_producer() με όρισμα το είδος του φαγητού που θα παράγει, δηλαδή τον buffer στον οποίο θα γράφει. Ο κάθε producer θα μπαίνει σε ένα ατέρμονο loop όπου θα προσθέτει μια μερίδα φαγητού (έναν ακέραιο αριθμό δηλαδή) κάθε ένα δευτερόλεπτο στον buffer που έχει αναλάβει. Όταν ο buffer του γεμίσει, ο producer θα μπλοκάρει περιμένοντας να αφαιρεθεί ένα τουλάχιστον στοιχείο από τον buffer.

Τέλος, το main thread στο process των producers θα πρέπει περιοδικά να τυπώνει την κατάσταση των τριών buffers με τα φαγητά (τα sequence numbers των μερίδων που περιέχει κάθε buffer). Για παράδειγμα, κάτι σαν το παρακάτω:
spaggeti pizza hamburger
8 11 9
3 4
3
2
Όταν θα κλείνετε την διεργασία των producers, πατώντας CTRL-C, θα πρέπει οπωσδήποτε να αποδεσμεύετε τα shared memory segments υλοποιώντας τον κατάλληλο signal handler (για τα signals SIGINT και SIGTERM). Αυτός ο signal handler θα πρέπει να είναι απο τα πρώτα πράγματα που θα υλοποιήσετε. Είναι σημαντικό να μην αφήνετε στα μηχανήματα που δουλεύετε shared memory segments, επειδή όταν αυτά φτάσουν ενα συγκεκριμένο όριο δεν θα μπορείτε να δεσμεύσετε άλλα και το πρόγραμμά σας δεν θα δουλεύει (πρέπει και να κοιτάζετε τα μηνύματα λάθους όταν δημιουργείτε καινούργια shared memory segments). Aν έχετε αφήσει shared memory segments σε κάποιο μηχάνημα θα πρέπει να τα αποδεσμεύετε με τις αντίστοιχες εντολές από command line (δείτε στο τέλος της εκφώνησης τις εντολές αυτές).

Consumers

Μια άλλη διεργασία, που θα την αρχίζετε μετά που θα έχετε αρχίσει την διεργασία με τους producers (ώστε να έχουν δημιουργηθεί τα shared memory segments), θα προσομοιώνει τους consumers χρησιμοποιώντας threads. Πρώτα θα πρέπει να βρίσκει και να κάνει attach τα shared memory segments που έχουν δημιουργηθεί απο την διεργασία με τους producers.

Έπειτα, θα δημιουργεί ένα thread για κάθε consumer. Ο αριθμός των consumers θα πρέπει να δίνεται στο πρόγραμμα αυτό από την γραμμή εντολών. Κάθε thread θα καλεί την συνάρτηση food_consumer(). Εκεί θα γίνεται ένα ατέρμονο loop, και σε κάθε επανάληψη (κάθε ένα δευτερόλεπτο) ο consumer θα ζητάει έναν τυχαίο αριθμό από μερίδες φαγητού (από 0 μέχρι Ν/3) από το κάθε είδος. Έπειτα, θα αφαιρεί αυτόν τον αριθμό από μερίδες φαγητού (ένα προς ένα) από τους αντίστοιχους buffers και θα τυπώνει το sequence number και το είδος της κάθε μερίδας που βγάζει από τον κάθε buffer. Αν κάποιος buffer γίνει άδειος πρίν δώσει την μερίδα στο thread ενός consumer, το thread αυτό θα πρέπει να μπλοκάρει μέχρι ο αντίστοιχος producer να βάλει τουλάχιστον ένα στοιχείο στον buffer.

Τρέξτε το πρόγραμμα με τους consumers πολλές φορές με διαφορετικό αριθμό από consumers και εξετάστε τις διαφορές.

Λίστα με χρήσιμα man pages για την Aσκηση 2

Σας παραθέτουμε man pages με κάποιες συναρτήσεις που θα χρειαστείτε για την υλοποίηση της άσκησης. Η παρακάτω λίστα δεν είναι δεσμευτική. Μπορείτε να χρησιμοποιήσετε και εναλλακτικούς τρόπους.

Shared Memory 
ftok(3C)
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>

Παρατηρήσεις

  1. Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα από κατάλληλο πρόγραμμα και θα μηδενιστούν. Συμπεριλάβετε το όνομα σας και το λογαριασμό σας (account) σε όλα τα αρχεία. Μην παραδώσετε εκτυπώσεις των προγραμμάτων.
  2. Κατασκευάστε ένα αρχείο Makefile, έτσι ώστε πληκτρολογώντας make all να γίνεται η μεταγλώττιση (compilation) του προγράμματος και να παράγονται τα εκτελέσιμα αρχεία. Επίσης πληκτρολογώντας make clean να καθαρίζονται όλα τα περιττά αρχεία, και να μένουν μόνο τα αρχεία που χρειάζονται για τη μεταγλώττιση.
  3. Επιπλέον, γράψτε και ένα αρχείο readme.txt το πολύ 30 γραμμών που να περιέχει επεξηγήσεις για τον τρόπο υλοποίησης.
  4. Κατασκευάστε τον κατάλογο assign2 που θα περιέχει όλα τα αρχεία που χρειάζονται για τη μεταγλώττιση της άσκησης 2. Παραδώστε το παραπάνω αρχείο χρησιμοποιώντας το πρόγραμμα submit (πληκτρολογήστε submit assignment_2@hy345 assign2 από τον κατάλογο που περιέχει τον assign2).
  5. Προσέξτε να ελευθερώνετε όσα shared memory segments έχετε δεσμεύσει στα μηχανήματα που θα τρέχετε τις ασκήσεις σας. Με την εντολή ipcs -m μπορείτε να δείτε αν έχετε αφήσει memory segments στο μηχάνημα. Με την εντολή ipcrm -m [id] μπορείτε να σβήσετε τα segments με το συγκεκριμένο id, αν έχετε permissions.