Αμοιβαίος αποκλεισμός (υπολογιστές): Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Ggia (συζήτηση | συνεισφορές) Χωρίς σύνοψη επεξεργασίας |
Ggia (συζήτηση | συνεισφορές) Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 1:
[[File:Mutual exclusion example with linked list.png|400px|thumb|'''Παράδειγμα''': Δύο κόμβοι, ''i'' και ''i+1'', αφαιρούνται ταυτόχρονα με αποτέλεσμα ο κόμβος ''i+1'' τελικά να μην αφαιρείται.]]
Στην [[Πληροφορική|επιστήμη των υπολογιστών]] με τον όρο '''αμοιβαίο αποκλεισμό''' ([[Αγγλικά]]: ''Mutual exclusion'') αναφερόμαστε στην διασφάλιση παράλληλων διεργασιών όταν φτάνουν σε μια ''κρίσιμη περιοχή'' όπου υπάρχει διαμοιρασμός πόρων (όπως μια κοινή θέση μνήμης). Η ιδέα είναι να υπάρξει κάποιος μηχανισμός ώστε όταν δύο παράλληλες διεργασίες θέλουν να χρησιμοποιήσουν ένα κοινό πόρο να μην υπάρχει σύγκρουση επεξεργασίας αλλά να διασφαλίζεται ένας αμοιβαίος αποκλεισμός. Το πρόβλημα αυτό μελετήθηκε από τον [[Έντσγκερ Ντάικστρα|Ντάικστρα]] σε ακαδημαϊκή δημοσίευση το 1965 με τίτλο ''Λύση στο πρόβλημα ελέγχου παράλληλων και ταυτόχρονων προγραμμάτων''. Θεωρείται ο πρώτος που ασχολήθηκε με ταυτόχρονους αλγόριθμους. <ref>{{cite journal|last=Dijkstra|first=E. W.|title=Solution of a problem in concurrent programming control|journal=Communications of the ACM|volume=8|issue=9|pages=569|doi=10.1145/365559.365617|year=1965}}</ref><ref name="Taubenfeld:2004">Taubenfeld, [http://www.cs.tau.ac.il/~afek/gadi.pdf The Black-White Bakery Algorithm]. In Proc. Distributed Computing, 18th international conference, DISC 2004. Vol 18, 56-70, 2004</ref> <ref>{{Citation | url=http://www.podc.org/influential/2002.html | title=PODC Influential Paper Award: 2002 | work=ACM Symposium on Principles of Distributed Computing | accessdate=2009-08-24}}</ref>
Με τον αμοιβαίο αποκλεισμό μπορούν να επιλυθούν πολλά προβλήματα που προκύπτουν από την ταυτόχρονη προσπέλαση κοινών πόρων. Τέτοια ζητήματα εμφανίζονται κυρίως (αλλά όχι αποκλειστικά) στο χώρο των [[λειτουργικό σύστημα|λειτουργικών συστημάτων]] αλλά και των [[βάση δεδομένων|βάσεων δεδομένων]]. Οι [[σημαφόρος (υπολογιστές)|σημαφόροι]] αποτελούν μηχανισμό με τον οποίο μπορεί να επιτευχθεί αμοιβαίος αποκλεισμός μεταξύ δύο ή περισσοτέρων διεργασιών.
Ένα απλό παράδειγμα γιατί ο αμοιβαίος αποκλεισμός είναι σημαντικός στην πράξη μπορεί να φανεί για παράδειγμα με μια απλή συνδεδεμένη λίστα. Σε αυτή την λίστα η αφαίρεση ενός κόμβου γίνεται αλλάζοντας τον δείκτη που δείχνει στον επόμενο κόβμο. Για παράδειγμα ένα ο κόμβος '''i''' θέλουμε να αφαιρεθεί τότε το επόμενος δείκτης του '''i-1''' θα αλλαχθεί ώστε να δείνχει τον κόμβο '''i+1'''. Στην περίπτωση που η συνδεδεμένη λίστα είναι προσβάσιμη από δύο παράλληλες διεργασίες και στην περίπτωση που και οι δύο διεργασίες προσπαθήσουν να αφαιρέσουν δύο διαφορετικούς κόμβους παράλληλα θα αντιμετωπίσουμε το παρακάτω πρόβλημα: έστω οι κόμβοι '''i''' και '''i+1''' θέλουμε να αφαιρεθούν. Μετά την αφαίρεση ο κόμβος '''i-1''' θα δείχνει τον '''i+1''' ενώ ο κόμβος ''i'' θα δείχνει στον '''i+2'''. Παρόλο που οι δύο διεργασίες θα ολοκληρώσουν παράλληλα και με επιτυχία τις αφαιρέσεις των δύο κόμβων στην πράξη ο κόμβος '''i+1''' δεν αφαιρείται. Για να λυθεί σωστά το πρόβλημα θα πρέπει να απαιτείται ο αμοιβαίος αποκλεισμών των διεργασίων όταν οι διεργασίες φτάνουν στην κρίσιμη περιοχή όπου πρέπει να αφαιρεθεί ο κόμβος. Όταν η μια διεργασία αμοιβαία αποκλείει την άλλη κατά την κρίσιμη περιοχή η αφαίρεση και των δύο κόμβων μπορεί να γίνει με επιτυχία.
==Παραπομπές==
{{παραπομπές}}
{{ενσωμάτωση κειμένου|en|Mutual exclusion}}
[[Κατηγορία:Προγραμματισμός]]
| |||