25. Συγχρονισμός σε κατανεμημένα συστήματα με τον αλγόριθμο των Ricart και Agrawala

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

Ο αλγόριθμος λειτουργεί ως εξής:

Όταν μια διεργασία θέλει να εισέλθει σε κρίσιμη περιοχή, φτιάχνει ένα μήνυμα που περιέχει το όνομα της κρίσιμης περιοχής που θέλει να εισέλθει, τον αριθμό διεργασίας και την τρέχουσα ώρα. Στη συνέχεια στέλνει το μήνυμα προς όλες τις άλλες διεργασίες, συμπεριλαμβανομένης και της ίδιας. Όταν μια διεργασία λάβει ένα μήνυμα αιτήματος από μια άλλη διεργασία, η δράση της εξαρτάται από την κατάστασή της σε σχέση με την κρίσιμη περιοχή που αναφέρεται στο μήνυμα. Υπάρχουν τρεις δυνατές καταστάσεις:

· Αν ο αποδέκτης δεν είναι μέσα στην κρίσιμη περιοχή και δεν θέλει να εισέλθει σε αυτή, στέλνει πίσω ένα OK μήνυμα προς τον αποστολέα (φαίνεται ως κατάσταση Ready στο πάγκο εργασίας).

· Εάν ο αποδέκτης είναι ήδη μέσα στην κρίσιμη περιοχή, δεν απαντά. Αντ 'αυτού, βάζει στην ουρά την αίτηση (εμφανίζεται ως κατάσταση CS στο πάγκο εργασίας).

· Εάν ο αποδέκτης θέλει να εισέλθει στην κρίσιμη περιοχή, αλλά δεν έχει ακόμη μπει, συγκρίνει το timestamp (χρονοσφραγίδα) στο εισερχόμενο μήνυμα με εκείνο που περιέχεται στο μήνυμα που έχει σταλεί σε όλους. Ο μικρότερος χρόνος κερδίζει. Αν το εισερχόμενο μήνυμα είναι παλιότερο , ο δέκτης στέλνει πίσω OK μήνυμα. Αν το δικό της μήνυμα έχει χαμηλότερη timestamp (παλιότερη), οι δέκτης βάζει στην ουρά του το εισερχόμενο μήνυμα και δε στέλνει τίποτα (φαίνεται ως κατάστασηWaiting στο πάγκο εργασίας).

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

Αυτός ο πάγκος εργασίας εμφανίζει ένα κατανεμημένο σύστημα με τέσσερις κόμβους, με κάθε κόμβο να έχει μια ουρά για αιτήσεις και μια ουρά για επιβεβαιώσεις. Η αποστολή αιτήματος παρουσιάζεται με χρωματιστές μπάλες και η αποστολή επιβεβαιώσεων με τη χρήση ορθογώνιων. Στο διαδραστικό τρόπο, μπορείτε να δημιουργήσετε αιτήσεις για τους κόμβους πιέζοντας αντίστοιχα κουμπιά στο κάτω μέρος του κάθε κόμβου. Μπορείτε επίσης να λειτουργήσετε τον πάγκο εργασίας σε συνεχή λειτουργία πατώντας το κουμπί «Animate». Η ταχύτητα του animation μπορεί να μεταβάλλεται με τη γραμμή κύλισης.