Semaphores

Semaphores are fundamental to operating systems. Dijkstra first invented them 1965 as part of his early work on operating systems.

Semaphores can be either binary or counting. A binary semaphore is a counting semaphore starting at 1. They are often implemented with hardware support using Test and Set instructions or by using critical section.

What does a semaphore mean in a system?

• A semaphore means whatever the designer says it means.
• When a designer adds a semaphore to a system he is really adding a new set of programming rules.
• If we have a data structure D and add a semaphore SD to protect it, we also need to add the programming rules for using the semaphore. In this case:
  • Any code that reads or writes to data structure D shall first acquire semaphore SD.
• Only with this rule does the semaphore become meaningful and only when the rule is followed does the data structure get protected.

Semaphores can be used as flags or as counters.

• To use as a flag create with count = 0.
• To use as a counter create with count = n.
• Used as flags, semaphores can signal an event or coordinate the action between two tasks, or between an ISR and a task.
  • ISR signaling a task
  • Producer / consumer pattern
  • Lock step or back and forth with tow or more tasks
• Used as counters, semaphores can be used to keep track of resources.
  • Increment count by one for each available resource
  • Such as ports or slots in a buffer
• Task can grab one then hold it as long as it needs while posting, pending, delaying on other things.

Semaphore pseudo code

The following is an example of a very simple way to implement a semaphore using two functions, wait and signal. While you would not want to implement it this way, it does shows the essence of what a semaphore does.

The variable s is a shared global. It is initialize to 0. Any task calling the wait function will be forced to wait as long as s equals 0. It will spin on testing s until some other task calls the signal function.

The signal function increments s by one which frees the first task from the spin loop in the wait function. Once it free from waiting it decrement s by one setting s back to 0.

In this way one task can be made to wait as long as necessary. It will wait until another task calls the signal function. Signaling that it may continue.

The functions wait and signal are often called pend and post. uCOS uses the terms pend and post which we will use from now on also.

int s = 0;

wait() {
    while(s==0); // spin
    s--;
}

signal() {
    s++;
}

While the simple implementation works it is not very efficient. The task that called wait continues to run though it is stuck in loop wasting cycle. A more efficient way to implement the semaphore is to take advantage of the OS’s scheduler.

In this case, when a task calls pend and s equals 0, the task is added to a wait list and scheduler is called to reschedule the tasks. This means the task that called pend stops running. The call to reschedule does not return. All other tasks continue as they were before but this task will not run again until another task calls the post function.

When another task calls the post function s is incremented by 1 and the scheduler is called to reshedule the tasks. The schedule will examine all the tasks in the wait list and look for a task waiting for s to be greater then 0. It it find one, that task is removed from the wait list and added back to the running list.

The schedule examines the tasks on the running list and picks the one with the highest priority. If necessary the scheduler will do a context switch to switch the CPU to the task with the highest priority.

Which task runs after the schedule is called is independent of which task was waiting on pend or which task called post. It only depends on the relative priorities of the tasks.

If the task waiting on pend has a higher priority then the task that called post, then it will run. If the task that call post has a higher priority it will run. Because of this, calling post does not necessarily mean there will be a context switch.

A context switch will only occur if the waiting task has a higher priority then the task that called post.

pend(s) {
    if (s==0) {
        add_this_task_to_wait_list();
        reschedule();
    }
    s--;
}

post(s) {
    s++;
    reschedule();
}

The pseudo code for the Pend operation is:

enter_critical_section()
if (semaphore > 0)
{
    semaphore = semaphore - 1
    leave_critical_section()
}
else
{
    leave_critical_section()
    suspend thread
}

The pseudo code for the Post operation is:

• enter critical section // make atomic operation
• semaphore = semaphore + 1
• exit critical section
• check for reschedule

Using a Semaphore

OS_EVENT *pDataLogSem;
main()
{
    pDataLogSem = OSSemCreate(1);
}

// creator of data
ThreadA()
{
    newSample = ReadNewData();
    if (samples->arrayCount < MAX_ARRAY)
    {
        OSSemPend(pDataLogSem, 0, &err);
        samples->data[samples->arrayCount++] = newSample;
        err = OSSemPost(pDataLogSem);
    }
    else
    {
        // error case
    }
}

// consumer of data
ThreadB()
{
    UINT32 lastSample = 0;
    OSSemPend(pDataLogSem, 0, &err);
    if (Samples->ArrayCount > lastSample)
    {
        newSample = Samples->Data[lastSample++];
        err = OSSemPost(pDataLogSem);
        ProcessSample(newSample);
    }
    else
    {
        err = OSSemPost(pDataLogSem);
    }
}

