2011年408真题操作系统篇

选择题

问题 23

下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。

A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先

解答：

  • A. 先来先服务
    先来先服务（FCFS）算法是一种非抢占式的调度算法，按照进程到达的顺序进行调度。虽然它不会发生饥饿现象，但并不满足短任务优先。因为FCFS对所有任务一视同仁，不考虑任务的执行时间，可能会导致长任务在短任务之前执行，从而不满足短任务优先。因此，A 错误。
  • B. 高响应比优先
    高响应比优先（HRRN）算法考虑了等待时间和执行时间，响应比 = (等待时间 + 执行时间) / 执行时间。此算法既考虑了短任务优先，也通过增加等待时间的任务的优先级，避免了饥饿现象。随着任务等待时间的增加，它的响应比会变高，从而得到执行机会。所以，高响应比优先既满足短任务优先，又不会发生饥饿现象。B 正确。
  • C. 时间片轮转
    时间片轮转（RR）算法不会导致饥饿现象，因为每个进程都按顺序轮流执行。但它并不保证短任务优先。短任务可能因为时间片的长度被多次中断，导致相对于长任务的执行顺序较晚，因此不满足短任务优先。C 错误。
  • D. 非抢占式短任务优先
    非抢占式短任务优先（SJF）算法会优先执行短任务，确保短任务快速完成，但由于长任务可能长期占用CPU，导致短任务一直无法执行，从而可能发生饥饿现象。D 错误。

本题选B。

问题 24

下列选项中，在用户态执行的是（ ）。

A. 命令解释程序
B. 缺页处理程序
C. 进程调度程序
D. 时钟中断处理程序

解答：

  • A. 命令解释程序
    命令解释程序（Command Interpreter），也称为Shell，运行在用户态。它接收用户输入的命令，解析并执行相应的操作。这是一个典型的用户程序，用户可以直接与之交互，因此运行在用户态。A 正确。
  • B. 缺页处理程序
    缺页处理程序负责处理页面缺失中断，通常在内核态执行。它需要访问内存管理的数据结构，并可能导致内存的换入换出，属于操作系统核心功能，因此在内核态运行。B 错误。
  • C. 进程调度程序
    进程调度程序负责选择和调度进程执行，需要访问操作系统的资源管理部分，并且其操作属于内核功能，因此它在内核态执行。C 错误。
  • D. 时钟中断处理程序
    时钟中断处理程序是处理定时中断的程序，它用于操作系统中处理时间片轮转、进程调度等功能，因此也在内核态执行。D 错误。

本题选A。

问题 25

在支持多线程的系统中，进程P创建的若干个线程不能共享的是（ ）。

A. 进程P的代码段
B. 进程P中打开的文件
C. 进程P的全局变量
D. 进程P中某线程的栈指针

解答：

在多线程的系统中，不同线程共享以下内容：

  • 代码段：所有线程共享相同的代码段，这意味着它们都执行相同的程序代码。
  • 全局变量：线程之间共享进程中的全局变量，因此它们可以读取和修改相同的全局数据。
  • 打开的文件：线程间共享进程中打开的文件，这意味着多个线程可以同时访问相同的文件描述符。

然而，每个线程都有自己独立的：

  • 栈指针：每个线程拥有独立的栈空间，用于存储局部变量、函数调用等信息。栈空间不被其他线程共享，因此栈指针是不能共享的。

本题选D。

问题 26

用户程序发出磁盘I/O请求后，系统的正确处理流程是（ ）。

A. 用户程序→系统调用处理程序→中断处理程序→设备驱动程序
B. 用户程序→系统调用处理程序→设备驱动程序→中断处理程序
C. 用户程序→设备驱动程序→系统调用处理程序→中断处理程序
D. 用户程序→设备驱动程序→中断处理程序→系统调用处理程序

解答：

磁盘I/O请求的正确处理流程为：

  1. 用户程序：用户程序发出磁盘I/O请求，例如读取或写入文件。
  2. 系统调用处理程序：当用户程序通过系统调用请求磁盘I/O时，控制权传递给系统调用处理程序，它将请求传递给操作系统内核。
  3. 设备驱动程序：系统调用处理程序将磁盘I/O请求转交给设备驱动程序，设备驱动程序负责与硬件交互，发出实际的磁盘操作命令。
  4. 中断处理程序：当磁盘I/O操作完成时，硬件产生中断信号，通知操作系统操作已完成。中断处理程序负责处理这个中断并将控制权传回系统。

