Structure protection: One writer, mult reader

Kernel
1

hermarcel wrote on Wednesday, May 22, 2013:

Hello,

I am designing my first real FreeRTOS project and would like your opinion on the following.

I have a common datastructure that is frequently updated with new data from the outside world. Updates are done by a gatekeeper task. This is the only task that will be updating the structure.

Several tasks will need read-access to the data. These tasks should not have to wait for each other (they are only reading).

I would like to create a situation where the writer indicates it is about to update the struct and then blocks until all current readers are done with it. When the writer is updating the struct, the readers will wait (block) until the writer is done.

What would be a nice strategy to go with?
I could have the writer-task take a binary semaphore when it is about to update the structure. And give the semaphore when updating is finished. The reader-tasks should then have a means to check is the semaphore is taken or not.
After the writer has taken it’s semaphore it could block until a counting-semaphore reaches zero to indicate that no reader-tasks are using the structure.

Is this a viable approach? There seem to be no RTOS api-calls for checking if a binary-semaphore is taken. Nor can I find funtions that block until a counting semaphore reaches zero.

What approach would you take?

Thank you,

Marcel

2

rtel wrote on Thursday, May 23, 2013:

The easiest approach would be to guard the structure with a mutex, and code your tasks (be they reading or writing) to block on obtaining the mutex before accessing the structure, and then give the mutex back when they are finished with the structure. 

Another approach would be to place all reads and writes inside a critical section.  That is an easy solution if reading and writing is very fast.  If reading and writing is not fast then you can always suspend the scheduler (so no context switches occur) before a read or write, then resume it again when the read or write has finished.

However, whether any of these options are necessary or not depends on what the structure contains.

If reading of the structure is atomic, then the readers really need not worry about mutual exclusion at all.

Reads will be atomic if the following two conditions are met:

1) The values being read from the structure are contained in variables that are no greater than the natural size of the architecture.  Therefore, on a 32 bit architecture, reading a 32 bit value is atomic, but on an 8 or 16 bit architecture, reading a 32 bit value is not atomic.

2) The values in the data structure make sense individually, and are not dependent on other values in the same structure.  For example, if the the structure contains members x and y and x and y must be updated together for the data to be valid, then the values must also be read together to make sense.  Consider the scenario where x is read by a task, then y is updated by another task before the original task has read y, then if that does not matter then mutual exclusion on reading is not needed.  If it does matter then some form of mutual exclusion is needed.

Regards.

3

hermarcel wrote on Thursday, May 23, 2013:

Richard, thank you for your reply.

The reads/writes are not atomic. So, I do need to protect the readers from reading incoherent data.

It seems that the approaches you propose do not allow multiple readers at the “same” time. Usage of a mutex or critical section would allow only one reader atthe time accessing the structure. What I would like is to give all readers concurrent access but give the single writer exclusive access to the structure.

