Αδιέξοδα

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Πόροι

Ένα σύνολο διεργασιών βρίσκεται σε αδιέξοδο (deadlock) αν κάθε διεργασία του συνόλου περιμένει ένα γεγονός που μόνο μια άλλη διεργασία του συνόλου μπορεί να προκαλέσει. (Tanenbaum)

Τα αδιέξοδα δημιουργούνται ως αποτέλεσμα της διαχείρισης των πόρων από τις διαδικασίες. Κάθε πόρος (resource) μπορεί να είναι προεκχωρήσιμος (preemptable) δηλαδή να αποδεσμευτεί από μια διεργασία που τον κατέχει χωρίς παρενέργιες ή μη προεκχωρήσιμος (nonpreemptable). Παραδείγματα της πρώτης κατηγορίας είναι ο δίσκος και η μνήμη. Παραδείγματα της δεύτερης κατηγορίας είναι ο εκτυπωτής και η μονάδα ταινίας. Τυπικά μια διεργασία χρησιμοποιεί έναν πόρο ως εξής:

Ζητά τον πόρο από το λειτουργικό σύστημα (αίτηση χρήσης).
Χρησιμοποιεί τον πόρο.
Ενημερώνει το λειτουργικό σύστημα ότι δε χρειάζεται άλλο τον πόρο (αποδέσμευση).

Η διαδικασία της αίτησης και η αντιμετώπιση αιτήσεων που δεν μπορούν να καλυφθούν εξαρτόνται από το λειτουργικό σύστημα.

Αδιέξοδα και μοντελοποίησή τους

Οι παρακάτω συνθήκες πρέπει να ικανοποιούνται για να δημιουργηθεί αδιέξοδο:

Αμοιβαίος αποκλεισμός: Κάθε πόρος είναι δεσμευμένος ή διαθέσιμος.
Δέσμευση και αναμονή: Διεργασίες που δεσμεύουν πόρους μπορούν να ζητούν και νέους.
Μη προεκχώρηση: Μόνο η διεργασία που έχει δεσμεύσει τους πόρους μπορεί να τους αποδεσμεύσει.
Κυκλική αναμονή: Οι διαδικασίες που ζητούν πόρους πρέπει να σχηματίζουν κύκλο.

Με βάση την τελευταία συνθήκη τα αδιέξοδα μοντελοποιούνται ως κατευθυνόμενοι γράφοι με κόμβους τις διεργασίες και τους πόρους.

Ακμή από διεργασία σε πόρο σημαίνει πως η διεργασία περιμένει να ελευθερωθεί ο πόρος αυτός.
Ακμή από πόρο σε διεργασία σημαίνει πως ο πόρος είναι δεσμευμένος από την αντίστοιχη διεργασία.

Οι παρακάτω στρατηγικές μπορούν να χρησιμοποιηθούν για την αντιμετώπισή τους:

Αγνόηση του προβλήματος
Ανίχνευση και επανόρθωση
Δυναμική αποφυγή με προσεκτική κατανομή των πόρων
Πρόληψη με αναίρεση των παραπάνω αναγκαίων συνθηκών

Ανίχνευση και επανόρθωση

Η ανίχνευση των αδιεξόδων μπορεί να γίνει με έρευνα του γράφου των αδιεξόδων για κύκλους. Αφού ανιχνευθεί το αδιέξοδο η επανόρθωση μπορεί να γίνει με τους παρακάτω τρόπους:

Προεκχώρηση του πόρου
Οπισθοδρόμηση της διεργασίας σε προηγούμενο σημείο ελέγχου (checkpoint)
Εξάλειψη κάποιων διεργασιών

Αποφυγή

Η αποφυγή του αδιεξόδου βασίζεται στη συντηρητική ικανοποίηση των αιτήσεων για πόρους με στόχο το σύστημα πάντα να βρίσκεται σε μια ασφαλή κατάσταση κατά την οποία δεν μπορεί να υπάρξει αδιέξοδο. Αιτήσεις που οδηγούν σε μη ασφαλείς καταστάσεις δεν ικανοποιούνται.

Πρόληψη

Η αναίρεση μιας τουλάχιστον από τις συνθήκες του αδιεξόδου εξασφαλίζει ότι δε θα υπάρχουν αδιέξοδα.

Αμοιβαίος αποκλεισμός: (Κάθε πόρος είναι δεσμευμένος ή διαθέσιμος.)
Αποφεύγεται η χρήση δεσμευμένων πόρων π.χ. με τη χρήση ετεροχρονισμού.
Δέσμευση και αναμονή: (Διεργασίες που δεσμεύουν πόρους μπορούν να ζητούν και νέους.)
Κάθε διεργασία ζητά από την αρχή τους πόρους που χρειάζεται.
Μη προεκχώρηση: (Μόνο η διεργασία που έχει δεσμεύσει τους πόρους μπορεί να τους αποδεσμεύσει.)
Δύσκολο πρακτικά να αναιρεθεί.
Κυκλική αναμονή: (Οι διαδικασίες που ζητούν πόρους πρέπει να σχηματίζουν κύκλο.)
Αίτηση για πόρους σύμφωνα με την απαρίθμησή τους.

Βάσεις δεδομένων

Σε βάσεις δεδομένων χρησιμοποιείται συχνά το κλείδωμα σε δύο φάσεις (two phase locking).

Οι εγγραφές που χρειάζεται η βάση για να εκτελέσει κάποια συναλλαγή σε πρώτη φάση κλειδώνονται.
Αν κλειδωθούν όλες με επιτυχία τότε ενημερώνονται.
Αν όχι, τότε ξεκλειδώνονται όλες και η διεργασία προσπαθεί να εκτελέσει την ίδια διαδικασία αργότερα.

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 331-359 Εκδόσεις Παπασωτηρίου, 1993.

Περιεχόμενα