6.3 Γραμμικό Φράγμα

Επόμενο:6.4 Φράγμα Δυαδικού Δένδρου Πάνω: Κεφάλαιο 6o : Σύγχρονος παραλληλισμός Πίσω: 6.2. Παράλληλος Αλγόριθμος Jacobi

6.3 Γραμμικό Φράγμα

Η γλώσσα Multi-Pascal δεν έχει μια ρητή δήλωση για τα φράγματα. Όμως, τα φράγματα μπορούν να υλοποιηθούν πολύ εύκολα με τη χρήση κλειδώματος ή καναλιών. Μια υλοποίηση με κλειδώματα και μια άλλη χρησιμοποιώντας κανάλια παρουσιάζονται στις ακόλουθες παραγράφους. Σκοπός αυτής της ανάλυσης είναι η κατανόηση των μεθοδολογιών που χρησιμοποιούνται για την υλοποίηση των φραγμάτων και η πολυπλοκότητά τους. Οι τεχνικές που περιγράφονται είναι ιδιαίτερα γενικές και μπορούν να εφαρμοστούν με καθένα από τους καθιερωμένους μηχανισμούς που παρέχονται από τις άλλες παράλληλες γλώσσες, όπως είναι οι σηματοφορείς ή οι ελεγκτές. Κάποιες από τις ασκήσεις αυτού του κεφαλαίου ζητούν την υλοποίηση των εφαρμογών φράγματος με σηματοφορείς αντί για κλειδώματα ή κανάλια.

Όλες οι εφαρμογές φράγματος θα εκφραστούν σαν διαδικασίες της Multi-Pascal. Στο παράλληλο πρόγραμμα του αλγορίθου Jacobi του σχήματος 6.6, η λειτουργία φράγματος μπορεί απλά να θεωρηθεί σαν μια κλήση σε μια διαδικασία που ονομάζεται Barrier και η οποία πραγματοποιεί τη λειτουργία χρησιμοποιώντας χαρακτηριστικά της Multi-Pascal. Μια από τις πιο απλές τεχνικές είναι η χρήση μιας μεταβλητής αθροιστή για την καταγραφή του συνολικού αριθμού των διεργασιών που έχουν φτάσει μέχρι στιγμής στο φράγμα. Όταν ο αθροιστής φτάσει τον απαιτούμενο αριθμό, τότε όλες οι διεργασίες αφήνονται ελεύθερες και ο αθροιστής παίρνει ξανά την τιμή 0. Καθώς κάθε διεργασία εκτελεί τη διαδικασία Barrier, αυτή ελέγχει και αυξάνει έναν γενικό αθροιστή. Αν ο αθροιστής δεν έχει φτάσει στον αριθμό n τότε οι διεργασίες εισέρχονται σε μια κατάσταση καθυστέρησης μέσα στη διαδικασία Barrier. Καθώς οι διεργασίες σταδιακά φτάνουν στο φράγμα, θέτονται σε καθυστέρηση και ο αθροιστής αυξάνει. Τελικά η τελευταία διεργασία που φτάνει βρίσκει τον αθροιστή στον αριθμό n και τότε αφήνει ελεύθερες όλες τις διεργασίες.

Η διαδικασία Barrier θα έχει δυο ξεχωριστές φάσεις. Κατά τη διάρκεια της Φάσης Άφιξης οι διεργασίες αθροίζονται καθώς φτάνουν στο φράγμα. Όταν έχουν φτάσει όλες οι διεργασίες τελειώνει η Φάση Άφιξης και αρχίζει η Φάση Αναχώρησης. Στη Φάση Αναχώρησης οι διεργασίες αφήνονται ελεύθερες να περάσουν το φράγμα, μια κάθε φορά. Η άθροιση συμβαίνει επίσης και κατά τη διάρκεια της Φάσης Αναχώρησης, έτσι ώστε να γίνει γνωστό πότε θα αφεθούν ελεύθερες όλες οι διεργασίες. Για το διαχωρισμό της δραστηριότητας των δυο φάσεων χρησιμοποιούνται δυο κλειδώματα: Η Άφιξη και η Αναχώρηση. Κάθε κλείδωμα χρησιμοποιείται για να κάνει την άθροιση μια ατομική λειτουργία κατά τη διάρκεια των αντίστοιχων φάσεων. Η διαδικασία της Multi-Pascal για την εφαρμογή του φράγματος φαίνεται παρακάτω:

PROGRAM JacobiBarrier;


CONST n = 32;


VAR ........


    count : Integer;


    Arrival, Departure : Spinlock;


PROCEDURE Barrier;


