操作系统-第八章作业
一.问答题
1.处理机调度都包括几种类型？简述各类调度的主要任务。
高级调度：
负责从后备队列中选择作业，调入内存创建进程并分配资源，使其进入就绪队列。主要用于多道批处理系统，分时和实时系统一般不使用。
中级调度：
将暂时不运行的进程移至外存进入挂起状态，提升内存利用率和系统吞吐量。中级调度决定何时将挂起进程重新调入内存。
低级调度：
主要在就绪队列中选择进程并分配CPU。适用于多道批处理、分时和实时系统，是基本的调度方式。
2.什么是作业？
用户在一次解题过程中要求计算机所做工作的集合称为一个作业
3.作业从进入系统开始到执行完毕，作业的状态有哪几种？
- 提交状态
- 后备状态
- 执行状态
- 完成状态
4.请说明在不同的操作系统环境下会具有哪些调度级别。
批处理系统：
使用高级调度控制作业进入内存，有时使用中级调度来挂起进程节省内存，低级调度分配CPU
分时系统
一般没有高级调度，可能有中级调度以挂起不活跃进程，低级调度用时间片实现多用户共享CPU
实时系统：
无高级和中级调度，关键是低级调度，通过优先级和抢占机制确保任务按时完成
5.试述作业、程序、进程、线程之间的关系。
作业是用户提交的任务整体，包括程序和所需资源
程序是实现任务的代码，但本身不执行
进程是程序的执行实体，是系统分配资源的基本单位，每个作业至少有一个根进程
线程是进程内部的执行路径，多个线程共享进程资源并能并发执行，提高效率
6.简述衡量一个处理机调度算法优劣的主要标准。
CPU利用率，表示CPU有效工作时间的百分比，越高越好。
吞吐量，单位时间内完成的进程数，越多越好。
周转时间，进程从提交到完成的总时间，越短越好。
响应时间，用户请求到系统响应的时间，越短越好。
带权周转时间，反映了调度的公平性。- 带权周转时间越小，说明长短作业都能较合理地得到处理。
公平性，指资源分配是否公平，避免某些进程长时间等待或饥饿。
7.什么是周转时间？- 带权周转时间？响应时间？吞吐率？
周转时间：指作业从提交时刻开始到完成时刻为止所经历时间。
带权周转时间：指作业周转时间和作业执行时间的比值。
响应时间：是从作业到达系统到其首次获得 CPU 服务所需的时间。
吞吐率：单位时间内完成的进程或作业数。
8.什么是JCB？说明JCB的作用并列举其主要内容。
作业调度程序为每个进入系统的作业建立JCB。在作业建立到消亡的整个过程中，JCB一直存在，直到作业撤销时。JCB是作业存在的标志。
系统为每个作业建立一个作业控制块(JCB)来对作业进行控制管理并记录作业在运行过程中的状态。
9.简述作业调度与进程调度之间的关系。
- 定义与作用：
- 作业调度（Job Scheduling）决定哪些作业进入内存并获得系统资源，属于长程调度，控制系统负载。
- 进程调度（Process Scheduling）决定分配给哪个进程使用 CPU，属于短程调度，提升 CPU 利用率。
- 调度频率：
- 作业调度频率较低，只在作业进入系统时进行。
- 进程调度频率较高，每次进程阻塞或时间片到期都会发生。
- 资源分配的阶段：
- 作业调度控制进入内存的作业数量。
- 进程调度进一步分配 CPU 资源，直接影响系统的响应速度。
- 相互关系：
- 作业调度决定了系统中可供进程调度的对象，进程调度在此基础上分配 CPU，实现高效执行。
10.举例说明Linux系统中对于交互式进程和计算型进程设计时间片大小的原则。
- 交互式进程：
- 原则：短时间片，快速响应。
- 例子：如文本编辑器、浏览器等，用户频繁输入需要即时反馈。
- 计算型进程：
- 原则：长时间片，减少切换开销。
- 例子：如数据处理或视频渲染，需长时间计算，减少频繁切换效率更高。
- 动态调整：
- 原则：系统可根据进程行为调整时间片。
- 例子：进程在运行时根据是否频繁等待 I/O，调整其时间片长度。
11.简述多级反馈轮转法调度策略中各级进程所享用的时间片大小的设置原因。
初始进入的进程在高优先级队列中，时间片较短，方便快速响应和优先处理短任务。如果进程未完成任务，就会降级到更低优先级队列，获得更长的时间片，从而减少频繁的调度切换，提高CPU利用率。
这种设计既保证了短任务的快速响应，又能让长任务更有效地使用CPU资源，减少上下文切换带来的开销。
12.什么是死锁？
多个进程因相互等待对方释放资源，形成循环等待，导致无法继续执行的状态。
13.试述产生死锁的必要条件。
互斥条件 不可剥夺条件 部分分配条件 环路等待条件
14.系统有输入机和打印机各1台，现有两个进程都要使用它们，采用PV操作实现请求使用和归还资源后，还会产生死锁吗？请说明理由。若是，则给出防止死锁的方法。
在系统中，只有一台输入机和一台打印机，两个进程都需要它们时，依靠PV操作可能会导致死锁。例如，进程A获得输入机后等待打印机，而进程B获得打印机后等待输入机，这样就产生了死锁
- 防止死锁的方法有： 资源有序分配：规定资源请求顺序，如先请求输入机再请求打印机，避免循环等待 资源预分配：运行前检查是否能分配所有资源，若不能，则进程等待，防止死锁 超时放弃：设置等待超时，进程等待超时则放弃资源，避免死锁
15.假设3个进程共享4个资源，每个进程一次只能申请一个资源，每个进程最多需要两个资源，证明此系统不会产生死锁。
每个进程最多需要2个资源，系统共有4个资源，因此即使有2个进程各占用1个资源，系统仍有2个资源剩余，可以满足至少一个进程的资源需求，避免循环等待，从而不会产生死锁。
二、计算题
1. 现有作业1～作业5(J1～J5)，如表3-11所示，作业编号即其到达系统顺序，在时刻0依次按顺号由低到高进入单CPU系统中，请分别采用FCFS、SJF、时间片轮转法(时间片大小为2ms)、非抢占式优先权调度算法计算各作业的平均周转时间和平均- 带权周转时间，以及作业调度顺序。表中优先权数值越大优先级越高。
调度算法
为了完成这个任务，我们将对四种调度算法进行讲解，并分析各作业的平均周转时间和平均- 带权周转时间。
1. 先来先服务调度算法 (FCFS)
描述：先来先服务算法按照作业到达的先后顺序来调度作业。作业越早到达系统，就越早得到处理。
调度顺序： 根据作业的到达顺序依次调度作业 $J1 \rightarrow J2 \rightarrow J3 \rightarrow J4 \rightarrow J5$。
2. 最短作业优先调度算法 (SJF)
描述：最短作业优先调度算法选择执行时间最短的作业进行调度，直到该作业完成。这样可以减少作业的平均周转时间。
调度顺序： 按执行时间从短到长调度作业：$J3 \rightarrow J2 \rightarrow J5 \rightarrow J4 \rightarrow J1$。
3. 时间片轮转法 (RR)
描述：时间片轮转法为每个作业分配一个时间片，在时间片内未完成的作业会被放到队列尾部等待下次执行。这样可以确保每个作业得到公平的 CPU 处理时间。
调度顺序： 每个作业在其时间片用完后会被放到队列的末尾，直到全部作业完成。具体的顺序会根据时间片大小进行切换。
4. 非抢占式优先权调度算法
描述：非抢占式优先权调度算法根据优先级调度作业，优先级越高的作业优先得到执行。这里优先级数值越大优先级越高。
调度顺序： 按照优先级从高到低调度作业：$J5 \rightarrow J3 \rightarrow J1 \rightarrow J2 \rightarrow J4$。
答案
FCFS：
作业1 (J1)
- 开始时间：0
- 结束时间：0 + 11 = 11
- 周转时间：11 - 0 = 11
- 带权周转时间：11 / 11 = 1.0
作业2 (J2)
- 开始时间：11
- 结束时间：11 + 2 = 13
- 周转时间：13 - 0 = 13
- 带权周转时间：13 / 2 = 6.5
作业3 (J3)
- 开始时间：13
- 结束时间：13 + 1 = 14
- 周转时间：14 - 0 = 14
- 带权周转时间：14 / 1 = 14.0
作业4 (J4)
- 开始时间：14
- 结束时间：14 + 4 = 18
- 周转时间：18 - 0 = 18
- 带权周转时间：18 / 4 = 4.5
作业5 (J5)
- 开始时间：18
- 结束时间：18 + 2 = 20
- 周转时间：20 - 0 = 20
带权周转时间：20 / 2 = 10.0
- 平均周转时间 = (11 + 13 + 14 + 18 + 20) / 5
- 平均- 带权周转时间 = (1.0 + 6.5 + 14.0 + 4.5 + 10.0) / 5
- 进程调度顺序：1–>2–>3–>4–>5
SJF (最短作业优先)
作业3 (J3)
- 开始时间：0
- 结束时间：0 + 1 = 1
- 周转时间：1 - 0 = 1
- 带权周转时间：1 / 1 = 1.0
作业2 (J2)
- 开始时间：1
- 结束时间：1 + 2 = 3
- 周转时间：3 - 0 = 3
- 带权周转时间：3 / 2 = 1.5
作业5 (J5)
- 开始时间：3
- 结束时间：3 + 2 = 5
- 周转时间：5 - 0 = 5
- 带权周转时间：5 / 2 = 2.5
作业4 (J4)
- 开始时间：5
- 结束时间：5 + 4 = 9
- 周转时间：9 - 0 = 9
- 带权周转时间：9 / 4 = 2.25
作业1 (J1)
- 开始时间：9
- 结束时间：9 + 11 = 20
- 周转时间：20 - 0 = 20
- 带权周转时间：20 / 11 ≈ 1.82
SJF 总结
- 平均周转时间 = (1 + 3 + 5 + 9 + 20) / 5
- 平均- 带权周转时间 = (1.0 + 1.5 + 2.5 + 2.25 + 1.82) / 5 调度顺序：J3 → J2 → J5 → J4 → J1
时间片轮转法（时间片大小为2ms）
作业1
- 开始时间：0
- 结束时间：21
周转时间：21 - 带权周转时间：1.91
作业2
- 开始时间：2
- 结束时间：4
周转时间：4 - 带权周转时间：2.0
作业3
- 开始时间：4
- 结束时间：6
周转时间：6 - 带权周转时间：6.0
作业4
- 开始时间：6
- 结束时间：14
周转时间：14 - 带权周转时间：3.5
作业5
- 开始时间：8
- 结束时间：10
周转时间：10 - 带权周转时间：5.0
平均周转时间：11.0
平均- 带权周转时间：3.28
进程调度顺序：J1 → J2 → J3 → J4 → J5 → J1 → J4 → J1 → J1 → J1 → J1
2.在某多道程序系统中(道数无限制)，作业进入后备队列即开始作业调度。现有4道作业进入系统，信息如表3-12所示(表中数据均为十进制)，作业和进程调度采用最高优先级算法(规定优先数数值越大优先级越高)。
作业4
- 开始时间：8.5
- 结束时间：8.6
- 周转时间：0.1
- 带权周转时间：1.0
- 作业3
- 开始时间：8.6
- 结束时间：8.9
- 周转时间：0.6
- 带权周转时间：2.0
- 作业1
- 开始时间：8.9
- 结束时间：9.5
- 周转时间：1.5
- 带权周转时间：2.5
- 作业2
- 开始时间：9.5
- 结束时间：9.7
- 周转时间：1.6
带权周转时间：8.0
- 平均周转时间：0.95
- 平均带权周转时间：3.38
- 进程调度顺序：4 → 3 → 1 → 2
3.一个3道批处理系统中，作业调度采用SJF调度算法，进程调度采用优先数为基础的抢占式调度算法。作业信息如表3-14所示(表中数据全部为十进制形式)，作业优先数即进程优先数，优先数越小则优先级越高。
调度算法
抢占式优先调度算法分析
抢占式优先调度算法在进程调度阶段进行，这意味着在执行过程中，如果有更高优先级的进程到达（优先数更小），当前进程将被抢占。
答案
根据题目描述，作业调度采用SJF调度算法（Shortest Job First，短作业优先），而进程调度采用优先数为基础的抢占式调度算法。这样一来，短作业会优先被调度，同时当有更高优先级的作业到达时，当前作业会被抢占。优先数越小，优先级越高。
以下是基于这些规则的详细调度过程：
作业 1：
- 开始时间：9.0
- 暂停时间：9.2（被作业 2 抢占）
作业 2：
- 开始时间：9.2
- 结束时间：9.5
作业 5：
- 开始时间：9.5
- 结束时间：9.9
作业 3：
- 开始时间：9.9
- 结束时间：10.5
作业 6：
- 开始时间：10.5
- 结束时间：10.6
作业 4：
- 开始时间：10.6
- 结束时间：10.9
作业 1（继续）：
- 开始时间：10.9
- 结束时间：11.3
最终调度顺序： 1 → 2 → 5 → 3 → 6 → 4 → 1
在此调度顺序中，作业 1 在最初执行一段时间后被更高优先级的作业抢占，后续再重新获得CPU完成其执行。
4.操作系统中有15个进程，竞争使用50个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用3个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？若不会产生死锁，该类资源最少应该为多少个？
不会死锁
因为每个进程最多需要3个资源，系统最多需要 15×3=45 个资源。而资源有50>45，因此不会产生死锁
最少资源数=总需求−(进程数−1)=45−(15−1)=45−14=31
系统需要至少31个资源才能确保不发生死锁
5.一台计算机有8台刻录机，被N个进程竞争使用，每个进程可能需要3台刻录机。请问N为多少时，系统没有死锁的危险？并说明理由。
假设每个进程最多需要3台刻录机，系统共有8台刻录机，则满足以下条件时不会死锁：
系统死锁分析
假设每个进程最多需要3台刻录机，系统共有8台刻录机，则满足以下条件时不会死锁：
$8 \geq 3N - (N - 1)$
简化得出: $N \leq 4$
当 $N \leq 4$ 时，系统没有死锁的危险。
6.某系统有m个同类资源供n个进程共享，若每个进程最多申请x个资源(1≤x≤m)，请推导系统不产生死锁的关系式(n, m和x)。
系统要避免死锁，需满足资源总数足以让至少一个进程完成并释放资源，以逐步满足其他进程需求。
对于每个进程最多申请 $x$ 个资源，系统中的资源数$m$应满足以下关系： $m \geq n \times (x - 1) + 1$ 。
即系统不产生死锁的条件是 $m \geq n \times (x - 1) + 1$ 。
7.假设系统中有5个进程(p1、p2、p3、p4、p5)和A、B、C三类资源，各种资源的数量分别为10、5、9，在T0时刻的资源分配情况如表3-16所示。
(1) 分析T0时刻系统是否是安全的？
根据银行家算法，用当前剩余资源检查是否能满足各进程需求。通过安全性检测，可以得到安全序列为p2 → p4 → p5 → p1 → p3，因此系统是安全的。
(2) 若T0时刻p2进程请求分配资源(1,0,2)，系统按银行家算法是否会实施分配？
p2的请求小于等于当前剩余资源，可以尝试分配。分配后更新剩余资源，再进行安全性检测，得到安全序列p2 → p4 → p5 → p1 → p3，因此该分配是安全的，系统会实施分配
(3) 若T0时刻p5进程请求分配资源(3,3,0)，系统按银行家算法是否会实施分配？
p5的请求大于当前剩余资源，无法满足，因此系统不会实施分配
(4) 若T0时刻p1进程请求分配资源(0,2,0)，系统按银行家算法是否会实施分配？
p1的请求小于等于当前剩余资源，可以尝试分配。分配后更新剩余资源，再进行安全性检测，得到安全序列p2 → p4 → p5 → p1 → p3，因此该分配是安全的，系统会实施分配