操作系统之程序锁、信号量、临界区

1 . Review: Too Much Milk Solution #3 •  Here is a possible two-note solution: CS162 Thread A Thread B Operating Systems and leave note A; while (note B) {\\X leave note B; if (noNote A) {\\Y Systems Programming do nothing; if (noMilk) { } buy milk; Lecture 8 if (noMilk) { } buy milk; } } remove note B; Locks, Semaphores, Monitors remove note A; •  Does this work? Yes. Both can guarantee that: –  It is safe to buy, or –  Other will buy, ok to quit September 20, 2017 •  At X: Prof. Ion Stoica –  If no note B, safe for A to buy, http://cs162.eecs.Berkeley.edu –  Otherwise wait to find out what will happen •  At Y: –  If no note A, safe for B to buy –  Otherwise, A is either buying or waiting for B to quit 9/20/17 CS162 ©UCB Fall 2017 Lec 8.2 Case 1 Case 1 •  “leave note A” happens before “if (noNote A)” •  “leave note A” happens before “if (noNote A)” leave note A; happene leave note B; leave note A; happene leave note B; d d while (note B) {\\X before if (noNote A) {\\Y while (note B) {\\X before if (noNote A) {\\Y do nothing; if (noMilk) { do nothing; if (noMilk) { }; buy milk; }; buy milk; } } } } remove note B; remove note B; if (noMilk) { if (noMilk) { buy milk; } buy milk; } } } remove note A; remove note A; 9/20/17 CS162 ©UCB Fall 2017 Lec 8.3 9/20/17 CS162 ©UCB Fall 2017 Lec 8.4 Page 1 

2 . Case 1 Case 2 •  “leave note A” happens before “if (noNote A)” •  “if (noNote A)” happens before “leave note A” leave note A; happene leave note B; leave note B; d while (note B) {\\X before if (noNote A) {\\Y ned if (noNote A) {\\Y happe e do nothing; if (noMilk) { leave note A; befor if (noMilk) { }; buy milk; while (note B) {\\X buy milk; } do nothing; } Wait for note B to } }; } be remove remove note B; remove note B; if (noMilk) { buy milk; } if (noMilk) { } buy milk; } remove note A; } remove note A; 9/20/17 CS162 ©UCB Fall 2017 Lec 8.5 9/20/17 CS162 ©UCB Fall 2017 Lec 8.6 Case 2 Case 2 •  “if (noNote A)” happens before “leave note A” •  “if (noNote A)” happens before “leave note A” leave note B; leave note B; ned if (noNote A) {\\Y ned if (noNote A) {\\Y happe e happe e leave note A; befor if (noMilk) { leave note A; befor if (noMilk) { while (note B) {\\X buy milk; while (note B) {\\X buy milk; do nothing; } do nothing; } }; } }; } remove note B; remove note B; Wait for note B to be remove if (noMilk) { if (noMilk) { buy milk; } buy milk; } } } remove note A; remove note A; 9/20/17 CS162 ©UCB Fall 2017 Lec 8.7 9/20/17 CS162 ©UCB Fall 2017 Lec 8.8 Page 2 

