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

Find the last ball! 

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

Περιγραφή του παιχνιδιού 

Το παιχνίδι έχει ως εξής: σε ένα τετραγωνικό ταμπλό (Χ κελιά * X κελιά) είναι κρυμμένες τέσσερις μπάλες. Ο κάθε παίκτης επιλέγει ένα κελί στην τύχη με στόχο να βρει μια από τις τέσσερις μπάλες. Οι κινήσεις γίνονται διαδοχικά. Αυτός που θα βρει την τελευταία κρυμμένη μπάλα είναι και ο νικητής. 

Υλοποίηση του παιχνιδιού 

Η υλοποίηση του παιχνιδιού θα πρέπει να γίνει σε δύο διαφορετικά κομμάτια. Το πρώτο κομμάτι είναι ο Game Server που κατασκευάζει το ταμπλό και τον Game Client που εξομοιώνει τη συμπεριφορά των παικτών. 

Υλοποίηση του Game Server 

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

Το ταμπλό θα πρέπει να "μοιραστεί" με το process που αντιστοιχεί στο Game Client, επομένως θα πρέπει να χρησιμοποιήσετε τις σχετικές με shared memory συναρτήσεις. ώστε να "μοιράσετε" την ποσότητα μνήμης που αντιστοιχεί στο ταμπλό μεταξύ του Game Server και του Game client. 

Υλοποίηση του Game Client 

Ο Game Client θα πρέπει να εξομοιώνει μια υποθετική παρτίδα μεταξύ δύο διαφορετικών παικτών. Για κάθε έναν από τους δύο παίκτες, θα πρέπει να κατασκευάσετε ένα thread. Θα πρέπει να χρησιμοποιήσετε τα POSIX Threads. 

Το thread που θα πετύχει τυχαία την τελευταία μπάλα, θα είναι είναι και ο νικητής της παρτίδας. Προσέξτε, ότι θα πρέπει να βρείτε έναν τρόπο ώστε ο Game Server να ειδοποιήσει τον Game Client, ότι η παρτίδα έχει λήξει. 

Επιπλέον, βασικό σημείο αποτελεί η δικαιοσύνη που θα πρέπει να επιτευχθεί ανάμεσα στους δύο παίκτες. Επειδή ο κάθε παίκτης εξομοιώνεται από ένα thread θα πρέπει να εγγυηθείτε ότι οι εναλλαγές των threads γίνονται απόλυτα σειριακά. Αν υποθέσουμε ότι το thread ΤΗ1 και το thread ΤΗ2 αντιστοιχούν στους παίκτες 1 και 2, αντίστοιχα, τότε θα πρέπει η εκτέλεση τους να έχει την αλληλουχία: TH1, TH2, TH1, TH2 και όχι κάτι της μορφής: TH1, TH1, TH2, TH1, TH1, TH1, TH2, ..., TH1. Για να το πετύχετε αυτό μπορείτε να χρησιμοποιήσετε Semaphores για την σωστή είσοδο των threads στο κομμάτι του κώδικα που είναι υπεύθυνος για την εκτέλεση μιας κίνησης του παιχνιδιού. 

Θα πρέπει να χρησιμοποιήσετε τα POSIX Semaphores. 

Τεχνικά Θέματα 

Οι βιβλιοθήκες που έχουν υποστήριξη για POSIX Threads/Semaphores είναι οι: libpthread.so. 

Reference - man pages 

Ένα man page περιγράφει τον τρόπο λειτουργίας ενός προγράμματος, ενός system call ή μιας library function. Η εμφάνιση ενός man page γίνεται με τη χρήση της εντολής: 

man(1) 

Για να δείτε το man page (σε SunOS) που αναφέρεται στη foo(N), κάνετε: 

% man -s N foo 

Για να δείτε το man page (σε Linux) που αναφέρεται στη foo(N), κάνετε: 

% man -S N foo 

Ο συμβολισμός foo(N) αναφέρεται στο man page που περιγράφει τη foo στη κατηγορία (section) 'Ν'. 

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

Σας παραθέτουμε man pages που θα βρείτε σε μηχάνημα με SunOS (π.χ. hades). Η παρακάτω λίστα δεν είναι δεσμευτική αν η ενότητα υποδεικνύεται ως 'Suggested', ενώ είναι δεσμευτική όταν υποδεικνύεται ως 'Required'. 

Shared Memory (Suggested)

shmget(2)

shmat(2)

shmctl(2)

shmdt(2)

POSIX Semaphores (Required)

sem_init(3RT)

sem_wait(3RT)

sem_post(3RT)

POSIX Threads (Required)

pthread_create(3THR)

pthread_join(3THR)

pthread_setconcurrency(3THR)

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

1. Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα από κατάλληλο πρόγραμμα και θα μηδενιστούν. Συμπεριλάβετε το όνομα σας και το λογαριασμό σας (account) σε όλα τα αρχεία. Μην παραδώσετε εκτυπώσεις των προγραμμάτων.
2. Κατασκευάστε ένα αρχείο Makefile, έτσι ώστε πληκτρολογώντας make all να γίνεται η μεταγλώττιση (compilation) του προγράμματος και να παράγεται το εκτελέσιμο αρχείο. Επίσης πληκτρολογώντας make clean να καθαρίζονται όλα τα περιττά αρχεία, και να μένουν μόνο τα αρχεία που χρειάζονται για τη μεταγλώττιση.
3. Επιπλέον, γράψτε και ένα αρχείο readme.txt το πολύ 30 γραμμών που να περιέχει επεξηγήσεις για τον τρόπο υλοποίησης.
4. Κατασκευάστε το αρχείο assign2.tar.gz που θα περιέχει όλα τα αρχεία που χρειάζονται για τη μεταγλώττιση της άσκησης 2 (χρησιμοποιώντας την εντολή tar και για συμπίεση το πρόγραμμα gzip). Παραδώστε το παραπάνω αρχείο χρησιμοποιώντας το πρόγραμμα submit (πληκτρολογήστε ~hy345/bin/submit 2 από το directory που περιέχει το αρχείο assign2.tar.gz και από μηχάνημα SunOS).
5. Το πρόγραμμα σας θα πρέπει να τρέχει σε SunOS (π.χ. hades).
6. Σε πολλές περιπτώσεις τα ονόματα των συναρτήσεων βιβλιοθήκης είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.