Semaphore Theory


Let s first go through a quick review of semaphore theory. A semaphore is nothing more than a variable that is protected. It provides a means to restrict access to a resource that is shared amongst two or more processes. Two operations are permitted, commonly called acquire and release. The acquire operation allows a process to take the semaphore, and if it has already been acquired , then the process blocks until it s available. If a process has the semaphore, it can release it, which allows other processes to acquire it. The process of releasing a semaphore automatically wakes up the next process awaiting it on the acquire operation. Consider the simple example in Figure 16.1.

click to expand
Figure 16.1: Simple binary semaphore example with two processes.

As shown in Figure 16.1, two processes are both vying for the single semaphore. Process A performs the acquire first and therefore is provided with the semaphore. The period in which the semaphore is owned by the process is commonly called a critical section . The critical section can be performed by only one process, therefore the need for the coordination provided by the semaphore. While Process A has the semaphore, Process B is not permitted to perform its critical section.

Note that while Process A is in its critical section, Process B attempts to acquire the semaphore. As the semaphore has already been acquired by Process A, Process B is placed into a blocked state. When Process A finally releases the semaphore, it is then granted to Process B, which is allowed to enter its critical section. Process B at a later time releases the semaphore, making it available for acquisition.

Semaphores commonly represent a point of synchronization in a system. For example, a semaphore could represent access to a shared resource. Only when the process has access to the semaphore can it access the shared resources. This ensures that only one process will have access to the shared resource at a time, thus providing coordination between two or more users of the resource.

Note  

Semaphores were invented by Edsger Dijkstra for the T.H.E. operating system. Originally, the semaphore operations were defined as P and V. The P stands for the Dutch Proberen, or to test, and the V for Verhogen, or to increment.

Edsger Dijkstra used the train analogy to illustrate the critical section. Imagine two parallel train tracks that for a short duration merge into a single track. The single track is the shared resource and is also the critical section. The semaphore ensures that only one train is permitted on the shared track at a time. Not having the semaphore could have disastrous results on two trains trying to use the shared track at the same time. The effect on software is just as treacherous.

Types of Semaphores

Semaphores come in two basic varieties. The first are binary semaphores , as illustrated in Figure 16.1. The binary semaphore represents a single resource, and therefore when one process has acquired it, others are blocked until it is released.

The other style is the counting semaphore , which is used to represent shared resources in quantities greater than one. Consider a pool of buffers. A counting semaphore could represent the entire set of buffers by setting its value to the number of buffers available. Each time a process requires a buffer, it acquires the semaphore, which decrements its value. When the semaphore value reaches zero, processes are blocked until it becomes nonzero. When a semaphore is released, the semaphore value is increased, thus permitting other processes to acquire a semaphore (and associated buffer). This is the one use for a counting semaphore (see Figure 16.2).

In the counting semaphore example, each process requires two resources before being able to perform its desired activities. In this example, the value of the counting semaphore is 3, which means that only one process will be permitted to fully operate at a time. Process A acquires its two resources first, which means that Process B blocks until Process A releases at least one of its resources.

click to expand
Figure 16.2: Counting semaphore example with two processes.



GNU/Linux Application Programming
GNU/Linux Application Programming (Programming Series)
ISBN: 1584505680
EAN: 2147483647
Year: 2006
Pages: 203
Authors: M. Tim Jones

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net