Σημειώσεις:Κατανεμημένοι Αλγόριθμοι:RAME

Από DistrSys

RAME

Πρόβλημα: Αμοιβαίος Αποκλεισμός Δίκτυο: Γενικό Κλάση: -

Πολυπλοκότητα

Χρονική: 2d+O(l) Επικοινωνίας: 2n-1 μηνύματα ανά αίτηση

Στη σύνταξη του κειμένου συνεισέφερε ο Βάσσης Γεώργιος

• Όπως και πριν οι διεργασίες διατηρούν ένα λογικό ρολόι Lamport (αλγόριθμος LamportTime) και μια ουρά προτεραιότητας για τις εισερχόμενες αιτήσεις που περιλαμβάνουν χρονοσφραγίδες.
• Κάθε διεργασία που επιθυμεί να μπει στο κρίσιμο τμήμα στέλνει αίτηση προς όλες τις άλλες διεργασίες και τοποθετεί την αίτηση στην δικιά της ουρά.
• Η επιβεβαίωση υπάρχει και εδώ αλλά είναι διαφορετική σαν έννοια. Η διεργασία θα μπει στο κρίσιμο τμήμα μόλις πάρει μήνυμα επιβεβαίωσης από όλες τις άλλες. Για να γίνει αυτό, μόλις μία διεργασία παραλάβει μήνυμα request θα στείλει μήνυμα για επιβεβαίωση όταν ισχύει όλες οι παρακάτω συνθήκες:
  1. Δεν είναι η ίδια σε κρίσιμο τμήμα.
  2. Είναι η μοναδική αίτηση στην ουρά της.
  3. Είναι η πρώτη αίτηση στην ουρά της.
• Αν καμία συνθήκη δεν ισχύει τότε η επιβεβαίωση θα γίνει όταν κάποια έρθει σε ισχύ. Με αυτόν τον τρόπο καταφέρνουμε να μην χρειάζονται τα μηνύματα απελευθέρωσης πόρου καθώς τα κριτήρια για να γίνει επιβεβαίωση πρόσβασης θα ικανοποιηθούν μόνο όταν ο πόρος είναι ελεύθερος. Πρακτικά δηλαδή συγχωνεύουμε τα μηνύματα επιβεβαίωσης με αυτά της απελευθέρωσης πόρου. Και εδώ όμως για να γίνει πρόσβαση στον πόρο από κάποια διεργασία πρέπει να λάβει μηνύματα επιβεβαίωσης από όλες τις υπόλοιπες.

Βελτιώσεις στον LogicalTimeME Αλγόριθμο

Θα περιγράψουμε τώρα μια απλή παραλλαγή του LogicalTimeME αλγόριθμου που σχεδιάστηκε για να μειώσει την πολυπλοκότητα επικοινωνίας. Ο αλγόριθμος, πήρε το όνομα του, RicartAgrawalaME αλγόριθμος από τους σχεδιαστές του, και χρησιμοποιεί μόνο 2n - 1 μηνύματα ανά αίτηση. Βελτιώνει τον Logical TimeME αναγνωρίζοντας αιτήσεις με έναν προσεκτικό τρόπο που εξαλείφει την ανάγκη για exit μηνύματα (exit messages). Ο αλγόριθμος χρησιμοποιεί τόσο την αναμετάδοση (broadcast) όσο και το send/receive μοντέλο επικοινωνίας όπου το send/receive μοντέλο επικοινωνίας επιτρέπεται για όλα τα ζευγάρια διακριτών διεργασιών.

Ο αλγόριθμος RicartAgrawalaME :

Οι χρονοσφραγίδες για τα γεγονότα δημιουργούνται όπως και στον LogicalTimeME. Το μοναδικό μήνυμα που μεταδίδεται είναι try, και το μοναδικό μήνυμα που αναμεταδίδεται σε ένα send/receive κανάλι είναι οκ. Κάθε μήνυμα φέρει την χρονοσφραγίδα του bcast ή send γεγονότος.

