5.2 Κλειδώματα

Επόμενο:5.3 Ανταγωνισμός για Διαμοιραζόμενα Δεδομένα Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: 5.1 Ατομικές Λειτουργίες

5.2 Κλειδώματα

5.2.1 Υλοποίηση των κλειδωμάτων

Για να γίνει κατανοητή η επίδραση του κλειδώματος στην όλη διαδικασία του παράλληλου προγραμματισμού είναι απαραίτητη η γνώση του πως υλοποιούνται σε ένα σύστημα μοιραζόμενης μνήμης. Ο σημαντικότερος στόχος της υλοποίησης είναι η επίτευξη της καθυστέρησης των διεργασιών όταν αυτές επιχειρούν να ενεργοποιήσουν ένα κλείδωμα που είναι ήδη ενεργοποιημένο. Στα περισσότερα συστήματα διαμοιραζόμενης μνήμης αυτό επιτυγχάνεται με μια μορφή διεργασίας καθυστέρησης που ονομάζεται ενεργός αναμονή (busy waiting): η διεργασία κατά κάποιο τρόπο εκτελείται, αλλά ταυτόχρονα εγκλωβίζεται σε ένα μικρό βρόχο που ελέγχει την κατάσταση του κλειδώματος. Για όσο χρονικό διάστημα το κλείδωμα είναι ενεργοποιημένο η διεργασία βρίσκεται μέσα στον βρόχο. (Από αυτή την κατάσταση αναμονής πηγάζει και το όνομα του spinlock : οι διεργασίες αναγκάζονται να καθυστερούν εκτελώντας κάποιον βρόχο - spin -ενώ περιμένουν την αλλαγή της κατάστασης κλειδώματος - lock).

Το κλείδωμα από μόνο του μπορεί να υλοποιηθεί σαν μια μεταβλητή που σχετίζεται με μια συνηθισμένη θέση μνήμης. Η τιμή 0 αναπαριστά την κατάσταση ξεκλειδώματος, ενώ η τιμή 1 την κατάσταση κλειδώματος. Η λειτουργία Unlock(L) πραγματοποιείται εύκολα γράφοντας ένα 0 στη θέση μνήμης :

Unlock(L): Write 0 into L;

Η λειτουργία lock(L) είναι λίγο πιο πολύπλοκη γιατί πρέπει το κλείδωμα να ελεγχθεί και να μετατραπεί. Η λειτουργία αυτή συνήθως πραγματοποιείται με τη βοήθεια μιας ειδικής εντολής μηχανής που ονομάζεται “TestandSet”. Η εντολή αυτή επιστρέφει την τρέχουσα τιμή της θέσης μνήμης και επίσης τη θέτει και ίση με 1. Αυτές οι δυο φάσεις της εντολής εκτελούνται από τον επεξεργαστή κατά έναν τρόπο που δεν μπορεί να διακοπεί. Όταν εκτελείται η εντολή TestandSet από έναν επεξεργαστή τότε και οι δύο φάσεις test και set εκτελούνται μαζί από το υλικό, χωρίς καμία πιθανότητα παρέμβασης από άλλους επεξεργαστές. Η ατομική φύση της εντολής αυτής είναι σημαντικότατη όσον αφορά τη σχέση της στην ολοκλήρωση του κλειδώματος. Η λειτουργία lock(L) πραγματοποιείται γράφοντας :

Lock(L) :
	
Repeat
	X:=TestandSet(L); 	(*Διαβάζεται η παλιά κατάσταση και ενεργοποιείται το κλείδωμα*)
until X=0;  	 		(*Σταματά η επανάληψη του βρόχου αν το L είναι απενεργοποιημένο*)

Η παραπάνω εντολή TestandSet διαβάζει την τρέχουσα τιμή της κατάστασης του κλειδώματος, δηλαδή την L, και αποθηκεύει την τιμή αυτή σε μια μεταβλητή X. Καθώς η τιμή L έχει διαβαστεί, λαμβάνει την τιμή 1 η οποία σημαίνει ότι το κλείδωμα έχει ενεργοποιηθεί. Έτσι, το X έχει την παλιά τιμή του κλειδώματος. Πρέπει όμως να λάβουμε υπόψη μας δυο βασικά θέματα που σχετίζονται με αυτή την υλοποίηση. Πρώτον, έστω ότι το κλείδωμα είναι αρχικά απενεργοποιημένο, η εντολή TestandSet θα διαβάσει την τιμή τιμή 0, θα την δώσει στην μεταβλητή X και θα ενεργοποιήσει το κλείδωμα. Με τον τρόπο αυτό ο βρόχος σταματά να εκτελείται. Όμως οι άλλες διεργασίες θα βρουν τώρα κλείδωμα ενεργοποιημένο και όταν κάποια από αυτές εκτελέσει την λειτουργία Lock(L) θα εκτελέσει και την εντολή TestandSet. Έτσι όμως η μεταβλητή X θα λάβει την τιμή 1 (που είναι η τρέχουσα τιμή του κλειδώματος) και όλες οι επόμενες διεργασίες που θα μπαίνουν στην λειτουργία Lock(L) θα περιμένουν μέσα στο βρόχο.

