SMP: Two locking protocols for clustered/partitioned scheduling

[Sebastian Huber]

Hello,

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 [1].  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 [2].

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 [3].  If time permits we will 
also implement Migratory Priority Inheritance [4].

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 
(SCHEDULED, LEADER).

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.

[1] We have currently a severe implementation flaw due to the Giant lock.

[2] Björn B. Brandenburg, Scheduling and Locking in Multiprocessor Real-Time 
Operating Systems, 2011.

[3] 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.

[4] 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.