Multiple task synchronization problem

Kernel
1

Hi All,
I’m really stuck and need some advice.

I have a shared resource and a management task that periodically allows access to this shared resource.
There can be multiple “user” tasks with random priorities that want access to the resource at random times. They all need to wait for the management task to allow them access. Once the management task allows access, it needs to then ensure it waits for all “user” tasks to do their thing before the management task disallows access again.

I have this implemented with and event group where all “user” tasks begin waiting for an even. Sometime later, the management task pulses the event, therefor unblocking all tasks.
xEventGroupSync(UserEvt, EVT_GO, EVT_GO, 0);
Note 1: In my case, I don’t care that all tasks unblock at the same time, the shared resource is fine with this.
Note 2: If a new task shows up and waits on the event 1 cpu cycle after the sync, it is forced to wait until next time and this is perfectly acceptable.
Note 3: I’m using Sync instead of Set, because if the management task simply “sets” the event, there may be multiple user tasks with higher priorities that just take over the CPU and the management task never gets the chance the “clear” the event.

The problem is that the management task has to wait for all “user” tasks to complete and there is no way of knowing how many were unblocked. I have tried all sorts of solutions like counting semaphores, event groups, queues, suspending tasks, and all are plagued with race conditions.

Is there a clean and elegant way this can be done that will not depend on task priorities? I’m out of ideas, my best bet for this would be to modify the kernel and make Sync return how many task were unblocked and I really don’t want to do that.
Help !

2

Any chance that the user tasks de/register to the shared resource ? That would provide the required information (e.g. just the number of user tasks). Maybe a simple atomic counter would be sufficient as de/register control object.

1 Like
3

I did consider this, and it is plausible, but de/registration has to happen on every cycle of every user task and I have a bit of a performance issue with that. There also needs to be a sort of a time slot in which registration is allowed because once the management task allows access, all other registration attempts need to be deferred until later.
Let’s imagine the following:
1 - User Task registers by let’s say vTaskSuspendAll(); var++; xTaskResumeAll();
2 - User Task waits for and event …
3 - Management task Syncs and remembers the count of registered tasks
4 - User task does work
5 - User task signals done ( somehow )
6 - Management task does a SemaphoreTake up to “var” times win an attempt to wait for all user tasks.

Do you see the dead-lock between points 1 and 2? The user task might have registered, but the event might come between 1 and 2 and now it never sees the event while the management task has seen the registration and is waiting for the user task.
A way around this is for the management task to Set the event instead of Sync it, but then if the user task is cyclic AND with higher priority than management, it will keep going 1 through 5 forever and never allow the management task to unblock and get a chance to clear the event.

4

How about if the management task not only allows access but also performs the “thing” on behalf of user tasks? User tasks can send some sort of command on a queue to the management task and management task will process them when it wants to allow access to the resource.

5

This approach will work great and the management task can have 2 queues and can switch them atomically so that while one queue enqueues tasks, the other is being processed. Yes this can definitely work. It will be hard to implement because now I have to move user code into my management task or do some kind of function pointers… It’s going to be messy but it absolutely is a valid way around my conundrum! Thanks!

p.s. I’d still like to hear other ideas on the original problem if anyone has them.

6

I thought of just an initial registration (on task creation/init). Seems I didn’t get the whole picture that you want/need to know the current (?) set of tasks waiting for the resource when the management tasks decides to publish an update of the resource ?
I afraid I know too little about your design/requirements… :frowning:

7

@hs2, at this point in my struggle, any brainstorming is helpful.

I just implemented a solution similar to what you suggested, but it is definitely not elegant.

The management task has the following:

struct TASK_SYNC_HELPER
{
	xQueueHandle			q;
	EventGroupHandle_t		e;
};
typedef struct TASK_SYNC_HELPER TaskSyncronizer_t;

static TaskSyncronizer_t	TSync[2];
static int8_t				tSyncIndex = 0;

Every time the management task decides to allow access, it toggles which struct get’s used:

// Swap the task synchronizer structs
int8_t TSyncHandleIndex;
vTaskSuspendAll();
TSyncHandleIndex = tSyncIndex;
tSyncIndex = (tSyncIndex + 1) & 1;
xTaskResumeAll();
// From this point on, all registrations will be on the other queue

// Signal all tasks that have registered
xEventGroupSetBits( TSync[TSyncHandleIndex].e, UAPP_EVT_RAM_STABLE );
				
// Consume the queue
xSemaphoreHandle s; 
int8_t SyncTaskCount = 0;
while ( pdTRUE == xQueueReceive( TSync[TSyncHandleIndex].q, &s, 0))
{
    SyncTaskCount++;
    // We have the semaphore that the task will use to signal when it's done.
    xSemaphoreTake( s, portMAX_DELAY);
}
xEventGroupClearBits( TSync[TSyncHandleIndex].e, UAPP_EVT_RAM_STABLE );

