961题库 北航计算机 操作系统 附答案 简答题形式

有题目和答案，没有解析，不懂的题问大模型即可，无偿分享。

第1组

习题

1. 某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200个扇区，扇区大小为 512B。文件系统的每个簇（或称数据块）包含 2 个扇区，且同一柱面相邻磁道的簇号存在相邻情况。请回答下列问题：
   （1）磁盘的容量是多少？
   （2）假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为 100260, 60005, 101660 和 110560。若采用最短寻道时间优先（SSTF）调度算法，则系统访问簇的先后次序是什么？
   （3）第 100530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 I/O 系统的什么程序完成的？

2. 某文件系统采用索引结点（或可理解为索引表）存放文件的属性和地址信息，簇大小为 4KB。每个文件索引结点占 64B，有 11 个地址项，其中直接地址项 8 个，一级、二级和三级间接地址项各1 个，每个地址项长度为 4B。请回答下列问题。
   （1）该文件系统能支持的最大文件长度是多少？（给出计算表达式即可。）
   （2）文件系统用 $1M（1M=2^{20}）$个簇存放文件索引结点，用 512M 个簇存放文件数据。若一个图像文件的大小为 5600B，则该文件系统最多能存放多少个图像文件？
   （3）若文件 F1 的大小为 6KB，文件 F2 的大小为 40KB，则该文件系统获取 F1 和 F2 最后一个簇的簇号需要的时间是否相同？为什么？

答案

1. 1）$磁盘容量=磁盘的柱面数每个柱面的磁道数\times 每个磁道的扇区数\times 每个扇区的大小=(300\times 10\times 200\times 512/1024)KB=3\times 10^{5}KB$
   2）磁头在 85 号柱面上，对 SSTF 算法而言，总是访问当前柱面距离最近的地址。注意每个簇包含 2 个扇区，通过计算得到，85 号柱面对应的簇号为 85000～85999。通过比较得出，系统最先访问离 85000～85999 最近的 100260，随后访问离 100260 最近的 101660，然后访问110560，最后访问 60005。顺序为 100260、101660、110560、60005。
   3）第 100530 簇在磁盘上的物理地址由其所在的柱面号、磁道号、扇区号构成。柱面号 = [簇号/每个柱面的簇数] = [100530/(10×200/2)] = 100。磁道号 = [(簇号%每个柱面的簇数)/每个磁道的簇数] = [530/(200/2)] = 5。扇区号 = 扇区地址%每个磁道的扇区数 = (530×2)%200 = 60。将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。

2. 1）簇大小为 4KB，每个地址项长度为 4B，故每簇有 4KB/4B = 1024 个地址项。最大文件的物理块数可达 $8+1\times 1024+1\times 1024^2+1\times 1024^3$，每个物理块（簇）大小为 4KB，故最大文件长度为$(8+1\times 1024+1\times 1024^2+1\times 1024^3)\times 4KB=32KB+4MB+4GB+4TB$。
   2）文件索引结点总个数为 1M×4KB/64B = 64M，5600B 的文件占 2 个簇，512M 个簇可存放的文件总个数为 512M/2 = 256M。可表示的文件总个数受限于文件索引结点总个数，故能存储 64M 个大小为 5600B 的图像文件。
   3）文件 F1 的大小为 $6KB<4KB\times 8=32KB$，故获取文件 F1 的最后一个簇的簇号只需要访问索引结点的直接地址项。文件 F2 的大小为 40KB，$4KB\times 8<40KB<4KB\times 8+4KB\times 1024$，故获取 F2 的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。

---

第2组

习题

1. 某计算机采用页式虚拟存储管理方式，按字节编址。CPU 进行存储访问的过程如图所示。
   
   根据图回答下列问题。
   （1）主存物理地址占多少位?
   （2）TLB 采用什么映射方式？TLB 是用 SRAM 还是用 DRAM 实现？
   （3）Cache 采用什么映射方式？若 Cache 采用 LRU 替换算法和回写（Write Back）策略，则 Cache 每行中除数据（Data）、Tag 和有效位，还应有哪些附加位？Cache 的总容量是多少？Cache 中有效位的作用是什么？
   （4）若 CPU 给出的虚拟地址为 0008 C040H，则对应的物理地址是多少？是否在 Cache 中命中？说明理由。若 CPU 给出的虚拟地址为 0007 C260H，则该地址所在主存块映射到的 Cache组号是多少？

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

答案

