Basics of Mutex and Semaphore (part 1)

Hey Guys! It’s been a while since I wrote. I was traveling and then swamped with work. So, I have made this awesome deal with  my very enthusiastic friends to keep the decoding going. This is the first one under my blog category called the “Decoder Buddies”.

This blog is written by Ravi , Embedded Engineer at Qualcomm. Who better than a embedded guy to take on this topic ;). Without further ado, let’s get started.


Why mutex and semaphore?

The age old question of what constitutes a mutex and a semaphore, is one of the most fundamental concepts that computer science engineers must grasp, if they ever need to be capable of writing programs which are inherently multi-tasking and multi-threaded. Without these two critical concepts, it would be highly impossible to build any decent multi-tasking, multi-threaded program/ OS which has access to multiple resources at its disposal.


Is Mutex a Binary Semaphore ?

A very common misconception is that Mutexes and Semaphores are very similar, with the only difference being that a Mutex is capable of counting to 1, while Semaphores are able to count from 0 to N. While this provides a very simplistic view of the concept and also lends to the fact that most engineers will be able to comprehend that a Mutex is a binary flag that is used to protect access to a shared resource, most will be unable to explain the usage of a semaphore, also known as counting semaphore, some may use the common explanation that it is used to protect several equivalent resources.

Let us consider the example of a library that has multiple discussion rooms. In the simplistic view, if the library had only one discussion room, we can use a Mutex to regulate access to this room. If someone wants to use the discussion room, they are given a key which unlocks the room, but if the room is already in use, then the person requesting it, must wait in queue until the room is available again.

But this same example cannot scale when we have two equivalent discussion rooms. If we go by the simplistic explanation that a Semaphore is a generalization of a Mutex, then for the case where the library has two discussion rooms, the semaphore would be a basket containing two identical keys, either one of which can open both rooms. Thus, a counting semaphore cannot solve a multi-resource sharing problem. We will always need other state information, typically achieved using a Mutex. This would mean we need two mutexes or two distinct keys to the two distinct discussion rooms to ensure mutual exclusion.

Counting semaphores are almost always used with respect to signaling between tasks. A mutex is always locked and unlocked by the same task, which is in the midst of accessing a shared resource. A semaphore is used by tasks to signal to other tasks about resource availability/non-availability.

To summarize with an example, here’s how to use a Mutex:

/* Task 1 */
  Mutex_Lock(&mutex_discussion_room);
       // Access Shared Resource
  Mutex_Unlock(&mutex_discussion_room);

/* Task 2 */
   Mutex_Lock(&mutex_discussion_room);
        // Access Shared Resource
   Mutex_Unlock(&mutex_discussion_room);

From the above example, it can be clearly demonstrated that both Tasks 1 & 2, need to acquire access to the Mutex prior to accessing the shared resource, the access to the Mutex is usually done via an “Atomic Test and Set Operation” which ensures that only one of the task gets access to the Mutex, and ensures that the other task waits until the task which was assigned the Mutex releases said Mutex.

By contrast,a semaphore is used as below :

/* Task 1 - Producer */
Semaphore_Post(&semaphore_prod_con);   // Send the signal

/* Task 2 - Consumer */
Semaphore_Wait(&semaphore_prod_con);  // Wait for signal

The above example illustrates the operation of a Semaphore, in this case we have two tasks, one of which is a “Producer” and the other task is a “Consumer”. A “Post” operation on a Semaphore increases its count, while a “Wait” operation decreases its count. Hence, in this case, the producer keeps increasing the count via “Post” as and when it produces an item, and the consumer task decreases the semaphore count via “Wait” operations.


Usage

Based on the concepts that we have learned today, we can write a simple producer – consumer algorithm that makes use of both Mutexes and Semaphores.

Algorithm

Semaphore empty_count = QUEUE_SIZE, full_count = 0;

Mutex mutex_res;

Queue item_queue;

Producer

while (1==1)

{

Item = get_new_item();

Sem_Wait(&empty_count);

Mutex_Lock(&mutex_res);

Item_queue.push(item);

Mutex_Unlock(&mutex_res);

Sem_Post(&full_count);

}

Consumer

while (1 == 1)

{

Sem_Wait(&full_count);

Mutex_Lock(&mutex_res);

Item = Item_queue.top();

Item_queue.pop();

Mutex_Unlock(&mutex_res);

Sem_Post(&empty_count);

}


 

So, coming to the meme of the blog, now you know why, right ? ;).  

Thanks Ravi for taking the time out to do this. Appreciate it :).