操作系统复习笔记

第1章 操作系统基础知识

练习题

请简述计算机从开机到操作系统完全启动的基本过程？

OS的引导过程（滚雪球方式）：

1. 初始引导
   • 系统加电
   • 执行初始引导程序，对系统硬件和配置进行自检，保证系统没有硬件错误
   • 从硬盘中读入操作系统引导程序，并将控制权交给该程序模块
2. 引导程序执行：将操作系统核心文件读入内存，并将控制交给核心的初始化程序。
3. 内核初始化，初始化系统数据结构及参数
   • 系统加电建立进程有关的数据结构 ；
   • 获得自由存储空间的容量，建立存储管理的数据结构 ；
   • 建立系统设备和文件系统的数据结构 ；
   • 初始化时钟。
4. 系统初始化
   • 完善OS的操作环境，装载命令处理程序 (或图形用户界面)，并初始化；
   • 在多用户系统中，为每个终端建立命令解释进程，使系统处于命令接收状态。

OS的启动流程：

1. 引导加载程序加载OS内核到内存中。

2. 内核初始化：OS内核进行一系列的初始化操作，如硬件设备检查，加载驱动，内存管理等。

3. 内核启动init进程：内核初始化完成后，会启动init进程（在Linux中）或systemd进程，该进程是所有其他用户进程的父进程。

4. 用户空间程序启动：init进程根据系统的配置，启动一系列的用户空间程序，如Shell，图形界面等。

什么是引导扇区（Boot Sector）？它在操作系统的启动过程中起什么作用？

引导扇区（Boot Sector） 是计算机存储设备（如硬盘、U盘等）上用于启动操作系统的关键数据区域，通常占据设备的第一个物理扇区（512字节）。它在操作系统的启动过程中扮演“启动链”的第一环角色，负责将控制权从 BIOS/UEFI 传递给更复杂的引导加载程序（Boot Loader）。

请描述一个程序从点击图标到完全运行的典型执行流程？

1. 加载： 当启动一个程序时，由OS的加载器将该程序的可执行文件加载到内存中。

2. 运行： OS创建一个新的进程，并将CPU的控制权交给该进程。该新进程开始执行加载到内存中的程序代码。

3. 系统调用： 当程序需要进行一些特权操作（如读写文件，发送网络数据等）时，它将发起系统调用。

4. 中断和信号： 程序的执行可能会被中断和信号打断。中断通常是由硬件事件触发的，如I/O操作的完成，定时器的超时等。信号则是一种软件中断，可以由其他进程或者内核发送。

5. 退出： 当程序执行完成或者由于某种原因需要停止时，它将执行退出操作，包括释放资源，关闭打开的文件，通知父进程等。

选择题

在脱机批处理方式中，有一台负责与外部设备交换信息的计算机，一般称之为_____。

A．终端处理机 B．外围处理机

C．客户机 D．服务处理机

在计算机系统中，操作系统是_____。

A. 一般应用软件 B. 核心系统软件

C. 用户应用软件 D. 硬件

实时操作系统必须在_____内处理来自外部的事件。

A.时间片 B.周转时间

C.被控制对象规定时间 D.一个机器周期

在设计实时操作系统时，不重点考虑的是______。

A．及时响应，快速处理 B．有高安全性

C．提高系统资源的利用率 D．有高可靠性

下述关于并发性的叙述中正确的是_____。

A.并发性是指若干事件在不同时间间隔内发生

B.并发性是指若干事件在同一时间间隔内发生

C.并发性是指若干事件在不同时刻发生

D.并发性是指若干事件在同一时刻发生

分时系统追求的目标是_____。

A.快速响应用户 B.充分利用I/O设备

C.充分利用内存 D.提供系统吞吐率

一个多道批处理系统，提高了计算机系统的资源利用率，同时_____。

A. 减少各个作业的执行时间

B. 增加了单位时间内作业的吞吐量

C. 减少了部分作业的执行时间

D. 减少单位时间内作业的吞吐量

批处理系统的主要缺点是_____。

A. 无交互能力 B. 系统吞吐量小

C. 资源利用率低 D. CPU利用率不高

从用户的观点看，操作系统是_____。

A.合理地组织计算机工作流程的软件

B. 由若干层次的程序按一定的结构组成的有机体

C. 控制和管理计算机资源的软件

D.用户与计算机之间的接口

所谓_____是指将一个以上的作业放入内存，并且同时处于运行状态，这些作业共享处理机的时间和外围设备等资源。

A.多道程序设计 B.多重处理

C.共行执行 D.实时处理

操作系统中最基本的两个特征是_____。

A. 虚拟和不确定 B.共享和虚拟

C. 并发和共享 D.并发和不确定

第2章 操作系统的运行环境和运行机制

练习题

从应用程序的视角来看，异常和中断的区别是什么？

特征	异常	中断
触发源	程序自身	外部硬件或定时器
同步/异步	同步（由指令触发）	异步（随机发生）
应用程序感知	直接感知，可能导致崩溃或信号处理	间接感知（如通过系统调用返回结果）
处理方式	需显式处理（如捕获异常）	由操作系统透明处理

从应用程序的角度来看，异常是程序自身执行过程中的“事故”，需要主动处理或修复；中断是外部事件的“通知”，由操作系统代为处理，对程序透明。

在发生CPU的特权级切换时，CPU会自动保存当前的执行状态，包括程序计器(PC)、栈指针(Stack Pointer, SP)等。请分析：如果不保存PC和SP，会出现什么问题？

1. 无法返回原执行流：PC 记录了下一条要执行的指令地址。如果切换特权级时未保存 PC，CPU 将无法知道中断/异常处理完成后应该返回到哪里继续执行。程序会跳转到错误的地址，导致执行流程混乱（例如执行随机指令、死循环或崩溃）。
2. 栈数据破坏与内存安全风险：SP 指向当前栈的顶部，保存了函数的返回地址、局部变量和寄存器状态。若未保存 SP，切换特权级时会使用错误的栈空间。
3. 特权级隔离失效：用户程序可能通过未隔离的 SP 或 PC 篡改内核栈或代码，引发安全漏洞（如提权攻击）。内核操作可能因用户态数据干扰而崩溃。
4. 多任务调度失效：在多任务系统中，进程切换依赖保存的 PC 和 SP 以恢复执行现场。若未保存 PC 和 SP，进程切换后无法恢复原执行状态，导致多任务调度完全失效，系统只能运行单一任务。

系统调用和库函数或API之间是什么关系？

系统调用、库函数和API之间的关系可以理解为不同层次的接口封装，三者协作实现用户程序与操作系统之间的交互。系统调用是操作系统内核提供的底层接口，允许用户程序（运行在用户态）请求内核（运行在内核态）执行特权操作，例如文件读写、进程创建、网络通信等。库函数是封装在用户态库中的函数，例如C标准库（libc）、数学库（libm）等。它们可能直接执行用户态操作，也可能间接调用系统调用。API是一组预定义的接口规范，用于定义程序与外部系统（如操作系统、库、服务）的交互方式。

层级结构：

+-----------------+
|  应用程序代码    | → 调用库函数或API
+-----------------+
        ↓
+-----------------+
| 库函数/API       | → 可能封装系统调用
+-----------------+
        ↓
+-----------------+
| 系统调用         | → 进入内核执行特权操作
+-----------------+

示例对比

操作	系统调用	库函数/API	说明
输出字符串	write()	printf()	printf()封装了 write()
创建进程	fork()	pthread_create()	线程库可能调用 clone()（系统调用）
获取时间	gettimeofday()	time()（C标准库）	time()可能直接调用系统调用
数学运算	无	sqrt()（数学库）	纯用户态计算，无需内核交互

• 系统调用是操作系统的底层入口，需特权级切换。
• 库函数/API是更高层次的封装，可能间接调用系统调用，也可能独立运行于用户态。
• 关系：API和库函数是对系统调用的抽象和扩展，目的是简化开发、增强功能、提高可移植性。

操作系统提供的系统调用有哪几种参数传递的方法？

1. 寄存器传递：将参数直接存放在CPU寄存器中，系统调用处理程序从寄存器中读取参数。
2. 内存块传递：将参数存储在用户空间的内存缓冲区中，通过寄存器传递缓冲区的地址和长度，内核通过该地址读取数据。
3. 结构体指针传递：将多个参数打包为结构体，通过寄存器传递结构体的指针，内核解析结构体内容。
4. 堆栈传递：将参数压入用户态堆栈，内核通过栈指针读取参数。

请解释说明系统调用机制涉及的概念：访管指令、系统调用号、参数传递、系统调用表、系统调用实现函数。

1. 访管指令：访管指令是用户态程序主动触发内核态执行的CPU指令，用于请求操作系统服务。它引发一个软中断（或异常），使CPU切换到特权模式（内核态）。
2. 系统调用好：每个系统调用在内核中对应唯一的数字编号，用于标识请求的服务类型。
3. 参数传递：用户程序向内核传递系统调用所需的输入参数（如文件路径、缓冲区地址等）。
4. 系统调用表：内核中维护的函数指针数组，每个条目对应一个系统调用的实现函数。
5. 系统调用实现函数：内核中实际执行系统调用操作的函数，完成用户请求的服务。

选择题

操作系统提供给编程人员的接口是_____。

A.系统调用 B.子程序

C.库函数 D.高级语言

第3章 进程线程模型

练习题

当使用fork()操作创建新进程时，父进程和子进程之间会共享以下哪种状态？

1.堆栈 2.堆 3.共享内存段

内核在进程间执行上下文切换时采取的主要操作步骤？

1. 触发切换 • 由中断/异常（如时间片耗尽、I/O请求）或主动系统调用（如sleep()）引发

2. 保存当前上下文 • 将当前进程的CPU状态存入其进程控制块(PCB)：

   ✓ 所有寄存器（通用寄存器、程序计数器PC、栈指针SP） ✓ 内存管理信息（页表基址寄存器） ✓ 浮点寄存器状态 ✓ 特殊功能寄存器

3. 切换至内核态 • 提升CPU特权级别到内核模式，使用内核栈进行后续操作

4. 执行调度程序 • 通过调度算法选择下一个要运行的进程

5. 更新内存管理单元 • 切换新进程的地址空间（页表基址寄存器更新）

   • 必要时刷新TLB（Translation Lookaside Buffer）

6. 恢复新进程上下文 • 从新进程的PCB加载保存的寄存器状态

   • 恢复程序计数器、栈指针等关键寄存器

7. 切换用户空间 • 降低CPU特权级别到用户模式

   • 开始执行新进程的代码

用户级线程与内核级线程的两个主要区别及其适用场景？

区别 1：管理主体与内核感知

• 用户级线程 ✓ 由用户空间的线程库（如 POSIX Pthreads）管理 ✓ 内核无法感知线程存在，仅看到单进程
• 内核级线程 ✓ 由操作系统内核直接管理 ✓ 每个线程在内核有独立的数据结构（如 Linux 的 task_struct）

