/* * 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 #include #include #include /* * 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; } }