Συγχρονισμός διαδικασίας: Πρόβλημα κρίσιμης ενότητας στο λειτουργικό σύστημα

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

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

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

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

Σε αυτό το σεμινάριο λειτουργικού συστήματος, θα μάθετε:

Πώς λειτουργεί ο συγχρονισμός διαδικασίας;

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

Τμήματα ενός Προγράμματος

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

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

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

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

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

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

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

Το κρίσιμο τμήμα πρέπει να εφαρμόζει και τους τρεις κανόνες:

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

Λύσεις στην κρίσιμη ενότητα

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

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

Λύση Πέτερσον

Η λύση του 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 [] μεγέθους Ν, ο οποίος είναι από προεπιλογή ψευδής. Έτσι, κάθε φορά που μια διαδικασία απαιτεί να εισέλθει στην κρίσιμη ενότητα, πρέπει να ορίσει τη σημαία της ως αληθινή. Για παράδειγμα, εάν το Pi θέλει να εισαχθεί θα ορίσει FLAG [i] = TRUE.
  • Μια άλλη μεταβλητή που ονομάζεται TURN υποδεικνύει τον αριθμό διεργασίας που αυτή τη στιγμή θέλει να εισαχθεί στο CS.
  • Η διαδικασία που εισέρχεται στο κρίσιμο τμήμα κατά την έξοδο θα αλλάξει το TURN σε άλλο αριθμό από τη λίστα των έτοιμων διεργασιών.
  • Παράδειγμα: η στροφή είναι 2, τότε το P2 εισέρχεται στο κρίσιμο τμήμα και ενώ βγαίνει από τη στροφή = 3 και επομένως το P3 ξεφεύγει από τον βρόχο αναμονής.

Υλικό συγχρονισμού

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

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

Κλειδαριές Mutex

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

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

Λύση Semaphore

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

Χρησιμοποιεί δύο ατομικές πράξεις, 1) αναμονή και 2) σήμα για το συγχρονισμό της διαδικασίας.

Παράδειγμα

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

Περίληψη:

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