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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Κλειδαριές Mutex

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

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

Semaphore Λύση

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

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

Παράδειγμα

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

Συχνές Ερωτήσεις