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 sequentiallyAll is fine until processes want to share dataExchange data between multiple processesAllow processes to navigate critical regionsMaintain proper sequencing of actions in multiple processesThese issues apply to threads as wellThreads 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 conditionsCooperating processes share storage (memory)Both may read and write the shared memoryProblem: can’t guarantee that read followed by write is atomicOrdering 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 regionsUse critical regions to provide mutual exclusion and help fix race conditionsFour conditions to provide mutual exclusionNo two processes simultaneously in critical regionNo assumptions made about speeds or numbers of CPUsNo process running outside its critical region may block another processNo 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 alternationUse a shared variable (turn) to keep track of whose turn it isWaiting process continually reads the variable to see if it can proceedThis is called a spin lock because the waiting process “spins” in a tight loop reading the variableAvoids 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 processesNotation 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 IShared datachoosing initialized to 0number 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 synchronizationPrior methods work, but…May be somewhat complexRequire busy waiting: process spins in a loop waiting for something to happen, wasting CPU timeSolution: use hardwareSeveral hardware methodsTest & set: test a variable and set it in one instructionAtomic swap: switch register & memory in one instructionTurn 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 hardwareSingle shared variable lockStill
View Full Document