= SMP =



[[TOC(Developer/SMP, depth=2)]]

=  Status  =


The [http://en.wikipedia.org/wiki/Symmetric_multiprocessing SMP] support for RTEMS is work in progress.  Basic support is available for ARM, PowerPC, SPARC and Intel x86.
=  Requirements  =


No public requirements exist currently.
=  Design Issues  =

=  Low-Level Start  =

== Status ==


The low-level start is guided by the per-CPU control state
[http://www.rtems.org/onlinedocs/doxygen/cpukit/html/group__PerCPU.html#gabad09777c1e3a7b7f3efcae54938d418 Per_CPU_Control::state].  See also ''_Per_CPU_Change_state()'' and
''_Per_CPU_Wait_for_state()''.

[wiki:File:rtems-smp-low-level-states.png File:rtems-smp-low-level-states.png]
== Future Directions ==


Get rid of ''_CPU_Context_switch_to_first_task_smp()'' and use
''_CPU_Context_restore()'' instead since this complicates things.  This function is only specific on SPARC other architectures like ARM or PowerPC do not need it.  The low-level initialization code of secondary processors can easily set up the processor into the right state.
=  Processor Affinity  =

==  Status  ==


Thread processor affinity is not supported.
==  Future Directions  ==


Implement the missing feature.  This consists of two parts

 *  the application level API, and
 *  the scheduler support.

There is no POSIX API available that covers thread processor affinity.  Linux
is the de facto standard system for high performance computing so it is
obvious to choose a Linux compatible API for RTEMS.  Linux provides
[http://man7.org/linux/man-pages/man3/CPU_SET.3.html CPU_SET(3)] to manage sets
of processors.  Thread processor affinity can be controlled via
[http://man7.org/linux/man-pages/man2/sched_setaffinity.2.html SCHED_SETAFFINITY(2)]
and
[http://man7.org/linux/man-pages/man3/pthread_setaffinity_np.3.html PTHREAD_SETAFFINITY_NP(3)].
RTEMS should provide these APIs and implement them.  It is not possible to use
the Linux files directly since they have a pure GPL license.

The scheduler support for arbitrary processor affinities is a major challenge.
Schedulability analysis for schedulers with arbitrary processor affinities is a
current research topic <ref name="Gujarati2013>Gujarati2013: Arpan Gujarati, Felipe Cerqueira, and Björn Brandenburg. Schedulability Analysis of the Linux Push and Pull Scheduler with Arbitrary Processor Affinities, Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS 2013), July 2013.</ref>.

Support for arbitrary processor affinities may lead to massive thread
migrations in case a new thread is scheduled.  Suppose we have M processors
0, ..., M - 1 and M + 1 threads 0, ..., M.  Thread i can run on processors i
and i + 1 for i = 0, ..., M - 2.  The thread M - 1 runs only on processor
M - 1.  The M runs only on processor 0.  A thread i has a higher priority than
thread i + 1 for i = 0, ..., M, e.g. thread 0 is the highest priority thread.
Suppose at time T0 threads 0, ..., M - 2 and M are currently scheduled.  The
thread i runs on processor i + 1 for i = 0, ..., M - 2 and thread M runs on
processor 0.  Now at time T1 thread M - 1 gets ready.  It casts out thread M
since this is the lowest priority thread.  Since thread M - 1 can run only on
processor M - 1, the threads 0, ..., M - 2 have to migrate from processor i to
processor i - 1 for i = 0, ..., M - 2.  So one thread gets ready and the
threads of all but one processor must migrate.  The threads forced to migrate
all have a higher priority than the new ready thread M - 1.
{| class="wikitable"
|+ align="bottom" | Example for M = 3
! Time
! Thread
! Processor 0
! Processor 1
! Processor 2
|-
| rowspan="4" | T0
| 0
|
| style="background-color:green" |
|
|-
| 1
|
|
| style="background-color:yellow" |
|-
| 2
|
|
|
|-
| 3
| style="background-color:red" |
|
|
|-
| rowspan="4" | T1
| 0
| style="background-color:green" |
|
|
|-
| 1
|
| style="background-color:yellow" |
|
|-
| 2
|
|
| style="background-color:purple" |
|-
| 3
|
|
|
|-
|}

In the example above the Linux Push and Pull scheduler would not find a
processor for thread M - 1 = 2 and thread M = 3 would continue to execute even
though it has a lower priority.

The general scheduling problem with arbitrary processor affinities is a
matching problem in a bipartite graph.  There are two disjoint vertex sets.
The set of ready threads and the set of processors.  The edges indicate that a
thread can run on a processor.  The scheduler must find a maximum matching
which fulfills in addition other constraints.  For example the highest priority
threads should be scheduled first.  The performed thread migrations should be
minimal.  The augmenting path algorithm needs O(VE) time to find a maximum
matching, here V is the ready thread count plus processor count and E is the
number of edges.  It is particularly bad that the time complexity depends on
the ready thread count.  It is an open problem if an algorithm exits that is
good enough for real-time applications.

[wiki:File:rtems-smp-affinity.png File:rtems-smp-affinity.png]
=  Implementation  =

=  = Testing ==


== References ==


<references/>