Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times #

这是vestal（2007）这篇论文里面所引用的论文，但是我认为，下面那篇论文更合适一些

On priority assignment in fixed priority scheduling #

这是Audsley关于priority assignment的另一篇论文。我认为这篇论文才是更贴切的。

introduction #

在固定优先级里面，有两个关键性的东西

• priority assignment
• feasibility analysis 后者决定了是否能满足所有的ddl

对于同步的周期性任务，他们在最开始同时释放，并且在每隔一个最小公倍数的时间内就重启

之前的工作已经证明了，在同步的周期性任务中，deadline-monotonic是最优的

但是可行性分析本身是个NP-完全的问题。对于deadline-monotonic，他的复杂度为O(E + n log2 n)

其中E表示复杂度分析本身的复杂度，后者表示给n个任务进行order（也就是排序）需要的成本

对于非同步的周期性任务，这种情况是因为他们不会同时release，也就是说，两个周期相同的任务，但是偏移不同，这个情况下无论如何也不会同时release

已有的证明证明了这种情况下，deadline-monotonic并不再是最优的，唯一的办法是枚举所有的n！暴力搜一遍。

但是本文想了个办法，表明它可以在多项式时间内解决这个问题，同时确定能够满足情况的最低优先级数量

基本背景 #

首先关于RTA（response time analyze），这个可以看看我在vestal那篇论文里面提到的公式的理解。

然后在系统中，有一个任务集合∆，分别是τ1，τ2，…，τn，总共有n个任务。 然后有个 \[ P ∈ Λ^∆ \] 这个我必须解释一下，P是上述的这些n个任务的某种优先级的排列，那么对于所有的排列P，组成一个排列的空间Λ^∆。而对于P来说，它由一堆元组(τi , k)组成，也就是表明这些n个任务，每个任务对应的优先级是多少。

另外的，还有一些函数，用于辅助说明

• pri(P,τi)，在优先级排列为P的情况下τi的优先级
• task(P,i)，在优先级排列为P的情况下，优先级为i的任务集合
• tasks(P,i,j)，在优先级排列为P的情况下，优先级介于i和j之间的任务集合
• hp(P,τi)，在优先级排列为P的情况下，比τi优先级更高的任务集合
• hpeq(P,τi)，在优先级排列为P的情况下，比τi优先级更高或者相同的任务集合

另外，还有个公式 \[ feasible(P , i ) → {true, false} \] 用于表示可调度性，但是这里的后面的i，是说，从i到n这些优先级，分配到这些优先级上的任务，都是可调度的。

最后，在RTA的情况下有四条定理：

• 对于一个任务τi，他的响应时间，取决于更高优先级的集合，但是跟这些任务的集合的优先级顺序没有关系（也就是更高优先级的随便怎么排列，都无所谓）
• 对于一个任务τi，他的响应时间，跟更低优先级的任务无关
• 一个任务的响应时间，不会随着优先级上升而增加（但是可以减少，优先级更高了，响应时间更低了，这很正常）
• 同样的，一个任务的响应时间，不会随着优先级的下降而减少（同理可得）

最后，这里的优先级中，1是最大的优先级，n是最小的优先级。

shift and transform #

原文的公式看上去更复杂，我解释一下

shift函数是这样的，在某个P下有一个τj，他需要挪动到优先级i，并且保证，τj初始的优先级在数字上比i更小

所以他给定了一个这种转换下的新的任务的优先级的集合（我看了半天，总算反应过来这是一个集合）

分别是（1到τj初始优先级之间的任务）（τj初始优先级到i之间的任务）（tj，他被挪动到了i优先级），（原先的i到n优先级之间的任务）

这就是shift的转换过程。

而transform函数是这样的，他输入两个优先级排列P和Q（应该这两个排列都是可行的），并返回一个新的优先级排列。

在这个新的优先级排列中，i到n之间的任务是Q原先的i到n，而在1到i之间的任务，虽然仍然是Q原先的1到i之间的任务，但他们的相对排列顺序，则按照在P排列下的相对顺序来排的。

他这里表示，这种转换可以通过一些shift函数和tranform函数的递归来实现的

优先级排列的方法和证明 #

这里提出的定理是这样的，如果存在一个优先级排列Q，让他在任务集合∆上，满足feasible(Q, i )，那么有且只有把对应的task，按照Q一样排列。

这个定理换句话说，其实就是证明transform(P , Q, k)在k在i到n的区间时候，仍然满足feasible的条件。（因为在k到n的范围内，transform(P , Q, k)和Q的task分布应该是一样的），而更高的优先级（优先级更小）则按照可调度的P的顺序排列的。

他用数学归纳法做的

递归基是这样的，最开始对k=n的情况，则R = transform(P ,Q, n)，从而，任务要么是优先级为n的，要么是高于n（即小于n的）

task(Q, n)，就是Q的优先级为n的任务，所以一定是feasible的

task(Q, n) = task(R, n) ∧(hp(Q,task(Q,n)) =hp(R,task(R,n) ) )

这个公式表达的是任务要么是优先级为n的，要么是高于n（即小于n的）这件事情。

递归假设

令：

R′ = transform(P , Q, i + 1)，显然归纳嘛，有feasible(R′, i + 1)（对于递归基，就是R= transform(P ,Q, n)的情况，上面已经说了，他是feasible的）

此时，让task(Q,i) = τk，即任务k在Q下的排序，他被放在优先级i上。

可以注意到的是，任务k，在R′下，他实际的优先级排列是按照P的，我们不知道他应该放在哪个优先级上，但有 i >= pri(R′,τk) >= 1

对于i情况下的优先级排序：R′′ =transform(P,Q,i)

我们需要证明他也是feasible的。

他的证明很简单

对于优先级1到i-1的task来说，因为P是可行的，去掉了τk之后，他们之间的排序并不发生变化，所以根据上面的定理，他们所有任务都是可行的（因为只取决于优先级更高的任务，顺序不变，更高优先级集合就没变）

对于τk被放到了优先级i上，由于R′′的优先级安排顺序，在i到n区间和Q相同，那么既然Q是feasible的，τk本身也是feasible的

从而R′′也是feasible的

因此，如果一个优先级集合是可行的，可以通过上述的方式进行转换，即生成R = transform(P ,Q, i)

所以衍生出来这篇论文所说的一个方法

太长不看一句话版本，给定一个固定优先级分配的系统，里面有n个任务，从最低优先级n开始，遍历整个任务集合，找到一个任务，如果他在优先级n上是feasible的，那么把它放在优先级n上，再把剩下的任务安排到1到n-1优先级上，如此递归，直到把所有n个任务都放在n个对应的优先级上，就这样。 #

复杂度为n^2（确切得按照论文说的那样，但是无关紧要）

压缩优先级 #

上面的情况，就是每个任务都占用一个优先级的情况，就是不允许两个任务占用同一个优先级。

后面的证明大同小异。之所以可以压缩优先级，是因为既然有两个以上任务占用同一个优先级，那么就可以用少于n个的优先级了，这是很自然的

所以priority assignment的算法就变成了，尽可能的把任务放在最低的优先级，剩下的任务放在次低的优先级。

但是他提到了性能问题，按我的理解，因为他提到了压缩，所以不是找到一个优先级可以放在那边就结束了，而是还需要继续向下压缩，也就是移动（不管算法怎么实现，最后实际的比较次数会更多）

评论 #

对于这个结论，我觉得很简单，但是他的推倒和理论，我认为是很棒的。（虽然只有结论是有用的）