2019年408真题操作系统篇

第23题：关于线程的描述

问题： 下列关于线程的描述中，错误的是（ ）。

A. 内核级线程的调度由操作系统完成 B. 操作系统为每个用户级线程建立一个线程控制块 C. 用户级线程间的切换比内核级线程间的切换效率高 D. 用户级线程可以在不支持内核级线程的操作系统上实现

解答：

  • A. 正确。 内核级线程的调度是由操作系统负责的，操作系统会创建、管理、调度内核级线程，调度机制通常由操作系统内核来执行。
  • B. 错误。 操作系统并不总是为每个用户级线程建立独立的线程控制块。用户级线程通常是由用户级线程库来管理，操作系统可能只为内核级线程（操作系统直接管理的线程）建立线程控制块。用户级线程的管理和调度通常是通过用户空间的库来完成，而不是由操作系统直接支持。
  • C. 正确。 用户级线程切换通常比内核级线程切换更高效，因为用户级线程切换只涉及用户空间的操作，不需要进入内核态进行上下文切换，因此避免了内核态的开销。
  • D. 正确。 用户级线程的实现和管理通常不依赖于操作系统提供的内核级线程支持。在不支持内核级线程的操作系统上，用户级线程库可以在用户空间中实现线程的创建、调度等操作。

本题选 B。

第24题：进程唤醒的事件

问题： 下列选项中，可能会将进程唤醒的事件是（ ）。

Ⅰ. I/O结束 Ⅱ. 某进程退出临界区 Ⅲ. 当前进程的时间片用完

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

解答：

进程唤醒是指将处于阻塞状态的进程转换为就绪态，以便操作系统能够将其调度执行。

  • Ⅰ. 正确。 当一个进程的I/O操作完成时，如果该进程处于阻塞态（等待I/O完成），则它会被唤醒，进入就绪态，等待调度器将其调度执行。
  • Ⅱ. 正确。 当一个进程退出临界区并释放了相关的共享资源，其他被阻塞的进程（等待获取该资源的进程）将会被唤醒，进入就绪态。
  • Ⅲ. 错误。 当前进程的时间片用完时，它会被从运行态切换到就绪态，释放CPU，但这不会唤醒一个阻塞的进程。时间片耗尽与进程唤醒无关，它仅影响已经在运行的进程。

本题选 C。

第25题：系统调用的叙述

问题： 下列关于系统调用的叙述中，正确的是（ ）。

Ⅰ. 在执行系统调用服务程序的过程中，CPU处于内核态 Ⅱ. 操作系统通过提供系统调用避免用户程序直接访问外设 Ⅲ. 不同的操作系统为应用程序提供了统一的系统调用接口 Ⅳ. 系统调用是操作系统内核为应用程序提供服务的接口

解答：

  • Ⅰ. 正确。 系统调用是通过用户程序发起的，而在执行系统调用时，程序会从用户态切换到内核态，以便操作系统执行需要特权权限的操作。

  • Ⅱ. 正确。 系统调用提供了一种机制，用户程序无法直接访问硬件外设，而是通过系统调用接口向操作系统请求外设的操作，操作系统会进行相应的权限检查和操作。

  • Ⅲ. 错误。 不同的操作系统有不同的系统调用接口和实现。例如，Linux、Windows等操作系统的系统调用接口是不同的，因此它们并没有提供统一的系统调用接口。

  • Ⅳ. 正确。 系统调用是应用程序和操作系统内核之间的接口，应用程序通过系统调用请求操作系统提供的服务，如文件操作、进程控制等。

综上，仅Ⅰ、Ⅱ、Ⅳ正确。

本题选 C。

第26题：用于文件系统管理空闲磁盘块的数据结构

问题： 下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（ ）。

Ⅰ. 位图 Ⅱ. 索引节点 Ⅲ. 空闲磁盘块链 Ⅳ. 文件分配表 (FAT)

