《操作系统》期末试卷A (精选03)

一、概念辨析题（判断下列说法的对错，错误的请说明理由，每题 3分，共计 24 分）

1. 操作系统的不确定性是说在 OS 控制下多个进程的执行顺序和每个进程的周转时间是不确定的。

查看答案与解析

答案：正确。

解析： 本题考查操作系统的基本特征。 操作系统的异步性（也称不确定性）是指在多道程序环境下，允许多个进程并发执行。但由于资源有限和进程间的相互制约，进程的推进速度是不可预知的，即“走走停停”。这直接导致了多个进程的执行顺序以及每个进程的周转时间（从提交到完成的时间）具有不确定性。

---

难度: ⭐
考点: #操作系统特征 #异步性 #不确定性

💡 学习锦囊

📖 相关公式与知识点:

• 操作系统的四大基本特征：并发、共享、虚拟、异步。
• 异步性与并发性相伴相生，没有并发就没有异步。

思路分析

看到“不确定性”，立刻联想到 OS 的“异步性”。只要理解“异步”是指速度不可控、顺序不可控，即可判定为正确。

🔄 举一反三

1. 操作系统中并发执行的进程，其执行结果具有什么特点？
   查看练习答案与解析

   答案：不可再现性。
   解析：并发进程由于异步推进，执行顺序不确定，如果对共享资源进行无互斥访问，可能会导致相同的初始条件得出不同的结果。

2. 多道程序设计可以缩短系统中作业的执行时间。

查看答案与解析

答案：错误。

理由： 多道程序设计的主要目标是提高系统资源的利用率和系统吞吐量（单位时间内完成的作业量）。然而，由于内存中有多道程序并发执行，它们会竞争 CPU 和 I/O 等资源，导致频繁的进程切换和等待。因此，对于单个作业而言，其执行时间（周转时间）通常会比独占系统时更长，而不是缩短。

---

难度: ⭐⭐
考点: #多道程序设计 #吞吐量 #周转时间

💡 学习锦囊

📖 相关公式与知识点:

• 吞吐量：单位时间内系统处理的作业数量。
• 周转时间：作业完成时间 - 作业提交时间。

思路分析

注意区分“系统整体效率”与“单个作业耗时”。并发虽然提升了整体效率，但增加了单个作业的排队等待时间。

易错点

误以为“效率提高”等于“时间缩短”。并发带来的开销（切换、竞争）会导致单个任务变慢。

🔄 举一反三

1. 引入多道程序设计技术的根本目的是什么？
   查看练习答案与解析

   答案：提高系统资源的利用率和吞吐量。
   解析：在单道程序环境下，CPU 经常需要等待 I/O 导致资源浪费；多道程序允许 CPU 在等待 I/O 时切换到其他作业执行。

3. 进程 A 和进程 B 共享变量 1，需要互斥；进程 B 和进程 C 共享变量 2，需要互斥；从而进程 A 与进程 C 也必须互斥。

查看答案与解析

答案：错误。

理由： 进程互斥关系不具有传递性。 进程互斥是指两个或多个进程由于竞争共享同一临界资源而产生的制约关系。

• 进程 A 与进程 B 互斥，是因为它们共享变量 1；
• 进程 B 与进程 C 互斥，是因为它们共享变量 2。 如果进程 A 与进程 C 之间没有共享任何临界资源，它们就不需要互斥，可以并发甚至并行执行。

---

难度: ⭐⭐
考点: #进程互斥 #临界资源 #制约关系

💡 学习锦囊

📖 相关公式与知识点:

• 临界资源：一段时间内只允许一个进程访问的资源。
• 互斥：当一个进程进入临界区使用临界资源时，另一个进程必须等待。

思路分析

画出资源关系图：A -> [变量1] <- B -> [变量2] <- C。显然 A 和 C 没有交集，因此没有互斥的必要。

🔄 举一反三

1. 两个进程由于争夺同一资源而产生的制约关系被称为什么？
   查看练习答案与解析

   答案：间接制约关系（即互斥关系）。
   解析：进程间的制约关系分为直接制约（同步）和间接制约（互斥）。

4. 在单处理机上，进程就绪队列和阻塞队列都只能有一个。

查看答案与解析

答案：错误。

理由： 在实际的操作系统中，为了便于管理和提高调度效率：

• 就绪队列：可以根据优先级设立多个队列（如多级队列调度算法）。
• 阻塞队列：通常根据阻塞原因（如等待键盘输入、等待磁盘 I/O、等待网络数据等）设立多个不同的队列。如果只有一个阻塞队列，事件发生时系统需要扫描整个队列，效率极低。

---

难度: ⭐⭐
考点: #进程队列 #就绪状态 #阻塞状态

