基础知识

1. 对比分析系统调用与一般用户程序及库函数的区别。

系统调用 (System Call)：运行在内核态，通过类似硬件中断的“陷入机制（Trap）”向操作系统内核请求服务。目的是让用户程序能安全、受控地使用硬件资源。

用户程序 (User Program)：运行在用户态，执行普通指令，不能直接访问硬件。

库函数 (Library Function)：是将常用功能封装好的代码集合（如 printf），在编译阶段链接到程序中。库函数内部可能会调用系统调用，也可能不调用。

2. 简述引导程序（Bootloader）两个阶段的主要任务。

第一阶段：主要负责硬件初始化（如关闭中断、初始化CPU），设置堆栈，并将第二阶段的代码从存储介质复制到 RAM 中。

第二阶段：负责检测系统内存映像，将内核映像和根文件系统映像读入 RAM，设置内核启动参数，最后调用内核。

3. 论述进程与程序的区别与联系。

区别：

• 进程是动态的，强调执行过程，是资源分配和独立运行的基本单位。
• 程序是静态的，是一组指令的集合，存储在磁盘上。

联系：进程是程序的执行实例，一个程序可以对应多个进程（例如打开了三个浏览器窗口）。

4. 深入分析引入线程的原因及其与进程的区别。

引入原因：为了减少并发执行时的时空开销（如进程间切换的上下文开销），提高系统的并发性和 CPU 利用率。

区别：

• 进程：是资源分配的基本单位，拥有独立的地址空间。
• 线程：是处理机调度（CPU执行）的基本单位。线程与同属一个进程的其他线程共享资源（如内存、文件），自身只拥有极少的资源（如栈、寄存器）。

5. 死锁产生的必要条件有哪些？并说明如何通过途径“预防”死锁。

4个必要条件：

1. 互斥（资源独占）。
2. 不剥夺（已获资源不能被强行抢占）。
3. 请求和保持（吃着碗里的，看着锅里的）。
4. 环路等待（A等B，B等C，C等A）。

预防途径：

• 破坏“请求和保持”：实行资源一次性分配。
• 破坏“不剥夺”：当新请求未满足时，释放已占有的资源。
• 破坏“环路等待”：对资源进行编号，必须按顺序申请。

6. 简述死锁避免（Avoidance）与死锁预防（Prevention）的区别。

死锁预防：是静态策略。通过严格限制进程请求资源的规则，确保存储的必要条件永远不满足。

死锁避免：是动态策略。在分配资源前，系统根据当前情况预测未来是否安全（如银行家算法），确保系统始终处于“安全状态”。

7. 对比分页（Paging）与分段（Segmentation）存储管理方式。

分页：是物理单位。目的是提高内存利用率（减少碎片），页大小固定由系统决定，地址空间是一维的。

分段：是逻辑单位。包含完整的逻辑信息（如代码段、数据段），段长度不固定由用户/编译器决定，地址空间是二维的（段号+段内偏移）。

8. 解释“抖动”现象及其产生原因

现象：系统花费大量时间在页面置换（换入换出）上，而不是执行程序指令。

原因：在请求页式存储管理中，页面淘汰算法选择不当，或者进程分配的物理块太少，导致刚换出的页面马上又要被访问（换入）。

9. 比较中断控制方式、DMA方式与通道方式的区别。

中断控制：以字节为单位传输，数据传输需要 CPU 频繁干预（每传一个字节都要打断 CPU）。

DMA方式 (直接存储器访问)：以数据块为单位传输，仅在传输开始和结束时需要 CPU 干预，中间过程由 DMA 控制器完成，效率较高。

通道方式：拥有独立的通道指令（类似一个小 CPU），能控制一组数据块的传输，最大程度减轻了 CPU 的负担，但硬件成本最高。

10. 请从交互性、及时性以及可靠性三个维度，深入比较分析分时系统与实时系统的差异。

• 及时性： 分时系统以人能接受的等待时间为准；而实时系统则严格受限于控制对象所要求的开始或完成截止时间，通常在秒级、毫秒级甚至微秒级。

• 交互性： 分时系统提供通用的资源共享和多用户交互；实时系统的交互通常仅限于访问特定的专用服务程序。

• 可靠性： 实时系统要求极高的可靠性，通常采取多级容错和冗余措施，因为任何差错都可能导致灾难性后果，而分时系统的要求相对较低

11. PCB的作用与状态转换

PCB 的作用：

