RTEMS线程调度算法（RMS）详解

RTEMS是以线程为基本调度单位的，调度算法基于优先级的抢占式线程调度，支持256个线程优先级。当然RTEMS值hi创建同等优先级线程，相同优先级的线程采用时间片轮转调度。调度器寻找下一个最高优先级就绪线程的时间是o(1)，这是实时性得到保障的一个关键机制。

为了增强对用户应用需求的可扩展性，rtems实现了基于线程的任务扩展机制，可在创建任务、上下文切换或者删除任务等系统事件发生时插入用户指定的函数（称为钩子函数，hook函数），以完成用户设定的特殊功能。

对于RTEMS这样的基于抢占式和优先级策略调度的os而言，为保证硬实时特性，需要选择一个合适的调度算法，静态调度算法-速率单调调度RMS是为周期性任务解决多任务调度的一种很好的算法。

本文会先介绍核心层的thread handler组件与调度实现，然后对RMS算法在RTEMS上的实现进行分析。

核心层的thread handler组件：

RTEMS的调度相对于通用操作系统而言较为简单，主要是基于线程的优先级进行的，除了对于优先级反转问题需要在运行时改变线程的优先级外，其他情况下不会对线程的优先级修改。

thread handler组件提供了thread_control结构体和以此配套的一组基本线程管理数据结构和管理函数，涉及线程初始化，线程启动，线程暂停，线程恢复，线程切换等。不同的高层API接口实现只是对这些结构和函数进行封装，这样线程管理就可以分为两层，方便API接口进行拓展。

1.线程控制块（TCB）

thread control block是thread handler组件对线程的静态进本情况和动态运行变化过程的描述，其包含了与线程运行管理所需要的所有信息集合，是线程存在的唯一标志。线程的创建主要体现在为该线程生成一个TCB，而线程终止则体现在回收其TCB。

TCB定义在cpukit/score/include/rtems/score/thread.h中，如下：

/**
 *  This structure defines the Thread Control Block (TCB).
 */
struct Thread_Control_struct {
  /** This field is the object management structure for each thread. */
  Objects_Control          Object;
  /** This field is used to enqueue the thread on RBTrees. */
  RBTree_Node              RBNode;
  /** This field is the current execution state of this thread. */
  States_Control           current_state;
  /** This field is the current priority state of this thread. */
  Priority_Control         current_priority;
  /** This field is the base priority of this thread. */
  Priority_Control         real_priority;

  /**
   * @brief Thread priority control.
   */
  Thread_Priority_control  Priority;

  /** This field is the number of mutexes currently held by this thread. */
  uint32_t                 resource_count;
  /** This field is the blocking information for this thread. */
  Thread_Wait_information  Wait;
  /** This field is the Watchdog used to manage thread delays and timeouts. */
  Watchdog_Control         Timer;
#if defined(RTEMS_MULTIPROCESSING)
  /** This field is the received response packet in an MP system. */
  MP_packet_Prefix        *receive_packet;
#endif
     /*================= end of common block =================*/

#if defined(RTEMS_SMP)
  /**
   * @brief Thread lock control.
   */
  Thread_Lock_control Lock;
#endif

#ifdef __RTEMS_STRICT_ORDER_MUTEX__
  /** This field is the head of queue of priority inheritance mutex
   *  held by the thread.
   */
  Chain_Control            lock_mutex;
#endif
#if defined(RTEMS_SMP)
  /**
   * @brief Resource node to build a dependency tree in case this thread owns
   * resources or depends on a resource.
   */
  Resource_Node            Resource_node;
#endif
#if defined(RTEMS_MULTIPROCESSING)
  /** This field is true if the thread is offered globally */
  bool                                  is_global;
#endif
  /** This field is true if the thread is preemptible. */
  bool                                  is_preemptible;

  /**
   * @brief Scheduler related control.
   */
  Thread_Scheduler_control              Scheduler;

#if __RTEMS_ADA__
  /** This field is the GNAT self context pointer. */
  void                                 *rtems_ada_self;
#endif
  /** This field is the length of the time quantum that this thread is
   *  allowed to consume.  The algorithm used to manage limits on CPU usage
   *  is specified by budget_algorithm.
   */
  uint32_t                              cpu_time_budget;
  /** This field is the algorithm used to manage this thread's time
   *  quantum.  The algorithm may be specified as none which case,
   *  no limit is in place.
   */
  Thread_CPU_budget_algorithms          budget_algorithm;
  /** This field is the method invoked with the budgeted time is consumed. */
  Thread_CPU_budget_algorithm_callout   budget_callout;
  /** This field is the amount of CPU time consumed by this thread
   *  since it was created.
   */
  Thread_CPU_usage_t                    cpu_time_used;

  /** This field contains information about the starting state of
   *  this thread.
   */
  Thread_Start_information              Start;

  Thread_Action_control                 Post_switch_actions;