💡 学习锦囊

📖 相关公式与知识点:

• 进程的三种基本状态：就绪、执行、阻塞。
• 进程控制块（PCB）的组织方式：链接方式、索引方式。

易错点

容易受“单处理机”这一条件的迷惑，误以为队列数量也受处理机数量限制。实际上队列是软件数据结构，数量取决于设计。

🔄 举一反三

1. 进程由执行态变为阻塞态，通常是因为什么？
   查看练习答案与解析

   答案：请求某种服务、等待事件发生（如等待 I/O 完成或申请资源）。
   解析：这是进程的主动行为。

5. 一个作业从进入系统到运行结束需要经历后备、就绪和完成 3 种状态。

查看答案与解析

答案：错误。

理由： 这里混淆了作业状态与进程状态。 一个作业从提交给系统到运行结束，通常经历以下四个状态：

1. 提交状态：作业通过输入设备进入外存的过程。
2. 后备状态：作业已全部进入外存的输入井，等待作业调度。
3. 执行状态：作业被调度选中，分配内存等资源，并创建对应进程。在此状态下，其进程会经历就绪、运行、阻塞等进程状态。
4. 完成状态：作业运行结束，释放资源。

---

难度: ⭐⭐
考点: #作业状态 #进程状态 #作业管理

💡 学习锦囊

📖 相关公式与知识点:

• 作业（Job）：用户在一次解题或一个事务处理过程中，要求计算机系统所做工作的集合。
• 作业状态转换图：提交 -> 后备 -> 执行 -> 完成。

思路分析

分清概念：“就绪”是进程的状态，而“后备”是作业的状态。作业在执行状态下才包含就绪态的进程。

🔄 举一反三

1. 作业调度的主要任务是什么？
   查看练习答案与解析

   答案：从后备队列中选择作业，为其分配资源并创建进程，使其进入执行状态。
   解析：作业调度又称高级调度。

6. 分段存储管理与分页存储管理的不同点之一是，页的大小是由系统确定的，段的长度因段而异，由程序员决定。

查看答案与解析

答案：正确。

解析： 这是分页与分段存储管理的核心区别之一。

• 分页：出于系统管理的需要，将物理内存和逻辑地址空间划分为固定大小的页，大小由**硬件（系统）**决定（通常为 2 的幂次）。
• 分段：出于用户/程序员的逻辑需要（如代码段、数据段、堆栈段），段长由程序员在编写程序时根据逻辑模块决定。

---

难度: ⭐
考点: #分页管理 #分段管理 #存储管理

💡 学习锦囊

📖 相关公式与知识点:

• 分页是一维地址空间，分段是二维地址空间。
• 分页的目的是提高内存利用率，分段的目的是满足用户逻辑需求。

🔄 举一反三

1. 在段页式存储管理中，地址映射的先后顺序是怎样的？
   查看练习答案与解析

   答案：段号 -> 页号 -> 页内偏移。
   解析：先通过段表查到页表起始地址，再通过页表查到物理块号。

7. SPOOLing 技术是通过在内存中开辟一块空间作为输入井、输出井来将独占设备模拟成共享设备的技术。

查看答案与解析

答案：错误。

理由： SPOOLing（假脱机）技术中的输入井和输出井是在**外存（通常是磁盘）**上开辟的，而不是在内存中。

• 外存（磁盘）：开辟输入井和输出井，用于暂存数据。
• 内存：开辟输入缓冲区和输出缓冲区，用于缓解 CPU 与磁盘间的速度矛盾。

---

难度: ⭐⭐
考点: #SPOOLing技术 #假脱机 #输入井输出井

💡 学习锦囊

📖 相关公式与知识点:

• SPOOLing 系统的组成：输入井/输出井、输入缓冲区/输出缓冲区、预输入/缓输出程序。
• 作用：实现虚拟设备，将独占设备改造为共享设备。

易错点

“井”与“缓冲区”的存储介质容易混淆。井在磁盘，缓冲区在内存。

🔄 举一反三

1. SPOOLing 技术使得独占设备变成了什么设备？
   查看练习答案与解析

   答案：共享设备（或虚拟设备）。
   解析：多道程序可以同时向输出井写入数据，由系统统一控制打印。

8. 在文件系统中，打开文件是指创建一个文件控制块。

查看答案与解析

答案：错误。

理由： 打开文件的核心操作是：将文件在外存中的文件控制块（FCB）或索引结点拷贝到内存的打开文件表中，并返回该表项的索引（文件描述符/句柄），以便后续读写。 而创建文件才是“创建一个新的文件控制块（FCB）”并分配外存空间的操作。

---

难度: ⭐⭐
考点: #文件系统 #打开文件 #FCB

💡 学习锦囊