• PCB (Process Control Block) 是进程存在的唯一标志。
• 它记录了进程的描述信息、控制信息及资源信息，是操作系统感知和管理进程的实体数据结构。

“就绪 $\rightarrow$ 运行”的处理过程：

1. 状态修改：操作系统将该进程 PCB 中的状态字段从“就绪态”修改为“运行态”。

2. 队列操作：将该 PCB 从就绪队列中摘除。

3. 恢复现场：利用 PCB 中保存的 CPU 现场信息（如通用寄存器、程序计数器 PC、栈指针等）来装配硬件环境，将 CPU 的控制权正式移交给该进程。

4. HRN算法的综合平衡逻辑

对比分析高响应比优先（HRN）调度算法是如何平衡先来先服务（FCFS）与短作业优先（SJF）算法缺点的？

• 平衡原理：

  • FCFS 的缺点：只看等待时间，对短作业不公平。
  • SJF 的缺点：只看执行时间，可能导致长作业“饥饿”（永远得不到调度）。

• 响应比公式：

  $$R = \frac{W + T}{T} = 1 + \frac{W}{T}$$

  • 其中：$W$ 为等待时间，$T$ 为要求服务时间（执行时间）。

• 逻辑优势：

  • 体现 SJF：当等待时间 $W$ 相同时，要求服务时间 $T$ 越短，响应比 $R$ 越大（短作业优先）。
  • 体现 FCFS：当要求服务时间 $T$ 相同时，等待时间 $W$ 越久，响应比 $R$ 越大（先来先服务）。
  • 避免饥饿：对于长作业，虽然 $T$ 很大，但随着等待时间 $W$ 的不断增加，其响应比 $R$ 也会逐渐升高，最终获得 CPU 执行权。

13. 解释设备独立性（Device Independence）的基本含义，并说明操作系统是如何实现这一特性的。

基本含义：

• 应用程序独立于具体使用的物理设备。
• 用户在编程时使用逻辑设备名（如 /dev/printer）来请求使用设备，而不需要关注具体的物理设备名（如具体的端口地址或硬件 ID）。

实现方式：

• 逻辑映射：操作系统通过引入“逻辑设备表（LUT）”来进行两层映射。
• 统一接口：系统在设备驱动程序之上设置了一层与硬件无关的软件接口。当用户发出 I/O 请求时，系统查表将逻辑设备名转换为对应的物理设备驱动程序入口地址，从而完成实际操作。

14. 设计现代操作系统的四个主要目标

方便性 (Convenience)

• 含义： 通过提供友好的用户界面（GUI 或 CLI）和编程接口（API），屏蔽底层硬件细节，使计算机系统易于使用和编程。

有效性 (Efficiency)

• 含义： 优化资源管理（CPU、内存、I/O），提高系统的吞吐量和资源利用率，减少空闲等待时间。

健壮性/可靠性 (Robustness/Reliability)

• 含义： 系统在出现错误（如硬件故障、程序崩溃）时能保持稳定，不导致整个系统瘫痪，并能准确处理异常。

可扩展性 (Extensibility)

• 含义： 适应硬件和软件的发展，方便添加新功能、新设备驱动或进行系统升级，而无需重写内核。

15. 操作系统的异步性及其潜在问题

什么是异步性？ 在多道程序环境下，允许多个进程并发执行。由于资源竞争（如等待 I/O、时间片耗尽）和中断机制，进程的执行不是一气呵成的，而是以**“走走停停”**的方式推进。

• 核心特征： 进程以不可预知的速度向前推进，不知道何时开始、何时暂停、何时结束。

引发的问题： 如果缺乏正确的同步互斥机制，异步性会导致：

• 结果不可再现性： 相同的程序、相同的输入，多次运行可能得到不同的结果。
• 竞态条件 (Race Condition)： 多个进程同时读写共享数据，导致数据混乱或逻辑错误。

16. 简述 P、V 原语和加锁法实现进程间互斥的区别

(1) 适用范围与功能

• 加锁法 (Locking):
  • 功能单一： 主要用于实现互斥 (Mutual Exclusion)。即“一把钥匙开一把锁”，强调对临界资源的独占权。
  • 语义： “上锁”表示占有，“开锁”表示释放。
