1CSE 380Computer Operating SystemsInstructor: Insup LeeUniversity of PennsylvaniaFall 2003Lecture 2.4: Interprocess Communication2Communicating Processesq Many applications require processes tocommunicate and synchronize with each otherq Main problem: operations of differentprocesses are interleaved in anunpredictable mannerq Same issues in multiple contextsß Multiple threads of same process accessing shared dataß Kernel processes accessing shared data structuresß User processes communicating via shared filesß User processes communicating via shared objects in kernel spaceß High-level programming languages supporting parallelismß Database transactions3Example: Shared variable problemq Two processes are each reading characters typed attheir respective terminalsq Want to keep a running count of total number ofcharacters typed on both terminalsq A shared variable V is introduced; each time acharacter is typed, a process uses the code:V := V + 1;to update the count.q During testing it is observed that the count recorded inV is less than the actual number of characters typed.What happened?4Analysis of the problemThe programmer failed to realize that the assignmentwas not executed as a single indivisible action, butrather as an arbitrary shuffle of following sequencesof instructions: P1. MOVE V, r0 Q1. MOVE V,r1 P2. INCR r0 Q2. INCR r1 P3. MOVE r0, V Q3. MOVE r1,VThe interleaving P1, Q1, P2, Q2, P3, Q3 increments V only by 15Sample Questioninterleave () { pthread_t th0, th1; int count=0; pthread_create(&th0,0,test,0); pthread_create(&th1,0,test,0); pthread_join(th0,0); pthread_join(th1,0); printf(count);}test () { for (int j=0; j<MAX; j++) count=count+1;}What’s minimum/ maximum value output?6Sample Questionint count = 0; /* global var */interleave () { pthread_t th0, th1; pthread_create(&th0,0,test,0); pthread_create(&th1,0,test,0); pthread_join(th0,0); pthread_join(th1,0); printf(count);}test () { for (int j=0; j<MAX; j++) count=count+1;}Maximum: 2 MAX, Minimum 2For Minimum, consider the sequence:Both threads read count as 0th0 increments count MAX-1 timesth1 writes 1th0, in its last iteration, reads count=1th1 finishes all its iterationsth0 writes 2 to count and ends7The Producer/Consumer Problem• from time to time, the producer places an item in the buffer• the consumer removes an item from the buffer• careful synchronization required• the consumer must wait if the buffer empty• the producer must wait if the buffer full• typical solution would involve a shared variable count• also known as the Bounded Buffer problem• Example: in UNIX shell eqn myfile.t | troffproducerprocessconsumerprocessPbufferC8Push and Pop examplestruct stacknode { int data; struct stacknode *nextptr;};typedef struct stacknode STACKNODE;typedef STACKNODE *STACKNODEPTR;void push (STACKNODEPTR *topptr, int info){ STACKNODEPTR newptr; newptr = malloc (sizeof (STACKNODE)); newptr->date = info; /* Push 1 */ newptr->nextptr = *topptr; /* Push 2 */ *topptr = newptr; /* Push 3 */}9Popint pop (STACKNODEPTR *topptr){ STACKNODEPTR tempptr; int popvalue; tempptr = *topptr; /* Pop 1 */ popvalue = (*topptr)->data; /* Pop 2 */ *topptr = (*topptr)->nextptr; /* Pop 3 */ free(tempptr); return popvalue;}Question: Is it possible to find an interleaved executionof Push 1, Push 2, …, Pop 3 such that the resultingdata structure becomes inconsistent?10Issues in Concurrent Programmingq Operations on shared data structures typically correspond toa sequence of instructionsq When two processes/threads are executing concurrently, theresult depends on the precise interleaving of the twoinstruction streams (this is called race condition)q Race conditions could cause bugs which are hard toreproduceq Besides race condition, the second issue is synchronization(one process is waiting for the results computed by another)ß Can we avoid busy waiting?11Overview of SolutionsLow-level (for mutual exclusion)Interrupt disablingUsing read/write instructionsUsing powerful instructions (Test-and-set, Compare-and Swap…)OS-level support (mutual exclusion and synchronization)Special variables: Semaphores, MutexesMessage passing primitives (send and receive)High-level Synchronization PrimitivesMonitors (Hoare, Brinch-Hansen)Synchronized method in JavaIdealized Problems Producer-Consumer Dining Philosophers Readers-Writers12Mutual Exclusion Problemq Motivation: Race conditions can lead to undesirable effectsq Solution:ß Identify a block of instructions involving shared memory accessthat should be executed without interference from othersß This block of code is called critical region/section (e.g., theentire assignment “V:=V+1” in our first example)ß Ensure that processes execute respective critical sections in amutually exclusive mannerq Mutual exclusion is required in multiple contexts wheresimultaneous access to shared data needs to enforceintegrity constraints (e.g., airline reservation system)13Requirements for solutions to MutualExclusion Problem1. Safety: No two processes should be simultaneously in theircritical regions2. Generality: No assumptions should be made about speedsor numbers of CPUs (i.e., it should work in the worst casescenario)3. Absence of deadlocks: Should not reach a state whereeach process is waiting for the other, and nobody gets toenter4. Bounded liveness (or fairness): If a process wants toenter a critical section then it should eventually get a chance14Low-level solution: Disable interruptsprocess A process B ... ... disable interrupts disable interrupts CS CS enable interrupts enable interruptsß Prevents context-switch during execution of CSß Recall maskable interrupts in Pentium architectureß This is sometimes necessary (to prevent further interruptsduring interrupt handling)ß Not a good solution for user programs (too powerful and notflexible)15Shared Variable SolutionsGeneral SkeletonTwo processes with shared variablesAssumption: Reads and Writes are atomicEach process P0 and P1 executes /* Initialization */ while (TRUE) { /* entry code */ CS() /* critical section */ /* exit code */ Non_CS()/* non-critical section */ }No assumption about how oftenthe critical section is accessedWrapper code16Using mutual exclusionint count=0, turn=0; /* global vars */bool flag[1]=false; /* global array */interleave () { pthread_t