操作系统调度与内存管理详解

table {
border-collapse: collapse;
width: 100%;
margin-bottom: 1rem;
}
th, td {
border: 1px solid #ddd;
padding: 8px;
text-align: left;
}
th {
background-color: #f2f2f2;
}
tr:nth-child(even) {
background-color: #f9f9f9;
}
pre {
background-color: #f8f8f8;
padding: 15px;
border-radius: 4px;
overflow-x: auto;
}

30、为什么调度器区分 I/O 密集型程序和 CPU 密集型程序很重要？

长期调度器需要选择 I/O 密集型和 CPU 密集型进程的良好组合。

如果所有进程都是 I/O 密集型，就绪队列几乎总是为空，短期调度器无事可做；

如果所有进程都是 CPU 密集型，I/O 等待队列几乎总是为空，设备将闲置，系统会失衡。

性能最佳的系统需要 CPU 密集型和 I/O 密集型进程的组合。

31、考虑用于预测下一次 CPU 突发长度的指数平均公式。设该公式中的参数为 α，初始预测值为 τ₀ 。为参数赋予以下值会对预测结果有什么影响？a. α = 0 且 τ₀ = 100 毫秒；b. α = 0.99 且 τ₀ = 10 毫秒

a. 当 α = 0 时，τₙ₊₁ = τₙ，意味着最近的历史信息对预测无影响，预测值始终保持初始值 100 毫秒，当前情况被认为是暂时的。

b. 当 α = 0.99 时，意味着仅最近的 CPU 突发长度对预测起主要作用，历史信息几乎被忽略，预测值会迅速趋近于最近的 CPU 突发长度，初始值 10 毫秒的影响会很快消失。

32、哪种算法能使所有进程的平均等待时间最短？

短作业优先（SJF）算法

通过对比发现：

先来先服务（FCFS）算法平均等待时间为

28毫秒

短作业优先（SJF）算法平均等待时间为

13毫秒

时间片轮转（RR）算法平均等待时间为

23毫秒

因此，

SJF算法平均等待时间最短

。

33、以下哪种调度算法可能导致饥饿现象？a. 先来先服务 b. 最短作业优先 c. 轮转调度 d. 优先级调度

b、d

34、考虑一个实现多级队列调度的系统。计算机用户可以采用什么策略来最大化分配给用户进程的 CPU 时间？

如果系统采用多级反馈队列调度，用户可尝试让进程的 CPU 突发时间保持在 8 毫秒或更短，这样进程能处于最高优先级队列，可以快速获得 CPU 并完成 CPU 突发。因为多级反馈队列调度中，CPU 突发时间短的进程会被分配到高优先级队列，优先得到执行。

35、解释先来先服务（FCFS）调度算法在偏向短进程方面的特点

先来先服务（FCFS）调度算法的特点

先来先服务（FCFS）调度算法对短进程

没有偏向性

。该算法按照进程到达的顺序依次分配CPU资源，因此在长进程先到达的情况下，后续到达的短进程必须等待长进程执行完毕后才能获得CPU。

存在的问题

短进程等待时间过长

：由于长进程占用CPU时间较长，短进程可能需要长时间等待，导致整体平均等待时间增加。

护航效应

：在动态环境下，短进程频繁等待长进程执行完毕，会形成“护航”现象，影响系统的响应速度。

降低CPU和设备利用率

：由于进程之间的等待时间增加，CPU和外部设备可能处于空闲状态，从而降低整体系统效率。

36、解释多级反馈队列调度算法对短进程的偏好程度

多级反馈队列调度算法

多级反馈队列调度算法高度偏好短进程。该算法会根据进程CPU突发的特性分离进程，具体规则如下：

若进程使用过多CPU时间，会被移至低优先级队列

，使I/O密集型和交互式进程留在高优先级队列。

优先级划分依据

CPU突发时间为8毫秒或更短的进程

：

被赋予最高优先级，这类进程能迅速获得CPU，完成CPU突发，然后进入下一个I/O突发。

需要超过8毫秒但少于24毫秒的进程

：

也能较快得到服务，不过优先级低于更短的进程。

长进程

：

会自动下沉到低优先级队列，按先来先服务顺序使用队列0和队列1剩余的CPU周期。

