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



Παράδοση: 18/11/2011
Χρυσωρυχείο

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

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

Το παιχνίδι έχει ως εξής: ένα τετραγωνικό ταμπλό Ν κελιών (Χ κελιά * Χ κελιά) εξομοιώνει το έδαφος. Μέσα στο έδαφος βρίσκονται θαμένα κομμάτια χρυσού, και περιοδικά δημιουργούνται και άλλα. Ο κάθε παίκτης σε κάθε προσπάθειά του επιλέγει ένα κελί στην τύχη με στόχο να βρεί όσο το δυνατόν περισσότερο χρυσό. Το παιχνίδι τελειώνει μετά από Ν προσπάθειες του κάθε παίχτη και νικητής είναι ο παίχτης που βρήκε τον περισσότερο χρυσό (αν κάποιοι παίχτες έχουν βρεί ίσο αριθμό απο κομμάτια χρυσού τότε έχουμε ισοβαθμία). Οι κινήσεις γίνονται ασύγχρονα. Κάθε παίκτης επιλέγει ένα κελί στην τύχη, περιμένει για τυχαίο διάστημα 1-3 δευτερολέπτων και ξαναπροσπαθεί.

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

Η υλοποίηση του παιχνιδιού θα πρέπει να γίνει σε δύο διαφορετικά προγράμματα - διεργασίες. Το πρώτο πρόγραμμα είναι ο Game Server που κατασκευάζει και γεμίζει το ταμπλό και το δεύτερο είναι ο Game Client που εξομοιώνει τη συμπεριφορά των παικτών. Οι δύο αυτές διεργασίες θα επικοινωνούν μέσω shared memory, στην οποία θα αποθηκεύονται το ταμπλό του παιχνιδιού, ο χρυσός και οι προσπάθειες των παιχτών. Θα πρέπει να εξασφαλίσετε οτι οι παίχτες και ο Game Server δεν προσπελαύνουν ταυτόχρονα το ίδιο κελί (πρόβλημα αμοιβαίου αποκλεισμού). Αυτό το πρόβλημα θα πρέπει να το λύσετε χρησιμοποιώντας σημαφόρους.

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

Ο Game Server είναι υπεύθυνος για την κατασκευή και την αρχικοποίηση του ταμπλό. Το ταμπλό έχει συνολικά Ν κελιά (Χ κελιά * Χ κελιά). Μπορείτε να ορίσετε με define το Χ (η μία διάσταση για το μέγεθος του ταμπλό) και να δοκιμάσετε διάφορες τιμές. Κάθε κελί αντιστοιχεί σε έναν ακέραιο αριθμό, οπότε το ταμπλό είναι ένας δισδιάστατος πίνακας ακεραίων. Ο Game Server αρχικά πρέπει να δημιουργήσει ένα shared memory segment για το ταμπλό του παιχνιδιού. Επισης, θα πρέπει να δημιουργήσει shared memory segments για τον χρυσό και τις προσπάθεις κάθε παίχτη, για τον μέγιστο αριθμό παιχτών που υποστηρίζει (π.χ. μέχρι 10 παίχτες). Τέλος, πρέπει να τοποθετήσει σε shared memory segments και όλες τις σημαφόρους που χρειάζονται. Έπειτα ο Game Server επιλέγει τυχαία Χ κελιά και σε καθένα τοποθετεί τυχαία από 1 έως 10 κομμάτια χρυσού. Μετά την αρχικοποίηση το παιχνίδι ξεκινάει.

Kάθε 2 δευτερόλεπτα, ο Game Server διαλέγει στην τύχη ένα κελί (i,j) και προσθέτει επίσης στην τύχη από 1 έως 10 κομμάτια χρυσού σε αυτό το κελί. Kάθε 1 δευτερόλεπτο, ο Game Server τυπώνει το ταμπλό με τα κομμάτια χρυσού που περιέχονται σε κάθε κελί. Για παράδειγμα, το παρακάτω στιγμιότυπο θα μπορούσε να τυπωθεί για ένα 5x5 ταμπλό:
0 0 6 0 8
5 7 0 12 4
0 1 0 6 0
2 0 9 0 2
0 15 0 0 2


Επίσης, ο Game Server κάθε 1 δευτερόλεπτο παρακολουθεί αν οι παίχτες έχουν κάνει όλες τις Ν προσπάθειες που τους επιτρέπονται και τυπώνει για κάθε παίχτη τις προσπάθεις που έχει κάνει ως εκείνη τη στιγμή και τον χρυσό που έχει μαζέψει. Μόλις ολοκληρώσουν όλοι οι παίχτες τις Ν προσπάθειές τους, ο Game Server τυπώνει την τελική κατάσταση του ταμπλό, τον χρυσό που έχει βρεί ο κάθε παίχτης, και συγκρίνοντας αυτά τα σκόρ τυπώνει και ποιός παίχτης νίκησε. Έπειτα το παιχνίδι τελειώνει και οι διεργασίες τερματίζουν.

Όταν θα κλείνετε την διεργασία του Game Server θα πρέπει οπωσδήποτε να αποδεσμεύετε τα shared memory segments που δεσμεύσατε. Είναι σημαντικό να μην αφήνετε στα μηχανήματα που δουλεύετε shared memory segments, επειδή όταν αυτά φτάσουν ενα συγκεκριμένο όριο δεν θα μπορείτε να δεσμεύσετε άλλα και το πρόγραμμά σας δεν θα δουλεύει (πρέπει και να κοιτάζετε τα μηνύματα λάθους όταν δημιουργείτε καινούργια shared memory segments). Aν έχετε αφήσει shared memory segments σε κάποιο μηχάνημα θα πρέπει να τα αποδεσμεύετε με τις αντίστοιχες εντολές από command line (δείτε στο τέλος της εκφώνησης τις εντολές αυτές).

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