Μετά από μια είσοδο try_i, η διεργασία P_i αναμεταδίδει το try όπως και στον Logical TimeME και μπορεί να μεταβεί στην C εφόσον έχει παραλάβει μεταγενέστερα ok μηνύματα από όλες τις υπόλοιπες διεργασίες. Το ενδιαφέρον κομμάτι του αλγορίθμου είναι ένας κανόνας για το πότε μια διαδικασία P_i μπορεί να στείλει ok μήνυμα σε μια άλλη διαδικασία P_j. Η ιδέα είναι να χρησιμοποιήσουμε ένα σχήμα προτεραιότητας. Σε απάντηση από ένα try μήνυμα από την P_j, η P_i κάνει τα εξής:

1. Εάν η διεργασία P_i είναι στην E ή στην R, ή στην T περιοχή έχει προτεραιότητα να μεταδώσει ένα μήνυμα try για την τωρινή της αίτηση, τότε η P_i απαντά με ok.

2. Εάν η P_i είναι στη C, τότε η P_i δεν απαντά έως ότου φτάσει στην E, και τότε στέλνει αμέσως τα αναβλεθέντα oks.

3. Εάν η P_i είναι στην T και η τωρινή της κατάσταση έχει ήδη μεταδοθεί, τότε η P_i συγκρίνει τη χρονοσφραγίδα της t_i (του bcast γεγονότος) της αίτηση της με τη χρονοσφραγίδα t_j που σχετίζεται με το εισερχόμενο try μήνυμα της P_j. Αν t_i > t_j, τότε στην αίτηση της P_i δίνεται μικρότερη προτεραιότητα και η P_i απαντά με ένα ok μήνυμα. Σε αντίθετη περίπτωση η αίτηση της P_i έχει μεγαλύτερη προτεραιότητα, γι’ αυτό αναβάλει την απάντηση τόσες φορές, όσες χρειάζεται για να τελειώσει με την επόμενη κρίσιμη περιοχή. Εκείνη τη στιγμή αμέσως στέλνει όλα τα αναβαλλόμενα oks. Η διαδικασία P_i μπορεί να εκτελέσει ένα remi σε οποιαδήποτε στιγμή, αφού έχει δεχτεί ένα exiti.

Με άλλα λόγια, όταν υπάρχει μια σύγκρουση, ο αλγόριθμος RicartAgrawalaME την επιλύει υπέρ της “γρηγορότερης” αίτησης, όπως ορίζεται από τις χρονοσφραγίδες.

Θεώρημα (20.3)

Ο αλγόριθμος RicartAgrawalaME λύνει το πρόβλημα του αμοιβαίου αποκλεισμού και εγγυάται lockout-freedom..

Απόδειξη:

Δίνουμε μια απόδειξη με επιχειρήματα. Πρώτον, αποδεικνύουμε τον αμοιβαίο αποκλεισμό με εις άτοπον αναγωγή. Ας υποθέσουμε ότι, σε ορισμένες προσβάσιμες καταστάσεις, δυο διεργασίες P_i και P_j είναι στη θέση C την ίδια χρονική στιγμή. Ας υποθέσουμε (χωρίς βλάβη της γενικότητας) ότι η χρονοσφραγίδα _i του τελευταίου try μηνύματος της P_i είναι μικρότερη από τη χρονοσφραγίδα t_j του τελευταίου try μηνύματος της διαδικασίας P_j. Στη συνέχεια, πρέπει να υπάρξουν try και ok μηνύματα που στέλνονται από την μια διαδικασία στην άλλη, με βάση την είσοδο τους στην κατάσταση C. Επιπλέον, σε κάθε διαδικασία, η παραλαβή των try γίνετε με την αποστολή απαντητικών ok. Αυτό ακόμα αφήνει αρκετές παραλαβές για τα διάφορα γεγονότα. Βλέπε την εικόνα που ακολουθεί για κάποιες περιπτώσεις.

☐

Τώρα ισχυριζόμαστε ότι το receive γεγονός για το τελευταίο try μήνυμα της διαδικασίας P_j εμφανίζεται αφότου η διαδικασία P_i έχει στείλει το δικό της τελευταίο try μήνυμα. Αν όχι, τότε από τις ιδιότητες των χρονοσφραγίδων συνεπάγεται ότι η χρονοσφραγίδα του receive γεγονότος είναι μεγαλύτερη από την t_j και ότι η χρονοσφραγίδα t_i του bcast γεγονότος από την διαδικασία P_i είναι μεγαλύτερο από τη χρονοσφραγίδα του receive γεγονότος. Έτσι, t_i > t_j, που είναι άτοπο.

