处理机调度的层次

低级调度（内存——>处理器）

  • 又称为进程或短程调度，调度对象是进程（内核级线程），进程调度是最基本的一种调度。
    主要功能：
    （1）保存处理机的现场信息
    （2）按某种算法选取进程
    （3）把处理器分配给进程
  • 进程调度方式
    （1）非抢占式
    系统开销小，适用于大多数的批处理 OS 环境
    难以满足紧急任务的要求-立即执行
    （2）抢占式
    防止一个长进程长时间占用处理机，为大多数进程提供更公平的服务（优点）
    系统开销大（缺点）

中级调度（内存——>外存）

主要目的：为了提高内存利用率和系统吞吐量
@ 高级调度（外存 内存 ）
@ 低级调度（内存 处理器）
@ 中级调度（内存 外存 ）

高级调度（外存——>内存）

调度算法

作业周转与平均周转时间

  • 如果作业 i 提交给系统的时刻是 ts，完成时刻是 tf，该作业的周转时间 ti 为：
    ti = tf - ts
  • 平均作业周转时间 T = (Σti) / n

先来先服务调度算法

  • 有利于CPU繁忙型的作业，不利于I/O繁忙性的作业
  • 不利于短作业，而优于长作业

最短作业调度算法

该算法对长作业不利
该算法完全未考虑作业的紧迫程度

高响应比调度算法

响应比 =作业周转时间/作业处理时间
=(作业等待时间+作业处理时间)/作业处理时间
=1+作业等待时间/作业处理时间

高优先权调度算法

  • 优先权调度算法(FPF)的类型
    非抢占式优先权算法
    抢占式优先权算法
  • 优先权的类型
    静态优先权
    动态优先权

时间片轮转调度算法

多级反馈调度算法

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

  • 产生死锁的原因可归结为以下两点：
    1、竞争资源引起进程死锁：当系统中供多个进程所共享的资源，不足以同时满足他们的需要时，引起他们对资源的竞争而引起死锁。
    2、进程推进顺序不当引起死锁：进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。
  • 操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁。
  • 系统形成死锁的四个必要条件
    互斥条件：进程互斥使用资源
    部分分配条件：申请新资源时不释放已占有资源
    不剥夺条件：一个进程不能抢夺其他进程占有的资源
    环路条件：存在一组进程循环等待资源的,即进程集合{P0,P1,P2,…Pn}中的 P0 正在等待 P1 占用的资源， P1 正在等待 P2 占用的资源，…… Pn 正在等待 P0 占用的资源
  • 产生死锁必须同时满足上述四个条件，一个不满足死锁便不会发生

处理死锁的基本方法

  • 预防死锁
  • 避免死锁
  • 检测死锁
    通过系统设置的检测机构，及时检测出死锁的发生，精 确地确定于死锁有关的进程和资源；然后采取适当措施，从系统中将已发生的死锁清除掉。
  • 解除死锁
    与检测死锁配套的措施。当检测到系统中已发生死锁时， 须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。

银行家算法

  1. 系统中的所有进程进入进程集合,
  2. 在安全状态下系统收到进程的资源请求后,先把资源试探性分配给它。
  3. 系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。
  4. 把这个进程从集合中去掉, 系统的剩余资源更多了,反复执行上述步骤。
  5. 最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可实施本次分配;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。