Livelock: Τι είναι, Παράδειγμα, Διαφορά με το Αδιέξοδο

Παραδείγματα Livelock

Παράδειγμα 1:

Ένα πιο εύκολο παράδειγμα του Livelock θα ήταν δύο άτομα που συναντιούνται πρόσωπο με πρόσωπο σε έναν διάδρομο και οι δύο απομακρύνονται για να αφήσουν τον άλλο να περάσει. Καταλήγουν να κινούνται από πλευρά σε πλευρά χωρίς να σημειώνουν καμία πρόοδο καθώς κινούνται με τον ίδιο τρόπο εκείνη τη στιγμή. Εδώ, δεν διασταυρώνονται ποτέ μεταξύ τους.

Παράδειγμα 2:

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

1. Διαδικασία Ένας πόρος αναμονής Υ
2. Η διαδικασία Β περιέχει τον πόρο Χ
3. Η διαδικασία Α απαιτεί πόρο Χ
4. Η διαδικασία Β απαιτεί πόρο Υ

Υποθέτοντας ότι η διεργασία Α εκτελείται πρώτα και αποκτά τον πόρο δεδομένων Χ και στη συνέχεια η διεργασία Β εκτελείται και αποκτά τον πόρο Υ, ανεξάρτητα από το ποια διεργασία εκτελείται πρώτη, καμία από αυτές δεν προχωρά περαιτέρω.

Ωστόσο, καμία από τις δύο διαδικασίες δεν είναι αποκλεισμένη. Καταναλώνουν τους πόρους της CPU επανειλημμένα χωρίς να σημειωθεί καμία πρόοδος, αλλά επίσης σταματούν οποιοδήποτε μπλοκ επεξεργασίας.

Επομένως, αυτή η κατάσταση δεν είναι αυτή του α αδιέξοδο γιατί δεν υπάρχει ούτε μία διαδικασία που να είναι μπλοκαρισμένη, αλλά αντιμετωπίζουμε την κατάσταση κάτι που ισοδυναμεί με αδιέξοδο, που είναι το LIVELOCK.

Τι οδηγεί στο Livelock;

Το Livelock εμφανίζεται όταν ο συνολικός αριθμός των επιτρεπόμενων διεργασιών σε ένα συγκεκριμένο σύστημα πρέπει να οριστεί από τον συνολικό αριθμό των καταχωρήσεων στον πίνακα διεργασιών. Επομένως, οι υποδοχές πίνακα διεργασιών θα πρέπει να αναφέρονται ως πεπερασμένοι πόροι.

Τι είναι το Deadlock;

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

Παράδειγμα Αδιεξόδου

• Ένα πραγματικό παράδειγμα θα ήταν η κυκλοφορία, η οποία πηγαίνει μόνο προς μία κατεύθυνση.
• Εδώ, μια γέφυρα θεωρείται πόρος.
• Έτσι, όταν συμβαίνει το αδιέξοδο, μπορεί εύκολα να επιλυθεί εάν ένα αυτοκίνητο κάνει αντίγραφα ασφαλείας (Preempt πόρους και rollback).
• Σε περίπτωση αδιεξόδου ενδέχεται να χρειαστεί να λάβετε αντίγραφα ασφαλείας για πολλά αυτοκίνητα.
• Άρα η πείνα είναι δυνατή.

Τι είναι η πείνα;

Η λιμοκτονία είναι μια κατάσταση όπου όλες οι διαδικασίες χαμηλής προτεραιότητας μπλοκάρονται και οι διαδικασίες υψηλής προτεραιότητας προχωρούν. Σε οποιοδήποτε σύστημα, τα αιτήματα για πόρους υψηλής/χαμηλής προτεραιότητας συνεχίζουν να συμβαίνουν δυναμικά. Ως εκ τούτου, απαιτείται κάποια πολιτική για να αποφασιστεί ποιος πότε θα λάβει υποστήριξη.

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

Παράδειγμα πείνας

Για παράδειγμα, ένα αντικείμενο προσφέρει μια συγχρονισμένη μέθοδο που πιθανότατα θα χρειαστεί πολύς χρόνος για να επιστρέψει. Εάν ένα νήμα χρησιμοποιεί αυτή τη μέθοδο συχνά, άλλα νήματα που χρειάζονται επίσης συχνή συγχρονισμένη πρόσβαση στο ίδιο αντικείμενο συχνά θα αποκλειστούν.

Διαφορά μεταξύ Deadlock, Starvation και Livelock

• Ένα αδιέξοδο είναι μια κατάσταση που εμφανίζεται στο λειτουργικό σύστημα όταν οποιαδήποτε διεργασία εισέρχεται σε κατάσταση αναμονής επειδή ο απαιτούμενος πόρος συγκρατείται από μια άλλη διαδικασία αναμονής.
• Ένα livelock, από την άλλη πλευρά, είναι σχεδόν παρόμοιο με ένα αδιέξοδο, με τη διαφορά ότι οι καταστάσεις των διαδικασιών που εμπλέκονται σε ένα livelock συνεχίζουν πάντα να αλλάζουν μεταξύ τους, χωρίς καμία πρόοδο.
• Έτσι, το Livelock είναι μια μοναδική περίπτωση λιμοκτονίας των πόρων.

Περίληψη

• Ορισμός: Ένα Livelock είναι μια κατάσταση όπου ένα αίτημα για αποκλειστικό κλείδωμα απορρίπτεται επανειλημμένα, καθώς πολλά αλληλεπικαλύπτονται.ping Οι κοινόχρηστες κλειδαριές συνεχίζουν να αλληλοεπηρεάζονται.
• Το Livelock συμβαίνει όταν ο συνολικός αριθμός των επιτρεπόμενων διεργασιών σε ένα συγκεκριμένο σύστημα πρέπει να οριστεί από τον συνολικό αριθμό των εγγραφών στον πίνακα διεργασιών
• Ένα αδιέξοδο είναι μια κατάσταση που εμφανίζεται στο λειτουργικό σύστημα όταν οποιαδήποτε διεργασία εισέρχεται σε κατάσταση αναμονής επειδή μια άλλη διαδικασία αναμονής κρατά τον απαιτούμενο πόρο.
• Ένα πραγματικό παράδειγμα θα ήταν η κυκλοφορία, η οποία πηγαίνει μόνο προς μία κατεύθυνση.
• Ένα παράδειγμα Livelock θα ήταν δύο άτομα που συναντιούνται πρόσωπο με πρόσωπο σε έναν διάδρομο και οι δύο απομακρύνονται για να αφήσουν τον άλλο να περάσει.
• Η λιμοκτονία είναι μια κατάσταση όπου όλες οι διαδικασίες χαμηλής προτεραιότητας μπλοκάρονται και οι διαδικασίες υψηλής προτεραιότητας προχωρούν.