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?

Answer 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.