Concurrency

Semaphore

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

Related

• Producer-Consumer Problem