【SCAU操作系统】期末复习简答及计算题例题解析

一、写出下列英文缩写词在计算机系统中的英文或中文全名。

OS: Operating System 操作系统
PSW: Program Status Word 程序状态字
FCFS: First Come First Serve 先来先服务
PCB: Process Control Block 进程控制块
DMA: Direct Memory Access 直接存储器存取
MMU: Memory Management Unit 内存管理单元
OPT: Optimal 最佳置换算法
RR: Round Robin 轮转
i-node: index node 索引节点
FF: First Fit 首次适配
FAT: File Allocation Table 文件分配表
PID: Process ID 进程标识符

BF：Best Fit 最佳适配
NF：Next Fit下次适配

二、进程状态/调度/周转问题

（1）进程状态

假设在时刻 3 时，系统资源只有处理器和内存被使用，然后发生如下事件：
时刻 6：P1 执行“写磁盘”操作。
时刻 15：P2 执行“读磁盘”操作。
时刻 23：P3 时间片结束。
时刻 28：P1“写磁盘”完成，产生中断。
时刻 32：P4 时间片结束。
请分别写出在时刻 20 和时刻 30 时，进程 P1、P2、P3 是什么状态。
答：时刻 20：P1 阻塞态，P2 阻塞态，P3 运行态。
时刻 30：P1 就绪态，P2 阻塞态，P3 就绪态。（此时 P4 运行态）

解析：

进程状态通常包括：就绪态（Ready）、运行态（Running）、阻塞态（Blocked/Waiting）等。

时刻 3：系统资源只有处理器和内存被使用。
时刻 6：P1 执行“写磁盘”操作。
P1 进入阻塞态，因为磁盘I/O操作是阻塞性的。
时刻 15：P2 执行“读磁盘”操作。
P2 进入阻塞态，原因同上。

时刻 20：
   P1 阻塞态：因为P1的“写磁盘”操作尚未完成（6——28）。
   P2 阻塞态：P2的“读磁盘”操作只是在时刻15请求了磁盘操作。
   P3 运行态：P3在时刻20运行，在时刻23时间片结束。

时刻 23：P3 时间片结束。
P3 从运行态变为就绪态，等待下一次调度。
时刻 28：P1“写磁盘”完成，产生中断。
P1 从阻塞态变为就绪态，因为磁盘操作已完成，等待调度。

时刻 30：
   P1 就绪态：P1的磁盘操作已完成。
   P2 阻塞态：P2的“读磁盘”操作可能尚未完成，因此它仍处于阻塞态。
   P3 就绪态：P3在时刻23时间片结束后处于就绪态。
   （P4 运行态：时刻32时间片结束）

（2）进程状态转换

画出进程的五状态转换模型，包括各状态间的转换方向和转换原因。
评分标准：五状态名称 4 分，转换方向和转换原因各 1 分。
答：

（3）进程调度

简述进程的抢占式调度和非抢占式调度的区别。
答：

非抢占：在这种情况下，一旦进程处于运行态，它就不断执行直到终止，或者为等待 I/O 或请求某些操作系统服务而阻塞自己。
抢占：当前正在运行的进程可能被操作系统中断，并转移到就绪态。是否抢占当前进程的决策可能发生在一个新进程到达时，或者在一个中断发生后把一个被阻塞的进程置为就绪态时，或者基于周期性的时间中断。

（4）最短进程优先调度算法

五个进程 A～E 的提交时刻和预计运行时间 Ts 如下。对于最短进程优先调度算法，填写下表，确定每个进程的周转时间、归一化周转时间 Tr/Ts、及所有进程的平均值。

进程	提交时刻	服务时间Ts	开始时刻	结束时刻	周转时间Tr	Tr/Ts
A	0	5	0	5	5	1
B	4	5	5	10	6	1.2
C	6	6	16	22	16	2.67
D	6	2	10	12	6	3
E	10	4	12	16	6	1.5
平均值					7.8	1.87

评分标准：每对周转时间和归一化周转时间 1 分。

根据Ts对进程进行排序：
D (Ts=2, 提交时刻=6)
A, B (Ts=5, 提交时刻分别为0和4)
E (Ts=4, 提交时刻=10)
C (Ts=6, 提交时刻=6)
由于A在B先提交且Ts相同，所以A先被调度。同时，D和C提交时刻相同，但D的Ts更短，所以D更先调度。

三、逻辑地址计算

