Semaphor

 

Basics

The semaphore is useful in controlling a shared resource that  a limited number of threads may obtain and work with it. It acts as a gate that limits the number of threads sharing the resource to a specified maximum number.

The semaphore enhances the usage of CPU and reduces the task switching.Semaphores allow changing the state of the tasks (Fig.1) - therefor a state variable needs to be maintained for each task in its TCB structure.

 

 

When a task is in BLOCKED(SUSPENDED) state, it is not picked by the scheduler until its state changes back to RUN(ACTIVE) thus the time and cycles on switching to and from a BLOCKED task are spared - reduced task switching!

A semaphore represents the number of abstract resources : if resources are available ,the semaphore counts the number of resources. If no resources are available, the semaphore counts the number of tasks that are waiting for resources. The latter situation can be expressed as the “number of resources missing”. If there are resources missing, then the TCBs of the tasks waiting for these resources are appended to a linked list of TCBs of waiting tasks, where the head of the list is part of the semaphore.

 

 

 

Implementation thoughts

The semaphore consists of two variables: a counter and a pointer to a TCB. The TCB pointer NextWaiting is only valid if the counter is less then 0; otherwise, it is invalid and set to 0 for clarity. It may be confusing but both pointers - at the semaphore and TCB structure bear the same name. The pointer represents the state of the semaphore as shown in the following table.

Counter Value NextWaiting TCB pointer State
N>0 0 N resources available
N=0 0 No resource,no task waiting
N Next Task waiting for the resource N tasks waiting for a resources;N resources miss

When a semaphore is created it is initialized with the number N>0 of resources initially available and the NextWaiting pointer is set to 0. Then task may request a resource by calling the semaphore’s  Acquire function, or the task may release a resource by calling semaphore’s Release function. The two functions have the following properties.

 

 

Implementation algorithm

What follows is a psevdo code implementation of semaphores’ Acquire and Release functions

Acquire:

  1. IF Counter>0

                Decrement  counter                          ;decrement number of available resources

  1. ELSE

                Decrement counter                ;increment number of tasks waiting

                Set state of current task to BLKD

                Append CurrentTask at the end of the waiting chain

                Yield current task quantum

 

The Acquire function examines Counter in order to verify if there are any resources available

If so - the number of resources is simply decremented and execution proceeds. Otherwise, the number of waiting tasks is increased(negative counter), the task is blocked and appended to the waiting chain, and finally the remaining task quantum is yielded which makes the blocking effective.

Release:

  1. IF Counter>=0

                    Increment counter                    ;increment number of available resources

  1. ELSE

                    Increment counter                   ;if tasks waiting - decrement their number

                   Set state of the first waiting task to run

                   Remove first waiting task from the head of the waiting chain

 

The Release function examines Counter - if it is >=0,which means there are no tasks waiting,then just increments counter,indicating there is one more resources available. If the Counter is

 

Acquire and Release intricacies  

Acquire() Release()
must not be called in ISR may be called from anywhere
may block the calling task not blocking call
the negative value of Counter is limited by the number of existing tasks,since every task is blocked at Acquire() call with Counter any number of Release() calles may be executed, thus increasing Counter to arbitrary high value
requires time O(N) if Counter0 requires constant time

Semaphores use some common initial Counter values.

 

Initial Counter Semantic
N>1 Semaphore represents a pool of N resources
N=1 A single resource that may only be used by one task at a time.
N=0 One or many resources,but none available initially

 

As it is said a picture is worth a thousand words - here is a visual working of an Acquire calls performed by a task T0, and Release function calls performed by another task or ISR on the same semaphore.

 

Acorn micro kernel lacks a semaphore synchronization premitive but it will be included in a higher version release.