OS--学习笔记：调度与死锁

三、调度与死锁

1.调度的概念

在多道程序系统中，进程的数量往往多于处理机的个数，进程争用处理机的情况就在所难免。 处理机调度是对处理机进行分配，就是从就绪队列中，按照一定的算法（公平、髙效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

2.调度队列模型

• 仅有进程调度的调度队列模型：

  

• 具有低级和高级调度的队列模型：

  

• 三级调度队列模型：

  

3.调度的基本准则与方式

调度的基本准则

• CPU 利用率
• 系统吞吐量
• 周转时间
  • 周转时间=作业完成时间-作业提交时间
  • 平均周转时间=$\frac{作业1周转时间+..+作业n周转时间}{n}$
  • 带权周转时间=$\frac{作业周转时间}{作业实际运行时间}$
  • 平均带权周转时间=$\frac{作业1带权周转时间+..+作业n带权周转时间}{n}$
• 等待时间
• 响应时间

方式

• 非剥夺调度方式（非抢占式）
• 剥夺调度方式（抢占式）

4.各种调度算法及其评价

先来先服务 (FCFS)

适用于作业或是进程调度

• 调度标准：按作业提交时间，从前到后依次分配处理机
• 评价
  • 简单，但效率低；
  • 对长作业有利，但对短作业不利（相对 SJF 和高响应比）；
  • 有利于 CPU 繁忙型作业，不利于 I/O 繁忙型作业

短作业优先 (SJF)

适用于作业与进程调度

• 调度标准：从后备队列中选择估计运行时间最短的作业
• 评价
  • 平均等待时间、平均周转时间最少
  • 必须预知作业的运行时间
  • 对长作业不利（可能会导致长作业 “饥饿”）
  • 未考虑作业的紧迫程度

优先级

• 调度标准：基于作业的紧迫程度，保证紧迫性作业优先

高响应比优先

适用于作业调度

• 调度标准：响应比高的优先运行。其中响应比定义如下
  • 响应比$R_p=\frac{等待时间要求服务时间}{要求服务时间}$
• 评价
  • 作业等待时间相同，要求服务时间越短，响应比越高，有利于短作业
  • 要求服务时间相同，作业的响应比由其等待时间确定，等待时间越长，其响应比越高。因而实现了先来先服务
  • 对于长作业，作业的响应比随等待时间的增加而提高，等待时间足够长时，响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态，兼顾了长作业。

时间片轮转

适用于进程调度

• 调度标准：先来先服务，但仅能运行一个时间片。
  • 若一个时间片未完成，剥夺该进程处理机，并将这个进程挂到就绪队列末尾，将处理机分配给当前就绪队列的第一个进程。

多级反馈队列

适用于进程调度

• 调度标准：

  时间片轮转和优先级调度

  • 多个队列，优先级不同，时间片也不同。
    • 总的来说，优先级越高的队列越先执行，但其时间片越短。
    • 一个时间片未完成，降优先级
    • 一个优先级队列都运行完后，才能运行下一个
    • 若有高优先级来，则抢占资源

• 评价：

  • 融合了前几种算法的优点

5.死锁

概念

• 多个进程相互竞争资源，形成一种相互等待的僵局

原因

• 竞争不可抢占性资源
• 竞争可消耗资源
• 进程推进顺序不当

产生死锁的必要条件

• 互斥
  • 资源使用只能一个一个来
• 请求和保持
  • 占着已有的，想占还没有的
• 不可抢占
  • 一个进程占有的，不能被其他进程抢占，而只能由自己释放
• 循环等待
  • 进程 i 需要的资源被进程 i + 1 占用，而进程 n 需要的资源被进程 0 占用。

死锁处理策略

• 不允许死锁发生：预防（破环死锁必要条件）–静态策略

  • 互斥：无法破坏
  • 请求和保持：一次分配所有需要的资源
  • 不可抢占：得不到新的，便先放弃旧的
  • 循环等待：按序分配

• 不允许死锁发生：避免 --动态策略

  • 银行家算法

    

    

    

允许死锁发生：检测

• 利用对资源分配图进行化简

  

  

允许死锁发生：解除

• 资源剥夺
• 撤销进程
• 进程回退