Semaphores

• Dijkstra (1965) introduced the concept of a semaphore
• A semaphore is an integer variable that is accessed through two standard atomic operations: wait ( a spinlock, i.e. stops blocking and decrements thesemaphore) and signal (i.e. the semaphore counts the signals it receives)
• Semaphores are variables that are used to signal the status of shared resources to processes (a semaphore could have the value of 0, indicating that no wakeups are saved, or some positive value if one or more wakeups are pending)
• How does that work?
  • If a resource is not available, the corresponding semaphore blocks any process waiting for the resource
  • Blocked processes are put into a process queue maintained by the semaphore (avoids busy waiting!)
  • When a process releases a resource, it signals this by means of the semaphore
  • Signalling resumes a blocked process if there is any
  • Wait and signal operations cannot be interrupted
  • Complex coordination can be specified by multiple semaphores
• the down operation on a semaphore
  • checks to see if the value is greater than 0
  • if so, it decrements the value and continues
  • if the value is 0, the process is put to sleep without the completing the down for the moment
  • all is done as a single, indivisible atomic action
    • checking the value
    • changing it
    • possibly going to sleep
  • it is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has completed
  • synchronization and no race condition
• the up operation on a semaphore
  • increments the value of the semaphore
  • if one or more processes were sleeping on that semaphore, unable to complete an earlier down operation, one of them is chosen by the system and allowed to complete its down
  • the semaphore will be 0. but there will be one fewer process sleeping on it
  • indivisible process; incrementing the semaphore and waking up one process
• Solving the producer-consumer problem using semaphores (see Fig. 2.14)
  • the solution uses three semaphores;
    • one called full for counting the number of slots that are full
    • one called empty for counting the number of slots that are empty
    • one called mutex to make sure the producer and the consumer do not access the buffer at the same time. mutex is initially 1 (binary semaphore)
    • if each process does a down just before entering its CR and an up just after leaving it, the mutual exclusion is guaranteed.
• Possible uses of semaphores;
  • Mutual exclusion, initialize the semaphore to one
  • Synchronization of cooperating processes (signaling), initialize the semaphore to zero
  • Managing multiple instances of a resource, initialize the semaphore to the number of instances
• Type of semaphores;
  • binary is a semaphore with an integer value of 0 and 1.
  • counting is a semaphore with an integer value ranging between 0 and an arbitrarily large number. Its initial value might represent the number of units of the critical resources that are available. This form is also known as a general semaphore.

Figure 2.14: The producer-consumer problem using semaphore