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.

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.