2017年408真题操作系统篇

选择题

✅ 第23题：作业调度选择题（共1分）

问题：

假设4个作业到达系统的时刻和运行时间如下：

作业 到达时刻 运行时间
J1 0 3
J2 1 3
J3 1 2
J4 3 1

系统在 t = 2 时开始调度。若分别采用先来先服务（FCFS）和短作业优先（SJF）调度算法，则选中的作业分别是（）。

选项：

A. J2、J3 B. J1、J4 C. J2、J4 D. J1、J3

✅ 答案：D. J1、J3

✅ 解析：

  • 时刻 t = 2 时，系统中已到达的作业有：
    • J1（到达时间0）
    • J2（到达时间1）
    • J3（到达时间1）
  • 先来先服务（FCFS）：
    • 优先调度最早到达的作业。
    • J1 到达最早 → 选中 J1
  • 短作业优先（SJF）：
    • 在已到达的作业中选运行时间最短的。
    • J1 和 J2：运行时间3；J3：运行时间2 → 选中 J3

✅ 第24题：系统调用过程（共1分）

问题：

执行系统调用的过程包括如下操作：

① 返回用户态 ② 执行陷入 (trap) 指令 ③ 传递系统调用参数 ④ 执行相应的服务程序

正确的执行顺序是（）。

选项：

A. ②→③→①→④ B. ②→④→③→① C. ③→②→④→① D. ③→④→②→①

✅ 答案：C. ③→②→④→①

✅ 解析：

  1. ③ 传递系统调用参数：
    • 用户程序调用系统调用前，会把参数通过寄存器、栈或内存等方式传递给操作系统。
  2. ② 执行陷入 (trap) 指令：
    • 用于从用户态切换到内核态，是发起系统调用的方式。
  3. ④ 执行相应的服务程序：
    • 操作系统接收系统调用号及参数后，进入内核，执行对应的服务功能。
  4. ① 返回用户态：
    • 系统调用执行完毕，返回用户态，继续执行用户进程。

✅ 第25题：内存回收与空闲分区合并（动态分区分配）

问题：

某计算机按字节编址，采用最佳适应算法（Best Fit）*进行*动态分区内存管理，每次分配和回收后都会对空闲分区链重新排序。

当前空闲分区信息如下：

分区起始地址 分区大小
20K 40KB
500K 80KB
1000K 100KB
200K 200KB

现在回收一个起始地址为 60K、大小为 140KB 的分区。回收后：

空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是（）。

选项：

A. 3、20K、380KB B. 3、500K、80KB C. 4、20K、180KB D. 4、500K、80KB

✅ 答案：B. 3、500K、80KB

✅ 解析：

  • 回收的分区：起始地址 60K，大小 140KB
  • 当前空闲区中：
    • 地址20K，大小40KB → 其末尾地址是 20K + 40KB = 60K
    • 地址200K，大小200KB

✅ 合并分析：

  • 20K–60K 与 60K–200K 是连续的 → 可以合并成 20K–200K 的 380KB
  • 这个新分区将替代原来的两个分区，地址为 20K，大小为 380KB
  • 其他未涉及的空闲分区保持不变（500K、80KB 和 1000K、100KB）

✅ 回收后空闲分区情况为：

起始地址 大小
500K 80KB
1000K 100KB
20K 380KB
  • 空闲分区数：3 个
  • 空闲分区链排序后第一个分区为：500K，80KB（因为采用按地址或大小升序排序）

✅ 第26题：文件系统簇空间分配

问题：

某文件系统中：

  • 簇大小为：1KB（1024B）
  • 扇区大小为：512B

若一个文件大小为 1026B，则系统为其分配的磁盘空间大小是（）。

选项：

A. 1026B B. 1536B C. 1538B D. 2048B

✅ 答案：D. 2048B

✅ 解析：

  • 文件系统是以簇（cluster）为单位进行磁盘空间分配的。
  • 一个簇 = 1KB = 1024B
  • 文件大小为 1026B > 1KB，超过了1个簇，需要 两个簇
    • ⌈1026 / 1024⌉ = 2
  • 分配的磁盘空间为：2 × 1KB = 2048B