Μερικές πιθανές διατάξεις γεγονότων στον RicartAgrawalaME αλγόριθμο

Ως εκ τούτου, τη χρονική στιγμή που η P_i λαμβάνει try μήνυμα από την P_j, η P_i είναι είτε στην T ή είτε στην C. Αλλά σε καμία από τις περιπτώσεις αυτές, οι κανόνες της P_i αναφέρουν ότι θα πρέπει να αναβάλλει την αποστολή ενός ok μηνύματος μέχρι να ολοκληρωθεί το δικό της κρίσιμο κομμάτι. Έτσι, η P_j δεν μπορεί να εισέλθει στην κατάσταση C, πριν η P_i φύγει, άτοπο.

Τώρα αποδεικνύουμε την πρόοδο, επίσης με εις άτοπον αναγωγή. Η πρόοδος για την περιοχή της εξόδου είναι άμεση. Ας υποθέσουμε ότι σε μια εύλογη εκτέλεση ένα σημείο επιτεύχθηκε στο οποίο κάποιος χρήστης είναι στη T και κανένας χρήστης στη C και μετά από αυτό κανένας χρήστης δεν εισέρχεται ξανά στη C. Στη συνέχεια, σε κάποια περίπτωση α1 της α, όλοι οι χρήστες είναι είτε στο R είτε στο T και δεν χρειάζεται περαιτέρω αλλαγή θέσης. Στη συνέχεια υπάρχει κάποια περίπτωση α2 της α1 στην οποία όλες οι διεργασίες στην Τ έχουν ανατεθεί χρονοσφραγίδες στην τελευταία τους αίτηση και στις οποίες κανένα μήνυμα δεν είναι ακόμα σε μετάδοση. Ανάμεσα σε όλες τις διεργασίες στην Τα και στην α2, ας είναι η P_i η διαδικασία της οποίας η τελευταία αίτηση έχει τη μικρότερη χρονοσφραγίδα, ας πούμε t_i.

Δεδομένου ότι η P_i έχει κολλήσει για πάντα στη T, πρέπει να γίνει το εξής: κάποια άλλη διαδικασία P_j δεν απαντά ποτέ με ok μήνυμα στο τελευταίο try μήνυμα της διαδικασίας P_i. Υπάρχουν μόνο δυο λόγοι γιατί η P_j ενδέχεται να μην στείλει το ok αμέσως μόλις έλαβε το try από την P_i.

1. Η P_j είναι στην C όταν λαμβάνει το try. Σε αυτήν την περίπτωση, δεδομένου ότι δεν υπάρχουν διεργασίες στο C κατά τη διάρκεια του α2, η P_j πρέπει να τερματίσει την κρίσιμη περιοχή της πριν το έναρξη της α2 πρέπει στη συνέχεια να στείλει το αναβαλλόμενο ok μήνυμα στην P_i.

2. Η P_j είναι στην T όταν λαμβάνει το try, με μια χρονική στιγμή t_j < t_i να έχει ανατεθεί στην αίτηση. Σε αυτή τη περίπτωση, δεδομένου ότι η αίτηση της P_i έχει τη μικρότερη χρονοσφραγίδα ανάμεσα στις διεργασίες που έχουν κολλήσει στην Τα της α2, πρέπει να είναι η P_j η διαδικασία που φτάνει και ολοκληρώνει την κρίσιμη περιοχή, εφόσον έχει λάβει το try από την P_i και πριν την αρχή της α2. Αλλά και πάλι, αυτό σημαίνει ότι η P_j πρέπει να στείλει το ανεβλήθην op μήνυμα στη διαδικασία P_i.

Σε κάθε περίπτωση, η διαδικασία P_i λαμβάνει όλα τα απαιτούμενα ok μηνύματα και μεταβαίνει στη θέση C, άτοπο.

Ανάλυση Πολυπλοκότητας. Είναι εύκολο να δούμε ότι ακριβώς 2n-1 μηνύματα στέλνονται ανά αίτηση. Η εύρεση της πολυπλοκότητας χρόνου αφήνεται ως άσκηση.

