操作系统复习-处理机调度与死锁
|
272
|
0
|
操作系统

1967 字
|
8 分钟

处理机调度与死锁

处理机调度概述

多道程序系统之中，调度的实质是一种资源的分配。分时系统中无作业调度，分道批系统中才有。

处理机调度的层次

  1. 高级调度（长程调度/作业调度）：调度的对象是作业，根据某种算法将外存上处于后备队列中的哪几个作业调入内存。
  2. 低级调度（短程调度/进程调度）：决定就绪队列中的哪个进程应该获得处理机
  3. 中级调度（内存调度）：把暂时不能运行的进程调出内存到外存，变成就绪外存（挂起）状态。具备运行条件并且内存有空闲的时候，就重新调入内存并且改为就绪态。

作业和作业调度

作业是多道批处理系统中用户提交给系统的一项相对独立的工作，比程序更加的广泛。

作业控制块

在多道批处理系统之中，每个作业都有一个作业控制块（JCB）。当一个作业进入系统的时候，“作业注册”程序就会为该作业创建一个JCB，根据作业类型放入相应的作业后备队列。

作业调度的主要任务

根据JCB中的信息，检查系统中的资源能否满足作业的需求，按照一定的调度算法从外存中的作业后备队列中选取某些作业调入内存，并为他们创建进程和分配必要的资源。作业调度要做两个决定：

  1. 接纳多少个作业
  2. 接纳哪些作业

进程调度

进程调度任务

  1. 保护CPU现场信息
  2. 按某种算法选取进程
  3. 把CPU分配给进程

进程调度机制

进程调度有三个部分：

  1. 排队器：按一定的策略把进程排成一个或多个队列。
  2. 分派器：从就绪队列选出特定的进程
  3. 上下文切换器：处理机切换会有两种上下文进行切换的操作：（1）第一对，OS保存当前进程的上下文；（2）第二对，移出分派程序的上下文，把新的进程的CPU现场信息装入CPU的各个寄存器。

进程调度的方式

  1. 非抢占式调度方式
  2. 抢占式调度方式

处理机调度算法的目标

处理机调度算法的共同目标

  1. 资源利用率：CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）
  2. 公平性：各个进程公平的获取CPU的时间
  3. 平衡性
  4. 策略强制执行：对于指定的策略，即使是延迟也一定要执行

批处理系统中处理机调度算法的目标

  1. 平均周转时间短：带权周转时间为：周转时间/系统为之提供服务的时间
  2. 系统吞吐量高
  3. 处理机利用率高

分时系统中的处理机调度算法的目标

  1. 保证响应时间快
  2. 保证均衡性

实时系统中处理机调度算法的目标

  1. 保证满足截止时间的要求
  2. 保证可预测性

调度算法

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

FCFS可以用作作业和进程调度。

系统按照作业到达的先后次序来进行调度

短作业优先调度算法（SJF）

SJF可以用于作业和进程调度。

SJF可以分为抢占式和非抢占式两种，周转时间最短，一般是最优的调度算法。

SJF有如下的缺点：

  1. 必须预先知道作业的运行时间
  2. 对长作业非常的不利，会出现饥饿现象
  3. 采用FCFS时无法实现人机交互
  4. SJF调度算法完全没有考虑作业的紧迫程度

优先级调度算法（PSA）

越紧迫的进程或者作业优先级越高。每个进程都有优先数，默认越小优先级越高，但是不一定。

类型

  1. 非抢占式
  2. 抢占式

 优先级的类型

  1. 静态优先级：在创建进程的时候确定
  2. 动态优先级：随着进程推进/等待时间而改变，为了防止饥饿现象。

高相应比优先调度算法（HRRN）

综合考虑了作业的运行时间和等待时间。为每一个作业引入一个动态地优先级。其中：

优先级 =（等待时间+要求服务时间）/要求服务时间

相应比R_p =（等待时间+要求服务时间）/要求服务时间 = 响应时间 / 要求服务时间

轮转调度算法（只适用于分时系统）

就绪队列上每个进程每次只运行一个时间片。就绪队列按照FCFS来排列。

其中时间片太大会退化为FCFS，太小会增加上下文切换的时间。

死锁概述

资源问题

会引起死锁的有以下三种资源：

  1. 可重用资源：只能分配给一个进程使用
  2. 可消耗资源：临时性资源，进程在运行的时候动态创建和消耗的
  3. 不可抢占资源

计算机系统之中的死锁

  1. 竞争不可抢占资源
  2. 竞争可消耗资源
  3. 进程推进顺序不当

死锁的定义、必要条件与处理方法

死锁的定义

如果一组进程中每个进程都在等待仅由该进程中的其他进程才能引发的事件发生，那么该组进程是死锁的。

产生死锁的必要条件

  1. 互斥条件
  2. 请求和保持条件：进程已经占有了一个资源，但是又提出新的请求，而目标资源被其他进程占用。
  3. 不可抢占条件：进程已经获得的资源在未使用完之前不能被抢占，只能完成后自行释放。
  4. 循环等待比如：{1, 2, 3, 4}中，1等2、2等3、3等4、4等1。

死锁的处理方法

有三种策略：

  1. 预防或者避免死锁
  2. 允许系统死锁，但是会检测死锁并且恢复
  3. 完全忽略这个问题

上述策略有4中实现方法：

  1. 预防死锁
  2. 避免死锁
  3. 检测死锁
  4. 解除死锁

资源分配图

死锁预防

破坏“请求和保持”条件

  1. 第一种协议：一次全部申请所有资源
  2. 第二种协议：边申请资源，运行时边释放资源

破坏“不可抢占”条件

一般不这么做，会使得工作前功尽弃

破坏“循环等待”条件

死锁避免

系统安全状态

安全状态是系统不会进入死锁的状态

银行家算法

数据结构

  1. 可利用资源向量：Available
  2. 最大需求矩阵：Max
  3. 分配资源矩阵Allocation
  4. 需求矩阵：Need

例题

题目如下

解答如下

 

 

上一篇
下一篇