Chapter 6.2: Process Synchronization Part 2Module 6: Process SynchronizationTest And Set InstructionMutual Exclusion via TestAndSet()Swap() – can provide mutual exclusion too…How about Bounded-Wait Time?Finishing Up Hardware InstructionsSemaphoreSemaphore as General Synchronization ToolCounting SemaphoresSemaphore ImplementationSemaphore Implementation with no Busy WaitingSemaphore Implementation with no Busy WaitingSemaphore Implementation with no Busy waiting (Cont.)Slide 15More – The System Calls and the QueueSingle and Multiple Processor IssuesDeadlock and StarvationClassical Problems of SynchronizationBounded-Buffer ProblemBounded Buffer Problem (Cont.)Slide 22End of Chapter 6 Part 2Chapter 6.2: Process SynchronizationChapter 6.2: Process SynchronizationPart 2Part 26.2Silberschatz, Galvin and Gagne ©2005Operating System ConceptsModule 6: Process SynchronizationModule 6: Process SynchronizationLecture 6.1BackgroundThe Critical-Section ProblemPeterson’s SolutionSynchronization HardwareLecture 6.2:SemaphoresClassic Problems of SynchronizationLecture 6.3: MonitorsSynchronization Examples Atomic Transactions6.3Silberschatz, Galvin and Gagne ©2005Operating System ConceptsTest And Set Instruction Test And Set Instruction Definition: Here’s the Test and Set Instruction…It is executed atomically. Consider the code: boolean TestAndSet (boolean *target) { boolean rv = *target; // rv set to the value of target *target = TRUE; // target set to TRUE return rv: // value passed to TEstAndSet() returned }// via rv.We will see how this is used (implemented) on the next slide…But you can see that a pointer value (dereferenced) ‘to something’ is passed to TestAndSet; a boolean variable rv is set to the pointer’s value. The dereferenced value of the actual parameter is set to TRUE, and we return this boolean value of rv which will be whatever was passed to TestAndSet(). Note: TestAndSet() returns a boolean value passed to it, but it sets the global variable to TRUE.6.4Silberschatz, Galvin and Gagne ©2005Operating System ConceptsMutual Exclusion via TestAndSet()But we implement the mutual exclusion shown by TestAndSet() by using a global boolean lock as the parameter and it is initially set to false.Consider:do {while (TestAndSetLock (&lock)) ; // do nothing// if lock is false (see above) , value of predicate is false (but remember // lock itself was set to TRUE), and we drop into critical section; // if TestAndSet() returns ‘true’ (which it would if another process // was already executing its critical section) , do nothing; Spin… // critical section lock = FALSE; // reset global variable as part of this ‘instruction.’ // remainder section} while (TRUE);Remember, TestAndSet() is atomic, the routine above includes TestAndSet() but theoverall execution is NOT atomic (only the TestAndSet() part). Let’s look at another hardware instruction that uses two variables: a lock and a key.6.5Silberschatz, Galvin and Gagne ©2005Operating System ConceptsSwap() – can provide mutual exclusion too… This hardware approach deals with two words and is also executed atomically.For machines that support a swap() instruction (remember, this is a hardware instruction), we can provide mutual exclusion as seen in the code below: // lock is a global Boolean variable initially declared to be FALSE. // Also, each process has a local Boolean variable key. do{ key = TRUE;while (key == TRUE) // recall: lock is global and declared to be FALSE. Swap (&lock, &key); (Invoke swap() - in book and quite standard…) // this swap() will set lock to TRUE and key to FALSE.// // So ‘if’ some other process could tries this code,.. Key ‘starts off’ in this other process to TRUE.. But lock is TRUE from ‘this’ process execution...// the Swap (note lock is global) both would be False and// So both key and lock = FALSE in this new, trying code, and // there is no entry to the critical section…// Note: since SWAP is atomic, if this original routine ‘has’ // lock; no other routine has it and cannot thus change it…// the while loop will essentially be a busy waiting for the other// process to finish up set lock to False. // critical section lock = FALSE // can see this resets the lock to FALSE // remainder section } while (TRUE);6.6Silberschatz, Galvin and Gagne ©2005Operating System ConceptsHow about Bounded-Wait Time?Both of these algorithms satisfy the mutual exclusion need but neither satisfies the bounded waiting time need, which says that the requesting code will be executed after a finite wait time.Note the ‘bounded waiting time’ need refers to the fact that there needs to be some kind of limit on the number of times that other processes are allowed to enter their critical sections after a different process has made a request to enter its critical section.Equivalently, a process needing to enter its critical section cannot be denied forever. This algorithm is presented as the Bounded-waiting Mutual Exclusion with TestAndSet() implemented a bit differently. (Figure 6.8)Recommend you plow through this to understand the code…6.7Silberschatz, Galvin and Gagne ©2005Operating System ConceptsFinishing Up Hardware InstructionsSo the last algorithm covers the bounded wait time and mutual exclusion. The key is how one implements these hardware instructions. Implementing the TestAndSet() instructions on multiple processors is not easy.Your book does not cover the details, but note that because the instructions are atomic (and this is the key) the real implementation of these instructions requires (likely) a carefully architected number of microinstructions, assuming the control unit of the CPU is micro-coded….Regardless, the instruction is burned into the hardware – silicon. Let’s now turn our attention to how Critical Sections can be handled in software.We will introduce the concept of a semaphore.6.8Silberschatz, Galvin and Gagne ©2005Operating System ConceptsSemaphoreSemaphoreA semaphore is merely an integer variable that can be binary (have values 0 or 1) or be a counting semaphore (have integer values – generally positive, but not always).Bear in mind that semaphores are used to control access to shared variables and shared resources and to