BEGIN


    (*Φάση Άφιξης - Άθροιση των διεργασιών καθώς εισέρχονται*)


    Lock(Arrival);


    count := count + 1;


    If count < n 


        then Unlock(Arrival) (*Συνέχιση της Φάσης Άφιξης*)


    else Unlock(Departure); (*Τέλος της Φάσης Άφιξης*)


    (*Φάση Αναχώρησης - Άθροιση των διεργασιών καθώς εξέρχονται*)


    Lock(Departure);


    count := count - 1;


    If count > 0 


        then Unlock(Departure) (*Συνέχιση της Φάσης Αναχώρησης*)


    else Unlock(Arrival); (*Τέλος της Φάσης Αναχώρησης*)


END;


BEGIN (*Κυρίως Πρόγραμμα*)


    count := o; (*Αρχικοποίηση της μεταβλητής count και των κλειδωμάτων*)


    Unlock(Arrival);


    Lock(Departure);


    .........


END.

ΣΧΗΜΑ 6.7 Εφαρμογή φράγματος με κλείδωμα.

Το πιο ενδιαφέρον χαρακτηριστικό της διαδικασίας φράγματος είναι η ασυνήθιστη χρήση της λειτουργίας απενεργοποίησης του κλειδώματος στο τέλος κάθε ατομικής λειτουργίας. Μπορούμε να δούμε από το πρόγραμμα ότι και η Φάση Άφιξης και η Φάση Αναχώρησης ξεκινούν με μια λειτουργία ενεργοποίησης κλειδώματος. Κατά τη διάρκεια της Φάσης άφιξης η μεταβλητή count αυξάνεται καθώς οι διεργασίες φτάνουν στο φράγμα. Κατά τη διάρκεια της Φάσης Αναχώρησης η ίδια μεταβλητή μειώνεται καθώς οι διεργασίες φεύγουν από το φράγμα. Όμως, πρέπει να υπάρχει κάποιος μηχανισμός που να εγγυάται ότι η Φάση Άφιξης ολοκληρώνεται πριν να αρχίσει η Φάση Αναχώρησης. Αυτό επιτυγχάνεται με το να διατηρείται κλειδωμένο το Departure κατά τη διάρκεια της Φάσης Άφιξης. Κάθε διεργασία που φτάνει στην αρχή της Φάσης Αναχώρησης θα “κολλήσει” στη δήλωση Lock(Departure), με τη οποία ξεκινά η Φάση Αναχώρησης. Όταν η τελευταία διεργασία φτάσει τελικά στη Φάση Άφιξης θα εκτελέσει την Unlock(Departure). Έτσι, θα απενεργοποιηθεί το κλείδωμα Departure και θα αρχίσει η εκτέλεση της Φάσης Αναχώρησης.

Για να δουλέψει σωστά αυτός ο διπλός μηχανισμός κλειδώματος πρέπει αρχικά να είναι απενεργοποιημένο το κλείδωμα Arrival και ενεργοποιημένο το Departure. Στο τέλος της διαδικασίας Barrier η τελευταία διεργασία που φεύγει από τη Φάση Αναχώρησης πρέπει να βεβαιωθεί ότι τα κλειδώματα έχουν οριστεί σωστά για το επόμενο φράγμα. Γι’ αυτό το λόγο όταν η τελευταία διεργασία φεύγει από τη Φάση Αναχώρησης, η οποία δηλώνεται θέτοντας την count ίση με 0, θα εκτελέσει την Unlock(Arrival). Μπορεί κάποιος να δει από το πρόγραμμα ότι στη αρχή της Φάσης Άφιξης έχουμε το κλείδωμα Arrival απενεργοποιημένο και το Departure ενεργοποιημένο, ενώ στην αρχή της Φάσης Αναχώρησης έχουμε το Arrival ενεργοποιημένο και το Departure απενεργοποιημένο. Αυτό το διπλό κλείδωμα είναι απαραίτητο στη διαδικασία αυτή για το διαχωρισμό των δυο φάσεων και τη διαβεβαίωση τι θα συμπεριφερθούν σωστά. Οι ασκήσεις που αφορούν την παράγραφο αυτή διερευνούν το θέμα περισσότερο.

Η απόδοση της υλοποίησης του φράγματος είναι περιορισμένη εξαιτίας του ανταγωνισμού για τη μεταβλητή count κατά τη διάρκεια των ατομικών λειτουργιών αύξησης και μείωσης. Χρησιμοποιώντας το σύστημα αλληλεπίδρασης της Multi-Pascal ορίζεται ότι κάθε ατομική λειτουργία απαιτεί περίπου 10 μονάδες χρόνου. Έτσι, ο συνολικός χρόνος για όλες τις n διεργασίες που θα αυξήσουν την count κατά τη διάρκεια της Φάσης Άφιξης είναι 10n. Όμοια, ο συνολικός χρόνος για τη Φάση Αναχώρησης είναι 10n. Έτσι, ο συνολικός χρόνος συγχρονισμού φράγματος για n διεργασίες είναι 20n. Ο υπολογισμός αυτός μπορεί να ποικίλει σε διαφορετικούς παράλληλους υπολογιστές, αλλά η άθροιση έχει πάντα χρόνο εκτέλεσης Ο(n).