Previous

Next

Semaphores

Semaphores are a popular mechanism for synchronizing tasks. A semaphore can be thought of as an event counter which can never become negative. A semaphore can be used by any number of tasks using the functions described in the RTKernel-32 Reference Manual. A program can use any number of semaphores.

Function RTKSignal stores an event in a semaphore; RTKWait retrieves an event from the semaphore if one is available; otherwise, it waits until an event is signalled. RTKernel-32 distinguishes five types of semaphores: counting, binary, event, resource, and mutex semaphores. A semaphore's type is set when the semaphore is created.

Counting Semaphores can store up to 2³²-1 events. They are suitable for general synchronization purposes and comply with the definitions given by Dijkstra ¹ or Ben-Ari².

Binary Semaphores cannot count, they can only accept the values 0 and 1. Function RTKSignal will always set a Binary Semaphore to value 1, even if it already has a value of 1; RTKWait always sets its value to 0.

Event Semaphores are similar to Binary Semaphores. However, executing RTKWait will not decrement the semaphore's count value. Thus, a single call to RTKSignal can release any number of tasks waiting at the Event Semaphore. To force an Event Semaphore back to zero, you must explicitly call function RTKResetEvent or RTKPulse, which are only available for Event Semaphores. Function RTKSignal will always set an Event Semaphore to value 1. RTKWait does not change the Event Semaphore value.

Resource Semaphores are especially suited for resource management (also refer to Advanced Topics, Mutual Exclusion). A Resource Semaphore guarantees the priority of a task occupying a resource to be at least the maximum of the priorities of all other tasks also requiring the respective resource. This technique is known as Priority Inheritance. A task requesting a resource using RTKWait hands down its priority to the task occupying the resource. This makes sure that a high priority task is never unnecessarily blocked by a task of lower priority.

Priority may be thought of as pseudo-priorities of Resource Semaphores. Assume that a task wants to occupy a resource using RTKWait, but is blocked because the resource is already occupied. In this case, the task passes its priority to the Resource Semaphore, which in turn passes its priority to the task currently occupying the resource. Priority Inheritance only takes place, of course, if it leads to an increase of the respective priority. A task's priority can only be raised by Priority Inheritance; it can never become lower than its base priority.

Another property of Resource Semaphores facilitates the safe termination and suspension of tasks. A task can only be suspended or terminated immediately if it does not occupy any resources. Otherwise, it continues to run until it has released all resources and subsequently suspends or terminates itself. This mechanism serves to avoid deadlocks.

Compared to other semaphore types, two important restrictions apply for Resource Semaphores: a resource must always be released (using RTKSignal) by the task that has acquired it using RTKWait. A task can occupy any number of resources simultaneously. However, it must release the resources exactly in the reverse sequence as they have been acquired.

Example:

RTKWait(R1); 
RTKWait(R2); 
... 
RTKSignal(R2); 
RTKSignal(R1);

If the sequence of RTKSignal calls were exchanged, RTKernel-32's Debug Version would abort the program with an error message. Since the Debug Version can check for compliance with the rules for Resource Semaphores, errors like those described in Typical Error Sources, Deadlock cannot occur. This is another important advantage of Resource Semaphores.

Due to these restrictions, Resource Semaphores are not suited for use by interrupt handlers.

A variation of Resource Semaphores are Mutex Semaphores. The only difference is that a task is allowed to acquire a resource it already owns.

Example:

RTKWait(R); 
RTKWait(R); 
... 
RTKSignal(R); 
RTKSignal(R);

If R were a Resource Semaphore, the second call to RTKWait would cause an error (a task cannot acquire a resource it already owns). However, for a Mutex Semaphore, such a construct is legal and the resource would not be released until the same number of RTKSignal calls as RTKWait calls have occurred.

The disadvantage of Mutex Semaphores compared to Resource Semaphores is that unmatched RTKWait/RTKSignal pairs are not detected. If a call to RTKSignal is missing, the resource would never be released and no error is reported, even when the task continues to call RTKWait and RTKSignal on the same mutex.

The following example shows how to use a semaphore for general synchronization. Assume Task A should be activated when Task B has reached a certain point (Task B is the main program):

#include <stdio.h> 
#include <Rtk32.h> 

RTKSemaphore S; 

void RTKAPI TaskA(void * P) 
{ 
   printf("Task A: waiting on semaphore S\n"); 
   RTKWait(S); 
   printf("Task A: continued\n"); 
} 

int main(void) 
{ 
   printf("\n"); 
   RTKernelInit(3); 
   S = RTKCreateSemaphore(ST_COUNTING, 0, "Semaphore S"); 
   printf("Main  : creating task A\n"); 
   RTKRTLCreateThread(TaskA, 4, 0, 0, NULL, "Task A"); 
   printf("Main  : setting semaphore S\n"); 
   RTKSignal(S); 
   printf("Main  : done.\n"); 
   return 0; 
}

The semaphore is initialized with 0 events. Task A has a higher priority and thus is started immediately after RTKCreateThread. Its second statement is RTKWait(S). Since there are no events stored, Task A is blocked and the main task runs until the semaphore is signalled. When the main task executes the statement RTKSignal(S), Task A is activated immediately and retrieves the event. Both tasks then run to completion and the program terminates.

Using semaphores to implement mutual exclusion is discussed in Advanced Topics, Mutual Exclusion.

The various semaphore related API functions of RTKernel-32 are documented in the RTKernel-32 Reference Manual.

Module RTKernel-32

Time

Spinlocks