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

Από DistrSys

LamportTime

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

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

Χρονική: χρόνος επεξεργασίας timestamps Επικοινωνίας: αύξηση κατα sizeof(timestamp) στο μέγεθος των μηνυμάτων

Στη σύνταξη του κειμένου συνεισέφερε ο Αμαξηλάτης Δημήτριος και ο Μάριος Λογαράς

Είδαμε ότι αντί για φυσικά ρολόγια και όποιες δυσκολίες στον συγχρονισμό αυτά έχουν, μπορούμε να χρησιμοποιήσουμε λογικά ρολόγια στην θέση τους. Ας τα ορίσουμε λίγο πιο αυστηρά.

Στον λογικό χρόνο το μόνο που μας ενδιαφέρει είναι να δώσουμε κάποια τιμή από ένα πλήρως διατεταγμένο σύνολο T, είναι αυτό που είπαμε πριν χρονοσφραγίδα. Έτσι η σχέση συνέβη πριν σi->σj θα μπορεί να γραφτεί ως TS(σi) < TS(σj). O Lamport στην ίδια εργασία προτείνει έναν απλό μηχανισμό για τις χρονοσφραγίδες έτσι ώστε να ικανοποιείται η σχέση συνέβη πριν. Μάλιστα έδωσε στον μηχανισμό του το όνομα λογικό ρολόι. Το λογικό ρολόι του Lamport είναι ένας μονότονα αυξανόμενος μετρητής που δεν έχει κάποια σχέση με το φυσικό ρολόι. Η κάθε διεργασία Pu έχει το δικό της λογικό ρολόι (logical clock) LCu. Η τιμή του λογικού ρολογιού αυξάνεται κάθε φορά που συμβαίνει ένα συμβάν. Το συμβάν παίρνει την τιμή του λογικού ρολογιού σαν λογικό χρόνο στον οποίο πραγματοποιήθηκε. Αναλυτικότερα:

• Όλες οι διεργασίες κρατούν μία μεταβλητή LC που παίρνει μη αρνητικές τιμές και παίζει τον ρόλο του λογικού ρολογιού. Η μεταβλητή ξεκινά με αρχική τιμή 0.
• Κάθε φορά που κάποιο συμβάν πραγματοποιείται, το λογικό ρολόι αυξάνεται κατά 1 και το συμβάν παίρνει την χρονοσφαγίδα του.
• Σε κάθε μήνυμα που στέλνεται η διεργασία που το στέλνει ενσωματώνει και την τρέχουσα τιμή του λογικού ρολογιού της.
• Σε κάθε μήνυμα που λαμβάνεται η διεργασία παραλήπτης συγκρίνει το δικό της LC με αυτό της διεργασίας που έστειλε το μήνυμα και επαναπροσδιορίζει το λογικό ρολόι της σε max{LC,TS(m)}+1. (TS(m) είναι η χρονοσφραγίδα που φέρει το μήνυμα m που λήφθηκε). Δηλαδή, το μήνυμα που παραλήφθηκε θα πάρει σαν χρονοσφαγίδα το TS(m)+1 ή το LC+1 ανάλογα. Έτσι κατά κάποιο τρόπο εξασφαλίζουμε κάτι σαν συχρονισμό ή καλύτερα καταφέρνουμε να διατηρήσουμε την σωστή χρονολογική σειρά των συμβάντων που είναι εξαρτώμενα.

Ο παραπάνω αλγόριθμος μας εξασφαλίζει ότι: Αν για δύο συμβάντα σ_i, σ_j ισχύει σ_i->σ_j δηλαδή το σ_i συνέβη πριν το σ_j, τότε ο αλγόριθμος εξασφαλίζει ότι TS(σ_i)<TS(σ_j). Το αντίστροφο δεν ισχύει, δηλαδή για σi, σj και με δεδομένο ότι ισχύει TS(σ_i)<TS(σ_j) δεν μπορούμε να πούμε ότι το σ_i συνέβη πριν το σ_j. Αυτό οφείλεται στα λογικά ανεξάρτητα γεγονότα που όπως είπαμε έχουν κάποια σειρά αλλά δεν συνδέονται μεταξύ τους μέσω της σχέσης συνέβη πριν.

