23级计院操作系统期末试题

23级计院操作系统期末试题 A 卷解析与答案

本文根据 23级计院操作系统期末.pdf 整理。试卷结构比较典型：选择题覆盖概念辨析，后面大题集中考进程互斥同步、处理机调度、银行家算法、虚拟页式存储、磁盘调度和 PV 操作。

一、单项选择

答案汇总：

二、简答题

1. 死锁与饿死的相同点和不同点

相同点：

• 都会导致某些进程长期不能向前推进。
• 都与资源分配、调度策略或同步机制有关。
• 都可能表现为进程长时间等待资源或处理机。

不同点：

• 死锁是多个进程形成相互等待关系，例如 P1 等 P2 的资源，P2 又等 P1 的资源，通常需要外部干预才能打破。
• 饿死是某个进程长期得不到资源或处理机，原因常是调度/分配策略不公平，例如高优先级进程不断到来、SSTF 长期服务近处磁道。
• 死锁进程集合中的进程通常都处于阻塞等待状态；饿死进程未必一直阻塞，也可能反复进入就绪队列但总是选不上。
• 死锁强调循环等待等 Coffman 条件；饿死强调等待时间无上界和公平性不足。

2. 磁头粘性

“磁头粘性”指磁盘调度中，如果新请求不断加入当前扫描队列，尤其集中在当前磁头附近或当前扫描方向上，磁头可能不断服务这些新来的近处请求，迟迟离不开某一区域，使远处请求长时间等待。

如果每个磁道各有一个磁头，则不存在移动磁头在磁道之间来回移动的问题，也就不存在原意义上的“磁头粘性”。仍可能有请求队列公平性问题，但不是由移动磁头调度造成的粘性。

3. test_and_set 算法的有限等待问题与改进

原算法：

do {
    while (test_and_set(&lock)) continue;
    临界区;
    lock = 0;
    其余部分;
} while (1);

不满足有限等待的原因：

当某进程离开临界区并把 lock 置 0 后，所有等待进程和新来的进程同时竞争 test_and_set。某个等待已久的进程可能反复竞争失败，被其他进程一次次抢先进入临界区，因此等待次数没有上界。

可用等待数组改进：

boolean waiting[n] = { false };
boolean lock = false;

do {
    waiting[i] = true;
    boolean key = true;

    while (waiting[i] && key) {
        key = test_and_set(&lock);
    }
    waiting[i] = false;

    /* 临界区 */

    int j = (i + 1) % n;
    while (j != i && !waiting[j]) {
        j = (j + 1) % n;
    }

    if (j == i) {
        lock = false;
    } else {
        waiting[j] = false;
    }

    /* 其余部分 */
} while (true);

解释：退出临界区时不是让所有进程无序抢锁，而是按循环顺序把进入权交给下一个正在等待的进程。这样每个等待进程至多被前面的有限个进程越过，满足有限等待。

三、处理机调度

进程表：

采用最短剩余时间优先。若剩余时间相同，保持当前进程或按先到达者优先。

Gantt 图：

0    3    9    14   19   26
| P1 | P2 | P3 | P4 | P1 |

计算表：

所以：

• 平均等待时间：(16+0+5+7)/4 = 7ms
• 平均周转时间：(26+6+10+12)/4 = 13.5ms
• 平均带权周转时间：(2.6+1.0+2.0+2.4)/4 = 2.0

四、死锁问题

题面表格中 P0 的 D 类资源有一处不一致：P0 的 Allocation(D)=2，但 Max(D)=0，这违反银行家算法要求的 Max >= Allocation。下面先按题面数字计算；如果把 P0 的 Max(D) 修正为 2，则只有 P0 的 Need 中 D 项由 -2 改为 0，安全性结论不变。

当前 Available：

Available = (1, 5, 2, 0)

Allocation：

Max：

1. 等待进程与资源总量

以 Need <= Available 判断当前能否继续完成：

• P0 的 Need 可由当前 Available 满足。
• P1、P2、P3 当前 Need 不能由 Available 满足，可认为处于等待状态。

系统资源总量：

Total = Available + sum(Allocation)
      = (1,5,2,0) + (1,3,7,7)
      = (2,8,9,7)

2. Need 矩阵

Need = Max - Allocation：

若修正 P0 的 Max(D)=2，则 P0 的 Need 为 (1,3,1,0)。

