From 5472ad414f5eec7aba13f3d03ee8e35dfdfa406a Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Sun, 11 Sep 2011 20:52:37 +0000 Subject: 2011-09-11 Petr Benes PR 1896/cpukit * sapi/include/confdefs.h, score/Makefile.am, score/preinstall.am: Add Earliest Deadline First (EDF) Scheduling Algorithm implementation. * score/include/rtems/score/scheduleredf.h, score/src/scheduleredf.c, score/src/scheduleredfallocate.c, score/src/scheduleredfblock.c, score/src/scheduleredfenqueue.c, score/src/scheduleredfenqueuefirst.c, score/src/scheduleredfextract.c, score/src/scheduleredffree.c, score/src/scheduleredfprioritycompare.c, score/src/scheduleredfreleasejob.c, score/src/scheduleredfschedule.c, score/src/scheduleredfunblock.c, score/src/scheduleredfupdate.c, score/src/scheduleredfyield.c: New files. --- cpukit/ChangeLog | 15 ++ cpukit/sapi/include/confdefs.h | 20 +- cpukit/score/Makefile.am | 16 ++ cpukit/score/include/rtems/score/scheduleredf.h | 265 ++++++++++++++++++++++++ cpukit/score/preinstall.am | 4 + cpukit/score/src/scheduleredf.c | 49 +++++ cpukit/score/src/scheduleredfallocate.c | 39 ++++ cpukit/score/src/scheduleredfblock.c | 36 ++++ cpukit/score/src/scheduleredfenqueue.c | 31 +++ cpukit/score/src/scheduleredfenqueuefirst.c | 25 +++ cpukit/score/src/scheduleredfextract.c | 31 +++ cpukit/score/src/scheduleredffree.c | 27 +++ cpukit/score/src/scheduleredfprioritycompare.c | 40 ++++ cpukit/score/src/scheduleredfreleasejob.c | 40 ++++ cpukit/score/src/scheduleredfschedule.c | 28 +++ cpukit/score/src/scheduleredfunblock.c | 47 +++++ cpukit/score/src/scheduleredfupdate.c | 50 +++++ cpukit/score/src/scheduleredfyield.c | 57 +++++ 18 files changed, 819 insertions(+), 1 deletion(-) create mode 100644 cpukit/score/include/rtems/score/scheduleredf.h create mode 100644 cpukit/score/src/scheduleredf.c create mode 100644 cpukit/score/src/scheduleredfallocate.c create mode 100644 cpukit/score/src/scheduleredfblock.c create mode 100644 cpukit/score/src/scheduleredfenqueue.c create mode 100644 cpukit/score/src/scheduleredfenqueuefirst.c create mode 100644 cpukit/score/src/scheduleredfextract.c create mode 100644 cpukit/score/src/scheduleredffree.c create mode 100644 cpukit/score/src/scheduleredfprioritycompare.c create mode 100644 cpukit/score/src/scheduleredfreleasejob.c create mode 100644 cpukit/score/src/scheduleredfschedule.c create mode 100644 cpukit/score/src/scheduleredfunblock.c create mode 100644 cpukit/score/src/scheduleredfupdate.c create mode 100644 cpukit/score/src/scheduleredfyield.c (limited to 'cpukit') diff --git a/cpukit/ChangeLog b/cpukit/ChangeLog index 6b770a14e8..31581e0faa 100644 --- a/cpukit/ChangeLog +++ b/cpukit/ChangeLog @@ -1,3 +1,18 @@ +2011-09-11 Petr Benes + + PR 1896/cpukit + * sapi/include/confdefs.h, score/Makefile.am, score/preinstall.am: Add + Earliest Deadline First (EDF) Scheduling Algorithm implementation. + * score/include/rtems/score/scheduleredf.h, score/src/scheduleredf.c, + score/src/scheduleredfallocate.c, score/src/scheduleredfblock.c, + score/src/scheduleredfenqueue.c, + score/src/scheduleredfenqueuefirst.c, + score/src/scheduleredfextract.c, score/src/scheduleredffree.c, + score/src/scheduleredfprioritycompare.c, + score/src/scheduleredfreleasejob.c, score/src/scheduleredfschedule.c, + score/src/scheduleredfunblock.c, score/src/scheduleredfupdate.c, + score/src/scheduleredfyield.c: New files. + 2011-09-09 Sebastian Huber PR 1901/cpukit diff --git a/cpukit/sapi/include/confdefs.h b/cpukit/sapi/include/confdefs.h index 3ecc60941d..2a9d75ac2c 100644 --- a/cpukit/sapi/include/confdefs.h +++ b/cpukit/sapi/include/confdefs.h @@ -573,6 +573,7 @@ rtems_fs_init_functions_t rtems_fs_init_helper = * CONFIGURE_SCHEDULER_PRIORITY - Deterministic Priority Scheduler * CONFIGURE_SCHEDULER_SIMPLE - Light-weight Priority Scheduler * CONFIGURE_SCHEDULER_SIMPLE_SMP - Simple SMP Priority Scheduler + * CONFIGURE_SCHEDULER_EDF - EDF Scheduler * * If no configuration is specified by the application, then * CONFIGURE_SCHEDULER_PRIORITY is assumed to be the default. @@ -598,7 +599,8 @@ rtems_fs_init_functions_t rtems_fs_init_helper = #if !defined(CONFIGURE_SCHEDULER_USER) && \ !defined(CONFIGURE_SCHEDULER_PRIORITY) && \ !defined(CONFIGURE_SCHEDULER_SIMPLE) && \ - !defined(CONFIGURE_SCHEDULER_SIMPLE_SMP) + !defined(CONFIGURE_SCHEDULER_SIMPLE_SMP) && \ + !defined(CONFIGURE_SCHEDULER_EDF) #if defined(RTEMS_SMP) && defined(CONFIGURE_SMP_APPLICATION) #define CONFIGURE_SCHEDULER_SIMPLE_SMP #else @@ -658,6 +660,22 @@ rtems_fs_init_functions_t rtems_fs_init_helper = #define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER (0) #endif +/* + * If the EDF Scheduler is selected, then configure for it. + */ +#if defined(CONFIGURE_SCHEDULER_EDF) + #include + #define CONFIGURE_SCHEDULER_ENTRY_POINTS SCHEDULER_EDF_ENTRY_POINTS + + /** + * define the memory used by the EDF scheduler + */ + #define CONFIGURE_MEMORY_FOR_SCHEDULER ( \ + _Configure_From_workspace(0)) + #define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER ( \ + _Configure_From_workspace(sizeof(Scheduler_EDF_Per_thread))) +#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 20d8ead7b9..d05ccfdb81 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -40,6 +40,7 @@ include_rtems_score_HEADERS += include/rtems/score/priority.h include_rtems_score_HEADERS += include/rtems/score/prioritybitmap.h include_rtems_score_HEADERS += include/rtems/score/rbtree.h include_rtems_score_HEADERS += include/rtems/score/scheduler.h +include_rtems_score_HEADERS += include/rtems/score/scheduleredf.h include_rtems_score_HEADERS += include/rtems/score/schedulerpriority.h include_rtems_score_HEADERS += include/rtems/score/schedulersimple.h include_rtems_score_HEADERS += include/rtems/score/stack.h @@ -222,6 +223,21 @@ libscore_a_SOURCES += src/schedulersimple.c \ src/schedulersimpleunblock.c \ src/schedulersimpleyield.c +## SCHEDULEREDF_C_FILES +libscore_a_SOURCES += src/scheduleredf.c \ + src/scheduleredfallocate.c \ + src/scheduleredfblock.c \ + src/scheduleredfenqueue.c \ + src/scheduleredfenqueuefirst.c \ + src/scheduleredfextract.c \ + src/scheduleredffree.c \ + src/scheduleredfprioritycompare.c \ + src/scheduleredfreleasejob.c \ + src/scheduleredfschedule.c \ + src/scheduleredfunblock.c \ + src/scheduleredfupdate.c \ + src/scheduleredfyield.c + ## PROTECTED_HEAP_C_FILES libscore_a_SOURCES += src/pheapallocate.c \ src/pheapextend.c src/pheapfree.c src/pheapgetsize.c \ diff --git a/cpukit/score/include/rtems/score/scheduleredf.h b/cpukit/score/include/rtems/score/scheduleredf.h new file mode 100644 index 0000000000..06569066d6 --- /dev/null +++ b/cpukit/score/include/rtems/score/scheduleredf.h @@ -0,0 +1,265 @@ +/** + * @file rtems/score/scheduleredf.h + * + * This include file contains all the constants and structures associated + * with the manipulation of threads for the EDF scheduler. + */ + +/* + * Copryight (c) 2011 Petr Benes. + * 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_SCHEDULEREDF_H +#define _RTEMS_SCORE_SCHEDULEREDF_H + +#include +#include +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @addtogroup ScoreScheduler + * + */ +/**@{*/ + +/** + * Entry points for the Earliest Deadline First Scheduler. + */ +#define SCHEDULER_EDF_ENTRY_POINTS \ + { \ + _Scheduler_EDF_Initialize, /* initialize entry point */ \ + _Scheduler_EDF_Schedule, /* schedule entry point */ \ + _Scheduler_EDF_Yield, /* yield entry point */ \ + _Scheduler_EDF_Block, /* block entry point */ \ + _Scheduler_EDF_Unblock, /* unblock entry point */ \ + _Scheduler_EDF_Allocate, /* allocate entry point */ \ + _Scheduler_EDF_Free, /* free entry point */ \ + _Scheduler_EDF_Update, /* update entry point */ \ + _Scheduler_EDF_Enqueue, /* enqueue entry point */ \ + _Scheduler_EDF_Enqueue_first, /* enqueue_first entry point */ \ + _Scheduler_EDF_Extract, /* extract entry point */ \ + _Scheduler_EDF_Priority_compare, /* compares two priorities */ \ + _Scheduler_EDF_Release_job, /* new period of task */ \ + _Scheduler_priority_Tick /* tick entry point */ \ + } + +/** + * This is just a most significant bit of Priority_Control type. It + * distinguishes threads which are deadline driven (priority + * represented by a lower number than @a SCHEDULER_EDF_PRIO_MSB) from those + * ones who do not have any deadlines and thus are considered background + * tasks. + */ +#define SCHEDULER_EDF_PRIO_MSB 0x80000000 + +/** + * @typedef Scheduler_EDF_Queue_state + * + * This enumeration distiguishes state of a thread with respect to the + * ready queue. + */ +typedef enum { + SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY, + SCHEDULER_EDF_QUEUE_STATE_YES, + SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN +} Scheduler_EDF_Queue_state; + +/** + * This structure handles EDF specific data of a thread. + */ +typedef struct { + /** + * Pointer to corresponding Thread Control Block. + */ + Thread_Control *thread; + /** + * Rbtree node related to this thread. + */ + RBTree_Node Node; + /** + * State of the thread with respect to ready queue. + */ + Scheduler_EDF_Queue_state queue_state; +} Scheduler_EDF_Per_thread; + +/** + * Top of the ready queue. + */ +extern RBTree_Control _Scheduler_EDF_Ready_queue; + +/** + * @brief Scheduler EDF Initialize + * + * This routine initializes the EDF scheduler. + */ +void _Scheduler_EDF_Initialize( void ); + +/** + * @brief Scheduler EDF Block + * + * 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 to be blocked. + */ +void _Scheduler_EDF_Block( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Schedule + * + * This kernel routine sets the heir thread to be the next ready thread + * in the rbtree ready queue. + */ +void _Scheduler_EDF_Schedule( void ); + +/** + * @brief Scheduler EDF Allocate + * + * This routine allocates EDF specific information of @a the_thread. + * + * @param[in] the_thread is the thread the scheduler is allocating + * management memory for. + */ +void *_Scheduler_EDF_Allocate( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Free + * + * This routine frees the EDF specific information of @a the_thread. + * + * @param[in] the_thread is the thread whose scheduler specific information + * will be deallocated. + */ +void _Scheduler_EDF_Free( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Update + * + * This routine updates position in the ready queue of @a the_thread. + * + * @param[in] the_thread will have its scheduler specific information + * structure updated. + */ +void _Scheduler_EDF_Update( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Unblock + * + * 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 will be unblocked. + */ +void _Scheduler_EDF_Unblock( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Yield + * + * This routine is invoked when a thread wishes to voluntarily + * transfer control of the processor to another thread in the queue with + * equal deadline. This does not have to happen very often. + * + * This routine will remove the running THREAD from the ready queue + * and place back. The rbtree ready queue is responsible for FIFO ordering + * in such a case. + */ +void _Scheduler_EDF_Yield( void ); + +/** + * @brief Scheduler EDF Enqueue + * + * This routine puts @a the_thread to the rbtree ready queue. + * + * @param[in] the_thread will be enqueued to the ready queue. + */ +void _Scheduler_EDF_Enqueue( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Enqueue first + * + * This routine puts @a the_thread to the rbtree ready queue. + * For the EDF scheduler this is the same as @a _Scheduler_EDF_Enqueue. + * + * @param[in] the_thread will be enqueued to the ready queue. + */ +void _Scheduler_EDF_Enqueue_first( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Extract + * + * This routine removes a specific thread from the scheduler's set + * of ready threads. + * + * @param[in] the_thread will be extracted from the ready set. + */ +void _Scheduler_EDF_Extract( + Thread_Control *the_thread +); + +/** + * @brief Scheduler EDF Priority compare + * + * This routine explicitly compares absolute dedlines (priorities) of threads. + * In case of EDF scheduling time overflow is taken into account. + * + * @return >0 for p1 > p2; 0 for p1 == p2; <0 for p1 < p2. + */ +int _Scheduler_EDF_Priority_compare ( + Priority_Control p1, + Priority_Control p2 +); + +/** + * @brief Scheduler EDF Release job + * + * This routine is called when a new job of task is released. + * It is called only from Rate Monotonic manager in the beginning + * of new period. + * + * @param[in] the_thread is the owner of the job. + * @param[in] deadline of the new job from now. If equal to 0, + * the job was cancelled or deleted, thus a running task + * has to be suspended. + */ +void _Scheduler_EDF_Release_job ( + Thread_Control *the_thread, + uint32_t deadline +); + +#ifdef __cplusplus +} +#endif + +/**@}*/ + +#endif +/* end of include file */ diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am index 884891f5c3..0461648517 100644 --- a/cpukit/score/preinstall.am +++ b/cpukit/score/preinstall.am @@ -127,6 +127,10 @@ $(PROJECT_INCLUDE)/rtems/score/scheduler.h: include/rtems/score/scheduler.h $(PR $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.h +$(PROJECT_INCLUDE)/rtems/score/scheduleredf.h: include/rtems/score/scheduleredf.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduleredf.h +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduleredf.h + $(PROJECT_INCLUDE)/rtems/score/schedulerpriority.h: include/rtems/score/schedulerpriority.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/schedulerpriority.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/schedulerpriority.h diff --git a/cpukit/score/src/scheduleredf.c b/cpukit/score/src/scheduleredf.c new file mode 100644 index 0000000000..2aa2d52cea --- /dev/null +++ b/cpukit/score/src/scheduleredf.c @@ -0,0 +1,49 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include + +int _Scheduler_EDF_RBTree_compare_function +( + RBTree_Node* n1, + RBTree_Node* n2 +) +{ + Priority_Control value1 = _RBTree_Container_of + (n1,Scheduler_EDF_Per_thread,Node)->thread->current_priority; + Priority_Control value2 = _RBTree_Container_of + (n2,Scheduler_EDF_Per_thread,Node)->thread->current_priority; + + /* + * This function compares only numbers for the red-black tree, + * but priorities have an opposite sense. + */ + return (-1)*_Scheduler_Is_priority_higher_than(value1, value2); +} + +void _Scheduler_EDF_Initialize(void) +{ + _RBTree_Initialize_empty( + &_Scheduler_EDF_Ready_queue, + &_Scheduler_EDF_RBTree_compare_function, + 0 + ); +} + +/* Instantiate any global variables needed by the EDF scheduler */ +RBTree_Control _Scheduler_EDF_Ready_queue; diff --git a/cpukit/score/src/scheduleredfallocate.c b/cpukit/score/src/scheduleredfallocate.c new file mode 100644 index 0000000000..6d45583519 --- /dev/null +++ b/cpukit/score/src/scheduleredfallocate.c @@ -0,0 +1,39 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include + +void *_Scheduler_EDF_Allocate( + Thread_Control *the_thread +) +{ + void *sched; + Scheduler_EDF_Per_thread *schinfo; + + sched = _Workspace_Allocate( sizeof(Scheduler_EDF_Per_thread) ); + + if ( sched ) { + the_thread->scheduler_info = sched; + schinfo = (Scheduler_EDF_Per_thread *)(the_thread->scheduler_info); + schinfo->thread = the_thread; + schinfo->queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN; + } + + return sched; +} diff --git a/cpukit/score/src/scheduleredfblock.c b/cpukit/score/src/scheduleredfblock.c new file mode 100644 index 0000000000..5923171bc9 --- /dev/null +++ b/cpukit/score/src/scheduleredfblock.c @@ -0,0 +1,36 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include +#include + +void _Scheduler_EDF_Block( + Thread_Control *the_thread +) +{ + _Scheduler_EDF_Extract( the_thread ); + + /* TODO: flash critical section? */ + + if ( _Thread_Is_heir( the_thread ) ) + _Scheduler_EDF_Schedule(); + + if ( _Thread_Is_executing( the_thread ) ) + _Thread_Dispatch_necessary = true; +} diff --git a/cpukit/score/src/scheduleredfenqueue.c b/cpukit/score/src/scheduleredfenqueue.c new file mode 100644 index 0000000000..dc59e26ab7 --- /dev/null +++ b/cpukit/score/src/scheduleredfenqueue.c @@ -0,0 +1,31 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include + +void _Scheduler_EDF_Enqueue( + Thread_Control *the_thread +) +{ + Scheduler_EDF_Per_thread *sched_info = + (Scheduler_EDF_Per_thread*) the_thread->scheduler_info; + RBTree_Node *node = &(sched_info->Node); + + _RBTree_Insert( &_Scheduler_EDF_Ready_queue, node ); + sched_info->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES; +} diff --git a/cpukit/score/src/scheduleredfenqueuefirst.c b/cpukit/score/src/scheduleredfenqueuefirst.c new file mode 100644 index 0000000000..e8297a147c --- /dev/null +++ b/cpukit/score/src/scheduleredfenqueuefirst.c @@ -0,0 +1,25 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include + +void _Scheduler_EDF_Enqueue_first( + Thread_Control *the_thread +) +{ + _Scheduler_EDF_Enqueue(the_thread); +} diff --git a/cpukit/score/src/scheduleredfextract.c b/cpukit/score/src/scheduleredfextract.c new file mode 100644 index 0000000000..019b68e32f --- /dev/null +++ b/cpukit/score/src/scheduleredfextract.c @@ -0,0 +1,31 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include + +void _Scheduler_EDF_Extract( + Thread_Control *the_thread +) +{ + Scheduler_EDF_Per_thread *sched_info = + (Scheduler_EDF_Per_thread*) the_thread->scheduler_info; + RBTree_Node *node = &(sched_info->Node); + + _RBTree_Extract( &_Scheduler_EDF_Ready_queue, node ); + sched_info->queue_state = SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY; +} diff --git a/cpukit/score/src/scheduleredffree.c b/cpukit/score/src/scheduleredffree.c new file mode 100644 index 0000000000..76667f0cdd --- /dev/null +++ b/cpukit/score/src/scheduleredffree.c @@ -0,0 +1,27 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include + +void _Scheduler_EDF_Free( + Thread_Control *the_thread +) +{ + _Workspace_Free( the_thread->scheduler_info ); +} diff --git a/cpukit/score/src/scheduleredfprioritycompare.c b/cpukit/score/src/scheduleredfprioritycompare.c new file mode 100644 index 0000000000..324e44af37 --- /dev/null +++ b/cpukit/score/src/scheduleredfprioritycompare.c @@ -0,0 +1,40 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include + +int _Scheduler_EDF_Priority_compare ( + Priority_Control p1, + Priority_Control p2 +) +{ + Watchdog_Interval time = _Watchdog_Ticks_since_boot; + + /* + * Reorder priorities to separate deadline driven and background tasks. + * + * The background tasks have p1 or p2 > SCHEDULER_EDF_PRIO_MSB. + * The deadline driven tasks need to have subtracted current time in order + * to see which deadline is closer wrt. current time. + */ + if (!(p1 & SCHEDULER_EDF_PRIO_MSB)) + p1 = (p1 - time) & ~SCHEDULER_EDF_PRIO_MSB; + if (!(p2 & SCHEDULER_EDF_PRIO_MSB)) + p2 = (p2 - time) & ~SCHEDULER_EDF_PRIO_MSB; + + return ((p1p2)); +} diff --git a/cpukit/score/src/scheduleredfreleasejob.c b/cpukit/score/src/scheduleredfreleasejob.c new file mode 100644 index 0000000000..0bd86e976f --- /dev/null +++ b/cpukit/score/src/scheduleredfreleasejob.c @@ -0,0 +1,40 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include + +void _Scheduler_EDF_Release_job( + Thread_Control *the_thread, + uint32_t deadline +) +{ + Priority_Control new_priority; + + if (deadline) { + /* Initializing or shifting deadline. */ + new_priority = (_Watchdog_Ticks_since_boot + deadline) + & ~SCHEDULER_EDF_PRIO_MSB; + } + else { + /* Switch back to background priority. */ + new_priority = the_thread->Start.initial_priority; + } + + the_thread->real_priority = new_priority; + _Thread_Change_priority(the_thread, new_priority, true); +} diff --git a/cpukit/score/src/scheduleredfschedule.c b/cpukit/score/src/scheduleredfschedule.c new file mode 100644 index 0000000000..1482be8207 --- /dev/null +++ b/cpukit/score/src/scheduleredfschedule.c @@ -0,0 +1,28 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include + +void _Scheduler_EDF_Schedule(void) +{ + RBTree_Node *first_node = + _RBTree_Peek(&_Scheduler_EDF_Ready_queue, RBT_LEFT); + Scheduler_EDF_Per_thread *sched_info = + _RBTree_Container_of(first_node, Scheduler_EDF_Per_thread, Node); + + _Thread_Heir = (Thread_Control *) sched_info->thread; +} diff --git a/cpukit/score/src/scheduleredfunblock.c b/cpukit/score/src/scheduleredfunblock.c new file mode 100644 index 0000000000..bca071adbc --- /dev/null +++ b/cpukit/score/src/scheduleredfunblock.c @@ -0,0 +1,47 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include + +void _Scheduler_EDF_Unblock( + Thread_Control *the_thread +) +{ + _Scheduler_EDF_Enqueue(the_thread); + /* TODO: flash critical section? */ + + /* + * If the thread that was unblocked is more important than the heir, + * then we have a new heir. This may or may not result in a + * context switch. + * + * Normal case: + * If the current thread is preemptible, then we need to do + * a context switch. + * Pseudo-ISR case: + * Even if the thread isn't preemptible, if the new heir is + * a pseudo-ISR system task, we need to do a context switch. + */ + if ( _Scheduler_Is_priority_lower_than( + _Thread_Heir->current_priority, + the_thread->current_priority )) { + _Thread_Heir = the_thread; + if ( _Thread_Executing->is_preemptible || + the_thread->current_priority == 0 ) + _Thread_Dispatch_necessary = true; + } +} diff --git a/cpukit/score/src/scheduleredfupdate.c b/cpukit/score/src/scheduleredfupdate.c new file mode 100644 index 0000000000..a4592d8c46 --- /dev/null +++ b/cpukit/score/src/scheduleredfupdate.c @@ -0,0 +1,50 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include +#include + +void _Scheduler_EDF_Update( + Thread_Control *the_thread +) +{ + Scheduler_EDF_Per_thread *sched_info = + (Scheduler_EDF_Per_thread*)the_thread->scheduler_info; + RBTree_Node *the_node = &(sched_info->Node); + + if (sched_info->queue_state == SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN) { + /* Shifts the priority to the region of background tasks. */ + the_thread->Start.initial_priority |= (SCHEDULER_EDF_PRIO_MSB); + the_thread->real_priority = the_thread->Start.initial_priority; + the_thread->current_priority = the_thread->Start.initial_priority; + sched_info->queue_state = SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY; + } + + if ( sched_info->queue_state == SCHEDULER_EDF_QUEUE_STATE_YES ) { + _RBTree_Extract(&_Scheduler_EDF_Ready_queue, the_node); + _RBTree_Insert(&_Scheduler_EDF_Ready_queue, the_node); + + _Scheduler_EDF_Schedule(); + if ( _Thread_Executing != _Thread_Heir ) { + if ( _Thread_Executing->is_preemptible || + the_thread->current_priority == 0 ) + _Thread_Dispatch_necessary = true; + } + } +} diff --git a/cpukit/score/src/scheduleredfyield.c b/cpukit/score/src/scheduleredfyield.c new file mode 100644 index 0000000000..be1b07a5c5 --- /dev/null +++ b/cpukit/score/src/scheduleredfyield.c @@ -0,0 +1,57 @@ +/* + * Copyright (C) 2011 Petr Benes. + * 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$ + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include +#include +#include + +void _Scheduler_EDF_Yield(void) +{ + Scheduler_EDF_Per_thread *first_info; + RBTree_Node *first_node; + ISR_Level level; + + Thread_Control *executing = _Thread_Executing; + Scheduler_EDF_Per_thread *executing_info = + (Scheduler_EDF_Per_thread *) executing->scheduler_info; + RBTree_Node *executing_node = &(executing_info->Node); + + _ISR_Disable( level ); + + if ( !_RBTree_Has_only_one_node(&_Scheduler_EDF_Ready_queue) ) { + /* + * The RBTree has more than one node, enqueue behind the tasks + * with the same priority in case there are such ones. + */ + _RBTree_Extract( &_Scheduler_EDF_Ready_queue, executing_node ); + _RBTree_Insert( &_Scheduler_EDF_Ready_queue, executing_node ); + + _ISR_Flash( level ); + + if ( _Thread_Is_heir( executing ) ) { + first_node = _RBTree_Peek( &_Scheduler_EDF_Ready_queue, RBT_LEFT ); + first_info = + _RBTree_Container_of(first_node, Scheduler_EDF_Per_thread, Node); + _Thread_Heir = first_info->thread; + } + _Thread_Dispatch_necessary = true; + } + else if ( !_Thread_Is_heir( executing ) ) + _Thread_Dispatch_necessary = true; + + _ISR_Enable( level ); +} -- cgit v1.2.3