Επόμενο:5.6 Περίληψη Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: 5.4 Αριθμητική Ολοκλήρωση

5.5 Συγκρίνοντας το Κλείδωμα και τα Κανάλια

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

5.5.1 Αντίστοιχη ισχύς

Ένα κλείδωμα έχει τη δυνατότητα να δημιουργεί ατομικές λειτουργίες γιατί μπορεί να “αναγκάζει” κάθε διεργασία να περιμένει σε μια κατάσταση κλειδώματος. Αυτό είναι και το στοιχειώδες χαρακτηριστικό στην εφαρμογή του κλειδώματος : η αναμονή των διεργασιών με τη λειτουργία του κλειδώματος και η είσοδος μόνο μιας από αυτές μετά την πραγματοποίηση της λειτουργίας του ξεκλειδώματος. Τα κανάλια έχουν και αυτά τη δυνατότητα να κάνουν μια διεργασία να περιμένει: όταν ένα κανάλι είναι άδειο η διεργασία ανάγνωσης περιμένει μέχρι να γραφτεί κάτι στο κανάλι. Ο μηχανισμός αυτός μπορεί να χρησιμοποιηθεί για τη δημιουργία ατομικών λειτουργιών.

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

Με την ίδια λογική, τα κανάλια μπορούν να προσομοιωθούν με τη βοήθεια κλειδωμάτων. Το κλείδωμα μπορεί να χρησιμοποιηθεί για τη δημιουργία ουράς επικοινωνίας διεργασιών. Ένα κανάλι είναι απλά μια FIFO ουρά παράλληλης προσπέλασης: η εγγραφή σε ένα κανάλι προσθέτει ένα στοιχείο στο τέλος της ουράς και η ανάγνωση από την ουρά αφαιρεί ένα στοιχείο από την κεφαλή της ουράς. Χρησιμοποιώντας κλείδωμα για την εγγύηση ότι οι τροποποιήσεις είναι ατομικές, είναι δυνατή η κατασκευή μιας ουράς παράλληλης προσπέλασης που λειτουργεί σαν κανάλι. Περισσότερες λεπτομέρειες αυτής της εφαρμογής αναφέρονται στις ασκήσεις στο τέλος του κεφαλαίου.

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

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

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

5.5.2. Ενεργός Αναμονή εναντίον Αναστολής

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

Επίσης, τα κανάλια προκαλούν μια διεργασία να περιμένει όταν αυτή προσπαθεί να διαβάσει ένα άδειο κανάλι. Όταν κάποια διεργασία εκτελεί μια λειτουργία ανάγνωσης σε ένα κενό κανάλι, η εκτέλεσή της αναστέλλεται μέχρι κάποια άλλη διεργασία να γράψει στο κανάλι. Αυτό επιτυγχάνεται με την εισαγωγή της διεργασίας ανάγνωσης σε μια σταματημένη κατάσταση, έτσι ώστε να μην μπορεί να εκτελεστεί από τον επεξεργαστή. Η εκτέλεση της διεργασίας σταματά εντελώς, αφήνοντας τον επεξεργαστή ελεύθερο να ασχοληθεί με κάτι άλλο, π.χ. να εκτελέσει άλλες διεργασίες για κάποιο χρονικό διάστημα. Όταν τελικά μια διεργασία εγγραφής γράψει κάτι στο κανάλι η σταματημένη διεργασία ανάγνωσης θα καταστεί έτοιμη προς εκτέλεση. Η αλλαγή αυτή στην κατάσταση της διεργασίας ειδοποιεί τον επεξεργαστή ότι τώρα μπορεί να αρχίσει να την εκτελεί ξανά.

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

Για διακρίνουμε καθαρά μεταξύ της ενεργού αναμονής και της αναστολής στη Multi-Pascal, η κατάσταση της κάθε διεργασίας είναι μια από τις παρακάτω: εκτελούμενη (running), καθυστερούμενη (spinning), σταματημένη (blocked), έτοιμη (ready). Η εκτελούμενη δηλώνει ότι η τρέχουσα διεργασία είναι αυτή που εκτελείται από τον επεξεργαστή. Η καθυστερούμενη ότι η διεργασία καθυστερείται μέσα σε μία λειτουργία κλειδώματος. Η σταματημένη ότι η διεργασία περιμένει να διαβάσει από ένα κενό κανάλι ή, στην περίπτωση γονικής διεργασίας, περιμένει την λήξη των διεργασιών-παιδιών. Τέλος, η έτοιμη διεργασία μπορεί να εκτελεστεί, αλλά δεν εκτελείται την τρέχουσα χρονική στιγμή από τον επεξεργαστή της, γιατί κάποια άλλη διεργασία εκτελείται σε αυτόν.

