Σημαφόρος (προγραμματισμός)

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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


Πίνακας περιεχομένων

[Επεξεργασία] Ορισμός

Για να απλοποιηθούν οι ρουτίνες που φροντίζουν τις ταυτόχρονες διεργασίες, ο Έντσγκερ Ντάικστρα (Edsger Dÿkstra) εισήγαγε την έννοια των σηματοφόρων. Ένας σηματοφόρος είναι μια ακέραιη μεταβλητή, την οποία μπορούν να εξετάσουν ή και να μεταβάλουν οι διάφορες διεργασίες.

Στον σηματοφόρο (έστω Sem1), εφαρμόζονται οι λειτουργίες P, (προέρχεται από την Ολλανδική λέξη proberen = να ελέγξεις), και V, (προέρχεται από την Ολλανδική λέξη verhogen = να αυξήσεις), που όρισε ο Ντάικστρα ως εξής:


αρχική τιμή Sem1 := 1
P(Sem1) while Sem1 <= 0 do skip;
Sem1 := Sem1 - 1;
V(Sem1) Sem1 := Sem1 + 1;


Οι εντολές P και V εκτελούνται αδιάκοπτα.

Η εντολή P λέει στην διεργασία «αν είναι η τιμή του Sem1 μικρότερη ή ίση με το μηδέν αδράνησε για λίγο, αλλιώς αφαιρείται 1 από την τιμή του Sem1 και μπορείς να συνεχίσεις». (Αυτό πετυχαίνει τον αμοιβαίο αποκλεισμό των διεργασιών).

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

Η εντολή V λέει στην διεργασία «προστίθεται 1 στην τιμή του Sem1 και μπορείς να συνεχίσεις».

Αν πολλές διεργασίες θέλουν να εκτελέσουν λειτουργίες P ή V για έναν σηματοφόρο Sem1, εκτελούνται όλες οι λειτουργίες με τυχαία σειρά. (Αυτό πετυχαίνει την ανεξαρτησία των διεργασιών).

Όταν ο σηματοφόρος παίρνει δυο τιμές μόνο (1 ή 0) λέγεται δυαδικός σηματοφόρος.

Τα προγράμματα των ταυτόχρονων διεργασιών γράφονται ανάμεσα από τις ειδικές εντολές, τις parbegin και parend:

  • parbegin, δηλαδή: εκκίνηση αναγραφής διεργασιών που εκτελούνται παράλληλα (< {parallel + begin} = {παράλληλα + εκκίνηση}),
  • || (δυο παράλληλες γραμμές), δηλαδή: ακολουθεί άλλη διεργασία, και
  • parend, δηλαδή: τερματισμός αναγραφής διεργασιών που εκτελούνται παράλληλα (< {parallel + end} = {παράλληλα + τερματισμός}).


[Επεξεργασία] Παράδειγμα αμοιβαίου αποκλεισμού

Έχουμε τρεις (μπορούν να είναι οσεσδήποτε) διεργασίες P1, P2, και P3, που αποκλείονται αμοιβαία. Χρησιμοποιούν έναν σηματοφόρο Sem1. Το πρόγραμμα που τις χειρίζεται είναι όπως παρακάτω:

Var Sem1 : semaphore;
Sem1:= 1;
parbegin
P1: repeat 
      μη ΚΤ1;  {αρχικό μη κρίσιμο τμήμα της P1}
      P(Sem1); {αίτηση να γίνει το Sem1 μηδενικό}
        KT1; {κρίσιμο τμήμα της διεργασίας P1}
      V(Sem1); {επαναφορά της τιμής του Sem1 στο 1}
      μη ΚΤ1;  {τελικό μη κρίσιμο τμήμα της P1}
    until false ||
P2: repeat 
      μη ΚΤ2; 
      P(Sem1); 
        KT2; 
      V(Sem1); 
      μη ΚΤ2;
    until false ||
P3: repeat 
      μη ΚΤ3; 
      P(Sem1); 
        KT3; 
      V(Sem1); 
      μη ΚΤ3;
    until false
parend

Όταν είναι ο σηματοφόρος Sem1=1, οποιαδήποτε διεργασία (με τυχαία σειρά) μπορεί να τον μηδενίσει, άρα οι διεργασίες δεν εμποδίζονται αμοιβαία.

Μόνο μία διεργασία μπορεί να μηδενίσει τον σηματοφόρο Sem1, και όταν το κάνει, (για να μπορέσει να εκτελέσει το κρίσιμο τμήμα της), οι άλλες αποκλείονται, άρα εξασφαλίζεται ο αμοιβαίος αποκλεισμός των διεργασιών.


[Επεξεργασία] Παράδειγμα μη δυαδικού σηματοφόρου

Υπάρχει τρόπος να δημιουργήσουμε έναν σηματοφόρο πολλών τιμών, (έστω τον SemK για K τιμές), με χρήση δυο δυαδικών σηματοφόρων (αμοιβαίου αποκλεισμού Sem1, και αναμονής Sem2) και μιας μεταβλητής (της Var3, που θα παίρνει ακέραιες τιμές).


Αρχικές τιμές Sem1=0; Sem2=1; Var3=K
P(SemK) P(Sem1);
Var3 := Var3 – 1;
V(Sem1);
if Var3 <= -1 then P(Sem2);
V(SemK) P(Sem1);
Var3 := Var3 + 1;
if Var3 <= 0 then V(Sem2);
V(Sem1);


Ο έλεγχος της τιμής και η αλλαγή της τιμής της μεταβλητής Var3 είναι κρίσιμο τμήμα, γι’ αυτό μπαίνει ανάμεσα από τις P(Sem1) και V(Sem1).

H διεργασία με την λειτουργία P(SemK), (με την οποία ζητάει να αρχίσει να εκτελεί το κρίσιμο τμήμα της), αφού μειώσει (λειτουργώντας με αποκλεισμένες τις άλλες διεργασίες) την τιμή της μεταβλητής Var3 κατά 1, αμέσως μετά (αν Var3 είναι μικρότερο ή ίσο με το μείον ένα, δηλαδή αν υπάρχουν διεργασίες σε αναμονή) ορίζει, με P(Sem2), ότι κάθε επόμενη διεργασία θα μπαίνει στην αναμονή.

Η αναμονή τελειώνει με την πρώτη λειτουργία V(SemK) που θα εκτελεστεί.


[Επεξεργασία] Παράδειγμα συγχρονισμού διεργασιών

Θέλουμε να συγχρονίσουμε δυο διεργασίες ώστε η Π1 να ειδοποιηθεί από την Π2. (Ας πούμε ότι η Π1 πρέπει να περιμένει μέχρι να φτάσει η Π2 σε συγκεκριμένο σημείο).

Θα χρησιμοποιήσουμε τον σηματοφόρο Sem1 με αρχική τιμή 0:

var Sem1 : semaphore;
Sem1 := 0;
parbegin
P1: begin
     {προηγούμενες εντολές της P1}
       P(Sem1); {περίμενε ειδοποίηση από την P2}
     {επόμενες εντολές της P1}
    end ||
P2: begin
      {προηγούμενες εντολές της P2}
        V(Sem1); {ειδοποίησε την P1}
      {επόμενες εντολές της P2}
    end
parend