Slide 1Issues in ConcurrencyPrinciples of Concurrency...Concurrency (contd.)SemaphoresCritical Section of n ProcessesSemaphore ImplementationSemantics of wait and signalSemaphores for CSTwo Types of SemaphoresSemaphore for SynchronizationClassical Problems of SynchronizationProducer/Consumer problemSolution for P/C using SemaphoresP/C: improved solutionP/C problem: Bounded bufferP/C: Bounded Buffer solutionSemaphores - commentsB . R A M A M U R T H YCritical Section and Critical ResourcesIssues in ConcurrencyConcurrent processes /threads help in improving performanceHowever when they share resources, it is required that the access to the resource is protected from inconsistency and incorrect states.These shared resources are called critical resources and the code accessing the resource is called the critical section.The access to the resource needs to be mutually exclusive among concurrent processes.Semaphores are kernel level primitives to help implement mutual exclusion.01/14/2019Page 3Principles of ConcurrencyInterleaving and overlapping the execution of processes.Consider two processes P1 and P2 executing the function echo:{ input (in, keyboard); out = in; output (out, display);}01/14/2019Page 4...Concurrency (contd.)P1 invokes echo, after it inputs into in , gets interrupted (switched). P2 invokes echo, inputs into in and completes the execution and exits. When P1 returns in is overwritten and gone. Result: first ch is lost and second ch is written twice.This type of situation is even more probable in multiprocessing systems where real concurrency is realizable thru’ multiple processes executing on multiple processors.Solution: Controlled access to shared resourceProtect the shared resource : in buffer; “critical resource”one process/shared code. “critical region”Semaphores 01/14/2019Page 5Semaphore is kernel level primitive for realizing mutual exclusion.Attributes: semaphore value, Operations on semaphore: init, wait, signalConsidered an kernel resource, a limited number available: a limited number of instances (objects) of semaphore is allowed.Can easily implement mutual exclusion among any number of processes.Can also be used for synchronization.Critical Section of n Processes01/14/2019Page 6Shared data: Semaphore mutex; //initially mutex = 1Process Pi: do { mutex.wait(); critical section mutex.signal(); remainder section} while (1);Semaphore Implementation01/14/2019Page 7Define a semaphore as a class:class Semaphore{ int value; // semaphore value ProcessQueue L; // process queue //operationswait()signal()}In addition, two simple utility operations:block() suspends the process that invokes it.Wakeup() resumes the execution of a blocked process P.Semantics of wait and signal01/14/2019Page 8Semaphore operations now defined as S.wait():S.value--;if (S.value < 0) { add this process to S.L;block(); // block a process}S.signal(): S.value++;if (S.value <= 0) {remove a process P from S.L;wakeup(); // wake a process}Semaphores for CS01/14/2019Page 9Semaphore is initialized to 1. The first process that executes a wait() will be able to immediately enter the critical section (CS). (S.wait() makes S value zero.) Now other processes wanting to enter the CS will each execute the wait() thus decrementing the value of S, and will get blocked on S. (If at any time value of S is negative, its absolute value gives the number of processes waiting blocked. )When a process in CS departs, it executes S.signal() which increments the value of S, and will wake up any one of the processes blocked. The queue could be FIFO or priority queue.Two Types of Semaphores01/14/2019Page 10Counting semaphore – integer value can range over an unrestricted domain.Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement. ex: nachosCan implement a counting semaphore using a binary semaphore.Semaphore for Synchronization01/14/2019Page 11Execute B in Pj only after A executed in PiUse semaphore flag initialized to 0Code:PiPj A flag.wait()flag.signal() BClassical Problems of Synchronization01/14/2019Page 12Bounded-Buffer ProblemReaders and Writers ProblemDining-Philosophers ProblemProducer/Consumer problem01/14/2019Page 13Producerrepeatproduce item v;b[in] = v;in = in + 1;forever;Consumerrepeatwhile (in <= out) nop;w = b[out];out = out + 1;consume w;forever;Solution for P/C using Semaphores 01/14/2019Page 14Producerrepeatproduce item v;MUTEX.wait();b[in] = v;in = in + 1;MUTEX.signal();forever;What if Producer is slow or late?Consumerrepeatwhile (in <= out) nop;MUTEX.wait();w = b[out];out = out + 1;MUTEX.signal();consume w;forever;Ans: Consumer will busy-wait at the while statement.P/C: improved solution 01/14/2019Page 15Producerrepeatproduce item v;MUTEX.wait();b[in] = v;in = in + 1;MUTEX.signal();AVAIL.signal();forever;What will be the initial values of MUTEX and AVAIL?ConsumerrepeatAVAIL.wait();MUTEX.wait();w = b[out];out = out + 1;MUTEX.signal();consume w;forever;ANS: Initially MUTEX = 1, AVAIL = 0.P/C problem: Bounded buffer01/14/2019Page 16Producerrepeatproduce item v;while((in+1)%n == out) NOP;b[in] = v;in = ( in + 1)% n;forever;How to enforce bufsize?Consumerrepeatwhile (in == out) NOP;w = b[out];out = (out + 1)%n;consume w;forever;ANS: Using another counting semaphore.P/C: Bounded Buffer solution01/14/2019Page 17Producerrepeatproduce item v;BUFSIZE.wait();MUTEX.wait();b[in] = v;in = (in + 1)%n;MUTEX.signal();AVAIL.signal();forever;What is the initial value of BUFSIZE?ConsumerrepeatAVAIL.wait();MUTEX.wait();w = b[out];out = (out + 1)%n;MUTEX.signal();BUFSIZE.signal();consume w;forever;ANS: size of the bounded buffer.Semaphores - comments01/14/2019Page 18Intuitively easy to use.wait() and signal() are to be implemented as atomic operations.Difficulties: signal() and wait() may be exchanged inadvertently by the programmer. This may result in deadlock or violation of mutual exclusion.signal() and wait() may be left out.Related wait() and signal() may be scattered all over the code among the
View Full Document
Unlocking...