  /** This field contains the context of this thread. */
  Context_Control                       Registers;
#if ( CPU_HARDWARE_FP == TRUE ) || ( CPU_SOFTWARE_FP == TRUE )
  /** This field points to the floating point context for this thread.
   *  If NULL, the thread is integer only.
   */
  Context_Control_fp                   *fp_context;
#endif
  /** This field points to the newlib reentrancy structure for this thread. */
  struct _reent                        *libc_reent;
  /** This array contains the API extension area pointers. */
  void                                 *API_Extensions[ THREAD_API_LAST + 1 ];

#if !defined(RTEMS_SMP)
  /** This field points to the set of per task variables. */
  rtems_task_variable_t                *task_variables;
#endif

  /**
   * This is the thread key value chain's control, which is used
   * to track all key value for specific thread, and when thread
   * exits, we can remove all key value for specific thread by
   * iterating this chain, or we have to search a whole rbtree,
   * which is inefficient.
   */
  Chain_Control           Key_Chain;

  /**
   * @brief Thread life-cycle control.
   *
   * Control state changes triggered by thread restart and delete requests.
   */
  Thread_Life_control                   Life;

  Thread_Capture_control                Capture;

  /**
   * @brief Variable length array of user extension pointers.
   *
   * The length is defined by the application via <rtems/confdefs.h>.
   */
  void                                 *extensions[ RTEMS_ZERO_LENGTH_ARRAY ];
};

其中解释几个重要的成员变量：

object是线程作为对象而存在的对象管理结构，也就是说TCB结构是作为一个对象。

real_priority和current_priority是线程的基础优先级和当前运行的优先级。

resource_count是代表线程获取到的资源（互斥量）数量，是为了实现优先级继承算法和优先级天花板算法而设计的。

cpu_time_budget是分配给线程的时间片，而budget_algorithm是用来管理该时间片的算法。RTEMS支持如下四种时间片算法配置：

 a. THREAD_CPU_BUDGET_ALGORITHM_NONE //不使用budget算法

 b. THREAD_CPU_BUDGET_ALGORITHM_RESET_TIMESLICE //线程切换时重新设置时间片

c. THREAD_CPU_BUDGET_ALGORITHM_EXHAUST_TIMESLICE //线程时用完时间片才重置

d. THREAD_CPU_BUDGET_ALGORITHM_CALLOUT //时间片用完时调用回调函数

通常在嵌入式系统中，为了节省内粗怒，内核所支持的最大线程数量是静态配置好的，在RTEMS中是通过宏定义完成的：

#define CONFIGURE_MAXIMUM_TASKS            1

通常是在testsuites例子程序的init.c文件中。

这样在系统初始化时可以根据线程的个数来为TCB分配内存，构成一个空闲的线程控制块链，创建线程时从该链上取出空闲TCB进行初始化，删除线程时，将该TCB返回到空闲链中。

2.线程调度机制

RTEMS中基本采用可抢占的调度方式，为了实现更加灵活的调度手段，RTEMS提供四种机制允许用户对线程调度进行干预：

a.用户执行线程优先级（可动态修改）

b.线程抢占式控制（该线程是否会被抢占）：用户可通过改变TCB中抢占模式标志（RTEMS_PREEMPT_MASK）影响调度的策略。若抢占位置为无效，那么线程就不会被抢占，除非线程结束或者被阻塞。否则就算有较高的优先级线程就绪，线程也不会被抢占。

c.线程时间片控制：基于优先级的时分复用，也称为轮转调度，如果时分复用状态位通过RTEMS_TIMESLICE使能，那么RTEMS将会限制线程在处理器中的运行时间，若到达该线程的运行时间片，将会被其他线程取代。但是当一个较高的优先级线程就绪时，会立即抢占处理器中低优先级的线程，即使线程还没用光其整个时间片。 也就是说时间片控制适用于同等优先级线程之间的调度。

d.主动放弃处理器，程序员可使用rtems_task_wake_after函数主动放弃对CPU的占用。

3.线程上下文

运行的线程变为就绪或者阻塞时，都需要保存当前进程的上下文。线程的上下文是和硬件的体系结构密切相关，RTEMS中，ARM的上下文定义如下：

typedef struct {
#if defined(ARM_MULTILIB_ARCH_V4)
  uint32_t register_cpsr;
  uint32_t register_r4;
  uint32_t register_r5;
  uint32_t register_r6;
  uint32_t register_r7;
  uint32_t register_r8;
  uint32_t register_r9;
  uint32_t register_r10;
  uint32_t register_fp;
  uint32_t register_sp;
  uint32_t register_lr;
#elif defined(ARM_MULTILIB_ARCH_V6M) || defined(ARM_MULTILIB_ARCH_V7M)
  uint32_t register_r4;
  uint32_t register_r5;
  uint32_t register_r6;
  uint32_t register_r7;
  uint32_t register_r8;
  uint32_t register_r9;
  uint32_t register_r10;
  uint32_t register_r11;
  void *register_lr;
  void *register_sp;
  uint32_t isr_nest_level;
#else
  void *register_sp;
#endif
#ifdef ARM_MULTILIB_HAS_THREAD_ID_REGISTER
  uint32_t thread_id;
#endif
#ifdef ARM_MULTILIB_VFP
  uint64_t register_d8;
  uint64_t register_d9;
  uint64_t register_d10;
  uint64_t register_d11;
  uint64_t register_d12;
  uint64_t register_d13;
  uint64_t register_d14;
  uint64_t register_d15;
#endif
#ifdef RTEMS_SMP
  volatile bool is_executing;
#endif
} Context_Control;

