diff options
Diffstat (limited to 'cpukit/score/src/schedulersimplesmpschedule.c')
-rw-r--r-- | cpukit/score/src/schedulersimplesmpschedule.c | 246 |
1 files changed, 246 insertions, 0 deletions
diff --git a/cpukit/score/src/schedulersimplesmpschedule.c b/cpukit/score/src/schedulersimplesmpschedule.c new file mode 100644 index 0000000000..07d149f43b --- /dev/null +++ b/cpukit/score/src/schedulersimplesmpschedule.c @@ -0,0 +1,246 @@ +/* + * Scheduler Simple SMP Handler / Schedule + * + * COPYRIGHT (c) 2011. + * On-Line Applications Research Corporation (OAR). + * + * The license and distribution terms for this file may be + * found in found in the file LICENSE in this distribution or at + * http://www.rtems.com/license/LICENSE. + * + * $Id$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include <rtems/system.h> +#include <rtems/score/smp.h> +#include <rtems/score/schedulersimplesmp.h> + +#include <stdio.h> + +/* + * The following is very useful on the scheduler simulator when debugging + * this algorithm. You are not likely to be able to print like this when + * running on a real system. + * + * NOTE: This is NOT using RTEMS_DEBUG because this is not consistency + * checking and is VERY VERY noisy. It is just for debugging + * the algorithm. + */ +#if 0 +#define D(format,...) printk( format, __VA_ARGS__) +#else +#define D(format,...) +#endif + +/** + * @brief Assign Heir Thread to CPU + * + * This method attempts to find a core for the thread under consideration + * (@a consider) to become heir of. The placement takes into account + * priority, preemptibility, and length of time on core. + * + * Combined with the loop in _Scheduler_simple_smp_Schedule, it attempts + * to faithfully implement the behaviour of the Deterministic Priority + * Scheduler while spreading the threads across multiple cores. + * + * @param[in] consider is the thread under consideration. This means + * that the method is looking for the best core to place it + * as heir. + * + * @return This method returns true if it was able to make @a consider + * the heir on a core and false otherwise. When this returns + * false, there is no point in attempting to place an heir of + * of lower priority. + */ + +bool _Scheduler_simple_smp_Assign( + Thread_Control *consider +) +{ + bool found; /* have we found a cpu to place it on? */ + uint32_t found_cpu; /* CPU to place this thread */ + bool blocked; /* CPU has blocked thread? */ + Thread_Control *pheir; /* heir on found cpu to potentially replace */ + Thread_Control *h; + Thread_Control *e; + uint32_t cpu; + + /* + * Initialize various variables to indicate we have not found + * a potential core for the thread under consideration. + */ + found = false; + blocked = false; + found_cpu = 0; + pheir = NULL; + + for ( cpu=0 ; cpu < _SMP_Processor_count ; cpu++ ) { + D( "SCHED CPU=%d consider=0x%08x ASSIGN\n", cpu, consider->Object.id ); + + /* + * If the thread under consideration is already executing or + * heir, then we don't have a better option for it. + */ + e = _Per_CPU_Information[cpu].executing; + if ( e == consider ) { + D( "SCHED CPU=%d Executing=0x%08x considering=0x%08x ASSIGNED\n", + cpu, e->Object.id, consider->Object.id ); + return true; + } + + if ( !_States_Is_ready( e->current_state ) ) { + pheir = h; + found_cpu = cpu; + found = true; + blocked = true; + D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x BLOCKED\n", + cpu, h->Object.id, consider->Object.id ); + continue; + } + + h = _Per_CPU_Information[cpu].heir; + if ( h == consider ) { + D( "SCHED CPU=%d Heir=0x%08x considering=0x%08x ASSIGNED\n", + cpu, h->Object.id, consider->Object.id ); + return true; + } + + if ( blocked ) + continue; + + /* + * If we haven't found a potential CPU to locate the thread + * under consideration on, we need to consider if this is a + * more important threads first (e.g. priority <). + * + * But when a thread changes its priority and ends up at the end of + * the priority group for the new heir, we also need to schedule + * a new heir. This is the "=" part of the check. + */ + if ( !found ) { + if ( consider->current_priority <= h->current_priority ) { + pheir = h; + found_cpu = cpu; + found = true; + D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x MAYBE #1\n", + cpu, h->Object.id, consider->Object.id ); + } + + continue; + } + + /* + * Past this point, found is true. + */ + + /* + * If we have found a potential CPU on which to make the + * thread under consideration the heir, then we need to + * check if the current CPU is a more appropriate place + * for this thread to be placed. + * + * Check 1: heir of potential CPU is more important + * then heir of current CPU. We want to + * replace the least important thread possible. + */ + if ( h->current_priority > pheir->current_priority ) { + pheir = h; + found_cpu = cpu; + D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x MAYBE #2\n", + cpu, h->Object.id, consider->Object.id ); + continue; + } + + if ( h->current_priority > pheir->current_priority ) + continue; + + /* + * If heir of potential CPU and of the current CPU are of the SAME + * priority, then which has been running longer? + * + * Which CPU has had its executing thread longer? + */ + if ( _Timestamp_Less_than( + &_Per_CPU_Information[cpu].time_of_last_context_switch, + &_Per_CPU_Information[found_cpu].time_of_last_context_switch + ) ) { + pheir = h; + found_cpu = cpu; + D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x LONGER\n", + cpu, h->Object.id, consider->Object.id ); + continue; + } + + /* + * If we are looking at a core with a non-preemptible thread + * for potential placement, then favor a core with a preeemtible + * thread of the same priority. This should help avoid priority + * inversions and let threads run earlier. + */ + if ( !pheir->is_preemptible && h->is_preemptible ) { + pheir = h; + found_cpu = cpu; + D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x PREEMPTIBLE\n", + cpu, h->Object.id, consider->Object.id ); + continue; + + } + } + + /* + * If we found a cpu to make this thread heir of, then we + * need to consider whether we need a dispatch on that CPU. + */ + if ( found ) { + e = _Per_CPU_Information[found_cpu].executing; + D( "SCHED CPU=%d executing=0x%08x considering=0x%08x FOUND\n", + found_cpu, e->Object.id, consider->Object.id ); + _Per_CPU_Information[found_cpu].heir = consider; + if ( !_States_Is_ready( e->current_state ) ) { + D( "SCHED CPU=%d executing not ready dispatch needed\n", found_cpu); + _Per_CPU_Information[found_cpu].dispatch_necessary = true; + } else if ( consider->current_priority < e->current_priority ) { + if ( e->is_preemptible || consider->current_priority == 0 ) { + D( "SCHED CPU=%d preempting\n", found_cpu); + _Per_CPU_Information[found_cpu].dispatch_necessary = true; + } + } + } + + /* + * Return true to indicate we changed an heir. This indicates + * scheduling needs to examine more threads. + */ + return found; +} + +/* + * Reschedule threads -- select heirs for all cores + */ +void _Scheduler_simple_smp_Schedule(void) +{ + Chain_Control *c; + Chain_Node *n; + Thread_Control *t; + uint32_t cpu; + + c = (Chain_Control *)_Scheduler.information; + cpu = 0; + + /* + * Iterate over the first N (where N is the number of CPU cores) threads + * on the ready chain. Attempt to assign each as heir on a core. When + * unable to assign a thread as a new heir, then stop. + */ + for (n = _Chain_First(c); !_Chain_Is_tail(c, n); n = _Chain_Next(n)) { + t = (Thread_Control *)n; + if ( !_Scheduler_simple_smp_Assign( t ) ) + break; + if ( ++cpu >= _SMP_Processor_count ) + break; + } +} |