Computer Operating System - Lecture 7: Process Synchronization - Nguyen Thanh Son

Nội dung text: Computer Operating System - Lecture 7: Process Synchronization - Nguyen Thanh Son

1. Chapter’s Content  Background  The Critical-Section Problem  Synchronization Hardware  Semaphores  Classical Problems of Synchronization  Critical Regions  Monitors BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 2
2. Bounded-Buffer  Shared data #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0; BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 4
3. Bounded-Buffer  Consumer process item nextConsumed; while (1) { while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter ; } BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 6
4. Bounded Buffer  The statement “count++” may be implemented in machine language as: register1 = counter register1 = register1 + 1 counter = register1  The statement “count—” may be implemented as: register2 = counter register2 = register2 – 1 counter = register2 BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 8
5. Bounded Buffer  Assume counter is initially 5. One interleaving of statements is: producer: register1 = counter (register1 = 5) producer: register1 = register1 + 1 (register1 = 6) consumer: register2 = counter (register2 = 5) consumer: register2 = register2 – 1 (register2 = 4) producer: counter = register1 (counter = 6) consumer: counter = register2 (counter = 4)  The value of count may be either 4 or 6, where the correct result should be 5. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 10
6. The Critical-Section Problem  n processes all competing to use some shared data  Each process has a code segment, called critical section, in which the shared data is accessed.  Problem – ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 12
7. Initial Attempts to Solve Problem  Only 2 processes, P0 and P1  General structure of process Pi (other process Pj) do { entry section (Primitive) critical section exit section reminder section } while (1);  Processes may share some common variables to synchronize their actions. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 14
8. Algorithm 2  Shared variables  boolean flag[2]; initially flag [0] = flag [1] = false.  flag [i] = true Pi ready to enter its critical section  Process Pi do { flag[i] := true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1);  Satisfies mutual exclusion, and progress but not bounded waiting requirement. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 16
9. Bakery Algorithm Critical section for n processes  Before entering its critical section, process receives a number. Holder of the smallest number enters the critical section.  If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first.  The numbering scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5 BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 18
10. Bakery Algorithm do { choosing[i] = true; number[i] = max(number[0], number[1], , number [n – 1])+1; choosing[i] = false; for (j = 0; j < n; j++) { while (choosing[j]) ; while ((number[j] != 0) && (number[j,j] < number[i,i])) ; } critical section number[i] = 0; remainder section } while (1); BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 20
11. Mutual Exclusion with Test-and-Set  Shared data: boolean lock = false;  Process Pi do { while (TestAndSet(lock)) ; critical section lock = false; remainder section } BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 22
12. Mutual Exclusion with Swap  Shared data (initialized to false): boolean lock; boolean waiting[n];  Process Pi do { key = true; while (key == true) Swap(lock,key); critical section lock = false; remainder section } BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 24
13. Critical Section of n Processes  Shared data: semaphore mutex; //initially mutex = 1  Process Pi: do { wait(mutex); critical section signal(mutex); remainder section } while (1); BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 26
14. Implementation  Semaphore operations now defined as wait(S): S.value ; if (S.value < 0) { add this process to S.L; block; } signal(S): S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 28
15. Deadlock and Starvation  Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.  Let S and Q be two semaphores initialized to 1 P0 P1 wait(S); wait(Q); wait(Q); wait(S);   signal(S); signal(Q); signal(Q) signal(S);  Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 30
16. Implementing S as a Binary Semaphore  Data structures: binary-semaphore S1, S2; int C:  Initialization: S1 = 1 S2 = 0 C = initial value of semaphore S BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 32
17. Classical Problems of Synchronization  Bounded-Buffer Problem  Readers and Writers Problem  Dining-Philosophers Problem BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 34
18. Bounded-Buffer Problem Producer Process do { produce an item in nextp wait(empty); wait(mutex); add nextp to buffer signal(mutex); signal(full); } while (1); BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 36
19. Readers-Writers Problem  Shared data semaphore mutex, wrt; Initially mutex = 1, wrt = 1, readcount = 0 BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 38
20. Readers-Writers Problem Reader Process wait(mutex); readcount++; if (readcount == 1) wait(rt); signal(mutex); reading is performed wait(mutex); readcount ; if (readcount == 0) signal(wrt); BK signal(mutex): TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 40
21. Dining-Philosophers Problem  Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) eat signal(chopstick[i]); signal(chopstick[(i+1) % 5]); think BK } while (1); TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 42
22. Critical Regions  Regions referring to the same shared variable exclude each other in time.  When a process tries to execute the region statement, the Boolean expression B is evaluated. If B is true, statement S is executed. If it is false, the process is delayed until B becomes true and no other process is in the region associated with v. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 44
23. Bounded Buffer Producer Process  Producer process inserts nextp into the shared buffer region buffer when( count < n) { pool[in] = nextp; in:= (in+1) % n; count++; } BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 46
24. Implementation region x when B do S  Associate with the shared variable x, the following variables: semaphore mutex, first-delay, second-delay; int first-count, second-count;  Mutually exclusive access to the critical section is provided by mutex.  If a process cannot enter the critical section because the Boolean expression B is false, it initially waits on the first-delay semaphore; moved to the second-delay semaphore before it is allowed to reevaluate B. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 48
25. Monitors  High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes. monitor monitor-name { shared variable declarations procedure body P1 ( ) { . . . } procedure body P2 ( ) { . . . } procedure body Pn ( ) { . . . } { initialization code } } BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 50
26. Schematic View of a Monitor BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 52
27. Dining Philosophers Example monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; void pickup(int i) // following slides void putdown(int i) // following slides void test(int i) // following slides void init() { for (int i = 0; i < 5; i++) state[i] = thinking; } } BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 54
28. Dining Philosophers void test(int i) { if ( (state[(I + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating)) { state[i] = eating; self[i].signal(); } BK } TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 56
29. Monitor Implementation  For each condition variable x, we have: semaphore x-sem; // (initially = 0) int x-count = 0;  The operation x.wait can be implemented as: x-count++; if (next-count > 0) signal(next); else signal(mutex); wait(x-sem); x-count ; BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 58
30. Monitor Implementation  Conditional-wait construct: x.wait(c);  c – integer expression evaluated when the wait operation is executed.  value of c (a priority number) stored with the name of the process that is suspended.  when x.signal is executed, process with smallest associated priority number is resumed next.  Check two conditions to establish correctness of system:  User processes must always make their calls on the monitor in a correct sequence.  Must ensure that an uncooperative process does not ignore the mutual-exclusion gateway provided by the monitor, and try to access the shared resource directly, without using the access protocols. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 60
31. Windows 2000 Synchronization  Uses interrupt masks to protect access to global resources on uniprocessor systems.  Uses spinlocks on multiprocessor systems.  Also provides dispatcher objects which may act as wither mutexes and semaphores.  Dispatcher objects may also provide events. An event acts much like a condition variable. BK TP.HCM 01-Sep-16 Faculty of Computer Science & Engineering 62