As you might notice, the event no longer get’s Sync-ed, but is Set. This prevents the user tasks from sending to the queue and then missing the event.
As you can see, the management task just depletes the queue. What is in the queue is a semaphore that the user tasks give when they are gone.

Here is what the tasks do when they want to “register” and wait for the common resource:

int8_t CurrIndex;
vTaskSuspendAll();
CurrIndex = tSyncIndex;
xQueueSend(TSync[CurrIndex].q, &DoneSemaphore ,0 );
// Once the above completes, we will get the event because the management task will be waiting on our semaphore before clearing the event.
xTaskResumeAll();

// Wait for the event	
EventBits_t RetBits = xEventGroupWaitBits( TSync[CurrIndex].e, EventMask, pdTRUE, pdTRUE, uiMaxWaitTicks);

The above has a bunch of error checking removed for brevity.
When the user task gets the event, it goes to work and when it’s done…

xSemaphoreGive( DoneSemaphore );

As I said, this is quite ugly and all the error-checking that needs to happen is annoying, but I just tried it and it worked once in a row :smiley:

Anyways, I’d love to hear a better solution. I’m sharing my current one for others that might search the forums. Thank you all, and if anyone has a better idea, by all means, let me know.

8

Could it be that what you are looking for is really a reader-writer lock in disguise? I have an implementation for an r/w lock on FreeRTOS in casevthat"s what you are,looking for.

1 Like
9

I had to pause and go read up on what a reader-writer lock is, but it sounds like maybe my problem is a reader-writer lock in disguise…
Let’s see if I understand what you mean…
Lets designate the writer to be what I’m calling the “management” thread.
Let’s also designate the readers to me what I’m calling the “user” threads.

When I say that the management thread does not want to allow access, that would be the writer, writing, so no reader would be allowed to read, correct?
And consequently, when my management thread allows access, that would constitute the writer being done and the readers can then read ( or do whatever ) in parallel… correct?

But how does a reader-writer lock handle a writer that wants to start writing while readers are reading? They can’t just get suspended… Is there a mechanism that allows the readers to finish what they are doing before the writer locks them out?

I’ll continue exploring the concept. If you have an implementation you can share, please do. I’d love to check it out.

1 Like
10

yes, that’s pretty much what an r/w lock does… it’s an asymmetric lock allowing either one thread of one functional group (the writer) or an arbeitrary number of threads of another functional group (the readers) access. So as long as there is at least one reader active, the writer is suspended.

I published code for a compound FreeRTOS R/W lock as a sample for the chapter on synchronization in my book. Unfortunately the book is in German (my publisher wasn’t interested in a translation), but the code is fairly self explanatory. You’ll find it here:

Embedded Controller - Grundlagen und praktische Umsetzung für industrielle Anwendungen | Rüdiger R. Asche | Springer

Scroll down about halfway, there’ll be an embedded link called “Zusatzmaterial” (supplementary material). It’s not protected. There’s a zip file of code you can download. In the chapter 6 subdirectory, there’s a file called rwlock.cpp somewhere down the code tree. It contains the logic to claim and release an r/w mutex either as a reader or a writer.

If you have additional questions about it, please open a new topic or contact me via PM.

11

The requirements sound slightly different than a normal reader-writer lock in that a reader of higher priority than the writer needs to be held off after an access to give the writer a chance to get in, and all readers that were waiting when the writer releases need to get a turn. This is a bit more restrictive that the general case of a normal reader-writer lock.

12

@RAc, thank you so much for the suggestion and source. They gave me a few ideas and also opened my eyes to a concept that I have never used before.
@richard-damon, yes you are absolutely correct, thanks for pointing it out. In my case, I’m also dealing with strictly one writer.

I still don’t have what I’d call an “elegant and efficient” solution, but you have all broadened my understanding and given me options and I really appreciate your insights. I’ll see if I can revise my solution with my new-found knowledge of reader-writer locks.
Thanks again, I think I’m good for now.

1 Like
13

One thought, untested, is to use two events like a master slave flip flop. Start with the first open and the second close. Readers first check the first event (but don’t clear it), and if open start a critical section, confirm the first is still open, increment a counter and then wait on the second.

When the writer want to start the readers, it first first event, and then opens the second and then waits for a signal.

When it opens the second event the readers that got past the first gate run, and when they are done the decrement the counter in a critical section, and if it goes to zero, then they all are done and the last out closes the second gate and signals the writer (in the critical section). That task or the writer then opens the first event.

