Tuesday, December 11, 2012

Semaphore


In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming or multi user environment.
A useful way to think of a semaphore is as a record of how many units of a particular resource are available, coupled with operations to safely (i.e., without race conditions) adjust that record as units are required or become free, and if necessary wait until a unit of the resource becomes available. Semaphores are a useful tool in the prevention of race conditions; however, their use is by no means a guarantee that a program is free from these problems. Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores (same functionality that mutexes have).
The semaphore concept was invented by Dutch computer scientist Edsger Dijkstra in 1965, and the concept has found widespread use in a variety of operating systems.

Important observations

When used for a pool of resources, a semaphore does not keep track of which of the resources are free, only how many there are. Some other mechanism (possibly involving more semaphores) may be required to select a particular free resource.
Processes are trusted to follow the protocol. Fairness and safety are likely to be compromised (which practically means a program may behave slowly, act erratically, hang or crash) if even a single process acts incorrectly. This includes:
  • requesting a resource and forgetting to release it
  • releasing a resource that was never requested
  • holding a resource for a long time without needing it
  • using a resource without requesting it first (or after releasing it).
Even if all processes follow these rules, multi-resource deadlock may still occur when there are different resources managed by different semaphores and when processes need to use more than one resource at a time, as illustrated by the dining philosophers problem.

No comments:

Post a Comment