Implementation

• The main disadvantage of the semaphore definition given here is that it requires busy waiting.
  • While a process is in its CS, any other process that tries to enter its CS must loop continuously in the entry code.
  • Busy waiting wastes CPU cycles that some other process might be able to use productively.
• This type of semaphore is also called a spinlock because the process ``spins'' while waiting for the lock. (Spinlocks do have an advantage in that no context switch is required when a process must wait on a lock, and a context switch may take considerable time. Thus, when locks are expected to be held for short times, spinlocks are useful.)
• To overcome the need for busy waiting, we can modify the definition of the $wait()$ and $signal()$ semaphore operations.
  • When a process executes the $wait()$ operation and finds that the semaphore value is not positive, it must wait.
  • However, rather than engaging in busy waiting, the process can block itself.
  • The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state.
  • Then control is transferred to the CPU scheduler, which selects another process to execute.
• A process that is blocked, waiting on a semaphore $S$, should be restarted when some other process executes a $signal()$ operation.
• The process is restarted by a $wakeup()$ operation, which changes the process from the waiting state to the ready state. The process is then placed in the ready queue. (The CPU may or may not be switched from the running process to the newly ready process, depending on the CPU-scheduling algorithm.)
• The list of waiting processes can be easily implemented by a link field in each process control block (PCB). Each semaphore contains an integer value and a pointer to a list of PCBs.
• The critical aspect of semaphores is that they be executed atomically. We must guarantee that no two processes can execute $wait()$ and $signal()$ operations on the same semaphore at the same time.