• P、V 原语 (Semaphores):
  • 功能强大： 不仅能实现互斥，还能实现进程同步 (Synchronization) 和 前趋关系。
  • 语义： 基于资源计数（信号量 $S$）。$P$ 操作表示申请资源（或等待信号），$V$ 操作表示释放资源（或发送信号）。当 $S$ 初始化为 1 时，它等同于互斥锁；当 $S > 1$ 时，它管理资源池。

(2) 等待机制 (Waiting Mechanism)

• 加锁法 (尤其是硬件指令实现的自旋锁):
  • 通常采用**“忙等” (Busy Waiting)** 策略。当进程无法获取锁时，它会在 CPU 上不断循环测试锁的状态，浪费 CPU 时间周期（虽现代 OS 的软件 Mutex 已优化为阻塞，但“加锁法”原始概念多指忙等）。
• P、V 原语:
  • 采用**“阻塞/唤醒” (Block/Wakeup)** 策略。当执行 $P$ 操作发现资源不足（$S < 0$）时，进程会主动放弃 CPU，进入等待队列，状态由运行转为阻塞。当其他进程执行 $V$ 操作释放资源时，再将其唤醒。这有效提高了 CPU 利用率。

(3) 复杂性与普适性

• 加锁法： 实现简单，常用于多处理器低层级的互斥，或作为实现 P、V 原语的基础工具。
• P、V 原语： 是更高层级的抽象机制，逻辑更严密，适用于各种复杂的并发场景。

17. 介绍存储器有关概念

• (1) 逻辑地址 (Logical Address)

  • 定义： 也称为相对地址或虚地址。是指用户程序经过编译、链接后生成的指令和数据地址。
  • 特点： 地址通常从 0 开始编址。它是 CPU 在执行程序时生成的地址，用户编程时看到的也是这个地址，并不代表数据在内存中的真实位置。

  (2) 物理地址 (Physical Address)

  • 定义： 也称为绝对地址或实地址。是数据在内存（RAM）中实际存储的单元地址。
  • 特点： 它是地址总线上实际传输的信号，内存单元直接通过该地址进行读写操作。

  (3) 重定位 (Relocation)

  • 定义： 系统将逻辑地址转换为物理地址的过程，称为重定位（或地址映射）。
  • 作用： 连接了程序视图（逻辑空间）和硬件视图（物理空间），确保程序能在内存的任意位置正确运行。

  (4) 静态重定位 (Static Relocation)

  • 定义： 在程序装入内存时（Load Time），由装入程序一次性将指令中的逻辑地址修改为物理地址。
  • 特点：
    • 时机： 运行前（装入时）。
    • 限制： 程序一旦装入内存，在运行期间不能移动位置；也难以实现虚拟内存或共享内存。
    • 硬件要求： 无需特定的硬件地址转换机构支持。

  (5) 动态重定位 (Dynamic Relocation)

  • 定义： 在程序执行期间（Run Time），每次访问内存指令时，才将逻辑地址转换为物理地址。
  • 特点：
    • 时机： 运行时（逐条指令执行时）。
    • 优势： 程序在内存中可以移动（如内存紧缩）；支持虚拟存储器；有利于程序段的共享。
    • 硬件要求： 需要硬件支持，通常由 CPU 中的 MMU (内存管理单元) 和 重定位寄存器 完成。

17. 数据传送控制方式有哪几种? 试比较它们各自的优缺点。

18. 何谓逻辑文件？何谓物理文件？

(1) 逻辑文件 (Logical File)

• 定义： 是指用户（或程序员）所看到的文件组织形式。它不考虑文件实际存储在什么介质上，而是关注文件内部的数据逻辑结构。
• 特点：
  • 从用户角度看，文件是连续的字符流（流式文件）或记录的集合（记录式文件）。
  • 逻辑地址通常是从 0 开始编号的连续空间。
  • 目的： 方便用户编程和检索数据，屏蔽硬件细节。

(2) 物理文件 (Physical File)

• 定义： 是指文件在存储介质（如磁盘、磁带）上的实际存放形式。也称为文件的存储结构。
• 特点：
  • 数据通常被划分为一个个**物理块（Block）**存储。
  • 在磁盘上可能是不连续存放的。常见的物理结构包括：顺序结构（连续分配）、链接结构（链式分配）和索引结构（索引分配）。
  • 目的： 提高存储空间的利用率和系统的读写性能。

专家点拨： 操作系统文件系统的核心功能之一，就是实现从“逻辑文件”到“物理文件”的映射（Mapping），让用户可以使用简单的逻辑地址访问分散在磁盘各处的物理数据。

计算

1.银行家算法

