Unformatted text preview:

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

Rose-Hulman CSSE 332 - Concurrency

Download Concurrency
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Concurrency and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Concurrency 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?