解答：

  • Ⅰ. 正确。 位图是一种数据结构，用于表示磁盘块的分配情况。每个位代表一个磁盘块，位的值为1表示该磁盘块已分配，位的值为0表示该磁盘块空闲。位图是管理空闲磁盘块的常用方法。

  • Ⅱ. 错误。 索引节点（inode）用于表示文件或目录的数据结构，管理文件的元数据，如权限、大小和磁盘块位置，而不是专门用于管理空闲磁盘块。

  • Ⅲ. 正确。 空闲磁盘块链是一种链表数据结构，用于管理空闲磁盘块。每个空闲磁盘块都有一个指向下一个空闲块的指针，形成一个链表，可以有效地分配和回收磁盘块。

  • Ⅳ. 正确。 文件分配表（FAT）是一种数据结构，记录了文件在磁盘上的分布情况。FAT表也可以用于管理磁盘上的空闲磁盘块，通过标记哪些块是空闲的来进行管理。

综上，仅Ⅰ、Ⅲ、Ⅳ正确。

本题选 B。

第27题：二级反馈队列调度算法

问题： 系统采用二级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2。若当前Q1、Q2为空，系统依次创建进程P1、P2后即开始进程调度，P1、P2需要的CPU时间分别为30ms和20ms，则进程P1、P2在系统中的平均等待时间为（ ）。

选项： A. 25ms B. 20ms C. 15ms D. 10ms

解答：

  1. P1的执行过程：

    • P1需要30ms的CPU时间，首先进入Q1队列。
    • Q1采用时间片轮转调度算法，时间片为10ms。因此P1会执行10ms，然后剩余时间为30ms - 10ms = 20ms，接着进入Q2。

  2. P2的执行过程：

    • P2需要20ms的CPU时间，首先也进入Q1队列。
    • P2执行10ms后，剩余时间为20ms - 10ms = 10ms，转入Q2队列。

  3. Q2队列的执行过程：

    • Q2采用短进程优先调度算法，因此P2会优先执行。P2在Q2队列中执行10ms，完成其执行。
    • 然后P1执行剩余的20ms。

  4. 甘特图（进程执行顺序）：

    1
    | P1(10ms) | P2(20ms) | P1(20ms) |

  5. P1和P2的等待时间：

    • P1的等待时间：P1的总等待时间 = 30ms - 10ms = 20ms
    • P2的等待时间：P2的总等待时间 = 10ms - 0ms = 10ms

  6. 平均等待时间：

    • 平均等待时间 = (20ms + 10ms) / 2 = 15ms

本题选 C。

扩展题：三级反馈队列调度算法

问题： 系统采用三级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用时间片轮转调度算法，时间片为20ms；就绪队列Q3采用先来先服务先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程，当Q2为空时系统才会调度Q3中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2；Q2中的进程执行一个时间片后，若未结束，则转入Q3。若当前Q1、Q2、Q3为空，系统依次创建进程P1、P2、P3后即开始进程调度，P1、P2、P3需要的CPU时间分别为60ms、60ms和60ms，则进程P1、P2、P3在系统中的平均等待时间为（ ）。

参考答案：90ms

解答：

  1. P1、P2、P3的执行过程：

    • 初始时，P1、P2、P3依次进入Q1队列，每个进程会在Q1执行一个时间片（10ms）。因此，P1、P2、P3各自会执行10ms，剩余时间分别为50ms。
    • 因为Q1已经用完，所有进程都转移到Q2队列，在Q2队列中每个进程会执行20ms，因此P1、P2、P3剩余的时间将减少20ms，剩余时间为30ms。
    • 之后，所有进程都会转移到Q3队列，在Q3队列中按照先来先服务的顺序执行。

  2. 甘特图（进程执行顺序）：

    1
    | P1(10ms) | P2(10ms) | P3(10ms) | P1(20ms) | P2(20ms) | P3(20ms) | P1(30ms) | P2(30ms) | P3(30ms) |

  3. P1、P2、P3的等待时间：

    • P1的等待时间：30ms（Q2执行时间） + 30ms（Q3执行时间） = 60ms
    • P2的等待时间：30ms（Q2执行时间） + 30ms（Q3执行时间） = 60ms
    • P3的等待时间：30ms（Q2执行时间） + 30ms（Q3执行时间） = 60ms

  4. 平均等待时间：

    • 平均等待时间 = (60ms + 60ms + 60ms) / 3 = 90ms

本题参考答案：90ms