本题选B。

问题 27

某时刻进程的资源使用情况如下表所示。

此时的安全序列是（ ）。

A. P1, P2, P3, P4
B. P1, P3, P2, P4
C. P1, P4, P3, P2
D. 不存在

解答：

安全序列是指在资源分配的过程中，系统是否能够在不发生死锁的情况下，逐步满足进程的资源需求并释放资源。如果系统中的所有进程都可以按某种顺序执行，并且不会导致死锁，那么该顺序就是安全的。

使用银行家算法来判断是否存在安全序列：

  • 系统必须先检查是否存在足够的资源满足某个进程的需求。如果满足，就可以让这个进程执行，并释放它所持有的资源。
  • 重复这一过程，直到所有进程都能够执行完毕。

在这个题目中，通过模拟资源分配过程，如果最终无法继续执行其他进程（例如因为没有足够的资源），则说明不存在安全序列。

模拟过程：

  • 如果依次执行P1和P4后，R2的可用资源数为2，但P2和P3仍需要3个R2资源才能继续执行，无法满足，系统无法继续分配资源，因此不存在安全序列。

本题选D。

img

问题 28

在缺页处理过程中，操作系统执行的操作可能是（ ）。

Ⅰ. 修改页表
Ⅱ. 磁盘I/O
Ⅲ. 分配页框

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

解答：

缺页异常发生时，操作系统会采取一系列步骤来处理页面缺失问题。主要操作包括：

  1. 修改页表（Ⅰ）：操作系统需要修改页表，将缺失页面映射到主存中的合适页框。当缺页处理完成后，页表中的信息会更新，以便下一次访问该页面时不会发生缺页异常。
  2. 磁盘I/O（Ⅱ）：缺页时，所需要的页面不在主存中，操作系统会通过磁盘I/O将该页面从磁盘调入内存。
  3. 分配页框（Ⅲ）：操作系统需要为缺失的页面分配一个合适的物理页框，以便将页面调入内存。

因此，所有三个操作都会发生。

本题选D。

问题 29

当系统发生抖动 (thrashing) 时，可以采取的有效措施是（ ）。

Ⅰ. 撤销部分进程
Ⅱ. 增加磁盘交换区的容量
Ⅲ. 提高用户进程的优先级

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

解答：

抖动（thrashing） 是指系统在页面置换中频繁地交换数据，导致系统资源浪费，性能急剧下降。引起抖动的主要原因是系统的内存不足，导致进程频繁地请求页面交换，从而导致大量的时间花在页面置换上。

针对抖动现象，可以采取以下措施：

  1. 撤销部分进程（Ⅰ）：通过撤销部分进程，可以释放内存，减轻系统压力，从而减少页面交换的频率，缓解抖动现象。
  2. 增加磁盘交换区的容量（Ⅱ）：增加交换区的容量并不能直接解决内存不足的问题，反而可能会使得页面交换更加频繁，因为系统会尝试将更多数据存入交换区，导致性能更差。
  3. 提高用户进程的优先级（Ⅲ）：提高进程优先级并不能解决内存不足的问题，且可能会加重资源竞争，不利于解决抖动问题。

因此，最有效的措施是 撤销部分进程，通过减少活跃进程来减少页面置换。

本题选A。

问题 30

在虚拟内存管理中，地址变换机构将逻辑地址变为物理地址，将逻辑地址转换为物理地址的阶段是（ ）。

A. 编辑
B. 编译
C. 链接
D. 装载

解答：

虚拟内存管理 中，地址变换机构将逻辑地址（虚拟地址）转换为物理地址。这个过程发生在程序从磁盘加载到内存中时。

各阶段的解释：

  • 编辑（A）：编辑是指程序员编写和修改程序代码的阶段，此时还未涉及地址变换。
  • 编译（B）：编译阶段将源代码转换为目标代码，但编译时地址仍然是逻辑地址（虚拟地址）。
  • 链接（C）：链接阶段将编译后的目标文件与库文件进行连接，生成最终的可执行文件。此时，逻辑地址仍然是虚拟地址，且未进行地址变换。
  • 装载（D）：装载阶段，操作系统将可执行文件从磁盘加载到内存中，并进行地址变换，将虚拟地址转换为物理地址。此时，实际的地址变换过程发生。

因此，装载阶段 负责将逻辑地址转换为物理地址。