The code to enter and leave the read access should be an API function that all the task use to avoid duplicate code.

The writer can monitor the counter to see if any readers are waiting to start the cycle over.

14

@hs2 ,
After reading all the suggestions here, I re-evaluated my messy solution and what I came up with made me realize, you were right from the very beginning, I just misinterpreted your reply.
I guess the reader-writer lock thing simply gave me a different perspective and here’s what I just came up with:

User ( reader ) loop:

... some precursory work ...
/* registration phase */
Take GlobalMutex
UserTaskCounter ++
Give GlobalMutex
/* At this point, the task is registered, meaning once it's allowed to
access the common resource, the management task will wait for this task to complete. */

Wait EVT_GO /* All user tasks that registered block here */
do_work_on_the_common_resource()
/* Signal the management task that we are done */
Give GlobalCountingSemaphore

Management ( writer ) loop:

... some precursory work ...
Take GlobalMutex /* registration is suspended now */
c = UserTaskCounter /* remember how many user tasks had registered */
UserTaskCounter = 0
Set EVT_GO /* This will unblock all user tasks. */
/* Allow for all users to finish regardless of their priority
and the exact instruction they were preempted at.*/
while( c-- ) 
    Take GlobalCountingSemaphore
/* Everybody is done, clear the event as we are about to allow registration again. */
Set EVT_GO
Give GlobalMutex

@hs2, as you can see, you suggested an atomic registration, I just misinterpreted it as incrementing a variable in with task suspended instead of being guarded by a mutex.

The key point above is sort of a double-lock where even if the management task has the lowest priority, it cannot be locked out with the event set. I think this solution is quite clean and should work even though I’ll have to wait until tomorrow to verify it.

p.s. @richard-damon , we were posting at the same time. I need to read your post a couple more times and think about it, but definitely thanks for sharing your thoughts.

2 Likes
15

I think your request for brainstorming was a good idea and very interesting for all of us :slightly_smiling_face:
Good luck Emil :+1:

16

one thought is that the manager should run at a higher priority than all consumer threads. this may solve what I understood to be the issue between 1 and 2 abov e.
I didn’t try to understand in detail, but I’d approach this with a job queue. The management task would put tokens in this job queue for each registered thread. The token could be a queue that the threads are waiting on. If the management thread is running at a higher priority it can put all tokens in the queue before any worker thread runs. The workers would register when they are done. when the management thread wakes it would check that the job queue is empty before enabling any new registrants to get new event.

17

Well yes, if this modelled the control flow appropriately, it would be a perfect solution. Yet from Emil’s initial description I was under the impression that this is not a master-worker architecture (meaning one master task assigns sub jobs and coordinates the workers) but instead, all threads run autonomously and only need to syncronize in an unusual fashion, in which case the token assignment architecture would be awkward.

It all boils down to modelling the underlying conterol flow of the issue at hand as closely as possible and then selecting the best tool from the tool box, just like in plumbing (well, it’s not exactly the same thing :wink: but some similarities spring to mind).

2 Likes
18

@eorojas, Thanks for the comment.
I’d like to point out though that it is my personal belief that if an algorithm is reliant on specific task priorities, it is an inferior one. I simply try to avoid such solutions if I have a choice. Just imagine that 2-3 years later, the original developer or someone else expands on the idea and they don’t realize or have forgotten the important role of task priorities and the algorithm stops working.
On the subject of queues… Yes you may notice my original solution involved queues and the tokens inside were semaphores. This worked, but it involves inordinate amounts of allocating and free-ing recources and a bunch of error handling cases. The solution was fairly slow and clunky and the implementation was prone to errors. Not something I’d call elegant.

@RAc was absolutely correct, my case was not a case of master-worker.

In reality, what I call “user” tasks are simply communication tasks that are implementing different network protocols. Those tasks need read/write access to a piece of memory and I have decided to allow them to read/write in parallel. If two write in the same part of the ram, it’s not my problem.
There is however a “management” task that knows when the piece of shared RAM is in a stable state and may be accessed by those communication task and it is the management task that provides this sort of rendezvous. The user tasks cannot be allowed to lock out the management task under any circumstance regardless of how fast they are and how high their priority is.

I hope the above shed a little more light on what I’m working on. I can’t go into more details.
@eorojas , I hope you can look at my final solution and realize how much faster and fool-proof the algorithm is. There are not a lot of resources to keep track of, so a bug-free implementation is easy.

One last note on performance if anyone has a similar use case… The algorithm in my last post can probably be improved by substituting the counting semaphore with task notifications, but that is an exercise for another day.

Thank you all!

19

@epopov, yes, I just took to time to understand your solution and consequently the type of problem and it seems like a good solution to me based on your requirements.