Subject: Operating System

Topic: PROCESS COORDINATION

Difficulty: Medium

A semaphore is hardware or a software tag variable whose value indicates the status of a common resource. Its purpose is to lock the resource being used. A process which needs the resource will check the semaphore for determining the status of the resource followed by the decision for proceeding.

A semaphore is a synchronization object that controls access by multiple processes to a common resource in a parallel programming environment.Semaphores are widely used to control access to files and shared memory.

The three basic functionalities associated with semaphores are set, check and wait until it clears to set it again. Semaphores are used to address benchmark synchronization problems. Semaphores are normally implemented using file descriptors. Semaphore creations are not atomic

If two processes try to create, initialize and use a semaphore at the same time, a race condition is created. Semaphores are created and initialized to a positive value to show the availability of a resource to be used. Semaphores can be implemented through interrupts or by using test-set operations.

Every semaphore maintains sets of permits. It restricts the number of threads accessing the resources. Semaphores with only one permit and initialized to one serve as mutual exclusion locks.

They are referred to as such because they have only two states: permit available or zero permits available. This encloses the property so that a lock can be released by a thread other than the owner, helping in deadlock recovery.

Semaphores are used for mutual exclusions where the semaphore has an initial value of one, and P () and V () are called before and after the critical sections.

There are two types of semaphores

1. Counting Semaphore

2. Binary 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.