Chapter 2Chapter 2: Processes & ThreadsPart 2Interprocess Communication (IPC) &SynchronizationChapter 22CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)WhydoweneedIPC? 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 multipleprocesses 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 processesshare storage (memory) Both may read and writethe shared memory Problem: can’t guaranteethat read followed by writeis atomic Ordering matters! This can result in erroneousresults! We need to eliminate raceconditions…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 Notwoprocessessimultaneouslyincriticalregion 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 BBblockedA 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 canproceed This is called a spin lock because the waiting process “spins” in a tightloop reading the variable Avoids race conditions, but doesn’t satisfy criterion 3 forcritical 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 processinterested[process] = TRUE; // show interestturn = process; // Set it to my turnwhile (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)intn;//# ofprocessesintchoosing[n];intnum ber[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 processchoosing[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 ourswhile ((number[j] != 0) &&((number[j] < number[i]) ||((number[j] == number[i]) && (j < i))));}// critical sectionnumber[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 forsomething 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 unlessit 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));//criticalsectionlock = 0;//rem ainderofcode}Code for process Piwhile(1){while(Swap(lock,1)== 1);//criticalsectionlock = 0;//rem ainderofcode}intlock = 0;Mutual exclusion using hardware Single shared variable lock Still requires busy waiting,but code is much simpler Two versions Test and set Swap Works for any number ofprocesses Possible problem withrequirements Non-concurrent code can leadto unbounded waitingChapter 212CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Eliminating busy waiting Problem: previous solutions waste CPU time Both hardware and software solutions require spin locks Allow processes to sleep while they wait to execute their criticalsections Problem: priority inversion (higher priority process waits forlower priority process) Solution: use semaphores Synchronization mechanism that doesn’t require busy waiting Implementation Semaphore S accessed by two atomic operations Down(S): while (S<=0) {}; S-= 1; Up(S): S+=1; Down() is another name for P() Up() is another name for V() Modify implementation to eliminate busy wait from Down()Chapter 213CS 1550, cs.pitt.edu (originaly modified by Ethan L. Miller and Scott A. Brandt)Critical sections using semaphoresCode for process Piwhile(1){dow