1. 梳理关系，列出需求矩阵：$Need_{ij} = Max_{ij} - Allocation_{ij}$

2. 安全性检查：

   即寻找一个进程 $P_i$，满足 $Need_i \le Work$（当前可用资源）。

   如果满足：

   1. 假定系统将资源分配给 $P_i$。
   2. $P_i$ 执行结束，释放其占用的所有资源：$Work = Work + Allocation_i$。
   3. 标记 $P_i$ 为 Finish，继续寻找下一个进程。

比如：

题目： 假定系统中有5个进程 {P0,P1,P2,P3,P4} 和3类资源 {A,B,C}，各类资源总数分别为 10,5,7。某时刻资源分配情况如下：

• Max（最大需求）： P0(7,5,3),P1(3,2,2),P2(9,0,2),P3(2,2,2),P4(4,3,3)。

• Allocation（已分配）： P0(0,1,0),P1(2,0,0),P2(3,0,2),P3(2,1,1),P4(0,0,2)。

• Available（可用）： (3,3,2)。

要求：

1. 计算 Need（尚需） 矩阵。

2. 判断当前状态是否安全。如果安全，请给出一个安全序列。

第一步：扫描所有进程

• 检查 $P_0$: Need $(7,4,3) \le (3,3,2)$? $\to$ False (资源不足)
• 检查 $P_1$: Need $(1,2,2) \le (3,3,2)$? $\to$ True (资源足够)
  • 执行 $P_1$。
  • $P_1$ 释放资源: Work = $(3,3,2) + (2,0,0) = (5,3,2)$
  • 当前安全序列: $<P_1>$

第二步：基于新 Work $(5,3,2)$ 继续扫描

• 检查 $P_2$: Need $(6,0,0) \le (5,3,2)$? $\to$ False (A资源不足: $6>5$)
• 检查 $P_3$: Need $(0,1,1) \le (5,3,2)$? $\to$ True
  • 执行 $P_3$。
  • $P_3$ 释放资源: Work = $(5,3,2) + (2,1,1) = (7,4,3)$
  • 当前安全序列: $<P_1, P_3>$

第三步：基于新 Work $(7,4,3)$ 继续扫描

• 检查 $P_4$: Need $(4,3,1) \le (7,4,3)$? $\to$ True
  • 执行 $P_4$。
  • $P_4$ 释放资源: Work = $(7,4,3) + (0,0,2) = (7,4,5)$
  • 当前安全序列: $<P_1, P_3, P_4>$

第四步：基于新 Work $(7,4,5)$ 扫描剩余进程 ($P_0, P_2$)

• 检查 $P_2$: Need $(6,0,0) \le (7,4,5)$? $\to$ True (此时A资源已足够)
  • 执行 $P_2$。
  • $P_2$ 释放资源: Work = $(7,4,5) + (3,0,2) = (10,4,7)$
  • 当前安全序列: $<P_1, P_3, P_4, P_2>$

第五步：基于新 Work $(10,4,7)$ 扫描剩余进程 ($P_0$)

• 检查 $P_0$: Need $(7,4,3) \le (10,4,7)$? $\to$ True
  • 执行 $P_0$。
  • $P_0$ 释放资源: Work = $(10,4,7) + (0,1,0) = (10,5,7)$
  • 当前安全序列: $<P_1, P_3, P_4, P_2, P_0>$

注：最终回收的资源总量 $(10,5,7)$ 等于系统资源总数，计算无误。

1. 安全序列： 存在多个合法的安全序列，经过上述推演，其中一个有效的安全序列为：

   $$< P_1, P_3, P_4, P_2, P_0 >$$

(备注：在第四步时，资源也满足 $P_0$，因此 $<P_1, P_3, P_4, P_0, P_2>$ 也是一个合法的安全序列。)

已知系统 Availability 为 (2, 0, 2, 2)，进程 P2 此时发出请求 Request(1, 0, 1, 0)。 要求：

1. 判断系统是否能立刻满足 P2 的请求。

2. 若分配后系统剩余资源为 (1, 0, 1, 2)，通过安全性算法检查分配后是否存在安全序列。

解析核心： 必须满足 Reques**t≤Available 且 Reques**t≤Need，分配后必须仍处于安全状态

2.处理器调度算法

题目： 现有5个作业在时刻0按 1,2,3,4,5 的顺序到达。

• 作业 1： 执行时间 10，优先级 3。

