Semaphore with critical section example

Suppose we have a program:

Wait(S);
<critical section>
Signal(S);

Our semaphore is binary, and has \(S_{initial} = 1\).

Let us define \(N_{cs}\) as the no. of processes in critical section.

These are the processes which have completed wait() but not signal(). This is equivalent to #Wait(S) - #Signal(S).

S_{current} = 1 + #Signal(S) - #Wait(S)

S_{current} + N_{CS} = 1

Since S_{current} >= 0 -> NCS <= 1

This usage of semaphore is known as mutex.

Deadlock

\(S_{current} = 0\) and \(N_{CS} = 0\).

\(S_{current}\) + \(N_{CS}\) = 1

logo