Changes between Version 8 and Version 9 of Developer/SMP


Ignore:
Timestamp:
Jan 13, 2014, 2:15:40 PM (6 years ago)
Author:
Sh
Comment:

/* Design Issues */

Legend:

Unmodified
Added
Removed
Modified
  • Developer/SMP

    v8 v9  
    3030Get rid of ''_CPU_Context_switch_to_first_task_smp()'' and use
    3131''_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.
     32=  Processor Affinity  =
     33
     34==  Status  ==
     35
     36
     37Thread processor affinity is not supported.
     38==  Future Directions  ==
     39
     40
     41Implement the missing feature.  This consists of two parts
     42
     43 *  the application level API, and
     44 *  the scheduler support.
     45
     46There is no POSIX API available that covers thread processor affinity.  Linux
     47is the de facto standard system for high performance computing so it is
     48obvious to choose a Linux compatible API for RTEMS.  Linux provides
     49[http://man7.org/linux/man-pages/man3/CPU_SET.3.html CPU_SET(3)] to manage sets
     50of processors.  Thread processor affinity can be controlled via
     51[http://man7.org/linux/man-pages/man2/sched_setaffinity.2.html SCHED_SETAFFINITY(2)]
     52and
     53[http://man7.org/linux/man-pages/man3/pthread_setaffinity_np.3.html PTHREAD_SETAFFINITY_NP(3)].
     54RTEMS should provide these APIs and implement them.  It is not possible to use
     55the Linux files directly since they have a pure GPL license.
     56
     57The scheduler support for arbitrary processor affinities is a major challenge.
     58Schedulability analysis for schedulers with arbitrary processor affinities is a
     59current 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>.
     60
     61Support for arbitrary processor affinities may lead to massive thread
     62migrations in case a new thread is scheduled.  Suppose we have M processors
     630, ..., M - 1 and M + 1 threads 0, ..., M.  Thread i can run on processors i
     64and i + 1 for i = 0, ..., M - 2.  The thread M - 1 runs only on processor
     65M - 1.  The M runs only on processor 0.  A thread i has a higher priority than
     66thread i + 1 for i = 0, ..., M, e.g. thread 0 is the highest priority thread.
     67Suppose at time T0 threads 0, ..., M - 2 and M are currently scheduled.  The
     68thread i runs on processor i + 1 for i = 0, ..., M - 2 and thread M runs on
     69processor 0.  Now at time T1 thread M - 1 gets ready.  It casts out thread M
     70since this is the lowest priority thread.  Since thread M - 1 can run only on
     71processor M - 1, the threads 0, ..., M - 2 have to migrate from processor i to
     72processor i - 1 for i = 0, ..., M - 2.  So one thread gets ready and the
     73threads of all but one processor must migrate.  The threads forced to migrate
     74all have a higher priority than the new ready thread M - 1.
     75{| class="wikitable"
     76|+ align="bottom" | Example for M = 3
     77! Time
     78! Thread
     79! Processor 0
     80! Processor 1
     81! Processor 2
     82|-
     83| rowspan="4" | T0
     84| 0
     85|
     86| style="background-color:green" |
     87|
     88|-
     89| 1
     90|
     91|
     92| style="background-color:yellow" |
     93|-
     94| 2
     95|
     96|
     97|
     98|-
     99| 3
     100| style="background-color:red" |
     101|
     102|
     103|-
     104| rowspan="4" | T1
     105| 0
     106| style="background-color:green" |
     107|
     108|
     109|-
     110| 1
     111|
     112| style="background-color:yellow" |
     113|
     114|-
     115| 2
     116|
     117|
     118| style="background-color:purple" |
     119|-
     120| 3
     121|
     122|
     123|
     124|-
     125|}
     126
     127In the example above the Linux Push and Pull scheduler would not find a
     128processor for thread M - 1 = 2 and thread M = 3 would continue to execute even
     129though it has a lower priority.
     130
     131The general scheduling problem with arbitrary processor affinities is a
     132matching problem in a bipartite graph.  There are two disjoint vertex sets.
     133The set of ready threads and the set of processors.  The edges indicate that a
     134thread can run on a processor.  The scheduler must find a maximum matching
     135which fulfills in addition other constraints.  For example the highest priority
     136threads should be scheduled first.  The performed thread migrations should be
     137minimal.  The augmenting path algorithm needs O(VE) time to find a maximum
     138matching, here V is the ready thread count plus processor count and E is the
     139number of edges.  It is particularly bad that the time complexity depends on
     140the ready thread count.  It is an open problem if an algorithm exits that is
     141good enough for real-time applications.
     142
     143[wiki:File:rtems-smp-affinity.png File:rtems-smp-affinity.png]
    32144=  Implementation  =
    33145