在采用页式存储管理的系统中，若逻辑地址用 48 位表示，其中 32 位表示页号。画出逻
辑地址的结构，并计算每页的最大长度及一个进程的逻辑地址空间的最大长度。

答：逻辑地址结构：

32b 页号

16b 页内地址

每页最大长度：2^16B=64KB
程序地址空间最大长度：2^48B=256TB
解析：

逻辑地址结构：
在页式存储管理系统中，逻辑地址被分为两部分：页号和页内地址（或称为页内偏移量）。

        依题，逻辑地址总共是48位，其中32位用于表示页号，剩下的16位用于表示页内地址。然后画出结构。
每页的最大长度：
        页内地址用于定位页面内的具体位置，因此决定了每页的最大长度。
        依题，页内地址是16位，所以它最多可以表示2^16个不同的地址。由于每个地址通常对应一个字节（byte），所以每页的最大长度是2^16字节，即64KB。
一个进程的逻辑地址空间的最大长度：
        逻辑地址空间的最大长度取决于页号的位数。
        依题，页号是32位，所以它最多可以表示2^32个不同的页面。结合每页的大小64KB，逻辑地址空间的最大长度是256TB。

即是

四、中断技术问题

（1）中断处理时出现新中断的处理方式

当一个中断正在处理时，又发生新的中断，简述此时的两种处理方式。
答：处理多中断有两种方法。

第一种方法是当正在处理一个中断时，禁止中断，顺序处理所发生的各个中断。

第二种方法是中断嵌套，定义中断优先级，允许高优先级中断打断低优先级中断的处理过程

（2）缺页中断处理

在分页虚拟存储管理系统中，什么情况下发生缺页中断？简述缺页中断的处理过程。
答：当 CPU 发出访问的逻辑地址的所在页还未调入内存时，发生缺页中断。
缺页中断的处理过程大致如下：首先判断内存中是否有空闲帧？如果没有则按照置换算法
选择一个内存页淘汰，如果该页被修改过还需先写回磁盘，这样得到一个空闲帧。然后按
照页表所指明的该页磁盘地址把此页调入空闲帧，修改页表，重新执行刚才那条指令。

五、存储的分配算法

简述可变分区存储管理中常用的 FF、BF、WF 分配算法的原理。
答：最先适应法（First Fit）：空闲区链表按起址递增顺序排列。分配时从链首开始查找，
从第一个满足要求的空闲区中划分出作业需要的大小并分配，其余的部分作为一个新空闲
区。
最佳适应法（Best Fit）：空闲区链表按分区大小递增顺序排列。分配时从链首开始查找，
第一个满足要求的空闲区就是满足要求的最小空闲区。
最坏适应法（Worst Fit）：空闲区链表按分区大小递减顺序排列。分配时从链首开始查找，
第一个空闲区不能满足要求时分配失败，否则从第一个空闲区中切出需要的大小分配。

六、磁盘读写问题

（1）寻道时间计算

假设磁头当前位置为 40 柱面，现有一个磁盘读写请求队列：20、44、40、4、80、12、
76。若寻道时移动一个柱面需 3ms，按最短寻道时间优先 SSTF 算法计算所需的寻道时间
总量。

答：
SSTF 调度顺序：40、44、20、12、4、76、80。移动总量（4+24+8+8+72+4)=120，
总寻道时间=120*3ms=360ms。

初始磁头位置是 40 柱面。
磁盘读写请求队列是：20、44、40、4、80、12、76。
按照 SSTF 算法选择距离当前磁头位置最近的请求进行服务：
4（40-44）+ 24（44-20）+ 8（20-12）+ 8（12-4）+ 72（4-76）+ 4（76-80）= 120柱面。
因为寻道时移动一个柱面需 3ms，所以总寻道时间是=120 柱面 * 3ms/柱面 = 360ms。

（2）寻道时间计算

假设磁头当前位置为 20 柱面，现有一个磁盘读写请求队列：10、22、20、2、40、6、38。若寻道时移动一个柱面需 3ms，按电梯算法（磁头正向磁道号增大方向移动）计算所需的寻道时间总量。
答：
电梯调度顺序：20、22、38、40、10、6、2。移动总量（2+16+2+30+4+4)=58，
总寻道时间=58*3ms=174ms。

