Concurrency

Semaphore

Binary semaphore provides both synchronization and mutual exclusion.

Semaphores were introduced in the context of my OS class.

The Fundamental Principle

Two or more processes can cooperate by means of simple signals, such that a process can be forced to stop at a specified place until it has received a specific signal.

This complex coordination requirement can be satisfied by the appropriate structure of signals (called semaphore).

Semaphores are a concurrency control mechanism based on a special variable used for signalling

• A semaphore is simply a variable that holds an integer value
• If a process is waiting for a signal, it is suspended until that signal is sent
• May be initialized to a nonnegative number

Semaphores are used for limiting access to a collection of resources (for Concurrency control).

3 operations (atomic):

• Initialize (generally 1)
• SemWait operation decrements— the semaphore value
  • Call this to receive a signal via semaphore s
  • If the value becomes negative, then the process executing the semWait is blocked.
• SemSignal operation increments++ semaphore value
  • Call this to transmit a signal via semaphore s
  • If the resulting value is less than or equal to zero, then a process blocked by a semWait operation, if any, is unblocked

How to think of semaphores

Think of semaphore as having a limited number of permits to give out. If a semaphore has given out all the permits it has, then any new thread that comes along requesting a permit will be blocked till an earlier thread with a permit returns it to the semaphore.

2 types of semaphores:

1. Binary Semaphore – This is similar to mutex lock but not the same thing. It can have only two values – 0 and 1. Its value is initialized to 1. It is used to implement the solution of critical section problem with multiple processes.
2. Counting Semaphore – Its value can range over an unrestricted domain. It is used to control access to a resource that has multiple instances.

How to implement Semaphores

For both counting semaphores and binary semaphores, a queue is used to hold processes waiting on the semaphore.

struct semaphore {
  int count;
  queueType queue; // the blocked queue
};

Order of the queue?

The question arises of the order in which processes are removed from such a queue. The fairest removal policy is FIFO: The process that has been blocked the longest is released from the queue first.

• A semaphore using a FIFO policy is called a strong semaphore (better because guarantees freedom from Starvation)
• A semaphore that does not specify the order of removal from queue is called a weak semaphore

If the corresponding signal has not yet been transmitted, the process is suspended until the transmission takes place.

 
void semWait(semaphore s) {
  s.count--;
  if (s.count < 0) {
    /* place this process in s.queue */;
    /* block this process */;
  }
}
 
void semSignal(semaphore s) {
  s.count++;
  if (s.count <= 0) {
  /* remove a process P from s.queue */;
  /* place process P on ready list */;
  }
}

Initialization of semaphore value: that value equals the number of processes that can issue a wait and immediately continue to execute.

Why does this work? (how do semaphores guarantee mutual exclusion?)

Notice any other process attempting to enter the critical section will be blocked because s.count is less than 0. Only once semSignal is called, we can unblock one of these processes and move them onto the ready queue.

• By that point, s.count is probably still negative, but because we only unblock 1 process by calling semSignal, it’s fine. We guarantee that we are only executing the critical section 1 process at a time!!

AH! -s.count after a semWait() call represents the size of the blocked queue. since we do s.count++, the if (s.count <=0) checks if there is a value in the queue.

Using Semaphore to implement Mutual Exclusion

/* program mutualexclusion */
const int n = /* number of processes */;
semaphore s = 1;
 
void P(int i) {
  while (true) {
    semWait(s);
    /* critical section */;
    semSignal(s);
    /* remainder */;
  }
}
 
void main() {
  parbegin(P(1), P(2), ... , P(n));
}

Binary Semaphore

A binary semaphore is a semaphore that takes on only the values 0 and 1.

Binary Semaphore Primitives

struct binary_semaphore {
  enum {zero, one} value;
  queueType queue;
};
 
void semWaitB(binary_semaphore s) {
  if (s.value == one) s.value = zero;
  else {
    /* place this process in s.queue */;
    /* block this process */;
  }
}
 
void semSignalB(semaphore s) {
  if (s.queue is empty()) s.value = one;
  else {
    /* remove a process P from s.queue */;
    /* place process P on ready list */;
  }
}

