Διδακτικά Βιβλία του Παιδαγωγικού Ινστιτούτου

Αναζήτηση

Βρες
Εμφάνιση

Αμοιβαίος αποκλεισμός για δυο διεργασίες: η λύση του Peterson

Η πρώτη λύση που δόθηκε στο πρόβλημα του αμοιβαίου αποκλεισμού για δύο διεργασίες ήταν αυτή του Δανού μαθηματικού Τ. Dekker, όμως η λύση που έδωσε το 1981 ο J. Peterson είναι πολύ πιο απλή. Υπάρχει μια κοινή μεταβλητή με όνομα π.χ. seira, που δείχνει ποια από τις δυο διεργασίες έχει σειρά να εκτελέσει το κρίσιμο τμήμα της. Αν η μεταβλητή έχει την τιμή 1, τότε είναι σειρά της πρώτης διεργασίας, ενώ αν έχει την τιμή 2 είναι σειρά της δεύτερης. Επίσης υπάρχουν δύο μεταβλητές, μία για κάθε διεργασία, με ονόματα π.χ. eisodosl και eisodos2. Η μεταβλητή eisodosl έχει την τιμή true όταν η διεργασία 1 είναι έτοιμη να εκτελέσει ή εκτελεί το κρίσιμο τμήμα της, ενώ σε όλες τις άλλες φάσεις εκτέλεσής της έχει τιμή false.

Διεργασία 1

Διεργασία 2

Αντίστοιχες τιμές παίρνει και η μεταβλητή eisodos2, για τη διεργασία 2. Οι δύο διεργασίες έχουν τη μορφή που φαίνεται στα σχήματα.

Κάθε διεργασία περιμένει για την άλλη, εφόσον είναι η σειρά της άλλης και εκείνη έχει δηλώσει πρόθεση να εκτελέσει το κρίσιμο τμήμα της. Αν π.χ. είναι η σειρά της διεργασίας 2 αλλά εκείνη δεν είναι έτοιμη να εκτελέσει το κρίσιμο τμήμα της (δηλαδή eisodos2=false), τότε η διεργασία 1 μπαίνει στο δικό της κρίσιμο τμήμα, εμποδίζοντας τη 2 με τη βοήθεια της eisodosl. Αν και οι δυο διεργασίες θέλουν ταυτόχρονα να εκτελέσουν το κρίσιμο τμήμα τους, το εκτελεί πρώτα εκείνη που υποδεικνύεται από τη μεταβλητή seira.

Η λύση αυτή μπορεί να επεκταθεί και για την περίπτωση που έχουμε ν διεργασίες· η λύση αυτή όμως είναι αρκετά πολύπλοκη, ενώ το πρόβλημα λύνεται πολύ πιο απλά με τη βοήθεια των σηματοφορέων (semaphores) που περιγράφονται στη συνέχεια.