高级分布式系统-第9讲 实时调度--静态调度与动态调度

静态调度

在静态调度中，任务组的调度表是通过离线计算得出的。在调度表的生成过程中，必须把所有任务的资源、优先级和同步要求考虑进去，并且确保所有的截止时间要求。这个调度表指明了各个任务的运行起始时间 ，一旦生成就不再变化。在系统运行期间 ，任务调度器只需要根据这张表在指定的时刻启动相应的任务 。

静态调度表是一个周期性的、时间触发的进度表。时间轴被分成一系列基本粒度，每个基本粒度被认为是一个基本循环时间（basic cycle time） 。

采用静态调度的系统只有一种中断 ：周期性时钟中断。每个时钟中断都是一个基本粒度的起点。在分布式系统中 ，这种时钟中断必须是全局同步的，同步精度要明显高于基本粒度的持续时间。

在不同节点中运行的任务 ，它们之间的相互制约关系可用优先顺序图，利用优先顺序图很容易得到搜索树 。

动态调度

在动态调度中，大部分或全部调度决策是在系统运行时由任务调度器执行某种调度算法来决定的。也就是说，由动态调度算法在线确定“就绪”任务组中下一个必须服务的任务 。

独立任务的调度：

在利用单一CPU的系统里 ，对一组周期性的、相互独立的强实时任务进行调度的最佳算法是单调速率（Rate Monotonic, RM ） 算法、最早截止时间优先（Earliest Deadline First，EDF ） 算法和最小疏密度（ Least

Laxity , LL ） 算法。

信号量：

用来协调不同进程间的数据对象，最主要的应用是共享内存方式的进程间通信。本质上，信号量是一个计数器（非负整数），用于记录对某个资源（如共享内存）的存取状况。一般说来，为了获得共享资源，进程需要执行下列操作：

（1）测试控制该资源的信号量。

（2）若此信号量的值为正，则允许进行使用该资源。进程将信号量减1。

（3）若此信号量为0，则该资源目前不可用，进程进入睡眠状态，直至信号量值大于0，进程被唤醒，转入步骤（1）。

（4）当进程不再使用一个信号量控制的资源时，信号量值加1。如果此时有进程正在睡眠等待此信号量，则唤醒此进程。

互斥量：

控制某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。通常是0/1两个状态。

一个互斥量只能用于一个资源的互斥访问，它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。当信号量为单值信号量时，也可以完成一个资源的互斥访问。

非独立任务的调度：设任务组是由周期性任务形成的，每个任务都拥有共享资源的独占访问权，共享资源（如共享数据结构）是通过信号量（semaphore）进行保护的 ，可以用来实现任务间（inter-task）通信。当使用信号量来协调任务对共享资源的访问时 ，可能遇到两个同步问题 ：死锁和优先级倒置 。

死锁问题

（1）优先级较高的任务T2正在运行 ，而任务T1处于就绪状态 。为了访问由信号量S1保护的共享资源（独占访问），T2锁定了S1。

（2）任务T2为了等待事件E的发生，自行转入等待状态。

（3）任务T1得以运行，并在运行中锁定了信号量S2（保护另外一些共享资源）。

（4）事件E发生了，由于T2的优先级高于T1, T2抢占T1，再次开始运行。

（5）假如T2 想要锁定信号量S2必然失败 ，因为S2已经被T1锁定。

（6）T2又进入了等待状态（直到S2 变成可锁定的），任务T1恢复运行。

（7）任务T1试图锁定信号量S1，但失败了 ，因为S1己经被T2锁定。

（8）T1 也进入等待状态（直到S1变成可锁定的）

优先级倒置问题

（1）在T2、T3和T4挂起期间，T1正在运行，并且锁定了信号量S（保护共享资源）。

（2）T2、T3和T4被激活，进入就绪状态，准备运行。

（3）由于T4的优先级最高 ，所以T4抢占T1获得运行权，其他任务进入就绪状态。

（4）T4在运行期间尝试锁定信号量S，由于S已经被T1锁定，T4的锁定操作失败 ，只能进入等待状态 。

（5）下一个高优先级任务T3开始运行，直至结束。然后T2运行至结束。之后T1又获得运行权 。

（6）T1在运行过程中释放了S，T4脱离等待状态 ，锁定信号量S并恢复运行。