[TBD]Mutual exclusion technique

Introduction

Layman explanation

Suppose that you are in barber shop for hair cut.

Technical explanation

Semaphore

Binary and Count semaphores

Binary semaphores are binary, they can have two values only; one to represent that a process/thread is in the critical section(code that access the shared resource) and others should wait, the other indicating the critical section is free.

On the other hand, counting semaphores take more than two values, they can have any value you want. The max value X they take allows X process/threads to access the shared resource simultaneously.

A semaphore has two parts : a counter, and a list of tasks waiting to access a particular resource. A semaphore performs two operations : wait (P) [this is like acquiring a lock], and release (V)[ similar to releasing a lock] - these are the only two operations that one can perform on a semaphore. In a binary semaphore, the counter logically goes between 0 and 1. You can think of it as being similar to a lock with two values : open/closed. A counting semaphore has multiple values for count.

What is important to understand is that the semaphore counter keeps track of the number of tasks that do not have to block, i.e., they can make progress. Tasks block, and add themselves to the semaphore's list only when the counter is zero. Therefore, a task gets added to the list in the P() routine if it cannot progress, and "freed" using the V() routine.

Binary semaphore Implementation

typedef struct

{

int count; --> Initialized to zero.

queue q; /* queue of threads waiting on this semaphore */

} Semaphore;

void P(Semaphore s)

{

Disable interrupts;

if (s->count > 0) {

s->count -= 1;

Enable interrupts;

return;

}

Add(s->q, current thread);

sleep(); /* re-dispatch */ Enable interrupts;

}

void V(Semaphore s)

{

Disable interrupts;

if (isEmpty(s->q)) {

s->count += 1;

} else {

thread = RemoveFirst(s->q);

wakeup(thread); /* put thread on the ready queue */

}

Enable interrupts;

}

Producer-Consumer problem

The emptyCount is initially N, fullCount is initially 0, and useQueue is initially 1.

The producer does the following repeatedly:

produce: P(emptyCount) P(useQueue) putItemIntoQueue(item) V(useQueue) V(fullCount)

The consumer does the following repeatedly

consume: P(fullCount) P(useQueue) item ← getItemFromQueue() V(useQueue) V(emptyCount)

Mutex

Reference

http://stackoverflow.com/questions/10898022/differnce-between-counting-and-binary-semaphores

https://en.wikipedia.org/wiki/Semaphore_(programming)

http://www.mpi-sws.org/~druschel/courses/os/lectures/proc4.pdf