Home | Projects | Notes > Operating Systems > Mutual Exclusion - Semaphores (OS Support)

Mutual Exclusion - Semaphores (OS Support)

Introduction

• In order to implement more modular, sophisticated waiting strategies, that eliminate busy-wait and starvation, we need structures that the OS can be involved with. We can allow the OS to assist with wait times using the state-transitions and events rather than relying on processes to idle in inefficient/costly busy wait loops.

• Semaphore, proposed by Edsger Dijktra, is a technique to manage concurrent process by using a special variable type (i.e., semaphore) with an integer value.

• Semaphores are used with shared memory systems, processes can each utilize the shared semaphores.

• Both OS and high-level languages provide support for the semaphore in code.

Semaphore types

• Depending on the maximum number of processes (or threads) allowed to enter the critical section:

  • Counting/general semaphore - >= 1

  • Binary semaphore - 1 (special case of counting/general semaphore)

• Depending on the order in which the processes blocked on the semaphore get moved to the ready queue:

  • Strong semaphore - FIFO (fair, starvation-free)

  • Weak semaphore - Unspecified order (may suffer from starvation)

  [!] Note: Semaphores each have a queue of waiting (blocked) processes.

Semaphore

• Semaphore Operations

  • Initialize

    • A semaphore may be initialized to a non-negative integer

    • Binary semaphores start with 1, counting semaphores >= 1

  • Wait

    • Decrements the semaphore value as an atomic operation

    • If the value becomes negative the process issuing the wait becomes blocked (not a busy wait)

    • Otherwise, the process has gained control of the semaphore and continues its execution

  • Signal

    • Increments the semaphore value as an atomic operations

    • If the value is still <= 0, then a blocked process that was waiting for the semaphore will be unblocked (i.e., moved into the ready queue) so it can proceed into the critical section when it is dispatched.

  A binary semaphore with value 1, means the resource is available

  A counting semaphore with a value of N means that N instances of the resource are available, or N more processes can enter the critical section

  If the semaphore value is 0 then the next process will have to block

  If the semaphore value is < 0, it represents the number of blocked process

• A Definition of Counting/General Semaphore Primitives

  xxxxxxxxxx
  24
  1
  struct semaphore
  2
  {
  3
      int count;
  4
      queue_type queue;
  5
  }
  6
  
  7
  void sem_wait(semaphore s)
  8
  {
  9
      s.count--;
  10
      if (s.count < 0)
  11
      {
  12
          // place this process in s.queue
  13
          // block this process
  14
      }
  15
  }
  16
  
  17
  void sem_signal(semaphore s)
  18
  {
  19
      s.count++;
  20
      if (s.count <= 0)
  21
      {
  22
          // remove a blocked process from s.queue and place it on the ready queue
  23
      }
  24
  }
  

• A Definition of Binary Semaphore Primitives

  xxxxxxxxxx
  26
  1
  struct binary_semaphore
  2
  {
  3
      enum {ZERO, ONE} value;
  4
      queue_type queue;
  5
  }
  6
  
  7
  void bsem_wait(binary_semaphore s)
  8
  {
  9
      if (s.value == ONE)
  10
          s.value = ZERO;
  11
      else
  12
      {
  13
          // place this process in s.queue
  14
          // block this process
  15
      }
  16
  }
  17
  
  18
  void bsem_signal(binary_semaphore s)
  19
  {
  20
      if (s.queue is empty())
  21
          s.value = ONE;
  22
      else
  23
      {
  24
          // remove a blocked process from s.queue and place it on the ready queue
  25
      }
  26
  }
  

  A binary semaphore just checks for 0 or 1 rather than incrementing and decrementing.

  Unlike a counting semaphore, a binary semaphore does not have way to tell how many processes are blocked on it. No matter how many blocked processes there are, the binary semaphore value will be kept as 0.

• Mutual Exclusion Using Semaphores

  xxxxxxxxxx
  22
  1
  // mutual exclusion using a semaphore
  2
  const int n = /* number of processes */;
  3
  semaphore s = 1;    // semaphores must be initialized upon creation
  4
  
  5
  void p(int i)
  6
  {
  7
      while (true)
  8
      {
  9
          sem_wait(s);
  10
          // critical section
  11
          sem_signal(s);
  12
          // remainder
  13
      }
  14
  }
  15
  
  16
  void main()
  17
  {
  18
      parbegin(p(1), p(2), ... , p(n));
  19
      // the construct 'parbegin(p1, p2, ... , Pn)' means, suspend the execution of the main program;
  20
      // initiate concurrent execution of procedures P1, P2, ... , Pn;
  21
      // when all of P1, P2, ... , Pn have terminated, resume the main program
  22
  }
  

Demonstration - Semaphores

• Let's say a section of code (critical section) is protected by a semaphore of initial value 5. Then, first 5 processes (or threads) will each enter the critical section without any problem decrementing the semaphore value. From this point on, no new process is allowed to get in until and unless any process in the critical section comes out and signals. The 6^th process, upon arrival, will see that the semaphore value is 0, and realize the critical section is already full. Decrementing the semaphore value, the 6^th process will move to the BLOCKED queue of the semaphore to wait for any process to come out of the critical section. (Any processes that arrive after the 6^th process will do the same and place themselves in the BLOCKED queue.). When a process comes out of the critical section, it will signal (increment the semaphore value by 1), and a process waiting in the BLOCKED queue, if any, will be moved to the READY queue so when it is dispatched it can enter the critical section.

• Don't be confused about the semaphore value. Even if the value is less than 0 at certain point in time, some processes may be leaving and some may be entering the critical section.

References

Stallings, W. (2018). Operating Systems: Internals and Design Principles (9th ed.). Pearson Education, Inc.