⚠️ 注意：

  • 虽然扇区为 512B，但文件系统不是按扇区而是按簇分配空间。
  • 多出的部分会造成内部碎片，但不会影响分配逻辑。

✅ 第27题：时间片轮转调度中错误说法

问题：

下列有关基于时间片的进程调度的叙述中，错误的是（ ）。

选项：

A. 时间片越短，进程切换的次数越多，系统开销也越大 B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态 C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间 D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等

✅ 答案：B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态

✅ 解析：

  • A 正确：时间片越短，切换越频繁，上下文切换的开销越大，系统效率可能降低。
  • B 错误（答案）：时间片用完后，进程不是阻塞，而是变为就绪态，等待重新调度。只有当进程等待资源（如I/O）时，才会变为阻塞态。
  • C 正确：系统通过时钟中断（Clock Interrupt）定期检查并更新当前进程的时间片剩余时间。
  • D 正确：时间片大小影响响应时间、系统切换开销和进程公平性等，因此需综合考量。

✅ 第28题：多道程序系统优点

问题：

与单道程序系统相比，多道程序系统的优点是（ ）。

选项：

Ⅰ. CPU利用率高 Ⅱ. 系统开销小 Ⅲ. 系统吞吐量大 Ⅳ. I/O设备利用率高

A. 仅Ⅰ、Ⅲ B. 仅Ⅰ、Ⅳ C. 仅Ⅱ、Ⅲ D. 仅Ⅰ、Ⅲ、Ⅳ

✅ 答案：D. 仅Ⅰ、Ⅲ、Ⅳ

✅ 解析：

  • Ⅰ. CPU利用率高：正确 多道程序系统可以并发执行多个进程，在一个进程等待I/O时，另一个进程可以使用CPU，提高CPU使用率。
  • Ⅱ. 系统开销小：错误 多道程序系统需要更多的管理机制（如调度器、内存管理），其系统开销相对单道程序更大。
  • Ⅲ. 系统吞吐量大：正确 并发执行多个程序，提高了单位时间内完成的任务数，即吞吐量更大。
  • Ⅳ. I/O设备利用率高：正确 I/O等待期间切换到其他进程可以避免设备空闲，充分利用I/O资源。

✅ 第29题：逻辑格式化程序的工作内容

问题：

下列选项中，磁盘逻辑格式化程序所做的工作是（ ）。

选项：

Ⅰ. 对磁盘进行分区 Ⅱ. 建立文件系统的根目录 Ⅲ. 确定磁盘扇区校验码所占位数 Ⅳ. 对保存空闲磁盘块信息的数据结构进行初始化

A. 仅Ⅱ B. 仅Ⅱ、Ⅳ C. 仅Ⅲ、Ⅳ D. 仅Ⅰ、Ⅱ、Ⅳ

✅ 答案：B. 仅Ⅱ、Ⅳ

✅ 解析：

  • 逻辑格式化（高级格式化）的任务是：
    • 在磁盘上创建文件系统（包括根目录、FAT表、空闲空间表等）。
    • 初始化用于管理文件的结构（如位图、FAT、inode表等）。
  • Ⅰ 错误：磁盘分区（如创建C盘、D盘）是物理格式化前的准备工作，不属于逻辑格式化的任务。
  • Ⅱ 正确：逻辑格式化会创建文件系统的根目录。
  • Ⅲ 错误：CRC校验位等与扇区格式结构有关，是物理格式化的一部分。
  • Ⅳ 正确：逻辑格式化会初始化空闲磁盘块信息的数据结构，如FAT或空闲位图。

✅ 第30题：文件权限位数计算

问题：

某文件系统中，针对每个文件，用户类别分为4类：安全管理员、文件主、文件主的伙伴、其他用户；访问权限分为5种：完全控制、执行、修改、读取、写入。若文件控制块中用二进制位串表示文件权限，为表示不同类别用户对一个文件的访问权限，则描述文件权限的位数至少应为（ ）。

选项：

A. 5 B. 9 C. 12 D. 20

