操作系统期末真题（二）解析

（1）交互型进程最关心的是响应时间。时间片轮转调度让就绪进程轮流获得 CPU，每个进程等待一个有限的轮转周期即可再次执行，因此比先来先服务更适合交互环境。

（2）紧急任务要求一旦就绪就能优先得到 CPU。在给出的算法中，可用静态优先级调度，把紧急任务设置为高优先级；只要采用抢占式优先级调度，高优先级紧急任务可以及时执行。若系统还希望运行过程中根据等待时间等因素调整优先级，则可进一步采用动态优先级。

常见的三类方法如下。

（1）死锁预防：破坏死锁产生的四个必要条件之一。例如规定资源按统一顺序申请，破坏循环等待条件。适用于资源种类和申请规则比较明确、可以接受一定资源利用率损失的系统。

（2）死锁避免：每次分配资源前判断分配后系统是否仍处于安全状态，例如银行家算法。适用于能够预先知道进程最大资源需求量、资源种类和数量相对稳定的系统。

（3）死锁检测与解除：系统允许死锁发生，周期性检测资源分配图或等待关系；检测到死锁后通过撤销进程、抢占资源或回滚等方法解除。适用于死锁发生概率较低、预防或避免代价过大的系统。

独占设备在一个进程使用期间不能被其他进程使用，而设备速度又很慢，因此一个进程长时间占有设备时，其他需要该设备的进程会长时间等待，系统并发程度和设备使用效率受到影响。

一种典型改进方法是 SPOOLing。进程不直接占用慢速独占设备，而是把要进行 I/O 的数据写入磁盘上的输出井（或输入井），由专门的 I/O 进程按照队列顺序统一驱动真实设备。这样，从普通进程的角度看，独占设备被改造成了可以被多个进程同时提交请求的“虚拟共享设备”。

例 1：访问速度与存储空间利用率存在冲突。增大磁盘块可以减少大文件访问时的块数和寻址次数，提高顺序访问效率，但小文件或文件尾部更容易产生内部碎片。设计时可根据典型文件大小选择折中的块大小，或采用多种块/片段机制。

例 2：可靠性与写入性能存在冲突。同步写、日志、数据多副本等机制可以提高崩溃恢复能力和可靠性，但会增加额外 I/O。设计时可以采用日志文件系统、写回缓存、批量提交等方式，在可靠性要求与性能之间折中。

页内地址占 8 位，因此每页大小为 $2^8=256$ 字节。一个 16 位虚拟地址可以直接按十六进制拆成：最高 1 位十六进制数为段号，中间 1 位为页号，最低 2 位为页内偏移。

前四次访问的页面均已在内存中。第 5 次访问 $(2,5)$ 时发生缺页。此前四次访问过的驻留页为 $(2,15)$、$(0,10)$、$(2,15)$、$(0,2)$，而 $(2,8)$ 在这段访问过程中最久未使用，所以按 LRU 将 $(2,8)$ 所在的 69EH 物理块换出，再把 $(2,5)$ 调入 69EH。因此第 5 个物理地址为 69E60H。

快表长度为 2，并采用 LRU。按访问顺序维护：

第一次 $(2,15)$：快表加入 $(2,15)\to48AH$；

第二次 $(0,10)$：加入 $(0,10)\to258H$；

第三次再次访问 $(2,15)$：命中，并把它更新为最近使用；

第四次访问 $(0,2)$：未命中，淘汰最久未使用的 $(0,10)$，加入 $(0,2)\to160H$；

第五次访问 $(2,5)$：缺页处理完成并重新执行后，将 $(2,5)\to69EH$ 加入快表，淘汰 $(2,15)$；

第六次访问 $(0,2)$：快表命中，并把 $(0,2)$ 更新为最近使用。

因此最后两个快表项为 $(2,5)\to69EH$ 和 $(0,2)\to160H$，其中 $(0,2)$ 是最近一次使用的表项。

LRU 利用“最近被访问的页面在近期再次被访问的可能性较大”的局部性规律。从本题访问序列看，2F 页面很快被再次访问，02 页面也在较短间隔后再次访问，所以用 LRU 管理快表能够保留近期使用的表项并产生快表命中。

页面置换方面，第 5 次访问发生缺页时，当前 4 个驻留页中 $(2,8)$ 在本次执行序列中一直未被使用，而其他页面都刚刚被访问，因此将 $(2,8)$ 置换出去符合局部性原则。由于本题只发生一次页面置换，能够观察到的性能差异有限，但该次选择本身是合理的。

只要在某个时刻把 $x$ 变成 12，并且此后两个进程都在再次执行循环体前检查到 $x=12$，两个进程即可退出。

情况 1：P1 先执行一次：$1\to2$；P2 执行一次：$2\to6$；P1 再执行一次：$6\to12$。之后 P1、P2 检查循环条件时都发现 $x=12$，正常结束。

情况 2：P2 先执行一次：$1\to3$；P1 执行一次：$3\to6$；P1 再执行一次：$6\to12$。之后两个进程均检查到 12 并退出。

情况 1：P1 连续获得 CPU，$x$ 依次为 $1,2,4,8,16,32,\ldots$。一旦越过 12，以后再乘 2 或乘 3 都无法回到 12，因此两个进程都无法通过条件 $x=12$ 正常退出。

情况 2：P2 连续执行若干次，$x$ 依次为 $1,3,9,27,81,\ldots$。同样会越过 12，之后只能继续乘 2 或 3，不会回到 12，因此两个进程均不能正常结束。

可以利用两个信号量严格控制前三次乘法的次序为 P1、P2、P1，使 $x$ 必然经历 $1\to2\to6\to12$。设信号量 $s_1=1,s_2=0$：

