Mutex Vs Semaphore

Few terms to be learnt before jumping into Mutex & Semaphore.

Read the posts about Preemptive and Non-preemptive
Read the posts about Race Condition

Synchronisation 

Synchronisation is defined as "Sharing the system resources by processes in such a way that, concurrent access to the shared data is handled thereby minimising the chance of inconsistent data". So, I assume the synchronisation technique is for only global variables.

Atomicity  

Atomic operations are those operations that finish their tasks as a whole i.e. no other interruption is allowed before its completion.

An operation acting on a shared memory is atomic if it completes in a single step relative to other threads. When an atomic store is performed on a shared variable, no other thread can observe the modification half-complete.

Critical Section

It can be accessed via both process and thread. Concurrent access to the shared resource(variable) is protected, this protected section is called " Critical Section ". In other words, Critical section is a piece of program that needs mutual exclusion access. The below program is critical section as it is protected.

acquire(lock);                                                                                                                                          
if(a == 0)                                                                                                                                                 
a = 2;     #variable a is shared resource                                                                                                   
release (lock);                                                                                                                                          

Dead-Lock

Tasks/Threads/Process are waiting to acquire a semaphore or a mutex that never becomes free. Please refer this post

Priority Inversion (Happens when we use Mutex)

Priority inversion is the case where a high priority task becomes blocked for an indefinite period by a low priority task. Or, in other word, high priority task is preempted by low-priority task.

Priority Inversion

Now we will go to the topic of Mutex and Semaphore

Problem :

Two threads or processes are trying to access the same resource/memory. After one thread access, the value in the memory may change. So the next one will get an unexpected result.

To avoid the above race conditions, we are going for synchronisation objects.

1. Mutual Exclusion (Mutex) Access
2. Semaphores
3. Spinlock

Mutex and Semaphore are kernel resources which provide synchronisation services.

Mutual Exclusion (Mutex)

It addresses the problem of resource sharing. Successful solution to the above problem must have at least these two properties.

1. It must implement mutual exclusion: only one thread can be in the critical section at a time.
2. It must be free of deadlocks: if processes are trying to enter the critical section, one of them must eventually be able to do so successfully, provided no process stays in the critical section permanently.

Only Mutex provides mutual exclusion. It serialises the thread synchronisation. It's locking and protection mechanism used to synchronise access to a resource. Only one task can acquire the mutex. It means there is an ownership associated with mutex, and only the owner can release the lock (mutex).

Officially: "Mutexes are typically used to serialise access to a section of re-entrant 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." 
Ref: Symbian Developer Library

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

This addresses several problems with binary semaphores.

1. Accidental release

2. Recursive deadlock 

3. Priority inversion

4. Semaphore as a signal

Mutual exclusion will make the resource available only in a specific code segment called the Critical Section. And it ensures only one thread executes the critical section of the code at a time.

After entering the Critical section, atomicity comes into picture. The objective of mutex is atomic access. There are other ways to achieve atomic access like disabling interrupts which can be much faster. If the task takes time, then we can't disable the interrupts, because it ruins the responsiveness.

Mutex has the ability to support priority inheritance which is the solution for priority inversion problem.

Priority Inheritance

When scheduling the processes, select the process which blocks the process of highest priority.

Recursive Mutex/Reentrant Mutex

A thread can lock the mutex more than once and won't deadlock. It has an ownership, the thread that grabs the mutex must be the same thread that releases the mutex

Non-recursive Mutex

There is no sense of ownership and any thread can usually release the mutex no matter which thread originally took the mutex.

Semaphore

Officially: "A 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)." 

Ref: Symbian Developer Library

Semaphore locking has a time limit to prevent a deadlock

Scholten’s semaphore is referred to as the General or Counting Semaphore, Dijkstra’s being known as the Binary Semaphore.

1. Counting Semaphore (signal/wait)

When number of resources a Semaphore protects is greater than 1, it is called a Counting Semaphore. 

2. Binary Semaphore (lock/unlock)

When it controls one resource, it is called a Boolean Semaphore. A boolean semaphore is equivalent to a mutex.

Advantage of Mutex over Semaphore

Ownership is associated with Mutex, so only the owner(who locked the Mutex) can release the Mutex.

Difference between Mutex and Semaphore 

Mutex