✅ 答案：D. 20

✅ 解析：

  • 本题是一个组合位权限控制问题，每个用户类别对应一组权限位。
  • 用户类别：4类 权限类型：5种 ⇒ 需要表示的权限组合总数 = 4 × 5 = 20 位。

每一位代表“某用户是否具有某种权限”，最少需要 20 位二进制数来分别表示这些权限。

✅ 第31题：硬链接文件的打开行为

问题：

若文件 f1 的硬链接为 f2，两个进程分别打开 f1 和 f2，获得对应的文件描述符为 fd1 和 fd2，则下列叙述中，正确的是（ ）。

选项：

Ⅰ. f1 和 f2 的读写指针位置保持相同 Ⅱ. f1 和 f2 共享同一个内存索引结点（inode） Ⅲ. fd1 和 fd2 分别指向各自的用户打开文件表中的一项

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

✅ 答案：B. 仅Ⅱ、Ⅲ

✅ 解析：

  • Ⅰ 错误：fd1 和 fd2 是两个进程的不同文件描述符，分别指向各自用户打开文件表中的项，因此它们的读写指针是独立的，不会保持同步。
  • Ⅱ 正确：硬链接意味着 f1 和 f2 指向的是同一个 inode（即同一个实际文件），共享同一个内核索引节点。
  • Ⅲ 正确：文件描述符 fd1 和 fd2 来自不同的进程，分别指向各自进程的用户打开文件表（user open file table）中的不同条目。

✅ 第32题：DMA 数据传输过程

问题：

系统将数据从磁盘读到内存的过程包括以下操作：

① DMA 控制器发出中断请求 ② 初始化 DMA 控制器并启动磁盘 ③ 从磁盘传输一块数据到内存缓冲区 ④ 执行“DMA 结束”中断服务程序

正确的执行顺序是（ ）。

选项：

A. ③→①→②→④ B. ②→③→①→④ C. ②→①→③→④ D. ①→②→④→③

✅ 答案：B. ②→③→①→④

✅ 解析：

正确的 DMA 传输过程如下：

  1. ② 初始化 DMA 控制器并启动磁盘：CPU 负责配置 DMA 控制器，指定源地址、目标地址和数据长度，启动传输。
  2. ③ 从磁盘传输一块数据到内存缓冲区：DMA 控制器控制数据流动，CPU 不干预。
  3. ① DMA 控制器发出中断请求：数据传输完成后，DMA 控制器向 CPU 发出中断信号。
  4. ④ 执行“DMA 结束”中断服务程序：CPU 响应中断，运行 ISR（中断服务例程）处理后续任务。

分页

✅ 第45题：二级分页虚拟存储管理及函数代码分析

问题：

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

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

函数 f1 的代码如下：

1
2
3
4
5
6
7
8
int f1(unsigned n) { 
    int sum = 1, power = 1;
    for (unsigned i = 0; i <= n-1; i++) { 
        power *= 2;
        sum += power;
    }
    return sum;
}

和题44中的机器指令代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
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 的机器指令代码占多少页？

  • 虚拟地址格式分析：根据题目，虚拟地址格式为：

    • 页目录号（10位）
    • 页表索引（10位）
    • 页内偏移量（12位） 总共32位（4字节），即每个虚拟地址占用4字节。

  • 机器指令分析：函数 f1 的指令代码从 00401020H 开始，假设这段代码是连续的，并且每条指令占用4字节。

  • 页目录号占10位、页表索引占10位，共占10+10=20位。函数f1的代码段中所有指令的虚拟地址的高20位相同，均为00401H，则所有的指令在同一页中。因此，函数 f1 的机器指令代码占用1页。

(2) 取第1条指令（push ebp）时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从0开始）？

  • push ebp 指令的虚拟地址：00401020H

    • 虚拟地址格式：

      • 页目录号（10位）：0000000001（即 1）
      • 页表索引（10位）：0000000001（即 1）
      • 页内偏移量（12位）：000000001000（即 16）

  • 页目录访问：

    • 页目录号为 1，因此访问页目录的第 1 个表项（编号从0开始）。

  • 页表访问：

    • 页表索引为 1，因此访问页表的第 1 个表项（编号从0开始）。

