# 操作系统期末复习 ## 一、名词解释 | 名词 | 解释 | |---|---| | 操作系统 | 管理计算机硬件和软件资源、控制程序运行，并为用户和应用程序提供服务接口的系统软件。 | | 操作系统的目标 | 提高系统的方便性、有效性、可扩充性和开放性，使用户更方便地使用计算机，并提高资源利用率。 | | 进程 | 程序在某个数据集合上的一次运行过程，是系统进行资源分配和调度的基本单位。 | | 线程 | 进程中的一个执行流，是处理机调度的基本单位，同一进程内的线程共享该进程的资源。 | | 进程控制块 | 简称 PCB，是操作系统为管理进程而设置的数据结构，保存进程状态、标识、调度信息和资源信息等。 | | 原语 | 由操作系统内核提供的、执行过程中不可被中断的操作。 | | 作业周转时间 | 作业从提交到完成所经历的全部时间。公式：周转时间 = 完成时间 - 提交时间。 | | 作业带权周转时间 | 作业周转时间与实际运行时间的比值。公式：带权周转时间 = 周转时间 / 运行时间。 | | 响应比 | 等待时间加服务时间后与服务时间的比值。公式：响应比 =（等待时间 + 服务时间）/ 服务时间。 | | Bernstein 条件 | 判断程序段能否并发执行的条件。若不存在读写冲突和写写冲突，则可并发执行。 | | 并发 | 多个程序在同一时间段内交替执行，宏观上像同时运行。 | | 并行 | 多个程序在同一时刻真正同时执行，通常需要多处理器或多核心支持。 | | 临界区 | 进程中访问临界资源的代码段。 | | 临界资源 | 一次只允许一个进程访问的共享资源。 | | 信号量 | 用于进程同步和互斥的机制，通常配合 P、V 操作使用。 | | 死锁 | 多个进程因竞争资源而互相等待，导致都无法继续执行的状态。 | | 死锁定理 | 系统处于死锁状态的充分必要条件是资源分配图中存在不可完全简化的环路。 | | 静态地址重定位 | 程序装入内存时一次性完成逻辑地址到物理地址的转换，运行期间地址不再改变。 | | 动态地址重定位 | 程序运行过程中由硬件地址转换机构完成逻辑地址到物理地址的转换。 | | 逻辑地址空间 | 程序中使用的地址集合，也称虚拟地址空间。 | | 物理地址空间 | 内存中真实物理单元的地址集合。 | | 虚拟内存 | 把主存和辅存结合起来，使程序认为自己拥有比实际内存更大的地址空间。 | | 程序局部性原理 | 程序执行时短时间内倾向于集中访问某些代码和数据，包括时间局部性和空间局部性。 | | 外页表 | 当页表较大时，将暂时不用的页表部分存放在外存中，需要时再调入内存。 | | 缺页中断率 | 缺页中断次数占页面访问总次数的比例。公式：缺页中断率 = 缺页次数 / 页面访问总次数。 | ## 二、简答题解答 ### 1. 多道程序设计处理器使用效率提高的图形分析 多道程序设计通过把多个作业同时装入内存，使它们交替占用 CPU 和 I/O 设备。当某个程序因等待 I/O 而不能继续执行时，CPU 不必空闲，可以切换去执行另一个就绪程序。这样可以减少 CPU 空闲时间，提高处理器利用率。 ### 2. 通道和中断技术解决了多道程序设计系统的什么问题？ 通道和中断技术解决了 CPU 与外设速度不匹配的问题，使 CPU 与 I/O 设备能够并行工作。CPU 启动 I/O 后可转去执行其他程序，I/O 完成后通过中断通知 CPU，从而减少 CPU 等待时间，提高处理器利用率和系统吞吐量。 ### 3. 进程三态模型：画图，并解释不存在的弧的原因(同第四题) 进程三态包括： - 就绪态：进程已具备运行条件，只等待 CPU。 - 运行态：进程正在 CPU 上执行。 - 阻塞态：进程因等待某事件或资源而不能运行。 ![操作系统期末复习-i40pmg2](/images/操作系统期末复习-i40pmg2.webp) ### 4. 五态模型：画图，并解释不存在的弧的原因 进程五态包括： - 创建态：进程正在被创建，尚未进入就绪队列。 - 就绪态：进程具备运行条件，等待 CPU。 - 运行态：进程正在执行。 - 阻塞态：进程等待事件或资源。 - 终止态：进程执行结束或被撤销。 主要转换关系： - 创建态 → 就绪态：进程创建完成。 - 就绪态 → 运行态：被调度。 - 运行态 → 就绪态：时间片用完或被抢占。 - 运行态 → 阻塞态：等待 I/O 或事件。 - 阻塞态 → 就绪态：等待事件完成。 - 运行态 → 终止态：进程正常结束或异常终止。 不存在的弧： - 就绪态不能直接到阻塞态，因为进程未运行，不能主动等待事件。 - 阻塞态不能直接到运行态，因为事件完成后要先进入就绪队列。 - 创建态不能直接到运行态，因为创建完成后还要等待调度。 - 阻塞态不能直接到终止态，通常需要先被唤醒或由系统撤销处理。 --- ### 5. 并发进程中与时间相关的错误分析 并发进程中与时间相关的错误，是指多个并发进程访问共享资源时，由于进程执行速度和调度顺序不确定，使程序运行结果依赖于时间先后而产生的错误。其主要原因是多个进程同时进入临界区，对共享变量或共享资源进行非互斥访问，造成数据不一致。解决方法是对临界区进行互斥控制，如使用信号量、PV 操作、互斥锁或管程等机制，保证同一时刻只有一个进程访问共享资源。 ### 6. 信号量与 PV 操作伪代码 信号量是用于进程同步和互斥的一种机制，只能通过 P、V 原语操作。P 操作表示申请资源，使信号量减 1，若结果小于 0，则进程阻塞；V 操作表示释放资源，使信号量加 1，若结果小于等于 0，则唤醒一个等待进程。利用信号量可以实现临界区互斥和进程同步。互斥问题通常设置 mutex = 1，同步问题通常设置同步信号量初值为 0。 P 操作: ```c P(S) { S = S - 1; if (S < 0) { 阻塞当前进程; 将当前进程加入 S 的等待队列; } } ``` V 操作: ```c V(S) { S = S + 1; if (S <= 0) { 从 S 的等待队列中唤醒一个进程; } } ``` ### 7. 证明层次化分配策略可以预防死锁：反证法 层次化分配策略规定所有资源按层次编号，进程必须按资源编号递增的顺序申请资源。用反证法证明：假设系统仍发生死锁，则必然存在一组进程形成循环等待。设进程 P1 占有 R1 等待 R2，P2 占有 R2 等待 R3，……，Pn 占有 Rn 等待 R1。由于进程只能按编号递增申请资源，所以有 R1 < R2 < ... < Rn < R1，这显然矛盾。因此系统不可能形成循环等待，层次化分配策略可以预防死锁。 ### 8. 证明按序分配策略可以预防死锁：反证法 按序分配策略规定系统中所有资源统一编号，进程必须按资源编号递增的顺序申请资源。用反证法证明：假设采用该策略后仍发生死锁，则一定存在循环等待。设 P1 占有 R1 等待 R2，P2 占有 R2 等待 R3，……，Pn 占有 Rn 等待 R1。由于进程只能按编号递增申请资源，所以有 R1 < R2 < ... < Rn < R1，矛盾。因此不可能形成循环等待，按序分配策略可以预防死锁。 ### 9. 为什么提出分页、分段、段页式存储管理？ 提出分页、分段和段页式存储管理，是为了解决连续分配方式中的内存利用率低、碎片严重、程序装入困难和逻辑结构不清晰等问题。 分页管理： - 把逻辑地址空间和物理内存划分为大小相等的页和块。 - 程序可以离散装入内存。 - 主要优点是减少外部碎片，提高内存利用率。 分段管理： - 按程序逻辑结构划分，如代码段、数据段、栈段。 - 便于共享、保护和动态链接。 - 缺点是可能产生外部碎片。 段页式管理： - 先分段，再把每段分页。 - 既保留分段的逻辑清晰性，又具有分页离散分配的优点。 --- ### 10. 页面大小为什么设计成二的整数次幂？ 页面大小设计成二的整数次幂，是为了方便地址划分和硬件地址转换。 如果页面大小为 2^k，那么逻辑地址的低 k 位可以直接作为页内偏移量，高位作为页号。 例如页面大小为 4KB，即 2^12B，则逻辑地址低 12 位就是页内偏移量，其余高位就是页号。 这样设计的优点： - 不需要复杂的除法运算。 - 页号和页内偏移可以直接由二进制位划分。 - 硬件实现简单。 - 地址转换速度快。 --- ### 11. 为什么说分段式存储管理中的程序逻辑地址是二维地址？ 分段式存储管理按照程序的逻辑结构划分地址空间，一个逻辑地址由 **段号** 和 **段内偏移量** 两部分组成。 段号表示访问哪一个段，段内偏移量表示访问该段中的具体位置。 也就是说，访问一个地址时，需要先确定“哪一段”，再确定“段内的哪个位置”。 因此，分段式存储管理中的逻辑地址是二维地址。 分页中的页号和页内偏移是系统按固定大小自动划分的，主要面向物理管理；而分段中的段号反映程序逻辑结构，对用户更可见。 --- ### 12. 多级页表相关问题 多级页表是为了解决页表过大、占用连续内存空间困难的问题。 在一级页表中，如果逻辑地址空间很大，页表项数量也很大，整个页表会占用大量连续内存。 多级页表的思想是：把页表本身再分页，形成页目录和页表的层次结构。 以二级页表为例，逻辑地址通常分为： - 页目录号 - 页表项号 - 页内偏移量 地址转换过程： 1. 根据页目录号找到对应页表。 2. 根据页表项号找到物理块号。 3. 物理块号加页内偏移量形成物理地址。 优点： - 页表不必连续存放。 - 没用到的页表可以不调入内存。 - 节省内存空间，适合大地址空间。 缺点： - 地址转换次数增加。 - 访问内存次数可能变多。 - 通常需要快表 TLB 提高访问速度。 ### 13.处理机调度问题 先来先服务算法是按作业或进程到达系统的先后顺序进行调度，先到达的先执行。该算法简单公平，但容易使短作业等待时间过长，平均周转时间可能较大。 最短作业优先算法是从后备队列或就绪队列中选择运行时间最短的作业优先执行。该算法可以有效降低平均等待时间和平均周转时间，但对长作业不利，可能产生饥饿现象。 响应比最高优先算法是在每次调度时计算各作业的响应比，选择响应比最高的作业投入运行。响应比等于作业等待时间加要求服务时间之和除以要求服务时间。该算法综合考虑了等待时间和运行时间，既照顾短作业，又避免长作业长期等待。 ## 三、大题 ### 理发师问题 >[!question] >理发店有一个理发师、一把理发椅和 n 个等待座位。没有顾客时，理发师睡觉；顾客到来时，如果有空座位就等待，否则离 >开。理发师被顾客唤醒后为顾客理发。 ```c semaphore customers = 0; // 等待理发的顾客数 semaphore barber = 0; // 理发师是否准备好 semaphore mutex = 1; // 互斥访问 waiting int waiting = 0; // 当前等待顾客数 int n; // 等待椅子数量 barber_process() { while (1) { P(customers); // 没有顾客则睡觉 P(mutex); waiting--; // 叫一个顾客来理发 V(barber); // 理发师准备好 V(mutex); 理发; } } customer_process() { P(mutex); if (waiting < n) { waiting++; V(customers); // 通知理发师有顾客 V(mutex); P(barber); // 等待理发师准备好 接受理发; } else { V(mutex); 离开; } } ``` ### 和尚打水水问题 >[!question] >水缸最多能装 n 桶水。小和尚负责从井中打水并倒入水缸，老和尚从水缸中取水喝。水缸满时小和尚不能倒水，水缸空时老和尚不能喝水。井和水缸都属于临界资源，需要互斥访问。 ```c semaphore empty = n; // 水缸中还能放多少桶水 semaphore full = 0; // 水缸中已有多少桶水 semaphore mutex = 1; // 互斥访问水缸 semaphore well = 1; // 互斥访问井 young_monk() { while (1) { P(empty); // 水缸满则等待 P(well); 从井中打一桶水; V(well); P(mutex); 倒入水缸; V(mutex); V(full); // 水缸中水增加 } } old_monk() { while (1) { P(full); // 水缸空则等待 P(mutex); 从水缸取一桶水; V(mutex); V(empty); // 水缸空位增加 喝水; } } ``` --- ### 读者写者问题 >[!question] >多个读者可以同时读同一文件，但写者写文件时，不能有其他读者或写者访问文件。即读读可以并发，读写互斥，写写互斥。 ```c semaphore rw = 1; // 控制读写互斥 semaphore mutex = 1; // 互斥访问 readcount int readcount = 0; // 当前读者数量 reader() { while (1) { P(mutex); readcount++; if (readcount == 1) { P(rw); // 第一个读者阻止写者进入 } V(mutex); 读文件; P(mutex); readcount--; if (readcount == 0) { V(rw); // 最后一个读者释放文件 } V(mutex); } } writer() { while (1) { P(rw); 写文件; V(rw); } } ``` --- ### 抽烟者问题 >[!question] >有三个抽烟者，分别拥有烟草、纸、胶水。每个抽烟者还需要另外两种材料才能抽烟。供应者每次随机放出两种材料，拥有第三种材料的抽烟者取走材料并抽烟。 ```c semaphore offer_tobacco = 0; // 通知拥有烟草者 semaphore offer_paper = 0; // 通知拥有纸者 semaphore offer_glue = 0; // 通知拥有胶水者 semaphore finish = 1; // 抽烟完成后供应者才能继续放材料 provider() { while (1) { P(finish); 随机放两种材料; if (放纸和胶水) { V(offer_tobacco); // 拥有烟草者可以抽烟 } else if (放烟草和胶水) { V(offer_paper); // 拥有纸者可以抽烟 } else if (放烟草和纸) { V(offer_glue); // 拥有胶水者可以抽烟 } } } smoker_tobacco() { while (1) { P(offer_tobacco); 取纸和胶水; 抽烟; V(finish); } } smoker_paper() { while (1) { P(offer_paper); 取烟草和胶水; 抽烟; V(finish); } } smoker_glue() { while (1) { P(offer_glue); 取烟草和纸; 抽烟; V(finish); } } ``` --- ### 吃水果问题 >[!question] >桌上有一个盘子，每次只能放一个水果。父亲放苹果，母亲放橘子，女儿吃苹果，儿子吃橘子。盘子空时才能放水果，有对应水果时对应的人才能吃。 ```c semaphore plate = 1; // 盘子是否为空 semaphore apple = 0; // 盘子中是否有苹果 semaphore orange = 0; // 盘子中是否有橘子 father() { while (1) { P(plate); 放苹果; V(apple); } } mother() { while (1) { P(plate); 放橘子; V(orange); } } daughter() { while (1) { P(apple); 吃苹果; V(plate); } } son() { while (1) { P(orange); 吃橘子; V(plate); } } ``` --- ### 生产者消费者问题 >[!question] >生产者向缓冲区放入产品，消费者从缓冲区取出产品。缓冲区有 n 个位置。缓冲区满时生产者不能放，缓冲区空时消费者不能取。生产者和消费者访问缓冲区时必须互斥。 ```c semaphore empty = n; // 空缓冲区数量 semaphore full = 0; // 满缓冲区数量 semaphore mutex = 1; // 互斥访问缓冲区 producer() { while (1) { 生产产品; P(empty); // 申请空缓冲区 P(mutex); // 进入临界区 放入产品; V(mutex); // 退出临界区 V(full); // 满缓冲区数量加 1 } } consumer() { while (1) { P(full); // 申请产品 P(mutex); // 进入临界区 取出产品; V(mutex); // 退出临界区 V(empty); // 空缓冲区数量加 1 消费产品; } } ``` --- ### 哲学家就餐问题：Token 完美解 >[!question] >五个哲学家围坐在圆桌旁，每人左右各有一根筷子。哲学家必须同时拿到左右两根筷子才能吃饭。若每个哲学家都先拿左边筷子，再等待右边筷子，可能发生死锁。利用 token 信号量，只允许最多四个哲学家同时尝试拿筷子，从而避免死锁。 ```c semaphore chopstick[5] = {1, 1, 1, 1, 1}; // 五根筷子 semaphore token = 4; // 最多允许四人同时拿筷子 philosopher(int i) { while (1) { 思考; P(token); // 申请进入就餐竞争 P(chopstick[i]); // 拿左筷子 P(chopstick[(i + 1) % 5]); // 拿右筷子 吃饭; V(chopstick[(i + 1) % 5]); // 放右筷子 V(chopstick[i]); // 放左筷子 V(token); // 释放就餐资格 } } ``` --- ### PV 操作常用模板 >[!question] >PV 操作常用于解决并发进程中的同步与互斥问题。P 操作表示申请资源，V 操作表示释放资源。 ```c // 互斥问题模板 semaphore mutex = 1; P(mutex); 临界区; V(mutex); ``` ```c // 同步问题模板：要求 A 先执行，B 后执行 semaphore S = 0; process_A() { A操作; V(S); } process_B() { P(S); B操作; } ``` ```c // 生产者消费者模型模板 semaphore empty = n; semaphore full = 0; semaphore mutex = 1; producer() { P(empty); P(mutex); 放入资源; V(mutex); V(full); } consumer() { P(full); P(mutex); 取出资源; V(mutex); V(empty); } ``` ### 分页|分段|段页式存储管理 分页存储管理把逻辑地址空间划分为大小相等的页，把内存划分为大小相等的块，逻辑地址由页号和页内偏移组成，通过页表查出物理块号，再由块号和页内偏移形成物理地址。分页优点是内存利用率高、无外部碎片，缺点是有内部碎片且需要页表。 分段存储管理按照程序逻辑结构划分地址空间，逻辑地址由段号和段内偏移组成，通过段表查出段基址和段长，若段内偏移超过段长则为非法地址，否则物理地址等于段基址加段内偏移。分段优点是便于共享和保护，缺点是容易产生外部碎片。 段页式存储管理先把程序分段，再把每段分页，逻辑地址由段号、段内页号和页内偏移组成。地址转换时先查段表，再查页表，最后得到物理块号并形成物理地址。它兼有分段和分页的优点，但地址转换复杂，系统开销较大。 --- > 作者: 房子 > URL: https://fzcy.net/posts/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E6%9C%9F%E6%9C%AB%E5%A4%8D%E4%B9%A0/