• Υλοποίηση του server: Ο server θα δέχετε ένα όρισμα: το μέγεθος Ν για τα strings τα οποία θα προσπαθούν να μαντέψουν οι clients. Για παράδειγμα, στην παρακάτω περίπτωση ο server θα δημιουργεί τυχαία ένα string με 100 χαρακτήρες για να μαντέψει ο κάθε client:
  
  ./server 100
  
  Αρχικά, ο server θα δημιουργεί ένα UNIX socket και θα περιμένει κάποιον client να συνδεθεί (χρησιμοποιώντας τις κλήσεις συστήματος socket(), bind(), listen() και accept()). Μπορείτε να βρείτε ένα απλό tutorial για UNIX sockets εδώ. Δεν χρειάζεται να υποστηρίζετε πολλούς ταυτόχρονους clients στον server. Όταν κλείσει μια σύνδεση με έναν client, o server θα περιμένει ξανά κάποιον άλλο client να συνδεθεί. O server θα τερματίζει με CTRL-C (με το αντίστοιχο signal).
  
  Μόλις συνθεθεί κάποιος client, o server διαβάζει από το socket τον αριθμό των threads Μ του client. Έπειτα, ο server στέλνει στον client τον αριθμό Ν με τους χαρακτήρες που πρέπει να μαντέψει. Επίσης, o server δημιουργεί το string secret με Ν τυχαίους χαρακτήρες (από A-z). Στη συνέχεια, ο server δημιουργεί τρία shared memory segments (με τις κλήσεις συστήματος shmget() και shmat()):
  1. Το πρώτο shared memory segment είναι για N χαρακτήρες, και χρησιμοποιείται για να γράφει ο client τις επιλογές του για το κάθε γράμμα από τα N που προσπαθεί να μαντέψει. Ο server θα αρχικοποιεί αυτούς τους Ν χαρακτήρες με την τιμή '0'.
  2. Το δεύτερο shared memory segment είναι για N ακέραιους αριθμούς. Σε κάθε θέση σε αυτό το segment, ο server θα γράφει την τιμή 1 αν ο χαρακτήρας στην αντίστοιχη θέση του πρώτου shared memory segment είναι σωστή επιλογή, δηλαδή ο ίδιος χαρακτήρας με την αντίστοιχη θέση του string secret. Αλλιώς η τιμή σε εκείνη την θέση θα παραμένει ίση με 0. Επίσης, οι τιμές σε αυτό το segment αρχικοποιούνται με 0.
  3. Στο τρίτο shared memory segment ο server θα πρέπει να τοποθετήσει και να αρχικοποιήσει σωστά (με την συνάρτηση sem_init()) έναν αριθμό από 2*M semaphores: δύο semaphores για κάθε thread (αν θέλετε μπορείτε να δημιουργήσετε και τέταρτο shared memory segment με semaphores).
  Για να δημιουργήσει κάθε ένα memory segment, ο server διαλέγει ένα κλειδί με τυχαίο τρόπο (αν για κάποιο κλειδί αποτύχει η δημιουργία του shared memory segment, ο server θα πρέπει να διαλέξει ένα άλλο κλειδί τυχαία μέχρι να πετύχει). Μετά την δημιουργία και αρχικοποίηση των τριών shared memory segments, ο server στέλνει μέσω του UNIX socket που είναι συνδεδεμένος με τον client τις τιμές των τριών κλειδιών που χρησιμοποίησε για τα τρία segments, έτσι ώστε να μπορέσει ο client να κάνει attach τα ίδια memory segments και να μοιραστεί την ίδια μνήμη με τον server.
  
  Στην συνέχεια, ο server δημιουργεί Μ threads καλώντας την pthread_create(). Το κάθε thread είναι υπεύθυνο να διαβάζει ένα μέρος από το πρώτο shared memory segment και να γράφει στο αντίστοιχο μέρος του δεύτερου segment, που θα αντιστοιχεί σε Ν/Μ χαρακτήρες. Οπότε το κάθε thread θα παρακολουθεί συνεχώς το αντίστοιχο μέρος από το πρώτο shared memory segment και θα συγκρίνει κάθε έναν από τους Ν/Μ χαρακτήρες με τους αντίστοιχους χαρακτήρες του string secret. Έτσι, θα γράφει τις αντίστοιχες τιμές 0 ή 1 στο δεύτερο memory segment ανάλογα με το αν η επιλογή του client για κάθε χαρακτήρα είναι σωστή ή οχι. Πρέπει όμως να συγχρονιστούν τα threads από τις δύο διεργασίες (του client και του server): όταν ένα client thread γράφει τις επιλογές του στο πρώτο memory segment, το αντίστοιχο server thread δεν θα πρέπει να μπορεί να διαβάσει. Αντίστοιχα, όταν το server thread γράφει στο δεύτερο shared memory segment, το αντίστοιχο client thread θα πρέπει να περιμένει να τελειώσει το server thread για να διαβάσει τις σωστές τιμές. Για να πετύχετε τον σωστό συγχρονισμό θα πρέπει να χρησιμοποιήσετε semaphores: δύο semaphores για κάθε ζευγάρι client thread-server thread, για το αντίστοιχο μέρος του string και του κάθε memory segment.
  
  Όταν ο server διαπιστώσει ότι ο client έχει βρεί όλους τους Ν χαρακτήρες, θα πρέπει να το τυπώνει και να σταματάει την παραπάνω διαδικασία. Επίσης, ο server θα πρέπει να μετράει τον χρόνο που πήρε σε έναν client να μαντέψει το string secret και να τον τυπώνει μόλις ο client μαντέψει ολόκληρο το string. Τέλος, ο server θα κλείνει την σύνδεση με τον client με το UNIX socket. Τότε θα εκτυπώνει οτι έκλεισε η σύνδεση και θα αποδεσμεύει σωστά τα τρια shared memory segments.
  
  
