Σημειώσεις:Κατανεμημένοι Αλγόριθμοι:LamportME
Από DistrSys
| LamportME |
| Πρόβλημα: Αμοιβαίος Αποκλεισμός Δίκτυο: Γενικό Κλάση: - |
|
|
| Πολυπλοκότητα |
| Χρονική: 2d+O(l) Επικοινωνίας: 3n-1 |
|
|
| Στη σύνταξη του κειμένου συνεισέφερε ο Βάσσης Γεώργιος |
Ο αλγόριθμος coordinator είδαμε ότι αν και σωστός ήταν κεντρικοποιημένος, κάτι που μπορούσε να μας δημιουργήσει σοβαρά προβλήματα. Ο Lamport συνεχίζοντας την θεωρία του για τα λογικά ρολόγια που είδαμε στην προηγούμενη ενότητα, διατύπωσε το 1978 τον πρώτο κατανεμημένο αλγόριθμο για την λύση του προβλήματος του αμοιβαίου αποκλεισμού.
- Οι διεργασίες κρατάνε η καθεμία από ένα λογικό ρολόι. Διατηρούν επίσης και μία ουρά για εισερχόμενες αιτήσεις.
- Κάθε διεργασία που επιθυμεί να μπει στο κρίσιμο τμήμα στέλνει ένα μήνυμα με την αίτησή της σε όλες τις άλλες διεργασίες. Το μήνυμα request θα περιέχει και την χρονοσφραγίδα του λογικού ρολογιού της διεργασίας. Η αίτησή της θα μπει και στην δική της ουρά.
- Όταν μία διεργασία παραλάβει μία αίτηση, την τοποθετεί στην ουρά και απαντάει στην αιτούσα διεργασία ότι η παραλαβή έγινε επιτυχώς.
- Αν η ουρά δεν είναι κενή και ο πόρος ελεύθερος οι διεργασίες αποφασίζουν να μπει στο κρίσιμο τμήμα η διεργασία με την μικρότερη χρονοσφραγίδα, πρακτικά δηλαδή αυτή που έκανε πρώτα την αίτηση σύμφωνα με την σχέση συνέβη πριν και τα λογικά ρολόγια του Lamport.
Δεν χρειάζεται να σταλεί μήνυμα για να μπει η διεργασία στο κρίσιμο τμήμα, αφού με τα στοιχεία του αλγορίθμου όλες οι διεργασίες έχουν ίδιες ουρές άρα θα αποφασίσουν το ίδιο και απλά θα περιμένουν μήνυμα απελευθέρωσης του πόρου από την διεργασία που νομίζουν ότι τον έχει. Δηλαδή, η διεργασία που θα δει ότι στην ουρά της η αίτηση με την μικρό-τερη χρονοσφραγίδα είναι δικιά της θα μπει στο κρίσιμο τμήμα.
- Για την απελευθέρωση του πόρου η διεργασία που τον έχει, στέλνει μήνυμα σε όλες τις υπόλοιπες για release και διαγράφει την δική της αίτηση από την ουρά της. Όταν και οι άλλες διεργασίες παραλάβουν το μήνυμα θα διαγράψουν και αυτές την διεργασία από την ουρά τους και θα συνεχιστεί η διαδικασία.
Ο αλγόριθμος χρησιμοποιεί τα τρία είδη μηνυμάτων με πριν (request, reply και release). Πριν εξετάσουμε την πολυπλοκότητα και τις άλλες ιδιότητες του αλγορίθμου ας δούμε πρώτα ότι είναι σωστός.
Αλγόριθμος LogicalTimeME
Αυτός ο αλγόριθμος παράγει λογικά ρολόγια για κάθε γεγονός χρησιμοποιώντας την στρατηγική του αλγορίθμου LamportTime, ο οποίος βασίζεται σε λογικά ρολόγια με μη αρνητικές ακέραιες τιμές. Ένας λογικός χρόνος είναι ένα ζευγάρι (c,i) όπου c ϵ N και i είναι ένας δείκτης μιας διεργασίας. Οι λογικοί χρόνοι είναι ζευγάρια τα οποία είναι διαταγμένα λεξικογραφικά.
Ο αλγόριθμος χρησιμοποιεί τόσο την αναμετάδοση όσο και το send/receive μοντέλο επικοινωνίας όπου το send/receive μοντέλο επικοινωνίας επιτρέπεται για όλα τα ζευγάρια διακριτών διεργασιών. Στην θέση της ουρά ή του καταχωρητή, κάθε διεργασία διατηρεί μια μοναδική βάση δεδομένων με την ιστορία της. Έτσι για κάθε j, το history(j)i καταγράφει όλα τα μηνύματα που η διεργασία Pi έχει λάβει από τη διεργασία Pj. Κάθε μήνυμα έχει και έναν μη αρνητικό ακέραιο αριθμό c, ο οποίος είναι η τιμή του ρολογιού όταν ένα μήνυμα αναμεταδόθηκε ή στάλθηκε. Οι αιτήσεις try και exit αναμεταδίδονται. Αντί να μεταδίδονται κενά μηνύματα, κάθε διεργασία επιβεβαιώνει ένα μήνυμα try με ένα ack μήνυμα.
Η διεργασία Pi βγάζει σαν έξοδο το criti, όταν η τελευταία της αίτηση try έχει τοποθετηθεί στο history(i). Έτσι εγγυάται ότι κάθε άλλη αίτηση που η διεργασία Pi έχει λάβει με μικρότερο λογικό χρόνο έχει γίνει αποδεκτή και ότι η διεργασία Pi έχει λάβει ένα μήνυμα με μεγαλύτερο λογικό χρόνο από κάθε άλλη διεργασία. (Αυτές οι δύο τελευταίες ιδιότητες μαζί εγγυώνται ότι δεν υπάρχει καμία σύγχρονη αίτηση με ένα μικρότερο λογικό χρόνο και επίσης ότι ποτέ δεν θα υπάρξει). Η διεργασία Pi μπορεί να βγάλει σαν έξοδο remi μόλις η τελευταία αίτηση exit φτάσεις στο history(i).
Με το σύμβολο ≤ υποδηλώνουμε λεξικογραφική σειρά στα ζευγάρια λογικού χρόνου
Αλγόριθμος LogicalTimeME
Αρχικά
Είσοδος:
tryi
exiti
receive(m)j,i όπου m ∈ {“try”,”exit”,”ack”} x N και 1≤ j ≤ n
Έξοδος:
criti
remi
send(m)i,j , m ∈ {“ack”} x N και j ≠ i
bcast(m)i, m ∈ {“try”,”exit”} x N
Καταστάσεις:
region ∈ {R,T,C,E}, αρχικά R
clock ∈ {N}, αρχικά 0
bcast-buffer, μια ουρά FIFO με {“try”,”exit”}, αρχικά άδεια
Για κάθε j,1≤ j ≤ n:
history(j), ένα υποσύνολο με {“try”,”exit”,”ack”} x N, αρχικά 0
Για κάθε j ≠ i:
send-buffer(j), μια FIFO ουρά με {”ack”} x N, αρχικά άδεια
Μεταβάσεις:
tryi
Αποτέλεσμα:
clock := clock+1
region := T
πρόσθεσε “try” στο bcast-buffer
bcast(m,c)i
Προϋπόθεση:
To m είναι πρώτο στο bcast-buffer
c = clock+1
Αποτέλεσμα:
clock := c
αφαίρεσε το πρώτο στοιχείο από τον bcast-buffer
receive(m,c)j,i
Αποτέλεσμα:
clock := max(clock,c)+1
history(j) := history(j) ∪ {(m,c)}
Αν m=”try” και j ≠ i τότε
Πρόσθεσε “ack” στον send-buffer(j)
Send(m,c)j,i
Προϋπόθεση:
To m είναι πρώτο στο send-buffer(j)
c = clock+1
Αποτέλεσμα:
clock := c
αφαίρεσε το πρώτο στοιχείο από τον send-buffer(j)
criti
Προϋπόθεση:
region = T
(“try”,c) ∈ history(i)
∄ (“exit”,c’) ∈ history(i) με c’>c
Για όλα τα j ≠ i:
Αν (“try”,c) ∈ history(j), (c’,j)<(c,i) τότε
∃(“exit”,c’’) ∈ history(j) με c’’>c’
∃(m,c’) ∈ history(j) με (c,i)<(c’,j)
Αποτέλεσμα:
clock := clock +1
region := C
exiti
Αποτέλεσμα:
clock := clock +1
region := Ε
πρόσθεσε “exit” στον Bcast-buffer
remi
Προϋποθέσεις:
region = Ε
(“exit”,c) ∈ history(i)
∄ (“try”,c’) ∈ history(i) με c’>c
Αποτέλεσμα:
clock := clock +1
region := R
Καθήκοντα
{criti}
{remi}
{bcast(m)i: m ∈ {“try”,”exit”} x N }
Για κάθε j ≠ i:
{send(m)i,j: m ∈ {“ack”} x N }
- Θεώρημα (FloodSet.1)
- Ο αλγόριθμος LogicalTimeME λύνει το πρόβλημα του αμοιβαίου αποκλεισμού και εγγυάται lockout freedom.
- Απόδειξη:
- Δίνουμε ένα λειτουργικό επιχείρημα. Για να δούμε ότι ο αλγόριθμος εγγυάται αμοιβαίο αποκλεισμό, χρησιμοποιούμε εις άτοπον απαγωγή. Υποθέτουμε ότι, σε κάποια κατάσταση δύο διεργασίες Pi και Pj του συστήματος είναι στην C την ίδια στιγμή. Υποθέτουμε (χωρίς βλάβη της γενικότητας) ότι ο λογικός χρόνος ti του πιο πρόσφατου μηνύματος try της διεργασίας Pi είναι μικρότερος από το λογικό χρόνο tj της διεργασίας Pj. Έτσι για να βγάλουμε στην έξοδο critj και να εισάγουμε το C, η διεργασία Pj θα πρέπει να δει στο history(i) της, ένα μήνυμα από τη διεργασία Pi με λογικό χρόνο μεγαλύτερο από τον tj και έτσι μεγαλύτερο από τον ti. Τότε η FIFO ιδιότητα του καναλιού επικοινωνίας των διεργασιών Pi και Pj συνεπάγεται ότι η διεργασία Pj πρέπει να έχει δει το πιο πρόσφατο μήνυμα try της διεργασίας Pi όταν αυτή εκτέλεσε το critj. Όμως από τις προϋποθέσεις του critj υπονοείται ότι η διεργασία Pj πρέπει να έχει δει ένα μήνυμα exit από την διεργασία Pi. Αυτό συνεπάγεται ότι η διεργασία Pi πρέπει να έχει ήδη αφήσει το C την ώρα που η διεργασία Pj εκτελούσε το critj, το οποίο είναι άτοπο. ☐
Στη συνέχεια ισχυριζόμαστε για το lockout-freedom. Το lockout-freedom για τη δοκιμαζόμενη περιοχή θεωρεί ότι οι αιτήσεις των γεγονότων λαμβάνονται με τη σειρά των λογικών χρόνων των try μηνυμάτων τους. Συμφωνούμε ότι ένα try μήνυμα με το μικρότερο λογικό χρόνο ανάμεσε σε όλες τις πρόσφατες αιτήσεις τελικά λαμβάνει μια απάντηση crit. Το ότι υπάρχουν πεπερασμένα άπειρα try μηνύματα τα οποία έχουν λογικούς χρόνους μικρότερους από κάθε άλλο try μήνυμα, είναι ένα επιχείρημα που μπορεί να χρησιμοποιηθεί για να δείξει ότι όλες οι αιτήσεις είναι εγγυημένες.
Έτσι υποθέτουμε ότι η διεργασία Pi είναι στον Τ και έχει το try μήνυμα με το μικρότερο λογικό χρόνο ti, μεταξύ αυτών με τις πρόσφατες αιτήσεις. Συμφωνούμε ότι τελικά η συνθήκη για το criti πρέπει να ικανοποιηθεί και να παραμείνει ικανοποιημένη μέχρι το criti να συμβεί. Η ιδιότητα της αμεροληψίας για το κανάλι μετάδοσης εφαρμόζεται και τελικά η διεργασία Pi λαμβάνει το δικό της try μήνυμα το οποίο τοποθετεί στο history(i)i. Επίσης, αφού τα μηνύματα try λαμβάνουν μηνύματα ack και οι μεταβλητές του ρολογιού χειρίζονται χρησιμοποιώντας τις αρχές του LamportTime, τελικά η διεργασία Pi αποκτά ένα μήνυμα για κάθε άλλη διεργασία με λογικό ρολόι μεγαλύτερο του ti. Τελικά, αφού η αίτηση της διεργασίας Pi είναι η τρέχουσα αίτηση με το μικρότερο λογικό ρολόι, κάθε αίτηση με μικρότερο λογικό ρολόι πρέπει να έχει ήδη ένα γεγονός exit. Στη συνέχεια η ιδιότητα της αμεροληψίας της μετάδοσης στο κανάλι συνεπάγεται ότι τελικά η διεργασία Pi λάμβανε αυτό το μήνυμα exit. Με αυτό τον τρόπο, όλες οι προϋποθέσεις για το criti πρέπει τελικά να ικανοποιούνται.
Εναλλακτικά τα παραπάνω είναι:
Για την ασφάλεια θα υποθέσουμε ότι δεν τηρείται και θα καταλήξουμε σε άτοπο. Συγκεκριμένα:
- Έστω ότι σε κάποια φάση και καθώς εκτελείται ο αλγόριθμος στο κρίσιμο τμήμα υπάρχουν 2 διεργασίες η 1 και η 2. Έστω επίσης ότι η 1 έστειλε το μήνυμα για request με κάποιο logical time μικρότερο από ότι η 2. Σύμφωνα με τον αλγόριθμο, η διεργασία 1 έχει δει την αίτηση της 2 και την είχε κρατήσει στην ουρά της και όμοια η 2 είχε δει την αίτηση της 1 και την είχε κρατήσει στην ουρά της. Ωστόσο αφού είπαμε ότι ισχύει ότι το logical time της 1 είναι μικρότερο από ότι της 2, η 2 για να μπει στο κρίσιμο τμήμα θα περιμένει οπωσδήποτε το μήνυμα που θα ενημερώνει για την απελευθέρωση του πόρου από την 1. Κάτι τέτοιο σημαίνει ότι η 1 θα έχει βγει από το κρίσιμο τμήμα πριν μπει η 2. Άρα δεν θα είναι και οι δύο μαζί στο κρίσιμο τμήμα πράγμα άτοπο σε σχέση με αυτό που ισχυριστήκαμε στην αρχή.
- Όσον αφορά την διάταξη, αυτή εξασφαλίζεται χάρη στο λογικό ρολόι που κρατά η κάθε διεργασία και στο ότι κάθε μήνυμα request που αποστέλλεται φέρει την χρονοσφραγίδα της διεργασίας. Βέβαια μην ξεχνάμε ότι τρέχει συγχρόνως και ο LamportTime αλγόριθμος για να ρυθμίζεται σωστά το λογικό ρολόι. Έτσι δεν είναι δυνατόν να χαθεί η διάταξη στις αιτήσεις για δέσμευση του πόρου.
- Βιωσιμότητα τώρα μπορούμε να πετύχουμε εξασφαλίζοντας ότι δεν θα παραμένει άπειρο χρονικό διάστημα μια διεργασία για να εισέλθει στο κρίσιμο τμήμα από την ώρα που θα κάνει αίτηση. Εδώ ας μην ξεχνάμε ότι δεν μετράμε την περίπτωση σφαλμάτων επικοινωνίας. Έτσι σε περίπτωση που προφανώς δεν έχουμε άπειρες αιτήσεις, κάτι ρεαλιστικό αφού δεν θα έχουμε και άπειρες διεργασίες, όποιες διεργασίες εισέλθουν στον κρίσιμο τμήμα κάποια στιγμή θα βγούνε κιόλας μετά από πεπερασμένο χρόνο. Συνεπώς, θα στείλουν μήνυμα σε όλες τις άλλες ότι ο πόρος είναι ελεύθερος. Μοιραία έτσι δεν γίνεται η σειρά κάποιας διεργασίας να εισέλθει στο κρίσιμο τμήμα, από την στιγμή που έχει κάνει αίτηση, να μην έρθει ποτέ.
Ανάλυση πολυπλοκότητας:
Για την πολυπλοκότητα επικοινωνίας, σημειώνουμε ότι στον αλγόριθμο LogicalTimeME, σε αντίθεση με τον αλγόριθμο CirculatingToken, όλα τα μηνύματα αντιστοιχούν σε συγκεκριμένες αιτήσεις. Έτσι μετράμε τον αριθμό των μηνυμάτων ανά αίτηση. Για κάθε αίτηση, υπάρχει μόνο μία μετάδοσης του try και μία του exit, για ένα σύνολο 2n ατομικών μηνυμάτων, συν n-1 μηνύματα ack τα οποία στέλνονται σαν απάντηση των μηνυμάτων try. Έτσι συνολικά υπάρχουν 3n-1 μηνύματα ανά αίτηση για κάθε αίτηση μέχρι να εισέλθει και να εξέλθει τελικά η διεργασία στο κρίσιμο τμήμα. Για να μπει μία διεργασία στο κρίσιμο τμήμα χρειάζεται ανταλλαγή 2(n-1) μηνυμάτων.
Για την χρονική πολυπλοκότητα, θεωρούμε αρχικά την περίπτωση μιας μεμονωμένης αίτησης από ένα χρήστη Ui. Στην πραγματικότητα, θεωρούμε μια ισχυρή μεμονωμένη αίτηση, για την οποία επίσης απαιτούμε ότι κανένα κανένα μήνυμα από προηγούμενες αιτήσεις δεν παραμένει στην κατάσταση του συστήματος όταν ένα γεγονός tryi συμβαίνει. Σε αυτή την περίπτωση ο χρόνος από το tryi στο criti είναι το πολύ 2d+O(l), όπου d είναι το άνω όριο για την παράδοση του παλιότερου μηνύματος μετάδοσης ή μηνύματος point-to-point από κάθε διεργασία i σε κάθε άλλη διεργασία j. Σε αντίθεση, η χρονική πολυπλοκότητα του αλγόριθμου CirculatingToken έχει έναν όρο dn, ακόμα και στην περίπτωση μιας μεμονωμένης αίτησης.
Αφήνουμε τη γενικό χειρότερο άνω όριο για το χρόνο από ένα γεγονός tryi σε ένα γεγονός criti σαν άσκηση.
Μία συζήτηση πάνω στον αλγόριθμο είναι αν λύσαμε τελικά το πρόβλημα που είχαμε στον αλγόριθμο coordinator όπου αν η διεργασία coordinator σταματούσε να λειτουργεί έπρεπε να εκλέξουμε καινούριο αρχηγό και να ανακτήσουμε την ουρά της. Θα μπορούσε να πει κάποιος ότι αυτό λύθηκε. Όμως στην πραγματικότητα αυτό που κάναμε εδώ είναι όλες οι διεργασίες να είναι συντονιστές. Αυτό έχει σαν αποτέλεσμα ότι αν μία διεργασία πέσει, θα πάψει να λειτουργεί σωστά ο αλγόριθμος καθώς για την αποδοχή των αιτήσεων θα πρέπει να ληφθούν μηνύματα από όλες τις διεργασίες για να έχουμε έγκυρη αίτηση. Συνεπώς το πρόβλημά μας αν και μοιάζει να λύθηκε είναι τελικά πιο μεγάλο καθώς ακόμα και μία διεργασία να έχει πρόβλημα θα σταματήσει όλος ο αλγόριθμος να λειτουργεί.