3 . Review: Solution #3 discussion Too Much Milk: Solution #4 •  Our solution protects a single “Critical-Section” piece of code for each •  Suppose we have some sort of implementation of a lock thread: –  lock.Acquire() – wait until lock is free, then grab if (noMilk) { buy milk; –  lock.Release() – Unlock, waking up anyone waiting } –  These must be atomic operations – if two threads are waiting for the •  Solution #3 works, but it’s really unsatisfactory lock and both see it’s free, only one succeeds to grab the lock –  Really complex – even for this simple an example •  Then, our milk problem is easy: »  Hard to convince yourself that this really works milklock.Acquire(); –  A’s code is different from B’s – what if lots of threads? if (nomilk) »  Code would have to be slightly different for each thread buy milk; –  While A is waiting, it is consuming CPU time milklock.Release(); »  This is called “busy-waiting” •  Once again, section of code between Acquire() and •  There’s a better way Release() called a “Critical Section” –  Have hardware provide higher-level primitives than atomic load & store •  Of course, you can make this even simpler: suppose you are out of –  Build even higher-level programming abstractions on this hardware support ice cream instead of milk –  Skip the test since you always need more ice cream ;-) 9/20/17 CS162 ©UCB Fall 2017 Lec 8.9 9/20/17 CS162 ©UCB Fall 2017 Lec 8.10 Where are we going with synchronization? Goals for Today Programs Shared Programs • Explore several implementations of locks Higher- level Locks Semaphores Monitors Send/Receive • Continue with Synchronization Abstractions API – Semaphores, Monitors, and Condition variables Hardware Load/Store Disable Ints Test&Set Compare&Swap • Very Quick Introduction to scheduling •  We are going to implement various higher-level synchronization primitives using atomic operations –  Everything is pretty painful if only atomic primitives are load and store –  Need to provide primitives useful at user-level 9/20/17 CS162 ©UCB Fall 2017 Lec 8.11 9/20/17 CS162 ©UCB Fall 2017 Lec 8.12 Page 3 

4 . How to Implement Locks? Naïve use of Interrupt Enable/Disable •  Lock: prevents someone from doing something –  Lock before entering critical section and How can we build multi-instruction atomic operations? before accessing shared data •  Recall: dispatcher gets control in two ways. –  Unlock when leaving, after accessing shared data –  Wait if locked –  Internal: Thread does something to relinquish the CPU »  Important idea: all synchronization involves waiting –  External: Interrupts cause dispatcher to take CPU »  Should sleep if waiting for a long time •  On a uniprocessor, can avoid context-switching by: •  Atomic Load/Store: get solution like Milk #3 –  Avoiding internal events (although virtual memory tricky) –  Pretty complex and error prone –  Preventing external events by disabling interrupts •  Hardware Lock instruction –  Is this a good idea? Consequently, naïve Implementation of locks: –  What about putting a task to sleep? LockAcquire { disable Ints; } »  How do you handle the interface between the hardware and scheduler? LockRelease { enable Ints; } –  Complexity? »  Done in the Intel 432 – each feature makes HW more complex and slow 9/20/17 CS162 ©UCB Fall 2017 Lec 8.13 9/20/17 CS162 ©UCB Fall 2017 Lec 8.14 Naïve use of Interrupt Enable/Disable: Problems Better Implementation of Locks by Disabling Interrupts Key idea: maintain a lock variable and impose mutual exclusion only during operations on that variable Can’t let user do this! Consider following: LockAcquire(); While(TRUE) {;} int value = FREE; Real-Time system—no guarantees on timing! Acquire() { Release() { disable interrupts; disable interrupts; •  Critical Sections might be arbitrarily long if (value == BUSY) { if (anyone on wait queue) { What happens with I/O or other important events? put thread on wait queue; take thread off wait queue Go to sleep(); Place on ready queue; •  “Reactor about to meltdown. Help?” // Enable interrupts? } else { value = FREE; } else { } value = BUSY; enable interrupts; } } enable interrupts; } 9/20/17 CS162 ©UCB Fall 2017 Lec 8.15 9/20/17 CS162 ©UCB Fall 2017 Lec 8.16 Page 4 

