Επόμενο:5.2 Κλειδώματα Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων

5.1 Ατομικές Λειτουργίες

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

Για παράδειγμα ας υποθέσουμε ότι η μεταβλητή Χ έχει την τιμή 20 και ότι δυο διεργασίες προσπαθούν να προσπελάσουν την Χ παράλληλα : η διεργασία Α επιχειρεί να διαβάσει την τιμή της Χ και η διεργασία Β θέλει να δώσει την νέα τιμή 30 στην Χ. Ο ελεγκτής της μνήμης εγγυάται ότι οι λειτουργίες της ανάγνωσης και της εγγραφής θα διατηρήσουν την ακεραιότητά τους - είτε θα συμβεί πρώτα η ανάγνωση και κατόπιν η εγγραφή ή το αντίθετο. Με αυτόν τον τρόπο η τιμή της Χ θα είναι 30 και η διεργασία Α θα διαβάσει την τιμή 20 ή 30. Θα ήταν σίγουρα λάθος αν οι λειτουργίες της ανάγνωσης και της εγγραφής συγκρούονταν μεταξύ τους με τέτοιο τρόπο ώστε η διεργασία Α να λάβει ως αποτέλεσμα της ανάγνωσης κάποια τιμή ανάμεσα στο 20 και το 30, π.χ. 25.

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

n := n + 1 ;

Η δήλωση αυτή στην αρχή προκαλεί την ανάγνωση της n (για να γνωστοποιηθεί η παλιά της τιμή) και στην συνέχεια η εγγραφή της νέας τιμής της μεταβλητής. Η ανάγνωση και η εγγραφή αποτελούν λογικά τμήμα της ίδιας λειτουργίας, είναι όμως δυνατό άλλες παράλληλες διεργασίες να επιχειρήσουν να προσπελάσουν τη n ανάμεσα στην ανάγνωση και την εγγραφή. Για παράδειγμα, έστω δυο διεργασίες οι Α και Β, που προσπαθούν να αυξήσουν την τιμή της n χρησιμοποιώντας δηλώσεις όπως η παραπάνω. Αν η αρχική τιμή της n είναι 20, τότε το τελικό αποτέλεσμα θα είναι 22. Όμως, έστω ότι η Α διαβάζει την τιμή της μεταβλητής, που είναι 20, και η Β διαβάζει επίσης την τιμή 20, πριν δηλαδή η Α προλάβει να αλλάξει την τιμή της n. Στην περίπτωση αυτή η Α προσθέτει 1 στην τιμή της n και το αποτέλεσμα που επιστρέφει είναι 21. Με τον ίδιο τρόπο η Β προσθέτει 1 στην τιμή της μεταβλητής και το αποτέλεσμα είναι 21. Έχουμε δηλαδή τελικά το εσφαλμένο αποτέλεσμα 21, αντί του σωστού 22. Αυτό το σενάριο παρουσιάζεται στο σχήμα 5.1.

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

Σαν ένα παράδειγμα του πως μπορεί να εμφανιστεί ένα τέτοιο λάθος σε ένα πρόγραμμα δίνουμε το παρακάτω πρόγραμμα, που αναζητά μια συγκεκριμένη τιμή σε έναν πίνακα και αποθηκεύει το συνολικό αριθμό εμφανίσεων της τιμής αυτής :

PROGRAM Search;
VAR   A : ARRAY [1..200] OF INTEGER;
      i, val, n : INTEGER;

BEGIN

.....

n := 0;
Readln(val);
FORALLL i := 1 TO 200 GROUPING 10 DO
  IF A[i] = VAL THEN n := n + 1;
WRITELN(‘Total occurrences : ‘ , n);

.....

Κάθε παράλληλη διεργασία που θα δημιουργηθεί από τη δήλωση FORALLL θα ψάχνει σε διαφορετικό τμήμα του πίνακα για την τιμή της μεταβλητής val. Κάθε φορά που θα συναντάται η τιμή αυτή θα αυξάνεται και η τιμή του μετρητή n. Όμως το πρόγραμμα αυτό καταλήγει σε λάθος όταν ο αριθμός εμφάνισης της val είναι μεγάλος και έτσι μπορεί να παρέμβουν δυο διεργασίες για την αύξηση του μετρητή.

ΣΧΗΜΑ 5.1 Λάθος σε διαμοιραζόμενα δεδομένα

Το παραπάνω πρόβλημα είναι δυνατόν να εξαλειφθεί με τη χρησιμοποίηση ενός κλειδώματος. Σε κάθε δεδομένη στιγμή κατά τη διάρκεια εκτέλεσης του προγράμματος, το κλείδωμα βρίσκεται σε μια κατάσταση : ενεργοποιημένη (locked) ή απενεργοποιημένη (unlocked). Για τη μετάβαση από τη μια κατάσταση στην άλλη υπάρχουν δυο απλές λειτουργίες: κλείδωμα ή ξεκλείδωμα Η λειτουργία του κλειδώματος έχει μια σημαντική ιδιότητα: αν το κλείδωμα είναι ήδη ενεργοποιημένο τότε η διεργασία αυτόματα περιμένει μέχρι να ξεκλειδωθεί από κάποια άλλη διεργασία. Με αυτόν τον τρόπο το κλείδωμα παρέχει έναν μηχανισμό καθυστέρησης μιας διεργασίας από μια άλλη. Μπορούμε έτσι να έχουμε ένα νέο πρόγραμμα Search:

PROGRAM Search;
VAR  A : ARRAY [1..200] OF INTEGER;
     i, val, n : INTEGER;
     L : SPINLOCK;

BEGIN

.....