• 作业 2： 执行时间 1，优先级 1（优先级1最高）。

• 作业 3： 执行时间 2，优先级 3。

• 作业 4： 执行时间 1，优先级 4。

• 作业 5： 执行时间 5，优先级 2。

要求： 计算在 FCFS（先来先服务） 和 SJF（最短作业优先） 算法下的平均周转时间

• FCFS： 按 1→2→3→4→5 执行，平均周转时间为 (10+11+13+14+19)/5=13.4。

• SJF： 按执行时间排序 2(1)→4(1)→3(2)→5(5)→1(10)，平均周转时间为 7

3.页面置换算法

假定分配给某进程的物理块数为 3。页面引用序列为：4-3-2-1-4-3-5-4-3-2-1-5。 要求： 分别计算使用 FIFO（先进先出） 和 LRU（最近最久未使用） 算法时的缺页次数和缺页率

$$缺页率 = \frac{缺页次数}{总访问次数} \times 100%$$

FIFO:

缺页率: $\frac{9}{12} \times 100% = \mathbf{75%}$

LRU:

缺页率: $\frac{10}{12} \times 100% \approx \mathbf{83.3%}$

然后这种题目还有一个扩展。

4.磁盘调度

磁头当前位于 345 磁道，正向 0 磁道移动。请求队列为：123, 874, 692, 475, 105, 376。 要求： 计算使用 SSTF（最短寻找时间优先） 算法时的总寻道长度

• SSTF： 每次选择离当前磁头最近的磁道。

• 移动次序为：345→376→475→692→874→123→105

1. 阶段 1 (向增大方向): 从 345 一路走到 874。
   • 距离 = $874 - 345 = 529$
2. 阶段 2 (向减小方向): 从 874 一路折返走到 105。
   • 距离 = $874 - 105 = 769$

总距离：

$$529 + 769 = 1298$$

磁头当前位于 40 号柱面。磁盘请求序列为：20, 44, 40, 4, 80, 12, 76。已知每移动一个磁道耗时 3ms。 要求： 分别计算使用 SSTF（最短寻找时间优先） 和 SCAN（电梯算法，假设向磁道递增方向移动） 算法时的总寻道时间。

解析核心： SSTF 每次找最近的；SCAN 需先向一个方向移动到底再折返

5.分段存储

在一个简单分段系统中，包含如下段表：

要求： 确定以下逻辑地址对应的物理地址，或说明是否发生越界中断：

\1. (0, 198)

\2. (2, 156)

\3. (1, 530)

解析： 物理地址 = 起始地址 + 段内偏移。需检查偏移量是否小于段长度

就是进行计算，看看长度是不是能塞的下逻辑长度就行！

6.Belady 异常

假定页面引用序列为：4-3-2-1-4-3-5-4-3-2-1-5。 要求：

1. 分别计算在分配 3 个 和 4 个 物理块的情况下，使用 FIFO（先进先出） 算法的缺页率。

2. 说明该序列在 FIFO 算法下是否出现了 Belady 现象。

解析核心： 当分配的物理块增加（从 3 块增至 4 块）时，若缺页次数反而增加，即为 Belady 现象

代码

1.生产者消费者

桌上有一空盘，允许存放一只水果。爸爸放苹果，妈妈放桔子；儿子专吃桔子，女儿专吃苹果。 要求： 请用 P、V（wait/signal）原语 实现三个并发进程的控制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

semaphore S = 1;  // 盘子是否为空
semaphore So = 0; // 盘中是否有桔子
semaphore Sa = 0; // 盘中是否有苹果

father() {
    while(1) {
        P(S);
        将苹果放入盘中;
        V(Sa);
    }
}

son() {
    while(1) {
        P(So);
        从盘中取出桔子;
        V(S);
        吃桔子;
    }
}

完整伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

// 定义信号量
semaphore S = 1;  // 盘子里的空位
semaphore Sa = 0; // 盘中的苹果数
semaphore So = 0; // 盘中的桔子数

// 爸爸进程：只放苹果
void father() {
    while(1) {
        // 1. 申请空盘子 (若盘子满，则阻塞)
        P(S); 
        
        // 2. 临界区操作
        将苹果放入盘中;
        
        // 3. 释放"苹果"信号量 (唤醒等待苹果的女儿)
        V(Sa); 
    }
}