本题选D。

形成逻辑地址是链接的时候！

问题 31

某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是（ ）。

A. 1500μs、1000μs
B. 1550μs、1100μs
C. 1550μs、1550μs
D. 2000μs、2000μs

解答：

设定：

  • 磁盘块读入缓冲区的时间 $T = 100\mu s$
  • 缓冲区传送到用户区的时间 $M = 50\mu s$
  • CPU分析时间 $C = 50\mu s$
  • 文件总共有10个磁盘块 $n = 10$

单缓冲区：

  • 对于单缓冲区，每块数据的处理时间是：$\max(T, C) + M$ （即数据传输和CPU分析是并行的）

  • 处理10块数据的时间是：

    • 由于 $\max(T, C) = \max(100\mu s, 50\mu s) = 100\mu s$，每块数据的处理时间为 $100\mu s + 50\mu s = 150\mu s$
    • 总时间计算：

双缓冲区：

  • 对于双缓冲区，每块数据的处理时间是：$\max(C + M, T)$（即数据传输+分析和磁盘读取是并行的）

  • 处理10块数据的时间是：

    • 由于 $C + M = 50\mu s + 50\mu s = 100\mu s$，每块数据的处理时间为 $\max(100\mu s, 100\mu s) = 100\mu s$
    • 总时间计算：

因此，单缓冲区和双缓冲区处理完文件的总时间分别是 1550μs 和 1100μs。

本题选B。

问题 32

有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。

P1 // 加1操作
load R1, x // 取x到寄存器R1中
inc R1
store x, R1 // 将R1的内容存入x

P2 // 减1操作
load R2, x // 取x到寄存器R2中
dec R2
store x, R2 // 将R2的内容存入x

两个操作完成后，x的值（ ）。

A. 可能为-1或3
B. 只能为1
C. 可能为0、1或2
D. 可能为-1、0、1或2

解答：

为了分析这个问题，考虑并发执行时不同的操作顺序和内存的共享情况。操作序列中的指令可能交替执行，因此结果依赖于指令执行的顺序。

  1. 初始情况：变量x的初值为1。
  2. P1加1操作：P1将x读取到寄存器R1中，然后对R1加1，最后将结果存回x。
  3. P2减1操作：P2将x读取到寄存器R2中，然后对R2减1，最后将结果存回x。

分析：

  • 如果P1先执行完加1操作，再执行P2的减1操作，结果是 x=2x = 2。
  • 如果P2先执行完减1操作，再执行P1的加1操作，结果是 x=0x = 0。
  • 如果P1和P2交替执行，例如P1的加1操作和P2的减1操作交替进行，可能出现以下情况：
    • P1执行完加载x到寄存器R1后，P2加载x到寄存器R2并减1，然后P1完成加1操作。此时x的值仍然是1。
    • 另一种交替执行方式可能会导致x的值为1，因为两个操作的影响相互抵消。

综上所述，x的值可能是0、1或2，但不可能为-1或3。

本题选C。

PV问题

问题 45

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

1
2
3
4
5
6
7
8
9
10
11
12
13
cobegin
process 顾客i {
    从取号机获得一个号码;
    等待叫号;
    获得服务;
}
process 营业员 {
    while (TRUE) {
        叫号;
        为顾客服务;
    }
}
coend

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

解答：

本题为典型的生产者消费者问题，顾客为生产者，营业员为消费者，座位区作为缓冲区。我们通过信号量来实现互斥和同步。

需要的信号量：

  1. mutex：用于保护座位区的互斥访问，初值为 1。
  2. empty：表示座位区中的空闲座位数，初值为 10。
  3. full：表示座位区中的顾客数，初值为 0。
  4. service_i：用于顾客等待叫号，初值为 0。
  5. machine：用于取号机的互斥，初值为 1。

顾客和营业员的过程：

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
semaphore mutex = 1;    // 座位区互斥信号量
semaphore empty = 10;   // 座位区空闲位置数量
semaphore full = 0;     // 座位区等待人的数量
semaphore service_i = 0; // 顾客i等待叫号
semaphore machine = 1;  // 取号机

cobegin
process 顾客i {
    P(empty);           // 顾客进入银行时，等待空座位
    P(machine);         // 获取取号机资源
    从取号机获得一个号码; // 顾客取号
    V(machine);         // 释放取号机资源

    P(mutex);           // 互斥进入座位区
    一位顾客进入座位区; // 顾客坐下
    V(mutex);           // 释放座位区互斥

    V(full);            // 增加等待顾客数

    P(service_i);       // 顾客等待叫号
    获得服务;           // 顾客接受服务
}