TCB中的Registers就是上下文的变量。

4.线程的优先级管理

每个优先级的就绪的线程都是一个FIFO链表，TCB中会包含该链表，便于线程调度时的操作。_thread_ready_chain就是由各个优先级的FIFO构成的数组，这是一个全局变量。

chain_control结构是对FIFO链表进行管理的数据结构，包含了链表的头和尾，这样可以很快确定每个优先级的第一个线程和最后一个。但问题在于，不容易确定下一个优先级最高的线程，如果切换出来的线程所在的优先级只有一个就绪线程，那么就需要在_thread_ready_chain数组中找到优先级最高的就绪线程，这是一个耗时的操作，因此RTEMS采用位图的方法解决了这个问题。它把256个优先级分为16*16，这样的话，就相当于两个16位整数就可以表示了，也就是两个16位长的二进制数组。这样提高了搜索速度。这样一个priority优先级可以分为major(priority/16)和minor(priority%16)两部分。major*16+minor.

RTEMS中的RMS实时调度

RMS速率单调调度算法基于以下假设：

a. 所有任务都是周期任务

b. 任务的相对截止时间等于任务周期

c.任务在每个周期的计算时间都相等

d.任务之间不进行通信，也不需要同步，是独立的

e.任何可以在计算的任何位置被抢占

任务的优先级和任务的周期表吓你为单调函数关系，任务周期越短，任务优先级越高。静态是指任务的优先级是事前确定的，在任务运行过程中不会改变。

关键数据结构

typedef struct {
  /** This field is the object management portion of a Period instance. */
  Objects_Control                         Object;

  /**
   * @brief Protects the rate monotonic period state.
   */
  ISR_LOCK_MEMBER(                        Lock )

  /** This is the timer used to provide the unblocking mechanism. */
  Watchdog_Control                        Timer;

  /** This field indicates the current state of the period. */
  rtems_rate_monotonic_period_states      state;

  /**
   * @brief A priority node for use by the scheduler job release and cancel
   * operations.
   */
  Priority_Node                           Priority;

  /**
   * This field contains the length of the next period to be
   * executed.
   */
  uint32_t                                next_length;

  /**
   * This field contains a pointer to the TCB for the thread
   * which owns and uses this period instance.
   */
  Thread_Control                         *owner;

  /**
   * This field contains the cpu usage value of the owning thread when
   * the period was initiated.  It is used to compute the period's
   * statistics.
   */
  Timestamp_Control                       cpu_usage_period_initiated;

  /**
   * This field contains the wall time value when the period
   * was initiated.  It is used to compute the period's statistics.
   */
  Timestamp_Control                       time_period_initiated;

  /**
   * This field contains the statistics maintained for the period.
   */
  Rate_monotonic_Statistics               Statistics;

  /**
   * This field contains the number of postponed jobs.
   * When the watchdog timeout, this variable will be increased immediately.
   */
  uint32_t                                postponed_jobs;

  /**
   *  This field contains the tick of the latest deadline decided by the period
   *  watchdog.
  */
  uint64_t                                latest_deadline;
}   Rate_monotonic_Control;

Watchdog_Control 是和这个结构体关联的定时器

rtems_rate_monotonic_period_states     RMS的状态

关键实现函数

对于RMS，RTEMS提供了以下API：

rtems_rate_monotonic_create 创建一个RMS

rtems_rate_monotonic_cancel 取消一个RMS

rtems_rate_monotonic_delete 删除一个RMS

rtems_rate_monotonic_get_status 获得RMS状态

rtems_rate_monotonic_period 核心函数，用于启动一个周期，在这里发生RMS状态转换

RTEMS中RMS实现算法如下：

程序调用rtems_rate_monotonic_period ，此时系统认为线程开始一项周期任务，且周期长度为length，记这一时刻time_at_period。当线程的执行流到达下一个rtems_rate_monotonic_period语句时（在一般程序中，是回到之前调用的那句rtems_rate_monotonic_period ），系统会判断从time_at_period开始到现在是否经过了length个tick，如果超过了，重新开始一个周期。通常是不会超过的，此时这个线程会被阻塞，等待下一周期的开始，知道系统时刻确实到达time_at_period+length。线程会被唤醒。

应用举例：

RTMES/testsuites/sptests/sp32中包含了对RMS的测试用例。其功能是让任务运行五个确定的周期，在每个周期的开始和结束记录时间，然后相减，看是否与指定的周期长度相等。