2009 ~ 2019 年 408【操作系统】大题解析

2009 年

讲解视频推荐：【BOK408真题讲解-2009年（催更就退网版）】

1. 同步与互斥（7’）

三个进程 P1, P2, P3 互斥使用一个包含 N（N > 0）个单元的缓冲区。P1 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中；P2 每次用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数；P3 每次用 geteven() 从该缓冲区中取出一个偶数并用 counteven() 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。（要求用伪代码描述）

【解析】：

互斥资源：缓冲区只能互斥访问， 因此设置互斥信号量 mutex 。

同步问题：P1 、P2 因为奇数的放置与取用而同步，设同步信号量 odd ；P1 、P3 因为偶数的放置与取用而同步，设置同步信号量 even ；P1、P2、P3 因为共享缓冲区，设同步信号量 empty ，初值为 N 。程序如下：

2. 虚拟内存管理（8’）

请求分页管理系统中，假设某进程的页表内容如下表所示。

页号	页框（Page Frame）号	有效位（存在位）
0	101H	1
1		0
2	254H	1

页面大小为 4KB ，一次内存的访问时间为 100ns , 一次快表（TLB）的访问时间为 10ns ，处理一次缺页的平均时间为 108ns（已含更新 TLB 和页表的时间），进程的驻留集大小固定为 2 ，采用最近最少使用置换算法（LRU）和局部淘汰策略。

假设：① TLB 初始为空；② 地址转换时先访问 TLB ，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间） ；③ 有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后， 返回到产生缺页中断的指令处重新执行。设有虚地址访问序列：2362H 、1565H 、25A5H ，请问：
（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。
（2）基于上述访问序列，虚地址 1565H 的物理地址是多少？请说明理由。

【解析】：

2010 年

讲解视频推荐：【BOK408真题讲解-2010年】

1. 磁盘（7’）

假设计算机系统采用 CSCAN（循环扫描）磁盘调度策略，使用 2KB 的内存空间记录 16384 个磁盘块的空闲状态。
（1）请说明在上述条件下如何进行磁盘块空闲状态的管理。
（2）设某单面磁盘旋转速度为每分钟 6000 转，每个磁道有 100 个扇区，相邻磁道间的平均移动时间为 1ms 。若在某时刻，磁头位于 100 号磁道处，并沿着磁道号增大的方向移动（见下图），磁道号请求队列为 50, 90, 30, 120 ，对请求队列中的每个磁道需读取 1 个随机分布的扇区，则读完这 4 个扇区点共需要多少时间？要求给出计算过程。
（3）如果将磁盘替换为随机访问的 Flash 半导体存储器（如 U 盘、SSD 等） ，是否有比 CSCAN 更高效的磁盘调度策略？ 若有， 给出磁盘调度策略的名称并说明理由；若无，说明理由。

【解析】：

2. 虚拟内存管理（8’）

设某计算机的逻辑地址空间和物理地址空间均为 64KB ，按字节编址。若某进程最多需要 6 页（Page ）数据存储空间，页的大小为 1KB ，操作系统采用固定分配局部置换策略为此进程分配 4 个页框（Page Frame）。在时刻 260 前的该进程访问情况如下表所示（访问位即使用位）。

页号	页框号	装入时刻	访问位
0	7	130	1
1	4	230	1
2	2	200	1
3	9	160	1

当该进程执行到时刻 260 时， 要访问逻辑地址为 17CAH 的数据。请回答下列问题：

（1）该逻辑地址对应的页号是多少？
（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针沿顺时针方向移动，且当前指向 2 号页框，示意图如下） 。

【解析】：

2011 年

讲解视频推荐：【BOK408真题讲解-2011年】

1. 同步与互斥（8’）

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

cobegin{process 顾客 i{从取号机获取一个号码;等待叫号;获取服务;}process 营业员{while(TRUE){叫号;为客户服务;}}
}coend

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

【解析】：

2. 文件系统基础（7’）

某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块， 需要 FCB 中设计哪些相关描述字段？
（2）为快速找到文件，对于 FCB ，是集中存储好， 还是与对应的文件数据块连续存储好？要求说明理由。

【解析】：

2012 年

讲解视频推荐：【BOK408真题讲解-2012年】

