Subject: Operating System

Topic: PROCESS COORDINATION

Difficulty: Medium

Dijkstra proposed a significant technique for managing concurrent processes for complex mutual exclusion problems. He introduced a new synchronization tool called Semaphore.

Semaphores are of two types −

1. Binary semaphore

2. Counting semaphore

Binary Semaphore

Binary semaphore is a semaphore with the integer value ranges over 0 and 1 whereas the counting semaphore's integer value ranges over unrestricted domain.

Binary semaphores are easier to implement comparing with the counting semaphore.

Binary semaphore allows only one thread to access the resource at a time. But counting semaphore allows N accesses at a time. The 2 operations that are defined for binary semaphores are take and release.

Take:Taking a binary semaphore brings it in the “taken” state, trying to take a semaphore that is already taken enters the invoking thread into a waiting queue.

Release:Releasing a binary semaphore brings it in the “not taken” state if there are not queued threads. If there are queued threads then a thread is removed from the queue and resumed, the binary semaphore remains in the “taken” state. Releasing a semaphore that is already in its “not taken” state has no effect.

Binary semaphores have no ownership attribute and can be released by any thread or interrupt handler regardless of who performed the last take operation.

Because of these binary semaphores are often used to synchronize threads with external events implemented as ISRs, for example waiting for a packet from a network or waiting that a button is pressed.

Counting Semaphore:

Counting Semaphore may have value to be greater than one, typically used to allocate resources from a pool of identical resources.

A counting semaphore is a synchronization object that can have an arbitrarily large number of states. The internal state is defined by a signed integer variable, the counter.

The counter value (N) has a precise meaning:

a. Negative, there are exactly -N threads queued on the semaphore.

b. Zero, no waiting threads, a wait operation would put in queue the invoking thread.

c. Positive, no waiting threads, a wait operation would not put in queue the invoking thread.

Two operations are defined for counting semaphores:

• Wait (chSemWait() in ChibiOS/RT). This operation decreases the semaphore counter; if the result is negative then the invoking thread is queued.

• Signal (chSemSignal() in ChibiOS/RT). This operation increases the semaphore counter, if the result is non-negative then a waiting thread is removed from the queue and resumed.

Counting semaphores have no ownership attribute and can be signaled by any thread or interrupt handler regardless of who performed the last wait operation.

Because there is no ownership concept a counting semaphore object can be created with any initial counter value as long it is non-negative.

The counting semaphores are usually used as guards of resources available in a discrete quantity. For example the counter may represent the number of used slots into a circular queue, producer threads would “signal” the semaphores when inserting items in the queue, consumer threads would “wait” for an item to appear in queue, this would ensure that no consumer would be able to fetch an item from the queue if there are no items available. Note that this is exactly how I/O queues are implemented in ChibiOS/RT, very convenient.