CSE 380 Computer Operating SystemsCommunicating ProcessesExample: Shared variable problemAnalysis of the problemSample QuestionSlide 6The Producer/Consumer ProblemPush and Pop examplePopIssues in Concurrent ProgrammingOverview of SolutionsMutual Exclusion ProblemRequirements for solutions to Mutual Exclusion ProblemLow-level solution: Disable interruptsShared Variable Solutions General SkeletonUsing mutual exclusionProof of Mutual Exclusion1st Attempt for Mutual exclusion2nd Attempt3rd AttemptPeterson’s SolutionHardware Supported SolutionHardware InstructionsLocksPropertiesHow to implement locksSolution using TSLSlide 28Avoiding WaitingSleep/wakeup Solution to Producer-Consumer ProblemProblematic ScenarioDijkstra’s SemaphoresMutual Exclusion using SemaphoresPotential ImplementationThe Producer-Consumer ProblemSlide 36POSIX Semaphore System CallsRoadmapDining PhilosophersThe Dining Philosopher ProblemNumber of possible statesNumber of possible behaviorsThe Readers and Writers ProblemA Solution to the R/W problemReaders and Writers ProblemSlide 46Slide 47MonitorsTraffic SynchronizationMonitor-based SolutionSummary of IPC1CSE 380Computer Operating SystemsInstructor: Insup LeeUniversity of PennsylvaniaFall 2003Lecture 2.4: Interprocess Communication2Communicating ProcessesMany applications require processes to communicate and synchronize with each otherMain problem: operations of different processes are interleaved in an unpredictable manner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 problemTwo processes are each reading characters typed at their respective terminalsWant to keep a running count of total number of characters typed on both terminalsA shared variable V is introduced; each time a character is typed, a process uses the code:V := V + 1;to update the count. During testing it is observed that the count recorded in V is less than the actual number of characters typed. What happened?4Analysis of the problemThe programmer failed to realize that the assignment was not executed as a single indivisible action, but rather as an arbitrary shuffle of following sequences of 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 execution of Push 1, Push 2, …, Pop 3 such that the resulting data structure becomes inconsistent?10Issues in Concurrent ProgrammingOperations on shared data structures typically correspond to a sequence of instructionsWhen two processes/threads are executing concurrently, the result depends on the precise interleaving of the two instruction streams (this is called race condition)Race conditions could cause bugs which are hard to reproduce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 ProblemMotivation: Race conditions can lead to undesirable effectsSolution: Identify a block of instructions involving shared memory access that should be executed without interference from othersThis block of code is called critical region/section (e.g., the entire assignment “V:=V+1” in our first example)Ensure that processes execute respective critical sections in a mutually exclusive mannerMutual exclusion is required in multiple contexts where simultaneous access to shared data needs to enforce integrity constraints (e.g., airline reservation system)13Requirements for solutions to Mutual Exclusion Problem1. Safety: No two processes should be simultaneously in their critical regions2. Generality: No assumptions should be made about speeds or numbers of CPUs (i.e., it should work in the worst case scenario)3. Absence of deadlocks: Should not reach a state where