rtems不仅支持基于优先级调度的算法，也支持简单优先级调度算法，简单优先级算法相比于优先级调度算法而言减少了bitmap，直接通过优先级和队列FIFO特性来更新调度优先级。本文介绍rtems中简单优先级的实现方法

调度器结构体

我们通过_Scheduler_simple_Initialize函数可以知道此调度算法的结构体构造，如下


void _Scheduler_simple_Initialize( const Scheduler_Control *scheduler )
{
  Scheduler_simple_Context *context =
    _Scheduler_simple_Get_context( scheduler );

  _Chain_Initialize_empty( &context->Ready );
}

首先，需要构造一个Scheduler_simple_Context结构体，其成员如下


typedef struct {
  /**
   * @brief Basic scheduler context.
   */
  Scheduler_Context Base;

  /**
   * @brief One ready queue for all ready threads.
   */
  Chain_Control Ready;
} Scheduler_simple_Context;

可以发现，此结构体的上下文只包含了调度器上下文和一个链表，这个链表就是此调度算法的实现
我们知道此调度算法通过链表，所以需要初始化链表如下


static inline void _Chain_Initialize_empty(
  Chain_Control *the_chain
)
{
  Chain_Node *head;
  Chain_Node *tail;

  _Assert( the_chain != NULL );

  head = _Chain_Head( the_chain );
  tail = _Chain_Tail( the_chain );

  head->next = tail;
  head->previous = NULL;
  tail->previous = head;
}

执行调度

对于基于队列的调度算法，其schedule函数就是将最高优先级的元素出队，如下


static inline Thread_Control *_Scheduler_simple_Get_highest_ready(
  const Scheduler_Control *scheduler
)
{
  Scheduler_simple_Context *context =
    _Scheduler_simple_Get_context( scheduler );

  return (Thread_Control *) _Chain_First( &context->Ready );
}

因为队列的FIFO结构，默认最高优先级的元素在队列头。所以直接从head->next拿即可。

阻塞任务

对于基于队列的调度算法，阻塞任务的方式就是从队列中解压出此任务，让其不在就绪队列中，如下


static inline void _Chain_Extract_unprotected(
  Chain_Node *the_node
)
{
  Chain_Node *next;
  Chain_Node *previous;

  _Assert( !_Chain_Is_node_off_chain( the_node ) );

  next           = the_node->next;
  previous       = the_node->previous;
  next->previous = previous;
  previous->next = next;

#if defined(RTEMS_DEBUG)
  _Chain_Set_off_chain( the_node );
#endif
}

任务就绪

对于基于队列的调度算法，任务就绪主要两个部分

将待插入的任务和就绪队列所有元素对比，找到小于等于的队列位置
插入队列

对于遍历就绪队列的代码如下


  while ( next != tail && !( *order )( key, to_insert, next ) ) {
    previous = next;
    next = _Chain_Next( next );
  }

这里的order就是根据遍历的元素，找到小于等于的队列位置，如下代码实现


static inline bool _Scheduler_simple_Priority_less_equal(
  const void       *key,
  const Chain_Node *to_insert,
  const Chain_Node *next
)
{
  const unsigned int   *priority_to_insert;
  const Thread_Control *thread_next;

  (void) to_insert;
  priority_to_insert = (const unsigned int *) key;
  thread_next = (const Thread_Control *) next;

  return *priority_to_insert <= _Thread_Get_priority( thread_next );
}

根据上面的操作，可以找到待插入的位置，然后执行队列的插入操作即可


static inline void _Chain_Insert_unprotected(
  Chain_Node *after_node,
  Chain_Node *the_node
)
{
  Chain_Node *before_node;

  _Assert( _Chain_Is_node_off_chain( the_node ) );

  the_node->previous    = after_node;
  before_node           = after_node->next;
  after_node->next      = the_node;
  the_node->next        = before_node;
  before_node->previous = the_node;
}

优先级更新

基于队列的优先级调度算法的更新优先级，主要如下操作

将待更新的任务取出
与任务就绪一致，找到队列中小于等于待更新优先级的位置
插入任务
执行调度

这里取出操作就是阻塞操作中的解压任务_Chain_Extract_unprotected
这里找到匹配的位置插入的操作和就绪任务一致这里执行调度的操作就是让最高优先级的任务得以调度

总结

至此，我们完全了解的简单优先级调度算法的逻辑了，其相比于优先级调度算法而言，没有使用位图。设计更加简单，因为位图占用一定的内存资源，故此调度器算法内存占用少。而又因为位图的时间复杂度是O(1),遍历队列链表的复杂度是O(n)。
故简单优先级调度算法，减少了内存占用，牺牲了一些性能，比较适合非常简单的任务系统

目录

调度器结构体

执行调度

阻塞任务

任务就绪

优先级更新

总结