区别 2：阻塞与并行性

• 用户级线程 ✓ 单个线程阻塞（如 I/O 操作）会导致整个进程阻塞 ✓ 无法利用多核 CPU 的并行性（所有线程绑定到单一内核线程）
• 内核级线程 ✓ 单个线程阻塞不影响其他线程执行 ✓ 支持多核并行调度（不同线程可分配到不同 CPU 核心）

---

适用场景对比

用户级线程更优的场景	内核级线程更优的场景
需要极速线程切换（无内核态切换开销）	需要多核并行计算（如科学计算、视频渲染）
大规模轻量级线程（如百万级连接处理）	涉及频繁阻塞操作（如文件I/O密集型任务）
跨平台移植性要求高（不依赖OS支持）	需要实时响应调度（如嵌入式系统控制）

选择题

对进程的管理和控制使用_____。

A. 指令 B. 信号量

C. 原语 D. 信箱

分配到必要的资源并获得处理机时的进程状态是_____。

A. 就绪状态 B.撤消状态

C. 执行状态 D.阻塞状态

下列进程状态变化中，_____变化是不可能发生的。

A.等待→就绪 B.等待→运行

C.运行→等待 D.运行→就绪

当_____时，进程从执行状态转变为就绪状态。

A.等待的事件发生 B.时间片到

C. 等待某一事件 D.进程被调度程序选中

下面对进程的描述中，错误的是_____。

A.进程是有生命期的 B. 进程执行需要处理机

C.进程是指令的集合 D.进程是动态的概念

如果系统中有n个进程，则就绪队列中进程的个数最多为_____。

A. n B. 1 C. n-1 D. n+1

操作系统通过_____对进程进行管理。

A. JCB B. PCB

C. DCT D. CHCT

下面所述步骤中，_____不是创建进程所必需的。

A.建立一个进程控制块

B.为进程分配内存

C. 将进程控制块链入就绪队列

D.由调度程序为进程分配CPU

下述哪一个选项，体现了原语的主要特点_____。

A. 并发性 B. 异步性

C.不可分割性 D.共享性

下面对父进程和子进程的叙述不正确的是_____。

A. 撤消父进程之时，可以同时撤消其子进程

B. 父进程和子进程之间可以并发

C. 父进程可以等待所有子进程结束后再执行

D.父进程创建了子进程，因此父进程执行完了子进程才能运行

下列几种关于进程的叙述中，最不符合操作系统对进程理解的是_____。

A．进程是在多程序并行环境中的完整的程序

B．进程可以由程序，数据和进程控制块描述

C．线程(Thread)是一种特殊的进程

D．进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位

当一个进程处于_____的状态时，称其为等待状态

A．它正等待调度

B．它正等着协作进程的一个消息

C．它正等分给它一个时间片

D．它正等进入内存

进程从执行状态到阻塞状态可能是由于_____ 。

A．进程调度程序的调度

B．现运行进程的时间片用完

C．现运行进程执行了P操作

D．现运行进程执行了V操作

一个进程被唤醒意味着_____ 。

A．该进程重新占有了CPU

B．进程状态变为就绪

C．它的优先权变为最大

D．其PCB移至就绪队列的队首

一个进程基本状态可以从其他两种基本状态转变过来 ，这个基本状态是_____。

A．执行状态 B．阻塞状态

C．就绪状态 D．撤销状态

设系统中有n（n>2）个进程，且当前不在执行进程调度程序，试考虑下述4种情况：

1. 有1个运行进程，n-1个就绪进程，没有进程处于等待状态。

2. 有1个运行进程，没有就绪进程，n-1进程处于等待状态。

3. 有1个运行进程，有1个就绪进程，n-2进程处于等待状态。

4. 没有运行进程，有2个就绪进程，n个进程处于等待状态

上述情况中，不可能发生的情况是_____。

下面关于进程的叙述中，不正确的有 _____ 条。2

① 进程申请CPU得不到满足时，其状态变为等待状态。

② 在单CPU系统中，任一时刻都有一个进程处于运行状态。

③ 优先级是进行进程调度的重要依据，一旦确定不能改变。

④ 进程获得处理机而运行是通过调度而实现的。

下列选项中，导致创建新进程的操作是 。

Ⅰ 用户登录成功 Ⅱ 设备分配

Ⅲ 启动程序执行

A.仅Ⅰ和Ⅱ B.仅Ⅱ和Ⅲ

C.仅Ⅰ和Ⅲ D.Ⅰ、Ⅱ、Ⅲ

下列选项中，在用户态执行的是____。

A、命令解释程序 B、缺页处理程序

C、进程调度程序 D、时钟中断处理程序

下列选项中，不可能在用户态发生的事件是（）。

A．系统调用 B. 外部中断

C. 进程切换 D. 缺页

第4章 进程线程调度

练习题

解释抢占式调度（preemptive scheduling）和非抢占式调度（nonpreemptive scheduling）的区别。

1. 抢占式调度（Preemptive Scheduling）

• 定义：操作系统可以在任意时刻中断当前运行的进程，将CPU分配给其他更高优先级或更紧急的进程。
• 特点：
  • 进程不需要主动释放CPU，调度程序强制剥夺其执行权。
  • 适用于分时系统、实时系统等需要快速响应的场景。
• 触发条件：
  • 时间片用完（如RR轮转调度）。
  • 更高优先级进程就绪（如优先级调度）。
  • 中断或系统调用导致内核态切换时可能触发调度。
• 优点：公平性高、响应快，避免单一进程长期独占CPU。
• 缺点：上下文切换开销较大。

2. 非抢占式调度（Nonpreemptive Scheduling）

• 定义：进程主动释放CPU后才会发生调度（如等待I/O、执行完毕或主动调用yield()）。
• 特点：
  • 进程一旦获得CPU，除非自身阻塞或终止，否则不会被强制中断。
  • 常见于批处理系统或简单嵌入式系统。
• 触发条件：
  • 进程执行完毕。
  • 进程主动阻塞（如等待资源）。
  • 进程调用exit()终止。
• 优点：上下文切换少，系统开销低。
• 缺点：可能导致长进程垄断CPU，降低交互性。

关键区别总结

对比维度	抢占式调度	非抢占式调度
控制权归属	操作系统强制剥夺CPU	进程主动释放CPU
响应速度	高（适合交互式系统）	低（适合批处理任务）
典型场景	分时系统、实时OS	批处理系统、简单任务调度
实现复杂度	高（需处理中断、上下文保存）	低（仅需简单队列管理）

在RR策略的设计实现中，通常会维护一个运行队列，队列中的元素是对任务的引用（指针），每次被调度的任务会运行固定长度的时间片。如果在实施RR策略的队列中加入一个功能，可以在该任务的后面插入多个对同一任务的引用，那么这样的设计会带来什么样的影响？这样的设计使得RR策略与什么类型的调度相似？

在标准RR（Round-Robin，轮转调度）策略中：

1. 所有就绪任务按FIFO顺序排列在一个队列中。
2. 每个任务执行固定时间片（time quantum）后，被移回队列尾部。
3. 公平性：每个任务获得均等的CPU时间份额。

若在RR队列中允许对同一任务插入多个引用（即同一任务在队列中出现多次），会产生以下影响：

1）任务获得的CPU时间增加

• 原理：任务在队列中的引用次数越多，被调度的概率越高。
  • 例如：任务A有3个引用，任务B有1个引用 → A的CPU时间约为B的3倍。
• 效果：
  • 优点：可为高优先级任务分配更多资源（类似优先级调度）。
  • 缺点：破坏RR的公平性，低引用任务可能“饥饿”（Starvation）。

（2）调度行为趋近于优先级调度

• 动态优先级模拟：通过调整任务的引用次数，间接实现优先级控制。

  • 例如：后台任务保持1个引用，交互式任务插入多个引用以提升响应速度。

• 与标准RR的区别：

  标准RR	多引用RR
  严格公平（时间片均等）	允许任务权重差异化
  无优先级	隐式优先级（引用数=权重）

（3）实现复杂度提高

• 需维护引用计数，避免同一任务被重复执行（如时间片未用完时跳过冗余引用）。
• 需处理任务终止时的引用清理（防止悬垂指针）。

这样的设计使得RR策略与多级反馈队列（MLFQ）或权重轮转（Weighted RR）调度相似

• 多级反馈队列（MLFQ）：
  • 通过将任务分配到不同优先级的队列，实现动态优先级调整。
  • 高优先级队列中的任务获得更多CPU时间（类似多引用任务的权重优势）。
• 权重轮转（Weighted RR）：
  • 直接为任务分配权重（如3:1），权重高的任务获得更多时间片。
  • 本例中“引用次数”实质是权重的隐式表达。

什么是处理器亲和性（Processor Affinity）？它在多处理器调度中起什么作用？

处理器亲和性是指进程或线程倾向于在特定的处理器或处理器集合上运行的特性。

作用：由于该进程或线程之前在这些处理器上运行过，因此可能有一些数据或状态仍然缓存在那里，如果再次在这些处理器上运行，则可以利用这些缓存数据，从而提高性能。

第5章 进程同步机制

练习题

过桥问题

赵家村和李家村靠一座独木桥连接，独木桥上一次只能供一个方向上的行人行走。

（1）若独木桥上一次只允许一个人行走，请用信号量实现对行人的同步。

（2）若不考虑独木桥的载重量，只要桥上有赵家村的人往李家村走(或李家村的人往赵家村走)，其他同方向的人就可以连续通过。当桥上没有某一方向的行人行走时，另一方向的行人就可以走。请用信号量实现对两个方向上行人的同步。

---

（1）一次仅允许一人通行 解法：互斥信号量 • 信号量设计：

• mutex：初始值为1，表示桥的互斥访问权。

• 伪代码：

semaphore mutex = 1; // 独木桥互斥锁

// 赵家村行人（A方向）
void person_A() {
    wait(mutex);    // 申请桥的使用权
    cross_bridge(); // 过桥
    signal(mutex);  // 释放桥
}

// 李家村行人（B方向）
void person_B() {
    wait(mutex);    // 申请桥的使用权
    cross_bridge(); // 过桥
    signal(mutex);  // 释放桥
}

• 说明：

• wait(mutex) 和 signal(mutex) 保证同一时间只有一人过桥。

---

（2）允许同方向连续通行，反方向需等待 解法：读者-写者变种（方向优先级） • 信号量设计：

• bridge：互斥锁，初始值为1（保护方向切换）。

• counter_A 和 counter_B：统计当前方向的行人数量。

• mutex_A 和 mutex_B：保护对应计数器的互斥锁（初始值为1）。

• 伪代码：

semaphore bridge = 1;     // 方向切换锁
semaphore mutex_A = 1;    // 保护赵家村计数器
semaphore mutex_B = 1;    // 保护李家村计数器
int counter_A = 0;        // 赵家村方向行人计数
int counter_B = 0;        // 李家村方向行人计数