// P1
P(s1);
while (x != 12) {
    x = x * 2;
    V(s2);
    P(s1);
}

// P2
P(s2);
while (x != 12) {
    x = x * 3;
    V(s1);
    P(s2);
}
V(s1);

开始时 P1 执行一次，使 $x=2$；随后唤醒 P2，P2 使 $x=6$；再唤醒 P1，P1 使 $x=12$。P1 随后等待，P2 被唤醒后重新检查 while 条件并退出，再用最后一个 $V(s_1)$ 唤醒 P1，P1 重新检查条件后也退出。原有的 while 条件和乘法语句均未修改，也没有增加直接改变 $x$ 或强制退出的操作。

每个目录项为 256B，每个磁盘块为 1024B，因此一个目录内容块可存放

个目录项。/data 下共有 801 个文件，所以 /data 目录内容占

个磁盘块。

/data 目录自己的单级索引表需要保存 201 个内容块号，每个块号占 8B，共

所以索引表占

个连续磁盘块。

根目录内容已在内存，因此可以直接得到 /data 的索引表起始地址。若 f.dat 恰好在 /data 的第一个目录内容块中，只需读第一个索引表块以取得第一个内容块地址，再读该目录内容块，共 2 块。

若 f.dat 位于最后才能找到的位置，需要读完 2 个索引表块以及 201 个目录内容块，共

块。

文件大小为 $512\text{KB}=512\times1024$B，每个内容块 1024B，因此文件占 512 个内容块。每个块号 8B，所以索引表大小为

即占

个磁盘块。

第 409680 个字节所在的逻辑块号为

块内偏移为

因此它位于第 401 个内容块。一个索引表块可放 $1024/8=128$ 个块号，第 401 个内容块对应的索引项编号为 400，位于第 4 个索引表块（索引 384--511）。因为索引表连续，已知起始地址后可直接读第 4 个索引表块，再读目标数据块，共 2 个磁盘块。

一种明显不足是目录查找采用线性扫描。目录项很大（256B），/data 有 801 个目录项，需要占 201 个内容块；如果目标文件靠后，按文件名查找会产生大量磁盘 I/O。

可以将目录组织成哈希目录或 B/B+ 树目录，使文件名能够快速定位到相应目录项。这样可以把大量顺序扫描转换为少量索引查找，尤其适合目录中文件数较多的情况。代价是目录结构更复杂，需要额外索引空间，并增加插入、删除时的维护开销。

如果进程获得的物理内存足以容纳数组所涉及的全部页面，或这些页面已经全部驻留在内存且执行过程中基本不发生缺页，那么从操作系统内存管理角度看，P1 和 P2 都只是对同一批已驻留页面进行访问，缺页开销几乎相同，因此二者执行效率几乎没有区别。

在请求分页且可用物理块不足、会发生频繁页面置换时，二者差异明显。C 数组按行存放，P1 在一行内完成偶数列和奇数列的访问，访问地址总体集中在当前行附近，空间局部性较好；一个页面调入后会被连续访问多次。

P2 按列访问，相邻两次访问 $a[i][j]$ 和 $a[i+1][j]$ 在内存中相隔一整行。若一行大小接近或等于一个页面，则连续访问会不断跳到不同页面；当页框数量不足以容纳这些页面时容易出现大量缺页甚至抖动。因此 P1 效率更高。

可以。题目特别说明 a 是全局变量。C 语言中未显式初始化的全局变量在程序开始执行前按语言规则初始化为 0。因此如果程序的目标只是使整个数组为 0，就不需要再次逐元素写 0，例如：

int a[1024][1024];

int main(void)
{
    return 0;
}

在采用请求分页、按需零填充（demand-zero）等机制的系统中，未真正访问这些数组页面时，操作系统可以暂不为它们分配实际物理页框；需要访问时再提供内容为 0 的页面。因此上述程序既避免了 P1/P2 的大量写操作，也可避免相应的缺页和物理页分配，效率更高。

可以定义：

其中 empty 表示盘中空位置数量，apple 表示盘中苹果数量，orange 表示盘中橘子数量。

再定义

分别表示张老师和李老师是否轮到放水果。初始由张老师开始，因此 zhang 为 1，李老师先休息，因此 li 为 0。

由于任意时刻只有一位老师处于放水果阶段，教师之间不需要额外的互斥信号量；empty 能保证盘中水果总数不超过 30。

一种可行伪代码如下：

semaphore empty = 30;
semaphore apple = 0;
semaphore orange = 0;
semaphore zhang = 1;
semaphore li = 0;

process TeacherZhang() {
    while (true) {
        P(zhang);
        for (int k = 0; k < 10; k++) {
            P(empty);
            if (randomly_choose_apple())
                V(apple);
            else
                V(orange);
        }
        V(li);
    }
}

process TeacherLi() {
    while (true) {
        P(li);
        for (int k = 0; k < 10; k++) {
            P(empty);
            if (randomly_choose_apple())
                V(apple);
            else
                V(orange);
        }
        V(zhang);
    }
}

process Boy() {
    while (true) {
        P(apple);
        // take one apple and eat it
        V(empty);
    }
}

process Girl() {
    while (true) {
        P(orange);
        // take one orange and eat it
        V(empty);
    }
}

教师每放入一个水果都先申请一个空位置，然后根据随机选择的水果种类增加相应计数。每完成 10 次成功放置后才唤醒另一位老师。男孩只有在 apple 大于 0 时才能取苹果，女孩只有在 orange 大于 0 时才能取橘子；每取走一个水果就释放一个空位置。