Feature request: mutex that allows many readers or one writer

Kernel
1

It frequently occurs that I need to control access to a data structure that holds several related members, to prevent a task from reading its members while it is being updated. If that were to happen then an inconsistent set of members could be read, for example the variable holding the count of used elements in an array might not reflect the actual number of valid elements.

Where the time spent accessing the data structure is small, I can accomplish this by suspending the scheduler before the start of accessing or updating the data, and un-suspending the scheduler after completing it. However, access to the structure sometimes involves iterating through elements of arrays in the structure, so this is undesirable.

It’s typically rare that the data structure gets updated, but there may be several tasks reading the structure to report on it. Therefore, to avoid unnecessary task blocking and switching, I don’t want to enforce mutual exclusion between readers of the structure. What I need is a type of lock that supports two types of lock: read-locks and write-locks. Multiple tasks may hold read-locks on the object, OR one task may hold a write-lock.

I have implemented such a locking structure in my own code, using a combination of atomic variables to handle multiple readers without having to call FreeRTOS mutex functions, and a FreeRTOS Mutex to handle the situation when a write lock is owned or pending. The code is public if anyone wants it. Here’s an abbreviated summary of what I have implemented:

  • A task may request a read lock on the object. The lock will be granted if there is no existing or pending write lock on the object.
  • A task may request a write lock on the object. The lock will be granted if there are no read or write locks currently on the object. Otherwise the lock will be pending and the caller task suspended until these conditions are met.
  • Tasks may relinquish their locks. A task that owns a write-lock on an object may downgrade it to a read lock.

However, my code (and the above specification) doesn’t correctly handle task priorities, except in the case of multiple tasks requesting write locks. For example, it doesn’t allow any new read locks if a write lock is pending, even if the task requesting a read lock has a higher priority than the task with the pending write lock.

It would be great if this functionality could be made an optional feature of FreeRTOS and the priority issues resolved. The main implementation difficulty I see is that the amount of memory needed to track existing and pending locks is not fixed but depends on the maximum number of tasks that can make lock requests.

My current project uses 40+ instances of this type of lock. I can’t be the only person with a use for this type of lock because I see that the Java ReadWriteLock class implements essentially the same functionality.

Please can this be added to the list of features to be included in a future release of FreeRTOS.

2

I agree that this sort of lock has a number of uses. One big problem is to do this “right” requires that you need a chunk of memory for each reader x lock it is using, so either you need dynamic memory (which often isn’t allowed for systems) or you need the Read Lock operation to give a memory chunk to build the list of Current Read Locks. This is needed if you want to implement a priority inheritance on Readers if a higher Priority Write request comes in.

I have seen some implementations that get around this by just not tracking the individual readers, and then arbitrating between Reading and Writing on non-priority based method, either allowing or not allowing a new read lock if a write lock is pending (though you could just allow read locks of task higher in priority to the highest priority pending write lock).

Without the priority inheritance for tasks with a read-lock, all that is needed for the priority based lock would be a way to get the highest priority of tasks waiting on a semaphore, which would be a fairly small addition.

3

I remember there being a long thread on this topic before - some months back now.

These things do get overly burdensome for small devices, but can be simplified provided the simplifications are documented. The existing priority inheritance implementation is already such a simplification. A full priority inheritance scheme would probably require more flash and ram space than the rest of the kernel - but the code is massively simplified by making the documented simplification that a task’s inherited priority will only ever go up, and not be disinherited until it releases all the mutexes it holds. So, the implemented behavior is logically ‘wrong’ if

  1. Task A inherits task B’s medium priority because it holds mutex X.
  2. Task A then inherits task C’s high priority because it holds mutex Y.
  3. Task A returns mutex Y.

…because at that point it should return back to the priority of task B - but inherited priorities can only go up.

4

Meant to also say - we can open a feature request if we can agree a similar simplification for the reader/writer lock implementation.
https://www.freertos.org/roadmap.html
https://github.com/orgs/FreeRTOS/projects/2/views/1

5

From my memory of looking at this in the past, getting readers to inherit the priority of a blocked writer is expensive, as you need a many-many list.

