第三章 处理机调度和死锁

高级调度又称为:作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列上。
低级调度称为:进程调度或短程调度，用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。
进程调度可分为非抢占方式和抢占方式（优先权原则/短作业优先原则/时间片原则）。
中级调度又称:中程调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量，实际上就是存储器管理中的对换功能。
三种调度队列模型：仅有进程调度的调度队列模型，具有高级和低级调度的调度队列模型，同时具有三级调度的调度队列模型。
调度算法是指：根据系统的资源分配策略所规定的资源分配算法。
先来先服务调度算法（FCFS），短作业（进程）优先调度算法（SJF），高优先权优先调度算法，基于时间片的轮转调度算法。（P76）
高优先权优先调度算法分为:非抢占式优先权算法和抢占式优先权调度算法。
优先权分为:静态优先权和动态优先权。
基于时间片的轮转调度算法可分为:时间片轮转法和多级反馈队列调度算法。
实现实时调度的条件：提供必要的信息，系统处理能力强，采用抢占式调度机制，具有快速切换机制。
抢占调度的时机可在时钟中断发生的时候或者立即抢占。
实时调度算法：最早截止时间优先算法（EDF），最低松弛度优先算法（LLF）。（P84）
多处理器系统可分为:紧密耦合MPS（通过高速总线或高速交叉开关）和松弛耦合MPS（通过通道或通信线路）。
多处理器系统可分为:对称MPS（所有处理器都一样）和非对称MPS（一主多从）。
多处理器的进（线）程调度方式有：自调度方式、成组调度方式和专用处理器分配方式。
产生死锁的原因有：竞争资源、进程间推进顺序非法。
死锁的发生必须具备四个必要条件：1互斥条件，2请求和保持条件，3不剥夺条件，4环路等待条件。
处理死锁的基本方法有：预防死锁，避免死锁，检测死锁，解除死锁。
预防死锁的方法是使以上四个必要条件中的2，3，4不成立，如静态分配，有序分配。
安全序列是指:系统能按某种进程顺序来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。
避免死锁：例子：银行家算法避免死锁。（P95）
检测死锁：死锁定理：当且仅当S状态的资源分配图使不可完全简化的。（P99）
解除死锁：死锁解除可以通过剥夺资源和撤消进程（最小代价进程撤消法）。