37、传统的UNIX调度器强制规定优先级数字和优先级之间呈反比关系：数字越高，优先级越低。调度器每秒使用以下函数重新计算进程优先级：优先级 = （近期CPU使用情况 / 2）+ 基数，其中基数为60，近期CPU使用情况指的是自上次重新计算优先级以来进程使用CPU的频率。假设进程P1的近期CPU使用情况为40，进程P2为18，进程P3为10。重新计算优先级时，这三个进程的新优先级分别是多少？根据这些信息，传统的UNIX调度器会提高还是降低CPU密集型进程的相对优先级？

进程P1的新优先级为(40 / 2) + 60 = 80；

进程P2的新优先级为(18 / 2) + 60 = 69；

进程P3的新优先级为(10 / 2) + 60 = 65。

CPU密集型进程使用CPU更频繁，近期CPU使用情况值更大，根据公式计算出的优先级数字更高，而数字越高优先级越低，所以传统的UNIX调度器会降低CPU密集型进程的相对优先级。

38、考虑一个逻辑地址空间，它有64个页面，每个页面有1024个字节，映射到一个有32个帧的物理内存中。a. 逻辑地址需要多少位？b. 物理地址需要多少位？

a. 逻辑地址中，页面数量为 $64 = 2^6$，页内偏移为 $1024 = 2^{10}$，所以逻辑地址位数为 $6 + 10 = 16$ 位。

b. 物理内存中，帧数量为 $32 = 2^5$，帧内偏移和页内偏移一样是 10 位，所以物理地址位数为 $5 + 10 = 15$ 位。

39、在IBM/370中，通过使用密钥来提供内存保护。密钥是一个4位的量。每个2K的内存块都有一个关联的密钥（存储密钥）。CPU也有一个关联的密钥（保护密钥）。只有当两个密钥相等或其中一个为零时，才允许进行存储操作。以下哪些内存管理方案可以与此硬件成功配合使用？a. 裸机 b. 单用户系统 c. 固定数量进程的多道程序设计 d. 可变数量进程的多道程序设计 e. 分页 f. 分段

b/c/d/e/f

40、解释内部碎片和外部碎片的区别。

内存碎片详解

外部碎片

外部碎片是指当有足够的总内存空间来满足请求，但可用空间不连续时出现的情况，存储被分割成大量小空洞。

产生原因：


如采用首次适应和最佳适应策略进行内存分配时，随着进程的加载和移除，空闲内存空间会被分割成小块，产生外部碎片。

内部碎片

内部碎片是指分配给进程的内存可能比请求的内存稍大，两者之间的差值就是内部碎片，即分区内部未使用的内存。

例如：


在多分区分配方案中，若一个空洞为18,464字节，下一个进程请求18,462字节，分配后剩下2字节的空洞，对该空洞的管理开销可能远大于空洞本身。

产生原因：


采用将物理内存分成固定大小的块并按块大小分配内存的方法会产生内部碎片。

41、假设页面大小为1KB，对于以下以十进制数表示的地址引用，其页号和偏移量分别是多少：a. 2375 b. 19366 c. 30000 d. 256 e. 16385

a. 页号：2，偏移量：327；

b. 页号：18，偏移量：902；

c. 页号：29，偏移量：320；

d. 页号：0，偏移量：256；

e. 页号：16，偏移量：1

42、考虑一个逻辑地址空间，有32页，每页1024个字，映射到16个帧的物理内存上。a. 逻辑地址需要多少位？b. 物理地址需要多少位？

a. 逻辑地址需要15位。因为有32页（2

⁵

= 32，页号需5位），每页1024字（2

¹⁰

= 1024，页内偏移需10位），共5 + 10 = 15位。

b. 物理地址需要14位。有16个帧（2

⁴

= 16，帧号需4位），每页1024字（页内偏移10位），共4 + 10 = 14位。

43、考虑一个具有32位逻辑地址和4KB页面大小的计算机系统。该系统支持高达512MB的物理内存。以下各项分别有多少个条目？a. 传统单级页表 b. 反向页表

a. 传统单级页表的条目数：

逻辑地址空间大小为 $2^{32}$ 字节，页面大小为 4KB（$2^{12}$ 字节），则页的数量为

232/212=220232/212=220

