MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L21 – Processes & Synchronization 1 6.004 – Spring 20094/28/09Processes, Synchronization, & Deadlock Lab #7 due Thursday modified 4/27/09 11:15 L21 – Processes & Synchronization 2 6.004 – Spring 20094/28/09Interprocess Communication Why communicate? •Concurrency•Asynchrony•Processes as a programming primitive •Data/Event driven How to communicate? •Shared Memory(overlapping contexts)... •Supervisor calls •Synchronization instructions, (hardware support) Classic Example: “PRODUCER-CONSUMER” Problem: Real-World Examples: UNIX pipeline, Word processor/Printer Driver, Preprocessor/Compiler, Compiler/Assembler P1P2Code Stack Data Shared Data Code Stack Data PPRODUCERCCONSUMERloop:;send(c); goto loop loop:c = rcv(); ;goto loop L21 – Processes & Synchronization 3 6.004 – Spring 20094/28/09Synchronous Communication PRODUCER231send1send2send3CONSUMER1rcv12rcv23rcv3loop:;send(c); goto loop loop:c = rcv(); ;goto loop rcvisendi+1sendircvi•Can’t CONSUME data before it’s PRODUCEDPrecedence Constraints: “precedes”• Producer can’t “OVERWRITE” data before it’s consumedL21 – Processes & Synchronization 4 6.004 – Spring 20094/28/09FIFO BufferingRELAXES interprocesssynchronization constraints. Buffering relaxes the following OVERWRITE constraint to:PCN-character FIFO buffer ;send(c0);rcv(); //c0;;send(c1);rcv(); //c1;;send(c2);rcv(); //c2;;send(c3);time c0c1c2c0c1c2c0c1c2c0c1c2c3rcvisendi+Nc0c1c2c3c0c1c0c0c0Read ptr Write ptr c0“Ring Buffer:” L21 – Processes & Synchronization 5 6.004 – Spring 20094/28/09Example: Bounded Buffer Problem send(char c) { buf[in] = c; in = (in+1)% N; }char rcv() { char c; c = buf[out]; out = (out+1)% N; return c; }PRODUCER: CONSUMER: char buf[N]; /* The buffer */int in=0, out=0; SHARED MEMORY: Problem: Doesn’t enforce precedence constraints (e.g. rcv( ) could be invoked prior to any send() )L21 – Processes & Synchronization 6 6.004 – Spring 20094/28/09Semaphores (Dijkstra) Programming construct for synchronization: •NEW DATA TYPE:semaphore, integer-valued semaphore s = K;/* initialize s to K */•NEW OPERATIONS (defined on semaphores): •wait(semaphore s) stall current process if (s <= 0), otherwise s = s – 1 •signal(semaphore s) s = s + 1, (can have side effect of letting other processes proceed) •SEMANTIC GUARANTEE: A semaphore s initialized to K enforces the constraint: wait(s)i+Ksignal(s)iThis is a precedence relationship, meaning that the (i+K)thcall to wait cannot proceed before the ith call to signal completes. Often you will see P(s) used for wait(s) andV(s) used for signal(s)! P = “proberen”(test) or “pakken”(grab) V= “verhogen”(increase) L21 – Processes & Synchronization 7 6.004 – Spring 20094/28/09Semaphores for Resource Allocation ABSTRACT PROBLEM:• POOL of K resources• Many processes, each needs resource for occasional uninterrupted periods • MUST guarantee that at most K resources are in use at any time.Semaphore Solution: In shared memory: semaphore s = K; /* K resources */In each process: ... wait(s); /* Allocate one */... /* use it for a while */signal(s); /* return it to pool */... Invariant: Semaphore value = number of resources left in pool L21 – Processes & Synchronization 8 6.004 – Spring 20094/28/09Bounded Buffer Problem w/Semaphoressend(char c) { buf[in] = c; in = (in+1)%N; signal(chars); }char rcv() { char c; wait(chars); c = buf[out]; out = (out+1)%N; return c; } PRODUCER: CONSUMER: char buf[N]; /* The buffer */int in=0, out=0; semaphore chars=0; SHARED MEMORY: RESOURCE managed by semaphore: Characters in FIFO. DOES IT WORK?L21 – Processes & Synchronization 9 6.004 – Spring 20094/28/09Flow Control Problems Q: What keeps PRODUCER from putting N+1 charactersinto the N-character buffer?PCN-character FIFO buffer rcvisendi+NWHAT we still need: A: Nothing. sendircviWHAT we’ve got thus far: Result: OVERFLOW. Randomness. Havoc. Smoke. Pain. Suffering. D’s and F’s in MIT courses. L21 – Processes & Synchronization 10 6.004 – Spring 20094/28/09Bounded Buffer Problem w/^SemaphoresRESOURCEs managed by semaphore: Characters in FIFO, Spaces in FIFO send(char c) { wait(space); buf[in] = c; in = (in+1)%N; signal(chars); }char rcv() { char c; wait(chars); c = buf[out]; out = (out+1)%N; signal(space); return c; }PRODUCER: CONSUMER: char buf[N]; /* The buffer */int in=0, out=0; semaphore chars=0, space=N; SHARED MEMORY: more WORKS with single producer, consumer. But what about… L21 – Processes & Synchronization 11 6.004 – Spring 20094/28/09Simultaneous Transactions Suppose you and your friend visit the ATM at exactly the same time, and remove $50 from your account. What happens? Debit(int account, int amount) { t = balance[account]; balance[account] = t – amount; }What is supposed to happen? Debit(6004, 50) Debit(6004, 50) Process # 1Process #2 LD(R10, balance, R0) SUB(R0, R1, R0) ST(R0, balance, R10) ……LD(R10, balance, R0) SUB(R0, R1, R0) ST(R0, balance, R10) NET: You have $100, and your bank balance is $100 less. L21 – Processes & Synchronization 12 6.004 – Spring 20094/28/09But, what if… Process # 1Process #2 LD(R10, balance, R0) …LD(R10, balance, R0) SUB(R0, R1, R0) ST(R0, balance, R10) …SUB(R0, R1, R0) ST(R0, balance, R10) …NET: You have $100 and your bank balance is $50 less! We need to be careful when writing concurrent programs. In particular, when modifying shared data. For certain code segments, called CRITICAL SECTIONS, we would like to assure that no two executions overlap.This constraint is called MUTUAL EXCLUSION. Solution: embed critical sections in wrappers (e.g., “transactions”) that guarantee their atomicity, i.e. make them appear to be single, instantaneous operations.Two people at ATMs.L21 – Processes & Synchronization 13 6.004 – Spring 20094/28/09Semaphores for Mutual Exclusion …Debit(int account, int amount) {t = balance[account]; balance[account] = t – amount; }RESOURCE managed by “lock” semaphore: Access to critical section ISSUES:Granularity of lock 1 lock for whole balance database? 1 lock per account? 1 lock for all accounts ending in 004? Implementation of wait() and signal() functions “precedesorprecedes”(i.e., they don’t overlap) signal(lock); /* Finished with lock */semaphore lock = 1; wait(lock); /* Wait for exclusive access */L21 – Processes & Synchronization 14 6.004 – Spring 20094/28/09Producer/Consumer Atomicity Problems Consider multiple PRODUCER processes: P1CN-character FIFO buffer P2...buf[in] = c; in = (in+1) % N; ......buf[in] = c; in = (in+1) % N; ...P1P2BUG: Producers interfere with each other. L21 – Processes & Synchronization 15 6.004 – Spring 20094/28/09Bounded Buffer Problem w/^Semaphoressend(char c) { wait(space); wait(mutex); buf[in] = c; in = (in+1)%N; signal(mutex); signal(chars); }char rcv() { char c; wait(chars); wait(mutex); c = buf[out]; out = (out+1)%N; signal(mutex); signal(space); return c; } PRODUCER: CONSUMER: char buf[N]; /* The buffer */int in=0, out=0; semaphore chars=0, space=N; semaphore mutex=1; SHARED MEMORY: even more L21 – Processes & Synchronization 16 6.004 – Spring 20094/28/09The Power of Semaphores send(char c) { wait(space); wait(mutex) buf[in] = c; in = (in+1)%N; signal(mutex); signal(chars); }char rcv() { char c; wait(chars); wait(mutex); c = buf[out]; out = (out+1)%N; signal(mutex); signal(space); return c; } PRODUCER: CONSUMER: char buf[N]; /* The buffer */int in=0, out=0; semaphore chars=0, space=N; semaphore mutex=1; SHARED MEMORY: A single synchronization primitive that enforces both: Precedence relationships: sendircvircvisendi+NMutual-exclusionrelationships: protect variablesin and outL21 – Processes & Synchronization 17 6.004 – Spring 20094/28/09Semaphore Implementations Semaphore implementation must address a basic arbitration problem: how to choose among simultaneously waiting processes when a signal occurs. This involves some basic atomicity assumption in the implementation technology. Approaches:•SVC implementation, using atomicity of kernel handlers. Works in timeshared processor sharing a single uninterruptable kernel. •Implementation by a special instruction (e.g. “test and set”), using atomicity of single instruction execution. Works with shared-bus multiprocessors supporting atomic read-modify-write bus transactions.•Implementation using atomicity of individual read or write operations.Complex, clever, 2-phase scheme devised by Dijkstra. Unused in practice.Bootstrapping: A simple lock (“binary semaphore”) allows easy implementation of full semaphore support. L21 – Processes & Synchronization 18 6.004 – Spring 20094/28/09Semaphores as Supervisor Call wait_h( ) {int *addr; addr = User.Regs[R0]; /* get arg */if (*addr <= 0) { User.Regs[XP] = User.Regs[XP] – 4; sleep(addr); } else *addr = *addr -1; }signal_h( ) {int *addr; addr = User.Regs[R0]; /* get arg */*addr = *addr + 1; wakeup(addr);}Calling sequence: …|| put address of lock || into R0 CMOVE(lock, R0) SVC(WAIT)SVC call is not interruptible since it is executed in supervisory mode. L21 – Processes & Synchronization 19 6.004 – Spring 20094/28/09Atomicity Guaranteed, e.g. by Bus protocols H/W support for Semaphores TCLR(RA, literal, RC)test and clear location PCPC + 4EAReg[Ra] + literal Reg[Rc]MEM[EA] MEM[EA]0 Executed ATOMICALLY (cannot be interrupted) Can easily implement mutual exclusion using binary semaphore wait:TCLR(R31, lock, R0) BEQ(R0,wait)… critical section … CMOVE(1,R0)ST(R0, lock, R31) wait(lock) signal(lock) L21 – Processes & Synchronization 20 6.004 – Spring 20094/28/09Synchronization: The Dark Side The indiscriminate use of synchronization constraints canintroduce its own set of problems, particularly when a process requires access to more than one protected resource. Transfer(int account1, int account2, int amount) {wait(lock[account1]);wait(lock[account2]);balance[account1] = balance[account1] -amount; balance[account2] = balance[account2] + amount; signal(lock[account2]);signal(lock[account1]);}Transfer(6004, 6001, 50) Transfer(6001, 6004, 50) DEAD-LOCK! Two people at ATMs.L21 – Processes & Synchronization 21 6.004 – Spring 20094/28/09Famous Toy Problem:Dining Philosophers •Take (wait for) LEFT stick•Take (wait for) RIGHT stick•EAT until sated•Replace both sticksPHILOSOPHER'S ALGORITHM:Philosophers think deep thoughts, but have simple secular needs. When hungry, a group of N philosophers will sit around a table with N chopsticks interspersed between them. Food is served, and each philosopher enjoys a leisurely meal using the chopsticks on either side to eat (2 sticks are required, to avoid an ancient Zen paradox about the sound of one stick feeding). They are exceedingly polite and patient, and each follows the following dining protocol: L21 – Processes & Synchronization 22 6.004 – Spring 20094/28/09Deadlock!CONDITIONS: 1)Mutual exclusion -only one process can hold a resource at a given time 2) Hold-and-wait -a process holds allocated resources while waiting for others 3) No preemption -a resource can not be removed from a process holding it 4) Circular Wait SOLUTIONS: Avoidance -or-Detection and Recovery No one can make progress because they are all waiting for an unavailable resource L21 – Processes & Synchronization 23 6.004 – Spring 20094/28/09One Solution •Take LOW stick•Take HIGH stick•EAT•Replace both sticks.KEY: Assign a unique number to each chopstick, request resources in globally consistent order:New Algorithm: SIMPLE PROOF: Deadlock means that each philosopher is waiting for a resource held by some other philosopher … But, the philosopher holding the highest numbered chopstick can’t be waiting for any other philosopher (no hold-and-wait) … Thus, there can be no deadlock L21 – Processes & Synchronization 24 6.004 – Spring 20094/28/09Dealing with Deadlocks Cooperating processes: •Establish a fixed ordering to shared resources and require all requests to be made in the prescribed order Transfer(int account1, int account2, int amount) {int a, b; if (account1 > account2) { a = account1; b = account2; } else {a = account2; b = account1; } wait(lock[a]);wait(lock[b]);balance[account1] = balance[account1] -amount; balance[account2] = balance[account2] + amount; signal(lock[b]);signal(lock[a]);}Unconstrained processes: -O/S discovers circular wait & kills waiting process -Transaction model -Hard problem Transfer(6004, 6001, 50) Transfer(6001, 6004, 50) Drawing of five people sitting at a table. There are chopsticks on the in which each person has picked up one chopstick, so no can eat.chopstick is labeled with number.Figure by MIT OpenCourseWare. Figure by MIT OpenCourseWare. Figure by MIT OpenCourseWare. Two ATMs.L21 – Processes & Synchronization 25 6.004 – Spring 20094/28/09SummaryCommunication among asynchronous processes requires synchronization….•Precedence constraints: a partial ordering among operations •Semaphores as a mechanism for enforcing precedence constraints•Mutual exclusion (critical sections, atomic transactions) as a common compound precedence constraint •Solving Mutual Exclusion via binary semaphores •Synchronizationserializes operations, limits parallel execution. Many alternative synchronization mechanisms exist! Deadlocks:•Consequence of undisciplined use of synchronization mechanism •Can be avoided in special cases, detected and corrected in others.