Μια άλλη βελτιστοποίηση. Είναι δυνατόν να βελτιώσουμε περαιτέρω τον RicartAgrawalaME αλγόριθμο δίνοντας μια διαφορετική ερμηνεία στα ok μηνύματα. Τώρα όταν κάποια διαδικασία Pi στείλει ένα ok μήνυμα σε μια άλλη διαδικασία P_j, όχι μόνο αποδέχεται την αίτηση της τρέχουσας P_j, αλλά δίνει επίσης στην P_j διαδικασία άδεια η P_i να εισέλθει στη θέση C όσες φορές θέλει - μέχρις ότου η P_j να στείλει ένα ok μήνυμα στην Pi σε απάντηση στο try μήνυμα της P_i. Οι κανόνες για την απάντηση σε ένα try μήνυμα είναι οι ίδιοι με τους κανόνες του RicartAgrawalaME.

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

Ανάλυση Απόδοσης

Ο αλγόριθμος ικανοποιεί και τις 3 συνθήκες ορθότητας καθώς δεν είναι τίποτα παρά μια βελτίωση στον τομέα της πολυπλοκότητας επικοινωνίας του αλγορίθμου του Lamport. Συγκεκριμένα η πολυπλοκότητα για την εξυπηρέτηση μιας αίτησης είναι 2(n-1) σε σχέση με το 3(n-1) του LamportME καθώς 2 τύποι μηνυμάτων γίνονται ένας. Η απόκριση για μία αίτηση παραμένει 2d+O(l).

Το πρόβλημα που διαπιστώσαμε στον LamportME δεν διορθώνεται με αυτόν τον αλγόριθμο καθώς και πάλι έχουμε τόσα σημεία αποτυχίας όσα και οι διεργασίες.

Τέλος ακολουθεί ένα παράδειγμα εκτέλεσης του αλγορίθμου

Το δίκτυο έχει 5 μονάδες και 6 κανάλια. Η διεργασία 1 είναι η ϱίζα του δέντρου.΄Ολες οι ουρές είναι άδειες

Η διεργασία 4 επιθυμεί να εισέλθει σε ΚΤ.Εισάγει την αίτηση στην ουρά της

Η διεργασία 4 επεξεργάζεται την αίτηση (εφόσον αρχικά η ουρά ήταν άδεια).Στέλνει μήνυμα αίτησης στην διεργασία 5. Η διεργασία 5 αποθηκεύει το μήνυμα στην ουρά της

Η διεργασία 5 επεξεργάζεται την αίτηση (εφόσον αρχικά η ουρά ήταν άδεια). Στέλνει μήνυμα αίτησης στην διεργασία 1.Η διεργασία 1 αποθηκεύει το μήνυμα.

Η διεργασία 3 επιθυμεί να εισέλθει σε ΚΤ.Εισάγει την αίτηση στην ουρά της

Η διεργασία 3 επεξεργάζεται την αίτηση (εφόσον αρχικά η ουρά ήταν άδεια).Στέλνει μήνυμα αίτησης στην διεργασία 5.

Η διεργασία 5 αποθηκεύει το μήνυμα στην ουρά της. Η ουρά δεν είναι άδεια-δεν στέλνει κάποιο μήνυμα στην 1

Η διεργασία 1 βγαίνει από το ΚΤ. Επεξεργάζεται την πρώτη αίτηση.Στέλνει το κουπόνι στην 5 και αντιστρέφει την ακμή

Η διεργασία 5 επεξεργάζεται την πρώτη αίτηση.Στέλνει το κουπόνι στην 4 και αντιστρέφει την ακμή.

Η διεργασία 5 επεξεργάζεται την επόμενη αίτηση και στέλνει μήνυμα αίτησης στην διεργασία 4. Η διεργασία 4 αποθηκεύει το μήνυμα στην ουρά της.

Η διεργασία 4 επεξεργάζεται την πρώτη αίτηση. Εισέρχεται σε ΚΤ

Η διεργασία 4 βγαίνει από το ΚΤ.Επεξεργάζεται την πρώτη αίτηση.Στέλνει το κουπόνι στην διεργασία 5 και αντιστρέφει την ακμή.

Εικόνες:Rame13.jpg Algorithm LCR