src/edf/scheduler_edf.c

   1 #include "scheduler_edf.h"
   2 #include "rbtree.h"
   3 #include <stdio.h>
   4 #include <rtems/system.h>
   5 #include <rtems/score/isr.h>
   6 #include <rtems/score/watchdog.h>
   7 #include <rtems/score/wkspace.h>
   8 #include <rtems/score/percpu.h>
   9 #include <rtems/score/thread.h>
  10 #include <stdint.h>
  11
  12
  13 inline void edf_postpone_deadlines(Thread_Control *the_thread) {
  14         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
  15         if (node->abs_deadline == 0) { // for the first time
  16                 the_thread->real_priority = (_Watchdog_Ticks_since_boot + node->rel_deadline) % EDF_HYBRID_MASK;
  17         } else {        // any other time
  18                 the_thread->real_priority = (node->abs_deadline + node->rel_deadline) % EDF_HYBRID_MASK;
  19         }
  20         node->abs_deadline = the_thread->current_priority = the_thread->real_priority;
  21 }
  22
  23 // if cmp_time is 0, no CBS is used, only pure EDF
  24 rtems_status_code edf_next_period(rtems_id period_id, uint32_t __rel_deadline__, uint8_t flags) {
  25         Thread_Control *the_thread = _Per_CPU_Information.executing;
  26         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
  27
  28         node->flags = flags;
  29
  30         // FIXME: remove cmp_time from EDF completely
  31         if (node->cmp_time) {
  32                 the_thread->cpu_time_budget = node->cmp_time;
  33
  34                 // do not allow changing the rel_deadline when using a server
  35         } else {
  36                 node->rel_deadline = __rel_deadline__;
  37         }
  38
  39         edf_postpone_deadlines(the_thread);
  40
  41         //_Scheduler_edf_Update(the_thread);
  42         return rtems_rate_monotonic_period(period_id, node->rel_deadline);
  43 }
  44
  45
  46 rtems_status_code edf_deadline_init(rtems_name name, rtems_id *period_id) {
  47         return rtems_rate_monotonic_create(name, period_id);
  48 }
  49
  50 // return to start params
  51 rtems_status_code edf_deadline_cancel(rtems_id period_id) {
  52         Thread_Control *the_thread = _Per_CPU_Information.executing;
  53
  54         the_thread->real_priority = the_thread->Start.initial_priority + EDF_HYBRID_MASK;
  55         the_thread->current_priority = the_thread->real_priority;
  56
  57         _Scheduler_edf_Update(the_thread);
  58         return rtems_rate_monotonic_delete(period_id);
  59 }
  60
  61
  62
  63 //=======================================================================================
  64
  65
  66 int _Scheduler_edf_Priority_compare (Priority_Control p1, Priority_Control p2) {
  67         uint32_t time = _Watchdog_Ticks_since_boot;
  68         //correct priorities
  69         if (p1 < EDF_HYBRID_MASK)
  70                 p1 = (p1 - time) % EDF_HYBRID_MASK;
  71         if (p2 < EDF_HYBRID_MASK)
  72                 p2 = (p2 - time) % EDF_HYBRID_MASK;
  73         if (p1 > p2) return -1;
  74         else if (p1 < p2) return 1;
  75         else return 0;
  76 }
  77
  78
  79 void _Scheduler_edf_Initialize(void) {
  80         // initialize the RB tree
  81         _Thread_Ready_EDF_chain.root = NULL;
  82         _Thread_Ready_EDF_chain.first = NULL;
  83         _Thread_Heir = NULL;
  84         _Thread_Executing = NULL;
  85         _Signal_Manager_initialization();
  86 }
  87
  88 void _Scheduler_edf_Block(  Thread_Control    *the_thread ) {
  89         _Scheduler_edf_Extract(the_thread);
  90
  91         /* TODO: flash critical section? */
  92
  93         if ( _Thread_Is_heir( the_thread ) )
  94                 _Scheduler_edf_Schedule();
  95
  96         if ( _Thread_Is_executing( the_thread ) )
  97                 _Thread_Dispatch_necessary = true;
  98 }
  99
 100 void _Scheduler_edf_Schedule(void) {
 101         // set the heir
 102         _Thread_Heir = (Thread_Control *) _Thread_Ready_EDF_chain.first;
 103 }
 104
 105 void * _Scheduler_edf_Allocate(  Thread_Control      *the_thread) {
 106         void * sched;
 107         RBT_Node *schinfo;
 108         sched = _Workspace_Allocate (sizeof(RBT_Node));
 109         the_thread->scheduler_info = (RBT_Node *) sched;
 110         //edf_initial_priority_shift(&(the_thread->real_priority));
 111
 112         the_thread->Start.initial_priority += (EDF_HYBRID_MASK);
 113
 114         schinfo = (RBT_Node *)(the_thread->scheduler_info);
 115         schinfo->rel_deadline = 0;      // This has to be negotiated afterwards
 116         schinfo->abs_deadline = 0;
 117         schinfo->is_enqueued = 2;
 118         schinfo->left = NULL;
 119         schinfo->right = NULL;
 120         schinfo->parent = NULL;
 121         schinfo->cmp_time = 0;
 122         schinfo->ready_chain = &_Thread_Ready_EDF_chain;
 123
 124         return sched;
 125 }
 126
 127 void _Scheduler_edf_Free(  Thread_Control      *the_thread) {
 128         _Workspace_Free (the_thread->scheduler_info);
 129 }
 130
 131 void _Scheduler_edf_Update(  Thread_Control      *the_thread) {
 132         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 133         // Make sure the previous priority meaning does not show up
 134         // if the task was just initialized
 135         if (node->is_enqueued == 2) {
 136                 the_thread->real_priority = the_thread->Start.initial_priority;
 137                 the_thread->current_priority = the_thread->real_priority;
 138                 node->is_enqueued = 0;
 139         }
 140         // Update deadlines for deadline driven tasks
 141         if (!(the_thread->current_priority & EDF_HYBRID_MASK))
 142                 ((RBT_Node*)the_thread->scheduler_info)->abs_deadline = the_thread->current_priority;
 143         else
 144                 ((RBT_Node*)the_thread->scheduler_info)->abs_deadline = 0;
 145         if(node->is_enqueued == 1) {
 146                 _Scheduler_edf_Extract(the_thread);
 147                 _Scheduler_edf_Enqueue(the_thread);
 148                 if ( the_thread->current_priority < _Thread_Heir->current_priority ) { //TODO: compare priorities
 149                         _Thread_Heir = the_thread;
 150                         if ( _Thread_Executing->is_preemptible || the_thread->current_priority == 0 )
 151                                 _Thread_Dispatch_necessary = true;
 152                 }
 153         }
 154 }
 155
 156 void _Scheduler_edf_Unblock(  Thread_Control    *the_thread ) {
 157         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 158
 159         //Late unblock rule
 160         if (node->flags & EDF_LATE_UNBLOCK) {
 161                 uint32_t Q_left = the_thread->cpu_time_budget;
 162                 uint32_t P_left = node->abs_deadline - _Watchdog_Ticks_since_boot;
 163                 uint32_t P = node->rel_deadline;
 164                 uint32_t Q = node->cmp_time;
 165                 if(P*Q_left > Q*P_left)
 166                         edf_postpone_deadlines(the_thread);
 167         }
 168
 169         _Scheduler_edf_Enqueue(the_thread);
 170         /* TODO: flash critical section? */
 171
 172         /*
 173         *  If the thread that was unblocked is more important than the heir,
 174         *  then we have a new heir.  This may or may not result in a
 175         *  context switch.
 176         *
 177         *  Normal case:
 178         *    If the current thread is preemptible, then we need to do
 179         *    a context switch.
 180         *  Pseudo-ISR case:
 181         *    Even if the thread isn't preemptible, if the new heir is
 182         *    a pseudo-ISR system task, we need to do a context switch.
 183         */
 184         if ( the_thread->current_priority < _Thread_Heir->current_priority ) {
 185                 _Thread_Heir = the_thread;
 186                 if ( _Thread_Executing->is_preemptible || the_thread->current_priority == 0 )
 187                         _Thread_Dispatch_necessary = true;
 188         }
 189
 190 }
 191
 192 void _Scheduler_edf_Yield( void ) {
 193         RBT_Node *sched_info;
 194         ISR_Level                      level;
 195         Thread_Control                *executing;
 196         EDF_Chain_Control                 *ready;
 197
 198         executing  = _Thread_Executing;
 199         sched_info = (RBT_Node *) executing->scheduler_info;
 200         ready      = sched_info->ready_chain;
 201         _ISR_Disable( level );
 202         if ( !_RBT_Has_only_one_node( ready ) ) {
 203                 _Scheduler_edf_Extract(executing);
 204                 _Scheduler_edf_Enqueue(executing); // preserve the abs_deadline
 205
 206                 _ISR_Flash( level );
 207
 208                 if ( _Thread_Is_heir( executing ) )
 209                         _Thread_Heir = (Thread_Control *) ready->first;
 210                 _Thread_Dispatch_necessary = TRUE;
 211         }
 212         else if ( !_Thread_Is_heir( executing ) )
 213                 _Thread_Dispatch_necessary = TRUE;
 214
 215         _ISR_Enable( level );
 216
 217 }
 218
 219 void _Scheduler_edf_Enqueue(  Thread_Control    *the_thread) {
 220         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 221         EDF_Chain_Control *chain = node->ready_chain;
 222
 223         _RBT_Insert(chain,the_thread);
 224         node->is_enqueued = 1;
 225 }
 226
 227 void _Scheduler_edf_Enqueue_first(  Thread_Control    *the_thread) {
 228         // FIXME: force first position
 229         _Scheduler_edf_Enqueue(the_thread);
 230 }
 231
 232 void _Scheduler_edf_Extract(  Thread_Control     *the_thread) {
 233         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 234         EDF_Chain_Control* chain = ((RBT_Node*)the_thread->scheduler_info)->ready_chain;
 235
 236         _RBT_Extract(chain,the_thread);
 237         node->is_enqueued = 0;
 238 }
 239