📖 相关公式与知识点:

• FCB 包含：文件名、物理位置、逻辑结构、存取权限等。
• 打开文件表：系统级和进程级。

思路分析

“打开”本质上是“读入内存”的缓存过程，不是“新建”。

🔄 举一反三

1. 关闭文件（Close）时，操作系统主要完成什么工作？
   查看练习答案与解析

   答案：将内存中被修改的 FCB 写回外存，并释放打开文件表中的表项。
   解析：清理打开状态。

---

二、简答题（每题 4 分，共 20 分）

1. 在进程基本状态转换图中，增加换出（将进程换出至辅存）和换入（将进程从辅存中换入至主存）两个操作。试画出进程状态转换图。

查看答案与解析

答案： 增加换入、换出操作后，进程状态转换图（包含挂起状态）如下：

graph TD
    New[新建态] -->|提交| Ready[就绪态]
    Ready -->|进程调度| Running[运行态]
    Running -->|时间片用完| Ready
    Running -->|等待事件| Blocked[阻塞态]
    Blocked -->|事件发生| Ready
    Running -->|终止| Exit[终止态]

    %% 挂起转换
    Ready -->|挂起/换出| ReadySuspend[挂起就绪态]
    ReadySuspend -->|激活/换入| Ready
    
    Blocked -->|挂起/换出| BlockedSuspend[挂起阻塞态]
    BlockedSuspend -->|激活/换入| Blocked
    
    BlockedSuspend -->|事件发生| ReadySuspend

状态转换关系说明：

1. 换出（挂起）：
   • 就绪 -> 挂起就绪：当内存紧张时，系统将就绪进程换出到外存。
   • 阻塞 -> 挂起阻塞：为了腾出内存空间，系统将处于阻塞状态的进程换出到外存。
2. 换入（激活）：
   • 挂起就绪 -> 就绪：外存进程被重新调入内存。
   • 挂起阻塞 -> 阻塞：极少发生，通常直接由外存事件触发转换为挂起就绪。
3. 事件触发：
   • 挂起阻塞 -> 挂起就绪：在外存等待事件的进程，事件发生后直接在外存转为就绪。

---

难度: ⭐⭐⭐
考点: #进程状态转换 #挂起状态 #换入换出

💡 学习锦囊

📖 相关公式与知识点:

• 进程的基本状态：就绪、执行、阻塞。
• 引入挂起的目的：满足终端用户的请求、父进程请求、操作系统负荷调节的需要、对换的需要。

思路分析

重点在于理解“挂起”状态依然保留了原有的“就绪”和“阻塞”属性。因此，挂起后的状态应分为“挂起就绪”和“挂起阻塞”，并在外存上实现状态间的迁移。

🔄 举一反三

1. 处于挂起阻塞态的进程，在其等待的事件发生后，会转换为什么状态？
   查看练习答案与解析

   答案：挂起就绪态。
   解析：因为该进程仍在辅存（外存）中，事件发生仅改变其状态属性（由阻塞变为就绪），并未换入内存。

2. 请详细说明分区式存储器管理方案三种放置策略的思想、特点及其自由主存队列的排列方式。

查看答案与解析

答案： 动态分区分配的常用放置策略有以下三种：

策略名称	核心思想	优缺点特点	自由主存队列排列方式
首次适应算法 (FF)	从头开始查找，分配第一个满足大小的空闲区。	优点：分配速度快。 缺点：低地址会产生大量碎片。	按地址递增的顺序排列。
最佳适应算法 (BF)	查找满足要求的、容量最小的空闲区分配。	优点：尽量保留了大空闲区。 缺点：会产生极难利用的外部小碎片。	按容量递增的顺序排列。
最坏适应算法 (WF)	查找满足要求的、容量最大的空闲区分配。	优点：剩余碎片较大，易于再利用。 缺点：破坏了大空闲区，大作业难以进入。	按容量递减的顺序排列。

---

难度: ⭐⭐
考点: #动态分区分配 #首次适应 #最佳适应 #最坏适应

💡 学习锦囊

📖 相关公式与知识点:

• 动态分区分配是根据作业的实际大小动态建立分区的管理方式。
• 碎片分类：内部碎片（已分配分区内未用空间）、外部碎片（未分配但太小无法使用的空间）。

易错点

容易记混队列的排列顺序：首次适应按地址，最佳/最坏按容量。

🔄 举一反三

1. 动态分区分配算法中，哪种算法通常会导致大作业无法进入系统？
   查看练习答案与解析

   答案：最坏适应算法（以及没有采用紧凑技术的最佳适应）。
   解析：最坏适应算法每次都切割最大的空闲区，最终导致系统中缺乏足够大的连续空闲空间。