1. 虚拟内存管理（7’）

某请求分页系统的局部页面置换策略如下：系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时， 如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中； 否则，从空闲页框链表头部取出一个页框。

假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为 32, 15, 21, 41 。进程 P 依次访问的 <虚拟页号，访问时刻> 是： <1, 1> ,＜3, 2>, <0, 4>, <0, 6>, <1, 11>, <0, 13>, <2, 14> 。请回答下列问题。

（1）访问 <0, 4> 时，对应的页框号是什么？
（2）访问 <1, 11> 时，对应的页框号是什么？说明理由。
（3）访问 <2, 14> 时，对应的页框号是什么？说明理由。
（4）该策略是否适合于时间局部性好的程序？说明理由。

【解析】：

2. 文件系统基础（8’）

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

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

【解析】：

2013 年

讲解视频推荐：【BOK408真题讲解-2013年】

1. 同步与互斥（7’）

某博物馆最多可容纳 500 人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：

cobegin{参观者进程 i:{…进门;…参观;…出门;}
}coend

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

【解析】：

出入口一次仅允许一个人通过， 设置互斥信号量 mutex ，初值为 1 。博物馆最多可同时容纳 500 人， 故设置信号量 empty ，初值为 500 。

Semaphore empty = 500;
Semaphore mutex = 1;
cobegin{参观者进程 i:{…P(empty);P(mutex);进门;V(mutex);参观;P(mutex);出门;V(mutex);V(empty);…}
}coend

2. 内存管理概念（8’）

某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题。
（1）若使用一级页表的分页存储管理方式， 逻辑地址结构如下：

页号（20 位）	页内偏移量（12 位）

则页的大小是多少字节？页表最大占用多少字节？
（2）若使用二级页表的分页存储管理方式，逻辑地址结构如下：

页目录号（10 位）	页表索引（10 位）	页内偏移量（12 位）

设逻辑地址为 LA ，请分别给出其对应的页目录号和页表索引的表达式。
（3）采用（1）中的分页存储管理方式， 一个代码段起始逻辑地址为 0000 8000H ，其长度为 8KB ，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增） 。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面 2 的起始物理地址。

【解析】：

2014 年

讲解视频推荐：【BOK408真题讲解-2014年】

1. 文件系统基础（6’）

文件 F 由 200 条记录组成，记录从 1 开始编号。用户打开文件后，欲将内存中的一条记录插入文件 F ，作为其第 30 条记录。请回答下列问题，并说明理由。

（1）若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件 F 存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块？F 的文件控制块内容会发生哪些改变？
（2）若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块？若每个存储块大小为 1KB ，其中 4 字节存放链接指针，则该文件系统支待的文件最大长度是多少？

【解析】：

2. 同步与互斥（9’）

系统中有多个生产者和多个消费者进程，共享一个能存放 1000 件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待； 当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出 10 件产品后，其他消费者进程才可以取产品。请使用信号量 P 、V [wait() 和 signal()] 操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。

【解析】：

2015 年

讲解视频推荐：【BOK408真题讲解-2015年】

1. 同步与互斥（9’）

有 A 、B 两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设 A 的信箱最多放 M 个邮件，B 的信箱最多放 N 个邮件。初始时 A 的信箱中有 x 个邮件（0 < x < M），B 的信箱中有 y 个（0 < y < N）。辩论者每取出一个邮件，邮件数减 1 。A 和 B 两人的操作过程描述如下：

当信箱不为空时， 辩论者才能从信箱中取邮件，否则需要等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则需要等待。请添加必要的信号量和 P 、V（或 wait 、signal）操作，以实现上述过程的同步。要求写出完整过程，并说明信号量的含义和初值。

【解析】：

2. 虚拟内存管理（6’）

某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：

页目录号（10 位）	页表索引（10 位）	页内偏移量（12 位）

请回答下列问题。
（1）页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？
（2）假定页目录项和页表项均占 4 字节，则进程的页目录和页表共占多少页？要求写出计算过程。
（3）若某指令周期内访问的虚拟地址为 0100 0000H 和 0111 2048H ，则进行地址转换时共访问多少个二级页表？要求说明理由。

【解析】：

2016 年