// 妈妈进程：只放桔子
void mother() {
    while(1) {
        // 1. 申请空盘子 (若盘子满，则阻塞)
        P(S);
        
        // 2. 临界区操作
        将桔子放入盘中;
        
        // 3. 释放"桔子"信号量 (唤醒等待桔子的儿子)
        V(So);
    }
}

// 儿子进程：只吃桔子
void son() {
    while(1) {
        // 1. 申请桔子 (若盘中无桔子，则阻塞)
        P(So);
        
        // 2. 临界区操作
        从盘中取出桔子;
        
        // 3. 释放盘子空间 (唤醒爸爸或妈妈)
        V(S);
        
        吃桔子; // 非临界区操作
    }
}

// 女儿进程：只吃苹果
void daughter() {
    while(1) {
        // 1. 申请苹果 (若盘中无苹果，则阻塞)
        P(Sa);
        
        // 2. 临界区操作
        从盘中取出苹果;
        
        // 3. 释放盘子空间 (唤醒爸爸或妈妈)
        V(S);
        
        吃苹果; // 非临界区操作
    }
}

2.进程同步

四个进程 A、B、C、D 都要读一个共享文件 F。系统限制：进程 A 和 C 不能同时读文件 F，进程 B 和 D 也不允许同时读文件 F。 要求：

1. 应如何定义信号量及其初值？

2. 编写 P、V 操作序列以保证进程 A、B、C、D 能正确并发工作。

代码逻辑提示： 需定义两个互斥信号量 S1（控制 A、C 互斥）和 S2（控制 B、D 互斥），初值均为 1

S1: 用于控制进程 A 和 C 对文件 F 的互斥访问。

• 初值 = 1（表示允许 A 或 C 中的某一个先进入）。

S2: 用于控制进程 B 和 D 对文件 F 的互斥访问。

• 初值 = 1（表示允许 B 或 D 中的某一个先进入）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// 定义信号量
semaphore S1 = 1; // 保护 A-C 互斥
semaphore S2 = 1; // 保护 B-D 互斥

// 进程 A
void Process_A() {
    while(1) {
        P(S1);      // 申请 S1 锁 (若 C 占用则阻塞)
        读文件 F;    // 临界区
        V(S1);      // 释放 S1 锁 (唤醒等待的 C)
    }
}

// 进程 C (与 A 对称)
void Process_C() {
    while(1) {
        P(S1);      // 申请 S1 锁 (若 A 占用则阻塞)
        读文件 F;    // 临界区
        V(S1);      // 释放 S1 锁 (唤醒等待的 A)
    }
}

// ---------------------------

// 进程 B
void Process_B() {
    while(1) {
        P(S2);      // 申请 S2 锁 (若 D 占用则阻塞)
        读文件 F;    // 临界区
        V(S2);      // 释放 S2 锁 (唤醒等待的 D)
    }
}

// 进程 D (与 B 对称)
void Process_D() {
    while(1) {
        P(S2);      // 申请 S2 锁 (若 B 占用则阻塞)
        读文件 F;    // 临界区
        V(S2);      // 释放 S2 锁 (唤醒等待的 B)
    }
}

真题

简答

1. 操作系统具有哪些功能？并说明各功能对应的计算机系统部件分别是什么？

处理机管理（对应部件：CPU）：负责进程控制、进程同步、进程通信、死锁处理及处理机调度。

存储器管理（对应部件：内存）：负责内存分配、内存保护、地址映射及内存扩充（虚拟内存）。

设备管理（对应部件：I/O设备）：负责缓冲管理、设备分配、设备处理及虚拟设备实现。

文件管理（对应部件：文件/数据/磁盘）：负责文件存储空间管理、目录管理、文件的读写管理及存取控制。

用户接口（对应部件：用户/硬件）：提供用户与计算机系统之间的交互界面。

1. 操作系统包括哪几种类型的用户接口？它们分别适用于哪种情况？

命令接口：

• 联机命令接口（交互式）：适用于用户在终端上直接、交互地使用计算机（如命令行、Shell）。
• 脱机命令接口（批处理）：适用于作业控制，用户编写作业说明书，由系统自动处理。

图形用户接口 (GUI)：采用图形化操作，适用于普通用户，操作简单直观（如 Windows, macOS 桌面）。

程序接口 (系统调用)：由一组系统调用组成，适用于程序员在编程时请求操作系统服务。

1. 请说明线程与进程的区别。

调度方面：线程是独立调度和分派的基本单位；进程是资源分配的基本单位。