5.5.3. Σηματοφορείς

Κατά τις δυο τελευταίες δεκαετίες έρευνες πάνω στον παράλληλο προγραμματισμό έχουν ανακαλύψει έναν αριθμό στοιχειωδών λειτουργιών για το συντονισμό της δραστηριότητας των παράλληλων διεργασιών και την εγγύηση της ατομικής πρόσβασης στις δομές των διαμοιραζόμενων δεδομένων. Η πιο γνωστή αλλά και παλιότερη δομή είναι ο σηματοφορέας, που αρχικά προτάθηκε από τον Dijkstra [1968a]. Ένας σηματοφορέας είναι μια μεταβλητή τύπου integer και περιορίζεται μόνο σε θετικές ακέραιες τιμές. Υπάρχουν δυο λειτουργίες που διενεργούνται πάνω σε σηματοφορείς: το σήμα (signal) και η αναμονή (wait) που ορίζονται με τον τρόπο που φαίνεται παρακάτω:

For a semaphore S.


Wait(S): IF S > 0 THEN S := S + 1
         ELSE suspend execution and wait for Signal operation on S.


Signal(S): IF a process is waiting on S, THEN release the process
           ELSE S := S + 1;

Και οι δύο αυτές λειτουργίες μέσα από την υλοποίηση της γλώσσας εγγυώνται την ατομικότητά τους. Ένας σηματοφορέας μπορεί να χρησιμοποιηθεί για την εγγύηση της ατομικής πρόσβασης σε δομές διαμοιραζόμενων δεδομένων μέσα από τη λειτουργία Wait(S) - από την οποία αρχίζει η πρόσβαση στα διαμοιραζόμενα δεδομένα - και τη λειτουργία Signal(S) - μετά την οποία η πρόσβαση σταματά. Η αρχικοποίηση της τιμής του S σε 1, εγγυάται ότι μόνο μια διεργασία κάθε χρονική στιγμή έχει πρόσβαση στα διαμοιραζόμενα δεδομένα. Η χρήση των σηματοφορέων είναι ιδιαίτερα δημοφιλής στο πεδίο σχεδιασμού των λειτουργικών συστημάτων.

Οι σηματοφορείς μπορούν πολύ εύκολα να προσομοιωθούν από τις μεταβλητές καναλιών της Multi-Pascal. Με την αντικατάσταση απλώς ενός σηματοφορέα με ένα κανάλι και χρησιμοποιώντας μια λειτουργία εγγραφής σε κανάλι για τη Signal και άλλη μια ανάγνωσης για τη Wait έχουμε :

TYPE Semaphore = CHANNEL OF INTEGER;


VAR S: Semaphore;


............


Procedure Wait (VAR S: Semaphore);
VAR dummy: integer;


BEGIN
dummy := S;	(*Ανάγνωση από το κανάλι*)
END;


Procedure Signal (VAR S: Semaphore);
BEGIN
S := 1;	(*Εγγραφή στο κανάλι*)
END;

Στην προσομοίωση σηματοφορέα με κανάλι η τιμή του σηματοφορέα αναπαρίσταται από τον αριθμό των αντικειμένων που βρίσκονται μέσαστο κανάλι. Κάθε Wait λειτουργία αφαιρεί και ένα αντικείμενο από το κανάλι, μειώνει δηλαδή και την τιμή του σηματοφορέα. Κάθε Signal λειτουργία προσθέτει ένα νέο στοιχείο στο κανάλι και αυξάνει έτσι την τιμή του σηματοφορέα. Αν μια Wait λειτουργία πραγματοποιηθεί σε ένα κενό κανάλι (η τιμή του σηματοφορέα είναι δηλαδή 0) τότε η εκτέλεση της διεργασίας σταματά με τη δήλωση dummy := S μέχρι να εκτελέσει κάποια άλλη διεργασία μια Signal και έτσι να προσθέσει ένα στοιχείο στο κανάλι.

Επόμενο:5.6 Περίληψη Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: 5.4 Αριθμητική Ολοκλήρωση