3. 什么叫死锁？死锁产生的必要条件是什么？

查看答案与解析

答案： 死锁的定义： 指多个进程在运行过程中，因争夺资源而造成的一种僵局（相互等待现象）。若无外力作用，这些进程都将永远处于阻塞状态，无法向前推进。

死锁产生的四个必要条件：

1. 互斥条件：一个资源在同一时刻只能被一个进程占用。
2. 不可抢占条件：进程已获得的资源在未使用完之前，不能被强行剥夺，只能由该进程主动释放。
3. 请求和保持条件：进程至少已经保持了一个资源，但又提出了新的资源请求，而该资源正被其他进程占用，此时请求进程阻塞，但对自己已获得的资源保持不放。
4. 循环等待条件：存在一个进程——资源的环形等待链（如 $P_1$ 等 $P_2$ 的资源，$P_2$ 等 $P_1$ 的资源）。

---

难度: ⭐
考点: #死锁 #死锁必要条件

💡 学习锦囊

📖 相关公式与知识点:

• 死锁处理策略：死锁预防（破坏条件）、死锁避免（银行家算法）、死锁检测与解除。

思路分析

牢记“互不请循”四个字：互斥、不可抢占、请求保持、循环等待。

🔄 举一反三

1. 预防死锁时，通过“资源有序分配法”可以破坏死锁的哪一个必要条件？
   查看练习答案与解析

   答案：循环等待条件。
   解析：为所有资源编号，规定进程必须按编号递增的顺序请求资源，从而消除资源环路。

4. 什么叫缓冲技术？引入缓冲技术的目的是什么？

查看答案与解析

答案： 缓冲技术： 在两个速度差异较大的硬件实体（如 CPU 与 I/O 设备）之间设置一个专用的数据暂存区域（缓冲区）。

引入缓冲技术的目的：

1. 缓和矛盾：缓和 CPU 与外设之间速度极度不匹配的矛盾。
2. 减少中断：减少 CPU 响应 I/O 中断的频率，降低系统开销。
3. 提高并行性：提高 CPU 和 I/O 设备之间的并行工作程度。
4. 解决单位不匹配：解决数据传输基本单元大小（如字符流与块数据）不匹配的问题。

---

难度: ⭐⭐
考点: #缓冲技术 #I/O管理

💡 学习锦囊

📖 相关公式与知识点:

• 缓冲区类型：单缓冲、双缓冲、循环缓冲、缓冲池。
• 在块设备管理中，单缓冲的数据处理时间 $T = \max(C, T) + M$。

易错点

注意缓冲区本身并不能真正提高设备的物理传输速度，它只是通过并发处理“掩盖”了慢速设备带来的等待。

🔄 举一反三

1. 引入双缓冲后，系统处理一块数据的平均时间主要受什么限制？
   查看练习答案与解析

   答案：$\max(C, T)$。
   解析：$C$ 为 CPU 处理时间，$T$ 为 I/O 输入时间。双缓冲实现了输入和处理的完全并行。

5. 简述文件系统应具备的功能。

查看答案与解析

答案： 文件系统是操作系统中负责管理和存取文件信息的软件机构。它应具备以下核心功能：

1. 文件管理：负责文件的创建、删除、打开、关闭、读、写及修改操作。
2. 目录管理：建立和维护文件目录，实现“按名存取”，并提供目录检索。
3. 外存空间管理：负责外存空闲磁盘块的分配、回收与记录。
4. 文件共享与保护：允许多用户共享文件，并提供访问控制机制防止非法越权存取。
5. 接口提供：向程序员提供统一的系统调用接口（如 open(), write()）。

---

难度: ⭐⭐
考点: #文件系统功能 #按名存取

💡 学习锦囊

📖 相关公式与知识点:

• 文件控制块（FCB）：文件存在的唯一标志。
• 索引结点（Inode）：为了提高目录检索速度，将文件名与文件描述信息分离。

思路分析

从文件的生命周期思考：首先要“起名”（目录）、然后要“存盘”（空间）、使用时要“增删改查”（管理）、多用户时要“防盗”（保护）。

🔄 举一反三

1. 文件系统中，Inode 技术的核心优势是什么？
   查看练习答案与解析

   答案：减小了目录项的体积，使得一个磁盘块能容纳更多目录项，从而显著减少检索文件时读取磁盘的次数。

---

三、计算分析题（共计 44分）

1. （8 分）设某作业占有 7 个页面，如果在主存中只允许装入 4 个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是 1， 2， 3， 6， 4， 7， 3， 2， 1， 4，7， 5， 6， 5， 2， 1。假设开始的 4 个页面已装入主存。 (1) 若试用 FIFO 页面调度算法，列出各自的页面淘汰顺序 and 缺页中断次数，以及最后留驻主存 4 页的顺序。
   (2) 若用 LRU 页面调度算法，列出各自的页面淘汰顺序 and 缺页中断次数，以及最后留驻主存 4 页的顺序。

