Ting's Blog

听的无名小站

0%

处理机的调度与死锁

发表于 更新于 分类于 ，
💡 TIP

image-20241220111714119

相关链接|

💡 TIP

平均周转时间 与 平均等待时间？

  • 周转时间 = 作用完成时间 - 作业到达时间

  • 带权周转时间 = 周转时间 / 服务时间

  • 平均周转时间 = 作业周转总时间 / 作业个数

  • 平均带权周转时间 = 带权周转总时间 / 作业个数

调度算法

  • 先来先服务算法（FCFS）（First Come, First Served.）

  • 短作业优先算法（SJF）（Shortest Job First）

  • 优先级调度（RR）

  • 高响应比优先调度算法（HRRN）(highest response ratio next)

算法性能评价

周转时间

  1. 周转时间 = 完成时间 - 到达时间

  2. 平均周转时间：周转时间/进程数

  3. 带权周转时间：周转时间/服务时间

  4. 平均带权周转时间：带权周转时间/进程数

响应时间

从用户通过键盘提交一个请求开始，到系统首次产生响应为止的时间，包括键盘输入时间、信息处理时间和信息回收时间

截止时间

某任务必须开始执行的时间（开始截止时间）和执行完成时间（完成截止时间）

💡 TIP

非抢占式调度

指进程一旦获得处理机，只有在该进程任务完成或因某事间而阻塞才让出处理机，绝不允许某进程抢占已经分配出去的处理机。

抢占式调度

抢占式调度 (PreemptiveMode) 允许调度程序根据某种原则，暂停某个占用处理机的进程，抢占已经分配出去的处理机。抢占的原则有优先权原则、短作业优先原则和时间片原则。

短作业优先算法 SJF

从等待队列中取下服务时间最短的进程进行执行

非抢占式调度

  1. 找出最先到达的进程（该进程的完成时间=到达时间+服务时间）；

  2. 根据上一进程的完成时间，找到在这个完成时间内所有到达的进程，并找到这些进程中服务时间最短的那个，然后计算它的完成时间（该进程的完成时间=上一进程的完成时间+该进程服务时间）；

  3. 重复2直至完成所有进程的计算。

抢占式调度

  1. 找出最先到达的进程（该进程的完成时间=到达时间+服务时间）

  2. 根据上一进程的完成时间，找到在这个完成时间内所有到达的进程，并找到这些进程中服务时间最短的那个，在进程运行中，有新到达的进程时，会比较两者的服务时间（该进程剩余的服务时间与新进程的服务时间进行比较，若小则继续运行，若大则暂停进程，新进程运行。）

  3. 重复2直至完成所有进程的计算。

💡 TIP

这里有基于最短服务时间和基于最短剩余服务时间两种

上面提供的抢占式调度流程，是基于最短剩余时间的

SJF特点是降低了系统平均周转时间。

但对长作业不利，长作业有可能长时间得不到调度。

优先级调度算法

高响应比优先调度算法

  • 响应比

    $$
    R_P = \frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}} = \frac{\text{响应时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{服务时间}}
    $$

📝 NOTE

相关例题

image-20241220163207688

解题方略

画表画轴

在考察这类知识点时，一般题目都会给出进程到达时间以及进程运行时间 (也叫服务时间)

在草稿纸上画表，加上开始时间，完成时间，周转时间，带权周转时间项

然后，画数轴，来反映进程执行状态

image-20241220165621402

优缺点

  • 如等待时间相同，取决于运行时间，类似于SJF

  • 如运行时间相同，取决于等待时间，类似于FCFS

  • 长作业可随其等待时间的增加而提高，也可得到服务

  • 缺点：每次调度之前，都需要计算响应比，增加系统开销

时间片轮转调度算法

  • 一般准则：时间片/10>进程上下文

多级队列调度算法

  • 就绪队列从一个分为多个，如：

    • 前台[交互式]
    • 后台[批处理]

  • 每个队列都有自己的调度算法

  • image-20241220172015600

💡 TIP

几种调度算法对比

短作业优先（SJF）：最低的平均周转时间和平均带权周转时间，但对长作业不公平。

高响应比优先（HRRN）：平衡了短作业和长作业的公平性。

优先级调度：灵活性高，但需要合理设置优先级。

先来先服务（FCFS）：实现简单，但可能导致性能低下。

📝 NOTE

多个作业同时到达时

短作业优先算法拥有最低的平均周转时间

死锁

image-20241220183729683

死锁的必要条件

  • 互斥

    资源在某一时刻只能被一个资源占有或使用

  • 请求和保持

    一个进程已经持有至少一个资源，同时又请求其他资源

  • 不可抢占（不可剥夺）

    已经分配给某个进程的资源，在未被进程主动释放前，不能被其他进程强行夺走

  • 循环等待（环路等待）

    系统中存在一个进程等待环，环中的每个进程都在等待下一个进程持有的资源。

📝 NOTE

判断是否死锁的方法

系统中有 $N$ 个进程，某种资源 $M$ 个，每个进程需要最多 $k$ 个资源，系统不会发生死锁的条件是：
$$
N(k-1) < M
$$
即，先给每个进程分给他们所需要资源少于一个的资源，如果此时还有多的资源，则一定会有一个进程可以启动，所以就不会发送死锁

处理死锁的方法

死锁的避免

  • 银行家算法

    通过记录资源使用情况，以避免死锁的发生

    • 操作系统：银行家

    • 资源：周转资金

    • 进程：贷款的客户

安全状态与不安全状态

  • 安全状态：

    是指系统能按某种进程顺序 ($P_1$ ， $P_2$ ，$Pn$)( 称〈 PI·” Pn 〉序列为安全序列），来为每个进程 P i 分配其所需资源直牵满足每个进程对资源的最大需求，使每个进程都可顺利地成。

  • 不安全状态：

    如果系统无法找到这样一个安全序列，则称系统于不安全状态。

image-20241220190054024

银行家算法

略

死锁检测

  • 资源分配图

image-20241220190426767

image-20241220190438547

image-20241220190453753

image-20241220190547182

image-20241220190559889

image-20241220190711273

(完)