第28题：分段存储管理系统中的共享段

问题： 在分段存储管理系统中，用共享段表描述所有被共享的段。若进程P1和P2共享段S，下列叙述中，错误的是（ ）。

选项： A. 在物理内存中仅保存一份段S的内容 B. 段S在P1和P2中应该具有相同的段号 C. P1和P2共享段S在共享段表中的段表项 D. P1和P2都不再使用段S时才回收段S所占的内存空间

解答：

  1. A正确：在分段存储管理系统中，如果多个进程共享同一段，则物理内存中只需要保存该段的一份内容，避免重复占用内存空间。
  2. B错误：每个进程都有自己的段表，在段表中对每个段有自己的段号。如果进程P1和P2共享段S，它们的段号可以不同，主要通过共享段表中的段表项来保证两个进程访问的是同一段。因此，段号在P1和P2中可以不同。
  3. C正确：共享段表的作用是描述所有被共享的段，P1和P2共享段S时，会在共享段表中维护段S的段表项，记录该段的相关信息，如基地址、段长、共享权限等。
  4. D正确：在回收共享段S所占内存空间时，操作系统会通过计数器等机制来追踪是否所有进程都已经不再使用该段，只有在P1和P2都不再使用该段时，才会回收该段所占的内存空间。

本题选 B。

第29题：LRU页置换算法

问题： 某系统采用LRU页置换算法和局部置换策略，若系统为进程P预分配了4个页框，进程P访问页号的序列为0, 1, 2, 7, 0, 5, 3, 5, 0, 2, 7, 6，则进程访问上述页的过程中，产生页置换的总次数是（ ）。

选项： A. 3 B. 4 C. 5 D. 6

解答：

LRU（Least Recently Used）页置换算法选择最近最久未使用的页面进行置换。

模拟过程如下（标注红色表示未命中，蓝色表示置换，绿色表示命中）：

  • 访问页号0：页框空，置换页0。 页框：[0]
  • 访问页号1：页框中没有1，置换页1。 页框：[0, 1]
  • 访问页号2：页框中没有2，置换页2。 页框：[0, 1, 2]
  • 访问页号7：页框中没有7，置换页7。 页框：[0, 1, 2, 7]
  • 访问页号0：页框中有0，命中。 页框：[0, 1, 2, 7]
  • 访问页号5：页框中没有5，置换最久未使用的页1，置换页5。 页框：[0, 2, 7, 5]
  • 访问页号3：页框中没有3，置换最久未使用的页2，置换页3。 页框：[0, 7, 5, 3]
  • 访问页号5：页框中有5，命中。 页框：[0, 7, 5, 3]
  • 访问页号0：页框中有0，命中。 页框：[0, 7, 5, 3]
  • 访问页号2：页框中没有2，置换最久未使用的页7，置换页2。 页框：[0, 2, 5, 3]
  • 访问页号7：页框中没有7，置换最久未使用的页5，置换页7。 页框：[0, 2, 7, 3]
  • 访问页号6：页框中没有6，置换最久未使用的页3，置换页6。 页框：[0, 2, 7, 6]

产生页置换的次数： 共有5次置换：页1、页2、页3、页5、页7。

本题选 C。

第30题：死锁的叙述

问题： 下列关于死锁的叙述中，正确的是（ ）。

选项： A. 仅Ⅱ、Ⅲ B. 仅Ⅰ、Ⅱ、Ⅳ C. 仅Ⅰ、Ⅱ、Ⅲ D. 仅Ⅰ、Ⅲ、Ⅳ

解答：

  1. Ⅰ正确：可以通过剥夺进程资源解除死锁。通过抢占进程正在占用的资源，并分配给其他进程，帮助解除死锁状态。
  2. Ⅱ正确：死锁的预防方法能够确保系统不发生死锁。通过采取措施破坏死锁发生的四个必要条件（互斥条件、请求与保持条件、不剥夺条件和循环等待条件），从而避免死锁的发生。
  3. Ⅲ错误：银行家算法是一种死锁避免算法，它通过检查系统是否处于安全状态，判断是否可以分配资源，防止进入死锁状态。银行家算法不能判断系统是否已经处于死锁状态。
  4. Ⅳ正确：当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态。死锁的特点是进程互相等待资源，导致它们无法继续执行，因此至少有两个进程处于阻塞状态。

