Skip to main content

Operating systems

Mutex is not a Binary Semaphore

Very few people know this - A mutex is not same as a binary semaphore. It is very different in implementation and has a very different purpose and usage. We discuss the details in this post.

Mutex is not a Binary Semaphore

Before we even begin, let us be on the same page with some terms and conventions to be used in the rest of the explanation.

  1. A > B > C in terms of execution priority!
  2. Added means the process was added to the queue.
  3. Exit would mean the process terminated.
  4. A and C share a resource.
  5. In our case, C acquires the resource first and A waits for C to release it!
  6. A dark circle represents a shared resource being acquired.
  7. The Hollow circle represents wanting to acquire the resource.
  8. The scheduler is called every time a Process is added.

Binary semaphore

Look at what happens when A is added (@ t=7) while B is executing. In the case of a semaphore being used between A and C - there is priority inversion!

A is a higher priority than B but, B gets to execute because B is a higher priority than C, and note that C has the resource that A depends on! So, A cannot be run anyway!

Figure #1: Semaphore being used between A and C to access a shared resource.
🤔
When a lower priority process is scheduled over a higher priority process, it is called priority inversion.

Notice how B gets to run while A is waiting. This is problematic, especially in a real-time operating system. How can we prevent a higher priority process from being blocked by a lower priority process holding a required resource? One solution is to increase the priority of the process holding the resource.