查看答案与解析

答案：

(1) FIFO（先进先出）算法

• 淘汰顺序：1, 2, 3, 6, 4, 7
• 缺页中断次数：6 次（初始 4 页已装入，不计入缺页）
• 最后留驻主存的 4 页顺序：2, 1, 5, 6

推导过程： 初始状态（进入顺序）：1, 2, 3, 6

访问页面	状态(进入顺序)	是否缺页	淘汰页面
4	2, 3, 6, 4	是	1
7	3, 6, 4, 7	是	2
3	3, 6, 4, 7	否	-
2	6, 4, 7, 2	是	3
1	4, 7, 2, 1	是	6
4	4, 7, 2, 1	否	-
7	4, 7, 2, 1	否	-
5	7, 2, 1, 5	是	4
6	2, 1, 5, 6	是	7
5	2, 1, 5, 6	否	-
2	2, 1, 5, 6	否	-
1	2, 1, 5, 6	否	-

---

(2) LRU（最近最久未使用）算法

• 淘汰顺序：1, 2, 6, 4, 7, 3, 2, 1, 4, 7
• 缺页中断次数：10 次
• 最后留驻主存的 4 页顺序：6, 5, 2, 1

推导过程： 初始状态（访问栈，右侧为最近访问）：1, 2, 3, 6

访问页面	状态(左旧右新)	是否缺页	淘汰页面
4	2, 3, 6, 4	是	1
7	3, 6, 4, 7	是	2
3	6, 4, 7, 3	否	-
2	4, 7, 3, 2	是	6
1	7, 3, 2, 1	是	4
4	3, 2, 1, 4	是	7
7	2, 1, 4, 7	是	3
5	1, 4, 7, 5	是	2
6	4, 7, 5, 6	是	1
5	4, 7, 6, 5	否	-
2	7, 6, 5, 2	是	4
1	6, 5, 2, 1	是	7

---

难度: ⭐⭐⭐
考点: #页面置换算法 #FIFO #LRU

💡 学习锦囊

📖 相关公式与知识点:

• FIFO：淘汰在内存中驻留时间最长的页面。
• LRU：淘汰最近最久未被访问的页面。

易错点

在 LRU 算法中，每次“命中”都需要更新页面的访问时间（即在访问栈中移到最右侧）。

🔄 举一反三

1. 什么是 Belady 异常？哪种算法会出现此异常？
   查看练习答案与解析

   答案：分配的物理块数增加，缺页率反而上升的异常现象。FIFO 算法会出现，而 LRU（属于堆栈类算法）绝不会出现。

2. （10 分）系统中有 3 种类型的资源（A,B,C,）和 5 个进程 P1,P2,P3,P4,P5,A 资源总数为 10，B为 8，C 为 8，在 T0 时刻系统状态如下表。系统采用银行家算法实施死锁避免策略。试问： | 进程 | 最大需求 (A, B, C) | 已分配 (A, B, C) | | :--- | :--- | :--- | | P1 | (7, 7, 3) | (0, 2, 0) | | P2 | (3, 3, 4) | (2, 1, 0) | | P3 | (9, 1, 2) | (3, 0, 2) | | P4 | (2, 3, 3) | (2, 1, 2) | | P5 | (4, 3, 4) | (0, 1, 2) | （1） $T_0$ 时刻此系统是否安全，若是，给出一个安全序列。
   （2）此时若进程 P2请求资源（1，1，0），是否能实施资源分配，为什么？
   （3）在此基础上，若进程 P1请求资源（2，0，1），能否实施资源分配，为什么？

查看答案与解析

答案与解析：

首先计算 $T_0$ 时刻的剩余可用资源 $Available$ 和各进程的剩余需求 $Need$。

• $Allocated\_Total = (7, 5, 6)$
• $Available = Total - Allocated\_Total = (10-7, 8-5, 8-6) = (3, 3, 2)$
• $Need = Max - Allocated$，计算得下表： | 进程 | Need (A, B, C) | | :--- | :--- | | P1 | (7, 5, 3) | | P2 | (1, 2, 4) | | P3 | (6, 1, 0) | | P4 | (0, 2, 1) | | P5 | (4, 2, 2) |

(1) 安全性检查 目前 $Available = (3, 3, 2)$。