资源方面：进程拥有独立的系统资源（内存、文件等）；线程几乎不拥有资源，但共享所属进程的全部资源。

开销方面：线程的创建、切换和终止的时空开销远小于进程，并发性更高。

通信方面：进程间通信需要通过IPC机制（如管道、消息队列）；线程间可以直接读写同一进程的数据段进行通信，更加方便。

1. 什么是死锁？产生死锁的原因和必要条件是什么？

定义：多个进程因竞争资源而造成的一种互相等待的僵局，若无外力作用，这些进程都将无法向前推进。

产生原因：

1. 系统资源竞争（资源不足）。
2. 进程推进顺序非法。

四个必要条件（缺一不可）：

1. 互斥条件（资源独占）。

2. 不剥夺条件（已获资源不能被抢占）。

3. 请求和保持条件（占有资源并申请新资源）。

4. 环路等待条件（存在一个进程-资源的环形链）。

5. 什么是逻辑文件？什么是物理文件？

逻辑文件：

• 这是用户视角下的文件组织形式。
• 用户将数据看作是一组有序的字符流（流式文件）或记录的集合（记录式文件），独立于物理存储介质。

物理文件：

• 这是系统视角（存储视角）下的文件组织形式。
• 指文件在存储介质（如磁盘）上的存放方式。常见的形式有顺序文件（连续分配）、链接文件（链式分配）和索引文件（索引分配）。

1、某计算机系统有三个进程 A、B、C，进程 A 依次使用 CPU 计 6s，使用打印机计 10s，使用 CPU 计 5s，读写硬盘计 10s，使用 CPU 计 2s；进程 B 依次读写硬盘计 10s，使用 CPU 计 7s，使用打印机计 10s，使用 CPU 计 2s，使用打印机计 10s；进程 C 依次使用 CPU 计 2s，读写硬盘计 15s，使用打印机计 6s。在单道程序环境下先执行 A 再执行 B，最后执行 C，

进程 C 的周转时间是（1）s，

CPU 的利用率是（2）%；

在多道程序环境下，进程 A 的周转时间是（3）______s，

平均周转时间是（4）s，

CPU 的利用率是（5）%。

2.某国产著名品牌手机专卖店进行新品发售活动，有多个店员进行销售。每个顾客排队进店后取一个号，并且等待叫号进店，当一个店员空闲下来时，就叫下一个号。以下为使用 PV 操作设计的店员和顾客同步算法，请补充算法中缺少的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int i=0, j=0;
semaphore mutex_i=1, mutex_j=1;    //i 和 j 分别记录当前的取号值和叫号值

Consumer(){                        //顾客算法
    进入手机店;
    (6)//进入临界区准备操作共享变量i 答案应该是P(mutex_i);
    取号 i;
    i++;
    (7)//退出临界区，操作完成 答案应该是V(mutex_i);
    等待叫号 i 并购买手机;
}

Seller(){                          //店员算法
    while(1){
        (8)//准备访问共享变量J，准备加锁   P(mutex_j);
        if(j<i){
            叫号 j;
            (9)//更新J j++;
            (10)//释放锁 V(mutex_j);
            销售手机;
        }
        else{
            V(mutex_j);
            休息片刻;
        }
    }
}

所以加锁是P，解锁是V

计算

请回答下列问题

（1）页的大小为多少字节？系统的逻辑地址空间大小为多少页？（4 分）

64kb 64kb

（2）假定页表项占 8 个字节，则页表共占多少页？要求写出计算过程。（3 分）

页表总大小（字节） = 页表项总数 $\times$ 每个页表项的大小=$$= 2^{16} \times 8 \text{ Byte} = 65536 \times 8 \text{ Byte} = 524,288 \text{ Byte}$$

页表占用的页数 = 页表总大小 / 每页的大小 = $$= \frac{2^{16} \times 8 \text{ Byte}}{2^{16} \text{ Byte}} = 8 \text{ 页}$$

（3）如有一用户程序有 10 页长，且某一时刻该用户程序页表如下所示。如果分别遇到以下两个逻辑地址：0B11AC76H、110B19CFH 处的操作，说明存储管理系统如何处理，并写出具体物理地址（用 16 进制表示）。（8 分）

某时刻页表状态

地址 1：0B11AC76H

1. 拆分地址：
   • 逻辑页号 (Hex): 0B11
   • 页内偏移 (Hex): AC76