电梯算法（SCAN算法或LOOK算法）是一种磁盘调度算法，它模拟电梯的运行方式，即磁头在磁盘上按照一个方向移动，直到到达该方向上的最后一个请求，然后改变方向继续服务。
初始磁头位置是 20 柱面。
磁盘读写请求队列是：10、22、20、2、40、6、38。
假设磁头从20柱面开始，向磁道号增大的方向（正向）移动。
总的移动柱面数：
2（20-22）+ 16（22-38）+ 2（38-40）+ 30（40-10）+ 4（10-6）+ 4（6-2）= 58 柱面。
因为寻道时移动一个柱面需 3ms，所以总寻道时间是：
58 柱面 * 3ms/柱面 = 174ms。

七、资源占用/分配

（1）

有 A,B,C,D 共 4 种资源，在某时刻 P0~P4 对资源的占有和需求情况如下表。
进程
Allocation 已分配    Claim 最大需求        Available 可用
            A B C D            A B C D                       A B C D
P0 0 0 3 2             0 0 4 4                         1 6 2 2
P1 1 0 0 0             2 7 5 0
P2 1 3 5 4             3 6 10 10
P3 0 3 3 2            0 9 8 4
P4 0 0 1 4            0 6 6 10
问：1）系统此时处于安全状态吗？若是，给出安全序列；若不是，说明原因。

1）安全，安全序列 <P0, P3, P4, P1, P2>。
2）若此时 P1 发出 request(1,2,2,2)，系统能满足其请求吗？为什么？
2）不能。此次申请资源量超过了 P1 的“尚需资源量”。

安全状态意味着存在一个安全序列，即存在一个进程序列，使得按照这个序列依次分配资源，每个进程都能完成其任务并释放资源，最终系统不会处于死锁状态。
1）判断系统是否处于安全状态：
计算每个进程还需要多少资源（Claim-Allocation）。尝试找到一个安全序列，即找到一个进程序列，使得按照这个序列，每个进程在其前面的进程释放资源后都能获得所需的资源。已分配 (Allocation) 和最大需求 (Claim) 的差值即为尚需资源量：
P0: 尚需 (0, 0, 1, 2)
P1: 尚需 (1, 7, 5, 0)
P2: 尚需 (2, 3, 5, 6)
P3: 尚需 (0, 6, 5, 2)
P4: 尚需 (0, 6, 5, 6)
现有可用资源 (Available) 为 (1, 6, 2, 2)。
找到一个安全序列：<P0, P3, P4, P1, P2>。
2）对于 P1 发出 request(1,2,2,2) 的情况：
P1 尚需 (1, 7, 5, 0)，如果 P1 请求 (1, 2, 2, 2)，则 P1 的尚需资源将变为 (0, 5, 3, 0)。当前可用资源 (1, 6, 2, 2) 无法满足 P1 的这个请求。

八、死锁相关

（1）

系统资源分配图如下，请问现在是否已处于死锁状态，如果是，撤消哪个进程可以使系统代价最小地从死锁中恢复。

答：已处于死锁状态。撤消 P1 代价最小，因为剥夺的资源最少。

资源分配图是描述系统中进程与资源的申请和分配情况的有向图。
方框结点表示资源，圆圈结点表示进程。
从方框结点指向圆圈结点的有向边表示某类资源被某进程占有，从圆圈结点指向方框结点的有向边表示某进程申请某类资源。
由于某一类资源可能含有多个同类资源，在方框中用圆点来表示同一类资源的数目

R1-->P3、P4（R1一共三个资源，分配一个资源给P4，分配两个资源给P3）
R2-->P2、P3（R2一共两个资源，已经各分配一个给P2、P3；但是P1-->R2表示P1还需要一个R2才能执行，P2还需要一个R2）
R3-->P1、P2（R3一共两个资源，已经各分配一个给P1、P2；但是P3-->R3表示P3还需要一个R3才能执行，P4还需要一个R3）

（2）

简述死锁的四个必要条件。
答：
互斥：涉及的是需互斥访问的临界资源。
占有且等待：进程申请资源而阻塞时，继续占有（不释放）已分配的资源。
不可抢占：进程已占用的资源未使用完前不可强行剥夺，只能由进程自愿释放。
循环等待：进程间形成一个等待资源的循环链。

九、缺页问题

在一个请求分页系统中，假定系统分配给一个进程的物理帧数为 3，所有帧初始均为空。
此进程的页面访问顺序为 4、3、2、1、4、3、5、4、3、2、1、5。试用 OPT 和 LRU 页面
置换算法给出页面置换情况，并计算所发生的缺页总次数。
答：OPT 算法：缺页次数为 7。