If you don’t need that, then you can use mostly the code of a normal mutex with a slight modification, by adding a reader count to the mutex.

If a reader tries to take the mutex, and the reader count is already greater than 0, it just increments the reader count and can proceed. If the reader count is equal to 0, it take the mutex and increments the reader count, but doesn’t setup the “owner” info, as it doesn’t really own the mutex.

If a reader gives the mutex, then it decrements the reader count, and if it is 0 it frees the mutex and bypasses the ownership checks (as readers don’t inherit).

If a writer tries to take the mutex, it actually take it, and ownership. This means that no readers have taken it. If the mutex is “owned” (so the writer is blocked), but has no owner (because it is owned by readers) there is no inheritance.

When the writer gives the mutex, it releases it normally, except that it needs to unblock ALL tasks waiting on it, as there may be multiple readers blocked and all need to be started.

Because we can’t boost/inherit the priority of readers from a writer waiting, a low priority reader can block a high priority writer if a middle priority task starves it, but writers will inherit from higher priority writers or readers that it is blocking.

None of this deals with the “over-long” inheriting that rtel mentions, the discussion of which was something different, and fixing that would need every task to have a list of mutexes it owns. Not sure fixing that with such a list takes that much code, but does make getting blocked on, or releasing a mutex become a non-trivial operation that might entail scanning a number of lists.

6

I do not feel comfortable with your usage of the word “correct handling of priorities” here. If you look at “priority” as a task property, your use case sort of makes sense. However.

A reader/writer sense only begins to make sense when the number of readers is significantly higher than one, and the greater the number is, the more significant the throughput gain - but on the downside, the higher the risk of the writer being starved out due to a constant stream of readers passing the baton around. Therefore, it makes sense that a pending writer request prevents new readers from entering the lock to allow the writer to gets its share of the protected data - the more so as (now harping on the name of the construct) readers generally have an interest in the most current state of the data, which they can only obtain if the writer updates it in a timely fashion.

What that means in paraphrase is that the writer is granted highest priority - not in terms of its numerical priority but in what the semantics of the sync objects imply. That necessarily clashes with the concept of numerical ordered priorities, and trying to reconcile those two will in my experience open up a Pandora’s box of follow up issues.

Let us assume reader threads A (high pri), B,C and D (low pri) and writer thread W(mid pri). In this case, it seems feasible that A may bypass W’s pending request for the lock if any of B,C and D are already in the lock; however, none of the other threads not in the lock may “sneak in” in the wake of A. So far, so good. However, as there is more than one thread at a priority higher than W, we immediately face the potential issue of W being starved out again, leading to another form of writer starvation. It becomes even murkier when any of B,C and D may be subject to a dynamically raised inherited priority and thus may at runtime unexpectedly starve out W (in an unintended venomenous cooperation with A). There is a “critical mass pivot point” where a combination of too many threads at priorites higher than W along with their timing behavior (freqwuency and lengths of their lock claiming) makes the R/W lock unusable.

I would be very hesitant to provide such a feature. As @rtel points out, at the very least it must be very clearly documented where the limits and pitfalls of such an architecture would be.

7

I think his comment about “correct handling of priorities” is that a write request will block readers making a request after the attempted writer is blocked on the lock if they have a lower priority.

Yes, there are situations with many high-priority readers that might starve the writer, but many high-priority readers might starve it just by their running, even without the lock.

R/W locks without being priority based will, by necessity, either favor writers, normally based on the idea that writers are somewhat rare, and important, and that the writing will tend to reasonably fast. Or they can favor readers, which can only really be done if most readers are very quick.

A priority based R/W lock provides a balance between these, and is roughly based on priority being a measure of the importance of the action being timely, so making it affect the granting of the lock makes some sense. If execution priority doesn’t match the priority for getting the lock (particularly for you writer to too many high-priority readers), then a simple solution is to adjust the writer’s priority up just before taking the Lock, and then resetting itself right after it gets the lock, thus letting it block the readers for getting the lock. Since it needed to be the highest priority task to make the change priority call, it won’t really affect execution timing.

