Show how counting semaphores can be implemented using only binary semaphores and ordinary machine instructions?

Question

I am studying for a midterm and this was one of the practice questions: Show how counting semaphores (i.e, semaphores that can hold an arbitrary value) can be implemented using only binary semaphores and ordinary machine instructions?

I'm not even sure where so start. I found this online;

P(s) { Pb(mutex_s); s = s-1; if(s < 0) {Vb(mutex_s); Pb(delay_s);} Vb(mutex_s); }
V(s) { Pb(mutex_s); s = s+1; if(s <= 0) Vb(delay_s); else Vb(mutex_s); }

Unfortunately, I don't really understand what the answer is telling me. Can anyone explain this answer to me, or show me in pseudo code how to answer?

Solution 1

I built the following intuition on Prahbat's answer:

What we are trying to replicate:

• Counting Semaphore implies at most N threads are allowed to access a resource

We can do this using binary semaphores:

• The counting semaphore locks access to a thread's critical section if there are N processes already in their critical section
  • => We need a binary semaphore sectionLock that tells waiting threads if they can access their critical section (sectionLock = 1) or they cannot (sectionLock = 0)
• We have to keep track of number of threads accessing the resource in their critical section. Let this counter be an integer count
  • count decremented on thread entering critical section (i.e. one spot less for a thread in this resource) and incremented on thread exiting critical section (i.e. one spot freed up for a thread in this resource)
  • => count is a shared resource and should only be accessed by one thread at a time
  • => we need a binary semaphore, countLock, for count
• If count <= 0 then we cannot allow anymore threads into critical section and must wait for sectionLock to be released by an exiting thread

Thus the following pseudocode suggests itself

P_counting( int count )
   P( countLock )        // Acquire lock to count: countLock <- 0
   count--
   if( count <= 0 )      // If no more threads allowed into critical section
      P( sectionLock )   // Resource full => Acquire section lock: sectionLock <- 0
      V( countLock )     // Release lock to count: countLock <- 1
   else
      V( countLock)

V_counting( int count )
   P( countLock )
   count++
   if( count > 0)        // Release sectionLock if resource is freed up
      V(sectionLock)     // countLock released after sectionLock so that waiting
      V(countLock)       // threads do not jump in when before resource is available
   else
      V(countLock)

Please let me know if I have got something wrong.

Solution 2

CSem(K) cs { // counting semaphore initialized to K
    int val ← K; // the value of csem
    BSem gate(min(1,val)); // 1 if val > 0; 0 if val = 0
    BSem mutex(1); // protects val

    Pc(cs) {
        P(gate)
        a1: P(mutex);
        val ← val − 1;
        if val > 0
        V(gate);
        V(mutex);
    }

    Vc(cs) {
        P(mutex);
        val ← val + 1;
        if val = 1
        V(gate);
        V(mutex);
    }
}

source: http://www.cs.umd.edu/~shankar/412-Notes/10x-countingSemUsingBinarySem.pdf

Solution 3

Let x, y be binary semaphore. We are going to implement counting semaphore S by it.P stand for wait operation and V for signal. Since we are taking S=4 so only 4 process can enter critical section.

S = 4, x = 1, y = 0;

/*---P(S)---*/
{P(x);S--;if(s<=0){V(x);P(y);}else V(x); }

/*--CRITICAL SECTION--*/

/*--V(S) ---*/
  { P(x); S++;IF(S>0){ V(y);V(x); }else V(x);} 

NOTE: P(x) decrease value of x by 1 while V(x) increases by 1,same for y. y is called hanging semaphore as P(y) put all those process in queue if S< 0.

Comments

[Sharlie Maimonie]

Great solution, but i think that line 7 is wrong. It should be: "if (s < 0)..." not "if (s < n)..."

[notTypecast]

Shouldn't P(sectionLock) come after V(countLock) in P_counting? If a process tries to acquire the section lock before it releases the counting lock and is blocked, the counting lock will remain blocked. Therefore, no process will be allowed to move past the P(countLock) line in V_counting, thus keeping the critical section locked indefinitely. Correct me if I'm wrong.