Λιμοκτονία πόρων
Λιμοκτονία πόρων είναι πρόβλημα που εμφανίζεται στον ταυτόχρονο υπολογισμό, όταν μια διεργασία στερείται διαρκώς τους απαραίτητους πόρους για την εκτέλεση της εργασίας της.[1] Η λιμοκτονία μπορεί να προκληθεί από σφάλματα σε αλγόριθμο χρονοδρομολόγησης ή αμοιβαίου αποκλεισμού, αλλά μπορεί επίσης να προκληθεί από διαρροή πόρων ή να προκληθεί σκόπιμα μέσω επίθεσης άρνησης υπηρεσίας, όπως μια fork bomb.
Όταν η λιμοκτονία είναι αδύνατη σε έναν ταυτόχρονο αλγόριθμο, ο αλγόριθμος ονομάζεται ελεύθερος από λιμοκτονία, ελεύθερος από αποκλεισμό[2] ή λέγεται ότι έχει πεπερασμένη παράκαμψη.[3] Η ιδιότητα αυτή αποτελεί περίπτωση ζωτικότητας και είναι μία από τις δύο απαιτήσεις για κάθε αλγόριθμο αμοιβαίου αποκλεισμού· η άλλη είναι η ορθότητα. Η ονομασία «πεπερασμένη παράκαμψη» σημαίνει ότι κάθε διεργασία, δηλαδή κάθε ταυτόχρονο τμήμα του αλγορίθμου, παρακάμπτεται το πολύ πεπερασμένο αριθμό φορών πριν της επιτραπεί η πρόσβαση στον κοινό πόρο.[3]
Χρονοδρομολόγηση
[Επεξεργασία | επεξεργασία κώδικα]Η λιμοκτονία προκαλείται συνήθως από υπερβολικά απλοϊκό αλγόριθμο χρονοδρομολόγησης. Για παράδειγμα, αν ένα κακώς σχεδιασμένο πολυδιεργασιακό σύστημα εναλλάσσεται πάντοτε μεταξύ των δύο πρώτων εργασιών, ενώ μια τρίτη δεν εκτελείται ποτέ, τότε η τρίτη εργασία στερείται χρόνου CPU. Ο αλγόριθμος χρονοδρομολόγησης, ο οποίος αποτελεί μέρος του πυρήνα, υποτίθεται ότι κατανέμει τους πόρους δίκαια. Δηλαδή, ο αλγόριθμος πρέπει να κατανέμει τους πόρους έτσι ώστε καμία διεργασία να μη στερείται διαρκώς απαραίτητους πόρους.
Πολλοί χρονοδρομολογητές λειτουργικών συστημάτων χρησιμοποιούν την έννοια της προτεραιότητας διεργασιών. Μια διεργασία υψηλής προτεραιότητας Α θα εκτελεστεί πριν από μια διεργασία χαμηλής προτεραιότητας Β. Αν η διεργασία υψηλής προτεραιότητας, δηλαδή η διεργασία Α, μπλοκάρει και δεν παραχωρεί ποτέ τον επεξεργαστή, η διεργασία χαμηλής προτεραιότητας Β μπορεί, σε ορισμένα συστήματα, να μη χρονοδρομολογηθεί ποτέ· τότε θα υποστεί λιμοκτονία. Αν υπάρχει μια ακόμη υψηλότερης προτεραιότητας διεργασία Χ, η οποία εξαρτάται από αποτέλεσμα της διεργασίας Β, τότε η διεργασία Χ μπορεί να μην ολοκληρωθεί ποτέ, παρότι είναι η σημαντικότερη διεργασία στο σύστημα. Η κατάσταση αυτή ονομάζεται αντιστροφή προτεραιότητας. Οι σύγχρονοι αλγόριθμοι χρονοδρομολόγησης περιέχουν συνήθως κώδικα που εγγυάται ότι όλες οι διεργασίες θα λαμβάνουν μια ελάχιστη ποσότητα από κάθε σημαντικό πόρο, συχνότερα χρόνο CPU, ώστε να αποτρέπεται η λιμοκτονία οποιασδήποτε διεργασίας.
Στα δίκτυα υπολογιστών, ιδίως στα ασύρματα δίκτυα, οι αλγόριθμοι χρονοδρομολόγησης μπορεί να υποστούν λιμοκτονία χρονοδρομολόγησης. Παράδειγμα αποτελεί η χρονοδρομολόγηση μέγιστης διεκπεραιωτικότητας.
Η λιμοκτονία συχνά προκαλείται από αδιέξοδο, καθώς αυτό οδηγεί μια διεργασία σε πάγωμα. Δύο ή περισσότερες διεργασίες βρίσκονται σε αδιέξοδο όταν καθεμία δεν κάνει τίποτα, περιμένοντας έναν πόρο που κατέχεται από άλλο πρόγραμμα στο ίδιο σύνολο. Από την άλλη πλευρά, μια διεργασία βρίσκεται σε κατάσταση λιμοκτονίας όταν περιμένει έναν πόρο που δίνεται συνεχώς σε άλλες διεργασίες. Η ελευθερία από λιμοκτονία αποτελεί ισχυρότερη εγγύηση από την απουσία αδιεξόδου: ένας αλγόριθμος αμοιβαίου αποκλεισμού που πρέπει να επιλέξει να επιτρέψει σε μία από δύο διεργασίες να εισέλθει σε ένα κρίσιμο τμήμα και επιλέγει αυθαίρετα μία από αυτές είναι ελεύθερος από αδιέξοδο, αλλά όχι κατ' ανάγκη ελεύθερος από λιμοκτονία.[3]
Μια πιθανή λύση στη λιμοκτονία είναι η χρήση αλγορίθμου χρονοδρομολόγησης με ουρά προτεραιότητας, ο οποίος χρησιμοποιεί επίσης την τεχνική της γήρανσης. Η γήρανση είναι τεχνική σταδιακής αύξησης της προτεραιότητας διεργασιών που περιμένουν στο σύστημα για μεγάλο χρονικό διάστημα.[4]
Δείτε επίσης
[Επεξεργασία | επεξεργασία κώδικα]Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ Tanenbaum, Andrew (2001). Modern Operating Systems
. Prentice Hall. σελίδες 184–185. ISBN 0-13-092641-8. - ↑ Herlihy, Maurice· Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. σελ. 24. ISBN 9780123977953.
- 1 2 3 Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. σελίδες 10–11. ISBN 978-3642320279.
- ↑ Galvin, Peter (2010). Operating System Concepts. Wiley India Edition. σελ. 193. ISBN 978-81-265-2051-0.