I will agree that it is somewhat of a complicated primitive, and thought should be give to its need, especially since may people might think of them based on the non-priority based rules.

8

You”re not alone David :wink:
I’ve implemented the same type of ‘futex’ and it works pretty good for rather simple use cases and it’s very cheap. For me and up to now it’s good enough.

9

… AND the readers as a whole perform read operations infrequently enough on the average to give a fair chance to the writer. Unfortunately that is non deterministic and therefore unpredictable in an implementation which does not favor the writer.

A poster case here would be a web server where multiple clients would be the readers; a timely update of the data base can only be guaranteed if either the number of client requests can effectively be throttled (which somewhat defeats the idea of a Web server) or the writer gets unconditional priority in accressing the protected data.

Other than that, I agree with your elaborations. Just one more thought: R/W locks are conceptually speaking a limited case of a more generic “group lock” which would allow not 1:many but many:many of theoretically more than two groups of threads in the lock(1). Priorization of such a thing can become very very messy.

(1) Use cases are rare, so this “unlimited group lock” is more of a theoretical construct. A possible somehwat clumsy modelled use case here would be a surgical ward in a hospital where you would allow either an aribtrary number of cleaning staff or medical staff/patients in but no mix.

10

Would a solution be to prioritise writers over readers, but for the writing task to inherit the priority of the highest priority task waiting to read?

11

I believe so, sounds like an adequate strategy to reconcile the two frictional definitions of priority.

Edit: I do not think that it is possible to realize that with the existing sync primitives.

12

But is there a blocked reader if no write-op is in progress ? Given the scenario with only 1 allowed writer.

13

I stumbled across this as well, but I believe the use case is that the writer owns the lock, but a reader with a higher priority queues up in the wait list. So David would want the writer’s priority bumped to prevent some intermediate pri task (not involved in the lock at all) to starve out the entire assembly.

EDIT: If my interpretation of David’s suggestion is correct, I believe he proposes that the entire lock has a collective dynamic priority that is always the highest priority of all tasks participating in the lock at any time, with the subpriorization implied that the writer always takes precedence over the readers.

The more I think about it, the more I like the proposal.

14

A few comments.

There is a fundamental difference in the R/W lock to the group lock, in that the R/W lock, having only a single task possible in the Write lock side, allows for priority inheritance on that side, while a group lock could not implement inheritance without significant changes to way FreeRTOS handles these sort of primitives (you need to keep track of all instances of a many-many relationship, which REQUIRES memory allocations for every connection.

You can’t just prioritize writers, and that says that if a high-priority task comes to make a read request, it can be blocked by a string of low-priority write requests. All locking system have some cases where you can get unbounded blocking, if the system is overwhelmed. Different strategies just change the conditions where that occurs. Priority-based R/W locking says task priority is the priority you want to resolve request at, which often is a reasonable answer. The resolution strategy only matters in the case of multiple contention.

We can not build the priority-based scheme at present because we have no access to the highest priority task currently blocked on a primitive. Having that allows the creation of the priority-based scheme.

To implement inheritance on the Write side, we need a Mutex interface with relaxed semantics, Readers need to be able to take/give the Mutex without becoming “owners”, (which means readers can’t inherit). To allow Readers to inherit priority requires the much bigger change of having a list of owners, which I think gets beyond the scope of what FreeRTOS tries to do.

15

Hi,
for this kind of feature, i use a queue with just 1 element (a big structure in my application).
And related function :

  • xQueuePeek to read
  • xQueueOverwrite to write

This solve read, write access and ensure integrity of the data read.

Regards
pierre

16

Welcome Pierre, thanks for that!

That scheme looks like will work, yet at the cost of copying the structure with every access. There is nothin like a free lunch, I am afraid… :wink:

17

You’re right. This will have the cost of:

  • a copy a the structure each time it is read (or write)
  • a small delay to have the access (the mutex of the queue)
  • a small delay to have the copy of the data (size related)

Regards,
pierre

TANSTAAFL

18

:vulcan_salute: (close enough, I hope)

19

Another BIG cost, is there is no atomic read-modify-write operation available, and it only applies to something that is just a (small) chunk of memory.