Threads and Semaphores: 5.1 Synchronizing Threads: Semaphores: The Concept

A semaphore is a data structure on which three basic operations are performed. These operations allow threads to avoid conflicting with other threads. Think of a semaphore as a flag which programs can set to indicate that some resource is locked. Anyone else who wants to use the resource must wait in line until whoever set the flag resets it. The three basic operations on a semaphore are initialize, set, and reset.

Initialize

The "initialize" operation creates a semaphore and gives it a name. In its initial state, the semaphore is "unlocked," meaning the first process that attempts to access it will succeed right away. A semaphore must be initialized before it can be used, although the initialization can be handled by the operating system so that it is transparent to the programmer.

Set (the "P" Operation)

The "P" operation is what a program performs in order to make sure it is allowed to proceed. For example, if the program is about to access shared data, it performs the "P" operation on the semaphore protecting that data to make sure no other program is accessing it.

If the semaphore is unlocked and a thread performs the "P" operation on it, the thread simply marks the semaphore locked and proceeds normally. If the semaphore is locked, a thread performing the "P" operation will block . This means the thread will stop running and will wait in the thread queue associated with the semaphore. When its turn to perform the protected operation arrives, the thread will proceed.

Reset (the "V" Operation)

When a thread has finished a protected operation, it performs the "V" operation to unlock the semaphore. If there are other threads in the queue for this semaphore, one of them is restarted and takes over, keeping the semaphore locked. Thus only one thread at a time runs the protected operation. If a thread performs the "V" operation on a semaphore and there are no other threads waiting in the semaphore's queue, the thread simply marks the semaphore unlocked and proceeds.

Programs must always reset a semaphore when they are done with it. If you fail to reset a semaphore, other threads may wait forever.

Because only one thread at a time is performing the protected operation and this thread is responsible for unlocking the semaphore, it is sometimes said to "have" the semaphore. The "P" and "V" operations are often referred to as "grabbing" and "releasing" a semaphore, respectively.

The Dreaded Deadlock Problem

When semaphores are not used carefully, they can cause programs to stop running entirely. Suppose Thread A tries to grab a semaphore which Thread B has locked. Thread A stops running until Thread B releases the semaphore. Thread B then tries to grab a second semaphore, which Thread A has previously locked. Thread B waits for Thread A to release the second semaphore, but Thread A is waiting for Thread B to release the first semaphore. Neither thread will ever wake up. This situation is called "deadlock."

To avoid deadlock, follow these guidelines:

When possible, avoid having a thread attempt to lock one semaphore while it already has another one locked.
When two or more semaphores may be locked by the same thread at the same time, they should always be used in the same order. Semaphores are often arranged in a hierarchy, with the coarsest (the one controlling access to the most resources) at the top and the finest at the bottom. Any thread grabbing multiple semaphores in this hierarchy must always grab from top to bottom; that is, no thread should grab a semaphore "above" one it already has locked.
In certain situations, a semaphore is used "between" two threads. One thread needs to wait until another performs a specific action. The first thread is said to "block" on the second. Of course, two threads must never block on each other. To ensure this situation never arises, only one of the threads should use the @call keyword when sending messages to the other; the other should always use @send and, when getting return information, have some sort of notification message sent in response.
When using the GEOS messaging system to send a message with @call to an object in another thread, the sending thread automatically blocks on the receiving thread. Since a number of user interface objects must be sent messages with @call , the application thread sometimes blocks on the user interface thread. To avoid deadlock, code that runs in the user interface thread must never send messages with @call to objects in the application thread. (This is a particular example of the above rule being implemented.)

GEOS SDK TechDocs |

5 Synchronizing Threads | Next:

5.2 Semaphores In GEOS