1. 1）物理地址由实页号和页内地址拼接，因此其位数为 16 + 12 = 28 或直接可得 20 + 3 + 5 = 28。
   2）TLB 采用全相联映射，可以把页表内容调入任一块空 TLB 项中，TLB 中每项都有一个比较器，没有映射规则，只要空闲就行。TLB 采用静态存储器 SRAM，读写速度快，但成本高，多用于容量较小的高速缓冲存储器。
   3）从图中可以看到，Cache 中每组有两行，故采用 2 路组相联映射方式。因为是 2 路组相联并采用 LRU 替换算法，所以每行（或每组）需要 1 位 LRU 位；因为采用回写策略，所以每行有 1 位修改位（脏位），根据脏位判断数据是否被更新，若脏位为 1 则需要写回内存。28 位物理地址中 Tag 字段占 20 位，组索引字段占 3 位，块内偏移地址占 5 位，故 Cache共有 $2^3$ = 8 组，每组 2 行，每行有 $2^5$ = 32B，故 Cache 总容量为 $8\times 2\times (20+1+1+1+32\times 8)=4464位=558$ 字节。Cache 中有效位用来指出所在 Cache 行中的信息是否有效。
   4）虚拟地址分为两部分：虚页号、页内地址；物理地址分为两部分：实页号、页内地址。利用虚拟地址的虚页号部分去查找 TLB 表（缺失时从页表调入），将实页号取出后和虚拟地址的页内地址拼接，就形成了物理地址。虚页号 008CH 恰好在 TLB 表中对应实页号 0040H（有
   效位为 1，说明存在），虚拟地址的后 3 位为页内地址 040H，则对应的物理地址是 0040040H。物理地址为 0040040H，其中高 20 位 00400H 为标志字段，低 5 位 00000B 为块内偏移量，中间 3 位 010B 为组号 2，因此将 00400H 与 Cache 中的第 2 组两行中的标志字段同时比较，可以看出，虽然有一个 Cache 行中的标志字段与 00400H 相等，但对应的有效位为 0，而另一 Cache行的标志字段与 00400H 不相等，故访问 Cache 不命中。因为物理地址的低 12 位与虚拟地址低 12 位相同，即为 001001100000B。根据物理地址的结构，物理地址的后八位 01100000B 的前三位 011B 是组号，因此该地址所在的主存映射到 Cache的组号为 3。

2. (1)0180 6008H
   (2)PDBR 为页目录基址地址寄存器（Page-Directory Base Register），其存储页目录表物理内存基地址。进程切换时，PDBR 的内容会变化；同一进程的线程切换时，PDBR 的内容不会变化。每个进程的地址空间、页目录和 PDBR 的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新 PDBR。同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此 PDBR 的内容也不变。
   (3)改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）。

---

第3组

习题

1. 有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放人对方的信箱中。假设A的信箱最多放$M$个邮件，B的信箱最多$N$个邮件。初始时A的信箱中有$x$个邮件($0<x<M$)，B的信箱中有$y$个邮件($0<y<N$)。辩论者每取出一个邮件，邮件数减1。A和B两人的操作过程描述如下：
   
   当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V(或wait、signal)操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。

2. 某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：
   
   请回答下列问题。
   (1)页和页框的大小各为多少字节?进程的虚拟地址空间大小为多少页?
   (2)假定页目录项和页表项均占4个字节，则进程的页目录和页表共占多少页?要求写出计算过程。
   (3)若某指令周期内访问的虚拟地址为0100 0000H和0111 2048H，则进行地址转换时共访问多少个二级页表?要求说明理由。

答案

1. 如下：

semaphore Full_A = x ;//Fuu_A表示A的信箱中的邮件数量
semaphore Empty_A = M-x;//Empty_A表示A的信箱中还可存放的邮件数量
semaphore Full_B = y ;//Full_B表示B的信箱中的邮件数量
semaphore Empty_B = N-y;//Empty_B表示B的信箱中还可存放的邮件数量
semaphore mutex_A = 1 ;//mutex_A用于A的信箱互斥
semaphore mutex_B = 1 ;//mutex_B用于B的信箱互斥A{while(TRUE){P(Full_A)；P(mutex_A)；从 A 的信箱中取出一个邮件；V(mutex_A)；V(Empty_A)；回答问题并提出一个新问题；P(Empty_B)；P(mutex_B)；将新邮件放入 B 的信箱；V(mutex_B)；V(Full_B)；} }B{while(TRUE){P(Full_B)；P(mutex_B)；从 B 的信箱中取出一个邮件；V(mutex_B)；V(Empty_B)；回答问题并提出一个新问题；P(Empty_A)；P(mutex_A)；将新邮件放入 A 的信箱；V(mutex_A)；V(Full_A)；} }

2. (1)页和页框大小均为4 KB。进程的虚拟地址空间大小为$2^{32}/2^{12}=2^{20}$页。
   (2)$(2^{10}\ast 4)/2^{12}+(2^{20}\ast 4)/2^{12}=1025$页。
   (3)需要访问一个二级页表。因为虚拟地址0100 0000H和0111 2048H的最高10位的值都是4，访问的是同一个二级页表。

---

第4组

习题

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

答案

1. 如下：

semaphore odd = 0, even = 0, empty = N, mutex = 1;
P1( ) 
{ 
x = produce(); ∥生成一个数
P(empty); ∥判断缓冲区是否有空单元
P(mutex); ∥缓冲区是否被占用
Put();
V(mutex); ∥释放缓冲区
if(x%2 == 0)
V(even); ∥如果是偶数，向 P3 发出信号
else
V(odd); ∥如果是奇数，向 P2 发出信号
} 
P2( ) 
{ 
P(odd); ∥收到 P1 发来的信号，已产生一个奇数
P(mutex); ∥缓冲区是否被占用
getodd();
V(mutex); ∥释放缓冲区
V(empty); ∥向 P1 发信号，多出一个空单元
countodd(); 
} 
P3( ) 
{ 
P(even); ∥收到 P1 发来的信号，已产生一个偶数
P(mutext); ∥缓冲区是否被占用
geteven();
V(mutex); ∥释放缓冲区
V(empty); ∥向 P1 发信号，多出一个空单元
counteven(); 
}