Quality RTOS & Embedded Software

 Real time embedded FreeRTOS RSS feed 
Real time embedded FreeRTOS mailing list 
Quick Start Supported MCUs PDF Books Trace Tools Ecosystem TCP & FAT Training




Loading

Structure protection: One writer, mult reader

Posted by Marcel van Lieshout on 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

RE: Structure protection: One writer, mult reader

Posted by Richard on 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.

RE: Structure protection: One writer, mult reader

Posted by Marcel van Lieshout on 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.

RE: Structure protection: One writer, mult reader

Posted by Dave on 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();
}
}

RE: Structure protection: One writer, mult reader

Posted by Dave on May 23, 2013
Correction. The writing task should only reset its priority when it exits the function.

RE: Structure protection: One writer, mult reader

Posted by Marcel van Lieshout on May 24, 2013
Wow, you even included some code! :)

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.

RE: Structure protection: One writer, mult reader

Posted by Richard Damon on 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.

RE: Structure protection: One writer, mult reader

Posted by Marcel van Lieshout on 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?

RE: Structure protection: One writer, mult reader

Posted by Richard Damon on 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.

RE: Structure protection: One writer, mult reader

Posted by Marcel van Lieshout on September 6, 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.

RE: Structure protection: One writer, mult reader

Posted by Marcel van Lieshout on September 6, 2013
oh and the writer posts a message in each registered queue indicating that the sturcture has been updated.

(still no edit-function... ;) )


[ Back to the top ]    [ About FreeRTOS ]    [ Sitemap ]    [ ]




Copyright (C) 2004-2010 Richard Barry. Copyright (C) 2010-2016 Real Time Engineers Ltd.
Any and all data, files, source code, html content and documentation included in the FreeRTOSTM distribution or available on this site are the exclusive property of Real Time Engineers Ltd.. See the files license.txt (included in the distribution) and this copyright notice for more information. FreeRTOSTM and FreeRTOS.orgTM are trade marks of Real Time Engineers Ltd.

Latest News:

FreeRTOS V9.0.0 is now available for download.


Free TCP/IP and file system demos for the RTOS


Sponsored Links

⇓ Now With No Code Size Limit! ⇓
⇑ Free Download Without Registering ⇑


FreeRTOS Partners

ARM Connected RTOS partner for all ARM microcontroller cores

Renesas Electronics Gold Alliance RTOS Partner.jpg

Microchip Premier RTOS Partner

RTOS partner of NXP for all NXP ARM microcontrollers

Atmel RTOS partner supporting ARM Cortex-M3 and AVR32 microcontrollers

STMicro RTOS partner supporting ARM7, ARM Cortex-M3, ARM Cortex-M4 and ARM Cortex-M0

Xilinx Microblaze and Zynq partner

Silicon Labs low power RTOS partner

Altera RTOS partner for Nios II and Cortex-A9 SoC

Freescale Alliance RTOS Member supporting ARM and ColdFire microcontrollers

Infineon ARM Cortex-M microcontrollers

Texas Instruments MCU Developer Network RTOS partner for ARM and MSP430 microcontrollers

Cypress RTOS partner supporting ARM Cortex-M3

Fujitsu RTOS partner supporting ARM Cortex-M3 and FM3

Microsemi (previously Actel) RTOS partner supporting ARM Cortex-M3

Atollic Partner

IAR Partner

Keil ARM Partner

Embedded Artists