我们之前介绍了优先级调度算法和简单优先级调度算法，这两种调度算法都是基于优先级的值来调度的，也就是每个任务在创建的时候，会分配一个优先级，那么较高优先级始终比较低优先级优先调度。今天我们介绍rtems中另一种调度算法，EDF，最早截止事件调度算法

介绍EDF调度算法

对于最早截止时间调度算法而言，默认情况下会给任务分配一个截止事件，调度器根据每个任务的截止时间来确定优先级，它需要预设一个周期，当任务的实际运行时间越靠近周期设置时间，那么任务的优先级越高。这里优先级的动态调整通过的是timer来实现。
下面通过图示来介绍一下EDF调度算法的工作规则
现在加上，有任务A,B,C共三个任务，其中：

A任务运行时间为2s，A任务的截止时间(周期)是8s
B任务运行时间为3s，B任务的截止时间(周期)是6s
C任务运行时间为1s，C任务的截止时间(周期)是4S

根据上面的信息，实际EDF的执行流程会如下表现

光看图片可能不好理解，如下解释一下就清楚了：

根据EDF调度的定义，从0时刻开始调度，那么C的优先级最高，因为C的截止时间最短
到第1s的时候，C任务完成执行，但是还没有到周期，此时B任务截止时间是5，A任务截止时间是7，此时B优先级高
到第4s的时候，B任务完成调度，此时C任务也到达周期，C任务的截止时间是4，A任务的截止时间是4，但是A先如的队列，默认执行A
到第6s的时候，A任务完成执行，此时B任务到达周期，B任务截止时间是6，C任务优先级最高，默认执行C
到第7s的时候，C任务完成，开始执行B任务
到第10s的时候，B任务完成，并且没到截止时间，此时A任务的截止时间是8s，C任务优先执行
第11s的时候，A任务得以执行，因为B和C都未到截止时间
以此类推。

根据上面的详细解释，我们知道了edf调度算法的执行逻辑，下面查看实现

预设周期

根据上面分析的，如果我们需要使用edf调度算法将任务运行，那么任务必须要有一个周期值设置，在rtems中，设置周期的方式如下


status = rtems_rate_monotonic_create( argument, &rmid );
status = rtems_rate_monotonic_period( rmid, Periods[ argument ] );
status = rtems_rate_monotonic_delete( rmid );

上面的意思非常容易理解，就是为edf调度器设置一个周期，其实现通过timer。
那其实际对timer的操作如下


_Watchdog_Initialize( &the_period->Timer, _Rate_monotonic_Timeout );
deadline = _Watchdog_Per_CPU_insert_ticks(
    &the_period->Timer,
    cpu_self,
    next_length
);

值得注意的是，这里会提前设置周期的长度为 Periods的值，如下


the_period->next_length = length;

所以当timeout的时候，会再次重启timer。


_Rate_monotonic_Restart( the_period, owner, &lock_context );

或


_Rate_monotonic_Renew_deadline( the_period, &lock_context );

根据截止时间设置优先级

根据上面的介绍，我们知道了edf调度算法会通过截止时间来动态调整优先级，也知道了默认情况下我们会预先设置一个周期值，这个周期值就是rtems_rate_monotonic_period的第二个参数，接下来，我们需要明确edf算法如何根据截止时间来动态调整优先级
首先，我们关注_Rate_monotonic_Release_job函数，其实现如下


static void _Rate_monotonic_Release_job(
  Rate_monotonic_Control *the_period,
  Thread_Control         *owner,
  rtems_interval          next_length,
  ISR_lock_Context       *lock_context
)
{
  Per_CPU_Control      *cpu_self;
  Thread_queue_Context  queue_context;
  uint64_t              deadline;

  cpu_self = _Thread_Dispatch_disable_critical( lock_context );

  deadline = _Watchdog_Per_CPU_insert_ticks(
    &the_period->Timer,
    cpu_self,
    next_length
  );
  _Scheduler_Release_job(
    owner,
    &the_period->Priority,
    deadline,
    &queue_context
  );

  _Rate_monotonic_Release( the_period, lock_context );
  _Thread_Priority_update( &queue_context );
  _Thread_Dispatch_enable( cpu_self );
}

上述函数的步骤如下

为周期值开启一个定时器watchdog,返回定时器的时间period
根据定时器时间来确定deadline
根据deadline来调整scheduler edf的优先级Priority
在edf调度器中更新优先级的值
打开线程dispatch

我将关键点函数提取出来如下


rtems_rate_monotonic_period( rmid, Periods[ argument ] );
_Watchdog_Insert(header, the_watchdog, expire);
deadline = _Watchdog_Per_CPU_insert_ticks(*)
_Priority_Node_set_priority(*)
_Thread_Priority_update( &queue_context );
_Thread_Dispatch_enable( cpu_self );

