Σημειώσεις:Κατανεμημένοι Αλγόριθμοι:Coordinator
Από DistrSys
| Coordinator |
| Πρόβλημα: Αμοιβαίος Αποκλεισμός Δίκτυο: Γενικό Κλάση: - |
|
|
| Πολυπλοκότητα |
| Χρονική: - Επικοινωνίας: - |
|
|
| - |
Ο πρώτος αλγόριθμος που θα εξετάσουμε είναι ο αλγόριθμος Coordinator. Είναι πολύ απλός και στηρίζεται στο ότι θα υπάρχει μία διεργασία συντονιστής (coordinator) για να ρυθμίζει ποια διεργασία θα μπει στον πόρο. Η διεργασία αυτή έστω Pc θα αποφασιστεί ποια θα είναι μέσω εκλογής αρχηγού. Με το που θα ξεκινήσει το σύστημα όλες οι διεργασίες θα ξεκινήσουν την διαδικασία εκλογής αρχηγού. Μετά την εκλογή της, η Pc θα είναι έτοιμη να δέχεται μέσω μηνυμάτων αιτήσεις για τον πόρο. Για αυτό τον λόγο θα διατηρεί μία ουρά προτεραιότητας FIFO για να μπαίνουν με την σωστή σειρά στον πόρο οι διεργασίες. Όταν ο πόρος είναι ελεύθερος και η ουρά δεν είναι άδεια, η διεργασία coordinator Pc στέλνει ένα μήνυμα στην διεργασία που είναι πρώτη στην ουρά να μπει στον πόρο και την βγάζει από την ουρά. Για να απελευθερωθεί ο πόρος η διεργασία που τον έχει στέλνει ένα μήνυμα στον coordinator για αυτόν τον λόγο. Συνεπώς υπάρχουν 3 τύποι μηνυμάτων στον αλγόριθμο : request, reply και release. Η διεργασία Pc είναι συντονιστής και του εαυτού της.
Ο αλγόριθμος ικανοποιεί και τις 3 συνθήκες ορθότητας που διατυπώσαμε πιο πάνω. Ωστόσο όπως γίνεται αντιληπτό η απλότητα του αλγορίθμου θα δημιουργεί κάποια προβλήματα. Η διεργασία συντονιστής είναι μία με αποτέλεσμα η συμφόρηση στο δίκτυο να πέφτει αποκλειστικά σε αυτήν, κάτι που μπορεί να κάνει το σύστημα αργό. Επιπλέον το σύστημα μας δεν είναι καθόλου ανεκτικό σε σφάλματα. Τα κανάλια επικοινωνίας που χρησιμοποιούνται ως επί το πλείστον είναι αυτά που έχουν μια κορυφή στην διεργασία συντονιστή συνεπώς αν βάλουμε μια πιθανότητα λάθους ακόμα και μικρή, τότε με τον μεγάλο όγκο των μηνυμάτων που περνάει από τα συγκεκριμένα κανάλια η πιθανότητα σφάλματος επικοινωνίας γίνεται μεγαλύτερη όσο περνά ο χρόνος. Μάλιστα, τα αποτελέσματα θα ήταν καταστροφικά αν σε κάποια περίπτωση χανόταν ένα μήνυμα απελευθέρωσης του πόρου ή ένα μήνυμα επίδοσης του πόρου καθώς τότε ο συντονιστής θα περίμενε για πάντα απάντηση για απελευθέρωση του πόρου. Επίσης υπάρχει και η πιθανότητα να δημιουργηθεί σφάλμα στην διεργασία που είναι coordinator. Τότε, θα πρέπει να ξαναρχίσει η εκτέλεση του αλγορίθμου από την εκλογή νέου αρχηγού, ενώ οι αιτήσεις που υπήρχαν πρέπει να ανακτηθούν και με την σωστή διάταξη με πριν από τον νέο συντονιστή αλλιώς θα χαθούν με ότι μπορεί να σημαίνει αυτό για το σύστημα μας.
Είδαμε λοιπόν ότι αν και αποδοτικός (μόλις δύο μηνύματα χρειάζονται για να μπει μία διεργασία στο κρίσιμο τμήμα – ένα για request και ένα reply από τον συντονιστή) ο αλγόριθμος μας έχει χαμηλή κλιμάκωση κάτι που μπορεί να οδηγήσει σε σοβαρά προβλήματα. Ωστόσο είναι ένας σωστός αλγόριθμος που μπορεί να χρησιμοποιηθεί.
