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

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

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

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

αρχική τιμήSem1 := 1
P(Sem1)**while** Sem1 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, δηλαδή: εκκίνηση αναγραφής διεργασιών που εκτελούνται παράλληλα (parbegin Αρχικές τιμέςSem1=0; Sem2=1; Var3=K
P(SemK)P(Sem1); Var3 := Var3 – 1;V(Sem1);if Var3 
V(SemK)P(Sem1); Var3 := Var3 + 1; if Var3 V(Sem1);

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

Η διεργασία με την λειτουργία 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

### Παράδειγμα : Το πρόβλημα των Φιλοσόφων που συντρώγουν και συσκέπτονται

Αυτό το παράδειγμα δόθηκε από τον Ντάικστρα το 1965 για να μπορέσει να αποδείξει την χρησιμότητα των σηματοφόρων: 

Εικόνα:20050217_phil_table.JPG 
:Πέντε φιλόσοφοι περνούν την ζωή τους καθισμένοι σε ένα   στρογγυλό τραπέζι, άλλοτε τρώγοντας και άλλοτε σκεπτόμενοι. (1) Τα πιάτα τους τροφοδοτούνται από υπηρέτες. (2) Εκτός από τα πέντε πιάτα, στο τραπέζι βρίσκονται και πέντε ξυλάκια φαγητού, το καθένα ανάμεσα από δυο πιάτα. (3) Όταν ένας φιλόσοφος θέλει να φάει, παίρνει ταυτόχρονα τα δυο ξυλάκια που είναι αριστερά και δεξιά από το πιάτο του και τρώει. (4) Μετά αφήνει ταυτόχρονα τα ξυλάκια στην θέση τους και σκέπτεται μέχρι να πεινάσει πάλι.

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

Το πρόγραμμα που εξομοιώνει το πρόβλημα των πέντε φιλοσόφων που περιγράψαμε, θα μπορούσε να είναι όπως το παρακάτω, (όπου με P1t σημειώνουμε ότι ο φιλόσοφος 1 τρώει, και με P1s σημειώνουμε ότι ο φιλόσοφος 1 σκέπτεται):

 var Sa, Sb, Sc, Sd, Se: semaphores;
 Sa := Sb := Sc := Sd := Se := 1;
 parbegin
         begin P(Sa); P(Sb); P1t; V(Sa); V(Sb); P1s; end ||
         begin P(Sb); P(Sc); P2t; V(Sb); V(Sc); P2s; end ||
         begin P(Sc); P(Sd); P3t; V(Sc); V(Sd); P3s; end ||
         begin P(Sd); P(Se); P4t; V(Sd); V(Se); P4s; end ||
         begin P(Se); P(Sa); P5t; V(Se); V(Sa); P5s; end 
 parend

## Κρίσιμη περιοχή
Στον προγραμματισμό, μια **κρίσιμη περιοχή** προσδιορίζει ένα τμήμα κώδικα προγράμματος που μπορεί σε μια δεδομένη χρονική στιγμή να εκτελεστεί από ακριβώς μία διεργασία. Οι κρίσιμες περιοχές αποτελούν τμήματα κώδικα που εκτελούνται ατομικά.

Κατηγορία:Ταυτοχρονισμός
Κατηγορία:Τεχνολογία λειτουργικών συστημάτων