Διαδικασία SyncΧρονισμός: Πρόβλημα κρίσιμου τμήματος στο ΛΣ

Τι είναι Διαδικασία Syncχρονισμός;

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

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

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

Πώς Διαδικασία SyncΧρονισμός Έργα;

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

Διαδικασία SyncΧρονισμός Έργα

Ενότητες ενός Προγράμματος

Ακολουθούν τέσσερα βασικά στοιχεία της κρίσιμης ενότητας:

  • Ενότητα εισόδου: Είναι μέρος της διαδικασίας που αποφασίζει την είσοδο μιας συγκεκριμένης διαδικασίας.
  • Κρίσιμο τμήμα: Αυτό το τμήμα επιτρέπει σε μία διεργασία να εισάγει και να τροποποιεί την κοινόχρηστη μεταβλητή.
  • Ενότητα εξόδου: Η ενότητα Εξόδου επιτρέπει στις άλλες διεργασίες που βρίσκονται σε αναμονή στην Ενότητα Εισόδου να εισέλθουν στις Κρίσιμες Ενότητες. Ελέγχει επίσης ότι μια διεργασία που ολοκλήρωσε την εκτέλεσή της πρέπει να αφαιρεθεί μέσω αυτής της Ενότητας.
  • Υπόλοιπο τμήμα: Όλα τα άλλα μέρη του Κώδικα, τα οποία δεν βρίσκονται στην Ενότητα Κρίσιμη, Εισόδου και Εξόδου, είναι γνωστά ως Υπόλοιπο Ενότητα.

Τι είναι το πρόβλημα της κρίσιμης τομής;

Ένα κρίσιμο τμήμα είναι ένα τμήμα κώδικα στο οποίο μπορεί να προσπελαστεί με μια διεργασία σήματος σε ένα συγκεκριμένο χρονικό σημείο. Η ενότητα αποτελείται από κοινόχρηστους πόρους δεδομένων στους οποίους απαιτείται πρόσβαση από άλλες διαδικασίες.

  • Η καταχώρηση στο κρίσιμο τμήμα αντιμετωπίζεται από τη συνάρτηση wait() και αναπαρίσταται ως P().
  • Η έξοδος από ένα κρίσιμο τμήμα ελέγχεται από τη συνάρτηση signal(), που αναπαρίσταται ως V().

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

Κανόνες για το κρίσιμο τμήμα

Το κρίσιμο τμήμα πρέπει να επιβάλλει και τους τρεις κανόνες:

  • Αμοιβαίος αποκλεισμός: Ο αμοιβαίος αποκλεισμός είναι ένας ειδικός τύπος δυαδικού σηματοφόρου που χρησιμοποιείται για τον έλεγχο της πρόσβασης στον κοινόχρηστο πόρο. Περιλαμβάνει έναν μηχανισμό κληρονομικότητας προτεραιότητας για την αποφυγή προβλημάτων αντιστροφής εκτεταμένης προτεραιότητας. Δεν μπορούν να εκτελεστούν περισσότερες από μία διεργασίες στο κρίσιμο τμήμα της ταυτόχρονα.
  • Πρόοδος: Αυτή η λύση χρησιμοποιείται όταν κανείς δεν βρίσκεται στην κρίσιμη ενότητα και κάποιος θέλει να μπει. Στη συνέχεια, αυτές οι διεργασίες που δεν βρίσκονται στην ενότητα υπενθύμισής τους θα πρέπει να αποφασίσουν ποιος πρέπει να μπει, σε πεπερασμένο χρόνο.
  • Δεσμευμένη αναμονή: Όταν μια διεργασία υποβάλλει αίτημα για είσοδο σε κρίσιμη ενότητα, υπάρχει ένα συγκεκριμένο όριο σχετικά με τον αριθμό των διεργασιών που μπορούν να εισέλθουν στην κρίσιμη ενότητα τους. Έτσι, όταν επιτευχθεί το όριο, το σύστημα πρέπει να επιτρέψει στο αίτημα στη διαδικασία να εισέλθει στο κρίσιμο τμήμα της.

Λύσεις στο κρίσιμο τμήμα

Σε εξέλιξη SyncΧρονισμός, το κρίσιμο τμήμα παίζει τον κύριο ρόλο έτσι ώστε το πρόβλημα πρέπει να λυθεί.

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

Λύση Peterson

Η λύση του Peterson είναι ευρέως χρησιμοποιούμενη λύση σε προβλήματα κρίσιμων τομέων. Αυτός ο αλγόριθμος αναπτύχθηκε από έναν επιστήμονα υπολογιστών Peterson και γι' αυτό ονομάστηκε ως λύση Peterson.

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

Παράδειγμα

Λύσεις στο κρίσιμο τμήμα

