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



Παράδοση: 12/11/2010
Ναυμαχία!

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

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

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

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

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

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

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

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

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

Ο Game Client θα πρέπει να εξομοιώνει μια παρτίδα μεταξύ δύο διαφορετικών παικτών. Για κάθε έναν από τους δύο παίκτες, θα πρέπει να κατασκευάσετε ένα thread. Θα πρέπει να χρησιμοποιήσετε τα POSIX Threads. Ο υπολογιστής θα ελέγχει και τους δυο παίκτες. Ενδεικτικά ο παίκτης υπολογιστής μπορεί να λειτουργεί ως εξής: θα επιλέγει μια τυχαία θέση πάνω στο ταμπλό. Εάν αυτή η θέση είναι ήδη χτυπημένη (hit), τότε επιλέγει μια άλλη. Εάν αυτή η θέση αποτελεί δική του αποτυχημένη επιλογή του παρελθόντος (miss), τότε επιλέγει μια άλλη. Εάν κάνει τρεις προσπάθειες να βρει μια κατάλληλη θέση να χτυπήσει και δεν τα καταφέρει, αντιμετωπίζει το ταμπλό σαν συνεχόμενες θέσεις και επιλέγει την πρώτη διαθέσιμη. Κάθε παίκτης "βλέπει" τη θέση του δικού του πλοίου, μόνο τις δικές του αποτυχίες και όλες τις επιτυχημένες βολές (hits). Θεωρείστε οτι ο παίκτης υπολογιστής δεν κλέβει: έχει πρόσβαση σε όλο το ταμπλό αλλά δεν βασίζει τη λογική του στην ύπαρξη πληροφορίας που αφορά τον αντίπαλο παίκτη (π.χ., ο παίκτης υπολογιστής μπορεί να δει που είναι το αντίπαλο πλοίο αλλά δεν το λαμβάνει υπόψιν του στην επιλογή της θέσης που θα χτυπήσει)

Οι δυο παίκτες, μόλις ενημερωθούν για το νικητή του παιχνιδιού, τερματίζουν το παιχνίδι. Εμφανίζεται κατάλληλο μήνυμα για το ποιος έχει κερδίσει και εκτυπώνεται ολόκληρο το ταμπλό με εμφανείς τις βολές, αποτυχίες και τη θέση του αντίπαλου πλοίου. Ο τρόπος με τον οποίο ο server ενημερώνει τους παίκτες για το αποτέλεσμα του παιχνιδιού ΔΕΝ θα είναι η χρήση κάποιας κοινόχρηστης μεταβλητής.

Πολύ σημαντικό είναι να εξασφαλίζετε τη σωστή συμπεριφορά των παικτών και του game server όσον αφορά την πρόσβαση στο κοινόχρηστο ταμπλό. Θυμηθείτε ότι έχετε δυο threads τα οποία εκτελούνται παράλληλα, περιμένουν μια τυχαία καθυστέρηση (1-3 δευτερόλεπτα) και επιχειρούν να μεταβάλουν το ταμπλό. Παράλληλα, ο 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

Shared Memory 
shmget(2)
shmat(2)
shmctl(2)
Named Pipes 
mkfifo(3)
unlink(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 γραμμών που να περιέχει επεξηγήσεις για τον τρόπο υλοποίησης.