处理机调度与死锁

调度算法和银行家算法

处理机调度的层次和调度算法的目标

处理机调度的层次

1. 高级调度(又称：作业，长程，接纳调度)

   高级调度又称长程调度。调度对象是作业

2. 低级调度

   低级调度又称为进程调度或短程调度

3. 中级调度

   中级调度又称为内存调度，主要目的是：提高内存利用率和系统吞吐量。为此，应把那些暂时不能运行的进程，调值外存等待，此时进程的状态称为就绪驻外存状态(或挂起状态)

进程调度

1. 执行完，1个时间片以后的进程
2. 新创建的进程
3. 阻塞被唤醒进程

分类：非抢占和抢占

处理机调度算法的目标

$T_i=完成时间-到达时间$

$T= \frac{1}{n} \underset{i=1}{\stackrel{n} \sum }T_i$

$W_i= \frac{T_i}{T_s}$

$W= \frac{1}{n} \underset{i=1}{\stackrel{n} \sum }W_i$

注：T为平均周转时间，$T_i$为周转时间，$T_s$为执行时间，W为平均带权周转时间，$W_i$为带权周转时间

作业与作业调度

先来先服务(FCFS)

优点：简单，有利于长进程(作业)调度

缺点：不利于短进程(作业)调度

SJ(P)F短作业优先调度算法

策略

1. 根据进程(作业)执行时间越短越先调度执行
2. 到达时间

分类

1. 非抢占式
2. 抢占式

优点：有利于短进程(作业)的调度

缺点：不利于长进程(作业)的调度

优先权调度

策略 ：根据进程优先数的大小来调度执行

分类

1. 中断：非抢占式和抢占式

2. 变化

   1. 静态：不变 V

   2. 动态：响应比，$R_p = \frac{t_w+t_s}{t_s}$

      $t_w$为等待时间

时间片轮转(RR)

基本时间片(抢占式)

时间片(系统)：时钟信号，10~100ms

1. 太大：退化成先来先服务(FCFS)调度
2. 太小：系统开销过大

时间片大小

1. 为1
2. >1

同一时刻：2-1-3

1. 先写就绪队列，R=1(写到最后一个进程加入)

   

2. 再画图

   

例题：

考虑5个进程P1,P2,P3,P4,P5,见表1.规定进程的优先度越小,优先级越高.试描述在采用下述几种调度算法时各个进程的运行过程.并计算采用每种算法时的进程平均周转时间.假设忽略进程的调度时间.

1. 先来先服务调度算法
2. 时间片轮转调度算法(时间片为1ms)
3. 时间片轮转调度算法(时间片为2ms)
4. 非剥夺式SJF调度算法
5. 剥夺式优先级调度算法

解：

1. 
2. 
3. 
4. 
5. 

最早截至时间优先(EDF)

策略：

1. 根据截止时间的早晚确定调度顺序
2. 越早就越先执行
3. 到达时间

已知：

1. 到达顺序：$p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_4$
2. 截止时间：$p_1 \rightarrow p_3 \rightarrow p_4 \rightarrow p_2$

则调度顺序：$p_1 \rightarrow p_3 \rightarrow p_4 \rightarrow p_2$

注：抢占与非抢占的执行顺序一样

最低松弛度优先(LLF)

若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90

主要用于可抢占的调度方式中

死锁

1. 定义

   因为某些原因使进程不能执行，系统进入一种僵局定义为死锁

2. 产生的原因

   1. 竞争资源

      1. 可剥夺性：共享(不会发生)
      2. 非剥夺性：互斥(可能会)
      3. 临时性：(可能会)

   2. 进程推进的顺序不当

      例：两个进程：$p_1/p_2$；资源两个$R_1/R_2$

      两个操作：Req()[申请资源]，Rel()[释放资源]

      

      则：1，2，3不会发生死锁；4会产生死锁

避免死锁

方法：

1. 判断系统的状态
   1. 安全(不会发生死锁)
   2. 不安全(有可能会发生死锁)
2. 再资源分配(银行家算法)

补充(银行家算法)

引入4个资源分配相关的变量

1. Max:最大资源数
2. Allocation:已分配的资源数
3. Needi:还需要的资源数
4. Available:当前系统的可用资源数

**关系：**Max=Allocation+Needi

Needi与Available比较：

1. $\leq$ 可执行

2. $>$:阻塞等待

3. 安全状态

   找出进程推进顺序$\Rightarrow$安全序列(不是唯一的)$\Rightarrow$系统安全$\Rightarrow$不会发生死锁

   例：

   

   Available=12-(5+2+2)=3

   Needi:

   p1=10-5=5

   p2=4-2=2

   p3=9-2=7

   则安全序列：$p2 \rightarrow p1 \rightarrow p3$

   以p2为例：

   3(执行之前的Available)+2(Allocation)=5(执行之后的)

4. 不安全状态

   一个安全序列都没有(可能进入死锁)

申请资源：

发出请求向量Request:$\Rightarrow$银行家算法

增加了3个变量：

1. 请求向量Request(已知)
2. 可用资源数:work<->Available
3. 布尔变量:Finish

算法步骤

1. 两次比较
2. 预分配(修改3个变量)
3. 安全性检测
   1. 安全：可以分配
   2. 不安全：不分配，恢复变量