.
Ο σηματοφόρος ή σηματοφορέας ή σημαφόρος (αγγλ. semaphore)είναι μια προγραμματιστική δομή δεδομένων, κύρια χρήση της οποίας είναι ο συγχρονισμός ταυτόχρονα εκτελούμενων διεργασιών ενός προγράμματος, ή ακόμα και ο συγχρονισμός διαφορετικών προγραμμάτων. Συνήθως χρησιμοποιούνται οι δυαδικοί σηματοφορείς οι οποίοι παίρνουν τιμές στο δισύνολο {0, 1}. Η χρήση των σηματοφόρων εξασφαλίζει τον αμοιβαίο αποκλεισμό των ταυτόχρονα εκτελούμενων διεργασιών με αποτέλεσμα τον επιθυμητό συγχρονισμό τους.
Ορισμός
Για να απλοποιηθούν οι ρουτίνες που φροντίζουν τις ταυτόχρονες διεργασίες, ο Έντσγκερ Ντάικστρα (Edsger Dijkstra) εισήγαγε την έννοια των σηματοφόρων. Ένας σηματοφόρος είναι μια ακέραιη μεταβλητή, την οποία μπορούν να εξετάσουν ή και να μεταβάλουν οι διάφορες διεργασίες.
Στον σηματοφόρο (έστω 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, δηλαδή: εκκίνηση αναγραφής διεργασιών που εκτελούνται παράλληλα (parbegin < {parallel + begin} = {παράλληλα + εκκίνηση}),
|| (δυο παράλληλες γραμμές), δηλαδή: ακολουθεί άλλη διεργασία, και
parend, δηλαδή: τερματισμός αναγραφής διεργασιών που εκτελούνται παράλληλα (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
Κρίσιμο τμήμα (αγγλ. critical section): Είναι το υποσύνολο εντολών μιας διεργασίας που όταν εκτελούνται αυτές δεν πρέπει να εκτελούνται οι εντολές των παράλληλων διεργασιών. Οι εντολές του κρίσιμου τμήματος εκτελούνται αδιάκοπτα (δηλαδή χωρίς να επιτρέπονται διακοπές (αγγλ. interrupt))
Όταν είναι ο σηματοφόρος 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
Παράδειγμα : Το πρόβλημα των Φιλοσόφων που συντρώγουν και συσκέπτονται
Αυτό το παράδειγμα δόθηκε από τον Ντάικστρα το 1965 για να μπορέσει να αποδείξει την χρησιμότητα των σηματοφόρων:
Πέντε φιλόσοφοι περνούν την ζωή τους καθισμένοι σε ένα στρογγυλό τραπέζι, άλλοτε τρώγοντας και άλλοτε σκεπτόμενοι. (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
Κρίσιμη περιοχή
Στον προγραμματισμό, μια κρίσιμη περιοχή προσδιορίζει ένα τμήμα κώδικα προγράμματος που μπορεί σε μια δεδομένη χρονική στιγμή να εκτελεστεί από ακριβώς μία διεργασία. Οι κρίσιμες περιοχές αποτελούν τμήματα κώδικα που εκτελούνται ατομικά.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
