Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

2024-07-04: Σημειώσεις μελέτης συγχρονισμού λειτουργικού συστήματος και αμοιβαίου αποκλεισμού

---

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

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

---

9.1 Βασικές έννοιες συγχρονισμού και αμοιβαίου αποκλεισμού

9.1.1 Σχέση συγχρονισμού

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

---

9.1.2 Αμοιβαία αποκλειστική σχέση

Η σχέση που περιορίζει έμμεσα ο ένας τον άλλον ονομάζεται αμοιβαία αποκλειστική σχέση, π.χ

---

9.1.3 Κρίσιμοι πόροι

• Οι πόροι στους οποίους επιτρέπεται να έχει πρόσβαση μόνο μία διεργασία εντός μιας χρονικής περιόδου ονομάζονται κρίσιμοι πόροι (ή αποκλειστικοί πόροι)
• Για την κοινή χρήση κρίσιμων πόρων, θα πρέπει να χρησιμοποιείται αμοιβαίος αποκλεισμός μεταξύ των διαδικασιών

«Μοντέλο Παραγωγού και Καταναλωτή»
μετρητής+ +

首先把变量放到寄存器里面
register1 = counter;
接下来对寄存器进行一个自增
register1 = register1 + 1;
再把结果返回到counter里
counter = register1;
1
2
3
4
5
6

μετρητής- -

首先把变量放到寄存器里面
register2 = counter;
接下来对寄存器进行一个自减
register2 = register2 - 1;
再把结果返回到counter里
counter = register2;
1
2
3
4
5
6

Λύση: αντιμετωπίστε τον μετρητή ως κρίσιμο πόρο και επιτρέψτε στη διαδικασία να αποκτήσει αμοιβαία πρόσβαση στον μετρητή μεταβλητών (θα μάθετε τον μηχανισμό συγχρονισμού αργότερα)

---

9.1.4 Κρίσιμο τμήμα

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

Αυτές οι περιοχές είναι ουσιαστικά κωδικοί

• Περιοχή εισόδου
• κρίσιμο τμήμα
• Περιοχή εξόδου
• εναπομείνασα περιοχή

---

9.1.5 Οι μηχανισμοί συγχρονισμού πρέπει να ακολουθούν κανόνες

• Ελεύθερη είσοδος

Όταν καμία διεργασία δεν βρίσκεται στο κρίσιμο τμήμα, υποδεικνύει ότι οι πόροι της κρίσιμης ενότητας είναι αδρανείς.

• Αν είστε απασχολημένοι, περιμένετε

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

• περιορισμένη αναμονή

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

• υποχωρήστε και περιμένετε

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

---

9.2 Μηχανισμός συγχρονισμού λογισμικού

9.2.1 Μέθοδος ενιαίας ένδειξης

• Ορίστε μια δημόσια ακέραια μεταβλητή για να υποδείξετε εάν υπάρχει μια διεργασία στο κρίσιμο τμήμα, θα περιμένει μέσω ενός ελέγχου βρόχου στην περιοχή εισαγωγής θα τροποποιηθεί στην περιοχή εξόδου.
• Η μέθοδος single-flag ορίζει μια δημόσια ακέραια μεταβλητή στροφή για να υποδείξει τον αριθμό διεργασίας που επιτρέπεται να εισέλθει στην κρίσιμη ενότητα Όταν turn=0, η διεργασία P0 επιτρέπεται να εισέλθει στην κρίσιμη ενότητα.
• Όταν turn=1, η διεργασία P1 επιτρέπεται να εισέλθει στο κρίσιμο τμήμα και κατά την έξοδο από το κρίσιμο τμήμα, το δικαίωμα χρήσης του κρίσιμου τμήματος δίνεται σε άλλη διεργασία (όταν το Pi εξέρχεται από το κρίσιμο τμήμα, έστω turn=j)

两个进程必须交替进入临界区，若一个进程不再进入临界区，则另一个进程也无法进入临界区，违背了“空闲让进”准则

---

9.2.2 Διπλή σήμανση της μεθόδου πρώτου ελέγχου

Η μέθοδος πρώτου ελέγχου με διπλή σημαία ορίζει μια σημαία Boolean array[2] για να επισημάνει την προθυμία κάθε διεργασίας να εισέλθει στο κρίσιμο τμήμα.

• Προτού το Pi εισέλθει στο κρίσιμο τμήμα, ελέγξτε πρώτα εάν το άλλο μέρος έχει εισέλθει στο κρίσιμο τμήμα, αν ναι, περιμένετε
• Διαφορετικά, ορίστε το flag[i] σε true πριν εισέλθετε στην κρίσιμη ενότητα
• Όταν το Pi βγαίνει από το κρίσιμο τμήμα, ορίστε το flag[i] σε false

• Ο βρόχος while είναι ισοδύναμος με τον μηχανισμό του φαναριού
• Ο καθορισμός της σημαίας του άλλου μέρους ισοδυναμεί με την αλλαγή του φαναριού του άλλου.
• Ωστόσο, δεδομένου ότι και οι δύο διαδικασίες ελέγχουν πρώτα τη σημαία [κοίτα πρώτα το φανάρι] και και οι δύο είναι αρχικά ψευδείς [και τα δύο πράσινα φανάρια], είναι πιθανό οι δύο διαδικασίες να περάσουν το φανάρι ταυτόχρονα και να εισέλθουν στο κρίσιμο τμήμα μαζί .

---

9.2.3 Διπλή σήμανση μέθοδος μετά την επιθεώρηση

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

---

9.2.4 Αλγόριθμος Peterson