Τελικά η πρώτη διεργασία που “πέρασε” στη λειτουργία Lock(L) θα εκτελέσει και την λειτουργία Unlock(L) και συνεπώς η τιμή του κλειδώματος θα αλλάξει σε 0. Στη συνέχεια, αν υπάρχουν αλλές διεργασίες που βρίσκονται σε αναμονή μέσα σε βρόχο, τότε η πρώτη από αυτές θα εκτελέσει την εντολή TestandSet, θα διαβάσει την τιμή 0 του L, αλλά αμέσως θα την θέσει ίση με 1 και θα εξέλθει από το βρόχο της. Οι υπόλοιπες διεργασίες θα δουν ότι το κλείδωμα είναι ενεργοποιημένο ξανά και θα συνεχίσουν τους βρόχους τους. Με τον τρόπο αυτό πολλοί επεξεργαστές καθυστερούν μέσα στη λειτουργία Lock(L) και μόνο ένας κάθε φορά μπαίνει στην εκτέλεση της Unlock(L).

5.2.2. Τύποι δεδομένων και κλειδώματος

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

Ο τύπος δεδομένων SPINLOCK μπορεί να οργανωθεί σε δομημένους τύπους - τους πίνακες και τις εγγραφές. Με τον ίδιο τρόπο που κάποιος μπορεί να έχει έναν “Array of Integer” ή έναν “Array of Boolean” μπορεί να έχει και έναν “Array of Spinlock”. Η δεικτοδότηση τέτοιων πινάκων ακολουθεί τους ίδιους κανόνες της standard Pascal που αφορούν τη δεικτοδότηση πινάκων. Έστω, για παράδειγμα οι παρακάτω δηλώσεις :

VAR  G : ARRAY [1..10] OF SPINLOCK;
     H : ARRAY [1..10, 1..10] OF SPINLOCK;

Οι παρακάτω λειτουργίες είναι έγκυρες όσον αφορά τους παραπάνω πίνακες :

Lock(G[3]);
Unlock(H[1,5]);


i:=2;
Lock(G[i]);
Unlock(G[i+5]);

Όμοια, ο τύπος δεδομένων SPINLOCK μπορεί να χρησιμοποιηθεί και ως τμήμα μιας εγγραφής, όπως φαίνεται και παρακάτω :

VAR item: RECORD
    data: Integer;
    L: Spinlock;
END;

Για τη συγκεκριμένη δήλωση εγγραφής μπορούμε να έχουμε :

Lock(item,L);
Unlock(item.L);

Επίσης, οι δείκτες μπορούν να συνδιαστούν με κλείδωμα. Στην Pascal ένας δείκτης μπορεί να δηλωθεί έτσι ώστε να δείχνει σε οποιοδήποτε τύπο δεδομένων. Ο ίδιος κανόνας ισχύει και στην Multi-Pascal. Έτσι, μπορούμε να έχουμε :

TYPE	itempnt=^itemtype;
itemtype=Record
  data: Integer;
  L: Spinlock;
  next: itempnt;
         END;

VAR head: itempnt;

Με τις παραπάνω δηλώσεις μπορούμε να δημιουργήσουμε μια συνδεδεμένη λίστα της οποίας κάθε στοιχείο έχει το δικό του κλείδωμα. Τα κλειδώματα μπορούν επίσης να χρησιμοποιηθούν ως παράμετροι διαδικασιών ή συναρτήσεων και να συμπεριφερθούν όπως και οι υπόλοιπες παράμετροι της standard Pascal. Χρησιμοποιώντας ένα κλείδωμα ως μια παράμετρο VAR, θα έχει ως αποτέλεσμα το όνομα της παραμέτρου να γίνει ένα ψευδώνυμο για το κλείδωμα που χρησιμοποιείται σαν δήλωση στην κλήση της διαδικασίας. Χρησιμοποιώντας ένα κλείδωμα σαν παράμετρο τιμής θα πάρουμε ως αποτέλεσμα ένα αντίγραφο της κατάστασής του κατά την κλήση της διαδικασίας.