一、处理机调度概述
处理机调度的层次：
高级调度：又称长程调度或作业调度，调度对象是作业。
中级调度：又称内存调度。目的是提高内存利用率和系统吞吐量。
低级调度：又称短程调度或进程调度，调度对象是进程。
1、进程调度
进程调度的任务：
保存CPU现场信息
按某种算法选取进程
把CPU分配个进程
进程调度机制中，应具有以下三个基本部分：排队器，分派器，上下文切换器。
进程调度方式分为抢占式和非抢占式。
非抢占式调度方式：
优点：实现简单、系统开销小，适用于大多数批处理系统（但不能用于分时系统和大多数实时系统）。
可能引起进程调度的因素：
进程运行完毕，或无法继续运行
进程提出I/O请求而暂停执行
进程执行了原语操作（例如Block原语）
抢占式调度方式，允许调度程序根据某种原则去暂停某个正在执行的程序，并将已分配给该进程的处理机重新分配给令一进程。
抢占需要遵循的原则：
优先级原则
段建成优先原则
时间片原则
2、处理机调度算法的目标
名词解释及计算
CPU利用率计算公式：
周转时间：指作业被提交给系统开始，到作业完成为止的这段时间间隔。
平均周转时间T计算公式：
其中n表示又n个作业，Ti表示作业i的周转时间
作业i的带权周转时间T_{w_i}=\frac{T_i}{T_{S_i}}
平均带权周转时间Tw计算公式：
系统吞吐量：单位时间内系统所完成的作业数。
响应时间：从用户通过键盘提交一个请求开始，到屏幕上显示出处理结果为止的专断时间间隔。
截至时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间。
处理机调度算法的目标
共同目标：
资源利用率
公平性
平衡性
策略强制执行
批处理系统中：
平均周转时间短
系统吞吐量高。
处理机利用率高
分时系统中：
保证响应时间快
保证均衡性
实时系统中：
保证满足截止时间的要求
保证可预测性
三、调度算法
常见的调度算法：
先来先服务，FCFS
短作业优先，SJF
优先级调度算法，PR（如高响应比优先HRRN）
轮转调度算法，（如时间片轮转RR）
多级队列调度算法
多级反馈队列调度算法
基于公平原则的调度算法
1、先来先服务调度算法FCFS
通常将FCFS与其他调度算法结合使用。
只考虑了作业的等待时间。
2、短作业优先调度算法SJF
作业越短，优先级越高。作业的长短通过作业的运行时间来衡量。
只考虑了作业的运行时间。
缺点：
必须知道作业的运行时间
对长作业不利，容易造成饥饿现象
无法实现人机交互
没有考虑作业的紧迫程度，不能保证紧迫性作业能够得到及时处理。
3、优先级调度算法PR
优先级调度算法的类型：
非抢占式：一旦把处理机分配给某个进程，该进程就会一直执行下去，直至完成。
抢占式：高优先级的进程会抢占低优先级进程的处理机。
优先级的类型：
静态优先级：在创建时确定，并在整个运行期间都保持不变。
动态优先级：创建时先赋予一个优先级，执行过程中会改变。
高响应比优先调度算法HRRN
HRRN既考虑了作业的等待时间，又考虑了作业的运行时间。能够有效避免SJF中的饥饿现象。
HRRN中的优先级计算方法：
优先级又相当于相应比Rp。
4、时间片轮转调度算法RR
RR调度算法的基本原理：系统设置一定的时间间隔，每个进程执行完这段时间间隔后，就换下一个进程。
进程切换时机：
时间片未用完，进程就以执行完。则立即激活调度程序，将已经执行完的程序成功就绪队列中删除，并调度队首进程运行。
时间片用完，进程还未执行完。将进程送往就绪队列的末尾，并调度队首的进程执行。
时间片大小的确定：
若时间片很小，利于短作业。由于频繁切换进程，会增加系统开销。
若时间片很大，每个进程都能在时间片内执行完毕，则会退化为FCFS算法。
5、多级队列调度算法
采用多个就绪队列，不同就绪队列使用不同的调度算法，不同就绪队列可以设置不同优先级，一个就绪队列中的进程也可以设置不同的优先级。
6、多级反馈队列调度算法
短进程优先和基于进程当都的抢占式优先级调度算法都需要事先指明进程长度才能使用。
多级队列调度算法的调度机制：
设置多个就绪队列：设置多个就绪队列，队列的优先级依次降低。优先级越高的队列中，其时间片越小。
每个队列都采用FCFS算法。如果某个进程在时间片完后，执行完成，则撤离队列；否则，将其插入下一个队列的末尾。
按队列优先级调度。先调度高优先级的队列，高优先级队列空闲时，才调度低优先级队列。当有新进程进入高优先级队列中时，转去调度高优先级队列中的进程。
四、实时调度
实时调度算法的分类：
非抢占式：非抢占式轮转，非抢占式优先级
抢占式：基于时钟中断的抢占式优先级调度算法；立即抢占的优先级调度算法。
最早截至时间优先EDF：根据任务的截止时间确定任务的优先级，任务的截至时间越早，其优先级越高。
只考虑作业的等待时间。：根据任务的紧急程度（或松弛度）来确定优先级。松弛度最低的任务排在前面。
松弛度计算公式：
例如，任务A需要在5点之前完成，其运行时间需要2个小时，现在是1点钟。那么任务A的松弛度为5-2-1=2。
优先级倒置
优先级倒置：高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。
下图中优先级P1>P2>P3，由于低优先级的P1占用了临界资源mutex，导致P1即使获得了CPU也无法执行，只能阻塞，等待P1执行完毕后将临界资源释放。
解决优先级倒置的方法：
在进程进入临界区后，其所占用的处理机就不再允许被抢占。
高优先级进程A访问临界资源时，发现低优先级进程B正在访问，就把自己的优先级继承给这个低优先级的进程，知道这个进程推出临界区。这样可以保证，B在执行的过程中不会被比A优先级低的进程打断，从而能够使B更快的退出临界区，而不被那些优先级介于A、B之间的进程插队。
五、死锁
死锁概述
系统中的资源类型：
可重用资源：可供用户重复使用多次的资源。
可消耗资源：又称临时性资源，在进程运行期间由进程动态创建和消耗的。
可抢占资源：某进程获得资源后，该资源可以被其他进程或系统抢占。
不可抢占资源：资源分配给某进程后，就不能将它强行回收，只能等到进程用完后自行释放。
计算机中死锁产生的原因（P93）：
竞争不可抢占资源引起死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起死锁
死锁的定义：如果一组进程中的每个进程都在等待仅由该组进程中的其他进程才能引发的事件发生，那么该组进程是死锁的。
死锁产生的必要条件：
互斥条件：一段时间内，某资源只能被一个进程占用。
请求和保持（部分持有）：进程已经占有了至少一个资源，但又提出了新的资源请求。
不可抢占条件：进程已获得的资源在未使用完之前不能被抢占。
循环等待条件：发生死锁时，必然存在一个“进程-资源”循环链。（如p0等待p1占用的资源，p1等待p2占用的资源，p2又等待p0占用的资源，形成循环）
死锁的处理方法：预防、避免、检测、解除。
Linux和Windows中，采用忽略死锁，并假设系统永不会出现死锁的策略。
资源分配图。
用圆圈代表进程。
用方框代表一类资源。
方框中的圆点来表示该类资源的一个实例。
请求边由进程指向方框中的圆点
分配边始于方框中的一个圆点
死锁预防（破坏必要条件）
死锁预防通过破坏死锁的必要条件来实现。
破坏请求和保持条件：
第一种协议：进程不许一次性申请整个运行过程中的所有资源，资源全部满足时才运行。
第二章协议：运行过程中逐步是否能已分配给自己的、且已经用毕的全部资源，然后再请求新的所需的资源。
破坏不可抢占条件：当一个已经保持了某些不可抢占资源的进程提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，以待以后需要时再重新申请。
破坏循环等待条件：对系统所有资源类型就绪线性排序，规定每个进程必须按序号递增的顺序请求资源。
死锁避免
防止系统进入不安全状态，以避免发生死锁。避免死锁的实质在于，使系统再进行资源分配时不进入不安全状态。
系统安全状态：系统能够按某种进程推进顺序，分配资源并执行，进而使每个进程都能顺利完成的一种系统状态。这个进程推进顺序称为安全序列。
如果找不到一个安全序列，则称系统处于不安全状态。
当系统处于安全状态时，可避免发生死锁，当系统处于不安全状态时，则可能会发生死锁。
使用银行家算法来避免死锁。银行家算法，直接做题。
死锁的检测与解除
通过能否完全简化资源分配图来判断是否发生死锁。
某状态为死锁的充分条件时：当且仅当该状态的资源分配图时不可完全简化的。
