实时调度

假设有n个周期任务，周期分别为Ti，互相独立。有最坏执行时间（WCET）Ci。不考虑多线程阻塞。没有顺序约束，优先级固定Pi，切换时间可忽略，使用抢占式调度。

定理：如果存在一种优先级调度顺序可以产生可行的调度，那么按照周期排序的优先级（周期短的优先级高）也能产生可行的调度

RMS

任务周期越短优先级越高。如果任务级满足以下条件，那么可以被调度。 \(U=\sum_{i=1}^n\frac{C_i}{T_i}\le n(2^{1/n}-1)\) U为CPU利用因子

EDD

给定n个独立的单次任务有截止时间di，以最小化最大延迟的方式调度，即 \(L_{max}=\max_{1\le i\le n}\{f_i-d_i\}\) fi为完成任务i的时间。

EDD算法：按照截止时间非递减的顺序执行所有任务。

EDF

给定n个到达时间随机的任务，总是优先执行已到达任务中截止时间最早的任务

EDF在有执行顺序要求的情况下，不一定产生的是可行的调度。

LDF

截止时间最晚的任务最后执行

调度问题

排他锁

当多个线程共享资源时，需要锁来保证数据完整性。锁会使调度复杂化。

优先级反转

低优先级的任务已经获取了高优先级任务需要资源的锁，此时高优先级任务即使抢占了CPU，也因为低优先级任务的占用而无法进行，低优先级任务也因为被抢占而难以释放锁。

PIP算法

当一个任务占用了一个资源，其优先级暂时提升为需要此资源的任务的优先级最大者。具体而言，当高优先级任务被低优先级任务阻塞时，该低优先级任务的优先级会被提升。

死锁

两个任务相互等待资源