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         if (node->cmp_time) {
  31 //              rtems_signal_catch(budget_overrun_handler, RTEMS_DEFAULT_MODES);        // register this in frsh
  32                 the_thread->is_preemptible = true;
  33                 the_thread->budget_callout = (void *) edf_budget_overrun_callout;
  34                 the_thread->cpu_time_budget = node->cmp_time;
  35
  36                 // do not allow changing the rel_deadline when using a server
  37         } else {
  38                 node->rel_deadline = __rel_deadline__;
  39         }
  40
  41         edf_postpone_deadlines(the_thread);
  42
  43         //_Scheduler_edf_Update(the_thread);
  44         return rtems_rate_monotonic_period(period_id, __rel_deadline__);
  45 }
  46
  47
  48 rtems_status_code edf_deadline_init(rtems_name name, rtems_id *period_id) {
  49         return rtems_rate_monotonic_create(name, period_id);
  50 }
  51
  52 // return to start params
  53 rtems_status_code edf_deadline_cancel(rtems_id period_id) {
  54         Thread_Control *the_thread = _Per_CPU_Information.executing;
  55
  56         the_thread->real_priority = the_thread->Start.initial_priority + EDF_HYBRID_MASK;
  57         the_thread->current_priority = the_thread->real_priority;
  58
  59         _Scheduler_edf_Update(the_thread);
  60         return rtems_rate_monotonic_delete(period_id);
  61 }
  62
  63 // invoked when a limited time quantum (cmp_time) is exceeded
  64 Thread_CPU_budget_algorithm_callout edf_budget_overrun_callout() {
  65         Thread_Control *the_thread = _Per_CPU_Information.executing;
  66         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
  67         rtems_signal_send(the_thread->Object.id, RTEMS_SIGNAL_15);
  68         _Thread_Suspend (the_thread); //TODO: make options on suspension
  69         uint32_t ticks = node->abs_deadline - _Watchdog_Ticks_since_boot; //FIXME: wrong calc
  70         rtems_timer_fire_after(node->timer_id, ticks, (void *) edf_budget_overrun_reenable, the_thread);
  71         return 0;
  72 }
  73
  74 rtems_timer_service_routine_entry edf_budget_overrun_reenable(Thread_Control *the_thread) {
  75         _Thread_Resume(the_thread, false);
  76         printf("Come back\n"); //FIXME: Continue here
  77         return 0;
  78 }
  79
  80 //=======================================================================================
  81
  82
  83 int _Scheduler_edf_Priority_compare (Priority_Control p1, Priority_Control p2) {
  84         uint32_t time = _Watchdog_Ticks_since_boot;
  85         //correct priorities
  86         if (p1 < EDF_HYBRID_MASK)
  87                 p1 = (p1 - time) % EDF_HYBRID_MASK;
  88         if (p2 < EDF_HYBRID_MASK)
  89                 p2 = (p2 - time) % EDF_HYBRID_MASK;
  90         if (p1 > p2) return -1;
  91         else if (p1 < p2) return 1;
  92         else return 0;
  93 }
  94
  95
  96 void _Scheduler_edf_Initialize(void) {
  97         // initialize the RB tree
  98         _Thread_Ready_EDF_chain.root = NULL;
  99         _Thread_Ready_EDF_chain.first = NULL;
 100         _Thread_Heir = NULL;
 101         _Thread_Executing = NULL;
 102         _Signal_Manager_initialization();
 103 }
 104
 105 void _Scheduler_edf_Block(  Thread_Control    *the_thread ) {
 106         _Scheduler_edf_Extract(the_thread);
 107
 108         /* TODO: flash critical section? */
 109
 110         if ( _Thread_Is_heir( the_thread ) )
 111                 _Scheduler_edf_Schedule();
 112
 113         if ( _Thread_Is_executing( the_thread ) )
 114                 _Thread_Dispatch_necessary = true;
 115 }
 116
 117 void _Scheduler_edf_Schedule(void) {
 118         // set the heir
 119         _Thread_Heir = (Thread_Control *) _Thread_Ready_EDF_chain.first;
 120 }
 121
 122 void * _Scheduler_edf_Allocate(  Thread_Control      *the_thread) {
 123         void * sched;
 124         RBT_Node *schinfo;
 125         sched = _Workspace_Allocate (sizeof(RBT_Node));
 126         the_thread->scheduler_info = (RBT_Node *) sched;
 127         //edf_initial_priority_shift(&(the_thread->real_priority));
 128
 129         the_thread->Start.initial_priority += (EDF_HYBRID_MASK);
 130
 131         schinfo = (RBT_Node *)(the_thread->scheduler_info);
 132         schinfo->rel_deadline = 0;      // This has to be negotiated afterwards
 133         schinfo->abs_deadline = 0;
 134         schinfo->is_enqueued = 2;
 135         schinfo->left = NULL;
 136         schinfo->right = NULL;
 137         schinfo->parent = NULL;
 138         schinfo->cmp_time = 0;
 139         schinfo->ready_chain = &_Thread_Ready_EDF_chain;
 140
 141         return sched;
 142 }
 143
 144 void _Scheduler_edf_Free(  Thread_Control      *the_thread) {
 145         _Workspace_Free (the_thread->scheduler_info);
 146 }
 147
 148 void _Scheduler_edf_Update(  Thread_Control      *the_thread) {
 149         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 150         // Make sure the previous priority meaning does not show up
 151         // if the task was just initialized
 152         if (node->is_enqueued == 2) {
 153                 the_thread->real_priority = the_thread->Start.initial_priority;
 154                 the_thread->current_priority = the_thread->real_priority;
 155                 node->is_enqueued = 0;
 156         }
 157         // Update deadlines for deadline driven tasks
 158         if (!(the_thread->current_priority & EDF_HYBRID_MASK))
 159                 ((RBT_Node*)the_thread->scheduler_info)->abs_deadline = the_thread->current_priority;
 160         else
 161                 ((RBT_Node*)the_thread->scheduler_info)->abs_deadline = 0;
 162         if(node->is_enqueued == 1) {
 163                 _Scheduler_edf_Extract(the_thread);
 164                 _Scheduler_edf_Enqueue(the_thread);
 165                 if ( the_thread->current_priority < _Thread_Heir->current_priority ) { //TODO: compare priorities
 166                         _Thread_Heir = the_thread;
 167                         if ( _Thread_Executing->is_preemptible || the_thread->current_priority == 0 )
 168                                 _Thread_Dispatch_necessary = true;
 169                 }
 170         }
 171 }
 172
 173 void _Scheduler_edf_Unblock(  Thread_Control    *the_thread ) {
 174         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 175
 176         //Late unblock rule
 177         if (node->flags & EDF_LATE_UNBLOCK) {
 178                 uint32_t Q_left = the_thread->cpu_time_budget;
 179                 uint32_t P_left = node->abs_deadline - _Watchdog_Ticks_since_boot;
 180                 uint32_t P = node->rel_deadline;
 181                 uint32_t Q = node->cmp_time;
 182                 if(P*Q_left > Q*P_left)
 183                         edf_postpone_deadlines(the_thread);
 184         }
 185
 186         _Scheduler_edf_Enqueue(the_thread);
 187         /* TODO: flash critical section? */
 188
 189         /*
 190         *  If the thread that was unblocked is more important than the heir,
 191         *  then we have a new heir.  This may or may not result in a
 192         *  context switch.
 193         *
 194         *  Normal case:
 195         *    If the current thread is preemptible, then we need to do
 196         *    a context switch.
 197         *  Pseudo-ISR case:
 198         *    Even if the thread isn't preemptible, if the new heir is
 199         *    a pseudo-ISR system task, we need to do a context switch.
 200         */
 201         if ( the_thread->current_priority < _Thread_Heir->current_priority ) {
 202                 _Thread_Heir = the_thread;
 203                 if ( _Thread_Executing->is_preemptible || the_thread->current_priority == 0 )
 204                         _Thread_Dispatch_necessary = true;
 205         }
 206
 207 }
 208
 209 void _Scheduler_edf_Yield( void ) {
 210         RBT_Node *sched_info;
 211         ISR_Level                      level;
 212         Thread_Control                *executing;
 213         EDF_Chain_Control                 *ready;
 214
 215         executing  = _Thread_Executing;
 216         sched_info = (RBT_Node *) executing->scheduler_info;
 217         ready      = sched_info->ready_chain;
 218         _ISR_Disable( level );
 219         if ( !_RBT_Has_only_one_node( ready ) ) {
 220                 _Scheduler_edf_Extract(executing);
 221                 _Scheduler_edf_Enqueue(executing); // preserve the abs_deadline
 222
 223                 _ISR_Flash( level );
 224
 225                 if ( _Thread_Is_heir( executing ) )
 226                         _Thread_Heir = (Thread_Control *) ready->first;
 227                 _Thread_Dispatch_necessary = TRUE;
 228         }
 229         else if ( !_Thread_Is_heir( executing ) )
 230                 _Thread_Dispatch_necessary = TRUE;
 231
 232         _ISR_Enable( level );
 233
 234 }
 235
 236 void _Scheduler_edf_Enqueue(  Thread_Control    *the_thread) {
 237         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 238         EDF_Chain_Control *chain = node->ready_chain;
 239
 240         _RBT_Insert(chain,the_thread);
 241         node->is_enqueued = 1;
 242 }
 243
 244 void _Scheduler_edf_Enqueue_first(  Thread_Control    *the_thread) {
 245         // FIXME: force first position
 246         _Scheduler_edf_Enqueue(the_thread);
 247 }
 248
 249 void _Scheduler_edf_Extract(  Thread_Control     *the_thread) {
 250         RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
 251         EDF_Chain_Control* chain = ((RBT_Node*)the_thread->scheduler_info)->ready_chain;
 252
 253         _RBT_Extract(chain,the_thread);
 254         node->is_enqueued = 0;
 255 }
 256