Ο αλγόριθμος του Peterson συνδυάζειμέθοδος ενιαίας ένδειξηςκαιΔιπλή σήμανση μέθοδος μετά τον έλεγχοΗ ιδέα είναι να χρησιμοποιήσετε το flag[] για να λύσετε το πρόβλημα αμοιβαία αποκλειστικής πρόσβασης και να χρησιμοποιήσετε το turn για να λύσετε το πρόβλημα της λιμοκτονίας.

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

Αποτυχία παραίτησης από το δικαίωμα αναμονής

---

9.3 Μηχανισμός συγχρονισμού υλικού

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

9.3.1 Απενεργοποιήστε τις διακοπές

(1) Ορισμός απενεργοποίησης διακοπών

• Η απενεργοποίηση των διακοπών έχει συζητηθεί στις αρχές της σύνθεσης του υπολογιστή. Αναφέρεται στην τροποποίηση ενός bit στον καταχωρητή PSW στη CPU. Οι διακοπές χωρίς μάσκα δεν μπορούν να σταματήσουν
• Ο προγραμματισμός των διαδικασιών στο λειτουργικό σύστημα βασίζεται σε διακοπές, όπως διακοπές ρολογιού.
• Κατά την εκτέλεση μιας διαδικασίας στο κρίσιμο τμήμα, το σύστημα του υπολογιστή κλείνει διακοπές, οι οποίες δεν θα ενεργοποιούν τον προγραμματισμό και δεν θα υπάρχει καμία διαδικασία ή εναλλαγή νημάτων.

(2) Μειονεκτήματα της απενεργοποίησης των διακοπών

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

---

9.3.2 Εντολή Test-and-Set (εντολή TS)

Η εντολή TS μπορεί να θεωρηθεί ως μια διεργασία συνάρτησης (πρωταρχική) της οποίας η διαδικασία εκτέλεσης είναι αδιαίρετη.

• Η κλειδαριά έχει δύο καταστάσεις:
• • *lock=FALSE υποδηλώνει ότι ο πόρος είναι δωρεάν
• • *lock=TRUE υποδηλώνει ότι ο πόρος χρησιμοποιείται

Χρησιμοποιήστε το TS για να διαχειριστείτε κρίσιμα τμήματα και να ορίσετε ένα κλείδωμα για κάθε κρίσιμο πόρο.

• Η αρχική τιμή είναι FALSE, υποδεικνύοντας ότι οι κρίσιμοι πόροι είναι αδρανείς.
• Πριν εισέλθει η διαδικασία στο κρίσιμο τμήμα, χρησιμοποιεί πρώτα το TS για να δοκιμάσει το κλείδωμα Εάν είναι FALSE, μπορεί να εισαγάγει και να εκχωρήσει την τιμή TRUE στην κλειδαριά, κλείνοντας τον κρίσιμο πόρο.

---

9.3.3 Εντολή εναλλαγής

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

• Ορίστε ένα καθολικό κλείδωμα μεταβλητής Boolean για κάθε κρίσιμο πόρο, με αρχική τιμή FALSE.
• Χρησιμοποιήστε τις παραπάνω οδηγίες υλικού για να ολοκληρώσετε τη διαδικασία αμοιβαίας εξαίρεσης
• Ωστόσο, αυτή η μέθοδος θα κάνει επίσης τη διαδικασία πρόσβασης να δοκιμάζεται συνεχώς και σε κατάσταση "απασχολημένης αναμονής", η οποία δεν συμμορφώνεται με την αρχή "σωστή αναμονή".

---

9.4 Μηχανισμός σηματοφόρου

9.4.1 Ακέραιος σηματοφόρος

Ορίζεται ως ένας ακέραιος αριθμός S που χρησιμοποιείται για την αναπαράσταση του αριθμού των πόρων Υπάρχουν μόνο τρεις λειτουργίες για αυτόν τον ακέραιο σηματοφόρο: αρχικοποίηση (εκχώρηση αρχικής τιμής), αναμονή (μείωση), σήμα (αύξηση).

• Τόσο η αναμονή όσο και το σήμα είναι ατομικές λειτουργίες και δεν μπορούν να διακοπούν κατά την εκτέλεση.
• Όταν μια διεργασία τροποποιεί έναν σηματοφόρο, καμία άλλη διεργασία δεν μπορεί να τροποποιήσει τον σηματοφόρο ταυτόχρονα.

---

9.4.2 Εγγραφή σηματοφόρου

Μηχανισμός συγχρονισμού διεργασιών χωρίς φαινόμενο «απασχολημένης αναμονής».

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

• Η λειτουργία αναμονής είναι ισοδύναμη με τη λειτουργία P
• Η λειτουργία του σήματος είναι ισοδύναμη με τη λειτουργία V
• Μόνο δύο διαφορετικά ονόματα, οι λειτουργίες είναι ακριβώς ίδιες
• αναμονή (Α) = Ρ(Α)
• σήμα(B) = V(A)

---

(1) Χρησιμοποιήστε σηματοφόρο για να πραγματοποιήσετε τον αμοιβαίο αποκλεισμό της διαδικασίας

Ορίστε έναν αμοιβαία αποκλειστικό σηματοφόρο mutex=1 και, στη συνέχεια, τοποθετήστε το κρίσιμο τμήμα για κάθε διεργασία για πρόσβαση σε κρίσιμους πόρους μεταξύ αναμονής (mutex) και σήματος (mutex)

---

(2) Χρησιμοποιήστε σηματοφόρους για να επιτύχετε συγχρονισμό διεργασιών

Ορίστε έναν σηματοφόρο συγχρονισμού S=0, έτσι ώστε πρώτα να εκτελεστεί το σήμα της δήλωσης (S) και μετά η αναμονή (S)