Επιπλέον δεν εξασφαλίζεται ότι δύο συμβάντα που είναι λογικά ανεξάρτητα θα έχουν διαφορετικές χρονοσφραγίδες. Αυτό θα μπορούσε να είναι πρόβλημα γιατί είπαμε ότι θέλουμε το κάθε συμβάν να έχει διαφορετική χρονοσφραγίδα από οποιοδήποτε άλλο. Μία λύση είναι μαζί με την χρονοσφραγίδα να χρησιμοποιείται σαν κριτήριο και η διεργασία όπου γίνεται το συμβάν. Πρέπει βέβαια να εξασφαλίζουμε την μοναδικότητα των ταυτοτήτων γιατί αλλιώς το πρόβλημα ανακυκλώνεται και με περισσότερα δεδομένα μάλιστα να αποστέλλονται. Συνεπώς, για τα συμβάντα σ_ui και σ_vi που έχουν την ίδια χρονοσφραγίδα αλλά είναι σε διαφορετικές διεργασίες στην u και την v αντίστοιχα, θα είχαμε της χρονοσφραγίδες i.u και i.v οι οποίες μπορούν διαταχθούν με την χρήση κάποιου κανόνα με μοναδικό τρόπο. Πχ αν u=15, v=306 και i=11 τότε έχουμε τις χρονοσφραγίδες 11.15 και 11.306 και ένας κανόνας που θα έθετε μπροστά χρονικά την διεργασία με την μικρότερη ταυτότητα, θα έδινε 11.15 πιο μπροστά χρονικά από την 11.306.

Υλοποίηση αλγόριθμου

Για την υλοποίηση του αλγορίθμου του Lamport υπάρχουν δύο τεχνικές. Η μία είναι να δούμε το πρόβλημα με παρόμοιο τρόπο με τους συγχρονιστές και να δημιουργήσουμε ένα ενδιάμεσο επίπεδο ανάμεσα στις διεργασίες μας που να υλοποιεί τον αλγόριθμο εκτελώντας τις λειτουργίες του με την αποστολή και παραλαβή μηνυμάτων. Βέβαια η P πρέπει να ενημερώνει τον αλγόριθμο και για τα εσωτερικά (αν μπορούμε να τα πούμε έτσι) συμβάντα που δεν έχουν σχέση με αποστολή/παραλαβή μηνύματος.

LamportTime

Δίνουμε συνοπτικά την συμπεριφορά του αυτομάτου L.

Ενέργειες:

Εισόδου αυτομάτου L: Send(m) – αποστολή μηνύματος m από την P.
                     AdvanceClock – όταν ένα συμβάν εσωτερικό της P έχει προκύψει πρέπει να αυξηθεί το ρολόι.
                     Receive(m,Clock) – λήψη ενός μηνύματος από το εισερχόμενο κανάλι προς την P.

Εξόδου αυτομάτου L:  Receive(m) – παραλαβή μηνύματος m από την P
                     Send(m,Clock) – αποστολή μηνύματος m από την P προς το εξερχόμενο κανάλι.

Καταστάσεις:         Clocku – το αυτόματο αλλάζει κατάσταση όταν αυξηθεί το λογικό ρολόι όταν δηλαδή κάποιο συμβάν πραγματοποιηθεί.

Μεταβάσεις:          Send(m)
                     Clock++
                     send(m,Clock)
                     AdvanceClock
                     Clock++
                     Receive(m,c)
                     Clock = max(Clock,c) + 1
                     Receive(m)

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

LamportTime

Το αυτόματο αυτό θα έχει την εξής συμπεριφορά:

Ενέργειες:   Το αυτόματο θα έχει σίγουρα τις ενέργειες της διεργασίας P
             Επιπλέον η ενέργεια send(m) αντικαθίσταται απο την send(m, clock)  και η receive(m) απο την receive(m, clock).

Καταστάσεις: Ίδιες με το αυτόματο της P. 
             Επιπλέον το λογικό ρολόι clock με αρχική τιμή 0.

Μεταβάσεις:  Για ενέργειες εισόδου εξόδου και εσωτερικές που δεν είναι Send ή Receive οι μεταβάσεις θα είναι ίδιες με αυτές της διεργασίας P πρωτού προσθέσουμε κάτι. Αποτέλεσμά τους θα είναι η αύξηση του 
             ρολογιού   (clock++).
             Όταν τώρα έχουμε send(m, c) θα έχουμε ακριβώς τα ίδια που γίνονταν πριν επέμβουμε στον αλγόριθμο της P  και επιπλέον θα έχουμε αποστολή της μεταβλητής c που θα έχει γίνει c = clock + 1. Με την    
             πραγματοποίηση του συμβάντος έχουμε clock = c. Δηλαδή πρακτικά την αύξηση του ρολογιού κατά 1.
             Οι μεταβάσεις κατά ένα Receive(m, c) θα είναι οι ίδιες με πριν και επιπλέον θα γίνεται clock = max(clock, c) + 1.