1. $P_4$ 的 $Need(0,2,1) \le (3,3,2)$，分配后 $P_4$ 执行完毕，$Available = (3,3,2) + (2,1,2) = (5,4,4)$。
2. $P_2$ 的 $Need(1,2,4) \le (5,4,4)$，分配后 $P_2$ 执行完毕，$Available = (5,4,4) + (2,1,0) = (7,5,4)$。
3. $P_1$ 的 $Need(7,5,3) \le (7,5,4)$，分配后 $P_1$ 执行完毕，$Available = (7,5,4) + (0,2,0) = (7,7,4)$。
4. $P_3$ 的 $Need(6,1,0) \le (7,7,4)$，分配后 $P_3$ 执行完毕，$Available = (7,7,4) + (3,0,2) = (10,7,6)$。
5. $P_5$ 的 $Need(4,2,2) \le (10,7,6)$，分配后 $P_5$ 执行完毕。 结论：系统安全，存在安全序列 $P_4 \to P_2 \to P_1 \to P_3 \to P_5$。

(2) $P_2$ 发出 Request(1, 1, 0)

1. 检查：$Request(1,1,0) \le Need_2(1,2,4)$ 且 $Request(1,1,0) \le Available(3,3,2)$。
2. 试探分配：
   • $Available = (2, 2, 2)$
   • $Allocation_2 = (3, 2, 0)$
   • $Need_2 = (0, 1, 4)$
3. 安全性检查：使用新的 $Available=(2,2,2)$ 进行推导，可得安全序列仍为 $P_4 \to P_2 \to P_1 \to P_3 \to P_5$。 结论：可以实施分配。

(3) 在(2)基础上，$P_1$ 发出 Request(2, 0, 1)

1. 检查：$Request(2,0,1) \le Need_1(7,5,3)$ 且 $Request(2,0,1) \le Available(2,2,2)$。
2. 试探分配：
   • $Available = (0, 2, 1)$
   • $Allocation_1 = (2, 2, 1)$
   • $Need_1 = (5, 5, 2)$
3. 安全性检查：此时 $Available=(0,2,1)$。
   • 仅 $P_4$ 的 $Need(0,2,1) \le Available$。$P_4$ 执行完后 $Available = (0,2,1) + (2,1,2) = (2,3,3)$。
   • 此时剩余进程 $Need$ 均大于 $(2,3,3)$，系统进入不安全状态。 结论：不能分配。

---

难度: ⭐⭐⭐
考点: #银行家算法 #死锁避免 #安全性检查

💡 学习锦囊

思路分析

做题三步走：1. 算 Need 和 Avail；2. 查资源够不够（Request <= Need 且 Request <= Avail）；3. 试探分配并跑安全性算法找序列。

🔄 举一反三

1. 处于不安全状态的系统一定会发生死锁吗？
   查看练习答案与解析

   答案：不一定。
   解析：不安全状态只是意味着“有发生死锁的危险”。如果进程后续不提出最大需求请求，死锁就不会发生。

3. （9分）多道程序系统中，供用户使用的内存空间有 100KB，磁带机 2台，打印机 1 台。系统采用可变式分区分配方式管理内存，对磁带机和打印机采用静态分配方式。现有作业序列： | 作业号 | 到达时间 | 要求计算时间 | 要求内存 | 磁带机 | 打印机 | | :--- | :--- | :--- | :--- | :--- | :--- | | 1 | 8:00 | 25分 | 15K | 1台 | 1台 | | 2 | 8:20 | 10分 | 30K | - | 1台 | | 3 | 8:20 | 20分 | 60K | 1台 | - | | 4 | 8:30 | 20分 | 20K | 1台 | - | | 5 | 8:35 | 15分 | 10K | 1台 | 1台 | 假设调度采用 FCFS，优先分配内存低地址，不准移动。试问：调度的次序和所有作业的周转时间。

查看答案与解析

答案：

• 作业调度次序：1 -> 3 -> 2 -> 4 -> 5
• 各作业周转时间：
  • 作业 1：30 分钟 ($8:30 - 8:00$)
  • 作业 2：30 分钟 ($8:50 - 8:20$)
  • 作业 3：40 分钟 ($9:00 - 8:20$)
  • 作业 4：60 分钟 ($9:30 - 8:30$)
  • 作业 5：55 分钟 ($9:30 - 8:35$)

详细推导过程（时间线）：