Example – Imagine mutex as a key to a single toilet. Only one person can be inside the toilet at a time and he would want to lock the toilet and others waiting for toilet access must wait for person already inside to release the toilet. When finished, the person gives the key to next person in the queue.

• Mutex is for thread.
• Mutex is essentially atomic and singular in nature.
• Mutex is binary in nature.
• Operations like Lock and Release are possible
• Mutex works in userspace & kernel space.
• Only one thread can acquire a mutex at a time
• Mutex is an object
• A mutex can never be used as a semaphore.  
• Mutex object lock is released only by the process that has acquired the lock on it. 
• The thread with mutex has ownership over the resource.  
• If a mutex object is already locked, the process requesting for resources waits and queued by the system till lock is released.  
• It allows only one thread to access a critical section.
• Mutex will not work in Interrupt context.

Semaphore

Example – Imagine a bathroom with 4 identical keys here, identical keys can open the bathrooms. Here as many as 4 people can use the bathroom simultaneously and they wait and signal one another about the occupancy of the bathrooms.

• Semaphore is for processes & threads
• Semaphores are also atomic but not singular in nature
• Semaphores are of two types that are binary and counting.
• Semaphores work in kernel space.
• Only one process can acquire binary semaphore at a time but multiple processes can simultaneously acquire semaphore in case of counting semaphore.
• Semaphore is an integer variable.  
• A binary semaphore can be used as a mutex along with providing feature of signaling amongst threads.
• Semaphore value can be changed by any process acquiring or releasing the resource.  
• The concept of ownership is absent in semaphore.  
• If all resources are being used, the process requesting for resource performs wait () operation and block itself till semaphore count become greater than one.
• It allows more than one thread to access the critical section, but doesn't allow multiple processes.

• 
  

  
  

  Mutex & Sempahore

Interview Questions

1. What are the major concerns in multi-threaded programming?

1. Excessive locking 

2. Sleeping after acquiring lock 

3. Creating too many threads 

2. Is it possible to use mutex in multiprocessing case on Linux/UNIX ?

    Threads within the same process or other process can share mutex. So, mutex is used in multiprocessing environment also.

3. Difference between Mutex and semaphore 

i) Ownership
   Mutex can be released by the thread which claimed it. Mutex may store the id of the thread that locked it and verify the same thread unlocks it. But in case of semaphore any thread can unlock it.

ii) Access
   Mutex gives serialized access (not concurrent) to a single shared resource whereas semaphore gives simultaneous access to shared pool of resources.

iii) Mechanism
   Mutex is a locking mechanism and Semaphore is signalling mechanism.

iv) Recursive
    Mutex can lock the thread multiple times without creating a deadlock. Mutex can be acquired by same thread successfully multiple times with condition that it should release it same number of times.

But in semaphore, if the wait() called twice without releasing the semaphore, thread will block as it can be acquired only once.

v) Deletion safety

   Thread holding the mutex cannot be accidentally deleted. 

vi) System-wide/Process-wide 

   Another difference that would matter to developers is that semaphores are system-wide and remain in the form of files on the file-system, unless otherwise cleaned up. Mutex are process-wide and get cleaned up automatically when a process exits.

vii) Memory 

  According to the kernel documentation, Mutex are lighter when compared to semaphores. What this means is that a program with semaphore usage has a higher memory footprint when compared to a program having Mutex.

viii) Cost

Mutex is costly operation due to protection protocols associated with it.

ix)  Scope  

The scope of mutex is within a process address space which has created it and is used for synchronization of threads. Whereas semaphore can be used across process space and hence it can be used for inter-process synchronization as well.

x) Blocking calls
  Since only the owner should release the thread and mutex has only the serial access, there can be chances of thread waiting for long time to acquire the Mutex. So It is better to go for Semaphore always.

4. Process 1 sends an address to Process 2 somehow (without using any IPC mechanism), how can we protect process 2 accessing the address ?

I think the answer is using synchronisation methods.

5. Can we use mutex in Interrupt Context ? Why ? 

Click here for answer.

6. Which one is better ? Semaphore or Mutex ? Why ? 

7. What is critical section? 

8. What is deadlock and How to avoid it? 

9. What is re-entrant code? 

References:
linuxjournal, ecomputernotes, preshing (atomic operations), users.cs.cf.ac.uk (mutex programs)