个，所以传统单级页表有 $2^{20}$ 个条目。

b. 反向页表的条目数：

物理内存大小为 512MB（$2^{29}$ 字节），页面大小为 4KB（$2^{12}$ 字节），则物理帧的数量为

229/212=217229/212=217

个，所以反向页表有 $2^{17}$ 个条目。

44、考虑一个页表存于内存中的分页系统。a. 如果一次内存访问需要200纳秒，那么一次分页内存访问需要多长时间？b. 如果我们添加了快表（TLBs），且所有页表引用中有75%能在快表中找到，那么有效内存访问时间是多少？（假设如果页表项在快表中，查找该页表项的时间为零。）

a. 由于分页系统访问内存需要先访问页表获取帧号，再访问目标内存，所以需要两次内存访问。一次内存访问需200纳秒，那么分页内存访问需要

2×200=4002×200=400 纳秒。

b. 75%的引用能在快表中找到，此时访问时间为200纳秒；25%的引用不在快表中，需要先访问页表再访问目标内存，即

2×200=4002×200=400 纳秒。

有效内存访问时间 =

0.75×200+0.25×400=150+100=2500.75×200+0.25×400=150+100=250 纳秒。

45、考虑以下段表：段号 基地址 长度 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96。以下逻辑地址对应的物理地址是什么？a. 0,430 b. 1,10 c. 2,500 d. 3,400 e. 4,112

a. 物理地址为 219 + 430 = 649；

b. 物理地址为 2300 + 10 = 2310；

c. 偏移量 500 超出段 2 的长度 100，产生陷阱；

d. 物理地址为 1327 + 400 = 1727；

e. 偏移量 112 超出段 4 的长度 96，产生陷阱。

46、对页表进行分页的目的是什么？

在支持大逻辑地址空间（如2³²到2⁶⁴）的现代计算机系统中，页表本身会变得过大。例如，在32位逻辑地址空间且页大小为4KB的系统中，页表可能包含多达100万个条目，每个进程仅页表就可能需要多达4MB的物理地址空间。对页表进行分页可以将页表划分为更小的部分，避免在主存中连续分配页表。

47、假设一个系统有一个32位的虚拟地址，页面大小为4KB。编写一个C程序，该程序通过命令行传递一个虚拟地址（十进制），并输出给定地址的页号和偏移量。例如，程序运行如下：./a.out 19986 程序将输出：The address 19986 contains: page number = 4 offset = 3602 编写此程序需要使用适当的数据类型来存储32位。建议使用无符号数据类型。

以下是实现该功能的C程序：

#include <stdio.h>
#include <stdlib.h>
#define PAGE_SIZE 4096

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <virtual_address>
", argv[0]);
        return 1;
    }
    unsigned int virtual_address = (unsigned int)strtoul(argv[1], NULL, 10);
    unsigned int page_number = virtual_address / PAGE_SIZE;
    unsigned int offset = virtual_address % PAGE_SIZE;
    printf("The address %u contains: page number = %u offset = %u
", virtual_address, page_number, offset);
    return 0;
}

该程序首先检查命令行参数的数量是否正确。然后，将输入的虚拟地址转换为无符号整数。接着，通过除法和取模运算计算页号和偏移量。最后，输出结果。

48、考虑一个支持5000个用户的系统。假设你希望其中4990个用户能够访问一个文件。a. 如何在UNIX系统中指定这种保护方案？b. 你能提出一种比UNIX系统提供的方案更有效的保护方案吗？

a. 在UNIX系统中，可以创建一个包含4990个可访问用户的组，将该文件的组设置为这个组，并赋予组相应的访问权限。同时可以设置文件的所有者和其他用户（不属于该组的用户）的权限。

b. 可以使用访问控制列表（ACL），直接将4990个用户添加到文件的访问控制列表中，明确指定他们的访问权限，相比UNIX的所有者 – 组 – 其他用户的方案，ACL可以进行更细粒度的访问控制。

49、考虑一个文件系统，其中一个文件可以在指向该文件的链接仍然存在的情况下被删除并回收其磁盘空间。如果在同一存储区域或使用相同的绝对路径名创建一个新文件，可能会出现什么问题？如何避免这些问题？

可能出现的问题：