3. 安全性

初始：

Work = Available = (1,5,2,0)

P0 可完成，释放其 Allocation：

Work = (1,5,2,0) + (0,0,1,2) = (1,5,3,2)

此时：

• P1 Need (0,7,5,6)，B、C、D 不满足。
• P2 Need (2,0,0,2)，A 不满足。
• P3 Need (0,6,4,5)，B、C、D 不满足。

因此不能找到完整安全序列，系统不处于安全状态。只能得到部分序列 P0，不存在完整安全序列。

4. P1 请求 (0,4,2,0) 能否满足

先检查：

Request1 = (0,4,2,0)
Need1    = (0,7,5,6)      满足 Request <= Need
Available= (1,5,2,0)      满足 Request <= Available

试分配后：

Available' = (1,1,0,0)
Need1'     = (0,3,3,6)

用 Work=(1,1,0,0) 做安全性检查，没有任何进程的 Need 能被满足。因此试分配后系统不安全，请求不能被满足，应拒绝或让 P1 等待。

五、存储管理

页框大小 4KB，所以页内位移为低 12 位。访问逻辑地址对应页号：

本解按如下口径处理：页框按需分配；同一次缺页若要同时调入当前页和下一页，则作为一次连续页框申请，用最佳适应算法选择空闲块；进程最多占 6 个页框；超过 6 页时按局部 LRU 淘汰；预调入但未真正访问的页访问位为 0。

初始空闲页框表：

访问过程：

1. 访问页 2，页 3 不在内存，同时调入页 2、页 3。申请 2 个页框，最佳适应选 (196,3)，分配 196、197，剩余 (198,1)。
2. 访问页 3，命中，访问位置 1。
3. 访问页 9，页 10 不在内存，同时调入页 9、页 10。申请 2 个页框，最佳适应选 (31,7)，分配 31、32，剩余 (33,5)。
4. 访问页 1，下一页 2 已在内存，只调入页 1。申请 1 个页框，最佳适应选 (198,1)，分配 198。
5. 访问页 6，页 7 不在内存，应调入页 6、页 7。此时已有 5 页，先从 (33,5) 分配页框 33 给页 6；再调页 7 时已达 6 页上限，按 LRU 淘汰预调入且未被访问的页 10，用其页框 32 装入页 7。

1. 访问前五个地址后的页表

这里约定内外标志 1 表示在内存，0 表示在外存。

其他页未在内存中，可记为：

页框号 = -, 访问位 = 0, 内外标志 = 0

其中页 10 曾被预调入，但后来被页 7 置换出去。

2. 空闲页框表

分配后空闲页框表为：

说明：页 10 被淘汰时，其页框 32 被页 7 直接复用，不回到系统空闲页框表。

3. 继续访问 8AC2H 后的页表与物理地址

8AC2H 的页号是 8，页内位移是 AC2H。访问页 8 时，下一逻辑页 9 已经在内存，所以只调入页 8。进程已满 6 页，按 LRU 淘汰预调入但未访问的页 7，将页 8 装入页框 32。

访问后的页表：

逻辑地址 8AC2H 的物理地址：

页框号 = 32 = 20H
页内位移 = AC2H
物理地址 = 32 * 1000H + AC2H = 20AC2H

六、磁盘引臂调度算法

磁道由外向内编号为 0、1、2、...、249，所以“向外移动”表示磁道号变小。N-Step LOOK，N=4，将请求序列分成：

Q1: 90, 15, 200, 50
Q2: 10, 180, 70, 240
Q3: 120, 30

当前磁头在 100，向外即向小磁道号移动。

调度过程：

• Q1：从 100 向外服务 90、50、15，再反向服务 200。
• Q2：上一批结束时方向为向内，从 200 向内服务 240，再反向服务 180、70、10。
• Q3：上一批结束时方向为向外，从 10 向外无请求，于是反向服务 30、120。

调度序列：

90, 50, 15, 200, 240, 180, 70, 10, 30, 120

磁头移动量：

|100-90| + |90-50| + |50-15| + |15-200| + |200-240|
+ |240-180| + |180-70| + |70-10| + |10-30| + |30-120|
= 10 + 40 + 35 + 185 + 40 + 60 + 110 + 60 + 20 + 90
= 650 个磁道

时间计算：

