Changeset 99fc1d1d in rtems


Ignore:
Timestamp:
06/09/16 19:30:40 (7 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
5, master
Children:
768c483b
Parents:
9a78f8a5
git-author:
Sebastian Huber <sebastian.huber@…> (06/09/16 19:30:40)
git-committer:
Sebastian Huber <sebastian.huber@…> (06/22/16 12:37:11)
Message:

score: Rework EDF scheduler

Use inline red-black tree insert. Do not use shifting priorities since
this is not supported by the thread queues. Due to the 32-bit
Priority_Control this currently limits the uptime to 49days with a 1ms
clock tick.

Update #2173.

Location:
cpukit/score
Files:
12 edited

Legend:

Unmodified
Added
Removed

  • cpukit/score/include/rtems/score/scheduleredf.h

    r9a78f8a5 r99fc1d1d  
    3636/**@{*/
    3737
    38 #define SCHEDULER_EDF_MAXIMUM_PRIORITY 255
     38#define SCHEDULER_EDF_MAXIMUM_PRIORITY 0x7fffffff
    3939
    4040/**
    … …  
    8383
    8484/**
    85  * @typedef Scheduler_EDF_Queue_state
    86  *
    87  * This enumeration distiguishes state of a thread with respect to the
    88  * ready queue.
    89  */
    90 typedef enum {
    91   SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY,
    92   SCHEDULER_EDF_QUEUE_STATE_YES,
    93   SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN
    94 } Scheduler_EDF_Queue_state;
    95 
    96 /**
    9785 * @brief Scheduler node specialization for EDF schedulers.
    9886 */
    … …  
    11199   */
    112100  RBTree_Node Node;
    113   /**
    114    * State of the thread with respect to ready queue.
    115    */
    116   Scheduler_EDF_Queue_state queue_state;
     101
     102  /**
     103   * @brief The thread priority used by this scheduler instance in case no job
     104   * is released.
     105   */
     106  Priority_Control background_priority;
     107
     108  /**
     109   * @brief The thread priority currently used by this scheduler instance.
     110   */
     111  Priority_Control current_priority;
    117112} Scheduler_EDF_Node;
    118113

  • cpukit/score/include/rtems/score/scheduleredfimpl.h

    r9a78f8a5 r99fc1d1d  
    4545}
    4646
    47 int _Scheduler_EDF_Priority_compare (
    48   Priority_Control p1,
    49   Priority_Control p2
    50 );
     47RTEMS_INLINE_ROUTINE bool _Scheduler_EDF_Less(
     48  const void        *left,
     49  const RBTree_Node *right
     50)
     51{
     52  const Priority_Control   *the_left;
     53  const Scheduler_EDF_Node *the_right;
     54  Priority_Control          prio_left;
     55  Priority_Control          prio_right;
    5156
    52 RBTree_Compare_result _Scheduler_EDF_Compare(
    53   const RBTree_Node* n1,
    54   const RBTree_Node* n2
    55 );
     57  the_left = left;
     58  the_right = RTEMS_CONTAINER_OF( right, Scheduler_EDF_Node, Node );
     59
     60  prio_left = *the_left;
     61  prio_right = the_right->current_priority;
     62
     63  return prio_left < prio_right;
     64}
     65
     66RTEMS_INLINE_ROUTINE bool _Scheduler_EDF_Less_or_equal(
     67  const void        *left,
     68  const RBTree_Node *right
     69)
     70{
     71  const Priority_Control   *the_left;
     72  const Scheduler_EDF_Node *the_right;
     73  Priority_Control          prio_left;
     74  Priority_Control          prio_right;
     75
     76  the_left = left;
     77  the_right = RTEMS_CONTAINER_OF( right, Scheduler_EDF_Node, Node );
     78
     79  prio_left = *the_left;
     80  prio_right = the_right->current_priority;
     81
     82  return prio_left <= prio_right;
     83}
    5684
    5785RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
     86  Scheduler_EDF_Context *context,
     87  Scheduler_EDF_Node    *node,
     88  Priority_Control       current_priority
     89)
     90{
     91  _RBTree_Insert_inline(
     92    &context->Ready,
     93    &node->Node,
     94    &current_priority,
     95    _Scheduler_EDF_Less
     96  );
     97}
     98
     99RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue_first(
     100  Scheduler_EDF_Context *context,
     101  Scheduler_EDF_Node    *node,
     102  Priority_Control       current_priority
     103)
     104{
     105  _RBTree_Insert_inline(
     106    &context->Ready,
     107    &node->Node,
     108    &current_priority,
     109    _Scheduler_EDF_Less_or_equal
     110  );
     111}
     112
     113RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Extract(
     114  Scheduler_EDF_Context *context,
     115  Scheduler_EDF_Node    *node
     116)
     117{
     118  _RBTree_Extract( &context->Ready, &node->Node );
     119}
     120
     121RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Extract_body(
    58122  const Scheduler_Control *scheduler,
    59123  Thread_Control          *the_thread
    60124)
    61125{
    62   Scheduler_EDF_Context *context =
    63     _Scheduler_EDF_Get_context( scheduler );
    64   Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
     126  Scheduler_EDF_Context *context;
     127  Scheduler_EDF_Node    *node;
    65128
    66   _RBTree_Insert(
    67     &context->Ready,
    68     &node->Node,
    69     _Scheduler_EDF_Compare,
    70     false
    71   );
    72   node->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES;
    73 }
     129  context = _Scheduler_EDF_Get_context( scheduler );
     130  node = _Scheduler_EDF_Thread_get_node( the_thread );
    74131
    75 RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Extract(
    76   const Scheduler_Control *scheduler,
    77   Thread_Control          *the_thread
    78 )
    79 {
    80   Scheduler_EDF_Context *context =
    81     _Scheduler_EDF_Get_context( scheduler );
    82   Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
    83 
    84   _RBTree_Extract( &context->Ready, &node->Node );
     132  _Scheduler_EDF_Extract( context, node );
    85133}
    86134
    … …  
    91139)
    92140{
    93   Scheduler_EDF_Context *context =
    94     _Scheduler_EDF_Get_context( scheduler );
    95   RBTree_Node *first = _RBTree_Minimum( &context->Ready );
    96   Scheduler_EDF_Node *node =
    97     RTEMS_CONTAINER_OF( first, Scheduler_EDF_Node, Node );
    98   Thread_Control *heir = node->thread;
     141  Scheduler_EDF_Context *context;
     142  RBTree_Node           *first;
     143  Scheduler_EDF_Node    *node;
    99144
    100   ( void ) the_thread;
     145  (void) the_thread;
    101146
    102   _Scheduler_Update_heir( heir, force_dispatch );
     147  context = _Scheduler_EDF_Get_context( scheduler );
     148  first = _RBTree_Minimum( &context->Ready );
     149  node = RTEMS_CONTAINER_OF( first, Scheduler_EDF_Node, Node );
     150
     151  _Scheduler_Update_heir( node->thread, force_dispatch );
    103152}
    104153

  • cpukit/score/src/schedulercbsnodeinit.c

    r9a78f8a5 r99fc1d1d  
    2626)
    2727{
    28   Scheduler_CBS_Node *node = _Scheduler_CBS_Thread_get_node( the_thread );
     28  Scheduler_CBS_Node *node;
    2929
    30   (void) scheduler;
     30  _Scheduler_EDF_Node_initialize( scheduler, the_thread );
    3131
    32   _Scheduler_Node_do_initialize( &node->Base.Base, the_thread );
    33 
    34   node->Base.thread = the_thread;
    35   node->Base.queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN;
     32  node = _Scheduler_CBS_Thread_get_node( the_thread );
    3633  node->cbs_server = NULL;
    3734}

  • cpukit/score/src/schedulercbsunblock.c

    r9a78f8a5 r99fc1d1d  
    3131)
    3232{
    33   Scheduler_CBS_Node   *node = _Scheduler_CBS_Thread_get_node( the_thread );
    34   Scheduler_CBS_Server *serv_info = node->cbs_server;
    35   Priority_Control      new_priority;
     33  Scheduler_EDF_Context *context;
     34  Scheduler_CBS_Node    *node;
     35  Scheduler_CBS_Server  *serv_info;
     36  Priority_Control       priority;
    3637
    37   _Scheduler_EDF_Enqueue( scheduler, the_thread );
    38   /* TODO: flash critical section? */
     38  context = _Scheduler_EDF_Get_context( scheduler );
     39  node = _Scheduler_CBS_Thread_get_node( the_thread );
     40  serv_info = node->cbs_server;
     41  priority = node->Base.current_priority;
    3942
    4043  /*
    … …  
    4447   * miss of another task.
    4548   */
    46   if (serv_info) {
     49  if ( serv_info != NULL && ( priority & SCHEDULER_EDF_PRIO_MSB ) == 0 ) {
    4750    time_t deadline = serv_info->parameters.deadline;
    4851    time_t budget = serv_info->parameters.budget;
    49     time_t deadline_left = the_thread->cpu_time_budget;
    50     time_t budget_left = the_thread->real_priority -
    51                            _Watchdog_Ticks_since_boot;
     52    uint32_t deadline_left = the_thread->cpu_time_budget;
     53    Priority_Control budget_left = priority - _Watchdog_Ticks_since_boot;
    5254
    53     if ( deadline*budget_left > budget*deadline_left ) {
     55    if ( deadline * budget_left > budget * deadline_left ) {
    5456      /* Put late unblocked task to background until the end of period. */
    55       new_priority = the_thread->Start.initial_priority;
    56       the_thread->real_priority = new_priority;
    57       if ( the_thread->current_priority != new_priority ) {
    58         the_thread->current_priority = new_priority;
    59         _Scheduler_EDF_Change_priority(
    60           scheduler,
    61           the_thread,
    62           new_priority,
    63           true
    64         );
     57
     58      priority = node->Base.background_priority;
     59      the_thread->real_priority = priority;
     60
     61      if (
     62        _Thread_Priority_less_than( the_thread->current_priority, priority )
     63          || !_Thread_Owns_resources( the_thread )
     64      ) {
     65        the_thread->current_priority = priority;
    6566      }
    6667    }
    6768  }
     69
     70  node->Base.current_priority = priority;
     71  _Scheduler_EDF_Enqueue( context, &node->Base, priority );
    6872
    6973  /*
    … …  
    7983   *    a pseudo-ISR system task, we need to do a context switch.
    8084   */
    81   if (
    82     _Scheduler_EDF_Priority_compare(
    83       the_thread->current_priority,
    84       _Thread_Heir->current_priority
    85     ) == 1
    86   ) {
    87     _Scheduler_Update_heir(
    88       the_thread,
    89       the_thread->current_priority == PRIORITY_PSEUDO_ISR
    90     );
     85  if ( priority < _Thread_Heir->current_priority ) {
     86    _Scheduler_Update_heir( the_thread, priority == PRIORITY_PSEUDO_ISR );
    9187  }
    9288

  • cpukit/score/src/scheduleredf.c

    r9a78f8a5 r99fc1d1d  
    2121#include <rtems/score/scheduleredfimpl.h>
    2222
    23 int _Scheduler_EDF_Priority_compare (
    24   Priority_Control p1,
    25   Priority_Control p2
    26 )
    27 {
    28   Watchdog_Interval time = _Watchdog_Ticks_since_boot;
    29 
    30   /*
    31    * Reorder priorities to separate deadline driven and background tasks.
    32    *
    33    * The background tasks have p1 or p2 > SCHEDULER_EDF_PRIO_MSB.
    34    * The deadline driven tasks need to have subtracted current time in order
    35    * to see which deadline is closer wrt. current time.
    36    */
    37   if (!(p1 & SCHEDULER_EDF_PRIO_MSB))
    38     p1 = (p1 - time) & ~SCHEDULER_EDF_PRIO_MSB;
    39   if (!(p2 & SCHEDULER_EDF_PRIO_MSB))
    40     p2 = (p2 - time) & ~SCHEDULER_EDF_PRIO_MSB;
    41 
    42   return ((p1<p2) - (p1>p2));
    43 }
    44 
    45 RBTree_Compare_result _Scheduler_EDF_Compare(
    46   const RBTree_Node* n1,
    47   const RBTree_Node* n2
    48 )
    49 {
    50   Scheduler_EDF_Node *edf1 =
    51     RTEMS_CONTAINER_OF( n1, Scheduler_EDF_Node, Node );
    52   Scheduler_EDF_Node *edf2 =
    53     RTEMS_CONTAINER_OF( n2, Scheduler_EDF_Node, Node );
    54   Priority_Control value1 = edf1->thread->current_priority;
    55   Priority_Control value2 = edf2->thread->current_priority;
    56 
    57   /*
    58    * This function compares only numbers for the red-black tree,
    59    * but priorities have an opposite sense.
    60    */
    61   return (-1)*_Scheduler_EDF_Priority_compare(value1, value2);
    62 }
    63 
    6423void _Scheduler_EDF_Initialize( const Scheduler_Control *scheduler )
    6524{

  • cpukit/score/src/scheduleredfblock.c

    r9a78f8a5 r99fc1d1d  
    3030    scheduler,
    3131    the_thread,
    32     _Scheduler_EDF_Extract,
     32    _Scheduler_EDF_Extract_body,
    3333    _Scheduler_EDF_Schedule_body
    3434  );

  • cpukit/score/src/scheduleredfchangepriority.c

    r9a78f8a5 r99fc1d1d  
    4444)
    4545{
    46   Scheduler_EDF_Context *context =
    47     _Scheduler_EDF_Get_context( scheduler );
    48   Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
     46  Scheduler_EDF_Context *context;
     47  Scheduler_EDF_Node    *node;
    4948
    50   _RBTree_Extract( &context->Ready, &node->Node );
    51   _RBTree_Insert(
    52     &context->Ready,
    53     &node->Node,
    54     _Scheduler_EDF_Compare,
    55     false
    56   );
     49  context = _Scheduler_EDF_Get_context( scheduler );
     50  node = _Scheduler_EDF_Thread_get_node( the_thread );
     51
     52  if ( ( new_priority & SCHEDULER_EDF_PRIO_MSB ) != 0 ) {
     53    node->background_priority = new_priority;
     54  }
     55
     56  node->current_priority = new_priority;
     57
     58  _Scheduler_EDF_Extract( context, node );
     59
     60  if ( prepend_it ) {
     61    _Scheduler_EDF_Enqueue_first( context, node, new_priority );
     62  } else {
     63    _Scheduler_EDF_Enqueue( context, node, new_priority );
     64  }
    5765
    5866  _Scheduler_EDF_Schedule_body( scheduler, the_thread, false );

  • cpukit/score/src/scheduleredfnodeinit.c

    r9a78f8a5 r99fc1d1d  
    3333
    3434  node->thread = the_thread;
    35   node->queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN;
    3635}

  • cpukit/score/src/scheduleredfreleasejob.c

    r9a78f8a5 r99fc1d1d  
    1919#endif
    2020
    21 #include <rtems/score/scheduleredf.h>
    22 #include <rtems/score/threadimpl.h>
    23 #include <rtems/score/watchdogimpl.h>
     21#include <rtems/score/scheduleredfimpl.h>
     22
     23static bool _Scheduler_EDF_Priority_filter(
     24  Thread_Control   *the_thread,
     25  Priority_Control *new_priority_p,
     26  void             *arg
     27)
     28{
     29  Scheduler_EDF_Node *node;
     30  Priority_Control    current_priority;
     31  Priority_Control    new_priority;
     32
     33  node = _Scheduler_EDF_Thread_get_node( the_thread );
     34
     35  current_priority = the_thread->current_priority;
     36  new_priority = *new_priority_p;
     37
     38  if ( new_priority == 0 ) {
     39    new_priority = node->background_priority;
     40  }
     41
     42  node->current_priority = new_priority;
     43  the_thread->real_priority = new_priority;
     44
     45  return _Thread_Priority_less_than( current_priority, new_priority )
     46    || !_Thread_Owns_resources( the_thread );
     47}
    2448
    2549void _Scheduler_EDF_Release_job(
    … …  
    2953)
    3054{
    31   Priority_Control new_priority;
    32   Priority_Control unused;
    33 
    34   (void) scheduler;
    35 
    36   if (deadline) {
    37     /* Initializing or shifting deadline. */
    38     new_priority = (uint32_t) deadline & ~SCHEDULER_EDF_PRIO_MSB;
    39   }
    40   else {
    41     /* Switch back to background priority. */
    42     new_priority = the_thread->Start.initial_priority;
    43   }
    44 
    45   _Thread_Set_priority( the_thread, new_priority, &unused, true );
     55  _Thread_Change_priority(
     56    the_thread,
     57    (Priority_Control) deadline,
     58    NULL,
     59    _Scheduler_EDF_Priority_filter,
     60    true
     61  );
    4662}

  • cpukit/score/src/scheduleredfunblock.c

    r9a78f8a5 r99fc1d1d  
    2828)
    2929{
    30   _Scheduler_EDF_Enqueue( scheduler, the_thread );
    31   /* TODO: flash critical section? */
     30  Scheduler_EDF_Context *context;
     31  Scheduler_EDF_Node    *node;
     32
     33  context = _Scheduler_EDF_Get_context( scheduler );
     34  node = _Scheduler_EDF_Thread_get_node( the_thread );
     35
     36  _Scheduler_EDF_Enqueue( context, node, node->current_priority );
    3237
    3338  /*
    … …  
    4348   *    a pseudo-ISR system task, we need to do a context switch.
    4449   */
    45   if (
    46     _Scheduler_EDF_Priority_compare(
    47       the_thread->current_priority,
    48       _Thread_Heir->current_priority
    49     ) == 1
    50   ) {
     50  if ( the_thread->current_priority < _Thread_Heir->current_priority ) {
    5151    _Scheduler_Update_heir(
    5252      the_thread,

  • cpukit/score/src/scheduleredfupdate.c

    r9a78f8a5 r99fc1d1d  
    2727)
    2828{
    29   Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
     29  Scheduler_EDF_Node *node;
    3030
    31   (void) scheduler;
    32   (void) new_priority;
     31  node = _Scheduler_EDF_Thread_get_node( the_thread );
    3332
    34   if (node->queue_state == SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN) {
    35     /* Shifts the priority to the region of background tasks. */
    36     the_thread->Start.initial_priority |= (SCHEDULER_EDF_PRIO_MSB);
    37     the_thread->real_priority    = the_thread->Start.initial_priority;
    38     the_thread->current_priority = the_thread->Start.initial_priority;
    39     node->queue_state = SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY;
     33  if ( ( new_priority & SCHEDULER_EDF_PRIO_MSB ) != 0 ) {
     34    node->background_priority = new_priority;
    4035  }
     36
     37  node->current_priority = new_priority;
    4138}

  • cpukit/score/src/scheduleredfyield.c

    r9a78f8a5 r99fc1d1d  
    2727)
    2828{
    29   Scheduler_EDF_Context *context =
    30     _Scheduler_EDF_Get_context( scheduler );
    31   Scheduler_EDF_Node    *node = _Scheduler_EDF_Thread_get_node( the_thread );
     29  Scheduler_EDF_Context *context;
     30  Scheduler_EDF_Node    *node;
    3231
    33   /*
    34    * The RBTree has more than one node, enqueue behind the tasks
    35    * with the same priority in case there are such ones.
    36    */
    37   _RBTree_Extract( &context->Ready, &node->Node );
    38   _RBTree_Insert(
    39     &context->Ready,
    40     &node->Node,
    41     _Scheduler_EDF_Compare,
    42     false
    43   );
     32  context = _Scheduler_EDF_Get_context( scheduler );
     33  node = _Scheduler_EDF_Thread_get_node( the_thread );
    4434
     35  _Scheduler_EDF_Extract( context, node );
     36  _Scheduler_EDF_Enqueue( context, node, node->current_priority );
    4537  _Scheduler_EDF_Schedule_body( scheduler, the_thread, false );
    4638
Note: See TracChangeset for help on using the changeset viewer.