SMP: Two locking protocols for clustered/partitioned scheduling
sebastian.huber at embedded-brains.de
Wed May 14 08:08:07 UTC 2014
now all ingredients are in place to implement the locking protocols necessary
for proper clustered/partitioned scheduling support.
The benefit of clustered/partitioned scheduling is that each scheduler instance
can operate mostly independent of the other instances . This helps to keep
the worst case latencies under control. On SMP systems with many processors
this can be used to partition the system respecting the cache topology .
One problem with clustered/partitioned scheduling is that priorities of threads
are only meaningful in the context of the scheduler instance of the thread. In
order to allow resource sharing across scheduler boundaries various locking
protocols are available. For our current SMP project we will implement the
Multiprocessor Resource Sharing Protocol - MrsP . If time permits we will
also implement Migratory Priority Inheritance .
Both protocols use a helping strategy. In case a thread blocks on a shared
resource, then it can give the resource owner the right to execute on this
scheduler instance with the priority of the blocked thread.
One way to implement this is to allow a thread to be part of multiple scheduler
instances. For this we have to separate the scheduling relevant data
structures from the thread control block. The first step for this was the
introduction of scheduler nodes. The next step is to enable a thread to
temporarily use multiple scheduler nodes (in case of resource conflicts). This
leads to new node states
- SINGLETON - one-to-one relationship between thread and scheduler node,
- LEADER - a thread has more than one scheduler node, this node has a processor
assigned and the thread executes on this processor, and
- MINION - a thread has more than one scheduler node, this node may have a
processor assigned, but the thread doesn't execute on this processor.
In case a state transition from (SCHEDULED, LEADER) to (READY, MINION) occurs
the thread is denied execution on its previous processor. In this case we can
consult the other scheduler nodes of this thread. If one of them is in the
(SCHEDULED, MINION) state, we can claim the processor and turn it into the new
The next steps are:
1. Simplify _Thread_Change_priority() to get rid of the IN THE AIR state on SMP.
2. Propose the high level API for MrsP.
3. Change the scheduler operations to use scheduler nodes instead of thread
control blocks directly.
4. Add new states to scheduler nodes on SMP.
5. Implement new scheduler operations for SMP enabling the temporary usage of
multiple scheduler instances.
6. Implement MrsP using the new scheduler features.
 We have currently a severe implementation flaw due to the Giant lock.
 Björn B. Brandenburg, Scheduling and Locking in Multiprocessor Real-Time
Operating Systems, 2011.
 A. Burns and A.J. Wellings, A Schedulability Compatible Multiprocessor
Resource Sharing Protocol - MrsP, Proceedings of the 25th Euromicro Conference
on Real-Time Systems (ECRTS 2013), July 2013.
 B. Brandenburg and A. Bastoni, The Case for Migratory Priority Inheritance
in Linux: Bounded Priority Inversions on Multiprocessors, Proceedings of the
14th Real-Time Linux Workshop (RTLWS 2012), pp. 67-86. Real-Time Linux
Foundation, October 2012.
Sebastian Huber, embedded brains GmbH
Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : +49 89 189 47 41-16
Fax : +49 89 189 47 41-09
E-Mail : sebastian.huber at embedded-brains.de
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
More information about the devel