Enforcing Mutual Exclusion SemaphoresMutual Exclusion Requirements Mutually exclusive access to critical section Progress. If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. Bounded Waiting. A bound must exist on the # of times that other processes are allowed to enter their critical sections after a process has requested to enter its critical section and before that request is granted. Assume each process executes at a nonzero speed No assumption concerning relative speed of n processes.2Enforcing Mutual Exclusionfuntion(){<non-critical section>enter_critical_section();<critical section>exit_critical_section();<remainder section>}3Four different approaches Hardware support Software-defined approaches Support from the OS Support from the programming language4OS support: Semaphores Synchronization tool that does not require busy waiting Two or more processes can cooperate with each other by means of simple signals Integer variable accessible via two indivisible (atomic) operations : wait(s): s = s - 1, if s < 0 then block thread on the semaphore queue (wait) signal(s): s = s + 1, if s <= 0 then wake one sleeping process (signal).5Intro to Semaphores One other operation: initialized to a non-negative integer If a process is waiting on a signal, it is blocked until that signal is received Each Semaphore has an associated queue If FIFO queue then strong semaphore Prevents starvation6Mutual Exclusion Using Semaphores Shared data:semaphore mutex; //initially mutex = 1 binarysemaphore Process Pi: do {wait(mutex);critical sectionsignal(mutex);remainder section} while (1);7Semaphore Implementation Define a semaphore as a recordtypedef struct {int value;struct process *L;} semaphore; Assume two simple operations: wait(S) may suspends the process that invokes it signal(S) resumes the execution of a blocked process P8Implementationwait(S):S.value--;if (S.value < 0) { add this process to S.L;block;}signal(S): S.value++;if (S.value <= 0) {remove a process P from S.L;wakeup(P);}9Allowing multiple Critical Sections Counting semaphores s.count >= 0 - # of processes that can execute semWait(s) without blocking Assumption: no semSignal(s) executed Each can enter its critical section. s.count < 0 - # of processes blocked on s These suspended processes are in s.queue10Classical Synchronization Problems Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem11Producer/Consumer Problem Bounded-Buffer Problem One or more producers are generating data and placing these in a buffer A single consumer is taking items out of the buffer one at time Only one producer or consumer may access the buffer at any one time12Producer/Consumer Problem Infinite buffer – no overflow Finite buffer - overflow Empty buffer – consumer must be stopped Mutual exclusion and synchronization13Producer Processwhile (true) {/* produce item v */b[in] = v;in++; }14Consumer Processwhile (true) {while (in <= out) /*do nothing */;w = b[out];out++; /* consume item w */}15Producer/Consumer Problem1617Possible solution 118binary semaphore s = 1; int n = 0;binary semaphore delay = 0; Producer(){while(true){produce();semwaitB(s);append();n++;if(n==1)semsignalB(delay);semsignalB(s);}}Consumer(){semwaitB(delay);while(true){semwaitB(s);take();n--;consume();if(n==0)semwaitB(delay);semsignalB(s);}}19Producer with Finite Circular Bufferwhile (true) {/* produce item v */while ((in + 1) % n == out) /* do nothing */;b[in] = v;in = (in + 1) % n}20Consumer with Finite Circular Bufferwhile (true) {while (in == out)/* do nothing */;w = b[out];out = (out + 1) % n;/* consume item w */}212223Semaphores with TestAndSetwait(S): while (TestAndSet(S.lock) > 0) { ... do nothing ... };S.count = S.count – 1; // count can be modified nowif (S.count < 0) {Enter process into S.queue;Block this process;}S.lock = 0;signal(S):while (TestAndSet(S.lock) > 0) { ... do nothing ... }S.count = S.count + 1;if (S.count <= 0) {Remove first process from S.queue and put it on ready queue;} S.lock =
View Full Document