• Υλοποίηση του client: Ο client θα λαμβάνει ένα όρισμα από την γραμμή εντολών: τον αριθμό από threads Μ που θα χρησιμοποιήσει. Στο παρακάτω παράδειγμα ο client θα δημιουργήσει Μ=10 threads:
  
  ./client 10
  
  Αρχικά, ο client θα συνδέεται με ένα UNIX socket με τον server (με κλήσεις συστήματος socket() και connect()) και θα του στέλνει τον αριθμό των threads Μ που έδωσε ο χρήστης από το command line (κλήση send()). Έπειτα, θα διαβάζει από το socket (κλήση συστήματος recv()) το αριθμό των χαρακτήρων Ν του string secret και τα τρία κλειδιά για τα shared memory segments, τα οποία θα κάνει attach (επίσης με τις κλήσεις σε shmget() και shmat()). Στην συνέχεια, ο client θα δημιουργεί Μ threads καλώντας την pthread_create() αντίστοιχες φορές. Το κάθε thread θα προσπαθεί να μαντέψει N/Μ χαρακτήρες. Άν είχαμε μόνο ένα thread, ο client θα προσπαθούσε να μαντέψει τους Ν χαρακτήρες με τον παρακάτω τρόπο:

  for (i=0; i<N; i++) {
  	for(j='A'; j<='z'; j++) {
  		choice[i]=j;
  		//sync with server to check whether this choice is correct
  		//and wait for server's response in valid[i]
  		if (valid[i]==1) break;		//found it
  	}
  }		
  

  Σε αυτήν την άσκηση όμως έχουμε Μ threads, οπότε προσπαθούμε να μαντέψουμε παράλληλα τους Ν χαρακτήρες χωρίζοντας τους σε Μ groups, ένα για κάθε thread. Οπότε θα πρέπει να αλλάξετε την παραπάνω λύση. Το κάθε thread του client θα πρέπει να θυμάται τις λανθασμένες επιλογές που έχει κάνει σε κάθε θέση του string ώστε να μην τις δοκιμάσει ξανά. Επίσης, ο server θα έχει τον ίδιο αριθμό από threads, όπου κάθε ένα θα εξετάζει τις επιλογές για το αντίστοιχο group από χαρακτήρες που προσπαθεί να μαντέψει κάποιο από τα threads του client.
  
  Κάτι άλλο που θα πρέπει να προσέξετε είναι ο συγχρονισμός μεταξύ server και client threads. Ένα client thread θα πρέπει να δίνει την ευκαιρία στο αντίστοιχο server thread να εξετάσει τις καινούργιες του επιλογές που είναι σε ένα μέρος του πρώτου shared memory segment, και να περιμένει την απάντηση του server thread στο αντίστοιχο μέρος του δεύτερου shared memory segment. Για αυτό το λόγο, κάθε client thread θα πρέπει να μοιράζεται δυο semaphores με ένα server thread, και να τις χρησιμοποιούν κατάλληλα για να λύσουν το παραπάνω πρόβλημα. Μπορείτε να χρησιμοποιήσετε επιπλέον semaphores ή mutexes αν χρειαστεί να εξασφαλίσετε οτι τα threads που μοιράζονται κοινή μνήμη μεταξύ τους δεν έχουν race conditions.
  
  Τέλος, όταν ο client διαπιστώσει οτι έχει μαντέψει σωστά όλους τους Ν χαρακτήρες, τυπώνει το string secret και τον χρόνο που του πήρε για να τους μαντέψει (τον οποίο θα πρέπει να μετράει), κάνει detach τα shared memory segments, κλείνει την σύνδεση του με τον server, και τερματίζει την λειτoυργία του.
  
  
• Μετρήσεις: Θα πρέπει να μετρήσετε τον χρόνο που παίρνει στον client να μαντέψει το string secret για διαφορετικές τιμές του Ν και του Μ. Οπότε θα πρέπει να μεταβάλετε το μέγεθος του string (π.χ., από 1000 χαρακτήρες μέχρι 1,000,000 χαρακτήρες) και τον αριθμό των threads (π.χ., από 1 thread μέχρι 100 threads), και για κάθε ζευγάρι τιμών που θα δοκιμάσετε να επαναλάβετε τις μετρήσεις αρκετές φορές υπολογίζοντας τελικά την μέση τιμή του χρόνου που χρειάζεται για να μαντέψουν Μ threads N χαρακτήρες. Συμπεριλάβετε στην αναφορά σας συνοπτικά ένα πίνακα ή ένα γράφημα με τα αποτελέσματα από τις μετρήσεις σας και εξηγήστε σύντομα αυτά τα αποτελέσματα και τα συμπεράσματά σας.

socket(2)
bind(2)
listen(2)
accept(2)
connect(2)
read(2)
recv(2)
send(2)
write(2)
shutdown(2)
close(2)
shmget(2)
shmat(2)
shmctl(2)
shmdt(2)
pthread_create(3)
pthread_join(3)
pthread_exit(3)
sem_init(3)
sem_destroy(3)
sem_post(3)
sem_wait(3)
sem_getvalue(3)
pthread_mutex_lock(3)
pthread_mutex_unlock(3)
pthread_mutex_init(3)
pthread_mutex_destroy(3)
 

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

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