讲解视频推荐：【BOK408真题讲解-2016年】

1. 处理机调度（6’）

某进程调度程序采用基于优先数（priority）的调度策略， 即选择优先数最小的进程运行，进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数， 引入运行时间 cpuTime 和等待时间 waitTime ，初值均为 0 。进程处于执行态时，cpuTime 定时加 1 ，且 waitTime 置 0 ；进程处于就绪态时，cpuTime 置 0 ，waitTime 定时加 1 。请回答下列问题。

（1）若调度程序只将 nice 的值作为进程的优先数，即 priority = nice ，则可能会出现饥饿现象，为什么？
（2）使用 nice 、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用。

【解析】：

2. 文件系统基础（9’）

某磁盘文件系统使用链接分配方式组织文件，簇大小为 4KB 。目录文件的每个目录项包括文件名和文件的第一个簇号， 其他簇号存放在文件分配表 FAT 中。

（1）假定目录树如下图所示， 各文件占用的簇号及顺序如下表所示，其中 dir 、dir1 是目录，file1 、file2 是用户文件。请给出所有目录文件的内容。

（2）若 FAT 的每个表项仅存放簇号， 占 2 字节，则 FAT 的最大长度为多少字节？该文件系统支待的文件长度最大是多少？
（3）系统通过目录文件和 FAT 实现对文件的按名存取，说明 file1 的 106 、108 两个簇号分别存放在 FAT 的哪个表项中。
（4）假设仅 FAT 和 dir 目录文件已读入内存，若需将文件 dir / dir1 / file1 的第 5000 个字节读入内存， 则要访问哪几个簇？

【解析】：

2017 年

讲解视频推荐：【BOK408真题讲解-2017年】

1. 虚拟内存管理（7’）

假定题 44 给出的计算机 M 采用二级分页虚拟存储管理方式， 虚拟地址格式如下：

页目录号（10 位）	页表索引（10 位）	页内偏移量（12 位）

请针对题 43 的函数 f1 和题 44 中的机器指令代码， 回答下列问题。

int f1(unsigned n){int sum = 1, power = 1;for(unsigned i = 0; i <= n-1; i++) {power *= 2;sum += power;}return sum;
}

（1）函数 f1 的机器指令代码占多少页？
（2）取第 1 条指令（push ebp）时， 若在进行地址变换的过程中需要访问内存中的页目录和页表， 则会分别访问它们各自的第几个表项（编号从 0 开始） ？
（3）M 的 I/O 采用中断控制方式。若进程 P 在调用 f1 之前通过 scanf() 获取 n 的值，则在执行 scanf() 的过程中，进程 P 的状态会如何变化？ CPU 是否会进入内核态？

【解析】：

2. 同步与互斥（8’）

某进程中有 3 个并发执行的线程 thread1 、thread2 和 thread3 ，其伪代码如下所示。

请添加必要的信号量和 P 、V [或 wait() 、signal()] 操作，要求确保线程互斥访问临界资源，并且最大限度地并发执行。

【解析】：

2018 年

讲解视频推荐：【BOK408真题讲解-2018年】

1. 虚拟内存管理（8’）

请根据题 44 图给出的虚拟存储管理方式， 回答下列问题。

（1）某虚拟地址对应的页目录号为 6 ，在相应的页表中对应的页号为 6 ，页内偏移量为 8 ，该虚拟地址的十六进制表示是什么？
（2）寄存器 PDBR 用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR 的内容是否会变化？说明理由。同一进程的线程切换时，PDBR 的内容是否会变化？说明理由。
（3）为了支持改进型 CLOCK 置换算法，需要在页表项中设置哪些字段？

【解析】：

2. 文件系统基础（7’）

某文件系统采用索引节点存放文件的属性和地址信息，簇大小为 4KB 。每个文件索引节点占 64B ，有 11 个地址项，其中直接地址项 8 个， 一级、二级和三级间接地址项各 1 个，每个地址项长度为 4B 。请回答下列问题。

（1）该文件系统能支持的最大文件长度是多少？ （给出计算表达式即可。）
（2）文件系统用 1M（1M = 2²⁰）个簇存放文件索引节点， 用 512M 个簇存放文件数据。若一个图像文件的大小为 5600B ，则该文件系统最多能存放多少个图像文件？
（3）若文件 F1 的大小为 6KB ，文件 F2 的大小为 40KB ，则该文件系统获取 F1 和 F2 最后一个簇的簇号需要的时间是否相同？为什么？

