In working on designing a better Read-Write lock mechanism, I realized that it would be very useful to be able to find the priority of the highest priority task waiting to take a given semaphore. The fundamental operation would be to get the task handle of the highest priority task (if any) that is waiting on the Rx side of a Queue, which should be a fairly easy operation to obtain. For completeness, also being able to get the task waiting on the Tx side of the queue would seem reasonable.
It looks to be a fairly short piece of code, and it looks like I should be able to implement it in the additions file that task.c includes (need to look into the details of exactly how the lists are built).
Usage would need some care over race conditions, as just because that task was waiting when the call was made, something might happen (unless prevented) by the time that results is actually used.
Does this sound like something that might get done, and if/when I figure out how to do it would a contribution be acceptable?
How do you intend to arbitrate between murltiple threads of the same priority waiting?
Also, I see a chance of race conditions in which task A obtains the handle of task B for which the contion holds, yet before using it, task C with a higher pri than B also gets suspended on the queue. Pretty ugly scenarios up on the horizon…
Yes, you still need to define whether equal priority tasks are read or write dominate, the key is that you get rid of the case where low priority tasks can starve a high priority task.
Yes, there are race conditions I need to work through in the design, in your example if A is higher than B but lower than C, then that isn’t really a race failure if A adds itself to the existing read-lock, as there WAS a point in time during that period when that was valid behavior, so it is just like A finished its operation before C got in. There may need to be a critical section of some sort around part of the operation. Part of the plan is a double-checking strategy where you see if it might be possible to take the lock without the critical section, then go into a critical section and confirm and take.
Could be a poster case for a conditional critical section?.. Everything else to me smells dangerously like deadlock potential.
I wonder if the possible use cases justify the potential concurrency traps to fall into with an API like that.
Also, judging from previous discussions on this forum, there may be subtle issues when the priority of a thread is explicitly changed or an affected thread is subject to priority inheritance.
I have a gut feeling that your use case should be taken care of by the scheduler, ie instead of delegating the task selection to the application, there should be a way to implement queues not FIFO but FIPRO (possibly as an additional flag to xQueueCreate(). That would at least eliminate the race condition issue.
No “task selection” is taking place. A request for a read lock is seeing if there is a pending write lock that “out-ranks” it, and if so the read will “defer” itself waiting on the read semaphore, which will be taken down by write request is created, and given back when that is done. (So a race that mistakenly defers on it just get granted as it will be up again). I need to finish the algorithm, but I think all races do is perhaps make a task wait for a lower priority operation to clear.
Yes, perhaps if a task comes in for a read lock, sees a task higher priority than it waiting for a write lock and it blocks on the read semaphore, then that write request task loses priority below the reading task, won’t wake up then to join the read lock, but when the current read lock clears, since it is higher priority than the write task, it will put things back to a read lock before the write occurs.
Yes, an “in kernel” read-write lock might be a bit more efficient. But I am not sure it would be THAT much more efficient, as it would need to do something similar, just having more direct access.
I do not look at this issue in terms of efficiency, but rather robustness - the kernel has a chance to do everything it needs to do “atomically” by using the kernel critical section, so by going through a FIPRO wakeup mechanism, there is far less danger of race conditions through conditions that change dynamically (which a task woule need to be aware of).
It would be great to see some (pseudo) code of your implementation of an RW lock. In my implementation, the RW lock is an instance of a group lock in which members of a task group compete for a “pseudo mutex” which allows n tasks of each group (in the RW lock case 1 W and x readers) to execute. Once one task has “opened the door” (claimed the pseudo mutex), all other waiting tasks of that group can come into the door as well, arbitrating themselves among each other via the OSs regular priority mechanism; thus, there is no explicit need for synchronization between tasks of the same group against each other.
For R/W locks, I have yet to come across a use case in which readers should outprioritize a writer; typically, if the single writer does not obtain prioritized access to the R/W lock, what happens is that multiple readers will constantly pass the baton back and forth to each other, practically outstarving the writer. The only meaningful way to handle this imho is to close the open reader’s door once the writer claims access and wait for all readers still in the lock to leave it before allowing the writer in so the writer practically has highest priority access to the lock. It would be interesting to see a use case in which there could be readers on higher and lower priority levels of the writer and the lock being able to honor the priorities.
I will admit that I am still working on the details of what each type of lock/unlock operation needs to do to implement this.
One key point is that the kernel has access to no better critical sections than user code (unless you are in a restricted task) so other than the access to the internals of the structures (which this is a request to be able to access something useful that currently isn’t available), it isn’t a robustness question, but an efficiency question.
Yes, for “Restricted” tasks, the Read-Write locking code would need to be added to the “Privileged” side to work (if you don’t allow restricted tasks to create critical sections).
The use case of wanting SOME readers to have priority is if you have some background loggers running, and a high priority task needing to extract data from the stores. Even if you are in the middle of a number of logging events spooling their data to the backing store, if the high priority task needs to get its data, you don’t want it to have to wait for ALL the loggers to finish, with a priority determination, the loggers can be given priority over “mundane” readers so they can get in to write, but don’t unduly block critical access.
The one thing that making it a kernel object would be it could include priority inheritance which the user design can’t as we need to use Semaphores instead of Mutexes because control “passes” from task to task. If the system kept track of the tasks that have a “Read” lock somehow (which would come with a cost and might require a slightly more complicated way to get a read lock to allow for that, then the kernel could implement some sort of Mutex like priority inheritance to avoid priority inversion on the Read-Write lock.