• 总寻道时间：650 * 0.8ms = 520ms
• 磁盘转速：6000r/min = 100r/s，一圈 10ms
• 平均旋转延迟：半圈 5ms，10 次请求共 50ms
• 每道 60 个扇区，每次访问 1 个扇区，单扇区传输时间 10ms/60 = 1/6ms
• 总传输时间：10 * 1/6ms = 1.67ms

总访问处理时间：

520 + 50 + 1.67 = 571.67ms

七、信号量与 PV 操作

同步关系分析

关键约束：

• 盘子最多一个水果。
• 爸爸只有在孩子请求时才放对应水果。
• 放水果或取水果的人必须先获得一个座位。
• 如果孩子发现盘子为空，要叫醒爸爸；等待爸爸放水果时不应占着座位，否则两个孩子可能占满 2 个座位，爸爸无法坐下放水果而死锁。
• 同一时刻只允许一个孩子发出并等待一个水果请求，避免爸爸收到多个请求而盘子只能放一个水果。

信号量设置

semaphore seat = 2;        // 两个座位
semaphore order = 1;       // 一次只处理一个孩子的水果请求
semaphore request = 0;     // 孩子叫醒爸爸
semaphore appleReady = 0;  // 苹果已放好
semaphore orangeReady = 0; // 橘子已放好
semaphore mutex = 1;       // 保护 plate 和 want

enum Fruit { EMPTY, APPLE, ORANGE };
Fruit plate = EMPTY;
Fruit want = EMPTY;

爸爸进程

Father() {
    while (true) {
        /* 空闲时在沙发上睡觉 */
        P(request);          // 被孩子叫醒

        P(mutex);
        Fruit f = want;
        V(mutex);

        P(seat);             // 放水果前先坐到座位上
        P(mutex);
        plate = f;
        V(mutex);
        V(seat);

        if (f == APPLE) {
            V(appleReady);
        } else {
            V(orangeReady);
        }
    }
}

儿子进程

Son() {
    while (true) {
        P(order);

        P(seat);
        P(mutex);
        if (plate == APPLE) {
            plate = EMPTY;
            V(mutex);
            V(seat);
            V(order);
            eat_apple();
        } else if (plate == EMPTY) {
            want = APPLE;
            V(mutex);
            V(seat);         // 等爸爸时不能占座位

            V(request);      // 叫醒爸爸
            P(appleReady);   // 等苹果放好

            P(seat);         // 取水果前先坐到座位上
            P(mutex);
            plate = EMPTY;
            V(mutex);
            V(seat);

            V(order);
            eat_apple();
        } else {
            /* 盘中是橘子，儿子不能取，释放机会让女儿处理 */
            V(mutex);
            V(seat);
            V(order);
        }
    }
}

女儿进程

Daughter() {
    while (true) {
        P(order);

        P(seat);
        P(mutex);
        if (plate == ORANGE) {
            plate = EMPTY;
            V(mutex);
            V(seat);
            V(order);
            eat_orange();
        } else if (plate == EMPTY) {
            want = ORANGE;
            V(mutex);
            V(seat);         // 等爸爸时不能占座位

            V(request);      // 叫醒爸爸
            P(orangeReady);  // 等橘子放好

            P(seat);         // 取水果前先坐到座位上
            P(mutex);
            plate = EMPTY;
            V(mutex);
            V(seat);

            V(order);
            eat_orange();
        } else {
            /* 盘中是苹果，女儿不能取，释放机会让儿子处理 */
            V(mutex);
            V(seat);
            V(order);
        }
    }
}

正确性与饥饿分析

死锁不会发生：

• 孩子在等待爸爸放水果前释放座位，所以爸爸总能获得座位放水果。
• order 保证同一时刻只有一个孩子提出并等待请求，盘子容量为 1 不会被多个请求破坏。
• 爸爸放完对应水果后必定唤醒对应孩子，孩子取走水果后释放 order。

饥饿问题：

• 若信号量队列和处理机调度是公平的，例如 FIFO 信号量，则不会由该同步算法本身导致饥饿。每个获得 order 的请求都会被爸爸服务，完成后下一个等待者再进入。
• 若使用弱信号量且调度不公平，理论上仍可能饥饿。例如儿子总能抢先获得 order，女儿可能长期得不到请求机会。要彻底避免这种饥饿，可将 order 和 seat 实现为 FIFO 信号量，或额外设置公平排队/轮转机制。