综上，正确答案是： 本题选 B。

第31题：虚拟地址转换为页目录号和页号

问题： 某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：

页目录号 页号 页内偏移
10位 10位 12位

虚拟地址 20501225H 对应的页目录号、页号分别是（ ）。

选项： A. 081H、101H B. 081H、401H C. 201H、101H D. 201H、401H

解答：

虚拟地址 20501225H 转换过程如下：

  1. 将地址 20501225H 转换为二进制： 20501225H = 0010 0000 0100 0001 0000 0010 0010 0101。
  2. 根据地址结构：
    • 页目录号：前10位 = 0010 0000 01 = 081H。
    • 页号：接下来10位 = 0100000001 = 101H。

所以，虚拟地址对应的页目录号是 081H，页号是 101H。

本题选 A。

第32题：动态分区分配算法与内存碎片

问题： 在下列动态分区分配算法中，最容易产生内存碎片的是（ ）。

选项： A. 首次适应算法 B. 最坏适应算法 C. 最佳适应算法 D. 循环首次适应算法

解答：

  1. 首次适应算法：从空闲分区表的第一个表目起查找，找到第一个能满足作业需求的空闲分区，并分配给作业。这种方法的主要目的是减少查找时间，但可能会留下很多小的空闲区，导致内存碎片。
  2. 最佳适应算法：从所有空闲分区中选择能满足作业要求且最小的空闲分区。虽然这种方法可以保证每次分配最合适的空间，但它会导致较小的空闲分区频繁产生，增加了内存碎片的数量和大小，因为较大的空闲空间容易被切割成小块，从而增加碎片。
  3. 最差适应算法：从所有空闲分区中选择能满足作业要求且最大的空闲分区。虽然这种方法可以减少小碎片的产生，但它可能会使空闲链表中的区块大小均匀化，长期下来也可能产生不连续的较大碎片。
  4. 循环首次适应算法：每次查找从上次查找位置的下一个位置开始，找到第一个能满足需求的空闲分区。这种方法与首次适应算法类似，也可能产生一些内存碎片。

总结： 最佳适应算法最容易产生内存碎片，因为它倾向于选择最小的空闲分区，导致碎片化严重。

本题选 C。

哲学家进餐问题

第43题：哲学家进餐问题

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

解答：

方法一： 使用哲学家进餐问题的模板一，并考虑碗的数量m与最大可进餐名额数量n-1，限制碗的数量为min{m, n-1}，得到新的最大可进餐名额数量。本题适合采用此方法，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
semaphore bowls = min(n-1, m);    // 可用碗数量，即进餐名额数量
semaphore chopsticks[n];   // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
    chopsticks[i] = 1;  // 初始化每根筷子
}

CoBegin
Process 哲学家i() {
    while (true) {
        思考;
        P(bowls);  // 获取碗
        P(chopsticks[i]);    // 获取左边的筷子
        P(chopsticks[(i+1)%n]);    // 获取右边的筷子
        进餐;
        V(chopsticks[i]);    // 放回左边的筷子
        V(chopsticks[(i+1)%n]);    // 放回右边的筷子
        V(bowls);    // 放回碗
    }
}
CoEnd

信号量及初值说明：

  1. bowls（碗的信号量）：
    • 初值为 min(n-1, m)，表示最多有 min(n-1, m) 位哲学家可以同时就餐。n-1 是为了防止死锁，最多允许 n-1 位哲学家同时进餐。
    • 碗的数量限制了同时进餐的哲学家数量，当碗资源不足时，未能获得碗的哲学家将无法继续进餐。
  2. chopsticks[n]（筷子的信号量）：
    • 每根筷子的初值为1，表示每根筷子是可用的。哲学家只有获得左右两根筷子后才能进餐。