若删除文件后在同一存储区域创建新文件，原有的悬空指针可能指向新文件的中间部分，导致数据访问错误

若使用相同绝对路径名创建新文件，原有的链接可能指向新文件，造成混淆

避免方法：

可以在删除文件时，搜索并删除所有相关链接，但这需要维护每个文件的关联链接列表，否则搜索成本高

也可以在尝试使用链接时，判断文件是否存在，若不存在则不解析链接名

还可以采用引用计数法，当引用计数为 0 时才删除文件，避免悬空指针问题

50、解释虚拟文件系统（VFS）层如何使操作系统轻松支持多种类型的文件系统。

VFS层的作用

VFS层通过以下两种方式使操作系统轻松支持多种类型的文件系统：

通过定义清晰的VFS接口

，将文件系统通用操作与其实现分离。同一机器上可并存多个VFS接口实现，从而允许透明访问本地挂载的不同类型文件系统。

提供一种在整个网络中唯一表示文件的机制

。

– VFS基于一种称为

vnode

的文件表示结构，其中包含网络范围内唯一文件的数字标识符。

– 内核为每个活动节点（文件或目录）维护一个

vnode

结构。

– VFS可区分本地文件和远程文件，本地文件还可根据其文件系统类型进一步区分。

– 它根据文件系统类型激活特定于文件系统的操作来处理本地请求，并为远程请求调用NFS协议过程。

51、使用文件分配表（FAT）将文件块链接在一起的链接分配变体有哪些优点？

该方法简单高效；

可像链表一样使用，目录项包含文件首块号，表项包含后续块号，直至文件末尾；

分配新块简单，只需找到首个值为0的表项，替换前一个文件结束值为新块地址，再将0替换为文件结束值；

能提高随机访问时间，磁盘头可通过读取FAT信息找到任意块的位置。

52、考虑一个将空闲空间保存在空闲空间列表中的系统。a. 假设指向空闲空间列表的指针丢失了，系统能否重建空闲空间列表？请解释你的答案。b. 考虑一个类似于UNIX使用的采用索引分配的文件系统。假设没有任何磁盘块当前被缓存，读取位于 /a/b/c 的小型本地文件的内容可能需要多少次磁盘I/O操作？c. 提出一种方案，以确保指针不会因内存故障而丢失。

a. 若采用位向量法实现空闲空间列表，系统可通过扫描整个磁盘，根据磁盘块是否被使用的状态重建位向量，进而重建空闲空间列表；若采用链表法，若没有额外备份，丢失指针后无法重建；若采用计数法或使用 B-树存储空闲空间信息，若有备份或可通过扫描磁盘重建相关信息，就能重建空闲空间列表。

b. 读取位于

/a/b/c

的小型本地文件，首先需读取根目录块，找到目录

a

的索引节点，读取该索引节点得到目录

a

的数据块，再从目录

a

的数据块中找到目录

b

的索引节点，读取该索引节点得到目录

b

的数据块，从目录

b

的数据块中找到目录

c

的索引节点，读取该索引节点得到文件的索引块，最后读取文件的数据块，总共可能需要 7 次磁盘 I/O 操作。

c. 可将指向空闲空间列表的指针定期备份到磁盘，或使用非易失性内存存储该指针，还可采用冗余存储，在多个位置保存指针副本。

53、包括RC 4000系统在内，定义了一个进程树，使得一个进程的所有后代只能由其祖先赋予资源（对象）和访问权限。因此，一个后代永远不能拥有其祖先所没有的能力。树的根是操作系统，它拥有做任何事情的能力。假设访问权限集由一个访问矩阵A表示。A(x,y)定义了进程x对对象y的访问权限。如果x是z的后代，对于任意对象y，A(x,y)和A(z,y)之间有什么关系？

由于后代进程

x

不能拥有其祖先进程

z

所没有的能力，所以对于任意对象

y

，

A(x,y)

所代表的访问权限是

A(z,y)

所代表的访问权限的子集，即

A(x,y) ⊆ A(z,y)

。

54、能力列表通常保存在用户的地址空间内。系统如何确保用户不能修改列表的内容？

系统通过以下两种方式确保用户不能修改能力列表内容：

设置不可访问的标签


为每个对象设置标签以区分其是能力列表还是可访问数据，且标签不能被应用程序直接访问。此限制可借助硬件或固件支持来实施。