// 赵家村→李家村方向（A方向）
void person_A() {
    wait(mutex_A);        // 保护counter_A
    if (counter_A == 0)   // 如果是第一个A方向行人
        wait(bridge);     // 申请方向锁（禁止B方向）
    counter_A++;          // 增加A方向计数
    signal(mutex_A);

    cross_bridge();       // 过桥

    wait(mutex_A);
    counter_A--;          // 离开桥
    if (counter_A == 0)   // 如果是最后一个A方向行人
        signal(bridge);   // 释放方向锁（允许B方向）
    signal(mutex_A);
}

// 李家村→赵家村方向（B方向）
void person_B() {
    wait(mutex_B);
    if (counter_B == 0)
        wait(bridge);     // 申请方向锁（禁止A方向）
    counter_B++;
    signal(mutex_B);

    cross_bridge();

    wait(mutex_B);
    counter_B--;
    if (counter_B == 0)
        signal(bridge);   // 释放方向锁
    signal(mutex_B);
}

• 关键逻辑：

1. 第一个行人获取 bridge 锁，锁定方向。
   
2. 后续同方向行人直接通过（不竞争 bridge）。
   
3. 最后一个行人释放 bridge 锁，允许反方向行人通行。
   • 特点：

• 同方向可连续通行（类似读者-写者的“读者优先”）。

• 反方向行人需等待桥上无人（bridge 释放）才能通行。

---

咖啡店问题

在一家繁忙的咖啡店，顾客不断地排队下订单。咖啡店有多个收银员和咖啡师。为了提高效率和顾客满意度，咖啡店需要一个系统来管理订单的处理。

假设系统中有N个收银员线程负责接受顾客订单，有M个咖啡师线程负责制作饮品。订单需要先由收银员处理，然后由咖啡师制作。

请使用信号量和互斥锁来协调收银员和咖啡师之间的工作。确保订单被正确地接收和处理，并且咖啡师在有订单时才开始制作。

输出每个订单的接收和完成时间，以及当前队列中的订单数量。

提示

• 使用一个共享队列来存储订单，使用信号量来表示队列中的订单数量。
• 使用互斥锁保护对订单队列的插入和删除操作。
• 每个收银员和咖啡师由一个线程模拟。

问题分析 我们需要模拟一个咖啡店的订单处理系统，其中： 1. 收银员线程（N个）：负责接收顾客订单，并将订单加入共享队列。 2. 咖啡师线程（M个）：从共享队列获取订单并制作饮品。 3. 共享订单队列：存储待处理的订单，需保证线程安全。 4. 同步机制： • 收银员和咖啡师需互斥访问队列（防止数据竞争）。

• 咖啡师需等待订单到来（避免忙等待）。

• 收银员需通知咖啡师有新订单。

---

同步方案设计 1. 信号量与互斥锁 • queue_mutex：互斥锁，保护共享队列的插入/删除操作（初始值=1）。

• orders_available：信号量，表示队列中的订单数量（初始值=0），咖啡师通过 wait 等待订单。

• queue_space：信号量（可选），限制队列最大长度（避免内存耗尽）。

2. 共享数据结构 • 订单队列：存储订单（如订单ID、接收时间等）。

• 全局计数器：记录已处理的订单数量（需原子操作或加锁）。

3. 线程行为 • 收银员线程：

1. 接收订单（模拟输入）。

2. 获取 queue_mutex，将订单加入队列。

3. 释放 queue_mutex，并 signal(orders_available)。 • 咖啡师线程：

4. wait(orders_available) 等待订单。

5. 获取 queue_mutex，从队列取出订单。

6. 释放 queue_mutex，制作饮品并记录完成时间。

---

代码实现（伪代码）

from threading import Thread, Semaphore, Lock
import time
import queue

# 全局变量
order_queue = queue.Queue()  # 线程安全队列（实际可用list+锁模拟）
queue_mutex = Lock()         # 保护队列操作
orders_available = Semaphore(0)  # 初始无订单
order_counter = 0            # 已处理订单数（需原子操作或加锁）

# 收银员线程
def cashier_thread(cashier_id):
    global order_counter
    while True:
        # 模拟接收订单
        order_time = time.time()
        order = {"id": order_counter, "received": order_time}
        order_counter += 1

        # 将订单加入队列
        with queue_mutex:
            order_queue.put(order)
            print(f"订单 {order['id']} 接收时间: {order_time:.2f}, 队列长度: {order_queue.qsize()}")

        # 通知咖啡师有新订单
        orders_available.release()
        time.sleep(1)  # 模拟处理间隔

# 咖啡师线程
def barista_thread(barista_id):
    while True:
        # 等待订单
        orders_available.acquire()

        # 从队列取出订单
        with queue_mutex:
            order = order_queue.get()
            queue_size = order_queue.qsize()

        # 模拟制作饮品
        completion_time = time.time()
        print(f"订单 {order['id']} 完成时间: {completion_time:.2f}, 制作耗时: {completion_time - order['received']:.2f}s, 队列剩余: {queue_size}")

        time.sleep(2)  # 模拟制作时间

# 启动线程
for i in range(N):
    Thread(target=cashier_thread, args=(i,)).start()
for j in range(M):
    Thread(target=barista_thread, args=(j,)).start()

---

关键点说明 1. 线程安全队列： • 使用 queue_mutex 保护队列操作（若用 list 需手动加锁）。

• Python 的 queue.Queue 本身是线程安全的，但为演示显式加锁。

2. 信号量作用： • orders_available 确保咖啡师仅在订单到达时工作（避免忙等待）。

3. 输出信息： • 订单接收时间、完成时间、队列长度，用于监控系统状态。

4. 扩展性： • 可添加 queue_space 信号量限制队列最大长度（防止内存溢出）。

   • 可引入优先级队列（如VIP订单优先处理）。

---

总结 • 收银员和咖啡师通过互斥锁+信号量协同工作。

• 订单队列作为缓冲区，解耦接收与制作过程。

• 输出信息帮助分析系统性能（如平均等待时间、队列拥堵情况）。

• 实际应用中，可结合线程池（ThreadPoolExecutor）优化资源管理。

​ 某银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一个顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客及营业员的活动描述如下：

cobegin

{ process 顾客

​ { 从取号机获取一个号码；

​ 等待叫号；

 获得服务； }

process 营业员

{ while（TRUE）

{ 叫号；

​ 为顾客服务；} }

}coend

请添加必要的信号量和P、V（或wait（）、signal（））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

semaphore mutex=1; //互斥使用取号机

semaphore empty=10; //空座位的数量

semaphore full=0; //已占座位的数量

semaphore service=0; //等待叫号

cobegin