I believe it should be possible using two queues. The data in the queues is irrelevant but the numer of messages is.
The first queue would be a readersqueue: Each reader adds a message to the (large enough) queue to indicate that it is reading the struct. It reads a queue message when it is done. An empty queue means there arecurrently no readers accessing the struct. The second queue would be the writerqueue: The writer adds a message to this queue to indicate it wants exclusive access. The readers monitor this queue and when not-empty, stop accessing the struct  (and read a readerqueue-message to let the writer know they are done. When all readers are done, the readersqueue is empty and the writer can continue to update the struct. When updating is done, the writer reads his message from the writersqueue to indicate that the data is accesiblle again to the readers.

I think this may work but browsing through the api, I cannot find functions which block for a queue to get empty. This means that I would have to implement a getmessagecount followed by a yield to wait for the count to get zero. This is not very nice (and quite expensive).

A counting-semaphore might work but thre are no functions (afaik) to block until zero (without actually trying to take the semaphore, just block until someone else takes it).

I hope this makes things a little clearer.

4

davedoors wrote on Thursday, May 23, 2013:

What about:

static unsigned long ReadersCount = 0;
    
void LockToRead( void )
{
    taskENTER_CRITICAL();
    if( ReadersCount == 0 )
    {
        // Obtain the shared mutex. The writing function raises its priority
        // when it accesses the data so the reading task calling this function
        // will only run when the writing function is not running. This call to
        // take the semaphore should therefore ALWAYS pass. Check the
        // return value with a configASSERT() to make sure that condition
        // holds.
        xSemaphoreTakeFromISR();
    }
    // Increment the count of active readers.
    ReadersCount++;
    taskEXIT_CRITICAL();
}
void UnlockRead( void )
{
    taskENTER_CRITICAL();
    
    // Decrement count of active readers.
    ReadersCount--;
    
    if( ReadersCount == 0 )
    {
        // Give back the shared mutex. Use the FromISR function because
        // of the critical section.
        xSemaphoreGiveFromISR();
    }
    
    taskEXIT_CRITICAL();
}
void GetWriteAccess( void )
{
long GotAccess;
    // Ensure the writing task has a higher priority than the reading
    // tasks.
    xTaskPrioritySet( [a priority above the readers priority ] );
    
    // Block to wait for the shared mutex.
    GotAccess = xSemaphoreTake( mutex, block_time );
    
    // Reset priority.
    xTaskPrioritySet( [original priority] );
    
    if( GotAccess == pdPASS )
    {
        // Access data here.
        
        // Give back the shared mutex.
        xSemahoreGive();
    }
}
5

davedoors wrote on Thursday, May 23, 2013:

Correction. The writing task should only reset its priority when it exits the function.

6

hermarcel wrote on Friday, May 24, 2013:

Wow, you even included some code! :slight_smile:

The idea of having only the first reader and the last reader manipulate the readers-semaphore is a good one. I was, however, trying to find a way without the need for critical sections in my code.

Will study on your example.

7

richard_damon wrote on Tuesday, May 28, 2013:

I am not sure that code works, as readers don’t block on anything if the writing task has the lock. Are you assuming that the write task doesn’t need to block when it has the write semaphore?

My thought is that you need 2 different things for signaling, as you have have tasks both waiting to get access to read and write if the semaphore is currently in write mode, and if the semaphore is switched to read mode, you need to restart multiple readers, while still holding the writers at bay, which may be difficult with only a single blocking object.

One thought on how to implement this is using a semaphore (to indicate it is ok to switch between read and write modes) and a mutex to control access to the read counter.

To read lock:
Get Mutex
if ReadCounter == 0 take Semaphore, if fails, release mutex, wait a moment, and go back to the Get Mutex (this is a deadlock breaker)
increment the ReadCounter
Release Mutex

Read Unlock
Get Mutex
decrement counter
if counter == 0, Give semaphore
Release Mutex

Write Lock
Get Semaphore
Get Mutex

Write Unlock
Give Semaphore
Release Mutex 

When there are readers, or a writer, then writers are held off with the semaphore.
When there is a writer, then readers and held off with the mutex.

There is a slight chance of a deadlock if we get a task switch causing both the first reader and a writer to get there first lock and not being able to get their second. One of the paths needs to detect this and back off as shown in the pseudo-code.

8

hermarcel wrote on Tuesday, May 28, 2013:

What about the case that the writer wants access and therefore itnot only waits for all readers to leave, but also delaying new readers from starting?

9

richard_damon wrote on Wednesday, May 29, 2013:

The pseudo code I posted gives readers priority (once you have started reading). It should be possible to implement priority to the write task, so that once the write task blocks waiting to get control, no other read tasks can enter the read lock state.

One outline would be to have one semaphore grabbed by the first read task and release by the last reader, and a second one (or possibly a mutex) grabbed by the write task, which each read task before entering the read lock state needs to grab and release (so they block if the write task has grabbed it. There are still a number of details here that need to be worked out to handle the various race conditions,  so we will either likely need another mutex or use some critical sections to prevent.

10

hermarcel wrote on Friday, September 06, 2013:

Decided to go with the following scenario:

- Readers create a “wait for multiple events”-queue (because several, different, other events are important to the readers as well).
- Readers register themselves (their queue) with the Writer
- Each reader blocks on its queue
- In the writer, the structure updates are in a critical section
- The structure reads, in the readers, are also done from within a critical section

That should do it.

11

hermarcel wrote on Friday, September 06, 2013:

oh and the writer posts a message in each registered queue indicating that the sturcture has been updated.

(still no edit-function… :wink: )