5 . New Lock Implementation: Discussion Interrupt Re-enable in Going to Sleep •  Why do we need to disable interrupts at all? –  Avoid interruption between checking and setting lock value •  What about re-enabling ints when going to sleep? Acquire() { –  Otherwise two threads could think that they both have lock disable interrupts; Acquire() { if (value == BUSY) { disable interrupts; Enable Position put thread on wait queue; if (value == BUSY) { Enable Position Go to sleep(); put thread on wait queue; Enable Position } else { Go to sleep(); // Enable interrupts? Critical value = BUSY; } } else { Section enable interrupts; value = BUSY; } } •  Before Putting thread on the wait queue? enable interrupts; } –  Release can check the queue and not wake up thread •  Note: unlike previous solution, the critical section (inside •  After putting the thread on the wait queue Acquire()) is very short –  Release puts the thread on the ready queue, but the thread still thinks –  User of lock can take as long as they like in their own critical section: it needs to go to sleep doesn’t impact global machine behavior –  Misses wakeup and still holds lock (deadlock!) –  Critical interrupts taken in time! •  Want to put it after sleep(). But – how? 9/20/17 CS162 ©UCB Fall 2017 Lec 8.17 9/20/17 CS162 ©UCB Fall 2017 Lec 8.18 How to Re-enable After Sleep()? Atomic Read-Modify-Write Instructions •  In scheduler, since interrupts are disabled when you call sleep: •  Problems with previous solution: –  Responsibility of the next thread to re-enable ints –  When the sleeping thread wakes up, returns to acquire and re-enables –  Can’t give lock implementation to users interrupts –  Doesn’t work well on multiprocessor Thread A Thread B . »  Disabling interrupts on all processors requires messages and . would be very time consuming disable ints sleep context sleep return •  Alternative: atomic instruction sequences switch enable ints –  These instructions read a value and write a new value atomically . . –  Hardware is responsible for implementing this correctly . »  on both uniprocessors (not too hard) disable int sleep »  and multiprocessors (requires help from cache coherence sleep return context protocol) enable ints witch . s –  Unlike disabling interrupts, can be used on both uniprocessors . and multiprocessors 9/20/17 CS162 ©UCB Fall 2017 Lec 8.19 9/20/17 CS162 ©UCB Fall 2017 Lec 8.20 Page 5 

6 . Examples of Read-Modify-Write Implementing Locks with test&set •  Another flawed, but simple solution: •  test&set (&address) { /* most architectures */ result = M[address]; /* return result from “address” and int value = 0; // Free M[address] = 1; set value at “address” to 1 */ return result; Acquire() { } while (test&set(value)); // while busy } •  swap (&address, register) { /* x86 */ Release() { temp = M[address]; /* swap register’s value to value = 0; M[address] = register; value at “address” */ } register = temp; } •  Simple explanation: –  If lock is free, test&set reads 0 and sets value=1, so lock is now busy •  compare&swap (&address, reg1, reg2) { /* 68000 */ It returns 0 so while exits if (reg1 == M[address]) { M[address] = reg2; –  If lock is busy, test&set reads 1 and sets value=1 (no change) return success; It returns 1, so while loop continues } else { return failure; –  When we set value = 0, someone else can get lock } } •  Busy-Waiting: thread consumes cycles while waiting 9/20/17 CS162 ©UCB Fall 2017 Lec 8.21 9/20/17 CS162 ©UCB Fall 2017 Lec 8.22 Problem: Busy-Waiting for Lock Better Locks using test&set •  Positives for this solution •  Can we build test&set locks without busy-waiting? –  Machine can receive interrupts –  Can’t entirely, but can minimize! –  User code can use this lock –  Idea: only busy-wait to atomically check lock value –  Works on a multiprocessor int guard = 0; int value = FREE; •  Negatives –  This is very inefficient as thread will consume cycles waiting Acquire() { Release() { –  Waiting thread may take cycles away from thread holding lock (no // Short busy-wait time // Short busy-wait time while (test&set(guard)); one wins!) while (test&set(guard)); if anyone on wait queue { if (value == BUSY) { –  Priority Inversion: If busy-waiting thread has higher priority than take thread off wait queue put thread on wait queue; thread holding lock ⇒ no progress! go to sleep() & guard = 0; Place on ready queue; } else { •  Priority Inversion problem with original Martian rover } else { value = FREE; •  For semaphores and monitors, waiting thread may wait for an value = BUSY; } guard = 0; guard = 0; arbitrary long time! } –  Thus even if busy-waiting was OK for locks, definitely not ok for } other primitives •  Note: sleep has to be sure to reset the guard variable –  Homework/exam solutions should avoid busy-waiting! –  Why can’t we do it just before or just after the sleep? 9/20/17 CS162 ©UCB Fall 2017 Lec 8.23 9/20/17 CS162 ©UCB Fall 2017 Lec 8.24 Page 6 

7 . Locks using Interrupts vs. test&set Recap: Locks using interrupts Compare to “disable interrupt” solution int value = 0; Acquire() { int value = FREE; // Short busy-wait time Acquire() { disable interrupts; disable interrupts; if (value == 1) { Acquire() { Release() { } put thread on wait-queue; disable interrupts; disable interrupts; go to sleep() //?? if (value == BUSY) { if (anyone on wait queue) { lock.Acquire(); } else { … value = 1; put thread on wait queue; take thread off wait queue enable interrupts; Go to sleep(); Place on ready queue; critical section; } } else { … } // Enable interrupts? lock.Release(); value = FREE; } else { } value = BUSY; enable interrupts; Release() { Release() { } enable interrupts; // Short busy-wait time } } disable interrupts; enable interrupts; if anyone on wait queue { } take thread off wait-queue If one thread in critical Place on ready queue; section, no other } else { Basically replace value = 0; –  disable interrupts à while (test&set(guard)); activity (including OS) } can run! enable interrupts; –  enable interrupts à guard = 0; } 9/20/17 CS162 ©UCB Fall 2017 Lec 8.25 9/20/17 CS162 ©UCB Fall 2017 Lec 8.26 Recap: Locks using test & wait Administrivia int guard = 0; int value = 0; •  Midterm Thursday 9/28 6:30-8PM Acquire() { // Short busy-wait time int value = 0; while(test&set(guard)); •  Project 1 Design Document due today Acquire() { if (value == 1) { while(test&set(value)); put thread on wait-queue; } go to sleep()& guard = 0; •  Project 1 Design reviews upcoming } else { lock.Acquire(); value = 1; –  High-level discussion of your approach … critical section; guard = 0; »  What will you modify? } … } »  What algorithm will you use? lock.Release(); »  How will things be linked together, etc. Release() { Release() { »  Do not need final design (complete with all semicolons!) value = 0; // Short busy-wait time –  You will be asked about testing } while (test&set(guard)); if anyone on wait queue { »  Understand testing framework take thread off wait-queue »  Are there things you are doing that are not tested by tests we give you? Place on ready queue; Threads waiting to } else { enter critical section value = 0; •  Do your own work! } busy-wait guard = 0; –  Please do not try to find solutions from previous terms } –  We will be on the look out for anyone doing this…today 9/20/17 CS162 ©UCB Fall 2017 Lec 8.27 9/20/17 CS162 ©UCB Fall 2017 Lec 8.28 Page 7 

8 . Higher-level Primitives than Locks •  Goal of last couple of lectures: –  What is right abstraction for synchronizing threads that share memory? –  Want as high a level primitive as possible •  Good primitives and practices important! –  Since execution is not entirely sequential, really hard to find bugs, since they happen rarely –  UNIX is pretty stable now, but up until about mid-80s (10 years after started), systems running UNIX would crash every week or so – concurrency bugs BREAK •  Synchronization is a way of coordinating multiple concurrent activities that are using shared state –  This lecture and the next presents a some ways of structuring sharing 9/20/17 CS162 ©UCB Fall 2017 Lec 8.29 9/20/17 CS162 ©UCB Fall 2017 Lec 8.30 Semaphores Semaphores Like Integers Except •  Semaphores are like integers, except •  Semaphores are a kind of generalized lock –  No negative values –  First defined by Dijkstra in late 60s –  Only operations allowed are P and V – can’t read or write value, –  Main synchronization primitive used in original UNIX except to set it initially –  Operations must be atomic •  Definition: a Semaphore has a non-negative integer value and »  Two P’s together can’t decrement value below zero supports the following two operations: »  Similarly, thread going to sleep in P won’t miss wakeup from V – even if –  P(): an atomic operation that waits for semaphore to become positive, they both happen at same time then decrements it by 1 •  Semaphore from railway analogy »  Think of this as the wait() operation –  Here is a semaphore initialized to 2 for resource control: –  V(): an atomic operation that increments the semaphore by 1, waking up a waiting P, if any »  This of this as the signal() operation –  Note that P() stands for “proberen” (to test) and V() stands for “verhogen” (to increment) in Dutch Value=2 Value=0 Value=1 Value=2 9/20/17 CS162 ©UCB Fall 2017 Lec 8.31 9/20/17 CS162 ©UCB Fall 2017 Lec 8.32 Page 8 

9 . Two Uses of Semaphores Producer-Consumer with a Bounded Buffer Mutual Exclusion (initial value = 1) •  Also called “Binary Semaphore”. Producer Buffer Consumer •  Problem Definition •  Can be used for mutual exclusion: –  Producer puts things into a shared buffer semaphore.P(); // Critical section goes here –  Consumer takes them out semaphore.V(); –  Need synchronization to coordinate producer/consumer Scheduling Constraints (initial value = 0) •  Don’t want producer and consumer to have to work in lockstep, so •  Allow thread 1 to wait for a signal from thread 2, i.e., thread 2 put a fixed-size buffer between them schedules thread 1 when a given event occurs –  Need to synchronize access to this buffer •  Example: suppose you had to implement ThreadJoin which must –  Producer needs to wait if buffer is full wait for thread to terminate: –  Consumer needs to wait if buffer is empty Initial value of semaphore = 0 ThreadJoin { •  Example 1: GCC compiler semaphore.P(); } –  cpp | cc1 | cc2 | as | ld ThreadFinish { •  Example 2: Coke machine semaphore.V(); –  Producer can put limited number of Cokes in machine } –  Consumer can’t take Cokes out if machine is empty 9/20/17 CS162 ©UCB Fall 2017 Lec 8.33 9/20/17 CS162 ©UCB Fall 2017 Lec 8.34 Correctness constraints for solution Full Solution to Bounded Buffer •  Correctness Constraints: Semaphore fullSlots = 0; // Initially, no coke –  Consumer must wait for producer to fill buffers, if none full (scheduling Semaphore emptySlots = bufSize; constraint) // Initially, num empty slots –  Producer must wait for consumer to empty buffers, if all full (scheduling Semaphore mutex = 1; // No one using machine constraint) Producer(item) { –  Only one thread can manipulate buffer queue at a time (mutual emptySlots.P(); // Wait until space exclusion) mutex.P(); // Wait until machine free •  Remember why we need mutual exclusion Enqueue(item); mutex.V(); –  Because computers are stupid fullSlots.V(); // Tell consumers there is –  Imagine if in real life: the delivery person is filling the machine and // more coke } somebody comes up and tries to stick their money into the machine Consumer() { •  General rule of thumb: fullSlots.P(); // Check if there’s a coke Use a separate semaphore for each constraint mutex.P(); // Wait until machine free –  Semaphore fullBuffers; // consumer’s constraint item = Dequeue(); mutex.V(); –  Semaphore emptyBuffers;// producer’s constraint emptySlots.V(); // tell producer need more return item; –  Semaphore mutex; // mutual exclusion } 9/20/17 CS162 ©UCB Fall 2017 Lec 8.35 9/20/17 CS162 ©UCB Fall 2017 Lec 8.36 Page 9 

10 . Discussion about Solution Discussion about Solution (cont’d) Decrease # of Increase # of Is order of P’s important? Producer(item) { Why asymmetry? empty slots occupied slots –  Yes! Can cause deadlock mutex.P(); emptySlots.P(); •  Producer does: emptySlots.P(), fullSlots.V() Is order of V’s important? Enqueue(item); mutex.V(); •  Consumer does: fullSlots.P(), emptySlots.V() •  No, except that it might affect scheduling fullSlots.V(); Decrease # of Increase # of efficiency } occupied slots empty slots Consumer() { What if we have 2 producers or 2 fullSlots.P(); consumers? mutex.P(); item = Dequeue(); –  Do we need to change anything? mutex.V(); emptySlots.V(); return item; } 9/20/17 CS162 ©UCB Fall 2017 Lec 8.37 9/20/17 CS162 ©UCB Fall 2017 Lec 8.38 Motivation for Monitors and Condition Variables Monitor with Condition Variables •  Semaphores are a huge step up; just think of trying to do the bounded buffer with only loads and stores –  Problem is that semaphores are dual purpose: »  They are used for both mutex and scheduling constraints »  Example: the fact that flipping of P’s in bounded buffer gives deadlock is not immediately obvious. How do you prove correctness to someone? •  Cleaner idea: Use locks for mutual exclusion and condition variables •  Lock: the lock provides mutual exclusion to shared data for scheduling constraints –  Always acquire before accessing shared data structure –  Always release after finishing with shared data •  Definition: Monitor: a lock and zero or more condition variables –  Lock initially free for managing concurrent access to shared data •  Condition Variable: a queue of threads waiting for something inside a –  Some languages like Java provide this natively critical section –  Key idea: make it possible to go to sleep inside critical section by –  Most others use actual locks and condition variables atomically releasing lock at time we go to sleep –  Contrast to semaphores: Can’t wait inside critical section 9/20/17 CS162 ©UCB Fall 2017 Lec 8.39 9/20/17 CS162 ©UCB Fall 2017 Lec 8.40 Page 10 

11 . Simple Monitor Example (version 1) Condition Variables •  Here is an (infinite) synchronized queue •  How do we change the RemoveFromQueue() routine to wait until Lock lock; something is on the queue? Queue queue; –  Could do this by keeping a count of the number of things on the queue (with semaphores), but error prone AddToQueue(item) { •  Condition Variable: a queue of threads waiting for something inside a lock.Acquire(); // Lock shared data critical section queue.enqueue(item); // Add item lock.Release(); // Release Lock –  Key idea: allow sleeping inside critical section by atomically releasing } lock at time we go to sleep –  Contrast to semaphores: Can’t wait inside critical section RemoveFromQueue() { lock.Acquire(); // Lock shared data •  Operations: item = queue.dequeue();// Get next item or null –  Wait(&lock): Atomically release lock and go to sleep. Re-acquire lock.Release(); // Release Lock lock later, before returning. return(item); // Might return null } –  Signal(): Wake up one waiter, if any •  Not very interesting use of “Monitor” –  Broadcast(): Wake up all waiters –  It only uses a lock with no condition variables •  Rule: Must hold lock when doing condition variable ops! –  In Birrell paper, he says can perform signal() outside of lock – IGNORE –  Cannot put consumer to sleep if no work! HIM (this is only an optimization) 9/20/17 CS162 ©UCB Fall 2017 Lec 8.41 9/20/17 CS162 ©UCB Fall 2017 Lec 8.42 Complete Monitor Example (with condition variable) Summary (1/2) •  Here is an (infinite) synchronized queue •  Important concept: Atomic Operations Lock lock; –  An operation that runs to completion or not at all Condition dataready; Queue queue; –  These are the primitives on which to construct various synchronization primitives AddToQueue(item) { lock.Acquire(); // Get Lock queue.enqueue(item); // Add item •  Talked about hardware atomicity primitives: dataready.signal(); // Signal any waiters –  Disabling of Interrupts, test&set, swap, compare&swap, conditional lock.Release(); // Release Lock } RemoveFromQueue() { •  Showed several constructions of Locks lock.Acquire(); // Get Lock –  Must be very careful not to waste/tie up machine resources while (queue.isEmpty()) { dataready.wait(&lock); // If nothing, sleep »  Shouldn’t disable interrupts for long } »  Shouldn’t spin wait for long item = queue.dequeue(); // Get next item lock.Release(); // Release Lock –  Key idea: Separate lock variable, use hardware mechanisms to protect return(item); modifications of that variable } 9/20/17 CS162 ©UCB Fall 2017 Lec 8.43 9/20/17 CS162 ©UCB Fall 2017 Lec 8.44 Page 11 

12 . Summary (2/2) •  Semaphores: Like integers with restricted interface –  Two operations: »  P(): Wait if zero; decrement when becomes non-zero »  V(): Increment and wake a sleeping task (if exists) »  Can initialize value to any non-negative value –  Use separate semaphore for each constraint •  Monitors: A lock plus one or more condition variables –  Always acquire lock before accessing shared data –  Use condition variables to wait inside critical section »  Three Operations: Wait(), Signal(), and Broadcast() 9/20/17 CS162 ©UCB Fall 2017 Lec 8.45 Page 12