{ process 顾客i

{ P(empty); P(mutex);

从取号机获得一个号;

V(mutex); V(full);

P(service); // 等待叫号 }

process 营业员

{ while(TRUE)

{ P(full);

​ V(empty);

​ V(service); //叫号

​ 为顾客服务;

}

}

}coend

选择题

若信号量S的初值为2，当前值为-1，则表示有_____等待进程。

A. 2个 B. 1个

C. 0个 D. 3个

在操作系统中，P、V操作是一种_____。

A. 机器指令 B. 系统调用命令

C. 作业控制命令 D. 低级进程通信原语

下述哪个选项不是管程的组成部分_____。

A.对局部于管程的数据结构设置初值的语句

B.局部于管程的共享数据说明

C.管程内对数据结构进行操作的一组过程

D.管程外过程调用管程内数据结构的说明

临界区是_____。

A.一段共享数据区 B. 一段程序

C.一个互斥资源 D.一个缓冲区

用P、V操作管理临界区时，信号量的初值应定义为_____。

A. 1 B. 2

C. -1 D. 0

对于两个并发进程，设互斥信号量为mutex,若mutex=0则_____。

A.表示有一个进程进入临界区，另一个进程等待进入

B. 表示没有进程进入临界区

C. 表示有一个进程进入临界区

D. 表示有两个进程进入临界区

对信号量S执行V操作后，下述选项正确的是_____。

A.当S小于0时唤醒一个阻塞进程

B.当S小于等于0时唤醒一个阻塞进程

C.当S小于0时唤醒一个就绪进程

D.当S小于等于0时唤醒一个就绪进程

对信号量X执行P操作时，若 _____ 则进程进入等待状态。

A．X-1<0 B．X-1<=0

C．X-1>0 D．X-1>=0

有若干并发进程均将共享变量count的值加1一次，那么有关count值说法正确的是_____。

A．得到的结果肯定不正确

B．得到的结果肯定正确

C．若控制这些并发进程互斥执行count加1操作，count中的值正确

D．A，B，C均不对

下述关于管程的描述中错误的是____ 。

A．管程是一种进程同步工具，解决了信号量机制 中大量同步操作分散问题

B．管程每次只允许一个进程进入管程

C．管程中的signal操作的作用和信号量机制中的signal操作相同

D．管程是被进程调用的

单处理机系统中，可并行的是 。

Ⅰ. 进程与进程 Ⅱ. 处理机与设备

Ⅲ. 处理机与通道 Ⅳ. 设备与设备

A.Ⅰ、Ⅱ和Ⅲ B.Ⅰ、Ⅱ和Ⅳ

C.Ⅰ、Ⅲ和Ⅳ D.Ⅱ、Ⅲ和Ⅳ

设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待该资源的进程数，则M、N分别是 。

A.0，1 B.1，0

C.1，2 D.2，0

填空题

1. 如果信号量的当前值为-4，则表示系统中在该信号量上有 4个等待进程。

2. 对于信号量可以做 P 操作和 V 操作，P操作用于阻塞进程，V 操作用于释放进程。程序中的 P操作应谨慎使用，以保证其使用的正确性，否则执行时可能发生死锁。

3. 信号量的物理意义是：当信号量值大于0时表示 可用资源数量；当信号量值小于0时，其绝对值为 等待进程数量 。

4. 有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是1 到 -(m-1)。

5. 访问临界资源的进程应该遵循的条件有：互斥访问（Mutual Exclusion）、空闲让进（Progress）、有限等待（Bounded Waiting）、和 让权等待（No Busy Waiting。

6. 临界资源是指__一次仅允许一个进程访问__的资源。

7. 管程由共享变量声明、操作共享变量的过程（方法）和 初始化代码三部分组成

第6章 死锁

练习题

银行家问题

考虑以下系统快照：

    Allocation          Max          Available
     A B C D          A B C D         A B C D
T0   0 0 1 2          0 0 1 2         1 5 2 0
T1   1 0 0 0          1 7 5 0
T2   1 3 5 4          2 3 5 6
T3   0 6 3 2          0 6 5 2
T4   0 0 1 4          0 6 5 6

使用银行家算法回答以下问题： a. 矩阵 Need 的内容是什么？ b. 系统是否处于安全状态？ c. 如果线程 T1 请求资源 (0,4,2,0)，是否可以立即批准该请求？

a. 计算 Need 矩阵 Need = Max - Allocation（逐项计算）： • T0: (0-0, 0-0, 1-1, 2-2) = (0,0,0,0)

• T1: (1-1, 7-0, 5-0, 0-0) = (0,7,5,0)

• T2: (2-1, 3-3, 5-5, 6-4) = (1,0,0,2)

• T3: (0-0, 6-6, 5-3, 2-2) = (0,0,2,0)

• T4: (0-0, 6-0, 5-1, 6-4) = (0,6,4,2)

Need 矩阵：

   A B C D
T0 0 0 0 0
T1 0 7 5 0
T2 1 0 0 2
T3 0 0 2 0
T4 0 6 4 2

b. 检查系统是否处于安全状态

1. 初始可用资源：Available = (1,5,2,0)
   

2. 安全性检查过程： • T0 的 Need 为 (0,0,0,0) ≤ Available，执行后释放资源：

   ◦ 新 Available = (1+0,5+0,2+1,0+2) = (1,5,3,2)

   • T3 的 Need 为 (0,0,2,0) ≤ Available (1,5,3,2)，执行后释放资源：

   ◦ 新 Available = (1+0,5+6,3+3,2+2) = (1,11,6,4)

   • T4 的 Need 为 (0,6,4,2) ≤ Available (1,11,6,4)，执行后释放资源：

   ◦ 新 Available = (1+0,11+0,6+1,4+4) = (1,11,7,8)

   • T1 的 Need 为 (0,7,5,0) ≤ Available (1,11,7,8)，执行后释放资源：

   ◦ 新 Available = (1+1,11+0,7+0,8+0) = (2,11,7,8)

   • T2 的 Need 为 (1,0,0,2) ≤ Available (2,11,7,8)，执行后释放资源：

   ◦ 新 Available = (2+1,11+3,7+5,8+4) = (3,14,12,12)

3. 安全序列：T0 → T3 → T4 → T1 → T2 结论：系统处于安全状态。

---

c. 处理 T1 的请求 (0,4,2,0) 1. 验证请求合法性： • T1 的 Need 为 (0,7,5,0)，请求 (0,4,2,0) ≤ Need → 合法。

• 请求 (0,4,2,0) ≤ Available (1,5,2,0) → 资源足够。

2. 模拟分配： • 更新 Allocation(T1)：(1+0,0+4,0+2,0+0) = (1,4,2,0)

   • 更新 Need(T1)：(0,7-4,5-2,0) = (0,3,3,0)

   • 新 Available：(1-0,5-4,2-2,0-0) = (1,1,0,0)

3. 检查新状态是否安全： • 当前 Available = (1,1,0,0)

   • T0 的 Need (0,0,0,0) ≤ Available → 执行后 Available = (1,1,1,2)

   • T3 的 Need (0,0,2,0) ≤ Available → 执行后 Available = (1,7,4,4)

   • T4 的 Need (0,6,4,2) 需要资源 (0,6,4,2)，但 Available = (1,7,4,4) 中 B=7 ≥ 6，C=4 ≥ 4，D=4 ≥ 2 → 可执行，新 Available = (1,7,5,8)

   • T1 的 Need (0,3,3,0) ≤ Available → 执行后 Available = (2,7,5,8)

   • T2 的 Need (1,0,0,2) ≤ Available → 执行后 Available = (3,10,10,12)

   安全序列：T0 → T3 → T4 → T1 → T2 结论：请求可以立即批准。

---

最终答案： a. Need 矩阵：

A B C D
T0 0 0 0 0
T1 0 7 5 0
T2 1 0 0 2
T3 0 0 2 0
T4 0 6 4 2

b. 是，系统处于安全状态。 c. 是，可以立即批准 T1 的请求。

选择题

要防止死锁的发生，可以通过破坏这四个必要条件之一来实现，但破坏 _____ 条件是不太实际的。

A.循环等待 B.部分分配

C.不可抢占 D.互斥

为多道程序提供的可共享资源不足时，可能出现死锁。但是，不适当的 _____ 也可能产生死锁。

A.分配队列优先权 B.进程推进顺序

C.资源的线性分配 D.进程优先权

采用资源剥夺法可以解除死锁，还可以采用 _____ 方法解除死锁。

A.拒绝分配新资源 B.修改信号量

C.执行并行操作 D.撤消进程

在 _____ 的情况下，系统出现死锁。

A. 计算机系统发生了重大故障

B. 有多个封锁的进程同时存在

C. 若干进程因竞争资源而无休止地相互等待他方释放已占有的资源

D. 资源数大大小于进程数或进程同时申请的资源数大大超过资源总数

银行家算法在解决死锁问题中是用于 _____ 的。

A.检测死锁 B.预防死锁

C.避免死锁 D. 解除死锁

资源的有序分配策略可以破坏 _____ 条件。

A.占有且等待资源 B.循环等待资源

C. 非抢夺资源 D.互斥使用资源

某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是 _____ 。

A. 9 B. 10

C. 11 D. 12

有序资源分配方法属于_____ 方法。

A．死锁预防 B．死锁避免

C．死锁检测 D．死锁解除

不能防止死锁的资源分配策略是_____。

A．剥夺式分配方式 B．按序分配方式

C．静态分配方式 D．互斥使用分配方式

某计算机系统中有6台打印机，多个进程均最多需要2台打印机，规定每个进程一次仅允许申请一台打印机。为保证一定不发生死锁，则允许参与打印机资源竞争的最大进程数是__。

A．3 B．4 C．5 D．6

某计算机中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值为（）。

A、2 B、3 C、4 D、5

某时刻进程的资源使用情况如下表所示：

此时的安全序列是___。

A、P1，P2，P3，P4 B、P1，P3，P2，P4

C、P1，P4，P3，P2 D、不存在

问题分析： 我们需要根据给定的资源分配情况，判断是否存在一个安全序列，使得所有进程都能顺利完成。安全序列是指一个进程执行顺序，使得每个进程都能获得所需的资源并释放已占用的资源，从而保证系统不会进入死锁状态。

给定数据： | 进程 | 已分配资源 (Allocation) | 尚需资源 (Need) | 可用资源 (Available) | | —- | ———————– | ————— | ——————– | | | R1 R2 R3 | R1 R2 R3 | R1 R2 R3 | | P1 | 2 0 0 | 0 0 1 | 0 2 1 | | P2 | 1 2 0 | 1 3 2 | | | P3 | 0 1 1 | 1 3 1 | | | P4 | 0 0 1 | 2 0 0 | |

步骤 1：计算当前可用资源 (Available) 初始可用资源为：Available = (0, 2, 1)

步骤 2：寻找可以执行的进程 我们需要找到一个进程，其尚需资源 (Need) ≤ 当前可用资源 (Available)。

• P1：Need = (0, 0, 1) ≤ Available = (0, 2, 1) → 可以执行

• 执行后，释放已分配资源：Allocation(P1) = (2, 0, 0)

• 更新可用资源：Available = (0, 2, 1) + (2, 0, 0) = (2, 2, 1)

• P4：Need = (2, 0, 0) ≤ Available = (2, 2, 1) → 可以执行

• 执行后，释放已分配资源：Allocation(P4) = (0, 0, 1)

• 更新可用资源：Available = (2, 2, 1) + (0, 0, 1) = (2, 2, 2)

• P3：Need = (1, 3, 1) ≤ Available = (2, 2, 2) → 不满足（R2=3 > 2）

• 暂时无法执行。

• P2：Need = (1, 3, 2) ≤ Available = (2, 2, 2) → 不满足（R2=3 > 2）

• 暂时无法执行。

步骤 3：尝试其他顺序 由于直接执行 P1 后，P4 可以执行，但 P3 和 P2 仍无法执行，我们需要尝试其他顺序。

尝试顺序：P1 → P4 → P3 → P2 1. P1：执行后，Available = (2, 2, 1) 2. P4：执行后，Available = (2, 2, 2) 3. P3：Need = (1, 3, 1) ≤ Available = (2, 2, 2) → 不满足（R2=3 > 2） • 无法执行。

尝试顺序：P1 → P3 → P4 → P2 1. P1：执行后，Available = (2, 2, 1) 2. P3：Need = (1, 3, 1) ≤ Available = (2, 2, 1) → 不满足（R2=3 > 2） • 无法执行。

尝试顺序：P1 → P4 → P2 → P3 1. P1：执行后，Available = (2, 2, 1) 2. P4：执行后，Available = (2, 2, 2) 3. P2：Need = (1, 3, 2) ≤ Available = (2, 2, 2) → 不满足（R2=3 > 2） • 无法执行。

步骤 4：检查其他初始选择 • P4：Need = (2, 0, 0) ≤ Available = (0, 2, 1) → 不满足（R1=2 > 0）

• 无法直接执行。

• P3：Need = (1, 3, 1) ≤ Available = (0, 2, 1) → 不满足（R1=1 > 0, R2=3 > 2）

• 无法直接执行。

• P2：Need = (1, 3, 2) ≤ Available = (0, 2, 1) → 不满足（R1=1 > 0, R2=3 > 2）

• 无法直接执行。

结论： 唯一可以执行的初始进程是 P1，但执行 P1 后，后续进程无法满足需求，因此不存在安全序列。

最终答案： D、不存在

填空题

在有m个进程的系统中出现死锁时，死锁进程的个数k应该满足的条件是2≤k≤m。

银行家算法中，当一个进程提出的资源请求将导致系统从安全状态进入 不安全状态时，系统就拒绝它的资源请求。

对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于死锁避免 ，破坏环路等待条件是属于死锁预防，而剥夺资源是死锁解除的基本方法。

第7章 内存管理

页面置换算法

先进先出置换算法(FIFO)

先进先出算法：选择调入主存时间最长的页面予以淘汰。

特点：该算法实现比较简单，对按线性顺序访问的程序比较合适，但可能产生异常现象。很少使用纯粹的FIFO。

Belady异常：在某些情况下，分配给进程的页面数增多，缺页次数反而增加。

采用先进先出算法的页面置换情况

最佳置换算法（OPT）

最佳算法：也称最优置换算法。从内存中选择最长时间不会使用的页面予以淘汰。

特点：因页面访问的未来顺序很难精确预测，该算法具有理论意义，可以用来评价其他算法的优劣。

采用最佳置换算法的页面置换情况

最近最久未使用置换算法(LRU)

最近最久未使用算法：选择最近一段时间内最长时间没有被访问过的页面予以淘汰。

为此，应赋予每个页面一个访问字段，用于记录页面自上次访问以来所经历的时间。

LRU是Least Recently Used，也称为最近最少使用

采用LRU算法的页面置换情况

LRU算法的实现

1. 计数器
   • 每个页表项有一个计数器，每次访问页时，把时间拷贝到计数器中。
   • 置换计数器最小值的页
   • 为每个页面配置一个计数器，其初值为0。当进程访问某页时，将计数器的最高位置1，定时器每隔一定时间将计数器右移1位，则数值最小的页是最近最久未使用的页面。

计数器实现方法

2. 特殊栈
   • 利用一个特殊栈保存当前使用各页的页面号。当进程访问一个页面时，将该页面号从栈中移出压到栈顶。栈底即最近最久未使用的页面号。

特殊栈实现方法

LRU近似置换算法

近似LRU算法的基础：引用位（也称访问位）

• 每个页表项都关联一个引用位，初始值为0
• 当页被访问时将引用位设为1
• 如果存在引用位为0的页，则置换它

附加引用位算法

与前面的计数器实现方法类似

二次机会算法

是FIFO算法的改进，以避免将经常使用的页面淘汰掉。

算法思想：使用FIFO算法选择一页淘汰时，先检查该页的引用位，如果是0就立即淘汰该页，如果是1就给它第二次机会，将其引用位清0，并将它放入页面链的末尾，将其装入时间置为当前时间，然后选择下一个页面。

简单时钟（clock）算法

• 简单时钟置换算法既是对二次机会算法的改进，也是对LRU算法的近似。该算法也要求为每页设置一个访问位。
• 实现思想：将页面排成一个循环队列，类似于时钟表面，并使用一个置换指针。当发生缺页时，检查指针指向的页面，若其访问位为0则淘汰该页，否则将该页的访问位清0，指针前移并重复上述过程，直到找到访问位为0的淘汰页为止。最后指针停留在被置换页的下一页上；
• 该算法也称为最近未使用（Not Recently Used，NRU）算法。

改进的时钟算法

​ 将一个修改过的页面换出需要写磁盘，其开销大于未修改页面。为此在改进型时钟算法中应考虑页面修改情况。设R为访问位，U为修改位，将页面分为以下4种类型：

• 1类(R=0,U=0)：未被访问又未被修改
• 2类(R=0,U=1)：未被访问但已被修改
• 3类(R=1,U=0)：已被访问但未被修改
• 4类(R=1,U=1)：已被访问且已被修改

算法描述：

• 从指针当前位置开始扫描循环队列，寻找R=0,U=0的页面，将满足条件的第一个页面作为淘汰页。

• 若第1步失败，则开始第2轮扫描，寻找R=0,U=1的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位置0。

• 若第2步失败，则将指针返回到开始位置，然后重复第1步，若仍失败则必须重复第2步。此时一定能找到淘汰页面。

• 特点：减少了磁盘I/O次数，但算法本身开销增加。

最不经常使用算法（LFU）

• 选择到当前时间为止访问次数最少的页淘汰。
• 该算法要求为每页设置一个访问计数器，每当页被访问时，该页的访问计数器加1。发生缺页中断时，淘汰计数值最小的页面，并将所有计数器清零。

练习题

1. 为什么页面大小总是2的幂次方？

1. 硬件优化：计算机硬件（如内存管理单元MMU）通过二进制位运算处理地址转换时，2的幂次方能直接利用地址的低位作为页内偏移量，高位作为页号，简化计算（例如取模运算可替换为高效的位掩码操作）。
2. 对齐效率：2的幂次方对齐能确保内存块整齐划分，减少碎片，提升缓存命中率。例如，CPU缓存行通常也采用2的幂次方大小，与页面对齐可优化数据加载。
3. 地址空间利用：操作系统分配虚拟地址空间时，2的幂次方大小便于将地址均匀分割，简化管理逻辑（如多级页表的索引计算）。
4. 历史与兼容性：早期计算机设计采用二进制体系，此约定延续至今，软硬件生态已深度适配

2. 给定以下条件：

   • 逻辑地址空间：64 页，每页 1,024 字
   • 物理内存：32 帧

   需要计算：

   1. 逻辑地址的位数
   2. 物理地址的位数

a. 逻辑地址的位数

逻辑地址由 页号（page number） 和 页内偏移量（page offset） 组成：

1. 页号位数：

   • 逻辑地址空间有 64 页，因此需要足够多的位数来表示 64 个不同的页号。
   • 计算：log2(64)=6 位。

2. 页内偏移量位数：

   • 每页大小为 1,024 字，因此需要足够多的位数来表示 1,024 个不同的偏移位置。
   • 计算：log2(1024)=10 位。

3. 逻辑地址总位数：

   逻辑地址位数=页号位数+页内偏移量位数=6+10=16 位

答案 (a)：逻辑地址有 16 位。

b. 物理地址的位数

物理地址由 帧号（frame number） 和 页内偏移量（page offset） 组成：

1. 帧号位数：

   • 物理内存有 32 帧，因此需要足够多的位数来表示 32 个不同的帧号。
   • 计算：log2(32)=5 位。

2. 页内偏移量位数：

   • 页内偏移量与逻辑地址相同（因为页大小不变），仍然是 10 位。

3. 物理地址总位数：

   物理地址位数=帧号位数+页内偏移量位数=5+10=15 位

答案 (b)：物理地址有 15 位。

3. 给定 MPV 操作系统的内存管理参数：

   • 虚拟地址（Virtual Address）：24 位
   • 物理地址（Physical Address）：20 位
   • 页大小（Page Size）：4 KB

   需要计算：

   1. (a) 传统单级页表（conventional single-level page table）的条目数
   2. (b) 反向页表（inverted page table）的条目数
   3. MPV 操作系统支持的最大物理内存容量

1. 分析地址结构 首先，我们需要分解 虚拟地址 和 物理地址 的结构，以确定页号（page number）和页内偏移量（page offset）的位数。

1. 页内偏移量（Page Offset）位数 • 页大小 = 4 KB = 字节

• 因此，页内偏移量占 12 位（因为 2¹² = 4096 ）。

2. 虚拟地址分解（24 位） • 虚拟地址 = 页号（VPN） + 页内偏移量（Offset）

• 页号位数 = 虚拟地址位数 - 偏移量位数 =24 − 12 = 12 位

• 因此，虚拟页号（VPN）有 12 位，可以表示2¹² = 4096个不同的页。

3. 物理地址分解（20 位） • 物理地址 = 帧号（PFN） + 页内偏移量（Offset）

• 由于页内偏移量仍然是 12 位，帧号位数 = 物理地址位数 - 偏移量位数 =20 − 12 = 8位

• 因此，物理帧号（PFN）有 8 位，可以表示 2⁸ = 256 个不同的帧。

---

(a) 传统单级页表的条目数 • 传统页表 的条目数由 虚拟页号（VPN） 决定，即每个虚拟页对应一个页表条目。

• 虚拟页号有 12 位，因此页表条目数 = 2¹² = 4096 个。

答案 (a)：传统单级页表有 4096 个条目。

---

(b) 反向页表的条目数 • 反向页表（Inverted Page Table, IPT） 的条目数由 物理帧号（PFN） 决定，即每个物理帧对应一个反向页表条目。

• 物理帧号有 8 位，因此反向页表条目数 = 2⁸ = 256 个。

答案 (b)：反向页表有 256 个条目。

---

最大物理内存容量 • 物理地址有 20 位，因此可寻址的物理内存空间为2²⁰ = 1, 048, 576 字节（即 1 MB）。

• 但题目问的是 最大物理内存，而物理帧数由 帧号位数（8 位） 决定，即最多 256 帧。

• 每帧大小 = 页大小 = 4 KB

• 因此，最大物理内存 = 256 × 4 KB = 1024 KB = 1 MB 。

答案：MPV 操作系统支持的最大物理内存是 1 MB。

4. 给定一个分页系统，页表存储在内存中：

   • 内存访问时间（Memory Access Time）：50 ns
   • TLB（Translation Lookaside Buffer）命中率：75%
   • TLB 查找时间（TLB Lookup Time）：2 ns（命中时）

   需要计算：

   (a) 无 TLB 时，分页内存访问的总时间

   (b) 有 TLB 时，

   • 75% 的情况命中 TLB，访问时间 = TLB 查找时间 + 1 次内存访问

   • 25% 的情况未命中 TLB，访问时间 = TLB 查找时间 + 2 次内存访问（查页表 + 访问数据）

   • 求有效内存访问时间（Effective Memory Access Time, EMAT）

(a) 无 TLB 时，分页内存访问时间

在 无 TLB 的情况下，每次内存访问需要：

1. 查页表（1 次内存访问） → 50 ns
2. 访问目标数据（1 次内存访问） → 50 ns 因此，总时间 =PageTableLookup + MemoryAccess = 50ns + 50ns = 100ns

答案 (a)：无 TLB 时，分页内存访问时间为 100 ns。

(b) 有 TLB 时，有效内存访问时间（EMAT）

TLB 是一种缓存，用于加速页表查找。访问流程如下：

1. TLB 命中（75% 概率）

• TLB 查找（2 ns）→ 命中，直接得到物理地址
• 访问目标数据（1 次内存访问，50 ns） 总时间 =TLBLookup + MemoryAccess = 2ns + 50ns = 52ns

2. TLB 未命中（25% 概率）

• TLB 查找（2 ns）→ 未命中
• 查页表（1 次内存访问，50 ns）
• 访问目标数据（1 次内存访问，50 ns） 总时间 =TLBLookup + PageTableLookup + MemoryAccess = 2ns + 50ns + 50ns = 102ns

3. 计算有效内存访问时间（EMAT）

EMAT = (TLBHitRate × HitTime) + (TLBMissRate × MissTime)EMAT = (0.75 × 52ns) + (0.25 × 102ns) = 39ns + 25.5ns = 64.5ns

答案 (b)：有 TLB 时，有效内存访问时间为 64.5 ns

5. 在一个 固定多道程序度（degree of multiprogramming）为 4 的请求分页系统中，测量了 CPU 利用率 和 磁盘（分页磁盘）利用率，得到以下三种情况：

   1. (a) CPU 利用率 13%；磁盘利用率 97%
   2. (b) CPU 利用率 87%；磁盘利用率 3%
   3. (c) CPU 利用率 13%；磁盘利用率 3%

   问题：

   1. 每种情况下发生了什么？
   2. 能否通过增加多道程序度来提高 CPU 利用率？

情况	CPU 利用率	磁盘利用率	系统状态	能否增加多道程序度？
(a)	13%	97%	抖动（Thrashing）	❌ 不能，应减少
(b)	87%	3%	运行良好	⚠️ 可尝试增加，但需监控
(c)	13%	3%	进程数不足或 I/O 密集型	✅ 可以增加

关键结论

• 抖动（Thrashing） 发生时（高磁盘利用率 + 低 CPU 利用率），不能增加多道程序度，反而应该减少。
• 系统运行良好（高 CPU 利用率 + 低磁盘利用率）时，可以 谨慎增加 多道程序度，但需监控是否接近抖动阈值。
• CPU 和磁盘都空闲（低 CPU + 低磁盘）时，通常 可以增加多道程序度，以提高 CPU 利用率。

选择题

1. 首次适应算法的空白区是 _____ 。

A. 按大小递减顺序连在一起

B. 按地址由大到小排列

C. 按地址由小到大排列

D. 按大小递增顺序连在一起

2. 在分区存储管理中的拼接技术可以 _____ 。

A. 缩短访问周期 B. 增加内存容量

C.集中空闲区 D. 加速地址转换

3. 采用 _____ 不会产生内部碎片。

A.分页存储管理

B.固定分区存储管理

C.分段存储管理

D.段页式存储管理

4. 采用分段存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是 _____ 。

A. 2¹⁶ B. 2³² C. 2²⁴ D. 2⁸

5. 在固定分区分配中，每个分区的大小是 _____ 。

A.可以不同但预先固定

B.相同

C.随作业长度变化

D.可以不同但根据作业长度固定

6. 把作业地址空间使用的逻辑地址变成内存的物理地址称为 _____ 。

A.加载 B.重定位

C.物理化 D.逻辑化

7. 在以下存储管理方案中，不适用于多道程序设计系统的是 _____ 。

A.固定式分区分配 B.单一连续分配

C.可变式分区分配 D.页式存储管理

8. 在可变式分区分配方案中，某一作业完成后，系统收回其内存空间并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是 _____ 。

A.有下邻空闲区但无上邻空闲区

B.有上邻空闲区但无下邻空闲区

C.有上邻空闲区也有下邻空闲区

D.无上邻空闲区也无下邻空闲区

9. 采用两级页表的页式存储管理中，按给定的逻辑地址进行读写时，通常需访问主存的次数是_____ 。

A. 1次 B. 2次 C. 3次 D. 4次

10. 分页系统中的页面是_____。

A．用户感知的 B．操作系统感知的

C．编译程序感知的 D．链接装配程序感知的

11. 下述内存分配算法中，_____ 更易产生无法利用的小碎片。

A．首次适应算法 B．循环首次适应算法

C．最佳适应算法 D．最坏适应算法

12. 实现虚拟存储器的目的是 _____ 。

A. 实现存储保护 B. 实现程序浮动

C. 扩充辅存容量 D. 扩充内存容量

13. 页式虚拟存储管理的主要特点是 _____ 。

A. 不要求将作业装入到内存的连续区域

B. 不要求将作业同时全部装入到内存的连续区域

C. 不要求进行缺页中断处理

D. 不要求进行页面置换

14. 作业在执行中发生了缺页中断，经操作系统处理后，应让其执行 _____ 指令。

A. 被中断的前一条 B. 被中断的那条

C. 被中断的后一条 D. 启动时的第一条

15. 虚拟存储管理系统的基础是程序的 _____ 理论。

A. 局部性 B. 全局性

C. 动态性 D. 虚拟性

16. 在以下存储管理方案中，属于虚拟存储器管理的是 _____ 。

A. 可重定位分区分配 B. 分段存储管理

C. 请求分页存储管理 D. 段页式存储管理

17. 由于实现_____ 页面置换算法的成本高，通常使用一种近似的页面置换算法_____算法。

A.Optimal LRU B.LRU Clock

C.FCFS Clock D.Clock 改进的Clock

18. 会产生Belady异常现象的页面置换算法是_____。

A．最佳页面置换算法

B．先进先出页面置换算法

C．最近最久未使用置换算法

D．最少使用页面置换算法

19. 在请求分页存储管理系统中，下述_____策略是不适用的

A．固定分配局部置换 B．固定分配全局置换

C．可变分配全局置换 D．可变分配局部置换

20. 二次机会置换算法与简单时钟置换算法在决定淘汰哪一页时，都用到了_____。

A．快表 B．引用位

C．修改位 D．存在位

21. 请求段页式系统_____。

A．是以页为单位管理用户的虚空间，以段为单位管理内存空间。

B．是以段为单位管理用户的虚空间，以页为单位管理内存空间。

C．是以连续的内存区存放每个段。

D．为提高内存利用率，允许用户使用大小不同的页。

填空题

1. 在分区分配算法中，首次适应算法倾向于优先利用内存中的 低地址部分的空闲分区，从而保留了高地址部分的大空闲区。

2. 段页式存储管理中，是先将作业分段 ， 段内分页。分配以 页为单位。在不考虑使用联想存储器的情况下，执行程序时需要 3次访问内存，其中第 2次是查作业的页表。

3. 把作业装入内存中随即进行地址变换的方式称为静态重定位，而在作业执行期间，当访问到指令或数据时才进行地址变换的方式称为 动态重定位。

4. 三种不连续内存管理方式是：分页、分段和 段页式。

5. 分区存储管理可以分为：固定分区和动态分区。

6. 在请求页式存储管理系统中，常用的页面淘汰算法有：最佳置换算法（OPT），选择淘汰不再使用或最远的将来才使用的页；先进先出算法（FIFO），选择淘汰在内存驻留时间最长的页。

7. 程序运行时的局部性表现为： 时间局部性和空间局部性。

8. 虚拟存储器的特点是部分装入、按需调页、逻辑扩展内存、透明性。

9. 所谓虚拟存储器是指具有 请求调入 和 置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

10. 虚拟存储器的实现方法有三种请求分页、 请求分段和 段页式 。

11. 在请求页式系统中，当访问的页不在主存时，由缺页中断机制将该页调入内存；当主存无空闲块时，必须置换（或淘汰）一页。

考研题

1. 分区分配内存管理方式的主要保护措施是（）。

A、界地址保护 B、程序代码保护

C、数据保护 D、栈保护

2. 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长为（）。

A、2^8字节 B、2^16字节

**C、2^{24字节** D、2}32字节

3. 某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空），采用最佳适配算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小是

   A.7MB B.9MB C.10MB D.15MB

操作	空闲分区表（分配前）	分配/释放操作	空闲分区表（分配后）
初始	[55MB]	-	[55MB]
分配 15MB	[55MB]	从 55MB 中分配 15MB	[40MB]
分配 30MB	[40MB]	从 40MB 中分配 30MB	[10MB]
释放 15MB	[10MB]	释放 15MB	[10MB, 15MB]
分配 8MB	[10MB, 15MB]	从 10MB 中分配 8MB	[2MB, 15MB]
分配 6MB	[2MB, 15MB]	从 15MB 中分配 6MB	[2MB, 9MB]

4. 某计算机采用 二级页表 的分页存储管理方式，按字节编址，具体参数如下：

   • 页大小：2¹⁰ 字节（1KB）。
   • 页表项大小：2 字节。
   • 逻辑地址结构：页目录号 | 页号 | 页内偏移量。
   • 逻辑地址空间大小：2¹⁶ 页。

   问题：表示整个逻辑地址空间的 页目录表（一级页表） 中，包含的表项个数至少是多少？ ​​选项​​：A. 64 B. 128 C. 256 D. 512

解题步骤

1. 理解二级页表结构

• 二级页表 的地址转换流程：
  1. 根据 页目录号 查找页目录表（一级页表），获取二级页表的基址。
  2. 根据 页号 查找二级页表，获取物理页框号。
  3. 结合 页内偏移量 访问物理内存。
• 逻辑地址空间：
  • 总页数 = 216 页。
  • 每页大小 = 210 字节 → 逻辑地址空间总大小 = 216×210=226 字节（64MB）。

2. 计算页目录表的表项数

• 页目录表（一级页表） 的每个表项指向一个 二级页表。
• 关键问题：需要多少个二级页表才能覆盖 216 个逻辑页？

步骤：

1. 每个二级页表能映射多少页？
   • 页大小 = 210 字节，页表项大小 = 2 字节。
   • 每张二级页表的表项数 = 2210=29=512 项（即每张二级页表可映射 512 页）。
2. 需要的二级页表总数：
   • 总逻辑页数 = 216 页。
   • 每张二级页表映射 512 页 → 二级页表数量 = 29216=27=128 个。
3. 页目录表的表项数：
   • 页目录表需要 128 个表项（每个表项指向一个二级页表）。

3. 验证逻辑地址划分

• 逻辑地址结构：

  页目录号 | 页号 | 页内偏移量

  • 页内偏移量：10 位（210 字节页大小）。
  • 页号：9 位（每张二级页表 512 项，29）。
  • 页目录号：剩余位数 = 26 - 10 - 9 = 7 位 → 27=128 个表项。

第8章 文件系统

练习题

1. 解释open()和close()操作的作用。

• open()操作：用于打开一个资源（如文件、数据库连接等），使其可被访问或修改。例如，在文件操作中，open()会建立程序与文件之间的连接，返回一个文件对象供后续读写。
• close()操作：用于释放资源并终止与对象的连接。例如，关闭文件会确保数据写入磁盘并释放系统资源，避免内存泄漏或数据损坏。

2. 现有文件由100个块组成。假设文件控制块（以及索引分配的索引块）已在内存中。计算在以下情况下，连续分配、链接分配和单级索引分配策略所需的磁盘I/O操作次数（假设新增块的信息已在内存中）：
   • a. 在文件开头添加一个块
   • b. 在文件中间添加一个块
   • c. 在文件末尾添加一个块
   • d. 从文件开头删除一个块
   • e. 从文件中间删除一个块
   • f. 从文件末尾删除一个块

分配策略概述

1. 连续分配：文件块在磁盘上连续存储，需移动数据以腾出空间。
2. 链接分配：每个块包含指向下一个块的指针，无需移动数据，但需遍历链表。
3. 索引分配（单级）：索引块存储所有块的指针，修改索引块即可。

操作	连续分配	链接分配	索引分配
a. 开头添加块	101（移动全部块）	1（更新头指针+新块）	1（更新索引块）
b. 中间添加块	51（移动后半部分）	51（遍历到中间+更新指针）	1（更新索引块）
c. 末尾添加块	1（直接追加）	1（更新尾指针+新块）	1（更新索引块）
d. 开头删除块	0（仅更新FCB）	1（更新头指针）	1（更新索引块）
e. 中间删除块	49（移动后半部分）	51（遍历到中间+更新指针）	1（更新索引块）
f. 末尾删除块	0（仅更新FCB）	100（遍历到尾节点）	1（更新索引块）

选择题

1. 操作系统中对外存上的数据信息进行管理的部分叫做 _____ 。

A. 数据库系统 B. 文件系统

C. 检索系统 D. 数据存储系统

2. 文件系统中，打开文件（open）操作的功能是 。

A. 把文件信息从辅存读到内存

B. 把磁盘的超级块从辅存读到内存

C. 把文件的FAT表信息从辅存读到内存

D. 把文件的控制管理信息从辅存读到内存

3. 文件的绝对路径名是指 _____ 。

A. 文件名和文件扩展名

B. 一系列的目录文件名和该文件的文件名

C. 从根目录到该文件所经历的路径中各符号名的集合

D. 目录文件名和文件名的集合

4. 为了解决不同用户文件的“命名冲突”问题，通常在文件系统中采用 _____ 。

A. 约定的方法 B. 多级目录

C. 路径 D. 索引

5. 一个文件的相对路径名是从 _____ 开始，逐步沿着各级子目录追溯，最后到指定文件的整个通路上所有子目录名组成的一个字符串。

A. 当前目录 B. 根目录

C. 二级目录 D. 多级目录

6. 使用文件前必须先 ① 文件，文件使用完毕后应该 ② 。B，D

A. 建立 B. 打开

C. 命名 D. 关闭

7. 在文件系统中，文件的不同物理结构有不同的优缺点。在下列文件的物理结构中， ① 不具有直接读写文件任意一个记录的能力， ② 不利于文件长度动态增长。B，A

A. 顺序结构 B. 链接结构

C. 索引结构 D. Hash结构

8. 文件系统采用二级目录结构，这样可以 _____ 。

A. 缩短访问文件存储器时间

B. 实现文件共享

C. 解决不同用户之间的文件名冲突问题

D.节省主存空间

9. 常用的文件存取方法有两种：顺序存取和 _____ 存取。

A. 流式 B. 串联

C. 记录 D. 随机

10. 位示图可用于 _____ 。

A. 文件目录的查找

B. 磁盘空间的管理

C. 主存空间的共享

D. 实现文件的保护和保密

填空题

1. 索引文件大体上由 索引区和 数据区构成。
2. 逻辑文件有两种类型，即 流式文件与记录式文件。
3. 文件的物理组织有顺序结构、链接结构和索引结构。
4. 在文件系统中，要求物理块必须连续的物理文件是顺序文件。
5. 文件转储的方法有两种：全量转储和增量转储。
6. 文件的结构就是文件的组织形式，从用户观点出发所看到的文件组织形式称为文件的逻辑结构；从实现观点出发，文件在外存上的存放组织形式称为文件的物理结构。
7. 文件系统中若文件的物理结构采用连续结构，则文件控制块中关于文件的物理位置信息应包括文件的起始块号和 文件长度。
8. 二级目录结构通常由主文件目录（MFD）和各用户的 用户文件目录（UFD）组成。
9. 按用户对文件的存取权限将用户分为若干组，同时规定每一组用户对文件的访问权限。这样，所有用户组存取权限的集合称为该文件的访问控制表（ACL，Access Control List）。
10. 文件保护（File Protection）是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏。

考研题

1. 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件最大长度是 。

   A.33KB B. 519KB C. 1057KB D. 16613KB

解题步骤

1. 理解索引节点结构

索引节点（inode）用于存储文件的元数据，包括指向文件数据块的指针。题目中给出了7个地址项：

• 4个直接地址索引：直接指向数据块。
• 2个一级间接地址索引：指向一个索引块，该索引块中存储多个指向数据块的指针。
• 1个二级间接地址索引：指向一个索引块，该索引块中的指针指向其他索引块，这些索引块再指向数据块。

2. 计算每个地址项能指向的数据块数量

• 直接地址索引：每个直接指向一个数据块。
  • 4个直接地址索引 → 4个数据块。
• 一级间接地址索引：
  • 每个索引块大小为256字节，每个地址项（指针）大小为4字节。
  • 一个索引块可以存储的指针数量 = 256 / 4 = 64个。
  • 每个一级间接地址索引指向一个索引块，因此可以指向64个数据块。
  • 2个一级间接地址索引 → 2 × 64 = 128个数据块。
• 二级间接地址索引：
  • 二级间接索引的第一层是一个索引块，存储指向第二层索引块的指针。
  • 第二层每个索引块又可以指向64个数据块。
  • 因此，一个二级间接地址索引可以指向的数据块数量 = 64 × 64 = 4096个。
  • 1个二级间接地址索引 → 4096个数据块。

3. 计算总数据块数量

将直接、一级间接和二级间接索引指向的数据块数量相加：

• 直接：4块
• 一级间接：128块
• 二级间接：4096块
• 总数据块数量 = 4 + 128 + 4096 = 4228块。

4. 计算文件最大长度

• 每个数据块大小为256字节。
• 文件最大长度 = 总数据块数量 × 数据块大小 = 4228 × 256字节。

计算： 4228 × 256 = 4228 × (250 + 6) = 4228 × 250 + 4228 × 6 = 1,057,000 + 25,368 = 1,082,368字节。

转换为KB： 1,082,368字节 ÷ 1024 = 1057KB。

5. 验证选项

计算结果是1057KB，对应选项C。

2. 某文件系统空间的最大容量为4TB（1TB=2⁴⁰），以磁盘块为基本分配单元。磁盘块大小为1KB。文件控制块（FCB）包含一个512B的索引表区。请回答下列问题。

（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？

（2）假设索引表区采用如下结构：第0～7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间。其中起始块号占6B，块数占2B，剩余504字节采用直接索引结构，一个索引项占6B，则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

3. 下列文件物理结构中，适合随机访问且易于文件扩展的是（）

A、连续结构 C、链式结构且磁盘块定长

B、索引结构 D、链式结构且磁盘块变长

4. 设置当前工作目录的主要目的是 。

A. 节省外存空间 B. 节省内存空间

C. 加快文件的检索速度 D. 加快文件的读/写速度

5. 文件系统中，文件访问控制信息存储的合理位置是（）。

A、文件控制块 B、文件分配表

C、用户口令表 D、系统注册表

6. 设文件F1的当前连接计数为1，先建立F1的符号链接（软连接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时F2和F3的连接计数值分别是（）。

A、0、1 B、1、1

C、1、2 D、2、1

解析：

1. 初始状态：
   • F1的连接计数为1（仅自身指向inode）。
2. 建立符号链接F2：
   • 符号链接（软链接）是独立文件，不增加F1的连接计数。
   • F1的连接计数仍为1，F2的连接计数为1（指向自身）。
3. 建立硬链接F3：
   • 硬链接与F1共享inode，F1和F3的连接计数变为2。
4. 删除F1：
   • 删除F1后，其连接计数减1（从2→1），此时仅剩F3指向inode。
   • 符号链接F2仍存在，但指向已删除的F1（成为悬空链接），其连接计数仍为1（自身计数）。

关键点：

• 硬链接影响inode连接计数，符号链接不影响。
• 删除原文件后：
  • 硬链接F3仍有效（连接计数=1）。
  • 符号链接F2失效但计数不变（因它是独立文件）。

结论：F2=1（悬空），F3=1（选B）。

7. 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。

（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需在FCB中设计哪些相关字段？

（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

(1)在磁盘中连续存放(采取连续结构)，磁盘寻道时间更短，文件随机访问效率更高；在FCB中加入的字段为：<起始块号，块数>或者<起始块号，结束块号>。

(2)将所有FCB集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问FCB对应的块，可减少磁头移动和磁盘I/O访问的次数。

8. 若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是

Ⅰ.若该文件的数据不在内存，则该进程进入睡眠等待状态

Ⅱ.请求read系统调用会导致CPU从用户态切换到核心态

Ⅲ.read系统调用的参数应包括文件的名称

A.仅Ⅰ，Ⅱ B.仅Ⅰ，Ⅲ

C. 仅Ⅱ，Ⅲ D.Ⅰ，Ⅱ，Ⅲ

第9章 设备管理

练习题

一个磁盘驱动器有5000个柱面（编号0到4999）。当前磁头位于柱面2150，上一次请求的柱面是1805。待处理的请求队列（按FIFO顺序）为：

2069, 1212, 2296, 2800, 544, 1618, 356, 1523, 4965, 3681

需要计算以下磁盘调度算法下磁头移动的总距离（柱面数）：

1. FCFS（先来先服务）
2. SCAN（电梯算法）
3. C-SCAN（循环扫描）

1. FCFS（先来先服务）

• 规则：按请求到达的顺序依次处理。

• 移动顺序：从当前磁头位置2150开始，依次访问队列中的请求：

  2150 → 2069 → 1212 → 2296 → 2800 → 544 → 1618 → 356 → 1523 → 4965 → 3681

• 计算距离：

  • |2150 - 2069| = 81
  • |2069 - 1212| = 857
  • |1212 - 2296| = 1084
  • |2296 - 2800| = 504
  • |2800 - 544| = 2256
  • |544 - 1618| = 1074
  • |1618 - 356| = 1262
  • |356 - 1523| = 1167
  • |1523 - 4965| = 3442
  • |4965 - 3681| = 1284

• 总距离：81 + 857 + 1084 + 504 + 2256 + 1074 + 1262 + 1167 + 3442 + 1284 = 13011

2. SCAN（电梯算法）

• 规则：磁头沿一个方向移动，直到到达磁盘一端，然后反向移动。

• 初始方向：上一次请求是1805，当前是2150，说明磁头正在向外移动（从1805→2150，方向：增大）。

• 移动顺序：

  1. 向外移动（增大方向）处理所有≥2150的请求：

     2150 → 2296 → 2800 → 3681 → 4965（到达磁盘末端）

  2. 反向移动（减小方向）处理所有剩余请求：

     4965 → 3681 → 2069 → 1618 → 1523 → 1212 → 544 → 356

  • 注意：3681在向外移动时已处理，反向时不再重复计算。

• 计算距离：

  • 向外移动：
    • |2150 - 2296| = 146
    • |2296 - 2800| = 504
    • |2800 - 3681| = 881
    • |3681 - 4965| = 1284
  • 反向移动：
    • |4965 - 2069| = 2896
    • |2069 - 1618| = 451
    • |1618 - 1523| = 95
    • |1523 - 1212| = 311
    • |1212 - 544| = 668
    • |544 - 356| = 188

• 总距离：146 + 504 + 881 + 1284 + 2896 + 451 + 95 + 311 + 668 + 188 = 7424

3. C-SCAN（循环扫描）

• 规则：磁头沿一个方向移动到底后，立即返回磁盘起点，继续同一方向移动。

• 初始方向：向外移动（增大方向）。

• 移动顺序：

  1. 向外移动处理所有≥2150的请求：

     2150 → 2296 → 2800 → 3681 → 4965（到达末端）

  2. 立即返回到0（不处理请求）：

     4965 → 0

  3. 重新向外移动处理剩余请求：

     0 → 356 → 544 → 1212 → 1523 → 1618 → 2069

• 计算距离：

  • 向外移动：
    • |2150 - 2296| = 146
    • |2296 - 2800| = 504
    • |2800 - 3681| = 881
    • |3681 - 4965| = 1284
  • 返回：
    • |4965 - 0| = 4965
  • 重新向外移动：
    • |0 - 356| = 356
    • |356 - 544| = 188
    • |544 - 1212| = 668
    • |1212 - 1523| = 311
    • |1523 - 1618| = 95
    • |1618 - 2069| = 451

• 总距离：146 + 504 + 881 + 1284 + 4965 + 356 + 188 + 668 + 311 + 95 + 451 = 9849

---

最终答案

调度算法	总移动距离（柱面数）
FCFS	13011
SCAN	7424
C-SCAN	9849

DMA如何提高系统并发性？DMA如何使硬件设计复杂化？

1. 减轻CPU负担：
   • 传统I/O：CPU需要亲自处理数据搬运（如从磁盘到内存），导致频繁中断和上下文切换。
   • DMA（直接内存访问）：由DMA控制器（DMAC）直接管理I/O设备与内存的数据传输，CPU仅在传输开始和结束时介入，期间可执行其他任务。
2. 并行操作：
   • CPU计算与I/O传输可同时进行（如CPU处理已加载的数据，同时DMA加载下一批数据）。
3. 减少总线竞争：
   • DMA通过独占总线周期批量传输数据，比CPU逐字节操作更高效。

1. 硬件复杂性：
   • 需额外设计DMA控制器，并集成到主板或设备中（如磁盘控制器）。
2. 总线仲裁：
   • DMA与CPU可能竞争总线，需引入总线仲裁逻辑（如优先级机制）。
3. 缓存一致性：
   • DMA直接操作内存时，可能绕过CPU缓存，需硬件机制（如缓存嗅探）保证数据一致性。
4. 地址映射：
   • DMA需知晓物理地址，可能需MMU（内存管理单元）配合，避免访问非法内存区域。

为什么需要同步提升总线和设备速度？

1. 避免性能瓶颈：
   • CPU速度↑ → 处理能力↑，但若总线或设备速度不变，I/O成为瓶颈（如CPU等待慢速磁盘数据）。
   • 例：1GHz CPU + 100MB/s磁盘 → 磁盘拖累整体性能。
2. 平衡系统吞吐量：
   • 高速CPU需匹配高速总线（如PCIe 5.0）和存储设备（如NVMe SSD），否则资源利用率低下。
3. 减少等待时间：
   • 现代CPU采用多级流水线和超标量架构，停滞（stall）会大幅降低效率。快速I/O设备可减少等待。
4. 支持高并发：
   • 多核CPU需总线带宽足够分配（如16核CPU + 低带宽总线 → 核心争抢带宽）。

选择题

1. 缓冲技术中的缓冲池在 _____ 中。

A. 主存 B. 外存

C. ROM D. 寄存器

2. CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用_____ 。

A. 并行技术 B. 通道技术

C. 缓冲技术 D. 虚存技术

3. 通过硬件和软件的功能扩充，把原来独占的设备改造成能为若干用户共享的设备，这种设备称为 _____ 。

A. 存储设备 B. 系统设备

C. 用户设备 D. 虚拟设备

4. 为了使多个进程能有效地同时处理输入/输出，最好使用 _____ 结构的缓冲技术。

A. 循环缓冲 B. 缓冲池

C. 单缓冲 D. 双缓冲

5. 如果I/O设备与存储设备进行数据交换不经过CPU来完成，这种数据交换方式是 _____ 。

A. 程序查询 B. 中断方式

C. DMA方式 D. 无条件存取方式

6. 在采用Spooling 技术的系统中．用户的打印结果首先被送到 _____ 。

A. 磁盘固定区域 B. 内存固定区域

C. 终端 D. 打印机

7. 设备管理程序对设备的管理是借助一些数据结构来进行的，下面的 _____ 不属于设备管理数据结构。

A. DCT B. COCT

C. CHCT D. JCB

8. 操作系统中的Spooling技术，实质是将 _____ 转化为共享设备的技术。

A. 虚拟设备 B. 独占设备

C. 脱机设备 D. 块设备

9. 按 _____ 分类可将设备分为块设备和字符设备。

A. 从属关系 B. 操作特性

C. 共享属性 D. 信息交换单位

10. _____ 算法是设备分配常用的一种算法。

A. 短作业优先 B. 最佳适应

C. 先来先服务 D. 首次适应

11. 在下面关于设备属性的论述中，正确的论述是_____。　

A．字符设备的一个基本特征是可寻址的。

B．共享设备必须是可寻址的和可随机访问的设备。

C．共享设备是指在同一时刻，允许多个进程同时访问的设备。

D．在分配共享设备和独占设备时，都可能引起进程死锁。

12. 通道是一种特殊的___，具有执行I/O指令集的能力。

A．I/O设备　 　B．设备控制器

C．处理机　　 D．I/O控制器

13. 共享设备磁盘的物理地址为（柱面号，磁头号，扇区号），磁头从当前位置移动到需访问柱面所用的时间称为 ① ，磁头从访问的柱面移动到指定扇区所用时间称为 ② 。A，B

A. 寻道时间 B. 传输时间

C. 旋转等待时间 D. 周转时间

14. 若进程P1访问199号柱面，磁头是从0号柱面移到199柱面的，且在访问期间依次出现了P2申请读299号柱面，P3申请写209号柱面，P4申请读199号柱面，访问完199号柱面以后，如果采用：先来先服务算法，将依次访问 ① ；最短寻道时间优先算法，将依次访问 ② ；扫描算法，将依次访问 ③ 。B，D，C

A. 299，199，209 B. 299，209，199

C. 199，209，299 D. 209，199，299

1. 先来先服务（FCFS）

• 规则：按请求到达顺序处理。
• 请求顺序：P2（299）→ P3（209）→ P4（199）。
• 移动顺序：199（当前）→ 299 → 209 → 199。
• 对应选项：B（299, 209, 199）。

2. 最短寻道时间优先（SSTF）

• 规则：选择离当前磁头位置最近的请求。
• 计算距离：
  • 199 → 209（距离10）
  • 199 → 299（距离100）
  • 199 → 199（距离0，P4请求）
• 优先处理P4（199），但题目要求“访问完199号柱面以后”，因此跳过P4，选择最近的209：
  • 199 → 209 → 199（P4）→ 299。
• 注意：若P4在访问199后立即处理，顺序为199 → 199 → 209 → 299，但选项无此组合。最接近的是D（209, 199, 299）。

3. 扫描算法（SCAN，电梯算法）

• 规则：磁头单向移动到底后反向。
• 初始方向：从0→199，说明向外移动（增大方向）。
• 处理顺序：
  1. 向外：199 → 209 → 299（末端）。
  2. 反向：299 → 209 → 199（但已处理过209和199）。
• 实际顺序：199（当前）→ 209 → 299。
• 对应选项：C（199, 209, 299）。

关键点：

• FCFS严格按请求顺序，效率最低。
• SSTF优先最近请求，但可能导致饥饿。
• SCAN单向移动，公平性较好。

15. 存放在磁盘上的文件 _____ 。

A. 只能随机访问 B. 只能顺序访问

C. 既可随机访问，又可顺序访问

D. 不能随机访问

16. 用磁带作文件存储介质时，文件只能组织成 _____ 。

A. 目录文件 B. 链接文件

C. 索引文件 D. 顺序文件

填空题

1. 进行设备分配时所需的数据表格主要有设备控制表（DCT，Device Control Table）、 控制器控制表（COCT，Controller Control Table） 、通道控制表（CHCT，Channel Control Table）和 系统设备表（SDT，System Device Table） 。

2. 引起中断发生的事件称为中断源（Interrupt Source）。

3. 常用的I/O控制方式有程序直接控制方式、中断控制方式、DMA方式（Direct Memory Access）和通道控制方式（Channel Control）。

4. 通道是一个独立于 CPU的专管 I/O操作的处理器，它控制I/O设备与内存之间的信息交换。

5. SPOOLing系统是由磁盘中的 输入井（Input Spooling）和 输出井（Output Spooling） ，内存中的 输入缓冲区（Input Buffer） 和 输出缓冲区（Output Buffer），以及输入进程（Input Process）和输出进程（Output Process）所构成。

6. 设备分配程序分配外部设备时，先分配 设备（Device），再分配 控制器（Controller），最后分配 通道（Channel）。

7. 中断方式适合于低速设备（如键盘、鼠标），DMA方式适合于 高速设备（如磁盘、网卡） 。

8. 缓冲区的组织方式可分为 单缓冲（Single Buffer）、双缓冲（Double Buffer）、循环缓冲（Circular Buffer）和缓冲池。

9. 缓冲池中有三种类型的缓冲队列：空闲缓冲区队列（Empty Buffer Queue）、输入缓冲区队列（Input Buffer Queue）、输出缓冲区队列（Output Buffer Queue）。

10. 大多数设备控制器由三部分构成：设备接口（Device Interface）、控制器逻辑（Controller Logic）、 系统接口（System Interface）。

11. 活动头磁盘的访问时间包括寻道时间（Seek Time） 、旋转延迟时间（Rotational Latency）和 传输时间（Transfer Time）。

12. 最短寻道时间优先（SSTF，Shortest Seek Time First）算法选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。

考研题

1. 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（）。

A、逻辑设备名 B、物理设备名

C、主设备号 D、从设备号

2. 下列选项中，能引起外部中断的事件是（）。

A、键盘输入 B、除数为0

C、浮点运算下溢 D、访存缺页

3. 本地用户通过键盘登陆系统时，首先获得键盘输入信息的程序是 。

A.命令解释程序 B.中断处理程序

C.系统调用程序 D.用户登陆程序

4. 用户程序发出磁盘I/O请求后，系统的正确处理流程是______。

A、用户程序→系统调用处理程序→中断处理程序→设备驱动程序

B、用户程序→系统调用处理程序→设备驱动程序→中断处理程序

C、用户程序→设备驱动程序→系统调用处理程序→中断处理程序

D、用户程序→设备驱动程序→中断处理程序→系统调用处理程序

5. 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓存的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间是50μs。在单缓冲区及双缓冲区结构下，读入并分析完该文件的时间分别是____。

A、1500μs ，1000μs B、1550μs，1100μs

C、1550μs ，1550μs D、2000μs，2000μs

6. 中断处理和子程序调用都需要压栈保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）。

A．程序计数器 B.程序状态寄存器

C．通用数据寄存器 D.通用地址寄存器

7. 操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是()。

A、用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序

B、用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序

C、用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序

D、用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序

8. 假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问序列请求为35、45、12、68、110、180、170、195，采用SCAN算法得到的磁道访问序列为（）。

A、110、170、180、195、68、45、35、12

B、110、68、45、35、12、170、180、195

C、110、170、180、195、12、35、45、68

D、12、35、45、68、110、170、180、195

9. 下列选项中，不能改善磁盘I/O性能的是（）

   A．重排I/O请求次序

   B．在一个磁盘上设置多个分区

   C．预读和滞后写

   D．优化文件物理块的分布

10. 假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。

（1）请说明在上述条件下如何进行磁盘块空闲状态管理。

（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如图所示），磁道号请求队列为50，90，30，120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这个扇区点共需要多少时间？要求给出计算过程。

（3）如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。