process 营业员 {
    while (TRUE) {
        P(full);        // 如果有顾客，先减少等待顾客数
        P(mutex);       // 互斥进入座位区
        一位顾客离开座位区; // 顾客站起来等待服务
        V(mutex);       // 释放座位区互斥

        V(empty);       // 增加空座位数

        V(service_i);   // 向顾客发送叫号信号

        叫号;           // 叫号
        为顾客服务;     // 营业员为顾客服务
    }
}
coend

解释：

  • mutex：保护座位区的互斥，防止多个顾客同时进入或离开座位区。
  • empty：表示空闲座位的数量，顾客只有在空座位时才能进入座位区。
  • full：表示当前在座位区等待的顾客数量，营业员需要根据full信号量判断是否可以开始服务。
  • service_i：用于顾客等待叫号，每当顾客被叫号时，service_i信号量将被释放，顾客开始接受服务。
  • machine：保证取号机的互斥，防止多个顾客同时使用取号机。

补充：

  • 如果服务号是针对所有顾客的，可以使用一个散列表来存储顾客的服务号和对应的信号量。这样可以根据不同的顾客服务号来管理每个顾客的等待和服务过程。

总结：

本题通过使用信号量来实现顾客与营业员之间的同步和互斥。顾客在取号机处获取号码后，进入座位区等待服务，营业员根据叫号顺序为顾客提供服务。通过信号量和P、V操作实现了进程间的同步与互斥。

PV问题

问题

某寺庙，有小和尚、老和尚若干。寺庙有一个水缸，由小和尚用水桶从井中提水入缸，老和尚用水桶从缸里取水饮用。水缸可容纳10桶水，水取自同一井中。水井径窄，每次只能容一个水桶取水。水桶总数为3个。每次入水和取水仅为1桶，且不可以同时进行。请用P、V操作给出小和尚、老和尚动作的算法描述。

解答：

信号量的定义：

  1. well：表示水井的互斥信号量，初值为1，确保每次只有一个水桶从水井中取水。
  2. vat：表示水缸的互斥信号量，初值为1，保证每次只有一个进程可以访问水缸（即加水或取水）。
  3. empty：表示水缸的空余空间，初值为10，表示水缸最多可容纳10桶水。
  4. full：表示水缸中已存的水桶数，初值为0，表示水缸开始时为空。
  5. pail：表示可用的水桶数量，初值为3，保证每次操作时有足够的水桶。

小和尚和老和尚的过程描述：

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
semaphore well = 1;    // 互斥访问水井
semaphore vat = 1;     // 互斥访问水缸
semaphore empty = 10;  // 水缸剩余空间能容纳的水的水桶容量数量
semaphore full = 0;    // 水缸中水的水桶容量数量
semaphore pail = 3;    // 可用水桶的数量

cobegin
process 老和尚i {
    while (TRUE) {
        P(full);        // 确保水缸中有水可以取
        P(pail);        // 确保有一个水桶
        P(vat);         // 进入水缸，确保互斥
        从水缸中打一桶水;  // 取出一桶水
        V(vat);         // 离开水缸
        V(empty);       // 增加空余空间
        喝水;           // 喝水
        V(pail);        // 释放水桶
    }
}

process 小和尚i {
    while (TRUE) {
        P(empty);       // 确保水缸中有足够的空间来容纳水
        P(pail);        // 确保有一个水桶
        P(well);        // 互斥访问水井
        从井中打一桶水; // 从水井取水
        V(well);        // 释放水井
        P(vat);         // 进入水缸，确保互斥
        将一桶水倒入水缸;  // 将水倒入水缸
        V(vat);         // 离开水缸
        V(full);        // 增加水缸中水的数量
        V(pail);        // 释放水桶
    }
}
coend

解释：

  1. well：互斥信号量，保证每次只有一个小和尚能从水井中取水，因为水井较窄，最多只能提供一个水桶的水。
  2. vat：互斥信号量，确保每次只有一个进程（无论是小和尚还是老和尚）能访问水缸，防止同时发生加水或取水操作。
  3. empty：表示水缸中剩余的空余空间，每次小和尚加水时减少，保证水缸最多只能存储10桶水。
  4. full：表示水缸中已经有的水桶数，每次老和尚取水时减少，保证水缸中至少有1桶水可供取用。
  5. pail：表示水桶的数量，最多有3个水桶，确保每次操作时有水桶可用。