地址空间划分


将程序关联的地址空间分为两部分：

– 一部分供程序访问，包含程序的常规数据和指令；

– 另一部分包含能力列表，只能由操作系统访问。

该方式可利用分段内存空间来支持。

55、访问控制矩阵可用于确定一个进程是否可以从域A切换到域B并享有域B的访问权限。这种方法是否等同于将域B的访问权限包含在域A的访问权限中？

否，进程从域A切换到域B需满足访问矩阵中`access(A, B)`包含`switch`权限，且切换后按域B对应行的访问权限访问对象，并非将域B权限包含在域A中。

56、考虑一个计算机系统，在该系统中，学生只能在晚上10点到早上6点玩电脑游戏，教职工只能在下午5点到早上8点玩电脑游戏，而计算机中心工作人员可以随时玩。请提出一个有效实施该政策的方案。

可通过以下方案实施此政策：

用户身份认证

：系统需对用户身份进行认证，区分学生、教职工和计算机中心工作人员。可使用用户名、密码、身份令牌等方式。

时间记录与检查

：系统维护当前时间，并在用户尝试启动游戏时检查其身份和当前时间是否符合相应的时间限制。

访问控制列表（ACL）

：为不同用户角色创建ACL，明确各角色可玩游戏的时间范围。系统在用户请求玩游戏时，依据ACL进行判断。

实时监控与拦截

：系统实时监控用户操作，若发现用户在不符合其身份时间限制时尝试玩游戏，拦截该操作并给出提示。

时间同步

：确保系统时间准确，可通过网络时间协议（NTP）与权威时间源同步。

日志记录

：记录用户尝试玩游戏的时间、身份及结果，便于后续审计和管理。

57、最小特权原则如何有助于创建保护系统？

最小特权原则规定程序、用户和系统仅被赋予执行任务所需的足够特权。操作系统遵循该原则实现其功能、程序、系统调用和数据结构，使组件故障或受损时造成的损害最小化。

它有助于创建保护系统，如提供细粒度访问控制的系统调用和服务，能在需要时启用特权，不需要时禁用；

创建所有特权功能访问的审计跟踪，便于追踪系统的保护和安全活动；

管理用户时为每个用户创建单独账户，仅赋予其所需特权；

计算机可被限制运行特定服务、在特定时间通过特定服务访问特定远程主机，通常通过启用或禁用服务以及使用访问控制列表来实现，从而帮助营造更安全的计算环境。

58、实施最小特权原则的系统为何仍会出现导致安全违规的保护失败情况？

以Windows和Solaris系统对比为例，实施最小特权原则的系统仍可能出现保护失败导致安全违规的情况。

像Windows相比Solaris有更多代码行和服务，需要保护的内容更多；

Windows的保护方案可能不完整，或保护了操作系统错误的方面，使其他区域易受攻击。

59、可以通过采用更好的编程方法或使用特殊硬件支持来避免缓冲区溢出攻击。请讨论这些解决方案。

更安全的编程与硬件支持以防止缓冲区溢出

更好的编程方法

在编程时，程序员应进行

边界检查

，避免因疏忽未对输入字段进行边界检查而导致的

缓冲区溢出问题

。例如，在处理输入数据时，应确保输入数据的长度不超过程序预期的缓冲区大小。

特殊硬件支持

部分 CPU 具备

禁止在内存栈区执行代码

的功能：

Sun 的 SPARC 芯片

：最新版本具备此类设置，

Solaris

最新版本也启用了该功能。

AMD 和 Intel x86 芯片

：最新版本包含

NX 特性

（No-eXecute），通过在 CPU 页表中使用新位标记相关页面为不可执行，防止指令从该页面读取和执行。

随着该特性的普及，

缓冲区溢出攻击将大幅减少

。

60、在用户提供的密码中使用“盐值”（salt）的目的是什么？“盐值”应该存储在哪里，以及如何使用？

使用“盐值”的目的是确保即使两个明文密码相同，加密后也会得到不同的密文。“盐值”存储在密码文件中，当用户输入密码时，该密码会与存储在密码文件中的“盐值”重新组合，然后通过相同的单向转换函数进行处理，若结果与密码文件中的内容匹配，则密码被接受。