Deadlocks

A deadlock occurs when two or more threads are each waiting on events (e.g. semaphores, resources, etc.) that only the other thread can release. A deadlock can formally be defined as follows: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. See Tanebaum/Woodhull

Always take semaphores in the same order. If multiple semaphores are used by multiple threads, then they must be taken in the same order.

Always release in the opposite order taken. If you take SemA, then SemB, you should release SemB then SemA.

• Lots of Semaphores is a bad thing
  • One for all data in the system
  • One per major data structure or group
  • One per type of data processing

Semaphore Deadlock examples

AcquireDataThread()
{
   while (TRUE)
   {
       newData = GetDataItem();

       PendSemaphore(pDatabaseSem);
       AddDatabase(newData);
       PostSemaphore(pDatabaseSem);
   }
}

SendDataThread()
{
   while(TRUE)
   {
       PendSemaphore(pSerialPortSem);
       PendSemaphore(pDatabaseSem):
       if (new data in database)
       {
           SendData();
       }
       PostSemaphore(pDatabaseSem);
       PostSemaphore(pSerialPortSem);
   }
}

AcquireThread()
{
   while (TRUE)
   {
       newData = GetDataItem();
       PendSemaphore(pDatabaseSem);
       err = AddDatabase(newData);  // << A
       if (err)
       {
          PendSemaphore(pSerialPortSem);
          SendMessage("Database full error");
          PostSemaphore(pSerialPortSem);
       }
       PostSemaphore(pDatabaseSem);
   }
}

SendThread()
{
   while(TRUE)
   {
       PendSemaphore(pDatabaseSem);  // << B
       PendSemaphore(pSerialPortSem);
       if (new data in database)
       {
           SendData();
       }
       PostSemaphore(pSerialPortSem);
       PostSemaphore(pDatabaseSem);
   }
}

Threads at point A & B

Thread	Acquire Thread owns	Acquire Thread needs	Send Thread owns	Send Thread needs
ppDatabaseSem	X			X
ppSerialPortSem		X	X

Semaphore Deadlock example solution

AcquireThread()
{
    while (TRUE)
    {
        newData = GetDataItem();
        PendSemaphore(pDatabaseSem);
        err = AddDatabase(newData);
        if (err)
        {
            PendSemaphore(pSerialPortSem);
            SendMessage("Database full error");
        }
        PostSemaphore(pSerialPortSem);
        PostSemaphore(pDatabaseSem);
}

SendThread()
{
    while(TRUE)
    {
        PendSemaphore(pDatabaseSem);
        PendSemaphore(pSerialPortSem);
        if (new data in database)
        {
            SendData();
        }
        PostSemaphore(pSerialPortSem);
        PostSemaphore(pDatabaseSem);
    }
}

Priority Inversion

• Can occur in multi-tasking systems
• It is a condition where a lower priority task effectively blocks a higher priority task from accomplishing its job
• Can be difficult to detect
• Solutions - Don’t share semaphores in this fashion by design
• Priority Inheritance - supplied by some OSs * OS bumps low-priority tasks priority to that of high priority task for duration of inversion. (Sometimes only one-level deep, can be costly and non-deterministic)

Priority Inversion example

// Data acquisition thread
ImportantTask()
{
    SSetPriority(HIGHEST)
    While(TRUE)
    {
        //...
        Sleep(1 second)
        AcquireSemaphore(pDatabaseSem)
        // ... work on database
        ReleaseSemaphore(pDatabaseSem)
    }
}

// Database statistics thread
MenialTask()
{
    SetPriority(LOWEST)
    While(TRUE)
    {
        //...
        Sleep(5 minutes)
        AcquireSemaphore(pDatabaseSem)
        //... check database statistics
        ReleaseSemaphore(pDatabaseSem)
    }
}

All Threads Are Run-able

::

Priority 1 Thread A Thread B Thread C Priority 2 Thread B Thread C Mutex M[A,B] M[B,C]

R = Running B = Blocked

One Thread Is Blocked

::

Multiple depth inversion support Priority 1 Thread A Thread B Thread C Priority 2 Thread B Thread C Mutex M[A,B] M[B,C]

Single depth inversion support Priority 1 Thread A Thread B Thread C Priority 2 Thread B Thread C Mutex M[A,B] M[B,C]