Priority-boosting of Linux-kernel RCU implementations to support small-memory systems

Registered by Paul McKenney

In preemptible RCU, as you would expect from the name, it is possible for a low-priority thread to be preempted in an RCU read-side critical section. It is also possible that a set of high-priority real-time threads, one per CPU, might prevent the preempted thread from executing for an extended period of time. Because RCU grace periods by definition cannot complete until all pre-existing RCU read-side critical sections complete, no subsequent RCU grace period can complete until the preempted task is allowed to run. If no subsequent RCU grace period can complete, then all memory that is waiting for an RCU grace period to complete must continue to wait. Therefore, if the low-priority thread remains preempted for long enough, the system will run out of memory. This scenario is of less concern on large-memory systems, as their large memories allow them to tolerate this situation persisting for a relatively long time. However, small-memory systems can run out of memory quite quickly, and so this scenario is quickly transitioning from a theoretical failure mode to a very real one. The solution is to detect when the current grace period is taking too long due to preempted RCU readers, and to then boost the priority of those readers. This approach is similar to the priority-inheritance mechanisms that has long been used avoid priority inversion for locking.

Blueprint information

Loïc Minier
Paul McKenney
Needs approval
Paul McKenney
Series goal:
Milestone target:
milestone icon backlog
Completed by
Mounir Bsaibes

Related branches



[paulmck] Negotiate interface to scheduler: INPROGRESS
[paulmck] Detailed design: DONE
[paulmck] Implement rcutorture changes: DONE
[paulmck] Fix performance bugs in TINY_PREEMPT_RCU's scheduler-clock interrupt handler: DONE
[paulmck] Move RCU's softirq processing to a kthread to permit priority boosting: DONE
[paulmck] Implement RCU priority boosting in TINY_PREEMPT_RCU: DONE (in mainline)
[paulmck] Add tracing to TINY_PREEMPT_RCU priority boosting [NEW]: DONE (in mainline)
[paulmck] Update TREE_PREEMPT_RCU to use a single ->blkd_tasks list: INPROGRESS (coded, passes rcutorture testing)
[paulmck] Implement RCU priority boosting in TREE_PREEMPT_RCU: INPROGRESS (coded, testing in progress)
[paulmck] Update TINY_PREEMPT_RCU boosting based on lessons learned in TREE_PREEMPT_RCU: TODO
[paulmck] Run tests on ARM hardware: TODO
[paulmck] Update Documentation/RCU/ in-tree documentation: TODO
[paulmck] Produce community documentation (e.g., LWN article): TODO


Work Items

This blueprint contains Public information 
Everyone can see this information.


No subscribers.