Η διεργασία του Game Client εξομοιώνει πολλούς διαφορετικούς παίχτες. Πρώτα θα πρέπει να βρίσκει και να κάνει attach τα shared memory segments που έχουν δημιουργηθεί από τον Game Server, όπως το αρχικοποιημένο ταμπλό του παιχνιδιού, ο χρυσός και οι προσπάθειες των παιχτών, και οι σημαφόροι για όλα τα παραπάνω. Άρα θα ξεκινάτε τον Game Client μετά που θα έχετε ξεκινήσει τον Game Server (ώστε να έχουν δημιουργηθεί τα shared memory segments). Μπορείτε να δηλώσετε με define το Χ (μέγεθος μιας διάστασης του ταμπλό), που θα είναι το ίδιο με την τιμή που έχετε δηλώσει στον Game Server.

O Game Client θα δέχετε ένα όρισμα από την γραμμή εντολών, που είναι ο αριθμός των παιχτών. Ο Game Server θα πρέπει επίσης να ειδοποιηθεί (μέσω shared memory) για τον αριθμό των παιχτών. Για κάθε έναν από τους παίκτες θα πρέπει να κατασκευάσετε ένα thread. Θα πρέπει να χρησιμοποιήσετε τα POSIX Threads. Ο υπολογιστής θα ελέγχει όλους τους παίκτες (δεν δέχετε είσοδο απο τον χρήστη). Ο κάθε παίκτης (κάθε thread) θα λειτουργεί ως εξής: (i) θα επιλέγει μια τυχαία θέση στο ταμπλό. (ii) Αν αυτή η θέση περιέχει χρυσό, θα αφαιρεί όλα τα κομμάτια χρυσού απο αυτή τη θέση και θα τα προσθέτει στον συνολικό χρυσό του. (iii) Ο παίχτης θα τυπώνει την κίνηση του, δηλαδή ποιός παίχτης είναι, ποιά προσπάθεια έκανε, ποιά θέση διάλεξε στο ταμπλό, πόσο χρυσό βρήκε εκεί, και τον συνολικό του χρυσό. (iv) Έπειτα θα κοιμάται για τυχαίο διάστημα μεταξύ 1 και 3 δευτερόλεπτα προτού δοκιμάσει ξανά. Επίσης, ο κάθε παίχτης θα πρέπει να μετράει τις προσπάθειες που έχει κάνει και θα σταματάει μόλις κάνει ακριβώς Ν προσπάθειες (Ν=Χ*Χ). Τότε το αντίστοιχο thread θα τερματίζει. Όταν τερματίσουν όλα τα threads, θα τερματίζει και η διεργασία του Game Client.

Πολύ σημαντικό είναι να εξασφαλίζετε τη σωστή συμπεριφορά των παικτών και του Game Server όσον αφορά την πρόσβαση στο κοινόχρηστο ταμπλό. Θυμηθείτε ότι έχετε πολλά threads τα οποία εκτελούνται παράλληλα και αφαιρούν χρυσό από τυχαία κελιά στο ταμπλό. Είναι πολύ πιθανό κάποια από αυτά τα threads να διαλέξουν το ίδιο κελί. Επίσης, ταυτόχρονα εκτελείται και ο Game Server που προσθέτει χρυσό σε τυχαία κελιά στο ίδιο ταμπλό. Τι θα συμβεί αν σχεδόν ταυτόχρονα δυο ή παραπάνω threads/processes προσπαθήσουν να αφαιρέσουν/προσθέσουν χρυσό από το ίδιο κελι? Επίσης, ο Game Server διαβάζει τον αριθμό των προσπαθειών και τον χρυσό του κάθε παίχτη την ίδια στιγμή που οι παίχτες τα αυξάνουν. Οπότε είναι σημαντικό να διαβάσει τους σωστούς αριθμούς. Για να λύσετε όλα αυτά τα προβλήματα θα πρέπει να χρησιμοποιήσετε τα POSIX Semaphores.

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 με κάποιες συναρτήσεις που θα χρειαστείτε για την υλοποίηση της άσκησης. Η παρακάτω λίστα δεν είναι δεσμευτική. Μπορείτε να χρησιμοποιήσετε και εναλλακτικούς τρόπους.

Shared Memory 
ftok(3C)
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)
Η μεταγλώττιση πρέπει να γίνει με την παραμέτρο -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. Τοποθετήστε σε ένα κατάλογο όλα τα αρχεία που χρειάζονται για την άσκηση 2. Παραδώστε τα παραπάνω αρχεία χρησιμοποιώντας το πρόγραμμα submit (πληκτρολογήστε submit assignment_2@hy345 directory_name από τον κατάλογο που περιέχει τον κατάλογο directory_name με τα αρχέια της άσκησης).
  5. Σε πολλές περιπτώσεις τα ονόματα των συναρτήσεων βιβλιοθήκης είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.
  6. Προσέξτε να ελευθερώνετε όσα shared memory segments έχετε δεσμεύσει στα μηχανήματα που θα τρέχετε τις ασκήσεις σας. Με την εντολή ipcs -m μπορείτε να δείτε αν έχετε αφήσει memory segments στο μηχάνημα. Με την εντολή ipcrm -m [id] μπορείτε να σβήσετε τα segments με το συγκεκριμένο id, αν έχετε permissions.