n := 0;
Readln(val);
FORALLL i := 1 TO 200 GROUPING 10 DO
  IF A[i] = VAL THEN 
	BEGIN
  	 Lock(L);  (*Εισέρχεται και ενεργοποιεί το κλείδωμα*)
  	 n := n + 1;
  	 Unlock(L);  (*Εξέρχεται και απενεργοποιεί το κλείδωμα*)
	END;
WRITELN(‘Total occurrences : ‘ , n);

.....

Στο παραπάνω πρόγραμμα κάθε διεργασία πρέπει να εκτελέσει την lock(L) πριν τη μεταβολή της n. Όταν μια διεργασία εκτελεί την lock(L) τότε όλες οι άλλες διεργασίες θα βρουν την L κλειδωμένη και αν κάποια επιχειρήσει να πραγματοποιήσει τη δική της λειτουργία κλειδώματος τότε θα αναγκαστεί να περιμένει. Τελικά, η πρώτη διεργασία θα ολοκληρώσει την εντολή n := n + 1 και θα εκτελέσει την Unlock(L). Έτσι, το κλείδωμα L θα απενεργοποιηθεί και αν υπάρχει κάποια διεργασία που περιμένει στην εντολή lock(L) θα “περάσει” ενεργοποιώντας το κλείδωμα και πάλι. Με αυτόν τον τρόπο το κλείδωμα εγγυάται ότι μόνο μια διεργασία κάθε φορά μπορεί να αλλάξει την τιμή της μεταβλητής n διασφαλίζοντας και την σωστή εκτέλεση του προγράμματος.

Η λειτουργία του κλειδώματος παρουσιάζεται στο σχήμα 5.2. Οι λειτουργίες lock(L) και Unlock(L) δημιουργούν ένα είδος φράγματος γύρω από την εντολή n:=n+1, έτσι ώστε μόνο μια διεργασία κάθε φορά να είναι μέσα στο φράκτη για να μετατρέψει το n. Ο χρόνος κυλά από την κορυφή προς τη βάση του σχήματος δείχνοντας τα διαδοχικά στάδια της όλης διαδικασίας. Στην κορυφή του σχήματος η διεργασία P5 είναι η πρώτη που που φτάνει και βρίσκει το κλείδωμα απενεργοποιημένο. Όταν η διεργασία P5 εκτελεί την λειτουργία lock(L) υπάρχουν δύο αποτελέσματα : η διεργασία εισέρχεται και το κλείδωμα ενεργοποιείται. Στο επόμενο βήμα η διεργασία P5 εκτελεί την εντολή n := n + 1. Όσο συμβαίνει αυτό τρεις επιπλέον διεργασίες εκτελούν την λειτουργία του κλειδώματος προσπαθώντας να περάσουν μέσα, η P1, P2 και η P7. Εφόσον το κλείδωμα είναι ενεργοποιημένο, και οι τρεις διεργασίες αυτόματα θα σταματήσουν να εκτελούνται. Τελικά, η διεργασία P5 εξέρχεται εκτελώντας την λειτουργία Unlock(L). Με τον τρόπο αυτό το κλείδωμα απενεργοποιείται ξανά. Έτσι, οι διεργασίες μπορούν να μετατρέψουν τη μεταβλητή n μια κάθε φορά.

ΣΧΗΜΑ 5.2 Η επίδραση του κλειδώματος

Η λειτουργία της αύξησης μια μεταβλητής όπως αυτή φαίνεται στο πρόγραμμα Parallel Search αποτελεί ένα συγκεκριμένο παράδειγμα μιας σημαντικής έννοιας του παράλληλου προγραμματισμού: της ατομικής λειτουργίας. Μια ατομική λειτουργία πραγματοποιείται από μια και μόνη παράλληλη διεργασία και δεν μπορεί να διακοπεί από κάποια άλλη. Η αύξηση της τιμής της μεταβλητής n στο παραπάνω πρόγραμμα είναι ένα παράδειγμα λειτουργίας που πρέπει να είναι ατομική, έτσι ώστε το πρόγραμμα να δουλέψει σωστά. Άλλα παράλληλα προγράμματα μπορεί να έχουν πιο πολύπλοκες ατομικές λειτουργίες που συμπεριλαμβάνουν ανάγνωση και εγγραφή πολλών διαφορετικών μεταβλητών.

Κάθε παράλληλη γλώσσα προγραμματισμού έχει ειδικά χαρακτηριστικά που βοηθούν στη δημιουργία ατομικών λειτουργιών. Παραδείγματα τέτοιων χαρακτηριστικών αποτελούν οι σηματοφορείς (semaphores) [Dijkstra, 1968a, 1968b], τα κλειδώματα (locks) [Shaw, 1948], οι κρίσιμες περιοχές (critical regions) [Brinch Hansen, 1983] και οι επόπτες (monitors) [Hoare, 1974]. Σε κάθε περίπτωση ο σκοπός αυτών των χαρακτηριστικών είναι να επιτρέπουν σε μια διεργασία τη δυνατότητα πρόσβασης και μετατροπής κάποιων διαμοιραζομένων δεδομένων, ενώ την ίδια στιγμή απαγορεύουν σε άλλες την εγγραφή ή την ανάγνωση αυτών των δεδομένων μέχρι το τέλος της μετατροπής. Αυτή η απαίτηση αποτελεί και αυτό που ονομάζουμε στον παράλληλο προγραμματισμό πρόβλημα του αμοιβαίου αποκλεισμού: η χρήση κάποιων διαμοιραζομένων δεδομένων από μια διεργασία πρέπει να αποκλείσει την πρόσβαση των υπόλοιπων διεργασιών. Ο αποκλεισμός αυτός εγγυάται και το ότι η λειτουργία που διενεργείται είναι ατομική.

Επόμενο:5.2 Κλειδώματα Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων