Υλοποίηση των λειτουργιών Ρ και V

Όπως είδαμε, ένας σηματοφορέας είναι πρακτικά ένας μετρητής, τον οποίο μοιράζονται όσες διεργασίες χρησιμοποιούν το σηματοφορέα. Για να γίνονται σωστά οι λειτουργίες στο σηματοφορέα, πρέπει η πρόσβαση στο μοιραζόμενο αυτό μετρητή να γίνεται με ασφάλεια (κρίσιμο τμήμα). Αυτός είναι ο λόγος που οι λειτουργίες Ρ και V πρέπει να εκτελούνται αδιαίρετα.

Σε όλους τους υπολογιστές οι εντολές σε γλώσσα μηχανής, δηλαδή στο στοιχειωδέστερο επίπεδο προγραμματισμού τους, εκτελούνται αδιαίρετα. Έτσι αν οι δυο λειτουργίες υλοποιούνται σαν εντολές γλώσσας μηχανής, τότε ικανοποιείται αυτόματα ο περιορισμός της αδιαίρετης εκτέλεσής τους. Αυτό όμως μπορεί να δημιουργήσει δυο σοβαρά προβλήματα:

- Αν ο σηματοφορέας είναι ήδη κατειλημμένος από μια διεργασία, δηλαδή έχει τιμή Ο, η επόμενη που θα εκτελέσει τη λειτουργία Ρ θα αρχίσει να εκτελεί αδιαίρετα το βρόχο «while s = Ο do_nothing». Αφού η εκτέλεση είναι αδιαίρετη, όσο ο βρόχος εκτελείται δεν είναι δυνατόν να διακοπεί η διεργασία για να εκτελεστεί κάποια άλλη, συνεπώς και να απελευθερωθεί ο σηματοφορέας από τη διεργασία που τον κατέχει. Ο υπολογιστής τότε βρίσκεται σε κατάσταση αδιεξόδου και εκτελεί επ' άπειρο το βρόχο.

- Ακόμα και αν το προηγούμενο πρόβλημα ξεπεραστεί, κάθε εκτέλεση της λειτουργίας Ρ από μια διεργασία θα συνεπάγεται τη σπατάλη αρκετού υπολογιστικού χρόνου στην εκτέλεση του βρόχου. Οι διεργασίες, σε κάθε κβάντο χρόνου που τους αντιστοιχεί θα εκτελούν το βρόχο, ξοδεύοντας έτσι χρόνο που θα μπορούσε να χρησιμοποιηθεί πιο «παραγωγικά».

Για να ξεπεραστούν τα προβλήματα αυτά, οι λειτουργίες Ρ και V δεν υλοποιούνται στην πραγματικότητα όπως ορίζονται. Για την υλοποίηση των σηματοφορέων χρησιμοποιούνται λίστες αναμονής (waiting lists).

Κάθε σηματοφορέας έχει τη δική του λίστα αναμονής στην οποία περιμένουν οι διεργασίες που χρειάζονται το σηματοφορέα, για όσο χρόνο αυτός είναι κατειλημμένος. Όταν το ΛΣ επιλέγει την επόμενη διεργασία που θα εκτελεστεί, δε λαμβάνει υπόψη αυτές που περιμένουν στη λίστα κάποιου σηματοφορέα, γιατί έτσι και αλλιώς αυτή δεν έχει τίποτα να κάνει μέχρι να ελευθερωθεί ο σηματοφορέας.

Η λειτουργία Ρ λοιπόν γίνεται ως εξής: αν ο σηματοφορέας είναι ελεύθερος, τότε η διεργασία τον καταλαμβάνει. Αν δεν είναι ελεύθερος, η διεργασία καταγράφεται στη λίστα αναμονής του σηματοφορέα, όπου και παραμένει χωρίς να εκτελείται. Στη λειτουργία V, όπου μια διεργασία ελευθερώνει το σηματοφορέα, το ΛΣ εξετάζει τη λίστα αναμονής του. Επιλέγει από αυτή την πρώτη διεργασία και τη διαγράφει από τη λίστα αναμονής, εισάγοντάς τη στη λίστα των διεργασιών που εκτελούνται εκ περιτροπής στην ΚΜΕ. Σύντομα θα έλθει η σειρά της διεργασίας αυτής να εκτελεστεί, και τότε θα καταλάβει το σηματοφορέα ολοκληρώνοντας έτσι τη λειτουργία Ρ.

Η λίστα αναμονής ενός σηματοφορέα οργανώνεται σαν ουρά (queue). Σε μια ουρά, όπως π.χ. στο ταμείο μιας τράπεζας, επιλέγεται από την ουρά η διεργασία που περιμένει την περισσότερη ώρα.