From ba7bc099a86deef7c5b0f00887a315262e8f7974 Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Tue, 17 May 2011 19:48:44 +0000 Subject: 2011-05-17 Joel Sherrill PR 1789/cpukit * sapi/include/confdefs.h, score/Makefile.am, score/preinstall.am: Add Simple SMP Priority Scheduler. * score/include/rtems/score/schedulersimplesmp.h, score/src/schedulersimplesmpblock.c, score/src/schedulersimplesmpschedule.c, score/src/schedulersimplesmpunblock.c: New files. --- cpukit/ChangeLog | 10 + cpukit/sapi/include/confdefs.h | 38 +++- cpukit/score/Makefile.am | 17 +- .../score/include/rtems/score/schedulersimplesmp.h | 105 +++++++++ cpukit/score/preinstall.am | 8 +- cpukit/score/src/schedulersimplesmpblock.c | 28 +++ cpukit/score/src/schedulersimplesmpschedule.c | 246 +++++++++++++++++++++ cpukit/score/src/schedulersimplesmpunblock.c | 31 +++ 8 files changed, 473 insertions(+), 10 deletions(-) create mode 100644 cpukit/score/include/rtems/score/schedulersimplesmp.h create mode 100644 cpukit/score/src/schedulersimplesmpblock.c create mode 100644 cpukit/score/src/schedulersimplesmpschedule.c create mode 100644 cpukit/score/src/schedulersimplesmpunblock.c (limited to 'cpukit') diff --git a/cpukit/ChangeLog b/cpukit/ChangeLog index a414d7352d..7615aae0c1 100644 --- a/cpukit/ChangeLog +++ b/cpukit/ChangeLog @@ -1,3 +1,13 @@ +2011-05-17 Joel Sherrill + + PR 1789/cpukit + * sapi/include/confdefs.h, score/Makefile.am, score/preinstall.am: Add + Simple SMP Priority Scheduler. + * score/include/rtems/score/schedulersimplesmp.h, + score/src/schedulersimplesmpblock.c, + score/src/schedulersimplesmpschedule.c, + score/src/schedulersimplesmpunblock.c: New files. + 2011-05-16 Ralf Corsépius * libnetworking/Makefile.am: Reformat. diff --git a/cpukit/sapi/include/confdefs.h b/cpukit/sapi/include/confdefs.h index e10b615e8b..a3d3b21507 100644 --- a/cpukit/sapi/include/confdefs.h +++ b/cpukit/sapi/include/confdefs.h @@ -569,9 +569,10 @@ rtems_fs_init_functions_t rtems_fs_init_helper = * * The scheduler configuration allows an application to select the * scheduling policy to use. The supported configurations are: - * CONFIGURE_SCHEDULER_USER - user provided scheduler - * CONFIGURE_SCHEDULER_PRIORITY - Deterministic Priority Scheduler - * CONFIGURE_SCHEDULER_SIMPLE - Light-weight Priority Scheduler + * CONFIGURE_SCHEDULER_USER - user provided scheduler + * CONFIGURE_SCHEDULER_PRIORITY - Deterministic Priority Scheduler + * CONFIGURE_SCHEDULER_SIMPLE - Light-weight Priority Scheduler + * CONFIGURE_SCHEDULER_SIMPLE_SMP - Simple SMP Priority Scheduler * * If no configuration is specified by the application, then * CONFIGURE_SCHEDULER_PRIORITY is assumed to be the default. @@ -589,11 +590,20 @@ rtems_fs_init_functions_t rtems_fs_init_helper = #error "CONFIGURE_ERROR: CONFIGURE_SCHEDULER_USER requires CONFIGURE_SCHEDULER_USER_ENTRY_POINTS" #endif +#if !defined(RTEMS_SMP) + #undef CONFIGURE_SCHEDULER_SIMPLE_SMP +#endif + /* If no scheduler is specified, the priority scheduler is default. */ #if !defined(CONFIGURE_SCHEDULER_USER) && \ !defined(CONFIGURE_SCHEDULER_PRIORITY) && \ - !defined(CONFIGURE_SCHEDULER_SIMPLE) - #define CONFIGURE_SCHEDULER_PRIORITY + !defined(CONFIGURE_SCHEDULER_SIMPLE) && \ + !defined(CONFIGURE_SCHEDULER_SIMPLE_SMP) + #if defined(RTEMS_SMP) && defined(CONFIGURE_SMP_APPLICATION) + #define CONFIGURE_SCHEDULER_SIMPLE_SMP + #else + #define CONFIGURE_SCHEDULER_PRIORITY + #endif #endif /* @@ -630,6 +640,24 @@ rtems_fs_init_functions_t rtems_fs_init_helper = #define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER (0) #endif +/* + * If the Simple SMP Priority Scheduler is selected, then configure for it. + */ +#if defined(CONFIGURE_SCHEDULER_SIMPLE_SMP) + #include + #define CONFIGURE_SCHEDULER_ENTRY_POINTS SCHEDULER_SIMPLE_SMP_ENTRY_POINTS + + /** + * Define the memory used by the Simple SMP Scheduler + * + * NOTE: This is the same as the Simple Scheduler + */ + #define CONFIGURE_MEMORY_FOR_SCHEDULER ( \ + _Configure_From_workspace( sizeof(Chain_Control) ) \ + ) + #define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER (0) +#endif + #if defined(CONFIGURE_SCHEDULER_USER) #define CONFIGURE_SCHEDULER_ENTRY_POINTS \ CONFIGURE_SCHEDULER_USER_ENTRY_POINTS diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 585563a12e..38df872557 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -12,7 +12,11 @@ SUBDIRS = cpu include_rtemsdir = $(includedir)/rtems include_rtems_HEADERS = include/rtems/debug.h include/rtems/system.h \ - include/rtems/seterr.h include/rtems/bspsmp.h + include/rtems/seterr.h + +if HAS_SMP +include_rtems_HEADERS += include/rtems/bspsmp.h +endif include_rtems_scoredir = $(includedir)/rtems/score @@ -36,14 +40,13 @@ include_rtems_score_HEADERS = include/rtems/score/address.h \ include/rtems/score/timestamp64.h include/rtems/score/tod.h \ include/rtems/score/tqdata.h include/rtems/score/userext.h \ include/rtems/score/watchdog.h include/rtems/score/wkspace.h \ - include/rtems/score/cpuopts.h include/rtems/score/basedefs.h + include/rtems/score/cpuopts.h include/rtems/score/basedefs.h if HAS_SMP include_rtems_score_HEADERS += \ include/rtems/score/smplock.h include/rtems/score/smp.h endif - if HAS_PTHREADS include_rtems_score_HEADERS += include/rtems/score/corespinlock.h \ include/rtems/score/corerwlock.h @@ -56,6 +59,10 @@ include_rtems_score_HEADERS += include/rtems/score/mpci.h \ include/rtems/score/threadmp.h endif +if HAS_SMP +include_rtems_score_HEADERS += include/rtems/score/schedulersimplesmp.h +endif + ## inline include_rtems_score_HEADERS += inline/rtems/score/address.inl \ inline/rtems/score/chain.inl inline/rtems/score/corebarrier.inl \ @@ -97,7 +104,9 @@ libscore_a_SOURCES += src/mpci.c src/objectmp.c src/threadmp.c endif if HAS_SMP -libscore_a_SOURCES += src/smp.c src/smplock.c +libscore_a_SOURCES += src/smp.c src/smplock.c \ + src/schedulersimplesmpblock.c src/schedulersimplesmpschedule.c \ + src/schedulersimplesmpunblock.c endif ## CORE_APIMUTEX_C_FILES diff --git a/cpukit/score/include/rtems/score/schedulersimplesmp.h b/cpukit/score/include/rtems/score/schedulersimplesmp.h new file mode 100644 index 0000000000..0f57fcec9e --- /dev/null +++ b/cpukit/score/include/rtems/score/schedulersimplesmp.h @@ -0,0 +1,105 @@ +/** + * @file rtems/score/schedulersimplesmp.h + * + * This include file contains all the constants and structures associated + * with the manipulation of threads on a simple-priority-based ready queue. + * This implementation is SMP-aware and schedules across multiple cores. + * + * The implementation relies heavily on the Simple Scheduler and + * only replaces a few routines from that scheduler. + */ + +/* + * Copyright (C) 2011 On-Line Applications Research Corporation (OAR). + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.com/license/LICENSE. + * + * $Id$ + */ + +#ifndef _RTEMS_SCORE_SCHEDULERSIMPLE_SMP_H +#define _RTEMS_SCORE_SCHEDULERSIMPLE_SMP_H + +/** + * @addtogroup ScoreScheduler + * + * The Simple SMP Scheduler attempts to faithfully implement the + * behaviour of the Deterministic Priority Scheduler while spreading + * the threads across multiple cores. It takes into account thread + * priority, preemption, and how long a thread has been executing + * on a core as factors. From an implementation perspective, it + * relies heavily on the Simple Priority Scheduler. + */ +/**@{*/ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include + +/** + * Entry points for Scheduler Simple SMP + */ +#define SCHEDULER_SIMPLE_SMP_ENTRY_POINTS \ + { \ + _Scheduler_simple_Initialize, /* initialize entry point */ \ + _Scheduler_simple_smp_Schedule, /* schedule entry point */ \ + _Scheduler_simple_Yield, /* yield entry point */ \ + _Scheduler_simple_smp_Block, /* block entry point */ \ + _Scheduler_simple_smp_Unblock, /* unblock entry point */ \ + _Scheduler_simple_Allocate, /* allocate entry point */ \ + _Scheduler_simple_Free, /* free entry point */ \ + _Scheduler_simple_Update, /* update entry point */ \ + _Scheduler_simple_Enqueue, /* enqueue entry point */ \ + _Scheduler_simple_Enqueue_first, /* enqueue_first entry point */ \ + _Scheduler_simple_Extract /* extract entry point */ \ + } + +/** + * @brief Scheduler Simple SMP Schedule Method + * + * This routine allocates ready threads to individual cores in an SMP + * system. If the allocation results in a new heir which requires + * a dispatch, then the dispatch needed flag for that core is set. + */ +void _Scheduler_simple_smp_Schedule( void ); + +/** + * @brief Scheduler Simple SMP Block Method + * + * This routine removes @a the_thread from the scheduling decision, + * that is, removes it from the ready queue. It performs + * any necessary scheduling operations including the selection of + * a new heir thread. + * + * @param[in] the_thread is the thread that is to be blocked + */ +void _Scheduler_simple_smp_Block( + Thread_Control *the_thread +); + +/** + * @brief Scheduler Simple SMP Unblock Method + * + * This routine adds @a the_thread to the scheduling decision, + * that is, adds it to the ready queue and updates any appropriate + * scheduling variables, for example the heir thread. + * + * @param[in] the_thread is the thread that is to be unblocked + */ +void _Scheduler_simple_smp_Unblock( + Thread_Control *the_thread +); + +#ifdef __cplusplus +} +#endif + +/**@}*/ + +#endif +/* end of include file */ diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am index 7080f4efef..7891b6fd84 100644 --- a/cpukit/score/preinstall.am +++ b/cpukit/score/preinstall.am @@ -30,10 +30,11 @@ $(PROJECT_INCLUDE)/rtems/seterr.h: include/rtems/seterr.h $(PROJECT_INCLUDE)/rte $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/seterr.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/seterr.h +if HAS_SMP $(PROJECT_INCLUDE)/rtems/bspsmp.h: include/rtems/bspsmp.h $(PROJECT_INCLUDE)/rtems/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/bspsmp.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/bspsmp.h - +endif $(PROJECT_INCLUDE)/rtems/score/$(dirstamp): @$(MKDIR_P) $(PROJECT_INCLUDE)/rtems/score @: > $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) @@ -230,6 +231,11 @@ $(PROJECT_INCLUDE)/rtems/score/threadmp.h: include/rtems/score/threadmp.h $(PROJ $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/threadmp.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/threadmp.h endif +if HAS_SMP +$(PROJECT_INCLUDE)/rtems/score/schedulersimplesmp.h: include/rtems/score/schedulersimplesmp.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/schedulersimplesmp.h +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/schedulersimplesmp.h +endif $(PROJECT_INCLUDE)/rtems/score/address.inl: inline/rtems/score/address.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/address.inl PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/address.inl diff --git a/cpukit/score/src/schedulersimplesmpblock.c b/cpukit/score/src/schedulersimplesmpblock.c new file mode 100644 index 0000000000..bb9498d9cb --- /dev/null +++ b/cpukit/score/src/schedulersimplesmpblock.c @@ -0,0 +1,28 @@ +/* + * Scheduler Simple SMP Handler / Block + * + * 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 + +void _Scheduler_simple_smp_Block( + Thread_Control *the_thread +) +{ + _Scheduler_simple_Extract( the_thread ); + + _Scheduler_simple_smp_Schedule(); +} 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 +#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; + } +} diff --git a/cpukit/score/src/schedulersimplesmpunblock.c b/cpukit/score/src/schedulersimplesmpunblock.c new file mode 100644 index 0000000000..58332d4f9e --- /dev/null +++ b/cpukit/score/src/schedulersimplesmpunblock.c @@ -0,0 +1,31 @@ +/* + * Scheduler Simple SMP Handler / Unblock + * + * 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 + +void _Scheduler_simple_smp_Unblock( + Thread_Control *the_thread +) +{ + _Scheduler_simple_Ready_queue_enqueue(the_thread); + + /* + * Evaluate all CPUs and pick heirs + */ + _Scheduler_simple_smp_Schedule(); +} -- cgit v1.2.3