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

Από DistrSys

RaymondME

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

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

Χρονική: - Επικοινωνίας: -

-

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

• Υπάρχει μία φάση αρχικοποίησης κατά την οποία όλες οι διεργασίες κατασκευάζουν ένα επικαλυπτικό δέντρο. Η ρίζα μπορεί να επιλεγεί τυχαία στην αρχή. Το δέντρο που θα δημιουργηθεί θα έχει κατευθυνόμενες ακμές με κατεύθυνση από τους γονείς προς τα παιδιά.
• Η ρίζα αναλαμβάνει να δημιουργήσει ένα μήνυμα – κουπόνι.
• Όταν κάποια διεργασία θέλει να κάνει αίτηση για χρησιμοποίηση του πόρου πρέπει να το δηλώσει στην ρίζα. Αυτή με την σειρά της στέλνει στην διεργασία το κουπόνι. Το κουπόνι για να πάει στην διεργασία που το ζήτησε διατρέχει κάποιες ακμές των οποίων αλλάζει την κατεύθυνση. Με αυτό τον τρόπο μετά από την παράδοση του κουπονιού η διεργασία που έκανε την αίτηση θα είναι πλέον η ρίζα του δέντρου.
• Κάθε διεργασία διατηρεί ένα δείκτη προς το μονοπάτι που οδηγεί στην ρίζα πρακτικά δηλαδή προς τον γονέα της την δεδομένη στιγμή που τρέχει ο αλγόριθμος, ενώ κρατάει και μία ουρά για το ποιες διεργασίες (συμπεριλαμβανομένου και του εαυτού της) έχουν κάνει αίτηση για να πάρουν το κουπόνι.

Όπως είπαμε και στην αρχή λόγω της ύπαρξης του επικαλυπτικού δέντρου τα μηνύματα που ανταλλάσσονται μέχρι να εξυπηρετηθεί μία αίτηση είναι O(logn).

Ακολουθεί παράδειγμα μιας εκτέλεσης του αλγορίθμου σε ένα δίκτυο με 5 διεργασίες, 6 κανάλια επικοινωνίας και με τις ουρές όλων των διεργασιών αρχικά άδειες, χωρίς να έχει γίνει δηλαδή ακόμα κάποια αίτηση.

image

Στην εικόνα 1 φαίνεται το αρχικό δίκτυο έτσι όπως έχει σχηματιστεί αμέσως μετά από την κατασκευή του επικαλυπτικού δέντρου. Τα κανάλια είναι οι διακεκομμένες μαύρες γραμμές ενώ τα κόκκινα βελάκια είναι οι κατευθυνόμενες ακτές του δέντρου.

Στην εικόνα 2 βλέπουμε ότι η διεργασία 4 θέλει το κουπόνι συνεπώς στην εικόνα 3 ακολουθώντας την ακμή του δέντρου ειδοποιεί με μήνυμα request για την αίτησή της. Στην εικόνα 4 η 5 ειδοποιεί την 1 ακολουθώντας την ακμή του δέντρου. Η 1 βάζει την 5 σαν διεκδικητή του πόρου. Πλέον η αίτηση έχει φτάσει στην ρίζα.

Στην εικόνα 5 η 3 αποφασίζει να διεκδικήσει και αυτήν τον πόρο. Συνεπώς βάζει στην ουρά της τον εαυτό της. Στην εικόνα 6 φαίνεται το request που κάνει η διεργασία 3 στην 5 επικοινωνώντας με βάση το δέντρο πάντα. Πλέον στην 5 υπάρχουν αιτήσεις και από την 4 και από την 3 με προτεραιότητα στην 4 που έκανε πρώτη αίτηση κάτι που φαίνεται και στην εικόνα 7. Η 5 δεν ξανακάνει αίτηση στην 1 για να πάρει το κουπόνι καθώς έχει ήδη κάνει.

image

Συνεχίζοντας την εκτέλεση φτάνουμε στην εικόνα 8 όπου βλέπουμε πως πλέον η διεργασία 1 που είναι ρίζα βλέπει ότι στην ουρά της υπάρχει η 5 συνεπώς δίνει το κουπόνι στην 5 και ταυτόχρονα η ακμή αλλάζει φορά με αποτέλεσμα στο δέντρο μας να είναι πλέον ρίζα η 5 που έχει και το κουπόνι. Αν στην πρώτη θέση της ουράς είχε 5 τότε θα κρατούσε το κουπόνι και θα δέσμευε τον πόρο. Ωστόσο έχει 4 συνεπώς όπως φαίνεται και στην εικόνα 9 θα στείλει το κουπόνι στην 4 και θα αλλάξει η φορά της ακμής ώστε να γίνει πλέον ρίζα του δέντρου η 4. Επιπλέον η αίτηση της 4 σβήνεται από την ουρά της 5. Έπειτα αφού η 4 πάρει το κουπόνι θα σβήσει την αίτησή της από την ουρά της και θα δεσμεύσει τον πόρο (εικόνα 10).

Στην εικόνα 11 φαίνεται ότι η 5 έχοντας πλέον στην ουρά της το 3 και χωρίς να είναι πια ρίζα κάνει αίτηση στην ρίζα (4) για να πάρει το κουπόνι. Ταυτόχρονα η 4 βάζει την 5 στην ουρά της. Η 4 στην εικόνα 12 φαίνεται να έχει απελευθερώσει τον πόρο συνεπώς δίνει το κουπόνι στην 5 και την σβήνει από την ουρά της, αλλάζοντας και την φορά του καναλιού μεταξύ τους. Έτσι η 5 είναι πλέον ρίζα. Τέλος η 5 βλέπει πως έχει αίτηση από την 3 και της παραχωρεί το κουπόνι ενώ αλλάζει και την κατεύθυνση της ακμής κάνοντας την 3 ρίζα (εικόνα 13).