Saturday, August 13, 2011

Semaphores and Mutexes

The Classic Toilet Example:

Mutex:

Is a key to a toilet. One person can have the key - occupy the toilet - at the time. When finished, the person gives (frees) the key to the next person in the queue.

Mutexes - used to provide an access to code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section.

(A mutex is really a semaphore with value 1.)

Semaphore:

Is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count - the count of keys - is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.

Semaphore - restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore).

Algorithm

Binary Semaphore - Dijkstra Algorithm:
Use a pair of function calls to the operating system to indicate entering and leaving a critical region. This was achieved through the acquisition and release of an operating system resource called a semaphore. Dijkstra used the notation of P & V, Prolagen (P) To try and lower, and Verhogen (V) To raise, To increase.

// Task 1

P(S)
...
critical section code
...
V(S)


To begin with, S has value 1. Any task can enter critical section if the Semaphore is +ve. When a task enters P(S) - it decrements S making S equal to zero. When that task exists critical section, it again increments S to 1 - so that other task can now enter critical section.

With this model the first task arriving at the P(S) [where S is the semaphore] call gains access to the critical region. If a context switch happens while that task is in the critical region, and another task also calls on P(S), then that second task (and any subsequent tasks) will be blocked from entering the critical region by being put in a waiting state by the operating system. At a later point the first task is rescheduled and calls V(S) to indicate it has left the critical region. The second task will now be allowed access to the critical region.

Counting Semaphore - (Scholten, scientist)
In his proposal the semaphore can have an initial value (or count) greater than one. This enables building programs where more than one resource is being managed in a given critical region. For example, a counting semaphore could be used to manage the parking spaces in a robotic parking system. The initial count would be set to the initial free parking places. Each time a place is used the count is decremented. If the count reaches zero then the next task trying to acquire the semaphore would be blocked (i.e. it must wait until a parking space is available). Upon releasing the semaphore (A car leaving the parking system) the count is incremented by one.

Problems with Semaphores -

1) Accidental release
This problem arises mainly due to a bug fix or cut-and-paste mistake. In this case, a semaphore isn’t correctly acquired but is then released.

/* Oops, forgot P(S) */
...
critical section code
...
V(S)

Each time the buggy code is executed the count is increment and yet another task can enter the critical section.

2) Deadlock

2.1) Recursive Deadlock
Recursive deadlock can occur if a task tries to lock a semaphore it has already locked.

myFunction() {

P(S)
...
critical section code starts
...
myFunction();
...
critical section code ends.
...
V(S)

Here the S was still 0 when again recursive call was made.

2.2) Deadlock through Task Death
What if a task that is holding a semaphore dies or is terminated? If you can’t detect this condition then all tasks waiting (or may wait in the future) will never acquire the semaphore and deadlock.

2.3) Priority Inversion
Priority inversion is the case where a high priority task becomes blocked for an indefinite period by a low priority task. Lets say a thread A was waiting for completion of thread B to proceed. In the mean time, thread C with priority more than B came in and pre-empted thread B - thus thread A never completed.

2.4) Semaphore as a Signal
Assuming Task1 calls theP(S) it will block. When Task 2 later calls the V(S) then the unilateral synchronization takes place and both task are ready to run

MUTEX - a little bit more...

The mutex is similar to the principles of the binary semaphore with one significant difference: the principle of ownership. Ownership is the simple concept that when a task locks (acquires) a mutex - only it can unlock (release) it. If a task tries to unlock a mutex it hasn’t locked (thus doesn’t own) then an error condition is encountered and, most importantly, the mutex is not unlocked. It solves - all the problems with Semaphores listed above -

1) Accidental Release
Ownership stops accidental release of a mutex as a check is made on the release and an error is raised if current task is not owner.

2.1) Recursive Deadlock
Due to ownership, a mutex can support relocking of the same mutex by the owning task as long as it is released the same number of times.

2.2) Priority Inversion
With ownership this problem can be addressed using one of the following priority inheritance protocols. The idea is never let a high priority thread pre-empt you:

a) The Basic Priority Inheritance Protocol enables a low-priority task to inherit a higher-priorities task’s priority if this higher-priority task becomes blocked waiting on a mutex currently owned by the low-priority task. The low priority task can now run and unlock the mutex – at this point it is returned back to its original priority.

b) With the Priority Ceiling Protocol (PCP) method each mutex has a defined priority ceiling, set to that of the highest priority task which uses the mutex. Any task using a mutex executes at its own priority – until a second task attempts to acquire the mutex. At this point it has its priority raised to the ceiling value, preventing suspension and thus eliminating the “hold and wait” condition.

2.3) Death Detection
If a task terminates for any reason, the RTOS can detect if that task current owns a mutex and signal waiting tasks of this condition. In terms of what happens to the waiting tasks, there are various models, but two dominate:
a) All tasks readied with error condition;
b) Only one task readied; this task is responsible for ensuring integrity of critical region.

When all tasks are readied, these tasks must then assume critical region is in an undefined state. In this model no task currently has ownership of the mutex. The mutex is in an undefined state (and cannot be locked) and must be reinitialized.

When only one task is readied, ownership of the mutex is passed from the terminated task to the readied task. This task is now responsible for ensuring integrity of critical region, and can unlock the mutex as normal.

Some known APIs

It should be noted that many Real-Time Operating Systems (or more correctly Real-Time Kernels) have their own logics and APIs for mutexes and semaphores. Some common RTOS are -

VxWorks Version 5.4
POSIX Threads (pThreads) – IEEE Std 1003.1, 2004 Edition
Microsoft Windows Win32 – Not .NET

References -

http://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-1-semaphores/
http://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-2-the-mutex/
http://blog.feabhas.com/2009/10/mutex-vs-semaphores-–-part-3-final-part-mutual-exclusion-problems/

3 comments:

  1. I have read your blog its very attractive and impressive. I like it your blog.

    Java Training in Chennai Java Training in Chennai | Core Java Training in Chennai

    Online Java Training Java Online Training | Java J2EE Online Training | JavaEE Training Institute in Chennai

    ReplyDelete
  2. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in TECHNOLOGY , kindly contact us http://www.maxmunus.com/contact
    MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.
    For Demo Contact us.
    Saurabh Srivastava
    MaxMunus
    E-mail: saurabh@maxmunus.com
    Skype id: saurabhmaxmunus
    Ph:+91 8553576305 / 080 - 41103383
    http://www.maxmunus.com/


    ReplyDelete