操作系统大题带答案版¶
第二章 进程管理¶
【2016-46】¶
（6分）某进程调度程序采用基于优先数 (priority) 的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。
(1) 若调度程序只将nice的值作为进程的优先数，即priority=nice，则可能会出现饥饿现象，为什么？
(2) 使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。
解析
【官方答案】
(1) 由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。（2 分）
(2) 优先数 priority 的计算公式为：priority = nice + k1 × cpuTime - k2 × waitTime，其中 k1 >0, k2 > 0，用来分别调整 cpuTime 和 waitTime 在 priority 中所占的比例。（3 分）waitTime 可使长时间等待的进程优先数减小，从而避免出现饥饿现象。（1 分）
【评分说明】
① 公式中包含 nice 给 1 分，利用 cpuTime 增大优先数给 1 分，利用 waitTime 减少优先数给 1 分；部分正确，酌情给分。
② 若考生给出包含 nice、cpuTime 和 waitTime 的其他合理的优先数计算方法，同样给分。
【2023-45】¶
（7分）现要求学生使用 swap 指令和布尔型变量 lock 实现临界区互斥。lock 为线程间共享的变量。lock 的值为 TRUE 时线程不能进入临界区，为 FALSE 时线程能够进入临界区。某同学编写的实现临界区互斥的伪代码如题 45(a) 图所示。
(1) 题 45(a) 图中伪代码中哪些语句存在错误？将其改为正确的语句（不增加语句条数）。
(2) 题 45(b) 图中给出了两个变量值的函数 newSwap() 的代码是否可以用函数调用语句“newSwap(&key, &lock)”代替指令“swap key, lock”以实现临界区的互斥？为什么？
解析
【官方答案】
(1) 进入区中的语句“if (key == TRUE) swap key, lock”存在错误，（1 分）修改为“while (key == TRUE) swap key, lock”。（1 分）退出区中的语句“lock = TRUE”存在错误，（1 分）修改为“lock = FALSE”。（1 分）
(2) 否。（1 分）因为多个线程可以并发执行 newSwap()，newSwap() 执行时传递给形参 b 的是共享变量 lock 的地址，在 newSwap() 中对 lock 既有读操作又有写操作，并发执行时不能保证实现两个变量值的原子交换，从而会导致并发执行的线程同时进入临界区。（2 分）
【2021-45】¶
（7分）下表给出了整型信号量S的wait()和signal()操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法。
请回答下列问题。
(1) 为什么在wait()和signal()操作中对信号量S的访问必须互斥执行？
(2) 分别说明方法1和方法2是否正确。若不正确，请说明理由。
(3) 用户程序能否使用开/关中断指令实现临界区互斥？为什么？
解析
【官方答案】
(1) 因为信号量 S 是能够被多个进程共享的变量，多个进程都可以通过 wait() 和 signal() 对 S 进行读、写操作。所以，在 wait() 和 signal() 操作中对 S 的访问必须是互斥的。（1 分）
(2) 方法 1 是错误的。（1 分）在 wait() 中，当 S<=0 时，关中断后，其他进程无法修改 S 的值，while 语句陷入死循环。（1 分）方法 2 是正确的。（2 分）
(3) 用户程序不能使用开/关中断指令实现临界区互斥。（1 分）因为开中断和关中断指令都是特权指令。（1 分）
【2009-45】¶
三个进程P1、P2、P3互斥使用一个包含 N (N＞0) 个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countdd()统计奇数个数；P3每次用getven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义（要求用伪代码描述）。
解析
【官方答案】
(1) 缓冲区是一互斥资源，因此设互斥信号量 mutex。
(2) 同步问题：P1、P2 因为奇数的放置与取用而同步，设同步信号量 odd；P1、P3 因为偶数的放置与取用而同步，设同步信号量 even；P1、P2、P3 因为共享缓冲区，设同步信号量 empty。
semaphore mutex = 1;
semaphore odd = 0, even = 0;
semaphore empty = N;
main()
cobegin{
Process P1
while(True) {
number = produce();
P(empty);
P(mutex);
put();
V(mutex);
if (number % 2 == 0)
V(even);
else
V(odd);
}
Process P2
while(True) {
P(odd);
P(mutex);
getodd();
V(mutex);
V(empty);
countodd();
}
Process P3
while(True) {
P(even);
P(mutex);
geteven();
V(mutex);
V(empty);
counteven();
}
}coend【2011-45】¶
（8分）某银行提供 1 个服务窗口和 10 个顾客等待座位。顾客到达银行时，若有空座位，则到取号机领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：
请添加必要的信号量和P、V（或wait( )、signal( )）操作实现上述过程的互斥和同步。要求写出完整的过程，说明信号量的含义并赋初值。
解析
【官方答案】
(1) 互斥资源：取号机 (一次只允许一位顾客领号)，因此设一个互斥信号量 mutex；
(2) 同步问题：顾客需要获得空座位等待叫号,当营业员空闲时，将选取一位顾客并为其服务。空座位的有、无影响等待顾客数量，顾客的有、无决定了营业员是否能开始服务，故分别设置信号量 empty 和 full 来实现这一同步关系。另外，顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量 service 来完成这一同步过程。
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【评分说明】
① 能正确给出互斥信号量定义、含义及初值，给 1 分。
② 能正确给出 3 个同步信号量定义、含义及初值，给 2 分。
③ 营业员进程描述正确的，给 2 分。
④ 顾客进程描述中，互斥描述正确的，给 1 分；同步描述正确的。给 2 分；共 3 分。
⑤ 其他正确解答，参照 ①~④ 的标准给分。
【2013-45】¶
（7分）某博物馆最多可以容纳 500 人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：
请添加必要的信号量和P、V（或wait( )、signal( )）操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。
解析
【官方答案】
定义两个信号量
semaphore musempty = 500; // 博物馆可容纳的最多人数（2 分）
semaphore mutex = 1; // 用于出入口资源的控制（2 分）
cobegin
参观者进程 i:
{
...
P(empty);
P(mutex);
进门;
V(mutex);
参观;
P(mutex);
出门;
V(mutex);
V(empty);
...
}
coend（3 分）【评分说明】
① 信号量初值给 1 分，说明含义给 1 分，两个信号量的初值和含义共 4 分。
② 对 mutex 的 P、V 操作正确给 2 分。
③ 对 empty 的 P、V 操作正确给 1 分。
④ 其他答案，参照 ①~③ 的标准给分。
【2014-47】¶
（8分）系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量P、V（wait()，signal()）操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。
解析
【官方答案】
伪代码如下：
semaphore empty = 1000; // 空缓冲区数
semaphore full = 0; // 非空缓冲区数（1 分）
semaphore mutex1 = 1; // 用于实现生产者之间的互斥
semaphore mutex2 = 1; // 用于实现消费者之间的互斥（1 分）
item buf[1000]; // 缓冲区
int in = 0;
int out = 0;
生产者进程（2 分）
while(true) {
produce;
P(empty);
P(mutex1);
put an item into buf[in];
in = (in + 1) mod 1000;
V(mutex1);
V(full);
}
}
消费者进程（4 分）
while(true) {
P(mutex2);
for (int i = 0; i < 10; i++) {
P(full);
get an item from buf[out];
out = (out + 1) mod 1000;
V(empty);
}
V(mutex2);
consume;
}
}
coend【评分说明】
① 信号量的初值和含义都正确给 2 分。
② 生产者之间的互斥操作正确给 1 分；生产者与消费者之间的同步操作正确给 2 分；消费者之间互斥操作正确给 1 分。
③ 控制消费者连续取产品数量正确给 2 分。
④ 仅给出经典生产者-消费者问题的信号量定义和伪代码描述，最多给 3 分。
⑤ 若考生将题意理解成缓冲区中至少有 10 件产品，消费者才能开始取产品，其他均正确，得 6 分。
⑥ 部分正确，酌情给分。
【2015-45】¶
（9分）有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放人对方的信箱中。假设A的信箱最多放_M_个邮件，B的信箱最多放_N_个邮件。初始时A的信箱中有_x_个邮件(0<x<M)，B的的信箱中有_y_个邮件(0<y<N)。辩论者每取出一个邮件，邮件数减1。A和B两人的操作过程描述如下：
当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V（或wait、signal）操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。
解析
【官方答案】
semaphore Full_A=x; // Full_A表示A的信箱中的邮件数量
semaphore EmptyA=M-x; // Empty_A表示A的信箱中还可存放的邮件数量
semaphore Full_B=y; // Full_B表示B的信箱中的邮件数量
semaphore Empty_B=N-y; // Empty_B表示B的信箱中还可存放的邮件数量
semaphore mutex_A=1; // mutexA用于A的信箱互斥
semaphore mutex_B=1; // mutex_B用于B的信箱互斥
CoBegin
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(mulex_B);
V(Empty_B);
回答问题并提出一个新问题;
P(Empty_A);
P(mutex_A);
将新邮件放入A的信箱;
V(mutex_A);
V(Full_A);
}
}
CoEnd【评分说明】
① 每对信号量的定义及初值正确，给分。
② 每个互斥信号量的 P、V 操作使用正确，可 给分。
③ 每个同步信号量的 P、V 操作使用正确，可 给分。
④ 其他答案的情给分。
注：经过对分值的计算，每个信号量的定义 0.5 分，每次对信号量的正确的 P 或 V 操作占 0.5 分。
【2019-43】¶
（8分）有n(n≥3)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有m(m≥1)个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P、V操作（wait()、signal()操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
解析
【官方答案】
// 信号量
semaphore bowl; // 用于协调哲学家对碗的使用 （1 分）
semaphore chopsticks[n]; // 用于协调哲学家对筷子的使用 （1 分）
for (int i = 0; i < n; i++)
chopsticks[i].value = 1; // 设置两个哲学家之间筷子的数量
bowl.value = min(n-1, m); // bowl.value ≤ n-1，确保不死锁
CoBegin
// 哲学家 i 的程序
while (True) {
思考;
P(bowl); // 取碗 （1 分）
P(chopsticks[i]); // 取左边筷子 （1 分）
P(chopsticks[(i+1) MOD n]); // 取右边筷子 （1 分）
就餐;
V(chopsticks[i]); // 放回左边筷子 （1 分）
V(chopsticks[(i+1) MOD n]); // 放回右边筷子 （1 分）
V(bowl); // 放回碗 （1 分）
}
}
CoEnd【2020-45】¶
（7分）现有5个操作A、B、C、D和E，操作C必须在A和B完成后执行，操作E必须在C和D完成后执行，请使用信号量的wait()、signal()操作（P、V操作）描述上述操作之间的同步关系，并说明所用信号量及其初值。
解析
【官方答案】
Semaphore S_AC = 0; // 控制操作 A 和 C 的执行顺序
Semaphore S_BC = 0; // 控制操作 B 和 C 的执行顺序
Semaphore S_CE = 0; // 控制操作 C 和 E 的执行顺序
Semaphore S_DE = 0; // 控制操作 D 和 E 的执行顺序
CoBegin
Begin 操作 A; signal(S_AC); End
Begin 操作 B; signal(S_BC); End
Begin wait(S_AC); wait(S_BC); 操作 C; signal(S_CE); End
Begin 操作 D; signal(S_DE); End
Begin wait(S_CE); wait(S_DE); 操作 E; End
CoEnd【2017-46】¶
（8分）某进程中有3个并发执行的线程thread1、thread2、thread3，其伪代码如下所示。
请添加必要的信号量和P、V（或wait()、signal()）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。
解析
【官方答案】
互斥信号量如下：（3 分，每个互斥信号量 1 分）
semaphore mutex_y1; // mutex_y1用于thread1和thread3对变量y的互斥访问（1 分）
semaphore mutex_y2; // mutex_y2用于thread2和thread3对变量y的互斥访问（1 分）
semaphore mutex_z; // mutex_z用于变量z的互斥访问（1 分）互斥代码如下：（5 分，每一对 wait()、signal() 操作 1 分）
thread1
{
cnum w;
wait(mutex_y1);
w = add(x, y);
signal(mutex_y1);
...
}
thread2
{
cnum w;
wait(mutex_y2);
wait(mutex_z);
w = add(y, z);
signal(mutex_z);
signal(mutex_y2);
...
}
thread3
{
cnum w;
w.a = 1;
w.b = 2;
wait(mutex_z);
z = add(z, w);
signal(mutex_z);
wait(mutex_y1);
wait(mutex_y2);
y = add(y, w);
signal(mutex_y1);
signal(mutex_y2);
...
}【评分说明】
① 各线程与变量之间的互斥、并发情况及相应评分见下表。
② 若考生仅使用一个互斥信号量，互斥代码部分的得分最多给 2 分。
③ 答案部分正确，酌情给分。
【2022-46】¶
（8分）某进程的两个线程T1和T2并发执行A、B、C、D、E和F共6个操作，其中T1执行A、E和F，T2执行B、C和D。题46图表示上述6个操作的执行顺序所必须满足的约束：C在A和B完成后执行，D和E在C完成后执行，F在E完成后执行。请使用信号量的wait()、signal()操作描述T1和T2之间的同步关系，并说明所用信号量的作用及其初值。
解析
【官方答案】
semaphore S_AC = 0; // 描述 A、C 之间的同步关系（1 分）
semaphore S_CE = 0; // 描述 C、E 之间的同步关系（1 分）
T1:
A;
signal(S_AC); // （1 分）
wait(S_CE); // （1 分）
E;
F;
T2:
B;
wait(S_AC); // （1 分）
C;
signal(S_CE); // （1 分）
D;【2024-46】¶
（本题8分）计算机系统中的进程之间往往需要相互协作以完成一个任务。在某网络系统中，缓冲区B用于存放一个数据分组，对B的操作有现有C1、C2和C3三种操作。C1将一个数据分组写入B中，C2从B中读出一个分组，C3对B中的数据分组进行修改，要求 B 为空时才能执行C1，B 非空时才能执行C2和C3。
请回答下列问题。
(1) 假设进程P1、P2均需要执行C1，实现C1代码是否为临界区，为什么？（2分）
(2) 设B初始为空，进程P1执行C1一次，进程P2执行C2一次，请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2之间的同步或互斥关系，说明所用信号量的作用及其初值。（3分）
(3) 假设B初始不为空，进程P1和P2各执C3一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2之间的同步或互斥关系，说明所用信号量的作用及其初值。（3分）
解析
【官方答案】
(1) 实现 C1 代码是临界区，（1 分）因为代码 C1 执行对 B 的写操作，且 P1、P2 需要互斥执行 C1 。（1 分）
(2) 进程 P1 和 P2 的同步伪代码如下。
semaphore S = 0; // 实现进程 P1 和 P2 的同步 （1 分）
P1 {
...
C1;
signal(S); // （1 分）
...
}
P2 {
...
wait(S); // （1 分）
C2;
...
}(3) 进程 P1 和 P2 的互斥伪代码如下。
semaphore mutex = 1; // 实现进程 P1 和 P2 的互斥执行 C3 （1 分）
P1 {
...
wait(mutex); // （0.5 分）
C3;
signal(mutex); // （0.5 分）
...
}
P2 {
...
wait(mutex); // （0.5 分）
C3;
signal(mutex); // （0.5 分）
...
}第三章 内存管理¶
【2009-46】¶
（8分）请求分页管理系统中，假设某进程的页表内容见下表。
\(\begin{array}{|c|}\hline 页号&页框（\text{Page Frame}）号&有效位（存在位）\\\hline 0&\text{101H}&1\\\hline 1&-&0\\ \hline2&\text{254H}&1\\\hline \end{array}\)
页面大小为4KB，一次内存的访问时间为100ns，一次快表（TLB）的访问时间为10ns，处理一次缺页的平均时间为 10^8ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页面不在内存中，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：
(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。
(2) 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。
解析
【官方答案】
(1) 2362H 的访问时间 = 10 ns(访问 TLB)+100 ns(访问页表)+100 ns(访问内存单元) = 210 ns
1565H 的访问时间 = 10 ns(访问 TLB)+100 ns(访问页表)+100 000 000 ns(调页)+10 ns(访问 TLB)+100 ns(访问内存单元) = 100 000 220 ns
25A5H 的访问时间 = 10 ns(访问 TLB)+100 ns(访问内存单元) = 110 ns
(2) 1565H 的物理地址是：101565H；因为 2 号页面刚被访问，不会被置换，因此用 101H 页框。
【2013-46】¶
（8分）某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题。
(1) 若使用一级页表的分页存储管理方式，逻辑地址结构为：
\(\begin{array}{|c|}\hline 页号（20\ 位）&页内偏移量（12\ 位）\\\hline \end{array}\)
则页的大小是多少字节？页表最大占用多少字节？
(2) 若使用二级页表的分页存储管理方式，逻辑地址结构为：
\(\begin{array}{|c|}\hline 页目录号（10\ 位）&页表索引（10\ 位）&页内偏移量（12\ 位） \\\hline \end{array}\)
设逻辑地址为 LA，请分别给出其对应的页目录号和页表索引的表达式。
(3) 采用 (1) 中的分页存储管理方式，一个代码段起始逻辑地址为 0000 8000H，其长度为 8KB，被装载到从物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面 2 的起始物理地址。
解析
【官方答案】
(1) 因为页内偏移量是 12 位，所以页大小为 4 KB。（1 分）
页表项数为 2³² / 4 K = 2²⁰，该一级页表最大为 2²⁰ × 4 B = 4 MB。（2 分）
(2) 页目录号可表示为：(((unsigned int)(LA)) >> 22) & 0x3FF。（1 分）
页表索引可表示为：(((unsigned int)(LA)) >> 12) & 0x3FF。（1 分）
(3) 代码页面 1 的逻辑地址为 0000 8000H，表明其位于第 8 个页处，对应页表中的第 8 个页表项，所以第 8 个页表项的物理地址 = 页表起始地址 + 8 × 页表项的字节数 = 0020 0000H + 8 × 4 = 0020 0020H。由此可得如下图所示的答案。（3 分）
【2015-46】¶
（6分）某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：
请回答下列问题。
(1) 页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？
(2) 假定页目录项和页表项均占4个字节，则进程的页目录和页表共占多少页？要求写出计算过程。
(3) 若某指令周期内访问的虚拟地址为0100 0000H和0111 2048H，则进行地址转换时共访问多少个二级页表？要求说明理由。
解析
【官方答案】
(1) 页和页框大小均为 4 KB。（1 分）进程的虚拟地址空间大小为 页。（1 分）
(2) （页目录所占页数）+ （页表所占页数）= 1025 页。 （2 分，其中计算过程 1 分，结果 1 分）
(3) 需要访问一个二级页表。（1 分）因为虚拟地址 0100 0000H 和 0111 2048H 的最高 10 位的值都是 4，访问的是同一个二级页表。（1 分）
注：括号中的分值和说明为本人标注。
【评分说明】
用其他方法计算，思路和结果正确同样给分。
(1) 页大小：页内偏移量为12位，故页大小 = 
字节 = 4KB；
页框大小：页框大小 = 页大小 = 4KB（4096字节）；
虚拟地址空间页数：虚拟地址共 
位，虚拟地址空间大小 = 
字节，
(2) 页目录占用页数：
- 页目录项数 =
个 - 页目录大小 =
页
页表占用页数：
- 每个页目录项指向一个二级页表，共有 个二级页表
- 每个页表项数 = 个
- 每个页表大小 = 页
- 全部页表共占
页
合计：
(3) 共访问 1 个二级页表。
理由： 将两个虚拟地址分解为页目录号和页表索引：
两个虚拟地址的页目录号相同（均为4），因此它们都通过页目录第4项找到同一个二级页表（只是在该页表中访问不同的页表项）。
所以，地址转换过程中只访问了 1 个二级页表。
【2016-45】¶
（14分）某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB；TLB采用全相联映射；Cache数据区大小为64KB，按2路组相联方式组织，主存块大小为64B。存储访问过程的示意图如下。
请回答下列问题。
(1) 图中字段A～G的位数各是多少？TLB标记字段B中存放的是什么信息？
(2) 将块号为4099的主存块装入到Cache中时，所映射的Cache组号是多少？对应的H字段内容是什么？
(3) Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？
(4) 为什么Cache可以采用直写 (Write Through) 策略，而修改页面内容时总是采用回写 (Write Back) 策略？
解析
【官方答案】
(1) 页大小为 8 KB，页内偏移地址为 13 位，故 A = B = 32 - 13 = 19；D = 13；C = 24 - 13 = 11；主存块大小为 64 B，故 G = 6。2 路组相联，每组数据区容量有 64 B × 2 = 128 B，共有 64 KB / 128 B = 512 组，故 F = 9；E = 24 - G - F = 24 - 6 - 9 = 9。
因而 A = 19, B = 19, C = 11, D = 13, E = 9, F = 9, G = 6。（各 1 分，共 7 分）
TLB 中标记字段 B 的内容是虚页号，表示该 TLB 项对应哪个虚页的页表项。（1 分）
(2) 块号 4099 = 00 0001 0000 0000 0011B，因此，所映射的 Cache 组号为 0 0000 0011B = 3，（1 分）对应的 H 字段内容为 0 0000 1000B。（1 分）
(3) Cache 缺失带来的开销小，而处理缺页的开销大。（1 分）因为缺页处理需要访问磁盘,而 Cache 缺失只要访问主存。（1 分）
(4) 因为采用直写策略时需要同时写快速存储器和慢速存储器，而写磁盘比写主存慢得多,所以，在 Cache-主存层次，Cache 可以采用直写策略，而在主存-外存（磁盘）层次，修改页面内容时总是采用回写策略。（2 分）
【评分说明】
(3) 对于 (3) 中第 2 问，若考生回答因为缺页需要软件实现而 Cache 缺失用硬件实现，则同样给分。
【预备计算】
| 参数 | 计算 | 结果 |
|---|---|---|
| 页内偏移 | 8KB = 2¹³ | 13位 |
| 虚页号位数（A） | 32 - 13 | 19位 |
| 物理页框号位数（C） | 24 - 13 | 11位 |
| Cache块内偏移（G） | 64B = 2⁶ | 6位 |
| Cache组数 | 64KB ÷ (2 × 64B) = 512 | 512组 |
| Cache组索引（F） | log₂512 | 9位 |
| Cache标记（E） | 24 - 6 - 9 | 9位 |
(1) 图中字段A～G的位数各是多少？TLB标记字段B中存放的是什么信息？
解：地址变换流程各字段：
虚拟地址（32位）：
┌────────────────────┬───────────────────────┐
│ 虚页号 A = 19位 │ 页内偏移 D = 13位 |
└────────────────────┴───────────────────────┘
↓ TLB查找（全相联）
┌────────────────────┬───────────┐
│ TLB标记 B = 19位 │ │
└────────────────────┴───────────┘
↓ 命中则得到
┌─────────────────────┬──────────────────────┐
│ 物理页框号 C = 11位 │ 页内偏移 D = 13位 |
└─────────────────────┴──────────────────────┘
↓ 物理地址（24位）送Cache
┌──────────────┬─────────────┬───────────────┐
│ Cache标记 │ Cache组索引 │块内偏移 │
│ E = 9位 │ F = 9位 │ G = 6位 │
└──────────────┴─────────────┴───────────────┘
TLB标记字段B中存放的是虚页号（19位）。 因为TLB采用全相联映射，没有组索引，TLB的整个标记字段就是完整的虚页号，用于与CPU给出的虚页号比较判断是否命中。
(2) 将块号为4099的主存块装入Cache时，所映射的Cache组号是多少？对应的H字段（Cache标记）内容是什么？
法一： Cache共512组，2路组相联，块大小64B：
Cache组号 = 主存块号 mod Cache组数
Cache标记H = 主存块号 ÷ Cache组数 = floor(4099 / 512)
H字段内容 = 8（十进制），即 000001000B（9位二进制）。
法二：对于任意Cache格式，主存地址均可划分为\(\begin{array}{|c|c|}\hline\text{块号}&\text{块内地址}\\\hline\end{array}\) ，本题Cache采用组相联格式， 地址可划分为\(\begin{array}{|c|c|}\hline\text{块号}&\text{块内地址}\\\hline\end{array} =\begin{array}{|c|c|c|}\hline\text{主存字块标记}&\text{组号}&\text{块内地址}\\\hline\end{array}\) ，所以 \(\begin{array}{|c|}\hline\text{块号}\\\hline\end{array} =\begin{array}{|c|c|}\hline\text{tag}&\text{组号}\\\hline\end{array}\) 。块号4099=4096+3=\(\underbrace{00 0001 000}_{\text{tag}}\underbrace{0 0000 0011}_{\text{组号}}\) B，因此，所映射的Cache组号为0 0000 0011B=3。标记H为主存字块标记，块号4099对应的H字段内容为0 0000 1000B。
(3) Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？
缺页处理的时间开销远大于Cache缺失处理的时间开销。
Cache缺失时，直接从主存调块到Cache，全程硬件完成，速度快；缺页时必须从外存（磁盘）读取，磁盘I/O是机械运动或闪存擦写，延迟高出主存访问数个数量级。
(4) 为什么Cache可以采用直写策略，而修改页面内容时总是采用回写策略？
| 策略 | Cache（Cache-主存） | 虚拟内存（主存-外存） |
|---|---|---|
| 写策略 | 直写（Write Through）可行 | 必须采用回写（Write Back） |
| 原因 | 主存访问延迟约百纳秒，直写的性能损失可接受；且直写使Cache与主存保持一致，简化一致性管理 | 磁盘I/O延迟达毫秒级，若每次写页面都立即写磁盘，性能损失灾难性（写操作变慢10⁵倍）；采用回写仅在页面被置换时才写磁盘，大幅减少磁盘I/O次数 |
本质区别：下层存储器的访问延迟差异决定了写策略的选择。主存速度相对较快，直写可接受；磁盘速度极慢，必须回写以避免频繁磁盘I/O造成的性能崩溃。
【2017-45】¶
（7分）假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：\(\begin{array}{|c|}\hline \text{页目录号（10位）}&\text{页表索引（10位）}&\text{页内偏移量（12位）}\\\hline \end{array}\)
请针对题43的函数f1
int f1(unsigned n) {
int sum=1, power=1;
for (unsigned i=0; i<=n-1; i++) {
power*=2;
sum+=power;
}
return sum;
}
和题44中的机器指令代码，
int f1(unsigned n)
1 00401020 55 push ebp
... ... ...
for (unsigned i = 0; i <= n-1; i++)
... ... ...
20 0040105E 39 4D F4 cmp dword ptr [ebp-0Ch],ecx
... ... ...
{ power *= 2;
... ... ...
23 00401066 D1 E2 shl edx,1
... ... ...
return sum;
... ... ...
35 0040107F C3 ret
回答下列问题。
(1) 函数f1的机器指令代码占多少页？
(2) 取第1条指令（push ebp）时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从0开始）？
(3) M的I/O采用中断控制方式。若进程P在调用f1之前通过 scanf() 获取n的值，则在执行 scanf() 的过程中，进程P的状态会如何变化？CPU是否会进入内核态？
解析
【官方答案】
(1) 函数 f1 的代码段中所有指令的虚拟地址的高 20 位相同，因此 f1 的机器指令代码在同一页中，仅占用 1 页。（1 分）
(2) push ebp指令的虚拟地址的最高 10位（页目录号）为 00 0000 0001，中间10位（页表索引）为 000000 0001，所以，取该指令时访问了页目录的第 1 个表项，（1 分）在对应的页表中访问了第 1 个表项。（1 分）
(3) 在执行 scanf() 的过程中，进程 P 因等待输入而从执行态变为阻塞态。（1 分）输入结束时，P 被中断处理程序唤醒，变为就绪态。（1 分）P 被调度程序调度，变为运行态。（1 分）CPU 状态会从用户态变为内核态。（1 分）
【2020-46】¶
（8分）某32位系统采用基于二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为4字节，虚拟地址结构如下所示。
\(\begin{array}{|c|}\hline \text{页目录号（10位）}&\text{页号（10位）}&\text{页内偏移（12位）}\\\hline \end{array}\)
某C程序中数组a1024的起始虚拟地址为1080 0000H，数组元素占4字节，该程序运行时，其进程的页目录起始物理地址为0020 1000H，请回答下列问题。
(1) 数组元素a1的虚拟地址是什么？对应的页目录号和页号分别是什么？对应的页目录项的物理地址是什么？若该目录项中存放的页框号为00301H，则a1所在页对应的页表项的物理地址是什么？
(2) 数组a在虚拟地址空间中所占区域是否必须连续？在物理地址空间中所占区域是否必须连续？
(3) 已知数组a按行优先方式存放，若对数组a分别按行遍历和按列遍历，则哪一种遍历方式的局部性更好？
解析
【官方答案】
(1) 数组元素 a[1][2] 的虚拟地址是 1080 0000H + (1024 × 1 + 2) × 4 = 1080 1008 H。（1 分）
对应的页目录号为 042H，（1 分）页号为 001H。（1 分）对应的页目录项的物理地址是 0020 1000H + 4 × 42H = 0020 1108H。（1 分）对应页表项的物理地址是 00301H × 1000H + 4 × 1H = 0030 1004H。（1 分）
(2) 数组 a 在虚拟地址空间中所占区域必须连续，（1 分）在物理地址空间中所占区域不必连续。（1 分）
(3) 对数组 a 按行遍历局部性更好。（1 分）
【2018-45】¶
（8分）请根据题44图给出的虚拟存储管理方式，回答下列问题。
(1) 某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？
(2) 寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。
(3) 为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？
解析
【官方答案】
(1) 该虚拟地址为 0180 6008H。（1 分）
(2) 该地址是物理地址。（1 分）进程切换时，PDBR 的内容会变化；（1 分）同一进程的线程切换时，PDBR 的内容不会变化。（1 分）每个进程的地址空间、页目录和 PDBR 的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新 PDBR。（1 分）同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此 PDBR 的内容也不变。（1 分）
(3) 需要设置访问字段（引用位/使用位）（1 分）和修改字段（脏位）（1 分）。
【2021-45】¶
（8分）假设计算机M的主存地址为24位，按字节编址；采用分页存储管理方式，虚拟地址为30位，页大小为4KB；TLB采用2路组相联方式和LRU替换策略，共8组。请回答下列问题。
(1) 虚拟地址中哪几位表示虚页号？哪几位表示页内地址？
(2) 已知访问TLB时虚页号高位部分用作TLB标记，低位部分用作TLB组号，M的虚拟地址中哪几位是TLB标记？哪几位是TLB组号？
(3) 假设TLB初始时为空，访问的虚页号依次为10、12、16、7、26、4、12和20，在此过程中，哪一个虚页号对应的TLB表项被替换？说明理由。
(4) 若将M中的虚拟地址位数增加到32位，则TLB表项的位数增加几位？
解析
【2024-45】¶
（本题7分）某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址长度均为32位，页表项的大小为4字节，页大小为4MB，虚拟地址结构如下。
\(\begin{array}{|c|}\hline \text{页号（10位）}&\text{页内偏移量（22位）}\\\hline \end{array}\)
进程 P 的页表起始虚拟地址为B8C0 0000 H，被装载到从物理地址 6540 0000 H开始的连续主存空间中。
请回答下列问题，要求答案用十六进制表示。
(1) 若 CPU 在执行进程P的过程中，访问虚拟地址 1234 5678 H 时发生了缺页异常，经过缺页异常处理和 MMU 地址转换后得到的物理地址是 BAB4 5678 H，在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚拟地址和物理地址分别是什么？该页表项的页框号更新后的值是什么？（3分）
(2) 进程 P 的页表所在页的页号是多少？该页对应的页表项的虚拟地址是多少？该页表项中的页框号是多少？（4分）
解析
【官方答案】
(1) 页表项的虚拟地址为：
B8C0 0000H + 48H<<2 = B8C0 0120H。（1 分）
页表项的物理地址为：
6540 0000H + 48H<<2 = 6540 0120H。（1 分）
相应页表项中的页框号为：BAB4 5678H>>22 = 2EAH。（1 分）
(2) 进程 P 的页表所在页的页号为：
B8C0 0000H>>22 = 2E3H。（1 分）
页表项的虚拟地址为：
B8C0 0000H + 2E3H<<2 = B8C0 0B8CH。（1 分）
页表项中的页框号为：6540 0000H>>22 = 195H。（2 分）
【2012-45】¶
（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) 该策略是否适合于时间局部性好的程序？说明理由。
解析
【官方答案】
(1) 页框号为 21。（1 分）
因为起始驻留集为空，而 0 页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为 21。
(2) 页框号为 32。（1 分）
理由：因 11>10 故发生第三轮扫描，页号为 1 的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问,因此应被重新放回到驻留集中。其页框号为 32。（1 分）
(3) 页框号为 41。（1 分）
理由：因为第 2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框 41，页框号为 41。（1 分）
(4) 适合。（1 分）
理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。（1 分）
【2010-46】¶
（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页 (Page) 数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框 (Page Frame)。在时刻260前该进程访问情况见下表（访问位即使用位）。
\(\begin{array}{|c|}\hline \text{页号}&\text{页框号}&\text{装入时间}&\text{访问位}\\\hline 0&7&130&1\\ 1&4&230&1\\ 2&2&200&1\\ 3&9&160&1\\\hline \end{array}\)
当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：
(1) 该逻辑地址对应的页号是多少？
(2) 若采用先进先出 (FIFO) 置换算法，该逻辑地址对应的物理地址？要求给出计算过程。
(3) 采用时钟 (CLOCK) 置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针按顺时针方向移动，且指向当前2号页框，示意图如下图）。
解析
【官方答案】
(1) 因 17CAH = 0001 0111 1100 1010B，表示页号的位为左边 6 位，所以页号为 5。（2 分）
(2) 根据 FIFO 算法，需要替换装入时间最早的页，故需要置换装入时间最早的 0 号页，即将 5 号页装入 7 号页框中，所以物理地址为 0001 1111 1100 1010B，换算成十六进制，为 1FCAH。（3 分）
(3) 根据 CLOCK 算法，如果当前指针所指页框的使用位为 0，则替换该页；否则将使用位清零，并将指针指向下一个页框，继续查找。根据题设和示意图，将从 2 号页框开始，前 4 次查找页框号的顺序为 2→4→7→9，并将对应页框的使用位清零。在第 5 次查找中，指针指向 2 号页框,因 2 号页框的使用位为 0，故淘汰 2 号页框对应的 2 号页，把 5 号页装入 2 号页框中，并将对应使用位设置为 1，所以对应的物理地址为 0000 1011 1100 1010B，换算成十六进制，为 0BCAH。（2 分）
【评分说明】
(2) 正确指出被置换的页或页框得 1 分。正确计算出物理地址为 1FCAH 得 2 分。
(3) 正确指出被置换的页或页框得 1 分。正确计算出物理地址为 0BCAH 得 2 分。
第四章 文件管理¶
【2011-46】¶
（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题∶
(1) 在连续、链式、索引二种文件的数据块组织方式中。哪种更合适？要求说明理由。为定位文件数据块，需要在FCB中设计哪些相关描述字段？
(2) 为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。
解析
【官方答案】
(1) 在磁盘中连续存放 (采取连续结构)，磁盘寻道时间更短，文件随机访问效率更高；（2 分）在 FCB 中加入的字段为：<起始块号, 块数> 或者 <起始块号, 结束块号>。（1 分）
(2) 将所有 FCB 集中存放，文件数据集中存放。（2 分）这样在随机查找文件名时，只需访问 FCB 对应的块，可减少磁头移动和磁盘 I/O 访问次数。（2 分）
【2012-46】¶
（8分）某文件系统空间的最大容量为4TB（ \(1TB= 2^{40} B\)），以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块 (FCB) 包含一个512B的索引表区。请回答下列问题。
(1) 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？
(2) 假设索引表区采用如下结构：第0～7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，那么可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。
解析
【官方答案】
(1) 文件系统存储空间共有块数 2⁴² / 2¹⁰ = 2³²。为表示 2³² 个块号，索引表项占 32 / 8 = 4 B。（2 分）
512 字节可存放 2⁷ 个索引表项，故最大文件长度：2⁷ × 2¹⁰ = 2¹⁷ B = 128 KB。（2 分）
(2) 块号占 6 字节，块数占 2 字节的情形下，最大文件长度：2¹⁶ × 2¹⁰ + (504 / 6) × 2¹⁰ = 64 MB + 84 KB = 65620 KB。（2 分）
合理的起始块号和块数所占字节数分别为 4, 4 (或 1, 7 或 2, 6 或3, 5)。（1 分）理由：块数占 4 B 或以上，就可表示 4 TB 大小的文件长度，达到文件系统的空间上限。（1 分）
【评分说明】
(1) 过程描述正确，但计算结果不正确，可酌情给分。
(2) 过程描述正确，但计算结果不正确，可酌情给分。只要答出起始块号和块数所占字节数的任意合理值，均可得 1 分；理由说明正确得 1 分。
【2014-46】¶
文件F由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入文件F中，作为其第30条记录。请回答下列问题，并说明理由。
(1) 若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块？F的文件控制块内容会发生哪些改变？
(2) 若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块？若每个存储块大小为1KB，其中4B存放链接指针，则该文件系统支持的文件最大长度是多少？
解析
【官方答案】
(1) 向前移动文件的前 29 条记录，每条记录读写各 1 次，腾出一个磁盘块空间，以将该记录插入到此磁盘块作为文件的第 30 条记录。（1 分）故需要磁盘访问的次数为：29×2+1=59 次。（1 分）
文件控制块中文件的起始地址和文件大小发生了变化。（1 分）
(2) 采用链接分配方式存储文件 F，需要读文件的前 29 块的链接指针（共读 29 次），在第 29 块内找到指向原第 30 块的链接指针。再为该记录分配一个空闲磁盘块，将该记录及第 29 块内保存的链接指针写入其中，将该块写到磁盘（写 1 次）。最后修改第 29 块的链接指针,指向新的插入块，并将第 29 块写回磁盘（写 1 次）。（1 分）
故需要磁盘访问的次数：29+2=31 次。（1 分）
该文件系统支持的文件最大长度是：(1024 - 4) × 2³² B = 4080 GB。（2 分）
【评分说明】
① 第 (1) 小题的第 2 问，若答案中不包括文件的起始地址和文件大小，则不给分。
② 若按 1024 × 2³² B = 4096 GB 计算文件最大长度，给 1 分。
【2018-46】¶
（7分）某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。
(1) 该文件系统能支持的最大文件长度是多少？（给出计算表达式即可）
(2) 文件系统用1M(\(1M= 2^{20}\) ）个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件？
(3) 若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？
解析
【官方答案】
(1) 该文件系统能支持的最大文件长度为
8 × 4 KB + (4 KB / 4 B) × 4 KB + (4 KB / 4 B)² × 4 KB + (4 KB / 4 B)³ × 4 KB = 32 KB + 4 MB + 4 GB + 4 TB （3 分）
(2) 文件索引节点总个数为：1 M × 4 KB / 64 B = 64 M。5600 B 的文件占 2 个簇，512 M 个簇（ < 2³² 个簇）可存放的文件总个数为：512 M / 2 = 256 M。可表示的文件总个数受限于文件索引节点总个数。因此，该文件系统能存储 64 M 个大小为 5600 B 的图像文件。（2 分）
(3) 需要的时间不相同。（1 分）获取文件 F1 的最后一个簇的簇号只需要访问索引节点的直接地址项，而获取文件 F2 的最后一个簇的簇号还需要读一级索引表。（1 分）
【2022-45】¶
（7分）某文件系统的磁盘块大小为4KB，目录项由文件名和索引节点号构成，每个索引节点占256字节，其中包含直接地址项10个，一级、二级和三级间接地址项各1个，每个地址项占4字节。该文件系统中子目录stu的结构如题45(a)图所示，stu包含子目录course和文件doc，course子目录包含文件course1和course2。各文件的文件名、索引节点号、占用磁盘块的块号如题45(b)图所示。
请回答下列问题。
(1) 目录文件stu中每个目录项的内容是什么？
(2) 文件doc占用的磁盘块的块号 x 的值是多少？
(3) 若目录文件course的内容已在内存，则打开文件course1并将其读入内存，需要读几个磁盘块？说明理由。
(4) 若文件course2的大小增长到6MB，为了存取course2需要使用该文件索引节点的哪几级间接地址项？说明理由。
解析
【官方答案】
(1) 目录文件 stu 中两个目录项的内容是：
（2 分，每个目录项 1 分）
(2) 文件 doc 占用的磁盘块的块号 x 的值为 30。（1 分）
(3) 需要读 2 个磁盘块。（1 分）先读 course1 的索引节点所在的磁盘块，再读 course1 的内容所在的磁盘块。（1 分）
(4) 存取 course2 需要使用索引节点的一级和二级间接地址项。（1 分）6 MB 大小的文件需占用 6 MB / 4 KB = 1536 个磁盘块。直接地址项可记录 10 个磁盘块号，一级间接地址块可记录 4 KB / 4 B = 1024 个磁盘块号，二级间接地址块可记录 1024×1024 个磁盘块号，而 10+1024<1536<10+1024+1024×1024。（1 分）
【2016-47】¶
（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个字节读入内存，则要访问哪几个簇？
解析
第五章 输入输出（I/O）管理¶
【2023-46】¶
（8分）进程P通过执行系统调用从键盘接收一个字符的输入，已知此过程中与进程P相关的操作包括：①将进程P插入就绪队列；②将进程P插入阻塞队列；③将字符从键盘控制器读入系统缓冲区；④启动键盘中断处理程序；⑤进程P从系统调用返回；⑥用户在键盘上输入字符。以上编号①~⑥仅用于标记操作，与操作的先后顺序无关。请回答下列问题。
(1) 按照正确的操作顺序，操作①的前一个和后一个操作分别是上述操作中的哪一个？操作⑥的后一个操作上述操作中的哪一个？
(2) 在上述哪个操作之后CPU一定从进程P切换到其他进程？在上述哪个操作之后CPU调度程序才能选择进程P执行？
(3) 完成上述哪个操作的代码属于键盘驱动程序？
(4) 键盘中断处理程序执行时，进程P处于什么状态？CPU处于内核态还是用户态？
解析
【官方答案】
(1) 操作①的前一个操作是③，（1 分）后一个操作是⑤。（1 分）操作⑥的后一个操作是④。（1 分）
(2) 在操作②之后 CPU 一定从进程 P 切换到其他进程。（1 分）在操作①之后 CPU 调度程序才能选中进程 P 执行。（1 分）
(3) 完成操作③的代码属于键盘驱动程序。（1 分）
(4) 进程 P 处于阻塞状态。（1 分）CPU 处于内核态。（1 分）
【2010-45】¶
（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。
(1) 请说明在上述条件如何进行磁盘块空闲状态的管理。
(2) 设某单面磁盘的旋转速度为6000rpm，每个磁道有100个扇区，相邻磁道间的平均移动的时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（见下图），磁道号的请求队列为50, 90, 30, 120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这个扇区点共需要多少时间？需要给出计算过程。
(3) 如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。
解析
【官方答案】
(1) 用位图表示磁盘的空闲状态。（1 分）每一位表示一个磁盘块的空闲状态，共需要 16384/32=512 个字 = 512×4 个字节 = 2 KB，正好可放在系统提供的内存中。（1 分）
(2) 采用 CSCAN 调度算法，访问磁道的顺序为 120、30、50、90，（1 分）则移动磁道长度为 170，总的移动磁道时间为 170 ms。（0.5 分）
由于转速为 6000 r/m，则平均旋转延迟为 5 ms，总的旋转延迟时间 = 20 ms。（0.5 分）
由于转速为 6000 r/m，则读取一个磁道上一个扇区的平均读取时间为 0.1 ms，总的读取扇区的时间为 0.4 ms。（0.5 分）
读取上述磁道上所有扇区所花的总时间为 190.4 ms。（0.5 分）
(3) 采用 FCFS (先来先服务) 调度策略更高效。（1 分）因为 Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按 I/O 请求的先后顺序服务。（1 分）
【2019-44】¶
（7分）某计算机系统中的磁盘有300个柱面，每个柱面有10个磁道，每个磁道有200个扇区，扇区大小为512B。文件系统的每个簇包含2个扇区。请回答下列问题：
(1) 磁盘的容量是多少？
(2) 假设磁头在85号柱面上，此时有4个磁盘访问请求，簇号分别为100260、60005、101660和110560。若采用最短寻道时间优先 (SSTF) 调度算法，则系统访问簇的先后次序是什么？
(3) 第100530簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由I/O系统的什么程序完成的？
解析
【官方答案】
(1) 磁盘容量=(300×10×200×512/1024) KB = 3×10⁵ KB。（1 分）
(2) 依次访问的簇是 100260、101660、110560、60005。（2 分）
(3) 第 100530 簇在磁盘上的物理地址由其所在的柱面号、磁头号、扇区号构成。
其所在的柱面号为 ⌊100530/(10×200/2)⌋ = 100 。（1 分）
100530 %(10×200/2) = 530，磁头号为 ⌊530/(200/2)⌋ = 5。（1 分）
扇区号为 (530×2)%200 = 60。（1 分）
将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。（1 分）
【2021-46】¶
（8分）某计算机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分区引导程序外，还需要执行ROM中的引导程序。请回答下列问题。
(1) 系统启动过程中操作系统的初始化程序、分区引导程序、ROM中的引导程序、磁盘引导程序的执行顺序是什么？
(2) 把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、对磁盘进行分区，执行这4个操作的正确顺序是什么？
(3) 磁盘扇区的划分和文件系统根目录的建立分别是在第 (2) 问的哪个操作中完成的？
解析
【官方答案】
(1) 执行顺序依次是 ROM 中的引导程序、磁盘引导程序、分区引导程序、操作系统的初始化程序。（3 分）
(2) 4 个操作的执行顺序依次是磁盘的物理格式化、对磁盘进行分区、逻辑格式化、操作系统的安装。（3 分）
(3) 磁盘扇区的划分是在磁盘的物理格式化操作中完成的。（1 分）文件系统根目录的建立是在逻辑格式化操作中完成的。（1 分）