Ο κύριος στόχος ενός λειτουργικού συστήματος είναι να παρέχει σωστή επικοινωνία μεταξύ πόρων υλικού και λογισμικού και επίσης να παρέχει κοινές υπηρεσίες σε προγράμματα. Όταν μια διαδικασία λειτουργικού συστήματος θέλει να αποκτήσει πρόσβαση σε οποιονδήποτε πόρο, αποστέλλει πρώτα ένα αίτημα στον συγκεκριμένο πόρο στον οποίο θέλει να αποκτήσει πρόσβαση, στη συνέχεια χρησιμοποιεί τον πόρο και τελικά απελευθερώνει τον πόρο μετά τη χρήση. Για να υποθέσουμε ότι πολλές διαδικασίες προσπαθούν να αποκτήσουν πρόσβαση σε έναν πόρο ταυτόχρονα, καθίσταται δύσκολη η παροχή ενός πόρου σε όλες τις διεργασίες ταυτόχρονα σε μια τέτοια κατάσταση, προκύπτει η έννοια που ονομάζεται αδιέξοδο Ως εκ τούτου, αυτό το άρθρο περιγράφει πώς συμβαίνει το αδιέξοδο και πώς να ξεπεραστεί αυτό το αδιέξοδο.
Τι είναι το αδιέξοδο στο λειτουργικό σύστημα;
Ορισμός: Το Dead-Lock είναι μια κατάσταση όπου δύο ή περισσότεροι επεξεργαστές περιμένουν κάποιο συμβάν, αλλά τέτοια γεγονότα που δεν συμβαίνουν είναι μια κατάσταση αδιεξόδου και οι επεξεργαστές λέγεται ότι βρίσκονται σε αδιέξοδο. Για παράδειγμα, ας υποθέσουμε ένα σενάριο σε πραγματικό χρόνο, όπου υπάρχουν δύο αυτοκίνητα A & B, που οδηγούνται από δύο μεμονωμένους οδηγούς σε μονόδρομο. Τώρα προκύπτει η κατάσταση όπου ο οδηγός αυτοκινήτου λέει ότι κινείται προς το βορρά είναι σωστή κατεύθυνση, ενώ ο οδηγός του αυτοκινήτου Β λέει ότι κινείται προς νότια κατεύθυνση είναι σωστή. Αλλά κανένας δεν κινείται πίσω για να επιτρέψει σε ένα άλλο αυτοκίνητο να κινηθεί προς τα εμπρός, αυτή η κατάσταση ονομάζεται κατάσταση αδιεξόδου.
παράδειγμα αυτοκινήτου
Για καλύτερη κατανόηση ας εξετάσουμε ένα άλλο παράδειγμα όπου υπάρχουν δύο πόροι R1, R2 και δύο διαδικασίες P1 και P2, όπου το R1 έχει αντιστοιχιστεί στο P1 και το R2 έχει αντιστοιχιστεί στο P2. Τώρα εάν το P1 θέλει να έχει πρόσβαση στο R2, όπως ήδη γνωρίζουμε, το R2 κρατάει το P2 και τώρα το P2 θέλει να έχει πρόσβαση στο R1, το οποίο P1 εκτελεί μόνο όταν έχει πρόσβαση στο R2, επίσης το P2 εκτελεί μόνο όταν έχει πρόσβαση στο R1 αυτή η κατάσταση είναι αδιέξοδο.
παράδειγμα επεξεργαστή
Συνθήκες Dead-Lock
Ακολουθούν οι τέσσερις σημαντικές συνθήκες αδιεξόδου που συμβαίνουν εάν όλες οι συνθήκες συμβαίνουν ταυτόχρονα, υπάρχουν ορισμένες πιθανότητες να συμβεί το αδιέξοδο.
Αμοιβαίος αποκλεισμός
Σημαίνει ότι ο πόρος που χρησιμοποιούμε πρέπει να χρησιμοποιείται με έναν αποκλειστικό τρόπο. Όπου μόνο μία διαδικασία χρησιμοποιεί μόνο έναν πόρο κάθε φορά. Για παράδειγμα, η διαδικασία εκτύπωσης συνεχίζεται και ξαφνικά μια άλλη διαδικασία προσπαθεί να διακόψει τη διαδικασία εκτύπωσης. Εδώ λοιπόν σε κατάσταση αμοιβαίου αποκλεισμού, μόνο μετά την ολοκλήρωση της εργασίας εκτύπωσης, τότε επεξεργάζεται μόνο η επόμενη εργασία. Ο αμοιβαίος αποκλεισμός μπορεί να εξαλειφθεί με κοινή χρήση πόρων ταυτόχρονα, κάτι που δεν είναι πρακτικά δυνατό.
αμοιβαίος αποκλεισμός
Χωρίς προτίμηση
Σύμφωνα με προαγοραστικός βασισμένοι αλγόριθμοι, εάν υπάρχει μια εργασία προτεραιότητας που προσπαθεί να διακόψει την τρέχουσα εργασία. Ο προληπτικός αλγόριθμος που κρατά την τρέχουσα εργασία και πρώτα εκτελεί την εργασία προτεραιότητας και επιστρέφει στην πρώτη του εργασία. Μια κατάσταση που εξηγείται σύμφωνα με το παραπάνω παράδειγμα όπου μια διαδικασία κρατά τον πόρο όσο εκτελείται, δηλαδή το P1 μπορεί να απελευθερώσει το R1 μόνο μετά την εκτέλεση, παρόμοια το P2 να απελευθερώνει το R2 μόνο μετά την εκτέλεση. Εάν δεν υπάρχει προτίμηση, ενδέχεται να προκύψει αδιέξοδο.
no-preemption-παράδειγμα
Κρατήστε και περιμένετε
Μια διαδικασία κρατά μερικούς πόρους και περιμένει επιπλέον πόρους, αλλά αυτοί οι πόροι αποκτώνται από κάποια άλλη διαδικασία. Από το παραπάνω παράδειγμα, το Ρ1 κρατά το R1 και περιμένει το R2, όπου το R2 αποκτάται από το P2, και το P2 κρατά το R2 και περιμένει το R1, όπου το R1 αποκτάται από το P1 είναι μια κατάσταση αναμονής και αναμονής μπορεί να συμβεί αδιέξοδο στο σύστημα.
παραμονή-και-περιμένετε-παράδειγμα
Κυκλική αναμονή
Ένα σύνολο διαδικασιών λέγεται ότι βρίσκεται σε αδιέξοδο εάν μια διαδικασία περιμένει έναν πόρο που έχει εκχωρηθεί σε μια άλλη διαδικασία και ότι η διαδικασία περιμένει έναν πόρο, είναι παρόμοιο με το παραπάνω εξηγημένο παράδειγμα όπου βρίσκεται σε μορφή βρόχου. Όπου το P1 περιμένει το R2 και το R2 κατανέμεται για το P2 και το P2 περιμένει το R1 και το R1 που διατίθενται για το P1 που είναι μια κυκλική φόρμα αναμονής εάν αυτή η συνθήκη ικανοποιεί το αδιέξοδο.
κυκλικό-αναμονή-παράδειγμα
Αλγόριθμος ανίχνευσης νεκρού κλειδώματος
Οι περιπτώσεις στις οποίες διαθέτουμε πόρους σε διαδικασίες και ελέγχουμε το λειτουργικό σύστημα εάν έχει προκύψει αδιέξοδο στο σύστημα ή όχι χρησιμοποιώντας 2 κύριους αλγόριθμους ανίχνευσης αδιεξόδου, είναι
- Μία περίπτωση
- Πολλαπλές εμφανίσεις τύπου πόρου
Ενιαία παρουσία
Ένα μόνο παράδειγμα είναι μια κατάσταση όπου ένα σύστημα έχει μεμονωμένες παρουσίες όλων των πόρων. Είναι επίσης γνωστό ως αναμονή αλγορίθμου γραφήματος ή γράφημα κατανομής πόρων. Το γράφημα κατανομής πόρων αποτελείται από ένα σύνολο διαδικασιών και ένα σύνολο πόρων που αντιπροσωπεύονται ως δύο διαφορετικές κορυφές. Οι πόροι στο γράφημα κατανομής πόρων τροποποιούνται και παρουσιάζονται ως αναμονή για τη φόρμα γραφήματος. Όπου η αναμονή για τη μορφή γραφήματος έχει μόνο διαδικασίες που αναπαριστώνται ως κορυφές όπως φαίνεται παρακάτω όπου,
- Γράφημα κατανομής πόρων: Οι διαδικασίες P1, P2, P3 και οι πόροι R1, R2, R3 παρουσιάζονται στο γράφημα κατανομής πόρων.
- Περιμένετε για το γράφημα: Αναφέρονται μόνο οι διαδικασίες P1, P2, P3 σε αναμονή για το γράφημα.
- Εάν υπάρχει μια κατάσταση κύκλου, ότι εάν υπάρχει συνεχής ροή μιας διαδικασίας προς μία κατεύθυνση, αυτό σημαίνει ότι η κατάσταση κύκλου βγαίνει και περιμένετε το γράφημα να βρίσκεται σε κατάσταση αδιέξοδου.
Παράδειγμα 1: Το παρακάτω παράδειγμα δείχνει ότι δεν υπάρχει κατάσταση αδιεξόδου επειδή δεν παρατηρείται συνεχής ροή εν αναμονή του γραφήματος.
μονή περίπτωση-παράδειγμα1
Παράδειγμα 2: Η κατάσταση αδιεξόδου έχει προκύψει επειδή υπάρχει συνεχής ροή κύκλου από P1 έως P4.
μονή περίπτωση-παράδειγμα2
Εάν το αδιέξοδο εμφανίζεται πολύ συχνά στο σύστημα, τότε ο αλγόριθμος ανίχνευσης χρησιμοποιείται συχνά. Εάν υπάρχει περισσότερη χρήση του αλγορίθμου ανίχνευσης, τότε θα υπάρχει περισσότερος γενικός και περισσότερος χρόνος υπολογισμού. Ως εκ τούτου, για να ξεπεραστεί αυτό, επικαλούμεμε τον αλγόριθμο μετά, δίνοντας ίσο χρονικό διάστημα, έτσι χρησιμοποιείται το βάρος για το γράφημα για την ανίχνευση αδιεξόδου.
Πολλαπλές εμφανίσεις τύπου πόρου
Πολλαπλές εμφανίσεις του τύπου πόρου είναι μια κατάσταση όπου ένα σύστημα έχει πολλές παρουσίες όλων των πόρων, είναι επίσης γνωστός ως αλγόριθμος Bankers. Σύμφωνα με τον αλγόριθμο Bankers, μόλις η διαδικασία πάρει όλους τους απαιτούμενους πόρους της, τότε απελευθερώνει τους πόρους της.
Ας εξετάσουμε το ακόλουθο παράδειγμα, ας υποθέσουμε ότι υπάρχουν 3 διεργασίες P0, P1, P2 και πόροι τύπου A, B, C όπου το A μπορεί να είναι ΕΠΕΞΕΡΓΑΣΤΗΣ , Το B μπορεί να είναι εκτυπωτής και το C μπορεί να είναι το πληκτρολόγιο. Τα ψηφία '0' στη στήλη αντιπροσωπεύουν τη διαθεσιμότητα πόρων.
Περίπτωση (i): Ας υποθέσουμε ότι αν λάβουμε το αίτημα συνθήκης είναι συνθήκη '000' που υπάρχει στα P0 και P2, θα πρέπει να ελέγξουμε ποια αίτηση πληρούται, οι διεργασίες P0 απελευθερώνουν τις διαδικασίες μετά την κατανομή, και στη συνέχεια οι επόμενες διεργασίες P2 απελευθερώνονται μετά την κατανομή. Έτσι, σε μια ακολουθία, μία προς μία διαδικασία απελευθερώνει P0, P2, P3, P1, P4 σε μια ακολουθία. Τέλος, έχουμε διαθέσιμους πόρους ως P7, P2, P6. Η διαθέσιμη ακολουθία είναι μια κατάσταση όπου δεν υπάρχει αδιέξοδο.
τραπεζίτες-αλγόριθμος-παράδειγμα1
Σπίτια (ii): Ας υποθέσουμε ότι εάν το P2 είναι 001 αντί για 000, εφαρμόστε τώρα τον αλγόριθμο του τραπεζίτη για να ελέγξετε την κατάσταση αδιεξόδου, όπου το μόνο P0 εκτελείται και στις 5 διαδικασίες. Ως εκ τούτου, τα P1, P2, P3, P4 βρίσκονται σε αδιέξοδο εκτός από το P0.
τραπεζίτες-παράδειγμα2
Εφαρμογές του αδιεξόδου
Οι αιτήσεις του αδιεξόδου μπορούν να εξηγηθούν με ένα πραγματικό χρόνο των διαδικτυακών αποτελεσμάτων των εξετάσεων, όπου αρκετοί φοιτητές προσπαθούν να αποκτήσουν πρόσβαση στον ιστότοπο του πανεπιστημίου τους κατά την κυκλοφορία. Κάποιος μπορεί να παρατηρήσει ότι κατά καιρούς η ιστοσελίδα δεν φορτώνει ταυτόχρονα σε πολλούς χρήστες, αυτή είναι μια κατάσταση αδιεξόδου. Αυτό μπορεί να ξεπεραστεί χρησιμοποιώντας οποιονδήποτε από τους αλγόριθμους.
Πλεονεκτήματα
Τα πλεονεκτήματα του αδιεξόδου είναι
- Δεν παρατηρείται προτίμηση στην αποφυγή αδιεξόδου
- Καμία καθυστέρηση στη διαδικασία
Μειονεκτήματα
Το μειονέκτημα του αδιεξόδου είναι
- Ο πόρος που θα χρησιμοποιηθεί πρέπει να είναι γνωστός εκ των προτέρων
- Αποκλεισμός της διαδικασίας για μεγάλο χρονικό διάστημα
- Οι απώλειες προτίμησης κληρονομούνται.
Αυτό το άρθρο περιγράφει τον τρόπο με τον οποίο συμβαίνει το αδιέξοδο όταν υπάρχουν δύο ή περισσότερες διεργασίες και οι τρεις συνθήκες που είναι η αιτία για το αδιέξοδο και οι δύο τύποι αλγορίθμων, δηλαδή ο αλγόριθμος κοινής χρήσης πόρων που εντοπίζει ότι υπάρχει κατάσταση αδιεξόδου και αλγόριθμος τραπεζιτών που είναι αλγόριθμος αποφυγής αδιεξόδου. Εδώ είναι η ερώτηση «Τι θα συμβεί εάν αγνοηθεί το αδιέξοδο;».