61、所有密码列表都保存在操作系统中。因此，如果用户设法读取此列表，密码保护就失效了。请提出一种避免此问题的方案。（提示：使用不同的内部和外部表示形式。）

可以采用加密的方式，将用户输入的密码通过加密算法转换为内部存储的编码形式。例如，使用像 UNIX 系统那样的加密方法，对密码进行加密存储。

在存储密码时，使用加密函数 $ f(x) $ 对密码进行处理，即使存储的编码后的密码被看到，也无法解码得到原始密码。

同时，还可以在加密算法中加入“盐”（随机数），确保相同的明文密码加密后得到不同的密文。这样，即使有人获取了存储密码的文件，也难以破解出真实密码。

62、支持或反对针对小罗伯特·莫里斯创建和传播互联网蠕虫所做出的司法判决。

支持判决的理由：

莫里斯释放的蠕虫造成了巨大损失。

虽程序无破坏代码，但释放和传播范围不太可能是无意的。

且采取措施掩盖踪迹和抵抗阻止传播的努力。

他的行为扰乱了网络秩序，耗费大量系统和系统管理员时间，造成数百万美元损失。

司法判决起到了威慑作用，维护了网络安全的法律秩序。

反对判决的理由：

蠕虫程序未包含破坏或摧毁系统的代码，其行为可能只是一个失控的恶作剧。

莫里斯可能没有预料到会造成如此大的影响。

且他的行为或许是出于对网络安全的研究或测试目的，而非恶意破坏。

因此，三年缓刑、400小时社区服务和10000美元罚款的判决可能过重。

63、比较对称加密和非对称加密方案，并讨论分布式系统在什么情况下会使用其中一种。

加密算法概述

对称加密

对称加密使用相同的密钥进行加密和解密，即 $ E(k) $ 可从 $ D(k) $ 推导得出，反之亦然，因此必须同等程度地保护 $ E(k) $ 和 $ D(k) $ 的保密性。

历史与应用

：

过去几十年，美国民用领域最常用的对称加密算法是

数据加密标准（DES）

，它对 64 位值使用 56 位密钥进行一系列基于替换和置换操作的变换。

DES 如今对许多应用而言已不安全，NIST 因此推出了

三重 DES

。

2001 年，NIST 采用

高级加密标准（AES）

取代 DES。

其他常见算法

：

Twofish

RC5

RC4

非对称加密

非对称加密基于两个密钥：

公钥

（公开）和

私钥

（严格保密）。

加密算法

：

$ E(ke, N)(m) = m^{ke} mod N $

解密算法

：

$ D(kd, N)(c) = c^{kd} mod N $

特点

：

非对称加密基于数学函数而非变换，计算成本更高。

计算机使用通常的对称算法对密文进行编码和解码比使用非对称算法更快。

分布式系统中的应用

对称加密

：

适用于大量数据的通用加密。

原因：计算速度快，效率高。

非对称加密

：

不用于大量数据的通用加密。

用于：

少量数据的加密

身份验证

保证机密性

密钥分发

64、讨论与静态链接相比，库的动态（共享）链接的三个优点。描述静态链接更可取的两种情况。

动态链接的优点

更高效利用物理内存，系统库只需加载到内存一次；

节省磁盘空间，避免每个程序都包含相同系统库函数的副本；

便于库的更新，只需更新共享库，无需重新编译所有程序。

静态链接更可取的情况

当运行环境不稳定，动态库可能缺失或版本不兼容时；

对程序运行速度要求极高，避免动态链接的额外开销时。

65、比较在单台计算机上使用网络套接字和共享内存作为进程间数据通信机制的情况。每种方法的优点是什么？何时更适合使用每种方法？

网络套接字

优点

：

支持标准互联网协议及多种非 UNIX 操作系统原生协议。

适合不同系统间通信，在网络通信中应用广泛。

适用场景

：

当需要与远程进程通信时。

或在不同系统、不同进程间进行数据传输时更适合使用。

共享内存

优点

：

能实现最大速度和便利的通信。

在计算机内进行数据通信时可达到内存传输速度。

适合交换大量或少量数据。

适用场景

：

当进程间需要快速交换数据时。

且能自行处理同步和保护问题时更适合使用。