操作系统总结 处理机调度与死锁

原 作者 楚东方 | 发表于 | 分类于 2015级

操作系统 处理机调度与死锁

处理机调度

1、高级调度
  • 作业与作业步
  • 作业控制块
  • 作业调度
2、低级调度

低级调度也称为进程调度、短程调度，它所调度的对象为进程
低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。

功能
  • 保存处理机的现场信息
  • 按某种算法选取进程
  • 把处理机分配给进程
三个基本机制
  • 排队器
  • 分派器
  • 上下文切换机制
进程调度方式
  • 非抢占式
  • 抢占式
    1、优先权原则
    2、短专业优先原则
    3、时间片原则
中级调度

中级调度又称中程调度。引入中级调度的主要目的是为了提高内存的利用率和系统的吞吐量。
其把占时不运行的程序放到外存上，把外存上的程序放入内存，并使其为就绪态。

中级调度实际上就是存储管理器的对换功能。

调度队列模型和调度准则

调度队列模型
  • 仅有进程调度的调度队列模型
  • 具有高级和低级调度的调度队列模型
  • 同时具有三级调度的调度队列模型
选择调度方式和算法的准则

  • 面向用户准则
    1、周转时间
    2、相应时间快
    3、截止时间的保证
    4、优先权准则

  • 面向系统准则
    1、系统吞吐量高
    2、处理机利用率好
    3、各类志愿的平衡利用

3.3调度算法

（1）先来先服务调度算法FCFS

其可以用于进程调度，也可以用于作业调度。

  • 在作业调度中采用该算法，每次调度都是从后备队列中选择一个或多个最先进入改队列的作业，将他们调入内存，并为他们分配资源创建进程，然后放入就绪队列。

  • 在进程调度中采用FCFS算法，就是从就绪队列中选择一个最先进入该队列的进程 ，为之分配处理机，使之投入运行。

FCFS有利于长作业，而不利于短作业

（2）短作业优先调度算法 SJP

短作业优先调度算法 SJP 是指对短作业或短进程优先调度的算法。

  • 短作业优先调度算法是从后备队列中选择一个或若干个估计运行时间很短的作业，将他们调入内存运行。
  • 短进程优先调度算法则是从就绪队列中选出一个估计运行时间很短的作业，将处理机分配给他，使它立即执行。
    缺点
  • 对长作业不利
  • 未考虑作业的紧迫程度
（3）高优先权优先调度算法
1、优先调度算法的类型
  • 非抢占式优先权算法
  • 抢占式优先权算法
    在进程执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。
2、优先权的类型

  • 静态优先权
    静态优先权是在创建进程时确定的，而且在进程的整个运行时间期间保持不变。

  • 动态优先权
    动态优先权是指在创建进程时所赋予的优先权，是可以根据进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。

3、高相应比优先调度算法

R=(等待时间+要求服务时间)/要求服务时间

（4）基于时间片轮转法调度算法

  • 早期的时间片轮转算法
    系统将所有的就绪程序按FCFS的原则排列成一个队列，每次调度时，把CPU分配给队首进程，并执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾。

  • 多级反馈队列调度算法

    1. 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余各个队列的优先权逐个降低。该算法赋予各个队列进程执行的时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。
    2. 当一个新进程进入内存后首先将它放入第一队列的末尾，按FCFS原则排队进行调度，如果其能在该时间片内完成，便可撤离系统，如果尚未完成，调度程序便将该进程转入第二队列的末尾，同样地按FCFS原则等待调度执行
    3. 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。仅当第1 - i-1 队列均空时才会调度i队列中的进程运行。如果有高优先权的进程进入，新进程会抢占正在运行进程的处理机。

  • 多级调度算法的性能

    1. 终端型作业用户
    2. 短批处理作业用户
    3. 长批处理作业用户

实时调度

  • 实现实时调度的基本条件

    1. 提供必要的信息
    2. 系统处理能力强
    3. 采用抢占式调度机制
    4. 具有快速切换机制
  • 实时调度算法的分类
    1. 非抢占式调度算法
    2. 抢占式调度算法
  • 常用的几种调度算法
    1. 最早截止时间优先 EDF
    2. 最低松弛优先 LLF

产生死锁的原因和必要条件

1 产生死锁的原因

  • 竞争资源

    1. 可剥夺资源和不可剥夺资源
    2. 竞争非剥夺性资源
    3. 竞争临时性资源

  • 进程间推进顺序非法

2 产生死锁的必要条件
  • 互斥条件
    指进程对所分配到的资源进行排他性使用，资源不能被多个进程使用。
  • 请求和保持条件
    指进程已经至少保持了一个资源，但又提出新的资源请求，而该资源有被其他进程占用，此时请求进程阻塞。
  • 不剥夺条件
    进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  • 环路等待条件
    资源的环形链
3 处理死锁的基本方法
  • 预防死锁
  • 避免死锁
  • 检测死锁
  • 解除死锁

预防死锁的办法

  • 摒弃”请求和保持”条件
  • 摒弃”不剥夺”条件
  • 摒弃”环路等待”条件
1、利用银行家算法避免死锁
  • 银行家算法
  • 安全性算法
2、死锁的检测与解除

  • 死锁的检测
    资源分配图

  • 死锁定理

  • 死锁的解除
    1. 剥夺资源
    2. 撤消进程