单等待队列
- 资源对应的事件发生时，内核需要扫描整个等待队列，搜索等待该资源的任务，并按照一定的策略选取任务，把任务的任务控制块放置到就绪队列。
- 如果系统的资源和任务比较多，搜索等待该资源的任务所需要的时间就比较长，会影响整个系统的实时性能。
多等待队列
- 资源对应的事件发生时，能够在较短的时间内确立等待该资源的任务等待队列。
基于位图的优先级调度算法【大题】
对于就绪任务，如果采用上述队列方式(单/多等待队列)进行管理，在基于优先级的调度处理中，要获得当前具有最高优先级的就绪任务：
- 方式一：任务就绪时，把就绪任务的任务控制块放在就绪队列的末尾。
调度程序需要从就绪队列的头部到尾部进行一次遍历，才能获得就绪队列中具有最高优先级的任务； - 方式二：就绪队列按照优先级从高到低的顺序排列。
新的就绪任务到达时，需要插入到就绪队列的合适位置，确保就绪队列保持优先级从高到低排列的顺序性。
在这两种处理方式中，所花费的时间与任务数量有密切的关系，具有不确定性。
为提高实时内核的确定性，可采用一种被称为优先级位图的就绪任务处理算法。
调度用来确定多任务环境下任务执行的顺序和在获得CPU资源后能够执行的时间长度。
数据结构
要使用该算法，首先需要维护四个数据结构：
- 优先级就绪组
OSRdyGrp，原型：char OSRdyGrp - 优先级就绪表
OSRdyTbl，原型：char OSRdyTbl[8] - 优先级映射表
OSMapTbl，原型：char OSMapTbl[8] - 优先级判定表
OSUnMapTbl，原型：char OSUnMapTbl[256]
其中，OSRdyGrp和OSRdyTbl的值是随任务调度动态发生变化的。OSMapTbl和OSUnMapTbl是固定的值，仅用来做转换操作
OSRdyGrp 和 OSRdyTbl
二者关系见图：
-
OSRdyGrp用来表示OSRdyTbl当中的行是否存在就绪任务 -
OSRdyTbl一共8行8列，共64位，可以表示64种不同的优先级(0-63)。其中63为最低优先级，表示空闲任务 - 同时上图还表现出以下事实：任务的优先级中仅有6位是有效的(
0-63中第6、7位为0当然无效)，同时高三位表示Y即行，低三位表示X即列。将OSRdyTbl中对应行列置1，表示该优先级的任务已就绪，反之，也可以通过Y*8(或Y<<3) + X，得到对应位置的优先级
OSMapTbl
OSMapTbl(这个结构的功能相当于3-8译码器)的值为：
OSUnMapTbl
OSUnMapTbl的值为：
这个表看着很复杂，但其实都是一些预置好的值。该表的作用是求取任意8位二进制数当中1出现的最低位次，比如数48 二进制表示为0b00110000(0x30H)，1出现在了第4位和第5位，最低位是4位，因此OSUnMapTbl[48] = 4，可以查表验证
算法
任务进行就绪状态
当任务进行就绪状态，需要根据任务优先级将OSRdyTbl中对应位置1，同时将OSRdyGrp 置1，表示对应行存在就绪任务
// priority >> 3 取出高三位得到列，再经过OSMapTbl转换得到掩码，将OSRdyGrp对应位置1
OSRdyGrp |= OSMapTbl[priority >> 3];
// priority & 0x07取出低三位，再经过OSMapTbl转换得到掩码，将OSRdyTbl[priority >> 3]对应位置1
OSRdyTbl[priority >> 3] |= OSMapTbl[priority & 0x07];
任务退出就绪态
当任务退出就绪状态时，需要根据优先级将OSRdyTbl中对应位清0，同时判断OSRdyTbl[priority >> 3]是否仍存在就绪任务，若不存在，则需要将OSRdyGrp 清0.
if((OSRdyTbl[priority >> 3] &= ~OSMapTbl[priority & 0x07]) == 0)
{
OSRdyGrp &= ~OSMapTbl[priority >> 3];
}
获取进入就绪态的最高优先级
做了那么多铺垫，最终想要达到的目的就是在获取就绪态任务的最高优先级时能够快一些。
// 经过OSUnMapTbl的转换，我们知道OSRdyGrp中最低位的1是哪一位，这也是OSRdyTbl中优先级最高的行
high3Bit = OSUnMapTbl[OSRdyGrp];
// 经过OSUnMapTbl的转换，我们知道OSRdyTbl[high3Bit]中最低位的1是哪一位，这也是OSRdyTbl[high3Bit]中优先级最高的列
low3Bit = OSUnMapTbl[OSRdyTbl[high3Bit]];
// 通过优先级最高的行列最终定位到优先级最高的任务
priority = (high3Bit << 3) + low3Bit;
任务切换：保存，恢复
- 切换：保存当前任务的上下文，并恢复需要执行的任务的上下文的过程。
任务切换时的工作：
- 当前正在运行的任务的
上下文保存到该任务的任务控制块中； - 把需要投入运行的任务的
上下文从对应的任务控制块中恢复到CPU寄存器中。
任务切换将导致任务状态发生变化：
- 当前正在运行的任务将由运行状态变为
就绪或是等待状态； - 需要投入运行的任务则由就绪状态变为
运行状态。
基本步骤：
- 保存任务上下文环境
- 更新当前运行任务的控制块内容，将其状态改为就绪或等待状态
- 将任务控制块移到相应队列（就绪队列或等待队列）
- 选择另一个任务进行执行(调度)
- 改变需投入运行任务的控制块内容，将其状态变为运行状态
- 恢复需投入运行任务的上下文环境
抢占式和非抢占式调度
- 抢占式调度和非抢占式调度：任务在运行过程中能否被打断的处理情况。
抢占式调度
- 正在运行的任务可能被其他任务所打断。
- 抢占式调度算法要更复杂些，且需要更多的资源，并可能在使用不当的情况下会造成低优先级任务出现长时间得不到执行的情况。
非抢占式调度
- 一旦任务开始运行，该任务只有在运行完成而主动放弃CPU资源，或是因为等待其他资源被阻塞的情况下才会停止运行。
- 非抢占式调度算法常用于那些任务需要按照预先确定的顺序进行执行，且只有当任务主动放弃CPU资源后，其他任务才能得到执行的情况。
内核的可抢占性
- 执行内核提供的系统调用的过程中，是否可以被中断打断。
不可抢占内核
- 分为两种情况：内核服务函数不能被中断、内核服务函数能被中断
内核服务函数不能被中断
- 系统在执行内核服务函数时处于关中断状态，不能响应外部可屏蔽中断，这样就会在一定程度上延迟中断响应时间。
能被中断但是不能进行任务重新调度
- 系统在执行内核服务函数时可以响应中断，不会延迟中断响应时间；但是在中断退出时不进行任务重新调度。
- 执行流程如下：
- 低优先级任务调用内核服务
- 内核服务过程中，系统发生中断，在允许中断的情况下，进入中断服务程序（ISR）
- 中断服务程序完成后，回到内核服务中
- 内核服务完成，进行任务调度，切换到新就绪的高优先级任务
- 高优先级任务运行完成或者因为其它原因阻塞，内核调度低优先级任务，低优先级任务恢复执行
可抢占内核
- 即使正在执行的是内核服务函数，也能响应中断，并且中断服务程序退出时能进行任务重新调度
- 如果有优先级更高的任务就绪，就立即让高优先级任务运行，不要求回到被中断的任务，将未完成的系统调用执行完。
- 执行流程如下
- 低优先级任务调用内核服务
- 内核服务过程中系统发生中断，在允许中断的情况下，进入中断服务
程序（ISR） - 中断服务程序完成后，内核调度新就绪的高优先级任务运行
- 高优先级任务运行完成或者因为其它原因阻塞，系统回到先前被低优
先级任务调用的、尚未完成的内核服务中 - 内核服务完成，返回到低优先级任务中，低优先级任务继续执行
静态调度和动态调度
静态调度
- 所有任务的优先级在设计时就定下来，且在运行过程中不会发生改变，如RMS调度。
- 适用于能够完全把握系统中所有任务及其时间约束特性情况，比较简单，但缺乏灵活性，不利于系统扩展。
动态调度
-
任务的优先级在运行过程中确定，且可能不断地发生变化，如EDF调度。
-
有足够的灵活性来处理变化的系统情况，但需要消耗更多的系统资源。
时间片轮转调度
- 当有两个或多个就绪任务具有
相同的优先级，且它们是就绪任务中优先级最高的任务时，任务调度程序按照这组任务就绪的先后次序调度第一个任务，让第一个任务运行一段时间，然后又调度第二个任务，让第二个任务又运行一段时间，依次类推，到该组最后一个任务也得以运行一段时间后，接下来又让第一个任务运行。 - 任务运行的这段时间称为时间片（time slicing）。
- 当任务运行完一个时间片后，该任务即使还没有停止运行，也必须释放处理器让下一个与它相同优先级的任务运行，使实时系统中
优先级相同的任务具有平等的运行权利。 - 释放处理器的任务被排到同优先级就绪任务链的链尾，等待再次运行。
优先级反转（Priority Inversion）
- 高优先级任务需要等待低优先级任务释放资源，而低优先级任务又正在等待中等优先级任务的现象。
和死锁的区别
- “死锁”是（无外界干涉的情况下）永远的阻塞
- 优先级翻转是高优先级的任务在特定的时间内得不到响应（打破实时性）
优先级继承
概念
- 当一个任务阻塞了一个或多个高优先级任务时，该任务将不使用其原来的优先级，而使用被该任务所阻塞的所有任务的最高优先级作为其执行临界区的优先级。
- 当该任务退出临界区时，又恢复到其最初的优先级。
举例
- 如果任务T1被T3阻塞，优先级继承协议要求任务T3以任务T1的优先级执行临界区。这样，任务T3在执行临界区的时候，原来比T3具有更高优先级的任务T2就不能抢占T3了。当T3退出临界区时，T3又恢复到其原来的低优先级，使任务T1又成为最高优先级的任务。这样任务T1会抢占任务T3而继续获得CPU资源，而不会出现T1长期被任务T2所阻塞的情形。
分析
- 优势：系统运行前就能够确定任务的最大阻塞时间。
- 不足：
- 协议本身不能避免死锁的发生；
- 任务的阻塞时间虽然是有界的，但由于可能出现阻塞链，使得任务的阻塞时间可能会很长。
死锁
- 假定在时刻t1，任务T2获得信号量S2，进入临界区。在时刻t3，任务T2又试图获得信号量S1，但一个高优先级任务T1在这个时候就绪，抢占任务T2并获得信号量S1，接下来任务T1又试图获得信号量S2。这样就出现了死锁现象。
阻塞链
- 任务T3在S1控制的临界区中被T2抢占，然后T2进入S2控制的临界区。这个时候，任务T1被激活而获得CPU资源，发现信号量S1和S2都分别被低优先级任务T2和T3加锁，使得T1将被阻塞两个临界区，需要先等待任务T3释放信号量S1，然后等待任务T2释放信号量S2，这样就形成了关于任务T1的阻塞链。
优先级天花板协议
概念
-
优先级天花板指控制访问临界资源信号量的优先级天花板。 -
信号量的优先级天花板为所有使用该信号量的任务的最高优先级。
协议内容
- 对于控制临界区的信号量，设置信号量的优先级天花板为可能申请该信号量的所有任务中具有最高优先级任务的优先级；
- 如果任务成功获得信号量，任务的优先级将被抬升为信号量的优先级天花板；任务执行完临界区，释放信号量后，其优先级恢复到其最初的优先级；
- 如果任务不能获得所申请的信号量，任务将被阻塞。
举例
- 假设T1，T2，T3的优先级分别为p1、p2、p3，并且T1和T3通过信号量S共享一个临界资源。根据优先级天花板协议，信号量S的优先级天花板为p1。
- 假定在时刻t1，T3获得信号量S，按照优先级天花板协议，T3的优先级将被抬升为信号量S的优先级天花板p1，直到T3退出临界区。这样，T3在执行临界区的过程中，T1和T2都不能抢占T3，确保T3能尽快完成临界区的执行，并释放信号量S。
- 当T3退出临界区后，T3的优先级又回落为p3。如果在T3执行临界区的过程中，任务T1或T2已经就绪，则此时T1或T2将抢占T3的执行。
优先级继承协议、天花板协议对比
-
优先级天花板协议中，一旦任务获得某临界资源，其优先级就被抬升到可能的最高程度，不管此后在它使用该资源的时间内是否真的有高优先级任务申请该资源——有可能影响某些中间优先级任务的完成时间。
-
优先级继承协议中，只有当高优先级任务申请已被低优先级任务占有的临界资源这一事实发生时，才抬升低优先级任务的优先级，因此它对任务执行流程的影响相对要较小。
-
优先级继承协议可能多次改变占有某临界资源的任务的优先级，而优先级天花板协议只需改变一次。
?