分析：

  • 每位哲学家在进餐前需要获取一只碗和两根筷子。
  • P(bowls) 操作用于获取碗资源，每个哲学家在开始进餐前都需要获得一个碗。碗的数量限制了最多可以同时进餐的哲学家数量。
  • P(chopsticks[i]) 和 P(chopsticks[(i+1)%n]) 分别获取左右两侧的筷子。只有当两根筷子都被拿到时，哲学家才能开始进餐。
  • 进餐完成后，使用 V(chopsticks[i]) 和 V(chopsticks[(i+1)%n]) 操作释放筷子资源，允许其他哲学家使用。
  • V(bowls) 操作用于放回碗资源，允许其他哲学家使用。

总结： 通过限制碗的数量和使用信号量控制进餐的并发数量，可以避免死锁并有效管理资源。在每次进餐过程中，哲学家必须依次获取碗和筷子，确保不会出现多个哲学家同时持有同一资源的情况。

磁盘存储

第44题：计算机磁盘存储管理

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

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

解答：

(1) 磁盘的容量是多少？

磁盘的容量由以下因素决定：

  • 总柱面数 = 300
  • 每个柱面上的磁道数 = 10
  • 每个磁道上的扇区数 = 200
  • 每个扇区的大小 = 512B

首先，计算磁盘的总扇区数： \(\text{总扇区数} = 300 \times 10 \times 200 = 600000 \text{ 扇区}\)

然后，计算磁盘的总容量： \(\text{磁盘容量} = 600000 \times 512 \text{ B} = 307200000 \text{ B} = 307200 \text{ KB} = 300 \text{ MB}\)

所以，磁盘的容量是 300 MB。

(2) 若采用最短寻道时间优先 (SSTF) 调度算法，系统访问簇的先后次序是什么？

根据给定的簇号，首先计算每个簇所在的柱面号：

  • 每个柱面有1000个簇（因为每个柱面有10个磁道，每个磁道200个扇区，每个簇包含2个扇区）： \(\text{每个柱面的簇数} = 10 \times 200 / 2 = 1000 \text{ 个簇}\)

  • 簇号100260对应的柱面号： \(\text{柱面号} = \left\lfloor \frac{100260}{1000} \right\rfloor = 100\)

  • 簇号60005对应的柱面号： \(\text{柱面号} = \left\lfloor \frac{60005}{1000} \right\rfloor = 60\)

  • 簇号101660对应的柱面号： \(\text{柱面号} = \left\lfloor \frac{101660}{1000} \right\rfloor = 101\)

  • 簇号110560对应的柱面号： \(\text{柱面号} = \left\lfloor \frac{110560}{1000} \right\rfloor = 110\)

磁头当前在85号柱面上，采用最短寻道时间优先(SSTF)调度算法，访问顺序如下：

  • 从85号柱面出发，距离100号柱面的距离最小（100 - 85 = 15），先访问100号柱面。
  • 访问100号柱面后，距离101号柱面的距离最小（101 - 100 = 1），接着访问101号柱面。
  • 访问101号柱面后，距离110号柱面的距离最小（110 - 101 = 9），接着访问110号柱面。
  • 最后，访问距离60号柱面的距离最小（85 - 60 = 25），访问60号柱面。

因此，系统访问簇的先后次序是： 100260、101660、110560、60005

(3) 第100530簇在磁盘上的物理地址是什么？

  • 每个柱面有1000个簇，每个磁道有100个簇，因此可以计算出第100530簇在磁盘上的物理地址：

  1. 柱面号： \(\text{柱面号} = \left\lfloor \frac{100530}{1000} \right\rfloor = 100\)

  2. 磁道号（柱面内的磁道号）： \(\text{磁道号} = \left\lfloor \frac{100530 \mod 1000}{100} \right\rfloor = \left\lfloor \frac{530}{100} \right\rfloor = 5\)

  3. 扇区号（磁道内的扇区号）： \(\text{扇区号} = (100530 \mod 100) \times 2 = 30 \times 2 = 60\)

因此，第100530簇的物理地址是：柱面号100，磁道号5，扇区号60。

I/O系统程序：

将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成，它负责处理从文件系统到物理磁盘的映射。

总结：

  • 磁盘容量：300 MB。
  • 最短寻道时间优先调度（SSTF）下的访问顺序：100260、101660、110560、60005。
  • 第100530簇的物理地址：柱面号100，磁道号5，扇区号60。
  • 簇号转换为物理地址的程序：磁盘驱动程序。