(3) M的I/O采用中断控制方式。若进程P在调用 f1 之前通过 scanf() 获取 n 的值，则在执行 scanf() 的过程中，进程P的状态会如何变化？CPU是否会进入内核态？

  • 进程状态变化：

    • 在执行 scanf() 时，进程P需要等待用户输入，因此进程P会从 执行态 转变为 阻塞态（因为它在等待I/O）。
    • 用户输入完成后，输入数据会触发一个中断，进程P被中断服务程序唤醒并转为 就绪态。
    • 当调度程序再次调度进程P时，它会进入 运行态。

  • CPU是否进入内核态：

    • scanf() 是一个涉及 I/O 操作的库函数，在 I/O 操作过程中，CPU 必须进入 内核态 以确保对 I/O 设备的访问和控制。
    • 因此，在执行 scanf() 期间，CPU 会进入内核态。

总结：

  1. 函数 f1 的机器指令代码占用 1 页。
  2. 访问 push ebp 指令时，访问页目录的第1个表项和页表的第1个表项。
  3. 在执行 scanf() 时，进程P会从 执行态 变为 阻塞态，并且 CPU 会进入 内核态。

PV问题

✅ 第46题：线程同步与互斥

问题：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//复数的结构类型定义
typedef struct
{
    float a;
    float b;
}cnum;
cnum x, y, z; //全局变量

//计算两个复数之和
cnum add(cnum p, cnum q)
{
    cnum s;
    s.a = p.a + q.a;
    s.b = p.b + q.b;
    return s;
}

thread1
{
    cnum w;
    w = add(x, y);
    ...
}

thread2
{
    cnum w;
    w = add(y, z);
    ...
}

thread3
{
    cnum w;
    w.a = 1;
    w.b = 2;
    z = add(z, w);
    y = add(y, w);
    ...
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
semaphore mutex_y1; // mutex_y1用于thread1和thread3对变量y的互斥访问
semaphore mutex_y2; // mutex_y2用于thread2和thread3对变量y的互斥访问
semaphore mutex_z;  // mutex_z用于变量z的互斥访问

//复数的结构类型定义
typedef struct
{
    float a;
    float b;
}cnum;
cnum x, y, z; //全局变量

//计算两个复数之和
cnum add(cnum p, cnum q)
{
    cnum s;
    s.a = p.a + q.a;
    s.b = p.b + q.b;
    return s;
}

thread1
{
    cnum w;
    wait(mutex_y1); // 等待mutex_y1以保证对y的互斥访问
    w = add(x, y);
    signal(mutex_y1); // 释放mutex_y1
    ...
}

thread2
{
    cnum w;
    wait(mutex_y2); // 等待mutex_y2以保证对y的互斥访问
    wait(mutex_z);  // 等待mutex_z以保证对z的互斥访问
    w = add(y, z);
    signal(mutex_z); // 释放mutex_z
    signal(mutex_y2); // 释放mutex_y2
    ...
}

thread3
{
    cnum w;
    w.a = 1;
    w.b = 2;
    wait(mutex_z);  // 等待mutex_z以保证对z的互斥访问
    z = add(z, w);
    signal(mutex_z); // 释放mutex_z
    wait(mutex_y1);  // 等待mutex_y1以保证对y的互斥访问
    wait(mutex_y2);  // 等待mutex_y2以保证对y的互斥访问
    y = add(y, w);
    signal(mutex_y1); // 释放mutex_y1
    signal(mutex_y2); // 释放mutex_y2
    ...
}

总结：

  1. mutex_y1：用于保证 thread1 和 thread3 对全局变量 y 的互斥访问。
  2. mutex_y2：用于保证 thread2 和 thread3 对全局变量 y 的互斥访问。
  3. mutex_z：用于保证 thread2 和 thread3 对全局变量 z 的互斥访问。

通过合理地设计信号量操作，可以确保线程在访问临界资源时互斥，同时尽可能地提高并发性。