Σημειώσεις:Προβλήματα:Αμοιβαίος Αποκλεισμός
Από DistrSys
Το πρόβλημα του αμοιβαίου αποκλεισμού διατυπώθηκε για πρώτη φορά από τον Edsger Dijkstra to 1965 και έκτοτε απασχόλησε πολύ τα κατανεμημένα συστήματα.
Γενικά μπορούμε να το ορίσουμε ως εξής: Υπάρχουν ένας ή περισσότεροι πόροι και πολλές διεργασίες οι οποίες θέλουν να αποκτήσουν αποκλειστική πρόσβαση σε αυτούς. Επομένως, θέλουμε να εξασφαλίσουμε πως σε κάθε πόρο θα βρίσκεται το πολύ μία διεργασία κάθε χρονική στιγμή. Θα μπορούσαμε να το σκεφτούμε σαν έναν εκτυπωτή σε ένα δίκτυο στον οποίο πολλοί χρήστες θέλουν να εκτυπώσουν τα έγγραφά τους.
Βασική παραδοχή είναι ότι δεν ξέρουμε πότε κάθε διεργασία θα κάνει αίτηση για να μπει μέσα στον πόρο. Το μέρος του κώδικα της διεργασίας που χρειάζεται να χειριστεί τον πόρο αποκλειστικά ονομάζεται κρίσιμο τμήμα. Το πρόβλημα μπορεί να λυθεί είτε με κατανεμημένο είτε με κεντρικοποιημένο τρόπο. Στα λειτουργικά συστήματα συναντάμε κεντρικοποιημένες λύσεις στο πρόβλημα όπως semaphores, συντονιστές και άλλες.
Για να εστιάσουμε στις ιδιαιτερότητες του προβλήματος περιορίζουμε το μοντέλο επικοινωνίας κάνοντας ορισμένες ειδικές υποθέσεις. Συγκεκριμένα, υποθέτουμε ότι οι διεργασίες έχουν μοναδική ταυτότητα. Αν μία διεργασία δεν έχει μέρος του κώδικά της σε κρίσιμο τμήμα, δεν μας απασχολεί στην λύση του προβλήματος. Συνεπώς υποθέτουμε ότι στο σύστημά μας όλες οι διεργασίες έχουν κάποιο κομμάτι του κώδικά τους σε κρίσιμο τμήμα και συνεπώς θέλουν αποκλειστική πρόσβαση σε κάποιο πόρο. Υποθέτουμε επίσης ότι δεν υπάρχει κάποιο καθολικό ρολόι. Ως προς το δίκτυο επικοινωνίας, υποθέτουμε ότι τα κανάλια μας είναι αξιόπιστα και FIFO αποκλείουμε δηλαδή την περίπτωση σφαλμάτων επικοινωνίας. Τέλος, για να καταφέρουμε να βρούμε μια πρώτη λύση θα υποθέσουμε ότι το δίκτυό μας είναι πλήρες και ότι ο πόρος για τον οποίο συναγωνίζονται οι διεργασίες είναι ένας.
Ένας αλγόριθμος θεωρούμε ότι λύνει το πρόβλημα του αμοιβαίου αποκλεισμού εφόσον πληροί συγκεκριμένες προδιαγραφές:
- Ασφάλεια (safety): Με τον όρο ασφάλεια εννοούμε να μπορεί μόνο μία διεργασία να αποκτήσει πρόσβαση σε έναν πόρο.
- Βιωσιμότητα (liveness) : Βιωσιμότητα του αλγορίθμου νοείται σε δύο επίπεδα. Ένα είναι η αποφυγή αδιεξόδου για τις διεργασίες, δηλαδή ότι αν κάποια διεργασία θέλει να μπει στον πόρο τελικά αυτό θα γίνει κάποτε. Το άλλο είναι ότι πρέπει να διασφαλίζεται σε περίπτωση που ο πόρος είναι ελεύθερος, δηλαδή καμία διεργασία δεν είναι σε κρίσιμο τμήμα, και επιπλέον υπάρχει μία αίτηση εισόδου, τότε αυτή η αίτηση θα γίνει αποδεκτή και η διεργασία που την έχει κάνει θα μπει στον πόρο σε πεπερασμένο χρονικό διάστημα.
- Διάταξη: Πρέπει οι αιτήσεις των διεργασιών να ικανοποιούνται με την σειρά με την οποία έγιναν. Με άλλα λόγια να ισχύει η σχέση συνέβη πριν.
Κριτήρια για την αποδοχή ή όχι ενός αλγορίθμου που λύνει το πρόβλημα του αμοιβαίου αποκλεισμού είναι τα παρακάτω:
- Ορθότητα (Correctness): Για να είναι αποδεκτός ο αλγόριθμός μας θα πρέπει οπωσδήποτε πρώτα από όλα να είναι σωστός. Αυτό ισχύει όταν οι παραπάνω τρεις συνθήκες για ασφάλεια, βιωσιμότητα και διάταξη ικανοποιούνται.
- Πολυπλοκότητα επικοινωνίας (Communication Complexity): Όπως σε κάθε αλγόριθμο έτσι και εδώ θέλουμε όσο γίνεται να περιορίσουμε την αποστολή μηνυμάτων κατά την επεξεργασία των αιτήσεων.
- Απόκριση (Latency): Ελαχιστοποίηση της καθυστέρησης εισόδου στο κρίσιμο τμήμα.
Αλγόριθμοι Αμοιβαίου Αποκλεισμού:
