3.1 处理机调度的层次和调度算法的目标
一、处理机调度的层次（3）
1.高级调度 （作业调度、长程调度）
①用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行 。主要用于多道批处理系统。
②考虑两个问题：选择多少个作业进入内存，为之创建进程？ 取决于多道程序的度； 选择哪些作业? 取决于高级调度算法 。
2.低级调度 （进程调度、短程调度）
①决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程的具体操作。运行频率最高。
②功能：保存处理机的现场信息；按某种算法选取进程； 把处理器分配给进程。
③非抢占/抢占方式
非抢占方式：一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程。
抢占方式：允许调度程序根据某种原则（优先权原则，短作业优先原则，时间片原则），去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。
3.中级调度（中程调度）
①当内存空间非常紧张时，选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存。
②提高内存利用率和系统吞吐量。实际上是存储器管理的对换功能。
③只有支持进程挂起的操作系统才具有中程调度功能。
二、处理机调度算法的目标及准则
1.面向用户的准则（4）
①周转时间短
周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔
平均周转时间：
平均带权周转时间：
（Ti：周转时间 Tsi：服务时间）
②响应时间快 ：从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间
③截止时间的保证：指某任务必须开始执行的最迟时间，或必须完成的最迟时间
④优先权准则 ：基于优先权让某些紧急的作业能得到及时处理
2.面向系统的准则（3）
①系统吞吐量高。吞吐量是指在单位时间内，系统所完成的作业数。
②处理机利用率好
③各类资源的平衡利用
3.2 作业和作业调度
一、批处理系统中的作业
1.作业：包含程序，数据，作业说明书。在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。
2.作业控制块JCB
3.作业运行的三个阶段和三种状态
①收容阶段—后备状态
②运行阶段 – 运行状态
③完成阶段 – 完成状态
二、作业调度的主要任务
根据JCB信息，检查系统中的资源能否满足作业对资源的需求，按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为他们创建进程、分配必要资源，安排在就绪队列。
三、FCFS算法：有利于长作业（进程），而不利于短作业（进程）
四、SJF算法：对长作业不利；完全未考虑作业的紧迫程度；估计不准运行时间
五、优先级调度算法 ：把具有最高优先级的作业调入内存之中。
六、高响应比优先调度算法
动态优先级：
3.3 进程调度
一、进程调度的任务：保存处理机现场，按照某种算法选取进程 ，把处理机分配给进程
二、进程调度的方式 （最高优先权优先(FPF)调度下细分）
1.非抢占方式
在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。
2.抢占方式
在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。
“抢占”的原则： ①优先权原则；②短进程优先原则；③时间片原则
三、基于时间片的轮转调度算法
常用于分时系统及事务处理系统
四、优先级调度算法（抢占式/非抢占式）
五、多队列调度算法 具有较好的性能，能较好地满足各种类型用户的需要
1.置多个就绪队列，并为各个队列赋予不同的优先级。 第一个最高，以后依次降低
2.当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。
3.如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行。如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……。
4.仅当第1~i-1队列空闲时，调度程序才调度第i队列中的进程运行。
5.如果正在处理第i队列，又有新进程进入较高优先级的队列，则立即把正在处理的进程放回第i队末尾，将处理及分配给高优先级的进程。
3.4 实时调度
一、实现实时调度的基本条件
1.提供必要的信息 ：就绪时间，开始和完成截止时间，处理时间，资源要求，优先级
2.系统处理能力强
3.采用抢占式调度机制 ：硬实时任务
4.具有快速切换机制
二、实时调度算法分类
1.非抢占式轮转调度算法:
调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行。
2.非抢占式优先调度算法:
如果在系统中存在着实时要求较为严格的任务，则可采用非抢占式优先调度算法，为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，才能被调度执行。
3.基于时钟中断的抢占式优先权调度算法:
某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先权任务。
4.立即抢占的优先权调度算法:
一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。
三、最早截止时间优先EDF(Earliest Deadline First) 算法
该队列按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面
1.用于非抢占调度的调度方式
2.抢占式调度方式用于周期实时任务
四、最低松弛度优先LLF(Least Laxity First)算法
松弛度=必须完成时间－本身的运行时间－当前时间
当有任务执行时，只有等待任务的松弛度值为0才会发生任务的调度，其他情况不发生调度。
任务执行结束后或无任务执行时，再比较等待任务的松弛度值，较小的先执行。