PROCESS Pi
FLAG[i] = true
while( (turn != i) AND (CS is !free) ){ wait;
}
CRITICAL SECTION FLAG[i] = false
turn = j; //choose another process to go to CS
  • Ας υποθέσουμε ότι υπάρχουν N διεργασίες (P1, P2, … PN) και κάθε διεργασία κάποια στιγμή απαιτεί να εισέλθει στην Κρίσιμη Ενότητα
  • Διατηρείται ένας πίνακας FLAG[] μεγέθους N που είναι εξ ορισμού false. Έτσι, κάθε φορά που μια διεργασία απαιτεί να εισέλθει στην κρίσιμη ενότητα, πρέπει να ορίσει τη σημαία της ως αληθινή. Για παράδειγμα, εάν ο Pi θέλει να εισέλθει, θα ορίσει FLAG[i]=TRUE.
  • Μια άλλη μεταβλητή που ονομάζεται TURN υποδεικνύει τον αριθμό διεργασίας που θέλει να εισαχθεί στο CS.
  • Η διαδικασία που εισέρχεται στο κρίσιμο τμήμα κατά την έξοδο θα άλλαζε το TURN σε έναν άλλο αριθμό από τη λίστα των έτοιμων διεργασιών.
  • Παράδειγμα: η στροφή είναι 2, τότε η Ρ2 μπαίνει στο Κρίσιμο τμήμα και κατά την έξοδο από τη στροφή=3 και επομένως η Ρ3 βγαίνει από τον βρόχο αναμονής.

SyncΧρονισμός Υλικό

Μερικές φορές τα προβλήματα του Κρίσιμου Τμήματος επιλύονται και από υλικό. Μερικοί operaΤο σύστημα ting προσφέρει μια λειτουργία κλειδώματος όπου μια Διεργασία αποκτά ένα κλείδωμα όταν εισέρχεται στην Κρίσιμη ενότητα και απελευθερώνει την κλειδαριά αφού την εγκαταλείψει.

Έτσι, όταν μια άλλη διεργασία προσπαθεί να εισέλθει στο κρίσιμο τμήμα, δεν θα μπορεί να εισέλθει καθώς είναι κλειδωμένη. Μπορεί να το κάνει μόνο εάν είναι δωρεάν αποκτώντας την ίδια την κλειδαριά.

Κλειδαριές Mutex

SyncΤο υλικό hronization δεν είναι απλή μέθοδος εφαρμογής για όλους, επομένως εισήχθη και αυστηρή μέθοδος λογισμικού γνωστή ως Mutex Locks.

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

Λύση σηματοφόρου

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

Χρησιμοποιεί δύο atomic opera1) αναμονή και 2) σήμα για τη διαδικασία syncχρονισμός.

Παράδειγμα

WAIT ( S ):
while ( S <= 0 );
S = S - 1;
SIGNAL ( S ):
S = S + 1;

Χαρακτηριστικά

  • Διαδικασία syncΧρονισμός είναι το καθήκον του συντονισμού της εκτέλεσης των διαδικασιών με τρόπο που καμία διεργασία δεν μπορεί να έχει πρόσβαση στα ίδια κοινά δεδομένα και πόρους.
  • Τέσσερα στοιχεία της κρίσιμης ενότητας είναι 1) Ενότητα εισόδου 2) Κρίσιμη ενότητα 3) Ενότητα εξόδου 4) Ενότητα υπενθύμισης
  • Ένα κρίσιμο τμήμα είναι ένα τμήμα κώδικα στο οποίο μπορεί να προσπελαστεί με μια διεργασία σήματος σε ένα συγκεκριμένο χρονικό σημείο.
  • Τρεις υποχρεωτικοί κανόνες που πρέπει να επιβάλλονται από την κρίσιμη ενότητα είναι: 1) Αμοιβαία αποκλεισμός 2) Λύση διαδικασίας 3) Δεσμευμένη αναμονή
  • Ο αμοιβαίος αποκλεισμός είναι ένας ειδικός τύπος δυαδικού σηματοφόρου που χρησιμοποιείται για τον έλεγχο της πρόσβασης στον κοινόχρηστο πόρο.
  • Η λύση διαδικασίας χρησιμοποιείται όταν κανείς δεν βρίσκεται στο κρίσιμο τμήμα και κάποιος θέλει να μπει.
  • Στη λύση δεσμευμένης αναμονής, αφού μια διεργασία κάνει ένα αίτημα για είσοδο στο κρίσιμο τμήμα της, υπάρχει ένα όριο για το πόσες άλλες διεργασίες μπορούν να εισέλθουν στο κρίσιμο τμήμα τους.
  • Η λύση του Peterson είναι ευρέως χρησιμοποιούμενη λύση σε προβλήματα κρίσιμων τομέων.
  • Προβλήματα του Κρίσιμου Τμήματος επιλύονται επίσης από syncχρονισμός του υλικού
  • SyncΤο υλικό hronization δεν είναι μια απλή μέθοδος για εφαρμογή για όλους, επομένως εισήχθη και η αυστηρή μέθοδος λογισμικού γνωστή ως Mutex Locks.
  • Το Semaphore είναι ένας άλλος αλγόριθμος ή λύση στο πρόβλημα της κρίσιμης ενότητας.