【解析】：

（1）簇大小为 4KB ，每个地址项长度为 4B ，故每簇有 4KB / 4B = 1024 个地址项。最大文件

2019 年

讲解视频推荐：【BOK408真题讲解-2019年】

1. 同步与互斥（8’）

有 n（n ≥ 3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m（m ≥ 1）个碗，每两位哲学家之间有 1 根筷子。每位哲学家必须取到一个碗和两侧的筷子后， 才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐， 且防止出现死锁现象，请使用信号量的 P 、V 操作 [wait() 、signal() 操作］描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

【解析】：

semaphore bowl;		//信号量，用于协调哲学家对碗的使用
semaphore chopsticks[n];	//用于协调哲学家对筷子的使用
for(int i = 0; i < n; i++){chopsticks.value = 1;}	//设置两个哲学家之间筷子的数量
bowl.value = min(n-1, m);	//bowl.value ≤ n-1 ，确保不死锁
CoBegin{while(TRUE){	//哲学家 i 的程序思考;P(bowl);			//取碗P(chopsticks[i]);	//取左边筷子P(chopsticks[(i+1) MOD n]);	//取右边筷子就餐;V(chopsticks[i]);V(chopsticks[(i+1) MOD n]);V(bowl);}
}CoEnd

回顾传统的哲学家问题，假设餐桌上有 n 个哲学家、n 根筷子，那么可以用这种方法避免死锁：限制至多允许 n-1个哲学家同时 “抢” 筷子，那么至少会有 1 个哲学家可以获得两根筷子并顺利进餐，于是不可能发生死锁的情况。本题可以用碗这个限制资源来避免死锁:当碗的数量 m 小于哲学家的数量 n 时，可以直接让碗的资源量等于 m ，确保不会出现所有哲学家都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量 m 大于或等于哲学家的数量 n 时，为了让碗起到同样的限制效果，我们让碗的资源量等于 n-1 ，这样就能保证最多只有 n-1 个哲学家同时进餐，所以得到碗的资源量为 min{n-1, m} 。在进行 PV 操作时，碗的资源量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行 P 操作。

2. 磁盘（7’）

某计算机系统中的磁盘有 300 个柱面， 每个柱面有 10 个磁道， 每个磁道有 200 个扇区， 扇区大小为 512B 。文件系统的每个簇包含 2 个扇区。请回答下列问题：

（1）磁盘的容量是多少？
（2）假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为 100260 、60005 、101660 和 110560 。若采用最短寻道时间优先（SSTF）调度算法， 则系统访问簇的先后次序是什么？
（3）第 100530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 I/O 系统的什么程序完成的？

【解析】：

（1）磁盘容量 = (300 × 10 × 200 × 51 2/ 1024) KB = 3×10⁵KB

磁盘容量 = 磁盘的柱面数 × 每个柱面的磁道数 × 每个磁道的扇区数 × 每个扇区的大小。

（2）依次访问的簇是 100260 、101660 、110560 、60005 。

对 SSTF 算法而言，总是访问离当前柱面最近的地址。每个簇包含 2 个扇区，通过计算得到 85 号柱面对应的簇号为 85000 - 85999 。通过比较得出，最先访问离 85000 - 85999 最近的 100260 ，随后访问离 100260 最近的 101660 ，然后访问 110560 ，最后访问 60005 。

（3）第 100530 簇在磁盘上的物理地址由其所在的柱面号、磁头号、区号构成。
其所在的柱面号为 ⌊100530 ÷ (10 × 200 / 2)⌋ = 100 。
100530 % (10 × 200 / 2) = 530 ，磁头号为 ⌊530 ÷ (200 / 2)⌋ = 5 。
扇区号为 (530 × 2) % 200 = 60 。
将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。

柱面号 = ⌊簇号 / 每个柱面的簇数⌋
磁头号 = ⌊(簇号 % 每个柱面的簇数) / 每个磁道的簇数⌋
扇区号 = 扇区地址 % 每个磁道的扇区数