Αμοιβαίος αποκλεισμός (υπολογιστές)
Στην επιστήμη των υπολογιστών, με τον όρο αμοιβαίο αποκλεισμό (αγγλικά: mutual exclusion) αναφερόμαστε στη διασφάλιση παράλληλων διεργασιών να αποκτήσουν αποκλειστική πρόσβαση όταν φτάσουν σε μια κρίσιμη περιοχή (όπου υπάρχει διαμοιρασμός πόρων όπως για παράδειγμα μια κοινή θέση μνήμης). Η ιδέα είναι να υπάρξει ένας μηχανισμός ώστε όταν δύο παράλληλες διεργασίες θέλουν να χρησιμοποιήσουν ένα κοινό πόρο, να μην υπάρχει σύγκρουση επεξεργασίας αλλά να διασφαλίζεται ένας αμοιβαίος αποκλεισμός. Το πρόβλημα αυτό μελετήθηκε από τον Ντάικστρα σε ακαδημαϊκή δημοσίευση το 1965 με τίτλο Λύση στο πρόβλημα ελέγχου παράλληλων και ταυτόχρονων προγραμμάτων. Θεωρείται ο πρώτος που ασχολήθηκε με παράλληλους αλγόριθμους.[1][2][3]
Με τον αμοιβαίο αποκλεισμό μπορούν να επιλυθούν πολλά προβλήματα που προκύπτουν από την ταυτόχρονη προσπέλαση κοινών πόρων. Τέτοια ζητήματα εμφανίζονται κυρίως (αλλά όχι αποκλειστικά) στο χώρο των λειτουργικών συστημάτων αλλά και των βάσεων δεδομένων. Οι σημαφόροι (semaphores) υλοποιούν τον μηχανισμό με τον οποίο μπορεί να επιτευχθεί αμοιβαίος αποκλεισμός μεταξύ δύο ή περισσότερων διεργασιών.
Ένα απλό παράδειγμα γιατί ο αμοιβαίος αποκλεισμός είναι σημαντικός στην πράξη μπορεί να φανεί στο παράδειγμα μιας απλής συνδεδεμένης λίστας. Σε αυτή τη λίστα η αφαίρεση ενός κόμβου γίνεται αλλάζοντας τον δείκτη που δείχνει στον επόμενο κόμβο. Για παράδειγμα εάν ο κόμβος i θέλουμε να αφαιρεθεί, τότε το επόμενος δείκτης του i-1 θα αλλαχθεί ώστε να δείχνει τον κόμβο i+1. Στην περίπτωση που η συνδεδεμένη λίστα είναι προσβάσιμη από δύο παράλληλες διεργασίες και στην περίπτωση που και οι δύο διεργασίες προσπαθήσουν να αφαιρέσουν δύο διαφορετικούς κόμβους παράλληλα, ενδέχεται να αντιμετωπίσουμε το παρακάτω πρόβλημα: έστω οι κόμβοι i και i+1 που θέλουμε να αφαιρεθούν. Μετά την αφαίρεση ο κόμβος i-1 θα δείχνει τον i+1, ενώ ο κόμβος i θα δείχνει στον i+2. Παρόλο που οι δύο διεργασίες θα ολοκληρώσουν παράλληλα και με επιτυχία τις αφαιρέσεις των δύο κόμβων, στην πράξη ο κόμβος i+1 δεν αφαιρείται. Για να λυθεί σωστά το πρόβλημα θα πρέπει να απαιτείται ο αμοιβαίος αποκλεισμών των διεργασιών όταν οι διεργασίες φτάνουν στην κρίσιμη περιοχή αφαίρεσης του κόμβου. Όταν η μια διεργασία αμοιβαία αποκλείει την άλλη κατά την κρίσιμη περιοχή, η αφαίρεση και των δύο κόμβων σε συνδεδεμένη λίστα μπορεί να γίνει με επιτυχία.
Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ Dijkstra, E. W. (1965). «Solution of a problem in concurrent programming control». Communications of the ACM 8 (9): 569. doi:.
- ↑ Taubenfeld, The Black-White Bakery Algorithm. In Proc. Distributed Computing, 18th international conference, DISC 2004. Vol 18, 56-70, 2004
- ↑ PODC Influential Paper Award: 2002, http://www.podc.org/influential/2002.html, ανακτήθηκε στις 2009-08-24