操作系统论文导读（三）：Stack-based scheduling of realtime processes基于堆栈的实时进程调度

目录

一、论文核心思想：

二、基本的相关条件

作业运行的条件：

 作业抢占其他作业的条件： 

三、基本的相关定义

四、基本的相关调度

 五、基本的相关调度

 六、堆栈资源共享

 七、与PCP的比较

---

一、论文核心思想：

-引入了一个抢占优先级的概念，增加了任务抢占的苛刻程度，以及挑选任务执行的苛刻程度，以此来避免死锁、优先级翻转问题、频繁的上下文切换。

-最重要的，该种思想能够完美的契合堆栈共享，解决了堆栈占用空间的问题，大大减少了空间的浪费。

-另外，在单核上，SRP与PCP均为最优的两种调度方式。

二、基本的相关条件

作业运行的条件：

1.资源能够完全满足当前该作业的运行。（该作业运行所需要的资源均申请就可以得到）---> 防死锁

2.该作业不会妨碍优先级和抢占级别比他更高的作业的运行。（即优先级和抢占级别比他更高的作业一请求，该作业可以立刻交出资源使用权，最多阻塞一个临界区运行的时间）--->防优先级倒置

 作业抢占其他作业的条件： 

        1.抢占任务的优先级高于当前任务运行的优先级
        2.抢占任务的抢占优先级高于当前系统运行的抢占优先级天花板

三、基本的相关定义

其中ρ为优先级，r为任务到达时间，π为抢占优先级
对定义 1 稍作修改, 将任务优先级替换成任务相对截止时限, 可得在三者在使用EDF调度的系统中的函数关系。

重要定义：SRP 协议中调度决断的判定依赖于任务属性πi . 当系统为所有任务设置π 后, 可以得出系统中资源优先级天花板π（R）. 设π（R）为当前系统中所有请求资源 R 的作业中, 抢占优先级最高的作业的抢占优先级数值，r为请求资源 R 的任务子集。

在任意时刻 t, 系统优先级天花板 π（t） 设置为 t 时刻所有资源优先级天花板最大值, 如式 2 所示. 如果当前系统中所有资源都处于空闲状态, 那么 π（t）设置为 Ω , 表示π（t）于当前所有任务的π 值.

四、基本的相关调度

1)优先级天花板更新规则: 当系统中所有资源可用时, 系统优先级天花板π（t ）设置为 Ω ，其变更的时机为资源分配与释放的时刻;

2)任务调度规则: 当作业j2被调度器选中执行时, 首先进行资源分配测试, 即判断任务抢占优先级是否大于系统优先级天花板且大于当前运行中作业 j1 的抢占优先级。若是则作业j2执行, 若否则阻塞选择就绪队列中其他作业继续测试, 知道找到合适作业. 作业执行时根据其时限或者优先级以优先级驱动的方式调度执行.

3)资源分配规则: 在任意时刻, 如果有作业请求资源, 则直接分配资源给此作业. 在使用 SRP 协议时, 新作业可能因未通过资源分配测试被提前阻塞, 导致作业产生资源等待延迟时间, 延迟时间的上界由下式给出。
SRP协议中任务阻塞时机是任务间试图抢占的时刻, 而不是任务请求资源的时刻， 未通过资源分配测试的作业被提前阻塞，继续在就绪队列中等待执行。 而当前运行中的作业均已通过测试， 测试保证了系统在此作业运行时可以满足其所有的资源需求, 不会因为资源请求而阻塞.

 五、基本的相关调度

表中给出了在动态优先级系统中的任务集在一个超周期内作业的调度实例. 作业集合中 j1 到 j8 的相对截止时间 Di 依次增大, 抢占优先级 πi 依次减少.。设系统初始优先级天花板 π(0) =0 , 资源 R1 R2 R3 的优先级天花板为 π(R1)=6 ，π(R2)=4，π(R3)=5。执行的顺序如下图。

 

 六、堆栈资源共享

由于任务运行和被强占的苛刻性，协议与堆栈资源共享完美适配，不会出现栈中顺序乱掉的问题

 上图为正常情况下堆栈分配

 上图为SRP的堆栈分配

 七、与PCP的比较

1)PCP中抢占级别和优先级是一回事，在SRP中是两回事，优先级是动态，抢占级别是静态。2)PCP将每个进程看做同一类型的作业请求，SRP是不同作业的不同请求，有不同的抢占优先级。3)PCP用的互斥锁，SRP用的资源上限函数。
4)PCP不允许栈资源共享，SRP可以。
5)SRP阻塞在其他作业尝试抢占的时候，并且只会被他尝试抢占的作业阻塞（最多一个临界区的执行时间），PCP则是一个作业请求资源时被阻塞，此后就不会再被阻塞，对系统的影响较大。