2. 二进制转换与查表：
   • 将页号 0B11 转为二进制：0000 1011 0001 0001
   • 查表： 在表中查找该页号。
   • 发现表中的最后一行逻辑页号正是 0000 1011 0001 0001B。
   • 对应的物理块号为：0001 1000B。
3. 计算物理地址：
   • 物理块号 0001 1000B 转换为十六进制是 18H。
   • 物理地址拼接规则： 物理块号 + 页内偏移。
   • 物理地址 = 18 (块号) 拼接 AC76 (偏移)。
   • 物理地址：18AC76H

处理结果： 系统在页表中找到对应页号，成功进行地址映射，访问物理地址 18AC76H。

地址 2：110B19CFH

1. 拆分地址：
   • 逻辑页号 (Hex): 110B
   • 页内偏移 (Hex): 19CF
2. 二进制转换与查表：
   • 将页号 110B 转为二进制：0001 0001 0000 1011。
   • 查表：
     • 第3行是 0001 0001 0000 1010 (即 110A) $\to$ 不匹配。
     • 第5行是 1111 1111 0000 1011 (即 FF0B) $\to$ 不匹配。
     • 扫描全表，不存在页号为 110B 的表项。
3. 逻辑判断：
   • 由于页表中没有该逻辑页号的映射记录，说明该页面当前不在内存中，或者该地址是非法地址。
   • 题目提到“用户程序有10页长”（意味着合法页号应该是 0~9），而 110B H 对应的十进制是 4363，远超 10，这属于严重的越界访问（非法访问）。

处理结果： 产生**缺页中断（Page Fault）*或*越界/非法访问中断。系统将捕获该错误，通常会终止程序运行。

2、若干等待访问磁盘者依次要访问的磁道为 31、60、12、25、68、18、109，假设每移动一个磁道需要 1 毫秒时间，移动臂当前位于 40 号柱面，请按下述算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。

（1）先来先服务算法；（5 分）

先来先服务算法 (FCFS)，严格按照请求队列的先后顺序进行访问，不考虑磁头移动的优化。

$$40 \rightarrow 31 \rightarrow 60 \rightarrow 12 \rightarrow 25 \rightarrow 68 \rightarrow 18 \rightarrow 109$$

总寻道磁道数：$9 + 29 + 48 + 13 + 43 + 50 + 91 = \mathbf{283}$，总花费时间：$283 \times 1\text{ms} = \mathbf{283\text{ms}}$

（2）最短寻道时间优先算法；（5 分）

每次选择距离当前磁头位置最近的那个磁道进行访问（贪心策略）

当前 40：最近的是 31 (距9) vs 60 (距20) $\rightarrow$ 去 31。

当前 31：最近的是 25 (距6) vs 60 (距29) $\rightarrow$ 去 25。

当前 25：最近的是 18 (距7) $\rightarrow$ 去 18。

当前 18：最近的是 12 (距6) $\rightarrow$ 去 12。

当前 12：此时小号磁道全部访问完，回头找最近的大号 60 (距48) $\rightarrow$ 去 60。

当前 60：最近的是 68 (距8) $\rightarrow$ 去 68。

当前 68：最后剩下 109 (距41) $\rightarrow$ 去 109。

$$40 \rightarrow 31 \rightarrow 25 \rightarrow 18 \rightarrow 12 \rightarrow 60 \rightarrow 68 \rightarrow 109$$

总寻道磁道数：$9 + 6 + 7 + 6 + 48 + 8 + 41 = \mathbf{125}$

总花费时间：$125 \times 1\text{ms} = \mathbf{125\text{ms}}$

（3）扫描算法（当前磁头移动的方向为磁道递增）。（5 分）

磁头象电梯一样，先向一个方向移动（题目指定磁道递增），访问所有途经请求，直到该方向无请求后再反向。 注意：题目未给出磁盘边界（如0-200），通常按 LOOK 算法处理，即“到了该方向最远的请求就掉头”，不需要走到磁盘尽头。

阶段1（向递增方向/向右）：从 40 开始，依次访问比 40 大的磁道。

• 顺序：$60 \rightarrow 68 \rightarrow 109$

阶段2（掉头向递减方向/向左）：从 109 掉头，依次访问比 40 小的磁道（从大到小）。

• 顺序：$31 \rightarrow 25 \rightarrow 18 \rightarrow 12$

寻道距离计算（简化算法）：

• 向右行程：$109 - 40 = 69$
• 向左行程：$109 - 12 = 97$
• 总距离：$69 + 97 = 166$