同步:信号量，读取器/写入器

1 . Complete Monitor Example (with cond. variable) CS162 Operating Systems and •  Here is an (infinite) synchronized queue Systems Programming Lock lock; Condition dataready; Lecture 9 Queue queue; AddToQueue(item) { Synchronization, lock.Acquire(); // Get Lock Readers/Writers example, queue.enqueue(item); dataready.signal(); // // Add item Signal any waiters Scheduling lock.Release(); // Release Lock } September 25th, 2017 RemoveFromQueue() { lock.Acquire(); // Get Lock Prof. Ion Stoica while (queue.isEmpty()) { http://cs162.eecs.Berkeley.edu dataready.wait(&lock); // If nothing, sleep } item = queue.dequeue(); // Get next item lock.Release(); // Release Lock return(item); } 9/25/17 CS162 © UCB Fall 2017 Lec 9.2 Mesa vs. Hoare monitors Hoare monitors •  Need to be careful about precise definition of signal and wait. •  Signaler gives up lock, CPU to waiter; waiter runs Consider a piece of our dequeue code: immediately while (queue.isEmpty()) { •  Waiter gives up lock, processor back to signaler when it exits dataready.wait(&lock); // If nothing, sleep critical section or if it waits again } •  Most textbooks item = queue.dequeue(); // Get next item –  Why didn’t we do this? … lock.Acquire() lock.Acquire() … if (queue.isEmpty()) { … if (queue.isEmpty()) { Lock, CPU dataready.wait(&lock); // If nothing, sleep dataready.signal(); dataready.wait(&lock); } Loc … k, } CPU item = queue.dequeue(); // Get next item lock.Release(); … lock.Release(); •  Answer: depends on the type of scheduling –  Hoare-style –  Mesa-style 9/25/17 CS162 © UCB Fall 2017 Lec 9.3 9/25/17 CS162 © UCB Fall 2017 Lec 9.4 Page 1 

2 . Mesa monitors Mesa Monitor: Why “while()”? •  Signaler keeps lock and processor •  Why do we use “while()” instead of “if() with Mesa monitors? •  Waiter placed on ready queue with no special priority –  Example illustrating what happens if we use “if()”, e.g., •  Practically, need to check condition again after wait if (queue.isEmpty()) { •  Most real operating systems dataready.wait(&lock); // If nothing, sleep } … Put waiting lock.Acquire() •  We’ll use the synchronized (infinite) queue example lock.Acquire() thread on … … ready queue while (queue.isEmpty()) { AddToQueue(item) { RemoveFromQueue() { dataready.signal(); dataready.wait(&lock); lock.Acquire(); ad lock.Acquire(); … thre } if (queue.isEmpty()) { w a iting queue.enqueue(item); lock.Release(); dule … dataready.wait(&lock); dataready.signal(); sche lock.Release(); } lock.Release(); item = queue.dequeue(); } lock.Release(); Replace “while” with return(item); “if” } 9/25/17 CS162 © UCB Fall 2017 Lec 9.5 9/25/17 CS162 © UCB Fall 2017 Lec 9.6 Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue lock: FREE Running: T1 queue lock: BUSY (T1) Running: T1 Ready Ready dataready dataready NULL queue à NULL NULL queue à NULL queue queue … … T1 (Running) T1 (Running) RemoveFromQueue() { RemoveFromQueue() { lock.Acquire(); lock.Acquire(); if (queue.isEmpty()) { if (queue.isEmpty()) { dataready.wait(&lock); dataready.wait(&lock); } } item = queue.dequeue(); item = queue.dequeue(); lock.Release(); lock.Release(); return(item); return(item); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.7 9/25/17 CS162 © UCB Fall 2017 Lec 9.8 Page 2 

3 . Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue lock: FREE Running: queue lock: FREE Running: T2 Ready Ready dataready dataready T1 queue à NULL T1 queue à NULL queue queue … … wait(&lock) puts thread on T1 (Waiting) dataready queue and T1 (Waiting) T2 (Running) releases lock RemoveFromQueue() { RemoveFromQueue() { AddToQueue(item) { lock.Acquire(); lock.Acquire(); lock.Acquire(); if (queue.isEmpty()) { if (queue.isEmpty()) { queue.enqueue(item); dataready.wait(&lock); dataready.wait(&lock); dataready.signal(); } } lock.Release(); item = queue.dequeue(); item = queue.dequeue(); } lock.Release(); lock.Release(); return(item); return(item); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.9 9/25/17 CS162 © UCB Fall 2017 Lec 9.10 Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue add lock: BUSY (T2) Running: T2 queue lock: BUSY (T2) Running: T2 item Ready Ready dataready dataready T1 queue à NULL NULL queue à T1 queue queue … … T1 (Waiting) T2 (Running) T1 (Ready) T2 (Running) RemoveFromQueue() { AddToQueue(item) { RemoveFromQueue() { AddToQueue(item) { signal() wakes up T1 and lock.Acquire(); lock.Acquire(); lock.Acquire(); lock.Acquire(); moves it on ready queue if (queue.isEmpty()) { queue.enqueue(item); if (queue.isEmpty()) { queue.enqueue(item); dataready.wait(&lock); dataready.signal(); dataready.wait(&lock); dataready.signal(); } lock.Release(); } lock.Release(); item = queue.dequeue(); } item = queue.dequeue(); } lock.Release(); lock.Release(); return(item); return(item); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.11 9/25/17 CS162 © UCB Fall 2017 Lec 9.12 Page 3 

4 . Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue lock: BUSY (T2) Running: T2 queue lock: FREE Running: Ready Ready dataready dataready NULL queue à T1, T3 NULL queue à T1, T3 queue queue … … T1 (Ready) T2 (Running) T3 (Ready) T1 (Ready) T2 (Terminate) T3 (Ready) RemoveFromQueue() { AddToQueue(item) { RemoveFromQueue() { RemoveFromQueue() { AddToQueue(item) { RemoveFromQueue() { lock.Acquire(); lock.Acquire(); lock.Acquire(); lock.Acquire(); lock.Acquire(); lock.Acquire(); if (queue.isEmpty()) { queue.enqueue(item); if (queue.isEmpty()) { if (queue.isEmpty()) { queue.enqueue(item); if (queue.isEmpty()) { dataready.wait(&lock); dataready.signal(); dataready.wait(&lock); dataready.wait(&lock); dataready.signal(); dataready.wait(&lock); } lock.Release(); } } lock.Release(); } item = queue.dequeue(); } item = queue.dequeue(); item = queue.dequeue(); } item = queue.dequeue(); lock.Release(); lock.Release(); lock.Release(); lock.Release(); return(item); return(item); return(item); return(item); } } } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.13 9/25/17 CS162 © UCB Fall 2017 Lec 9.14 Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue lock: FREE Running: T3 queue lock: BUSY (T3) Running: T3 Ready Ready dataready dataready NULL queue à T1 NULL queue à T1 queue queue … … T3 scheduled first! T1 (Ready) T3 (Running) T1 (Ready) T3 (Running) RemoveFromQueue() { RemoveFromQueue() { RemoveFromQueue() { RemoveFromQueue() { lock.Acquire(); lock.Acquire(); lock.Acquire(); lock.Acquire(); if (queue.isEmpty()) { if (queue.isEmpty()) { if (queue.isEmpty()) { if (queue.isEmpty()) { dataready.wait(&lock); dataready.wait(&lock); dataready.wait(&lock); dataready.wait(&lock); } } } } item = queue.dequeue(); item = queue.dequeue(); item = queue.dequeue(); item = queue.dequeue(); lock.Release(); lock.Release(); lock.Release(); lock.Release(); return(item); return(item); return(item); return(item); } } } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.15 9/25/17 CS162 © UCB Fall 2017 Lec 9.16 Page 4 

5 . Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue remove lock: BUSY (T3) Running: T3 queue lock: FREE Running: item Ready Ready dataready dataready NULL queue à T1 NULL queue à T1 queue queue … … T1 (Ready) T3 (Running) T1 (Ready) T3 (Finished) RemoveFromQueue() { RemoveFromQueue() { RemoveFromQueue() { RemoveFromQueue() { lock.Acquire(); lock.Acquire(); lock.Acquire(); lock.Acquire(); if (queue.isEmpty()) { if (queue.isEmpty()) { if (queue.isEmpty()) { if (queue.isEmpty()) { dataready.wait(&lock); dataready.wait(&lock); dataready.wait(&lock); dataready.wait(&lock); } } } } item = queue.dequeue(); item = queue.dequeue(); item = queue.dequeue(); item = queue.dequeue(); lock.Release(); lock.Release(); lock.Release(); lock.Release(); return(item); return(item); return(item); return(item); } } } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.17 9/25/17 CS162 © UCB Fall 2017 Lec 9.18 Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue lock: BUSY (T1) Running: T1 queue lock: BUSY (T1) Running: T1 Ready Ready dataready dataready NULL queue à NULL NULL queue à NULL queue queue … … T1 (Running) T1 (Running) RemoveFromQueue() { RemoveFromQueue() { lock.Acquire(); lock.Acquire(); if (queue.isEmpty()) { if (queue.isEmpty()) { dataready.wait(&lock); dataready.wait(&lock); } } item = queue.dequeue(); item = queue.dequeue(); lock.Release(); lock.Release(); ERROR: return(item); return(item); Nothing in the } } queue! 9/25/17 CS162 © UCB Fall 2017 Lec 9.19 9/25/17 CS162 © UCB Fall 2017 Lec 9.20 Page 5 

6 . Mesa Monitor: Why “while()”? Mesa Monitor: Why “while()”? App. Shared State Monitor CPU State App. Shared State Monitor CPU State queue lock: BUSY (T1) Running: T1 queue lock: BUSY (T1) Running: T1 Ready Ready dataready dataready NULL queue à NULL NULL queue à NULL queue queue … … T1 (Running) T1 (Ready) RemoveFromQueue() { RemoveFromQueue() { lock.Acquire(); lock.Acquire(); while (queue.isEmpty()) { while (queue.isEmpty()) { dataready.wait(&lock); dataready.wait(&lock); } } Check item = queue.dequeue(); item = queue.dequeue(); again if Replace lock.Release(); lock.Release(); empty! return(item);“if” with return(item); } “while” } 9/25/17 CS162 © UCB Fall 2017 Lec 9.21 9/25/17 CS162 © UCB Fall 2017 Lec 9.22 Mesa Monitor: Why “while()”? Readers/Writers Problem CPU State App. Shared State Monitor W queue lock: FREE Running: T1 Ready dataready T1 queue à NULL R queue … R R T1 (Waiting) RemoveFromQueue() { lock.Acquire(); •  Motivation: Consider a shared database while (queue.isEmpty()) { dataready.wait(&lock); –  Two classes of users: } »  Readers – never modify database item = queue.dequeue(); »  Writers – read and modify database lock.Release(); return(item); –  Is using a single lock on the whole database sufficient? } »  Like to have many readers at the same time »  Only one writer at a time 9/25/17 CS162 © UCB Fall 2017 Lec 9.23 9/25/17 CS162 © UCB Fall 2017 Lec 9.24 Page 6 

7 . Basic Readers/Writers Solution Code for a Reader •  Correctness Constraints: Reader() { –  Readers can access database when no writers // First check self into system –  Writers can access database when no readers or writers lock.Acquire(); –  Only one thread manipulates state variables at a time while ((AW + WW) > 0) { // Is it safe to read? •  Basic structure of a solution: WR++; // No. Writers exist – Reader() okToRead.wait(&lock); // Sleep on cond var Wait until no writers WR--; Why release lock// No longer waiting Access data base } here? Check out – wake up a waiting writer AR++; // Now we are active! – Writer() lock.release(); Wait until no active readers or writers Access database // Perform actual read-only access Check out – wake up waiting readers or writer AccessDatabase(ReadOnly); –  State variables (Protected by a lock called “lock”): // Now, check out of system »  int AR: Number of active readers; initially = 0 lock.Acquire(); »  int WR: Number of waiting readers; initially = 0 AR--; // No longer active »  int AW: Number of active writers; initially = 0 if (AR == 0 && WW > 0) // No other active readers »  int WW: Number of waiting writers; initially = 0 okToWrite.signal(); // Wake up one writer »  Condition okToRead = NIL lock.Release(); »  Condition okToWrite = NIL } 9/25/17 CS162 © UCB Fall 2017 Lec 9.25 9/25/17 CS162 © UCB Fall 2017 Lec 9.26 Code for a Writer Simulation of Readers/Writers Solution Writer() { // First check self into system lock.Acquire(); •  Use an example to simulate the solution while ((AW + AR) > 0) { // Is it safe to write? WW++; // No. Active users exist okToWrite.wait(&lock); // Sleep on cond var •  Consider the following sequence of operators: WW--; // No longer waiting } –  R1, R2, W1, R3 AW++; // Now we are active! lock.release(); // Perform actual read/write access •  Initially: AR = 0, WR = 0, AW = 0, WW = 0 AccessDatabase(ReadWrite); // Now, check out of system lock.Acquire(); AW--; // No longer active if (WW > 0){ // Give priority to writers okToWrite.signal(); // Wake up one writer } else if (WR > 0) { // Otherwise, wake reader okToRead.broadcast(); // Wake all readers Why broadcast() } Why Give priority lock.Release(); here instead of to writers? } signal()? 9/25/17 CS162 © UCB Fall 2017 Lec 9.27 9/25/17 CS162 © UCB Fall 2017 Lec 9.28 Page 7 

8 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R1 comes along •  R1 comes along •  AR = 0, WR = 0, AW = 0, WW = 0 •  AR = 0, WR = 0, AW = 0, WW = 0 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.29 9/25/17 CS162 © UCB Fall 2017 Lec 9.30 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R1 comes along •  R1 comes along •  AR = 1, WR = 0, AW = 0, WW = 0 •  AR = 1, WR = 0, AW = 0, WW = 0 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.31 9/25/17 CS162 © UCB Fall 2017 Lec 9.32 Page 8 

9 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R1 comes along •  R2 comes along •  AR = 1, WR = 0, AW = 0, WW = 0 •  AR = 1, WR = 0, AW = 0, WW = 0 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.33 9/25/17 CS162 © UCB Fall 2017 Lec 9.34 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R2 comes along •  R2 comes along •  AR = 1, WR = 0, AW = 0, WW = 0 •  AR = 2, WR = 0, AW = 0, WW = 0 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.35 9/25/17 CS162 © UCB Fall 2017 Lec 9.36 Page 9 

10 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R2 comes along •  R2 comes along •  AR = 2, WR = 0, AW = 0, WW = 0 •  AR = 2, WR = 0, AW = 0, WW = 0 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); Assume readers take a while to access database } } Situation: Locks released, only AR is non-zero 9/25/17 CS162 © UCB Fall 2017 Lec 9.37 9/25/17 CS162 © UCB Fall 2017 Lec 9.38 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  W1 comes along (R1 and R2 are still accessing dbase) •  W1 comes along (R1 and R2 are still accessing dbase) •  AR = 2, WR = 0, AW = 0, WW = 0 •  AR = 2, WR = 0, AW = 0, WW = 0 Writer() { Writer() { lock.Acquire(); lock.Acquire(); while ((AW + AR) > 0) { // Is it safe to write? while ((AW + AR) > 0) { // Is it safe to write? WW++; // No. Active users exist WW++; // No. Active users exist okToWrite.wait(&lock);// Sleep on cond var okToWrite.wait(&lock);// Sleep on cond var WW--; // No longer waiting WW--; // No longer waiting } } AW++; AW++; lock.release(); lock.release(); AccessDbase(ReadWrite); AccessDbase(ReadWrite); lock.Acquire(); lock.Acquire(); AW--; AW--; if (WW > 0){ if (WW > 0){ okToWrite.signal(); okToWrite.signal(); } else if (WR > 0) { } else if (WR > 0) { okToRead.broadcast(); okToRead.broadcast(); } } lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.39 9/25/17 CS162 © UCB Fall 2017 Lec 9.40 Page 10 

11 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  W1 comes along (R1 and R2 are still accessing dbase) •  W1 comes along (R1 and R2 are still accessing dbase) •  AR = 2, WR = 0, AW = 0, WW = 1 •  AR = 2, WR = 0, AW = 0, WW = 1 Writer() { Writer() { lock.Acquire(); lock.Acquire(); while ((AW + AR) > 0) { // Is it safe to write? while ((AW + AR) > 0) { // Is it safe to write? WW++; // No. Active users exist WW++; // No. Active users exist okToWrite.wait(&lock);// Sleep on cond var okToWrite.wait(&lock);// Sleep on cond var WW--; // No longer waiting WW--; // No longer waiting } } AW++; AW++; lock.release(); lock.release(); AccessDbase(ReadWrite); AccessDbase(ReadWrite); lock.Acquire(); lock.Acquire(); AW--; AW--; if (WW > 0){ if (WW > 0){ okToWrite.signal(); okToWrite.signal(); } else if (WR > 0) { } else if (WR > 0) { okToRead.broadcast(); okToRead.broadcast(); } } lock.Release(); lock.Release(); } } W1 cannot start because of readers, so goes to sleep 9/25/17 CS162 © UCB Fall 2017 Lec 9.41 9/25/17 CS162 © UCB Fall 2017 Lec 9.42 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R3 comes along (R1, R2 accessing dbase, W1 waiting) •  R3 comes along (R1, R2 accessing dbase, W1 waiting) •  AR = 2, WR = 0, AW = 0, WW = 1 •  AR = 2, WR = 0, AW = 0, WW = 1 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.43 9/25/17 CS162 © UCB Fall 2017 Lec 9.44 Page 11 

12 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R3 comes along (R1, R2 accessing dbase, W1 waiting) •  R3 comes along (R1, R2 accessing dbase, W1 waiting) •  AR = 2, WR = 1, AW = 0, WW = 1 •  AR = 2, WR = 1, AW = 0, WW = 1 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); Status: okToWrite.signal(); lock.Release(); •  R1 lock.Release(); and R2 still reading } } •  W1 and R3 waiting on okToWrite and okToRead, respectively 9/25/17 CS162 © UCB Fall 2017 Lec 9.45 9/25/17 CS162 © UCB Fall 2017 Lec 9.46 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R2 finishes (R1 accessing dbase, W1, R3 waiting) •  R2 finishes (R1 accessing dbase, W1, R3 waiting) •  AR = 2, WR = 1, AW = 0, WW = 1 •  AR = 1, WR = 1, AW = 0, WW = 1 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.47 9/25/17 CS162 © UCB Fall 2017 Lec 9.48 Page 12 

13 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R2 finishes (R1 accessing dbase, W1, R3 waiting) •  R2 finishes (R1 accessing dbase, W1, R3 waiting) •  AR = 1, WR = 1, AW = 0, WW = 1 •  AR = 1, WR = 1, AW = 0, WW = 1 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.49 9/25/17 CS162 © UCB Fall 2017 Lec 9.50 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R1 finishes (W1, R3 waiting) •  R1 finishes (W1, R3 waiting) •  AR = 1, WR = 1, AW = 0, WW = 1 •  AR = 0, WR = 1, AW = 0, WW = 1 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.51 9/25/17 CS162 © UCB Fall 2017 Lec 9.52 Page 13 

14 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R1 finishes (W1, R3 waiting) •  R1 finishes (W1, R3 waiting) •  AR = 0, WR = 1, AW = 0, WW = 1 •  AR = 0, WR = 1, AW = 0, WW = 1 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } All reader finished, signal writer – note, R3 still waiting 9/25/17 CS162 © UCB Fall 2017 Lec 9.53 9/25/17 CS162 © UCB Fall 2017 Lec 9.54 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  W1 gets signal (R3 still waiting) •  W1 gets signal (R3 still waiting) •  AR = 0, WR = 1, AW = 0, WW = 1 •  AR = 0, WR = 1, AW = 0, WW = 0 Writer() { Writer() { lock.Acquire(); lock.Acquire(); while ((AW + AR) > 0) { // Is it safe to write? while ((AW + AR) > 0) { // Is it safe to write? WW++; // No. Active users exist WW++; // No. Active users exist okToWrite.wait(&lock);// Sleep on cond var okToWrite.wait(&lock);// Sleep on cond var WW--; // No longer waiting WW--; // No longer waiting } } Got signal AW++; AW++; from R1lock.release(); lock.release(); AccessDbase(ReadWrite); AccessDbase(ReadWrite); lock.Acquire(); lock.Acquire(); AW--; AW--; if (WW > 0){ if (WW > 0){ okToWrite.signal(); okToWrite.signal(); } else if (WR > 0) { } else if (WR > 0) { okToRead.broadcast(); okToRead.broadcast(); } } lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.55 9/25/17 CS162 © UCB Fall 2017 Lec 9.56 Page 14 

15 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  W1 gets signal (R3 still waiting) •  W1 gets signal (R3 still waiting) •  AR = 0, WR = 1, AW = 1, WW = 0 •  AR = 0, WR = 1, AW = 1, WW = 0 Writer() { Writer() { lock.Acquire(); lock.Acquire(); while ((AW + AR) > 0) { // Is it safe to write? while ((AW + AR) > 0) { // Is it safe to write? WW++; // No. Active users exist WW++; // No. Active users exist okToWrite.wait(&lock);// Sleep on cond var okToWrite.wait(&lock);// Sleep on cond var WW--; // No longer waiting WW--; // No longer waiting } } AW++; AW++; lock.release(); lock.release(); AccessDbase(ReadWrite); AccessDbase(ReadWrite); lock.Acquire(); lock.Acquire(); AW--; AW--; if (WW > 0){ if (WW > 0){ okToWrite.signal(); okToWrite.signal(); } else if (WR > 0) { } else if (WR > 0) { okToRead.broadcast(); okToRead.broadcast(); } } lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.57 9/25/17 CS162 © UCB Fall 2017 Lec 9.58 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  W1 gets signal (R3 still waiting) •  W1 gets signal (R3 still waiting) •  AR = 0, WR = 1, AW = 0, WW = 0 •  AR = 0, WR = 1, AW = 0, WW = 0 Writer() { Writer() { lock.Acquire(); lock.Acquire(); while ((AW + AR) > 0) { // Is it safe to write? while ((AW + AR) > 0) { // Is it safe to write? WW++; // No. Active users exist WW++; // No. Active users exist okToWrite.wait(&lock);// Sleep on cond var okToWrite.wait(&lock);// Sleep on cond var WW--; // No longer waiting WW--; // No longer waiting } } AW++; AW++; lock.release(); lock.release(); AccessDbase(ReadWrite); AccessDbase(ReadWrite); lock.Acquire(); lock.Acquire(); AW--; AW--; if (WW > 0){ if (WW > 0){ okToWrite.signal(); okToWrite.signal(); } else if (WR > 0) { } else if (WR > 0) { okToRead.broadcast(); okToRead.broadcast(); } } lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.59 9/25/17 CS162 © UCB Fall 2017 Lec 9.60 Page 15 

16 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  W1 gets signal (R3 still waiting) •  R1 finishes (W1, R3 waiting) •  AR = 0, WR = 1, AW = 0, WW = 0 •  AR = 0, WR = 1, AW = 0, WW = 0 Writer() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + AR) > 0) { // Is it safe to write? WW++; // No. Active users exist while ((AW + WW) > 0) { // Is it safe to read? okToWrite.wait(&lock);// Sleep on cond var WR++; // No. Writers exist WW--; // No longer waiting okToRead.wait(&lock); // Sleep on cond var } WR--; // No longer waiting AW++; } lock.release(); Got signal AR++; // Now we are active! from W1 lock.release(); AccessDbase(ReadWrite); AccessDbase(ReadOnly); lock.Acquire(); AW--; if (WW > 0){ lock.Acquire(); okToWrite.signal(); AR--; } else if (WR > 0) { if (AR == 0 && WW > 0) okToRead.broadcast(); okToWrite.signal(); } lock.Release(); lock.Release(); } } No waiting writer, signal reader R3 9/25/17 CS162 © UCB Fall 2017 Lec 9.61 9/25/17 CS162 © UCB Fall 2017 Lec 9.62 Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R1 finishes (W1, R3 waiting) •  R1 finishes (W1, R3 waiting) •  AR = 0, WR = 0, AW = 0, WW = 0 •  AR = 0, WR = 0, AW = 0, WW = 0 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.63 9/25/17 CS162 © UCB Fall 2017 Lec 9.64 Page 16 

17 . Simulation of Readers/Writers Solution Simulation of Readers/Writers Solution •  R1 finishes (W1, R3 waiting) •  R1 finishes (W1, R3 waiting) •  AR = 0, WR = 0, AW = 0, WW = 0 •  AR = 0, WR = 0, AW = 0, WW = 0 Reader() { Reader() { lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { // Is it safe to read? while ((AW + WW) > 0) { // Is it safe to read? WR++; // No. Writers exist WR++; // No. Writers exist okToRead.wait(&lock); // Sleep on cond var okToRead.wait(&lock); // Sleep on cond var WR--; // No longer waiting WR--; // No longer waiting } } AR++; // Now we are active! AR++; // Now we are active! lock.release(); lock.release(); AccessDbase(ReadOnly); AccessDbase(ReadOnly); lock.Acquire(); lock.Acquire(); AR--; AR--; if (AR == 0 && WW > 0) if (AR == 0 && WW > 0) okToWrite.signal(); okToWrite.signal(); lock.Release(); lock.Release(); } } DONE! 9/25/17 CS162 © UCB Fall 2017 Lec 9.65 9/25/17 CS162 © UCB Fall 2017 Lec 9.66 Read/Writer Questions Read/Writer Questions Reader() { Writer() { Reader() { Writer() { // check into system // check into system // check into system // check into system lock.Acquire(); lock.Acquire(); lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { while ((AW + AR) > 0) { while ((AW + WW) > 0) { while ((AW + AR) > 0) { WW++; WW++; WR++; okToWrite.wait(&lock); WR++; okToWrite.wait(&lock); okToRead.wait(&lock); WW--; okToRead.wait(&lock); WW--; WR--; } WR--; } } AW++; } AW++; AR++; lock.release(); AR++; lock.release(); lock.release(); lock.release(); // read/write access // read/write access AccessDbase(ReadWrite); AccessDbase(ReadWrite); // read-only What if we access // read-only access AccessDbase(ReadOnly); remove this AccessDbase(ReadOnly); What if we turn line? // check out of system // check out of system lock.Acquire(); signal to lock.Acquire(); // check out of system AW--; // check out broadcast? of system AW--; if (WW > 0){ if (WW > 0){ lock.Acquire(); okToWrite.signal(); lock.Acquire(); okToWrite.signal(); AR--; } else if (WR > 0) { AR--; } else if (WR > 0) { if (AR == 0 && WW > 0) okToRead.broadcast(); if (AR == 0 && WW > 0) okToRead.broadcast(); okToWrite.signal(); } okToWrite.broadcast(); } lock.Release(); lock.Release(); lock.Release(); lock.Release(); } } } } 9/25/17 CS162 © UCB Fall 2017 Lec 9.67 9/25/17 CS162 © UCB Fall 2017 Lec 9.68 Page 17 

18 . Read/Writer Questions Read/Writer Questions Reader() { Writer() { Writer() { // check into system // check into system Reader() { lock.Acquire(); lock.Acquire(); // check into system // check into system lock.Acquire(); lock.Acquire(); while ((AW + WW) > 0) { while ((AW + AR) > 0) { WW++; while ((AW + WW) > 0) { while ((AW + AR) > 0) { WR++; okContinue.wait(&lock); WW++; okContinue.wait(&lock); WW--; WR++; okContinue.wait(&lock); } okContinue.wait(&lock); WW--; WR--; WR--; } } AW++; } AW++; AR++; lock.release(); AR++; lock.release(); lock.release(); lock.release(); // read/write access // read/write access AccessDbase(ReadWrite); AccessDbase(ReadWrite); // read-only access // read-only access AccessDbase(ReadOnly); // check out of system AccessDbase(ReadOnly); lock.Acquire(); // check out of system AW--; lock.Acquire(); // check out of system if (WW > 0){ // check out of system AW--; lock.Acquire(); okContinue.signal(); lock.Acquire(); if (WW > 0){ AR--; } else if (WR > 0) { okContinue.signal(); if (AR == 0 && WW > 0) okContinue.broadcast(); AR--; } else if (WR > 0) { okContinue.signal(); } if (AR == 0 && WW > 0) okContinue.broadcast(); lock.Release(); okContinue.signal(); } lock.Release(); lock.Release(); } } lock.Release(); } } •  R1 arrives •  W1, R2 arrive while R1 still reading à W1 and R2 wait for R1 to finish What if we turn okToWrite and okToRead into okContinue? •  Assume R1’s signal is delivered to R2 (not W1) 9/25/17 CS162 © UCB Fall 2017 Lec 9.69 9/25/17 CS162 © UCB Fall 2017 Lec 9.70 Read/Writer Questions Administrivia Reader() { Writer() { // check into system // check into system lock.Acquire(); •  Midterm on Thursday 9/28 6:30-8PM lock.Acquire(); while ((AW + WW) > 0) { while ((AW + AR) > 0) { WW++; WR++; okContinue.wait(&lock); okContinue.wait(&lock); WR--; } WW--; •  Closed book, no calculators, one double-side letter-sized } AW++; page of handwritten notes AR++; lock.release(); lock.release(); // read/write access AccessDbase(ReadWrite); // read-only access AccessDbase(ReadOnly); // check out of system lock.Acquire(); // check out of system AW--; if (WW > 0){ lock.Acquire(); okContinue.signal(); AR--; } else if (WR > 0) { if (AR == 0 && WW > 0) okContinue.broadcast(); okContinue.broadcast(); } lock.Release(); lock.Release(); } } Need to change to broadcast! 9/25/17 CS162 © UCB Fall 2017 Lec 9.71 9/25/17 CS162 © UCB Fall 2017 Lec 9.72 Page 18 

19 . Recall: CPU Scheduling •  Earlier, we talked about the life-cycle of a thread BREAK – Active threads work their way from Ready queue to Running to various waiting queues. 9/25/17 CS162 © UCB Fall 2017 Lec 9.73 9/25/17 CS162 © UCB Fall 2017 Lec 9.74 Recall: CPU Scheduling (Cont.) Assumption – CPU Bursts Weighted toward small bursts •  Question: How does OS decide which thread to dequeue? •  Execution model: programs alternate between bursts of CPU and I/O –  Obvious queue to worry about is ready queue –  Program typically uses the CPU for some period of time, then does I/O, then uses CPU again –  Others can be scheduled as well, however –  Each scheduling decision is about which job to give to the CPU for use •  Scheduling: deciding which threads are given access to by its next CPU burst resources from moment to moment –  With timeslicing, thread may be forced to give up CPU before finishing current CPU burst 9/25/17 CS162 © UCB Fall 2017 Lec 9.75 9/25/17 CS162 © UCB Fall 2017 Lec 9.76 Page 19 

20 . Scheduling Assumptions Scheduling Assumptions (Cont.) •  CPU scheduling big area of research in early 70’s •  Clearly, unrealistic but they simplify the problem •  Many implicit assumptions for CPU scheduling: –  For instance: is “fair” about fairness among users or programs? –  One program per user »  If I run one compilation job and you run five, you get five –  One thread per program times as much CPU on many operating systems –  Programs are independent •  The high-level goal: Dole out CPU time to optimize some desired parameters of system USER1 USER2 USER3 USER1 USER2 Time 9/25/17 CS162 © UCB Fall 2017 Lec 9.77 9/25/17 CS162 © UCB Fall 2017 Lec 9.78 Scheduling Policy Goals/Criteria Scheduling Policy Goals/Criteria (Cont.) •  Minimize Response Time •  Maximize Throughput –  Minimize elapsed time to do an operation (or job) –  Maximize operations (or jobs) per second –  Response time is what the user sees: –  Throughput related to response time, but not identical: »  Time to echo a keystroke in editor »  Minimizing response time will lead to more context switching »  Time to compile a program than if you only maximized throughput »  Real-time tasks: Must meet deadlines imposed by World –  Two parts to maximizing throughput »  Minimize overhead (for example, context-switching) »  Efficient use of resources (CPU, disk, memory, etc) 9/25/17 CS162 © UCB Fall 2017 Lec 9.79 9/25/17 CS162 © UCB Fall 2017 Lec 9.80 Page 20 

21 . Scheduling Policy Goals/Criteria (Cont.) First-Come, First-Served (FCFS) Scheduling •  First-Come, First-Served (FCFS) •  Fairness –  Also “First In, First Out” (FIFO) or “Run until done” –  Share CPU among users in some equitable way »  In early systems, FCFS meant one program –  Fairness is not minimizing average response time: scheduled until done (including I/O) »  Better average response time by making system less fair »  Now, means keep CPU until thread blocks •  Example: Process Burst Time P1 24 P2 3 P3 3 –  Suppose processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is: P1 P2 P3 0 24 27 30 9/25/17 CS162 © UCB Fall 2017 Lec 9.81 9/25/17 CS162 © UCB Fall 2017 Lec 9.82 FCFS Scheduling (Cont.) FCFS Scheduling (Cont.) •  Example continued: •  Example continued: –  Suppose that processes arrive in order: P2 , P3 , P1 Now, we have: P1 P2 P3 P2 P3 P1 0 24 27 30 0 3 6 30 –  Waiting time for P1 = 0; P2 = 24; P3 = 27 –  Waiting time for P1 = 6; P2 = 0; P3 = 3 –  Average waiting time: (0 + 24 + 27)/3 = 17 –  Average waiting time: (6 + 0 + 3)/3 = 3 –  Average Completion time: (24 + 27 + 30)/3 = 27 –  Average Completion time: (3 + 6 + 30)/3 = 13 •  Convoy effect: short process behind long process •  In second case: –  Average waiting time is much better (before it was 17) –  Average completion time is better (before it was 27) •  FIFO Pros and Cons: –  Simple (+) –  Short jobs get stuck behind long ones (-) »  Safeway: Getting milk, always stuck behind cart full of small items 9/25/17 CS162 © UCB Fall 2017 Lec 9.83 9/25/17 CS162 © UCB Fall 2017 Lec 9.84 Page 21 

22 . Round Robin (RR) Scheduling RR Scheduling (Cont.) •  FCFS Scheme: Potentially bad for short jobs! •  Performance –  Depends on submit order –  q large ⇒ FCFS –  If you are first in line at supermarket with milk, you don’t care who is behind you, on the other hand… –  q small ⇒ Interleaved (really small ⇒ hyperthreading?) •  Round Robin Scheme –  q must be large with respect to context switch, otherwise –  Each process gets a small unit of CPU time overhead is too high (all overhead) (time quantum), usually 10-100 milliseconds –  After quantum expires, the process is preempted and added to the end of the ready queue. –  n processes in ready queue and time quantum is q ⇒ »  Each process gets 1/n of the CPU time »  In chunks of at most q time units »  No process waits more than (n-1)q time units 9/25/17 CS162 © UCB Fall 2017 Lec 9.85 9/25/17 CS162 © UCB Fall 2017 Lec 9.86 Example of RR with Time Quantum = 20 Round-Robin Discussion •  Example: Process Burst Time •  How do you choose time slice? P1 53 –  What if too big? P2 8 P3 68 »  Response time suffers P4 24 –  What if infinite (∞)? –  The Gantt chart is: »  Get back FIFO P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 –  What if time slice too small? 0 20 28 48 68 88 108 112 125 145 153 »  Throughput suffers! –  Waiting time for P1=(68-20)+(112-88)=72 •  Actual choices of timeslice: P2=(20-0)=20 –  Initially, UNIX timeslice one second: P3=(28-0)+(88-48)+(125-108)=85 »  Worked ok when UNIX was used by one or two people. P4=(48-0)+(108-68)=88 »  What if three compilations going on? 3 seconds to echo each –  Average waiting time = (72+20+85+88)/4=66¼ keystroke! –  Average completion time = (125+28+153+112)/4 = 104½ –  Need to balance short-job performance and long-job throughput: •  Thus, Round-Robin Pros and Cons: »  Typical time slice today is between 10ms – 100ms –  Better for short jobs, Fair (+) »  Typical context-switching overhead is 0.1ms – 1ms –  Context-switching time adds up for long jobs (-) »  Roughly 1% overhead due to context-switching 9/25/17 CS162 © UCB Fall 2017 Lec 9.87 9/25/17 CS162 © UCB Fall 2017 Lec 9.88 Page 22 

23 . Comparisons between FCFS and Round Robin Earlier Example with Different Time Quantum •  Assuming zero-cost context-switching time, is RR always better than P2 P4 P1 P3 FCFS? Best FCFS: [8] [24] [53] [68] •  Simple example: 10 jobs, each take 100s of CPU time 0 8 32 85 153 RR scheduler quantum of 1s All jobs start at the same time Quantum P1 P2 P3 P4 Average •  Completion Times: Job # FIFO RR Best FCFS 32 0 85 8 31¼ 1 100 991 Q=1 84 22 85 57 62 Q=5 82 20 85 58 61¼ 2 200 992 Wait Q=8 80 8 85 56 57¼ … … … Time Q = 10 82 10 85 68 61¼ 9 900 999 Q = 20 72 20 85 88 66¼ 10 1000 1000 Worst FCFS 68 145 0 121 83½ –  Both RR and FCFS finish at the same time Best FCFS 85 8 153 32 69½ –  Average response time is much worse under RR! Q=1 137 30 153 81 100½ »  Bad when all jobs same length Q=5 135 28 153 82 99½ Completion Q=8 133 16 153 80 95½ •  Also: Cache state must be shared between all jobs with RR but can Time Q = 10 135 18 153 92 99½ be devoted to each job with FIFO Q = 20 125 28 153 112 104½ –  Total time for RR longer even for zero-cost switch! Worst FCFS 121 153 68 145 121¾ 9/25/17 CS162 © UCB Fall 2017 Lec 9.89 9/25/17 CS162 © UCB Fall 2017 Lec 9.90 Synchronization Summary •  Monitors: A lock plus zero or more condition variables –  Always acquire lock before accessing shared data –  Use condition variables to wait inside critical section »  Three Operations: Wait(), Signal(), Broadcast() •  Round-Robin Scheduling: –  Give each thread a small amount of CPU time when it executes; cycle between all ready threads –  Pros: Better for short jobs 9/25/17 CS162 © UCB Fall 2017 Lec 9.91 Page 23