Changes between Version 8 and Version 9 of Developer/SMP

Timestamp:

01/13/14 14:15:40 (10 years ago)

Author:

Sh

Comment:

/* Design Issues */

Developer/SMP

@@ -30 +30 @@
 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  =