With semaphores, we can implement Mutual Exclusion.

Semaphores in Hardware

uC++ uSemaphore (CS343)

uC++ provides uSemaphore, a general (counting) semaphore whose counter can be any non-negative integer; a binary semaphore is just uSemaphore(1). Internally the counter going negative represents the number of blocked tasks.

class uSemaphore {
public:
    uSemaphore( int count = 1 );
    void P();              // wait (decrement); block if would go < 0
    bool TryP();           // non-blocking P — true iff acquired
    void V( int times = 1 );  // signal (increment); release one waiter per increment
    int counter() const;   // current value (negative ⇒ # blocked)
    bool empty() const;    // true if no task is blocked
};

Idioms

• Synchronization: uSemaphore s(0); ... s.P();, A waits, B does s.V() when ready.
• Mutex: uSemaphore m(1); m.P(); CS(); m.V();, exactly one in CS at a time.
• Resource pool of k: uSemaphore slots(k);, P to borrow, V to return.

Batched V for multi-waiter synchronization. T2 and T3 must both wait for S1 to complete in T3 before running S2/S3. Instead of two separate V() calls, use V(2) to release both in one atomic increment.

_Task T1 { uSemaphore & lk;  void main() { ...; lk.P(); S2; ... } };
_Task T2 { uSemaphore & lk;  void main() { ...; lk.P(); S3; ... } };
_Task T3 { uSemaphore & lk;  void main() {
    S1;
    lk.V( 2 );         // one call releases both T1 and T2
    // equivalent to: lk.V(); lk.V();
} };
 
int main() {
    uSemaphore lk( 0 );                     // closed
    T1 x( lk ); T2 y( lk ); T3 z( lk );
}

The V(n) form is the reason a counting semaphore generalizes binary: you can release n waiters at once, matching graph fan-out without writing a loop.

How uSemaphore is implemented (Buhr §6.3)

Both semaphores carry the same three fields, plus an internal spinlock to serialize access to them:

class BinSem {                          // binary
    bool avail;                         // 1 permit or not
    queue<Task> blocked;
    SpinLock lock;
};
class CntSem {                          // counting
    int cnt;                            // positive: free permits; negative: # blocked
    queue<Task> blocked;
    SpinLock lock;
};

• cnt < 0 ⇒ |cnt| is the number of tasks currently on blocked, no extra length field needed
• cnt > 0 ⇒ that many permits are free, P() decrements without blocking
• internal SpinLock is held only for the short enqueue/dequeue window, never across the critical section the semaphore protects

P and V follow the same barging-prevention shape as Mutex Lock: the spinlock is passed from V to the woken task (the baton), so a newly-arriving caller cannot barge in between.

void CntSem::P() {
    lock.acquire();
    cnt -= 1;
    if ( cnt < 0 ) {
        // add self to blocked
        yieldNoSchedule( lock );        // release lock + block atomically
    } else {
        lock.release();
    }
}
void CntSem::V( int times ) {
    lock.acquire();
    for ( int i = 0; i < times; i += 1 ) {
        cnt += 1;
        if ( cnt <= 0 ) {
            // dequeue one task, make ready
            // spinlock ownership is conceptually passed to it (baton)
        }
    }
    lock.release();                     // see baton-passing variant in Mutex Lock
}

Why the counter, not the queue length, is the source of truth

cnt -= 1 happens before the blocked check, so the counter reflects the task’s intent to acquire even before it lands on the queue. A concurrent V reading cnt <= 0 therefore knows a waiter is coming and leaves the permit “reserved” by not incrementing past zero. Reading queue length would race with the enqueue.

Binary semaphore is structurally the same with avail replacing cnt: P tests avail, blocks if false; V either flips avail = true (no waiters) or wakes one waiter with avail staying false (baton keeps the permit reserved for the woken task, a form of baton passing).

Related

• Producer-Consumer Problem
• Bounded Buffer
• Unbounded Buffer
• Precedence Graph
• Split Binary Semaphore
• Baton Passing