流程描述：

  • 小和尚：每次从水井取水，先确保有一个水桶（P(pail)），再互斥访问水井（P(well)）。取水后，小和尚将水倒入水缸，并确保水缸中有足够的空间（P(empty)）。倒水后，增加水缸的水桶数量（V(full)）。
  • 老和尚：每次从水缸取水，先确保水缸中有水（P(full)），然后确保有一个水桶（P(pail)）。老和尚取水后，释放水桶（V(pail)），并增加水缸的空余空间（V(empty)）。

总结：

通过上述信号量的设置和P、V操作的实现，保证了小和尚和老和尚的水桶使用互斥，且水缸中的水加水和取水操作不会同时进行，确保了系统的同步和互斥。

文件系统

问题

某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题：

(1) 在连续、链式、索引二种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要在FCB中设计哪些相关描述字段？

(2) 为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

解答

(1) 数据块组织方式的选择

文件数据块的组织方式有三种：连续结构、链式结构和索引结构。

  • 连续结构：
    • 将文件的数据块连续地存储在磁盘上。它适合一次性写入磁盘的文件，因为写入操作简单且不需要频繁扩展。
    • 优点：连续存储可以提供最快的随机访问速度，因为磁盘头无需进行多次跳转，寻道时间较短。
    • 缺点：一旦文件大小发生变化，可能会导致空间浪费或重新分配问题。在文件扩展时，必须有足够的连续空闲空间，这对文件扩展非常不友好。
  • 链式结构：
    • 文件数据通过链表形式存储，每个数据块指向下一个数据块。
    • 优点：可以灵活地进行文件扩展，因为文件的各个部分可以分散存储，不需要连续的空间。
    • 缺点：不适合快速随机访问，因为需要逐块读取文件，增加了磁盘寻道的时间。
  • 索引结构：
    • 文件的每个数据块都有一个索引表，索引表记录了文件数据块的位置。
    • 优点：提供了随机访问的优势，能够高效地定位文件的任意数据块。
    • 缺点：会增加额外的空间开销，索引表本身需要存储空间。

对于本问题的文件系统，由于文件数据是一次性写入并且不可修改，因此文件扩展的问题不需要考虑。最适合的方式是 连续结构，因为：

  • 文件是一次性写入的，不需要考虑后续的扩展，因此连续结构不受限制。
  • 连续结构能够提供最优的访问速度，减少寻道时间。

FCB设计的相关字段：

  • 起始块号：指示文件数据的第一个数据块的位置。
  • 块数：记录文件使用的块的数量。

(2) FCB存储位置选择

FCB（文件控制块）是管理文件元数据的结构，包含文件的名称、大小、权限、起始块号等信息。

  • 集中存储FCB：
    • 将所有文件的FCB集中存储在固定位置。这种方式有以下优点：
      • 减少磁盘I/O次数：将所有FCB集中存储，可以一次性访问所有相关的元数据，减少了磁盘寻道时间和I/O操作。
      • 高效检索：由于文件系统中的FCB数量相对较少，集中存储能够在查找文件时通过较少的磁盘块访问迅速找到所需的文件信息。
      • 易于管理：集中存储方便进行管理和优化，便于对文件控制块进行统一的操作。
  • 与文件数据块连续存储FCB：
    • 这种方式会导致每个文件的元数据与其数据块一起存储，虽然可能减少了寻找文件元数据的次数，但会带来以下问题：
      • 增加磁盘I/O次数：每次访问文件数据时，都需要一起访问文件的FCB，这可能增加不必要的磁盘访问次数。
      • 文件碎片问题：如果文件系统有大量文件，FCB和文件数据一起存储可能导致磁盘空间的碎片化，影响系统的效率。

因此，FCB应该集中存储。这种方式能够减少磁盘访问次数，提高文件访问的效率，尤其是在大量文件系统操作中，集中存储能够提供更好的性能。

总结：

  1. 数据块组织方式：对于一次性写入、不可修改的文件，最合适的方式是 连续结构，因为它能够提供更快的随机访问速度，并减少寻道时间。
  2. FCB存储方式：FCB应 集中存储，这样可以减少磁盘I/O次数，提高文件访问效率。