• 8:00：作业 1 到达，申请 15K, 1T, 1P。系统满足，作业 1 进入内存运行。剩余：85K, 1T, 0P。
• 8:20：作业 2、3 到达。作业 2 缺打印机等待；作业 3 满足（60K<=85K, 1T<=1T）进入内存。此时内存有作业 1、3，平分 CPU。
• 8:30：作业 1 完成（在 8:20 前独占消耗 20m，8:20 后并发 10m 消耗 5m，共 25m）。释放资源，可用：40K, 1T, 1P。作业 2 资源满足进入内存，作业 4 到达但内存（20K>10K）不足等待。内存有作业 3、2，平分 CPU。
• 8:50：作业 2 完成（消耗 10m）。作业 3 在 8:30-8:50 消耗了 10m（累计 15m）。可用：40K, 1T, 1P。作业 4 满足进入内存。内存有作业 3、4，平分 CPU。
• 9:00：作业 3 消耗完最后的 5m 计算量，完成！释放资源。作业 5 满足进入内存。内存有作业 4、5，平分 CPU。
• 9:30：作业 4、5 分别消耗完 15m 计算量，同时完成！

---

难度: ⭐⭐⭐
考点: #作业调度 #FCFS #并发执行 #平分CPU

💡 学习锦囊

📖 相关公式与知识点:

• 周转时间 = 完成时间 - 到达时间。
• 带权周转时间 = $\frac{\text{周转时间}}{\text{要求服务时间}}$。

思路分析

“平分 CPU”意味着如果有 $N$ 个作业在内存中，它们每分钟只能获得 $\frac{1}{N}$ 分钟的 CPU 时间。推导时建议画出甘特图。

🔄 举一反三

1. 若在 8:30 作业 1 完成后，有新的短作业 6（5m，无设备要求）到达，在 FCFS 策略下它和作业 4 谁先被调度？
   查看练习答案与解析

   答案：作业 4。
   解析：FCFS（先来先服务）严格按照到达时间排序。作业 4 在 8:30 到达，早于作业 6，因此优先进入内存。

4. （9分）在请求分页系统中，某用户程序的逻辑地址空间为16页，每页1KB，分配的内存空间为8KB。假定某时刻该用户的页表如下。 | 页号 | 块号 | | :--- | :--- | | 0 | 3 | | 1 | 7 | | 2 | 4 | | 3 | 1 | | 4 | 12 | | 5 | 9 | | 6 | 61 | | 7 | 20 | 试问：逻辑地址 184BH 对应的物理地址；5000 对应的物理地址；访问 24A0H 会出现什么现象。

查看答案与解析

答案：

1. 184BH 对应的物理地址：F44BH
2. 5000 对应的物理地址：13192
3. 访问 24A0H：会产生缺页中断。

解析： 页大小为 $1\text{KB} = 1024\text{B} = 400\text{H}$。

1. 184BH：$184\text{B}\text{H} / 400\text{H} = 6$ 页，余 $4\text{B}\text{H}$。页号为 6，查表得块号 61（$3\text{D}\text{H}$）。物理地址 = $3\text{D}\text{H} \times 400\text{H} + 4\text{B}\text{H} = \text{F}44\text{B}\text{H}$。
2. 5000：$5000 / 1024 = 4$ 页，余 904。页号为 4，查表得块号 12。物理地址 = $12 \times 1024 + 904 = 13192$。
3. 24A0H：$24\text{A}0\text{H} / 400\text{H} = 9$ 页。查页表发现无 9 号页记录，故缺页。

---

难度: ⭐⭐
考点: #请求分页 #地址转换 #物理地址

💡 学习锦囊

📖 相关公式与知识点:

• 物理地址 = 块号 $\times$ 块大小 + 页内偏移。
• $1\text{KB} = 2^{10}\text{B}$，在十六进制中为 $400\text{H}$。

思路分析

十六进制地址转换技巧：页长为 $400\text{H}$ 时，逻辑地址的后三位十六进制数即为页内偏移，前面的数即为页号。

🔄 举一反三

1. 已知某页式存储管理系统的物理地址为 3B20H，页大小为 4KB，该地址对应的页内偏移是多少？
   查看练习答案与解析

   答案：B20H。
   解析：$4\text{KB} = 4096\text{B} = 1000\text{H}$。因此物理地址的后三位十六进制数（B20H）直接对应页内偏移。

5. （8 分）系统盘块大小为 512B，盘块编号长 4B，文件说明中可存放 10 个盘块编号。关于文件大小有如下统计结果：

• 文件大小≤512B 占 $40\%$
• 512B < 文件大小≤3KB 占 $30\%$
• 3KB < 文件大小≤64KB 占 $20\%$
• 64KB < 文件大小≤192KB 占 $8\%$
• 192KB < 文件大小 $\leqslant$ 8MB 占 $2\%$ 试为该系统设计文件的物理结构，并计算其平均访问磁盘次数。

查看答案与解析

答案： 物理结构设计： 采用混合索引结构。文件说明中的 10 个盘块号作如下分配：

