Simple Semaphore

janakas wrote on Wednesday, July 05, 2006:

Hi guys,
Finally I had time to do a RAM audit of my FreeRTOS project.  I was bit disappointed about the ram taken by each semaphore, 101 bytes each (project is based on AT91SAM7S64-32bit processor).
Because of this I created a simple semaphore.  The code is as given below.  Is there any other disadvantages for this approach other than the once I’ve mentioned below ?
- No Identification of which task has the semaphore
- Could cause task switching every 1ms when trying to get the semaphore
- Cannot use to protect resources what are used within interrupts

typedef volatile char* pSimpleSemaphore;

unsigned char vGiveSimpleSemaphore( pSimpleSemaphore pSemaphore )
{
    unsigned char ucRet = pdFALSE;

    taskENTER_CRITICAL();
    {
        if (*pSemaphore == pdTRUE)            //Semaphore already taken (Hopefully by same thread)
        {
            ucRet = pdTRUE;
            *pSemaphore = pdFALSE;            //Give the semaphore
        }
        else                                //Can’t give a none taken semaphore
        {           

        }
    }
    taskEXIT_CRITICAL();

    return ucRet;
}

unsigned char vTakeSimpleSemaphore( pSimpleSemaphore pSemaphore, portTickType xBlockTime )
{
    unsigned char ucRet = pdFALSE;

    do
    {
        taskENTER_CRITICAL();
        {
            if (*pSemaphore == pdTRUE)        //Semaphore already taken
            {
               
            }
            else                            //Semaphore available
            {           
                ucRet = pdTRUE;
                *pSemaphore = pdTRUE;        //Take the semaphore
                break;
            }
        }
        taskEXIT_CRITICAL();
        vTaskDelay( 1 );
    }
    while (xBlockTime–);

    return ucRet;
}

void vCreateSimpleSemaphore( pSimpleSemaphore pSemaphore)
{
    taskENTER_CRITICAL();
    {
        pSemaphore = pvPortMalloc ( sizeof( char ));
        *pSemaphore = pdFALSE;                //Clear the semaphore
    }
    taskEXIT_CRITICAL();
}

janakas wrote on Wednesday, July 05, 2006:

Sorry make the CreateSimpleSemaphore as below:

void vCreateSimpleSemaphore( pSimpleSemaphore* pSemaphore)
{
    taskENTER_CRITICAL();
    {
        *pSemaphore = pvPortMalloc ( sizeof( char ));
        **pSemaphore = pdFALSE;                //Clear the semaphore
    }
    taskEXIT_CRITICAL();
}

rtel wrote on Wednesday, July 05, 2006:

There is a trade off here between ROM and RAM usage.  The semaphore implementation is provided purely by macros that use the queue implementation, so each semaphore is basically a queue of length 1 and size zero.  Semaphores don’t add any extra ROM usage to the kernel.

When you measure the RAM usage of a semaphore you are measuring both the semaphore itself and the event management structures associated with the semaphore.  In FreeRTOS.org the two are contained in the same structure, whereas in other RTOS implementations the two are separate so there is a ‘hidden’ overhead to the semaphore.

Your simple semaphore implementation is of coarse fine for certain applications, but as you point out has a number of drawbacks.  It is basically a spin lock with a delay.  In addition to those you already highlight, some other drawbacks are:

+ Lack of prioritisation.  In the FreeRTOS.org implementation if there are two (or more) tasks blocked on the same semaphore then the highest priority of the two will be the task woken when the semaphore is available.

+ Wasted CPU cycles.  In the FreeRTOS.org implementation the task that is waiting for the semaphore uses no CPU cycles until either it times out or the semaphore becomes available.  The spin lock solution can use a lot of CPU cycles depending on the priority of the task that is waiting for 1 tick each time.

+ Starvation of lower priority tasks.  Waking each tick, testing the variable, then delaying again might take half a tick, leaving lower priority tasks little time to execute (the other half of the tick period).  This could really slug the application - especially if the task that has the semaphore is a lower priority task.

+ Interrupt response.  If the task waiting to obtain the semaphore is the task that executes most of the time (it has a high priority) then the application will spend a large percentage of its time with interrupts disabled (as the Get function uses a critical section).

+ Response time.  The FreeRTOS.org implementation is truly prioritised, with higher priority tasks executing immediately that they are able.  For example, take the following sequence:

a) A task of priority 2 attempts to get a semaphore, fails and blocks.

b) A task of priority 1 starts executing.

c) An ISR executes causing the semaphore to be Given* now a task of priority 2 is able to execute so even thought the ISR interrupted a priority 1 task it returns immediately to the priority 2 task.  In the spin lock implementation the lower priority task would continue to execute until the next tick, even though it was no longer the highest priority task that was able to execute.

Even though I point out a number of disadvantages here, like I say above your implementation is suitable for some applications.  It might be that the requirements of your application are met by the simpler implementation, and if so it is the best to use.  The FreeRTOS.org implementation is larger but more portable and more generic so more suitable to the majority of applications.

Regards,
Richard.

*Semaphores might be used for synchronisation, in the ARM9 serial driver I use a semaphore witin an ISR to wake a task when the FIFO has space, with the task blocking when the FIFO becomes full.

janakas wrote on Wednesday, July 05, 2006:

Thanks for your detailed response.

nobody wrote on Monday, July 10, 2006:

You can reduce the size of the semaphore structure significantly by defining portBASE_TYPE to be char.  This would likely cause larger and maybe slower code generated.