Chapter 2: Processes & ThreadsWhy do we need IPC?Example: bounded buffer problemProblem: race conditionsCritical regionsBusy waiting: strict alternationBusy waiting: working solutionBakery algorithm for many processesBakery algorithm: codeHardware for synchronizationMutual exclusion using hardwareEliminating busy waitingCritical sections using semaphoresImplementing semaphores with blockingSemaphores for general synchronizationTypes of semaphoresMonitorsMonitor usageCondition variables in monitorsMonitor semanticsLocks & condition variablesImplementing locks with semaphoresImplementing condition variablesMessage passingBarriersDeadlock and starvationClassical synchronization problemsBounded buffer problemReaders-writers problemDining PhilosophersDining Philosophers: solution 1Dining Philosophers: solution 2Dining philosophers with locksThe Sleepy Barber ProblemCode for the Sleepy Barber ProblemChapter 2Chapter 2: Processes & ThreadsPart 2Interprocess Communication (IPC) & SynchronizationChapter 22CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Why do we need IPC?Each process operates sequentiallyAll is fine until processes want to share dataExchange data between multiple processesAllow processes to navigate critical regionsMaintain proper sequencing of actions in multiple processesThese issues apply to threads as wellThreads can share data easily (same address space)Other two issues apply to threadsChapter 23CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Shared variablesconst int n;typedef … Item;Item buffer[n];int in = 0, out = 0, counter = 0;Atomic statements:Counter += 1;Counter -= 1;ConsumerItem citm;while (1) { while (counter == 0) ; citm = buffer[out]; out = (out+1) % n; counter -= 1; … consume the item in citm …}ProducerItem pitm;while (1) { … produce an item into pitm … while (counter == n) ; buffer[in] = pitm; in = (in+1) % n; counter += 1;}Example: bounded buffer problemChapter 24CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Problem: race conditionsCooperating processes share storage (memory)Both may read and write the shared memoryProblem: can’t guarantee that read followed by write is atomicOrdering matters!This can result in erroneous results!We need to eliminate race conditions…R1 <= xR1 = R1+1R1 => xR3 <= xR3 = R3+1R3 => xP1 P2x=3x=5R1 <= xR1 = R1+1R1 => xR3 <= xR3 = R3+1R3 => xx=6!Chapter 25CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Critical regionsUse critical regions to provide mutual exclusion and help fix race conditionsFour conditions to provide mutual exclusionNo two processes simultaneously in critical regionNo assumptions made about speeds or numbers of CPUsNo process running outside its critical region may block another processNo process must wait forever to enter its critical regionProcess AProcess BB blockedA enterscritical regionB tries to entercritical regionB enterscritical regionA leavescritical regionB leavescritical regionTimeChapter 26CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Busy waiting: strict alternationUse a shared variable (turn) to keep track of whose turn it isWaiting process continually reads the variable to see if it can proceedThis is called a spin lock because the waiting process “spins” in a tight loop reading the variableAvoids race conditions, but doesn’t satisfy criterion 3 for critical regionswhile (TRUE) { while (turn != 0) ; /* loop */ critical_region (); turn = 1; noncritical_region ();}while (TRUE) { while (turn != 1) ; /* loop */ critical_region (); turn = 0; noncritical_region ();}Process 0Process 1Chapter 27CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Busy waiting: working solution#define FALSE 0#define TRUE 1#define N 2 // # of processesint turn; // Whose turn is it?int interested[N]; // Set to 1 if process j is interestedvoid enter_region(int process){ int other = 1-process; // # of the other process interested[process] = TRUE; // show interest turn = process; // Set it to my turn while (turn==process && interested[other]==TRUE) ; // Wait while the other process runs}void leave_region (int process){ interested[process] = FALSE; // I’m no longer interested}Chapter 28CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)int n; // # of processesint choosing[n];int number[n];Bakery algorithm for many processesNotation used<<< is lexicographical order on (ticket#, process ID)(a,b) <<< (c,d) if (a<c) or ((a==c) and (b<d))Max(a0,a1,…,an-1) is a number k such that k>=ai for all IShared datachoosing initialized to 0number initialized to 0Chapter 29CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Bakery algorithm: codewhile (1) { // i is the number of the current process choosing[i] = 1; number[i] = max(number[0],number[1],…,number[n-1]) + 1; choosing[i] = 0; for (j = 0; j < n; j++) { while (choosing[j]) // wait while j is choosing a ; // number // Wait while j wants to enter and has a better number // than we do. In case of a tie, allow j to go if // its process ID is lower than ours while ((number[j] != 0) && ((number[j] < number[i]) || ((number[j] == number[i]) && (j < i)))) ; } // critical section number[i] = 0; // rest of code}Chapter 210CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Hardware for synchronizationPrior methods work, but…May be somewhat complexRequire busy waiting: process spins in a loop waiting for something to happen, wasting CPU timeSolution: use hardwareSeveral hardware methodsTest & set: test a variable and set it in one instructionAtomic swap: switch register & memory in one instructionTurn off interrupts: process won’t be switched out unless it asks to be suspendedChapter 211CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Code for process Piwhile (1) { while (TestAndSet(lock)) ; // critical section lock = 0; // remainder of code}Code for process Piwhile (1) { while (Swap(lock,1) == 1) ; // critical section lock = 0; // remainder of code}int lock = 0;Mutual exclusion using hardwareSingle shared variable lockStill