页面走向	4	3	2	1	4	3	5	4	3	2	1	5
帧1	4	4	4	4			4			2	2
帧2		3	3	3			3			3	1
帧3			2	1			5			5	5
缺页	缺	缺	缺	缺			缺			缺	缺

LRU 算法：缺页次数为 10。

页面走向	4	3	2	1	4	3	5	4	3	2	1	5
帧1	4	4	4	1	1	1	5			2	2	2
帧2		3	3	3	4	4	4			4	1	1
帧3			2	2	2	3	3			3	3	5
缺页	缺	缺	缺	缺	缺	缺	缺			缺	缺	缺

十、计算物理地址

在一页式存储管理系统中，某作业页表如下。已知页面大小为 1024 字节，问逻辑地址1068，2566，5699 所对应的物理地址各是多少？如果需要置换一页，应该选择哪一页？置换后所对应的物理地址是多少？

页号	帧号	有效位	访问位	修改位
0	8	1	1	0
1	3	1	1	1
2		0	0	0
3	1	1	0	0
4		0	0	0
5	2	1	0	1

答：
1) 1068 位于 1#页，页内偏移 44，物理地址 3×1024＋44＝3116
2) 2566 位于 2#页，页内偏移 518，但此页不在内存，所以产生缺页中断。置换时应该选
择 3#页。置换后 2566 对应的物理地址是 1×1024＋518＝1542
3) 5699 位于 5#页，页内偏移 579，物理地址 2×1024＋579＝2627

逻辑地址到物理地址的转换
在一页式存储管理系统中，逻辑地址被分为页号和页内偏移两部分。页面大小1024字节，页内偏移是10位（2^10=1024）。逻辑地址的前几位表示页号，剩余位表示页内偏移。
逻辑地址1068：
页号=1068 // 1024 = 1
页内偏移 = 1068 mod 1024 = 44
查找页表，页号1对应的帧号是3，所以物理地址 = 3 * 1024 + 44 = 3116

物理地址 = 帧号 * 页面大小 + 页内偏移

十一、CPU和磁盘利用率

（1）

若检测到 CPU 和磁盘利用率如下，请问现在可能发生了什么情况，应采取什么措施？
1）CPU 10%，磁盘 94%。
2）CPU 55%，磁盘 3%。

答：
1) CPU 10%，磁盘 94%：此时系统可能已经出现抖动，可暂停部分运行进程；
2) CPU 55%，磁盘3%：此时系统运行正常，磁盘利用率稍低，可增加进程数
以提供资源利用率。

（2）

设作业 A、B、C 的优先级递减，可抢占 CPU 但不能抢占 I/O 设备。运行轨迹如下：
A：CPU 20ms, I/O 30ms, CPU 10ms
B：CPU 40ms, I/O 20ms, CPU 10ms
C：CPU 10ms, I/O 30ms, CPU 20ms
求多道并发运行时的 CPU 利用率。
答：多道时按 A、B、C 并发运行，
总运行 140ms，CPU 利用率＝110/140＝78.6％

十二、动态分区内存管理技术

某系统采用动态分区内存管理技术。设操作系统在低地址占用了 100KB 空间，用户空间从 100KB 至 612KB，初始时用户空间全部为空闲，分配时截取空闲分区的低地址部分作为已分配区。若采用最佳适配算法，执行以下申请释放操作序列：请求 300KB；请求 100KB；释放 300KB；请求 150KB；请求 50KB；请求 90KB。画出内存分布图，并指出空闲分区的首地址和大小。

答：空闲区有 2 块：块 1（首地址 340KB，大小 60KB），块 2（首地址 550KB，
大小 62KB）。

十三、虚拟分页内存管理技术

描述虚拟分页内存管理技术的基本原理及其优点。

答：内存被划分成许多大小相等的页框，进程被划分为许多大小与页框相等的
页；进程的页在需要访问时，装入内存中不一定连续的某些页框中。（评分标准：4 分）
没有外部碎片，多道程序度更高，虚拟地址空间巨大。（评分标准：2 分）

十四、原语伪代码

写出 semWait 和 semSignal 原语的伪代码定义。
答： semWait 原语：

semWait(semaphore s)
{
    s.count－－;
    if (s.count < 0)
    { 将当前进程放入 s.queue;
    阻塞当前进程;
    }
}

semSignal 原语

semSignal(semaphore s)
{
    s.count＋＋;
    if (s.count <= 0)
    { 从 s.queue 中移除进程 P;
    将进程 P 插入就绪队列;
    }
}

评分标准：各3分。