• 直接索引：6 个，可寻址 $6 \times 512\text{B} = 3\text{KB}$ 空间。
• 一级间接索引：3 个。每个盘块可存放 $512 / 4 = 128$ 个块号，共寻址 $3 \times 128 \times 512\text{B} = 192\text{KB}$ 空间。
• 二级间接索引：1 个。可寻址 $1 \times 128 \times 128 \times 512\text{B} = 8\text{MB}$ 空间。

平均访问磁盘次数计算：

• 当文件大小 $\le 3\text{KB}$（占 $40\% + 30\% = 70\%$）时，通过直接索引访问，需 1 次磁盘 I/O。
• 当 $3\text{KB} < \text{大小} \le 192\text{KB}$（占 $20\% + 8\% = 28\%$）时，通过一级间接访问，需 2 次磁盘 I/O。
• 当大小 $> 192\text{KB}$（占 $2\%$）时，通过二级间接访问，需 3 次磁盘 I/O。

平均访问次数 = $0.70 \times 1 + 0.28 \times 2 + 0.02 \times 3 = \mathbf{1.32}$ 次。

---

难度: ⭐⭐⭐
考点: #文件索引结构 #平均访问次数

💡 学习锦囊

📖 相关公式与知识点:

• 直接寻址范围 = 直接块号数 $\times$ 盘块大小。
• 一级间接范围 = 一级块号数 $\times$ (盘块大小/地址项大小) $\times$ 盘块大小。

思路分析

混合索引设计必须对齐题目给出的统计分界线。本题中 3KB 和 192KB 是关键的拐点。

🔄 举一反三

1. 若盘块大小改为 1KB，地址项长为 4B，一个盘块可存放多少个盘块号？
   查看练习答案与解析

   答案：256 个。
   解析：$1\text{KB} = 1024\text{B}$，地址项 4B，则一个盘块可存放 $\frac{1024}{4} = 256$ 个盘块号。

---

四、应用题（共计 12分）

1. 有三个进程 PA、PB 和 PC 协作解决文件打印问题：PA 将文件记录从磁盘读入主存的缓冲区 1，每执行一次读一个记录；PB 将缓冲区 1的记录复制到缓冲区 2，每执行一次复制一个记录；PC 将缓冲区 2 的内容打印出来，每执行一次打印一个记录。缓冲区的大小和一个记录大小一样。试用 P、V操作来保证文件的正确打印。

查看答案与解析

答案： 本题属于多级生产者-消费者问题。

• 进程 $P_A$ 是缓冲区 $B_1$ 的生产者。
• 进程 $P_B$ 是缓冲区 $B_1$ 的消费者，同时是缓冲区 $B_2$ 的生产者。
• 进程 $P_C$ 是缓冲区 $B_2$ 的消费者。

1. 信号量设置：

• empty1：表示缓冲区 $B_1$ 是否为空，初值为 1。
• full1：表示缓冲区 $B_1$ 是否有数据，初值为 0。
• empty2：表示缓冲区 $B_2$ 是否为空，初值为 1。
• full2：表示缓冲区 $B_2$ 是否有数据，初值为 0。

2. 伪代码实现：

semaphore empty1 = 1; // B1 的空位数
semaphore full1  = 0; // B1 的产品数
semaphore empty2 = 1; // B2 的空位数
semaphore full2  = 0; // B2 的产品数

void PA() {
    while(1) {
        从磁盘读取一个文件记录;
        
        P(&empty1);      // 申请 B1 的空位
        将记录存入 B1;
        V(&full1);       // 释放 B1 的数据信号
    }
}

void PB() {
    while(1) {
        P(&full1);       // 检查 B1 是否有数据
        从 B1 中取出记录;
        V(&empty1);      // 释放 B1 的空位

        P(&empty2);      // 申请 B2 的空位
        将记录复制到 B2;
        V(&full2);       // 释放 B2 的数据信号
    }
}

void PC() {
    while(1) {
        P(&full2);       // 检查 B2 是否有数据
        从 B2 中取出记录并打印;
        V(&empty2);      // 释放 B2 的空位
    }
}

---

难度: ⭐⭐⭐
考点: #PV操作 #进程同步与互斥 #生产者消费者问题

💡 学习锦囊

📖 相关公式与知识点:

• P 操作（wait）：使信号量减 1，若 $<0$ 则进程阻塞。
• V 操作（signal）：使信号量加 1，若 $\le 0$ 则唤醒阻塞进程。

思路分析

理清数据流向：磁盘 -> B1 -> B2 -> 打印机。每经过一个缓冲区，都涉及一次“空位申请（P(empty)）”和“数据填充（V(full)）”。

🔄 举一反三

1. 若缓冲区 $B_1$ 的大小可以存放 $N$ 个记录，初始信号量应如何修改？
   查看练习答案与解析

   答案：只需将 semaphore empty1 = 1; 修改为 semaphore empty1 = N; 即可。