根据上面的代码流程，我们知道了，在edf调度算法中，一个周期Period内，优先级是根据watchdog的expire来动态调整，expire的值会换算成调度器的priority值，edf调度算法根据此值来动态调整任务的优先级

红黑树管理优先级

对于调度器的优先级管理，edf中使用的是红黑树，其主要函数如下


    _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_Update_priority,  /* update priority entry point */ \

下面我们逐个介绍调度器管理优先级的方式

执行调度

_Scheduler_EDF_Schedule的作用是将当前任务调度一次，此时需要获得优先级最高的任务，对于edf而言，默认expire值最小说明优先级越高，所以在红黑树中是获得最小的节点，在红黑树获得最小节点的方式是遍历根节点，找其左孩子
那么执行调度过程中，获得最高优先级任务的方式如下


RBTree_Node *_RBTree_Minimum( const RBTree_Control *tree )
{
  RBTree_Node *parent;
  RBTree_Node *node;

  parent = NULL;
  node = _RBTree_Root( tree );

  while ( node != NULL ) {
    parent = node;
    node = _RBTree_Left( node );
  }

  return parent;
}

当找到优先级最高的任务之后，直接设置其标志位为true即可


_Scheduler_uniprocessor_Schedule
_Thread_Dispatch_necessary = true;

让出任务

对于让出任务而言，我们需要做的是

将任务从红黑树中删除
根据新的优先级，将任务插入到红黑树中
执行调度

关于1，其实就是红黑树的删除操作，其代码如下


RTEMS_RB_REMOVE( RBTree_Control, the_rbtree, the_node );

关于红黑树的删除，可以查看文章<rb-tree实现-删除操作-原理>

关于2，其实就是红黑树的插入操作，其代码如下


static inline bool _RBTree_Insert_inline(
  RBTree_Control *the_rbtree,
  RBTree_Node    *the_node,
  const void     *key,
  bool         ( *less )( const void *, const RBTree_Node * )
)
{
  RBTree_Node **link;
  RBTree_Node  *parent;
  bool          is_new_minimum;

  link = _RBTree_Root_reference( the_rbtree );
  parent = NULL;
  is_new_minimum = true;

  while ( *link != NULL ) {
    parent = *link;

    if ( ( *less )( key, parent ) ) {
      link = _RBTree_Left_reference( parent );
    } else {
      link = _RBTree_Right_reference( parent );
      is_new_minimum = false;
    }
  }

  _RBTree_Add_child( the_node, parent, link );
  _RBTree_Insert_color( the_rbtree, the_node );
  return is_new_minimum;
}

根据上面的代码，我们可以知道，在插入之前，我们需要遍历根节点，找到小于等于某个节点的位置，然后如果待插入节点插入到其节点的左边。然后执行红黑树的插入操作_RBTree_Insert_color
关于红黑树的插入，可以查看文章<rb-tree实现-插入操作-原理>

阻塞任务

对于阻塞当前任务，我们需要做的是

将任务从红黑树中删除
执行调度

代码如下


static inline void _Scheduler_uniprocessor_Block(
  const Scheduler_Control *scheduler,
  Thread_Control          *the_thread,
  Scheduler_Node          *node,
  void                  ( *extract )(
                             const Scheduler_Control *,
                             Thread_Control *,
                             Scheduler_Node *
                        ),
  Thread_Control       *( *get_highest_ready )( const Scheduler_Control * )
)
{
  ( *extract )( scheduler, the_thread, node );

  /* TODO: flash critical section? */

  if ( _Thread_Is_heir( the_thread ) ) {
    Thread_Control *highest_ready;

    highest_ready = ( *get_highest_ready )( scheduler );
    _Scheduler_uniprocessor_Update_heir( _Thread_Heir, highest_ready );
  }
}

恢复任务

对于当前任务恢复调度，就是将其加入就绪队列中，也就是红黑树的插入操作，其代码如下


void _Scheduler_EDF_Unblock(
  const Scheduler_Control *scheduler,
  Thread_Control          *the_thread,
  Scheduler_Node          *node
)
{
  Scheduler_EDF_Context *context;
  Scheduler_EDF_Node    *the_node;
  Priority_Control       priority;
  Priority_Control       insert_priority;

  context = _Scheduler_EDF_Get_context( scheduler );
  the_node = _Scheduler_EDF_Node_downcast( node );
  priority = _Scheduler_Node_get_priority( &the_node->Base );
  priority = SCHEDULER_PRIORITY_PURIFY( priority );
  insert_priority = SCHEDULER_PRIORITY_APPEND( priority );

  the_node->priority = priority;
  _Scheduler_EDF_Enqueue( context, the_node, insert_priority );
  _Scheduler_uniprocessor_Unblock( scheduler, the_thread, priority );
}

这里就绪队列的入队_Scheduler_EDF_Enqueue就是红黑树的插入操作

总结

至此，我们讲解了edf调度的原理，接下来通过实验来演示edf调度

目录