操作系统os-chapter7-13

第七章：死锁

死锁模型

死锁的概念还是经常考的

• 多道程序环境下，多个进程竞争有限资源。如果某个进程需求的资源被其他进程占用，则该进程可能被永久阻塞，这种情况称为 死锁（deadlock） 。
• 进程按照如下顺序使用资源：
  • 申请（Request） ：如果申请不能被允许（如资源正在被其他进程占用），则申请进程必须等待直到获得资源
  • 使用（Use）
  • 释放（Release）
• 资源的申请和释放都是系统调用，如设备的 request()/release()，文件的 open()/close()，内存的 allocate()/free() 等。对于进程或线程的每次执行，操作系统会检查并确保它们以获得所需资源。系统维护一张记录表，说明某个资源是否空闲，被分配给哪个进程。
• 永久性资源可分为：
  • 可剥夺资源（可重用资源）：当进程所占有的并使用的资源被剥夺时，对进程不产生破坏性影响（如内存、CPU）
  • 不可剥夺资源：如打印机等，一旦剥夺则任务执行失败

死锁与饥饿/饿死的区别

也考过

• Deadlock: A process waits for a resource that is currently assigned to another process, which is in turn waiting for another resource （资源直接不可用，进程永远得不到）

• Starvation: A process waits for a resource that continually becomes available but is never assigned to the waiting process（资源是可用的，但进程获取不到，未来可能获取到）

• Two major differences between deadlock and starvation

  • 从进程角度讲，in starvation, it is not certain that a process will never get the requested resource (i.e., there is a chance it might), while a deadlocked process is permanently blocked
  • 从资源角度讲，in starvation, the resource under contention is continuously available, whereas this is not true in a deadlock

Starvation is typically easier to fix than deadlock（饥饿可用用老化（aging）解决）

死锁特征

考过

• 以下四个条件（四个条件并不完全独立）同时成立时，死锁产生：
  • 互斥（mutual exclusion） ：至少有一个资源处于互斥模式，即该资源同时只能由一个进程使用。
  • 占有并等待（hold and wait） ：进程必须占有至少一个资源，并且等待另一资源，且等待的资源已被其他进程占有。
  • 非抢占（no preemptive） ：资源不能被抢占。
  • 循环等待（circular wait） ：一组等待进程 {P0, p1, ..., pn}，其中Pi等待的资源被 Pi+1 占有，Pn 等待的资源被 P0 占有。
• 死锁问题可用系统资源分配图（system resource-allocation graph）描述：
  • 该图的节点集合 V 分为系统活动进程集合 P = {P1, P2, ..., Pn} 和系统资源类型集合 R = {R1, R2, ..., Rm}。
  • 从进程 Pi 到资源类型 Rj 的有向边记为 Pi → Rj，称为 申请边（request edge） ，表示进程 Pi 已经申请并正在等待资源类型 Rj 的一个实例。
  • 从资源类型 Rj 到进程 Pi 的有向边记为 Rj → Pi，称为 分配边（assignment edge） ，表示资源类型 Rj 的一个实例已经分配给进程 Pi。
  • 在图上用圆形表示进程 Pi，用矩形表示资源类型 Rj，资源类型的多个实例在矩形中用圆点表示。
  • 申请边只需指向矩形 Rj，分配边的源点需要指定矩形内部的某个圆点。
  • 当进程 Pi 申请资源类型 Rj 的一个实例时，在资源分配图中加入一条申请边，当该申请可以满足时将该申请边 立即 转换为分配边。当进程释放资源时，该分配边从图中删除。
• 可证明：
  • 如果分配图中不存在环，则系统未发生进程死锁
  • 如果分配图中存在环且每个资源类型仅有一个实例，则系统已处于进程死锁
  • 如果分配图中存在环，且存在某个资源类型有多个实例，则系统可能处于进程死锁

一个带有死锁的资源分配图如下图所示：

在系统中有两个最小环：

$P_1\rightarrow R_1\rightarrow P_2 \rightarrow R_3 \rightarrow P_3\rightarrow R_2\rightarrow P_1$

$P_2\rightarrow R_3\rightarrow P_3\rightarrow R_2\rightarrow P_2$
进程P1、P2和 P3 是死锁。 进程 P2等待资源类型 R3 ，而它又被进程P3占有。 另一方面，进程P3等待进程P1或进程P2 以释放资源类型 R2。另外，进程P1等待进程P2释放资源 R1。

现在考虑图 7.4 所示的资源分配图。 在这个例子中， 也有个环
$P_1\rightarrow R_1\rightarrow P_3\rightarrow R_2\rightarrow P_1$
然而， 却没有死锁。注意进程P3可能释放资源类型R3的实例。这个资源可分配给进程P3, 以打破环。

死锁处理

• 三种方法可以处理死锁：
  • 使用某种协议预防或避免死锁，确保系统不进入死锁状态
  • 允许系统进入死锁状态，且系统可以检测到死锁并恢复
  • 忽视死锁问题，认为系统中不可能发生死锁
• 多数操作系统采用第三种（包括 UNIX 和 Windows），因此死锁由应用程序员处理。

死锁预防

软院不怎么考，考研会有

根据死锁特征，只要破坏四个条件中的一个使之不同时成立即可实现 死锁预防（prevention） 。

• 破坏互斥：非共享资源必须满足互斥条件，因此此条件无法破坏
• 破坏占有并等待：必须保证一个进程不能在已经占有其他资源的情况下再申请一个资源，两种方法可选（两种方法资源利用率均较低，且可能导致饥饿，需要多个常用资源的进程可能会永久等待）：
  • 每个进程在执行前申请并获得执行期间所需的全部资源；
  • 仅允许进程在没有资源时才可申请资源，在它申请更多资源前必须释放全部已持有资源。
• 破坏非抢占：剥夺资源策略。如果一个进程在占有一些资源的同时申请了另一个不能立刻被分配的资源（等待列表中的其他进程也没有持有该资源），则该进程目前已获得的所有资源都可被其它正在等待的进程抢占。也就是说，该进程持有的资源被隐式释放了。该进程要想重新执行，必须分配到要申请的资源，同时还要恢复自己在等待时被抢占的资源。此协议通常用于状态可以保存和恢复的资源，如 CPU 寄存器和内存，对于不可剥夺资源无效。
• 破坏循环等待：资源有序分配策略。系统定义一个函数F: R → N为资源类型集合编号，不同资源类型的编号不同。每个进程只能按照递增顺序申请资源，进程开始执行时可以申请任意数量的资源类型 Ri 的实例，之后若想申请资源类型 Rj 的实例，则必须满足F(Rj) > F(Ri)才可申请，否则它必须释放所有编号大于F(Rj)的资源后才能再申请。
  • 证明：若存在循环等待，设循环等待的进程集合为 {P0, P1, ..., Pn} ，其中 Pi 等待资源 Ri，且 Ri 被进程 Pi+1 占有，因为 Pi+1 占有资源 Ri 且申请资源 Ri+1，所以对所有 i 有 F(Ri) < F(Ri+1)，即 F(R0) < F(R1) < ... < F(Rn) < F(R0)，假设不成立。
  • 按照此协议，程序员必须按系统为资源定义的顺序来编写程序才可防止死锁。有些软件（如 Witness）可以验证资源锁是否按顺序获取，并对不按顺序获取的代码做出警告。

以上通过限制资源申请来预防死锁的方法可行，但会降低设备使用率和系统吞吐率。

死锁避免

• 死锁避免（deadlock-avoidance） 算法动态监测资源分配状态以保证循环等待条件无法成立，同时它要求进程提供一定的 先验信息 ，例如进程执行期间可能需要使用的每种资源类型实例的最大数量。
• 若系统中的进程按照某个特定顺序执行不会产生死锁，则称此时系统处于安全状态，这个进程执行的顺序称为 安全序列（safe sequence） 。

A sequence $<P_1, P_2, …, P_n>$ is a safe sequence for the current allocation if, for each $P_i$, the resources that $P_i$ can still request can be satisfied by the currently available resources plus resources held by all the $P_j$, for $j<i$

• 安全状态必然不会导致死锁，不安全状态可能会导致死锁状态，死锁状态必然是不安全状态。
• 安全序列可能并不唯一。

Example: A system with 12 units of a resource

Three processes:

​ 最大需求资源 已经分配的资源数

• P1: max need = 10, allocated= 5

• P2: max need = 4, allocated = 2

• P3: max need = 9, allocated = 2

This is a safe state, since a safe sequence <P2, P1, P3> exists

因为我们现在有12-5-2-2=3个空闲资源，可以满足P2，完成P2后空闲资源会变成5（P2释放了占用的两个空闲资源）完成P1，最后完成P3

资源分配图算法

• 适用于每个资源只有一个实例的系统（局限性）；
• 向系统资源分配图中加入一种新类型的边，称为 需求边（claim edge） 。需求边 Pi->Rj 表示进程 Pi 可能在将来某时刻申请资源 Rj，需求边用虚线表示。当 Pi 申请资源 Rj 时，需求边 Pi->Rj变为申请边，当进程 Pi 释放资源 Rj 时，分配边 Rj->Pi 变成需求边；
• 若进程 Pi 试图申请资源 Rj，则系统需要检查：如果需求边 Pi->Rj 变成分配边 Rj->Pi 后，资源分配图中不存在环（虚实线无所谓），则允许申请，否则进程 Pi 必须等待。
• 系统检查是否存在环可使用 Tarjan 等求联通子图的 n² 级算法。

当然，应该注意这是有向图。

银行家（Banker’s）算法

• 适用于每种资源类型有多个实例的情形，效率低于资源分配图

• 银行家算法需要在进程请求资源时检查分配后的状态是否保持安全。使用下面的安全性算法可确定系统是否处于安全状态，算法的时间复杂度为 $mn²$。

• 银行家算法使用的数据结构：

  • Available：长度为 m 的数组，表示每种资源当前可用的（未被分配给进程的）实例数量
  • Max：n × m 的矩阵，Max[i][j] 表示进程 Pi 在整个生命周期中需要申请资源类型 Rj 实例的最大数量
  • Allocation：n × m 矩阵，Allocation[i][j] 表示进程 Pi 当前已经持有（已被分配）的资源类型 Rj 的实例数量；Allocation 的第 i 行记作 Allocation[i,]，表示进程 Pi 当前持有的不同资源类型的数量。
  • Need：n × m 矩阵，Need[i][j] = Max[i][j] - Allocation[i][j]，表示进程 Pi 还可能申请多少个 Rj 类型的资源实例；Need 的第 i 行记作 Need[i,]，表示进程 Pi 结束前可能仍要申请的不同资源数量

算法逻辑

资源分配算法与安全性算法：

安全性算法

1. 令 Work = Available 为长度为 m 的行向量，表示每种资源当前剩余可用的实例数量；令 Finish=[False for i = 0 to n-1] 为长度为 n 的行向量，初始化全部为 False，表示进程当前是否已结束执行。
2. 寻找一个正在执行的进程 Pi，并且 Need[i,] ≤ Work，即：Finish[i] == False && Need[i,] ≤ Work，这意味着当前系统剩余资源能够满足 Pi 的全部需求。若不存在这样的进程，则调到第 4 步。
3. 更新 Work = Work + Allocation[i,] ，令 Finish[i] = True 并跳回第 2 步。这意味着进程 Pi 已经执行结束，并且它所持有的资源全部释放，因此系统可用资源数量 Work 增加。注意这一步实际 等价于对资源分配图的化简 ，它将一个可消去的进程（即该进程可以得到资源并执行完）和所有该进程与相关资源连接的边从资源分配图中删去。
4. 检查所有的 i，是否都有 Finish[i] == True，若是则系统处于安全状态，否则系统处于不安全状态。

#include <memory.h>
#include <stdlib.h>
#define NUM_PROCESS 20
#define NUM_RESOURCE 10
#define TRUE 1
#define FALSE 0
typedef Boolean unsigned int;
unsigned int Available[NUM_PROCESS];
unsigned int Max[NUM_PROCESS][NUM_RESOURCE];
unsigned int Allocation[NUM_PROCESS][NUM_RESOURCE];
unsigned int Need[NUM_PROCESS][NUM_RESOURCE];
Boolean safe(){
    Boolean Finish[NUM_PROCESS];
    unsigned int Work[NUM_PROCESS];
    unsigned int i, j, k;
    memset(Finish, FALSE, sizeof(Boolean) * NUM_PROCESS);
    memcpy(Work, Available, sizeof(unsigned int) * NUM_PROCESS);
    for (k = 0; k < NUM_PROCESS; k++){
        for (i = 0; i < NUM_PROCESS; i++){
            // 寻找满足条件的 Pi
            if (Finish[i])
                continue;
            Boolean flag = TRUE;
            for (j = 0; j < NUM_RESOURCE; j++)
                if (Need[i][j] > Work[j]){
                    flag = FALSE;
                    break;
                }
            if (flag){    // 寻找到进程 Pi 满足条件
                for (j = 0; j < NUM_RESOURCE; j++)
                    Work[j] += Allocation[i][j];
                Finish[i] = TRUE;
                break;
                // 进程 Pi 结束执行
            }
        }
    }
    for (k = 0; k < NUM_PROCESS; k++)
        if (!Finish[k])
            return FALSE;
    return TRUE;
}

资源请求算法

判断进程对资源的申请是否可以维持安全性。设申请资源的进程为Pi，Request[i,]为一个长度为 m 的行向量，表示进程 Pi 要申请的不同资源实例数量。

1. 若 Request[i,] ≤ Need[i,] 则转到第 2 步，否则产生出错条件（进程 Pi 要申请的资源数量超过了它此前声明的可能使用的最大资源数量）
2. 若 Request[i,] ≤ Available 则转第 3 步，否则 Pi 等待（剩余资源不满足 Pi 的请求）
3. 假设系统剩余资源足够 Pi 使用，则系统计算修改后的状态是否安全，若安全则允许修改，不安全则 Pi 必须等待。

Boolean allocate(unsigned int i, unsigned int *Request){
    unsigned int j;
    for (j = 0; j < NUM_RESOURCE; j++)
        if (Request[j] > Need[i][j])
            return False;
    for (j = 0; j < NUM_RESOURCE; j++)
        if (Request[j] > Allocation[i][j])
            wait();    // 进程 Pi 必须等待资源
    for (j = 0; j < NUM_RESOURCE; j++){
        Available[j] -= Request[j];
        Allocation[i][j] += Request[j];
        Need[i][j] -= Request[j];
    }
    // 假设可以分配
    if (!safe()){    // 分配后不安全，恢复状态
        for (j = 0; j < NUM_RESOURCE; j++){
            Available[j] += Request[j];
            Allocation[i][j] -= Request[j];
            Need[i][j] += Request[j];
        }
        wait();
    } else
        return TRUE;
}

案例

存在的问题：未来所需要的资源量通常不确定。所以更一般地使用死锁检测与恢复进行解决。

死锁检测

• 如果一个系统既不采用死锁预防算法，也不采用死锁避免算法，则该系统可能出现死锁。此时，系统应当提供：

  • 检查系统是否出现死锁的算法
  • 从死锁状态中恢复的算法

基于资源分配图的检测

单资源实例检测

每个资源类型仅存在一个实例：可以使用资源分配图的变种 等待（wait-for）图 ，该图删去了资源分配图中的资源节点，而将原图中所有 Pi->Rj->Pk　的边转化为 Pi->Pk，即进程 Pi 正在等待进程 Pk 掌握的资源。如果等待图中有环存在，则系统存在死锁。为了检测死锁，系统要维护这个等待图，并且周期性的在图中调用检测算法，该算法时间复杂度为 $n²$，$n$ 为系统中进程数。

例如：下图存在死锁

多资源实例检测

多资源实例中，有环不一定死锁。如：

我们基于银行家算法进行改进：

1. 令 Work = Available 为长度为 m 的行向量，表示每种资源当前剩余可用的实例数量；令 Finish 为长度为 n 的行向量，若进程 Pi 当前未持有任何资源（Allocation[i,] == 0）则 Finish[i] = True，否则 Finish[i] = False。这里将不持有资源的进程设置 Finish 为 True 是因为，不持有资源的进程不会对死锁产生影响，不会有其它进程在等待该进程，这实际 等价于等待图中的孤立点 。
2. 寻找一个正在执行的进程 Pi，并且 Request[i,] ≤ Work，即：Finish[i] == False && Request[i,] ≤ Work，这意味着当前系统剩余资源能够满足 Pi 此刻的需求。若不存在这样的进程，则跳到第 4 步。
3. 认为进程可以运行完成，更新 Work = Work + Allocation[i,] 且令 Finish[i] = True；跳回第 2 步。
4. 检查是否存在某个 i 有 Finish[i] == False，若存在则系统处于死锁状态，且进程 Pi 死锁。

PS.

注意上面的死锁检测算法的第 2 步：如果 Request[i,] ≤ Work 就给进程 Pi 分配资源。这是基于如下假定，如果 Pi 不会参与到死锁中（因为 Request[i,] ≤ Work，Pi 的需求可以被满足所以此时一定不会被死锁），则 乐观地认为 Pi 直到执行结束都不会再申请更多的资源 。这里的假定可能不正确，如果假定不正确，Pi 在之后又申请了更多的资源，则在系统下次运行死锁检测算法时仍然会发现，所以这里的假定不影响算法正确性。

案例

死锁算法的一些问题

• 调用检测算法的频率受如下两个因素影响：
  • 死锁可能发生的概率多少：如果经常发生死锁则应该经常调用检测算法
  • 死锁发生时有多少进程会受影响
• 考虑极端情况：每当出现进程请求资源不能被立刻允许的情况时就调用死锁检测算法，则系统不仅能确定哪些进程处于死锁，还能确定导致死锁的特定进程（实际上是死锁环上的每个节点共同导致了死锁）。此种方式会导致巨大的计算开销。但如果使用较低的频率调用检测算法，或当 CPU 使用率低于某个阈值时，则调用检测算法无法确定涉及死锁的进程中是哪些导致了死锁。

死锁恢复

进程终止

• 两种方法通过终止进程来取消死锁，被终止的进程所持有的所有资源都会被系统回收：
  • 终止所有死锁进程 ：代价较大，有些进程可能已经运行很长时间而不得不放弃
  • 每次终止一个进程，直到死锁状态取消 ：开销较大，每终止一个进程都需要重新调用死锁检测算法
• 当采用部分终止时，确定终止哪个进程/哪个进程可以打破死锁的因素涉及：
  • 进程优先级
  • 进程已运行的时间和完成任务所需要的剩余时间
  • 进程使用了哪些、多少资源，以及资源是否可抢占
  • 进程仍需多少资源
  • 有多少进程需要被终止
  • 交互进程还是批处理进程

资源抢占

• 死锁的恢复也可以通过抢占资源来逐步取消死锁状态，需要处理三个问题：
  • 选择被抢占对象（victim） ：抢占哪些进程和资源，这和死锁恢复中部分终止要考虑的因素类似。
  • 回滚（rollback） ：如果从某个进程抢占资源，则被抢占的进程需要回滚到某个安全状态以便之后重新执行。完全回滚（终止被抢占的进程并重启该进程）比较容易，更有效的方式是将进程回滚到足够打破死锁的状态，但这需要系统维护更多关于进程状态的信息，而且可能产生饥饿。
  • 饥饿 ：如何确保不会总从同一个进程抢占资源。通常会考虑回滚次数，确保一个进程只能被抢占有限次。

第七章习题拾遗

假设每个进程都获得了两台机器，那么只要保证至少有一台机器处于空闲状态就可以保证不会死锁。

也就是说$2x+1\leq 11$，$x\leq 5$。

第八章：内存

背景

基本硬件

程序（代码）必须从硬盘调入主存并产生进程后才能运行。

内存与寄存器值CPU能直接访问的存储器件。

CPU 通常在一个 CPU 时钟周期内完成对内置寄存器的访问，对内存的访问需多个 CPU 时钟周期，在缺少数据来完成正在执行的指令时，CPU 需要 暂停（stall） ，通常在 CPU 和内存之间添加高速缓存（cache）以协调速度差异。

Register access in one CPU clock (or less)

Main memory can take many cycles

Cache sits between main memory and CPU registers

地址绑定

程序执行前需将所需部分二进制数据调入内存并置于进程空间内，执行过程中根据操作系统采用的内存管理方案可能还会有内存/硬盘之间的换入换出移动。在磁盘上等待调入内存的进程构成了 输入队列（input queue） 。

多数系统允许用户进程存放在物理内存任意位置，原程序中的地址通常用符号来表示，编译器会将这些符号地址绑定（bind）到可重定位的地址，链接程序或加载程序，再将这些可重定位的地址绑定成绝对地址。绑定是从一个地址空间到另一个地址空间的映射。将指令和数据绑定到内存地址可能有如下几种情况：

• 编译时（compile time）：在编译时已经知道进程将在物理内存中的驻留地址，则可生成 绝对代码（absolute code） 。
• 装载时（load time）：（将代码调入内存的过程即为装载）若编译时尚不了解进程将位于物理内存中具体哪个位置，则编译器需生成 可重定位代码（relocatable code） ，如 “从这个模块开始的第 14 个字节”。此时，最后绑定延迟到加载时进行。这其实产生的是一个相对的位置。
  • 地址变换通常在装入时一次完成，之后不再改变
• 执行时（execution）：若进程在执行时可在内存段间移动，则绑定需要在执行时进行，此种方案需要特定硬件（MMU），绝大多数通用操作系统采用这种方式。
  • 模块装入内存后所有地址都是相对地址，程序执行过程中访问到相应指令或数据时才进行地址变换
• 装载时与执行时对应不同的重定位策略，可以在下面习题拾遗中找到

逻辑地址和物理地址

• CPU 生成的地址为 逻辑地址（logical address），加载到 内存地址寄存器（memory-address register） 中的地址为 物理地址（physical address）。

• 编译时和装载时的地址绑定方法生成的逻辑地址和物理地址相同，执行时的地址绑定方案生成的逻辑地址和物理地址不同。

• 通常称逻辑地址为虚拟地址（virtual address）。

• 逻辑地址空间（logical address space） 为由程序所生成的所有逻辑地址的集合， 物理地址空间（physical address space） 为与这些逻辑地址对应的物理地址集合。

逻辑地址（Logical Address） ：是指由程序产生的与段相关的偏移地址部分。例如，你在进行C语言指针编程中，可以读取指针变量本身值(&操作)，实际上这个值就是逻辑地址，它是相对于你当前进程数据段的地址，不和绝对物理地址相干。程序员仅需与逻辑地址打交道，而分段和分页机制对我们来说是完全透明的，仅由系统编程人员涉及。应用程序员虽然自己可以直接操作内存，那也只能在操作系统给你分配的内存段操作。

对于程序员，逻辑地址是轻而易举就可以理解的。我们在写C代码的时候经常说我们定义的结构体首地址的偏移量，函数的入口偏移量，数组首地址等等。当我们在考究这些概念的时候，其实是相对于你这个程序而言的。并不是对于整个操作系统而言的。也就是说，逻辑地址是相对于你所编译运行的具体的程序（或者叫进程吧，事实上在运行时就是当作一个进程来执行的）而言。你的编译好的程序的入口地址可以看作是首地址，而逻辑地址我们通常可以认为是在这个程序中，编译器为我们分配好的相对于这个首地址的偏移，或者说以这个首地址为起点的一个相对的地址值。

当我们双击一个可执行程序时，就是给操作系统提供了这个程序运行的入口地址。之后shell把可执行文件的地址传入内核。进入内核后，会fork一个新的进程出来，新的进程首先分配相应的内存区域。这里会碰到一个著名的概念叫做Copy On Write，即写时复制技术。新的进程在fork出来之后，新的进程也就获得了整个的PCB结构，继而会调用exec函数转而去将磁盘中的代码加载到内存区域中。这时候，进程的PCB就被加入到可执行进程的队列中，当CPU调度到这个进程的时候就真正的执行了。(这部分在课堂笔记中有更详细记录)

我们可以把程序运行的入口地址理解为逻辑地址的起始地址，也就是说，一个程序的开始的地址。以及以后用到的程序的相关数据或者代码相对于这个起始地址的位置（这是由编译器事先安排好的），就构成了我们所说的逻辑地址。逻辑地址就是相对于一个具体的程序（事实上是一个进程，即程序真正被运行时的相对地址）而言的。

运行时从虚拟地址到物理地址的映射由硬件设备 内存管理单元（memory-management unit，MMU） 完成。一个最简单的 MMU 方案是将用户进程产生的地址加上 重定位寄存器（relocation register） 的值作为最终的物理内存地址，更复杂地，会检查是否越界。

用户进程绝不会看到真正的物理地址，一个地址在内存中比较、使用均基于虚拟地址，只有该地址作为内存地址，如执行加载/存储时才需要做到物理空间的地址映射。总而言之，用户进程只产生逻辑地址，且认为地址空间从 0 开始，而使用对应内存地址前必须由 MMU 做物理地址映射。

动态加载、链接与共享库

动态加载（dynamic loading）：所有子程序均以可重定位的方式保存在磁盘上，仅主程序装入内存并执行，当且仅当某个子程序被需要时才会装载进内存。此种方法设计程序主要是用户程序开发者的责任。其优势在于不被使用的子程序绝不会加载，若程序中有较多代码用于处理异常，动态加载会特别有效。

动态链接库（dynamically linked library）：部分操作系统只支持 静态链接（static linking） ，即加载程序将操作系统提供的语言库与其他目标模块一起合并到最终的二进制程序镜像中，所有程序均有一份所需系统库的副本；而动态链接将系统库的加载延迟到运行时，用户程序对系统库的引用留有 存根（stub） ，存根指用于定位内存驻留库程序的一小段代码。当执行存根时，若所需的系统库已经驻留在内存中，则存根使用已有的系统库，否则将系统库装入内存。最终存根均会将系统库地址替换自身并执行系统库，此时所有使用某个库的进程只需要一个库代码副本。

动态链接库由操作系统提供支持。动态链接为库更新带来方便，库版本更新后，引用该库的程序会自动使用新版本而无需重新链接。多个版本的库也可以同时装入内存，程序根据自己所需的版本信息确定使用哪个副本。此类系统也称为 共享库（shared libraried） 。

覆盖（补充）

• 多道程序设计环境下可通过 覆盖（Overlays） 技术扩充内存。由程序员实现，不需要操作系统的特殊支持。其思想为：将程序划分为若干个功能上相对独立的程序段，按程序逻辑结构让不会同时执行的程序段共享所有程序段均会使用到的内存。
• 覆盖方式的内存管理仅始终保留一个程序在任何时候都需要的数据。
• 与交换的区别：
  • 覆盖对程序员要求较高，程序员必须十分清楚程序的逻辑结构，明确规定各程序段的执行和覆盖顺序以及设计实现覆盖驱动模块，而交换技术对用户透明
  • 覆盖在同一进程/作业内进行，而交换在进程与进程之间进行。

交换

内存中的进程可暂时从内存中 交换（swap） 到 备份存储（backing store） 上，等到再次需要执行时调回。有时称为 滚出（roll out） 和 滚入（roll in） 。

备份存储通常为足够大的快速磁盘，以容纳所有用户程序的内存镜像副本、并提供对内存镜像的直接访问。交换系统上下文切换时间较长，为有效使用 CPU，通常使每个进程每次执行获取的时间片比交换时间长（而且还存在磁头定位时间）。但无论如何，时间代价较大。为了 只交换用户进程真正使用的内存空间 （如一个用户进程当前可能只使用了 10MB，但其最多可能使用 200 MB），用户进程需要告诉系统其内存需求情况以减少交换时间。

另一个问题：换出进程时，进程必须完全处于空闲状态。考虑如下场景：一个正在等待 I/O 操作的进程 P 即将被换出，若 I/O 操作异步访问 P 进程内存中的缓冲区，或是 I/O 设备正忙，I/O 操作在排队等待，此时换出进程 P，换入进程 P’ 会导致 I/O 操作已经属于 P’ 的内存。解决方案：

• 不能换出有待处理 I/O 的进程
• I/O 操作只能使用操作系统缓冲区，仅当进程在内存中执行时才发生操作系统缓冲和进程内存缓冲之间的数据转移

上述标准交换在目前的操作系统中使用不广泛，交换需要很长时间并且只能提供很少的执行时间。对上述交换方式的一种修正在很多 UNIX 系统中得到使用：当且仅当系统负荷过高，内存吃紧时进行交换。早期缺乏高级硬件的个人计算机通过此种交换可同时运行多个进程，如 MS Windows 3.1，该系统内存不足时将老进程交换到磁盘上，当且仅当用户再次选择执行该进程时才再次换入。

连续内存分配

内存分为操作系统驻留区域和用户进程驻留区域，操作系统通常位于低内存（因为中断向量通常位于低内存）。 连续内存分配（contiguous memory allocation） 可使内存中每个进程占有连续的内存区域。

内存保护

要确保操作系统不被用户进程访问、用户进程不被其他用户进程访问，需要每个进程拥有独立的地址空间。通过 基地址寄存器（base register） 和 界限地址寄存器（limit register） 可对进程内存加以保护，基地址寄存器存储进程可访问的最低合法物理内存地址（也就是进程的起始地址），界限地址寄存器决定从该地址开始的，可访问的内存范围大小。CPU 硬件对 用户模式 下产生的 每一个 地址和寄存器指明的地址区间比较，用户模式下的程序试图访问操作系统/其他用户进程内存的行为会触发陷阱（trap），操作系统会将其视为致命错误处理。

A pair of base and limit registers define the address space

如下图（其实也是从虚拟地址到物理地址的映射原理）

基地址寄存器和界限地址寄存器能且仅能由操作系统的特权指令加载，因为仅有操作系统在内核模式下执行，故避免了用户程序修改这两个寄存器。

重定位寄存器机制也允许操作系统动态改变，若某操作系统服务（如某个驱动程序）不常使用，则内存中不必保留其代码和数据，这类代码称为 暂时（transient） 操作系统代码，它们根据需要调入/调出，可在程序执行时动态改变操作系统大小。

内存分配

更全的分配方式见笔记补充。

最简单的内存分配方法：将内存分为多个 固定 大小的 分区（partition） ，每个分区只能容纳一个进程，多道程序的程度受分区数限制。当一个分区空闲时可以从输入队列选择一个进程调入空闲分区，进程终止时释放该分区。此种方式最初被 MFT（F：Fixed，IBM OS/360）使用，目前已被淘汰。

对 MFT 的推广是 MVT（V:Variable），即 可变分区（variable partition） 方案。操作系统维护一个表以记录哪些内存可用和哪些内存已被占用。初始时所有内存均可用于用户进程，可视作一大块可用内存，称为孔（hole）。新进程到来时需要查找足够大的孔，并从该孔为进程分配所需内存，孔内剩余内存可分配给其他进程。随着进程的到来和离开，内存中会分散着大小不同的孔。进程终止时释放的内存会形成新孔，若新孔和其他孔相邻，则这些相邻的孔可以合并为一个大孔。此时系统可以检查是否有进程在等待分配内存空间，以及新合并的内存空间是否满足该进程的需求。

上述 MVT 方法是通用动态存储分配问题（dynamic storage allocation problem）的一种情况，从内存中的一组孔中选择一个空闲孔有如下三种常用方法，其中执行时间、空间利用方面最差适应方法最差，空间利用方面首次适应和最佳适应相近，但首次适应更快：

• 首次适应（First fit） ：分配寻找到的第一个足够大的孔，查找可以从任何位置（如内存开始位置或上次首次适应结束的位置）开始，一旦找到足够大的空闲孔就停止；
• 最佳适应（Best fit） ：分配最小的足够大的孔，此方式必须查找整个表（若表内孔位置记录按孔的大小排序则不需要查找整个表）；
• 最差适应（Worst fit） ：分配最大的孔，同样需要查找整个表，产生的孔比最佳适应方法产生的孔价值更大。这样剩下的一块可以给另一个进程使用，避免最佳适应造成碎片。

碎片

随着进程装入和移出内存，空闲内存空间被分为散落的小段，产生 外部碎片问题（external fragmentation） ，所有可用内存空间之和满足一个/多个进程的请求，但这些可用内存并不连续。上述首次适应和最佳适应两种不同方法导致的碎片的数量也不同，对于不同的系统两者各有优劣，分配方向（从空闲块的顶端还是模块开始分配内存）也会对碎片数量产生影响。

50% 规则 ：对采用首次适应方法的统计表明，假定有 N 个块已被分配，无论采用什么优化，都可能有 0.5N 个块为外部碎片，即 1/3 的内存无法被使用。

维护一个小孔的开销比小孔本身可能更大，例如一个需要 2046B 空间的进程被分配了大小为 2048B 的孔，剩余的 2B 小孔维护的开销比 2B 大得多。因此通常采用固定大小的块而不是字节作为分配单元。此时进程被分配的空间通常大于所需空间，分配给进程的块中使用不到的空间被称为 内部碎片（internal fragmentation） 。

解决外部碎片问题的方法：

• 紧缩（compaction） ：移动内存内容使所有空闲空间合并为一整块。紧缩仅可在重定位是动态的、且在运行时重定位的情况下可用。紧缩根据采用的合并算法不同，需要的开销大小也不同，最简单的合并算法将所有进程移动到内存的一端，空闲的孔移动到内存另一端以生成大孔，其开销较大；
• 允许一个进程占有的内存地址空间非连续，只要有物理内存就可以为进程分配：分页、分段、分段+分页。

分页

分页（Paging） 允许进程物理地址空间非连续，内存和备份存储均按页划分，页大小相同。在前述连续内存分配中，内存中的数据换入/换出到备份存储时，备份存储中也会存在类似的碎片问题，而分页避免了这一点。传统的分页由硬件处理，最近的设计（64位机）结合了硬件和操作系统。 在第八章中，需要假定自己尚未了解第九章的内容，并且进程在执行前已经把所需要的全部数据分页加载到内存中 。

分页方法

将物理内存分为固定大小的块，称为 帧（frame） ，将逻辑内存分配同样大小的块，称为 页（page） 。备份存储页分为同样固定大小的块，进程执行时将执行所需的页从备份存储中调入可用的内存帧中。

主存中与页大小相等的物理块（帧）可称为页框

CPU 生成的每个逻辑地址分为两部分： 页号（page number）和 页偏移（page offset），记为 p 和 d 。页号为 页表（page table）的索引，页表包含每页位于物理内存的基地址，页 p 在页表中对应的基地址加上页偏移量 d 即为该逻辑地址映射的物理地址。

通过页表，将页号p映射到帧号f，页偏移不变。

对于逻辑内存与物理内存，更详细的：

页大小由硬件决定，通常为 2 的次幂，根据计算机结构不同，每页大小从 512B ~ 16MB 不等。页大小为 2 的幂可直接将逻辑地址的 2 进制表示划分为 p 和 d。

分页也是一种动态重定位，每个逻辑地址由分页硬件绑定为对应的物理地址。采用分页技术不会产生外部碎片，但可能有内部碎片（进程所需内存不足一页，或要求的内存大小不是页的整数倍则最后一帧有内存空闲）。

目前页大小通常为 4 ~ 8KB，有的系统支持更大页，有的 CPU 内核支持多种页大小。页的大小受如下因素制约：

• 在进程大小和页大小无关的前提下，可以假设每个进程平均有半页内部碎片，因此更小的页会带来更少的内部碎片；
• 页表对于页和物理内存中的帧的对应关系记录需要一定开销，并且该开销随着页大小的增大而减小，页表中每个条目通常占 4B（可变）。

分页的重要特点是 用户视角内存 和 实际物理内存 的分离，通过地址转换硬件将用户视角下的逻辑地址转换为物理地址。用户程序将内存作为一整块处理，而实际物理内存中进程可能分布在各个独立的帧中。用户进程无法访问其页表规定之外的内存，进程可见的页表仅包含进程拥有的页面记录。

操作系统使用 帧表（frame table） 维护物理内存的分配细节（已被占用的帧、可用帧等），帧表的每个条目对应一帧，并标明该帧是否空闲，若占用则被哪个（些）进程的哪个页占用等。操作系统同时 为每个进程维护一个页表的副本 ，当一个进程可被分配 CPU 时，CPU 调度程序可根据该副本定义硬件页表（用户进程运行在用户模式，若进行系统调用，操作系统需要使用进程的页表副本来获取进程逻辑地址映射的物理地址）。

页表的硬件支持

最简单的页表硬件实现方法将页表作为一组专用寄存器。

当代计算机允许页表非常大，因此页表放置在内存中，并设置 页表基寄存器（page-table base register，PTBR） 指向页表，改变页表的位置仅需要修改此寄存器。此种做法的缺陷在于访问一个字节需要两次内存访问（一次用于在内存的页表中查找页号对应的条目，一次用于获取目标字节），导致效率较低。

转换表缓冲区（translation look-aside buffer，TLB）是针对上述问题的专用快速硬件缓冲（或称为关联存储器、快表），其条目由键和值组成，查找方式是并行查找。TLB 查找速度快且造价昂贵，通常仅有 64 ~ 1024 个条目。TLB 和页表一起使用时，TLB 仅包含最近使用过的页表条目，查询流程如下：

• CPU 产生逻辑地址，从逻辑地址提取出页号交付 TLB，TLB 将页号和存储的键比对，若寻找到相同键则结束流程；
• 请求的页码不在 TLB 中，即 TLB 失效（TLB miss） ，此时需要在页表中查询。在页表中查询到与页号对应的帧号后，将页号和帧号增加到 TLB 中。若 TLB 中条目已满，则操作系统使用某种策略替换掉已有的一个条目，例如最近最少使用替换（LRU） 或随机替换等。TLB 中有的条目是永久驻留的（不允许从 TLB 中被替换），通常内核代码在 TLB 中的条目固定。
• 有的 TLB 在每个 TLB 条目中存储了 地址空间标识符（address-space identifier，ASID） ，该项用于唯一标识进程，为进程提供地址空间保护。TLB 解析虚拟页号时必须确保当前运行进程的 ASID 和 TLB 中条目对应的 ASID 匹配，否则视作 TLB 失效。除了内存空间保护，ASID 还使 TLB 能够同时包含多个不同进程的记录。如果 TLB 不支持每个条目有独立的 ASID，那么一旦有新页表被选择（例如进程的换入/换出），TLB 就需要被全部 刷新（flushed） 或删除，防止 TLB 中存在无效的条目（页号地址无效的条目，如上一个进程留下来的无效物理地址）导致被换入的进程使用错误的地址转换。
• 页号在 TLB 中被查找到的百分比为 命中率（hit ratio） ， 有效访问时间（effective access time） 的计算需要根据 TLB 的命中率加权。例如查找 TLB 需要 20ns，内存访问需要 100ns，命中率 80%，则有效内存访问时间为 0.8 x 120 + 0.2 x 220 = 140ns 。
• 需要注意的是， TLB 查询早于内存中页表的查询，只有 TLB 查询结束并且没有查询到帧号时才会开始在页表中的查询 。查TLB的速度要远快于查内存中的页表（大概块一到两个数量级）。

保护和共享

分页情况下内存保护通过每个帧对应的保护位实现，这些保护位通常保存在页表中。常见类型的位有：

• 可读写/只读位：产生地址引用时除了在页表中查找对应的帧码，还需要检查保护位验证是否有对只读页进行了写操作，若有则向操作系统产生硬件陷阱。扩展这种方法可提供更细致的保护。
• 有效/无效位：该位有效表示与之相关的页属于当前进程的逻辑地址空间，为合法页，否则与之相关的页不属于当前进程的逻辑地址空间。使用该位可以捕获到非法地址，操作系统通过对该位的设置可允许/禁止进程对某页的访问。

一个进程很少会使用到所有分配的地址空间，页表为地址范围内的所有页都建立一个条目是浪费的行为（并且每个进程有一个页表副本），表中的多数条目不会被使用，而这些条目却占据可用地址空间。有些系统提供了 页表长度寄存器（page-table length register，PTLR） 表示页的大小，该寄存器的值可用于验证逻辑地址是否处于进程的有效范围内。

分页存储可以 共享 公共代码，这对于分时系统非常重要。例如一个多用户系统，每个用户均执行一个文本编辑器，若代码不支持共享，则每个用户需要维护一个文本编辑器的副本；若代码是 可重入代码（reentrant code） 或 纯代码（pure code） ，则这部分代码可以被共享。可重入代码是不能自我修改的代码，它们在执行期间从不改变因此多个进程可以同时执行这部分代码。当然，除了共享的代码，每个进程还有自己的寄存器副本和数据存储。要实现共享，代码必须能够重入，并且可重入代码的只读性需要操作系统强制实现。（如果你了解 Haskell，可重入代码和 Haskell 里的 pure code 有类似的特性，后者不会对环境产生副作用，每次执行仅根据参数确定结果）

页表结构

• 层次页表（Hierarchical Paging） ：当代计算机支持非常大的逻辑地址空间，此时页表本身将非常大。例如 32 位逻辑地址空间的计算机系统，若页大小为 4KB，则页表需要包含 2^20 个条目，即使每个条目在页表中仅需要 4B 存储，整个页表也需要 4MB 物理地址空间存储（每个进程还需要独立维护一个副本）。因为内存采取分页管理，页表的大小超过了一个页面的大小，因此需要将页表划分到足够小以便一页能够容纳。一种可行的方式是二级分页算法：例如上述 32 位逻辑地址系统，可将 20 位页号划分为 10 位的外部页表页码 p1 和 10 位的页表偏移量 p2。此种方案也称为 向前映射页表（forward-mapped page table） 。对于 64 位体系结构，层次结构并不合适，例如 64 位 UltraSPARC 体系结构使用 7 级分页，几乎已经是内存访问极限。

• 哈希页表（Hashed Page） 以虚拟页码作为哈希值，每个条目包括一个链表用于处理碰撞。链表中的每个元素包含三个域：虚拟页码，对应帧号以及指向链表中下一个元素的指针。此种方式的地址映射过程如下：将虚拟页号哈希到表中某个条目，若该条目对应的链表存在元素，则按顺序比较直到找到对应的元素。哈希页表的一个变种是 群集页表（clustered page table） ，它的每个条目包括多页信息，因此一个条目存储了多个物理页帧的映射，这对于 稀疏（sparse） 地址空间非常有效，稀疏地址空间中的地址引用通常不连续并且散布在整个地址空间。

• 反向页表（inverted page table） ：每个进程均维护一个相关页表，这个进程使用到的每个页在其持有的页表里有一项，或者每个虚拟地址在页表里都有一项而不论这个虚拟地址是否有效，此时每个页表会有很多项，这些表会消耗大量的内存，而其目的仅仅是追踪物理内存如何使用。反向页表中，每个真实的内存页/帧存在一个条目，该条目包括引用该物理帧的虚拟页号以及拥有该页的进程信息。所以整个系统只有一个页表，每个物理内存帧仅有一条相应的条目。
  • 一种简化的反向页表实现（IBM RT 采用）：系统每个虚拟地址对应一个三元组 <pid | page numbe r | offset>，反向表中每个条目为 <pid | page number>，需要内存引用时，操作系统查找反向页表寻找匹配，若匹配找到则产生物理地址，否则认为产生了非法地址访问。这种方案减少了存储每个页表所需的内存空间，但增加了查找页表所需要的时间。反向页表按照物理地址排序，而查找依据虚拟地址，所以可能需要查找整个表来寻找匹配。可以使用 哈希页表 限制页表条目或加入 TLB 来改善。此外，采用反向页表的系统很难共享内存，因为每个物理帧只对应一个虚拟页条目。对于这种情况，可以允许页表的没一个条目仅包含一个虚拟地址到共享内存地址的映射，这时对未被映射虚拟地址的引用会导致页错误（page fault）。
  • 实际使用很少

层次页表与局部性原理（来着os-note1-6）

在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万 （2^20） 个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。

这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。

那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。

要解决上面的问题，就需要采用的是一种叫作多级页表（Multi-Level Page Table）的解决方案。（就是层次页表）

在前面我们知道了，对于单页表的实现方式，在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 多万个「页表项」，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用 4MB 大小的空间。

我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。如下图所示：

你可能会问，分了二级表，映射 4GB 地址空间就需要 4KB（一级页表）+ 4MB（二级页表）的内存，这样占用空间不是更大了吗？

当然如果 4GB 的虚拟地址全部都映射到了物理内存上的话，二级分页占用空间确实是更大了，但是，我们往往不会为一个进程分配那么多内存。

其实我们应该换个角度来看问题，还记得计算机组成原理里面无处不在的局部性原理么？

每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。

如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

那么为什么不分级的页表就做不到这样节约内存呢？我们从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

我们把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用。

对于 64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：

• 全局页目录项 PGD（Page Global Directory）；
• 上层页目录项 PUD（Page Upper Directory）；
• 中间页目录项 PMD（Page Middle Directory）；
• 页表项 PTE（Page Table Entry）；

分段

采用分页管理导致用户视角的内存和实际物理地址内存分离，对于装载/写入操作必须将虚拟内存映射到实际的物理内存。 分段（segmentation） 支持另一种用户视角，其逻辑地址空间由一些段组成，每个段有自己的编号和长度，用户通过段号和段内偏移（与分页的区别在于，分页管理中用户只指定一个虚拟地址，由硬件将虚拟地址拆分为页码和偏移，这些工作对程序员透明）来指定地址。

编译用户程序时，编译器会自动根据输入的程序源码构造段（代码段、静态区、堆、栈等），编译时链接的库可能被分配不同的段，加载程序时装入这些段并分配段号。

用户可以通过二维地址（段号、偏移）来引用存储单元，但实际物理内存仍然为一维的序列。操作系统通过 段表（segment table） 实现将二维用户定义地址映射到一维物理地址，段表的每个条目对应一个段，存储着该段的段号（s）、段基地址（base）（段在内存中开始的物理地址）和段界限（limit）（段的长度），对于某段超出段长的地址引用访问会导致硬件陷阱的触发。

段表在内存中的位置由 段基址寄存器（segment table base register，STBR） 和 段长度寄存器（segment table length register，STLR） 指定，当段号 s 满足 s < STLR 时该段合法。

分段会导致不连续的空闲内存空间以及外部碎片，但是没有内部碎片，从空闲内存为进程分配段也存在类似连续内存分配中的问题，有首次适应和最佳适应两种分配方式。

段可以被共享，多个进程可以通过相同段号共享同一个段。段的保护可通过类似页表中的保护位实现，段表中的每一条条目有一个合法位（为 0 表示不合法），同时也可以支持读/写/执行权限。

分段地址空间是二维的

主要区别在于页号与段号，页号是系统生成的，访问地址时相同会将其划分为页号和页内偏移，页号本身是线性连续的。而段号是程序员自己定义的，不同段号有不同含义。

段页式内存管理

内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理。

段页式内存管理实现的方式：

• 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
• 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；

这样，地址结构就由段号、段内页号和页内位移三部分组成。

用于段页式地址变换的数据结构是每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号，如图所示：

段页式地址变换中要得到物理地址须经过三次内存访问：

• 第一次访问段表，得到页表起始地址；
• 第二次访问页表，得到物理页号；
• 第三次将物理页号与页内位移组合，得到物理地址。

可用软、硬件相结合的方法实现段页式地址变换，这样虽然增加了硬件成本和系统开销，但提高了内存的利用率。

第三章习题拾遗对以上几部分有更多阐释

选B。这是因为，分页更侧重于系统管理，提高内存利用率。分段更侧重于满足用户的内存需求。

实例：Intel Pentium

• 奔腾结构允许一个段的大小最大为 4GB，每个进程最多可持有 16K 个段。进程逻辑地址空间分为两部分，第一部分最多由 8K 个段组成，此部分私有；第二部分最多由 8K 个段组成，此部分可以被所有进程共享。第一部分的信息保存在 本地描述符表（local descriptor table，LDT） 中，第二部分信息保存在 全局描述符表（global descriptor table，GDT） 中，这两个表中每个条目占 8B 空间，包括一个段的详细信息（段基址、段界限）。
• 逻辑地址格式： <selector | offset>，其中选择器（selector）是一个 16 位的数，前 13 位表示段号，第 14 位表示该段在 GDT 还是 LDT 中，最后两位表示保护信息，支持四级保护。偏移量（offset）是 32 位的数，表示段内偏移量。奔腾 CPU 中有 6 个段寄存器，允许一个进程同时访问 6 个段，同时还有 6 个 8B 微程序寄存器保存相应的来自于 LDT 或 GDT 的描述符，它们使奔腾不必在每次内存引用时从内存读取描述符。
• 奔腾结构允许页的大小为 4KB 或 4MB，对于 4KB 的页，奔腾使用二级分页方案，32 位线性地址划分为 10、10、12 三块，类似前述的二级分页的例子。最高 10 位引用 页目录（page directory） 的条目，中间 10 位指向内部页表，最后 12 位为 4KB 页面内的偏移。页目录中每个条目有一个 PageSize 标志，若该标识被设置则代表页帧大小 4MB，此时跳过中间 10 位对内层页表的查询，直接使用后 22 位指向 4MB 页帧内偏移。奔腾的页表还可以交换到磁盘上，通过页目录条目的无效位表示该条目对应的页表位于内存还是磁盘。若页表在磁盘上，则可使用条目中剩下的 31 位标明页表在磁盘的具体位置以调入内存。
• 奔腾体系结构上运行的 Linux 系统使用 6 个段（内核代码段、内核数据段、用户代码段、用户数据段、任务状态段 TSS 以及默认的 LDT 段）。Linux 中默认的 LDT 段被所有进程共享，如果一个进程需要自己的 LDT ，则它可以生成一个新的 LDT 来代替默认值。此外，每个进程有自己的 TSS 以存储上下文切换中的硬件上下文，每个进程也有自己的页表。
• 奔腾体系结构上运行的 Linux 仅使用了四级保护中的两种，用于区分内核模式和用户模式。Linux 采用三级分页方案（全局目录-中间目录-页表-偏移），而奔腾采用二级分页模式，此时 Linux 的 “中间目录” 大小为 0，因此等价于奔腾的二级分页。

第八章习题拾遗

一、地址变换

[2011统考真题]在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是()
A、编辑 B、编译 C、链接 D、装载

答案是C。

编译后的程序需要经过链接才能装载，而链接后形成的目标程序中的地址也就是逻辑地址。以 C 语言为例：C 程序经过 预处理 → 编译 → 汇编 → 链接 产生了可执行文件，其中链接的前一步是产生可重定位的二进制目标文件。C 语言采用源文件独立编译的方法，如程序main.c，file1.c，file2.c，file1.h，file2.h 在链接的前一步生成了 main.o，file1.o，file2.o，这些目标模块的逻辑地址都从0开始，但只是相对于该模块的逻辑地址。链接器将这三个文件、libc 和其库文件链接成一个可执行文件。链接阶段主要完成重定位，形成整个程序的完整逻辑地址空间 。
例如，file1.o 的逻辑地址为 0 ~ 1023，main.o 的逻辑地址为 0 ~ 1023 ，假设链接时将 file1.o 链接在 main.o 之后，则链接之后 file1.o 对应的逻辑地址应为 1024 ~ 2047，整个过程如图所示。

二、段表映射

简单，不赘述。

三、重定位

以下主要参考 https://bbs.pediy.com/thread-76876.htm

静态重定位：即在程序装入内存的过程中完成，是指在程序开始运行前，程序中的各个地址有关的项均已完成重定位，地址变换通常是在装入时一次完成的，以后不再改变。

动态重定位：即在程序运行过程中要访问数据时再进行逻辑地址与物理地址的变换（即在逐条指令执行时完成地址映射）。（解决碎片问题，以及使程序可浮动的最好的办法是采用动态重定位技术）

以下介绍程序是如何装入内存，从而变成在计算机内可执行的形式的。

在用汇编语言或高级语言编写的程序中，是通过符号名来访问子程序和数据的，我们把程序中符号名的集合叫做“名字空间”。汇编语言源程序经过汇编，或者高级语言源程序经过编译，得到的目标程序是以“0”作为参考地址的模块，然后多个目标模块由连接程序连接成一个具有统一地址的装配模块，以便最后装入内存中执行。我们把目标模块中的地址称为相对地址（或逻辑地址），而把相对地址的集合叫做“相对地址空间”或简单地叫做“地址空间”。

装配模块虽然具有统一的地址空间，但它仍是以“0”作为参考地址，即是浮动的。要把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代码，这一过程叫做地址重定位，也就是说，是由逻辑地址确定物理地址。

地址空间的程序和数据经过地址重定位处理后，就变成了可由CPU直接执行的绝对地址程序。我们把这一地址集合称为“绝对地址空间”或“存储空间”。

地址重定位完成的相对地址转换成内存的绝对地址工作又称为地址映射（map）、按照重定位的时机，可分为静态重定位和动态重定位。

静态重定位

静态重定位是在程序执行之前进行重定位，它根据装配模块将要装入的内存起始位置，直接修改装配模块中的有关使用地址的指令。

例如，一个以“0”作为参考地址的装配模块，要装入以100为起始地址的存储空间。显然，在装入之前要做某些修改，程序才能正确执行。例如，MOV　EAX，[500]这条指令的意义，是把相对地址为500的存储单元内容1234装入EAX号累器。现在内容为1234的存储单元的实际地址为1500，即为相对地址(500)加上装入的地址(1000),因此，MOV　EAX，[500]这条指令中的直接地址码也要相应地加上起始地址，而成为MOV　EAX，[1500]。

程序中涉及直接地址的每条指令都要进行这样的修改。需要修改的位置称为重定位项，所做的加实际装入模块起始地址修改中的块起始地址称为重定位因子。

为支持静态重定位，连接程序在生成统一地址空间和装配模块时，　应产生一个重定位项表，连接程序此时还不知道装配模块将要装入的实际位置，故重定位表所给出的需修改位置是相对地址所表示的位置。

操作系统的装入程序要把装配模块和重定位项表一起装入内存。由装配模块的实际装入起始地址得到重定位因子，然后实施如下两步：

• 取重定位项，加上重定位因子而得到欲修改位置的实际地址；
• 对实际地址中的内容再做加重定位因子的修改，从而完成指令代码的修改。

对所有的重定位项实施上述两步操作后，静态重定位才完成，尔后可启动程序执行。使用过的重定位项表内存副本随即被废弃。

静态重定位有着无需硬件支持的优点，但存在着如下的缺点：一是程序重定位之后就不能在内存中搬动了；二是要求程序的存储空间是连续的，不能把程序放在若干个不连续的区域内。

动态重定位

动态重定位是指，不是在程序执行之前而是在程序执行过程中进行地址重定位。更确切地说，是在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改而装入内存，但是它需要硬件——定位寄存器的支持。

程序的目标模块装入内存时，与地址有关的各项均保持原来的相对地址不进行任何修改。如MOV　1，[500]这条指令仍是相对地址500。当此模块被操作系统调度到处理机上执行时，操作系统将把此模块装入的实际起始起始地址减去目标模块的相对基地址，然后将其差值装入定位寄存器中。当CPU取得一条访问内存的指令时，地址变换硬件逻辑自动将指令中的相对地址与定位寄存器中的值相加，再依此和值作为内存绝对地址去访问该单元中的数据。

由此可见，进行动态重定位的时机是在指令执行过程 中，每次访问内存前动态地进行。采取动态重定位可带来两个好处：

• 目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确执行，这对于存储器紧缩、解决碎片问题是极其有利的；
• 一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不是顺序相邻的，只要各个模块有自己对应的定位寄存器就行。

动态重定位技术所付出的代价是需要硬件支持。

四、页表映射

选A，很简单（块号就是帧号（frame））

五、存储与内部碎片

分页式产生内部碎片，分段式产生外部碎片（每段内部还是连续分配），但不会产生内部碎片，段页式会有内部碎片。

固定分区存储管理

把主存中可分配的用户区域预先划分成若干个连续的分区，每个连续区的大小可以相同，也可以不同。但是，一旦划分好分区之后，主存中分区的个数就固定了，且每个分区的大小也固定不变。这是一种静态分区法。

在固定分区方式管理下，每个分区用来装入一个作业。由于主存中有多个分区，就可同时在每个分区中装入一个作业。所以，这种存储管理方式适用于多道程序系统。

六、页表

选D，有利于快速访问。有起始寄存器，长度寄存器。

为什么分页机制中逻辑地址空间是一维的，而分段机制中逻辑地址空间是二维的？

页式，一个程序的各页是根据你的程序空间连续编址的，程序地址空间只有一维；

而段式，一个程序拆分成各段，独立编址（各段都从零开始编址），程序地址空间有两维。

例如一个50KB的程序，页式分配，不妨设每页4KB，各页地址分别为0~4，4~8 … 44～48；

而段式分配，各段地址则可能是0~20，0~20，0~10

假设有一段程序，在没有采用分段机制的时候（采用分页机制），这段程序会被编译成一大段机器指令，这些指令之间地址是连续的。如下图：

从图中我们可以看出逻辑地址空间如果采用分页机制，那么第0页的最后一个地址和第1页的第一个地址在数值上是连续的。因此分页机制的逻辑地址空间是一维的。

相对应的如果采用分段机制，那么这段程序就会被编译程序编译成多个段，比如数据段、代码段、附加段等，每个段的段号是编译器自动分配的，每个段的长度不定（一般最长64k）。如下图所示。从下图中我们可以看到，由于每个段的长度不一，因此虽然数据段、代码段的段号是连续的，但是数据段的最后一个地址和代码段的第一个地址是不连续，因此分段机制中的地址不是一维的，而是二维的。

八、页表的内存存储

选A。（反转页表不然但是一般不用）

九、页表

仅I正确。III应该是段式，用户并不关心在哪个页。页是分散的，在开始时不能确定，所以IV不对

十、二级页表

我们可以计算得到页表项个数为 $2^{10}\div 2=2^9$，则 $2^{16}$ 页需要 $2^{16}\div 2^9=128$个

第九章、虚拟内存

背景

虚拟内存技术允许进程在执行时不完全加载入内存（动态加载也可以实现，但要求程序员做更多细致的工作），因此程序可以远大于物理内存。虚拟内存将内存抽象为一个 统一的 巨大的统一存储数组，使用户看到的逻辑内存和物理内存分离，允许程序员不受内存存储限制。此外虚拟内存使进程共享文件/地址空间变得容易。

很多情况下不需要将整个程序加载到内存中，如：

• 程序执行过程中通常很少发生错误，处理异常错误的代码几乎不被执行
• 数组、链表、表等结构通常会被分配比实际需要的更大的内存
• 程序的一些功能/选项很少被使用

只将程序的一部分加载入内存可以带来如下优势：

• 程序不再受物理内存空间限制，用户可以针对一个远超过物理内存大小的 虚拟地址空间（virtual address space） 编写程序从而简化编程工作量；
• 更多的程序可以同时执行（每个程序使用了更少的物理内存），CPU 利用率也随之增加（响应时间/周转时间不随之增加）；
• 内存与备份存储之间换入换出的速度加快（程序实际占用物理内存变小）。

进程的虚拟地址空间即为进程在内存中存放的 逻辑 视图，通常进程的的虚拟地址空间从某一个逻辑地址开始（比如 0）连续存放。随着动态内存分配，堆向上增长，子程序调用带来栈向下增长以及载入动态链接库时空白区域被填充。堆和栈之间的巨大的空白部分是虚拟地址的一部分，但只有在堆/栈生长时这部分虚拟地址才需要对应实际的物理帧。含有空白的虚拟地址空间称为 稀疏（sparse） 地址空间。

虚拟内存允许文件和内存通过共享页被多个进程共享，优势在于：

• 系统库可被多个进程共享
• 多个进程之间可以通过共享内存通信
• 允许系统调用 fork() 创建进程之间的共享页从而加快进程创建。

按需调页（Demand Paging）

概念

当且仅当需要某页时才将该页调入内存的技术称为 按需调页（demand paging） ，被虚拟内存系统采用。按需调页系统类似于使用交换的分页系统，进程驻留在二级存储器上（磁盘），进程执行时使用 懒惰交换（lazy swapper） 换入内存。因为这种方式将进程视作一系列页而非巨大的连续空间，而 交换程序（swapper） 是对整个进程进行操作，因此使用 调页程序（pager） 对进程的单个页代替交换程序。

需要一定形式的硬件区分哪些页在内存中，第八章中的有效/无效位可用于此目的，当该位设为有效时表示对应的页既合法又在内存中，而该位设置为无效时表示相关的页无效（不属于进程的逻辑地址空间）或有效但尚未调入内存。对于尚未调入内存的页，其页表条目的标志位设置为无效或者包含了该页在磁盘上的地址。

进程通过MMU试图访问页表中尚未调入内存中的页会触发页错误陷阱（page-fault trap），则（内核态）操作系统会按如下流程处理页错误：

• 检查进程的内部页表（进程维护的内部页表和 PCB 一起保存）来确定该引用是否为合法地址，若引用非法则终止进程，否则准备从磁盘中调入页面；
• 操作系统寻找一个空闲帧（如从空闲帧链表中选择一个元素）；
• 操作系统调度 磁盘，将需要的页调入到上一步分配的空闲帧；
• 磁盘读操作完成后修改进程的内部页表和操作系统维护的页表以表示该页已经位于内存中（重置页表、填入帧号及修改页表标志位）；
• 重新读取因为页错误而中断的指令，进程可以访问此前无法访问的页。

上述按需调页的一种极端情况是在不调入任何需要页的情况下就执行进程，因此进程执行过程中将不断出现页错误、调入页、继续执行。这种方案称为 纯粹按需调页（pure demand paging） 。

理论上单个指令可能触发多个页错误（例如一页用于获取指令，一页用于获取指令所需的数据），但此种情况较少见，正常执行程序满足 局部引用（locality of reference） 特性，使按需调页的性能较好。

按需调页与分页

按需调页所需的硬件支持和分页、交换相同：

• 页表 ：通过有效/无效位保护进程地址空间
• 次级存储器 ：备份存储，保存不在内存中的页，通常为快速磁盘，用于和内存交换页的部分空间称为 交换空间（swap space） 。Linux 系统所需的 /swap 挂载点挂载的存储空间即为交换空间。

虚拟技术的困难在于，分页是加在 CPU 和内存之间的，并且要对用户进程完全透明。人们通常假定分页能够应用到任何系统中，这个假定对于非按需调页的环境而言是正确的（缺页即为访问无效内存，产生致命错误），而在按需调页系统中，页错误意味着可能缺页、需要调入一个额外的页。

调入额外的页的过程很可能导致原始的指令在调页完成后重新执行不再正确。考虑下面的情况：

• MVC 指令可以将 256B 的块从一处移动到另一处（可能重叠），如果源块或者目的块中任何一块跨越了页边界，则移动操作执行（在执行前并没有意识到源块/目标块缺页）到一半可能会出现页错误；
• 在上述情况（跨页）的基础上，如果源块和目的块有重叠（overlap），则移动执行到一半时，源块可能已经被修改，这时调页进入内存后，不能简单地重启该指令。

上述两类情况有两种不同解决方案：

• 微码计算并试图访问两块的两端，如果出现了页错误，则在指令 MVC 执行前将缺页调入内存；
• 使用临时寄存器保存 MVC 指令从执行到触发缺页之间被覆盖了的数据，如果发生了页错误，则临时寄存器中保存的值在处理页错误之前写回到内存，此时调页完成后指令可以重启，状态与之前相同。

性能

按需调页内存的 有效访问时间（effective access time） 计算为： $有效访问时间 = (1-p) \times ma + p \times 页错误时间)$。其中 ma 为计算机系统的内存访问时间，通常为 10 ~200ns； p 为出现页错误的概率，p 越接近于 0 则页错误发生越少。

进程 P 触发了页错误会导致下列动作：

1. 触发硬件陷阱，操作系统中断进程 P
2. 操作系统保存用户进程 P 的寄存器、进程状态
3. 确定中断是否为页错误，若是则判断页引用是否合法，若合法则确定页所在磁盘位置
4. 从磁盘读入页到某个空闲帧，这一步又包括：在该磁盘队列中等待直到处理完排在自己之前的请求，磁盘寻道/延迟以及磁盘传输的时间
5. 磁盘等待过程中将 CPU 分配给其他进程 Q（CPU 调度）
6. 从 I/O 子系统接收到中断
7. 保存 Q 的寄存器和进程状态（如果执行了第 5 步）
8. 确定中断是否来自于之前页错误触发的磁盘请求，若是则修正页表和其他表以更新页信息
9. 等待 CPU 调度程序将 CPU 资源再次分配给进程 P
10. 恢复进程 P 的用户寄存器、进程状态和新页表，重新执行被中断的指令

以上步骤不是全部必需的，例如第 5 步可以提高 CPU 使用率，但执行完 I/O 后也需要额外的时间保存现场。无论如何， 缺页导致的页错误处理时间主要包括：处理页错误中断、读入页以及重新启动进程 三部分，其中读入页除了磁盘设备本身的处理时间，还可能包括等待设备的时间。

交换空间的处理和使用对按需调页的性能也有很大影响，磁盘 I/O 操作到交换空间比到文件系统要快，因为 交换空间按照大块来分配 。如果在进程开始时将整个文件镜像复制到交换空间，并从交换空间执行按页调度则可能获得更好的调页效果。另一种方式是进程执行开始时从文件系统按需调页，但当出现页置换时则将页写入交换空间，这样只有所需的页才会从文件系统调用，而一旦调用某页，此后的该页再次调度时会从交换空间读入。

写时复制和页面置换

写时复制

系统调用 fork() 是将子进程创建为父进程的副本，传统的 fork() 会为子进程创建一个父进程地址空间的副本，将父进程的页复制，但由于很多子进程创建之后立刻执行系统调用 exec()，因此复制父进程地址空间完全没有必要。 写时复制（copy-on-write） 技术允许父进程和子进程开始时共享同一页面，这些页面标记为写时复制页，如果任何一个进程对某一个写时复制页进行了写操作，则为这个进程创建一个该页的副本。注意， 只有可能被修改的页才会被标记为写时复制 ，对于不允许被修改的页面（如包含可执行代码的页）可以被父进程和子进程共享。

许多操作系统为分配空闲页请求提供了空闲缓冲 池（pool） ，池中的空闲页在进程的栈/堆需要扩展时可用于分配，或者用于管理写时复制页。操作系统通常使用 按需填零（zero-fill-on-demand） 技术分配这些页，这些页在分配之前被填入 0 覆盖，因此清除了之前的内容。

虚拟内存 fork 是有的 UNIX 版本提供的 fork() 操作变种，vfork() 将父进程挂起，自己成使用父进程的地址空间，并且不采用写时复制。因此子进程对父进程地址空间的任何修改都会在父进程重启时可见。vfork() 主要用于子进程创建后立刻调用 exec() 的情况，它不会导致页面的复制操作，有时用来 实现 shell 接口 。

fork（）会产生一个和父进程完全相同的子进程，但子进程在此后多会exec系统调用，出于效率考虑，linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。在fork之后exec之前，两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间，如果不是因为exec，内核会给子进程的数据段、堆栈段分配相应的物理空间（至此两者有各自的进程空间，互不影响），而代码段继续共享父进程的物理空间（两者的代码完全相同）。而如果是因为exec，由于两者执行的代码不同，子进程的代码段也会分配单独的物理空间。

fork之后内核会通过将子进程放在队列的前面，以让子进程先执行，以免父进程执行导致写时复制，而后子进程执行exec系统调用，因无意义的复制而造成效率的下降。

页面置换概念

增加多道程序的程度会导致内存的 过度分配（over-allocating) 。I/O 缓存也需要使用大量内存，缓存的使用会增加内存分配算法的压力，有的操作系统为 I/O 缓存分配了一定比例的内存，有的则允许用户进程和 I/O 子系统竞争全部系统内存。

内存的过度分配会导致某个进程触发了页错误而没有空闲帧可用，因为按需调页对用户而言透明，因此操作系统不应当直接终止进程（操作系统也可以交换出一个进程来降低多道程序的级别，这种选择有时是好的）。

页置换（page replacement）发生在需要调页而没有空闲帧的情况，流程如下：

• 查找所需页在磁盘上的位置
• 查找空闲帧，若有则使用，否则通过页置换算法选择一个 牺牲（victim） 帧并将牺牲帧的内容写入备份存储（磁盘，交换空间），改变页表和帧表
• 将所需页写入到空闲帧，并改变页表和帧表
• 重启用户进程

可以看出，在没有帧空闲，需要页置换的情况下，会有两个页传输（一页换出，一页换入），这加倍了页错误处理时间。这一点可以通过在页表的每个条目中增加 修改位（modify bit） 或 脏位（dirty bit） 来降低额外开销，如果被置换出的页对应的修改位没有被设置，则说明此页从被调入内存后没有被修改，因此不必被写入回磁盘，这样就省去了换出的时间。

按需调页需要开发 帧分配算法（frame-allocation algorithm） 和 页置换算法（page-replacement algorithm） 。页置换算法的好坏可以通过计算页错误率进行评估：对于同一进程对一个特定的内存地址引用序列，运行置换算法，计算出页错误的数量。这个引用页号的序列称为 引用串（reference string） ，可以人工产生也可以跟踪一个真实的系统并记录其访问内存地址。利用两个事实可以降低引用串的数据量：只考虑内存引用的页码而不考虑完整地址；如果有对页 p 的引用，则紧跟着对页 p 的引用绝不会产生页错误。

理论上来说，我们期待增加可用帧（增加物理内存大小就会增加可用帧数量）的数量能够使页错误的数量相对应减少。 Belady 异常（Belady’s anomaly） 指违背这一期待的现象：对于有的页置换算法，页错误率甚至可能随着分配的物理帧数增加而增加，例如下面的 FIFO 算法。

页面置换算法

基本页置换算法

FIFO页置换 ：最简单的页置换算法，操作系统记录每个页被调入内存的时间，当必需置换掉某页时，选择最旧的页换出。实际操作中不需要真的记录调入时间，可以通过一个 FIFO 队列管理内存中的页，置换算法从队列的头部取出换出的页，将换入的页加入到队列尾部。FIFO 页置换算法的性能并不总是很好，它置换出的页可能是一个很久以前现在已经不再使用的页（符合我们的期望），也可能是一个进程创建时初始化的变量，而这个变量仍然在不停地被使用，此时被调出的这页很快就会再次导致页错误。

样例如下：空白表示没有出现页错误，否则说明出现页错误而进行了替换或调入。

初始时通过页错误调入7,0,1，然后加载页号为2的页时没找到，最先进入的是7，所以将7替换为2，以此类推

最优置换（optimal page-replacement） 是所有页置换算法中页错误率最低的，但它需要引用串的先验知识，因此无法被实现。它会将内存中的页 P 置换掉，页 P 满足：从现在开始到未来某刻再次需要页 P，这段时间最长。也就是 OPT 算法会 置换掉未来最久不被使用的页 。OPT 算法通常用于比较研究，衡量其他页置换算法的效果。

初始时通过页错误调入7,0,1，然后加载页号为2的页时没找到，在未来最久不会被使用（也就是在引用串中从当前位置往后找，找页号中在引用串中距离当前位置最远的页号）的页号为7，所以将7替换成2。

最近最少使用算法（least-recently-used algorithm）简称 LRU，它置换掉到目前时刻最久未被使用的页。这一算法可以视作 OPT 的倒转，LRU 和 OPT 算法都属于栈算法（stack algorithm），它们绝不会产生 Bleady 异常。一个有意思的地方在于，对于引用串 S，LRU 算法计算 S 和S^R的错误率时相同的（S^R是引用串 S 的逆序），这一特性对 OPT 算法也满足。LRU 策略可能需要一定的硬件支持，因为它需要为页帧按上次使用时间确定一个排序序列。两种实现方式：

• 计数器（counters） ：每个页表的条目关联一个时间域，CPU 增加一个计数器，每次内存引用发生时，计数器增加，并且将引用的页在页表中对应的条目的时间域更新为计数器的内容。这样 LRU 需要搜索页表置换具有最小时间域的页。这种方式每次内存访问都要写入内存，页表改变（因为 CPU 调度）的时候还需要保持时间，还需要考虑时钟溢出问题。
• 栈（stack） ：采用页码栈维护，每当引用了一个页就将该页从栈中删除并放置到顶部，这样栈顶总是最近使用的页，栈底则为 LRU 需要替换的页。因为要从栈中删除某项，所以可实现为带有头指针和尾指针的双向链表，从栈中删除一页并放置到栈顶最坏情况下需要修改 6 个指针（要移动的这个节点在链表中间的情况下），但这种实现方式不需要搜索整个表。

同理，加载页号为2的页时没找到，在此前最久没有被使用（也就是在引用串中从当前位置往前找，找页号中在引用串中距离当前位置最远的页号）的页号为7，所以将7替换成2。

近似 LRU 页置换算法

近似 LRU 页置换算法（LRU-Approximation Page Replacement） ：很少有系统能够提供足够的硬件支持真正的标准 LRU 页置换，通常通过引用位的方式提供支持实现近似的 LRU 算法。页表的每一个条目都关联着一个 引用位（reference bit） ，每当引用了一个页（无论读写），都将该页在页表中对应条目的引用位置位，检查引用位就可以确定哪些页使用过：

• 附加引用位（Additional-Reference-Bits） 算法：位于内存中的每页对应的条目保留一个字节（8位），这个字节的 8 位说明了这一页在过去 8 个时间周期内的使用情况。每过一段规定的时间间隔（如 100 ms），时钟定时器产生中断并将控制转交给操作系统，操作系统将页表每个条目的引用位右移，最低位舍弃，最高位设置为引用位，并将引用位清零。具有最小值的页即为 LRU 替换的页。这里历史位共 8 位，长度可以调整，极端情况下可以为 0 位（此时仅剩下引用位本身）。
• 二次机会（Second-Chance） 算法：该算法基本算法是 FIFO 置换。每当准备置换出一页时检查其引用位，如果引用位为 0 则直接置换该页，否则将引用位清零并给该页第二次机会，之后准备换出下一个 FIFO 页。如果一个页总是被使用，则其引用位经常被设置，所以不会被置换出内存。这种算法的实现采用循环队列，用一个指针表示下次置换队列中的哪一页，找到牺牲页时就将新页插入到牺牲页的位置。最坏情况下所有页都已经被设置，此时需要遍历整个循环队列，性质等价于 FIFO 置换，而所需时间比 FIFO 更长。
  • 而且在队列循环的时间间隔中，如果一个页被清零，但可能在此被使用，那下次循环时就可能会再次清零而不是直接替换
  • 一旦找到牺牲页并完成替换，剩下的页就不会进行清零

• 增强型二次机会（Enhanced Second-Chance） 算法：将引用位和修改位作为一对考虑以改进二次机会算法，这两个位可能有四种类型：(0, 0) 表示最近没有使用也没有修改（最佳置换页）；(0, 1) 表示最近没有使用但已修改（若置换则需要写入到磁盘）；(1, 0) 表示最近使用但尚未修改（此页可能很快会被使用）；(1, 1) 表示最近使用且已经被修改（此页可能很快会被使用并且如果置换需要写入磁盘）。这种方法给已经修改过的页更高的级别，降低了 I/O 操作数量。但找到要置换的页之前，可能需要搜索循环队列多次，每次将级别升高一级并寻找满足的页面。

  • (a,b)，a为访问位（使用位），b为脏位（修改位），每次都进行遍历所有页，做出如下修改

  • (0,0)->置换，新页设为(1,0)

  • (0,1)->(0,0)

  • (1,0)->(0,0)

  • (1,1)->(0,1)

基于计数的页置换算法

基于计数（Counting-Based） 的页置换通过为每页的条目保留一个引用次数的计数器来选择换出页，包括 LFU 和 MFU，这两种置换方式都很费时并且效果很差：

• 最不经常使用（least frequently used，LFU） 页置换算法：置换计数最小的页，理由是活动页通常有更大的引用次数。但带来问题是一个被使用多次的页可能已经很久不在使用，但仍然保留在内存中。一种解决方式是定期将次数寄存器右移一位来使使用次数指数衰减。
• 最常使用页（most frequently used，MFU） 置换算法：置换计数最大的页，理由是最小次数的页可能刚刚被调入且尚未使用。

页缓冲算法

系统保留一个空闲帧缓冲池，出现页错误时仍然选择一个牺牲帧，但牺牲帧写出前就将所需要的页写入到缓冲池的某一个空闲帧中，写入完成的空闲帧就可以直接被使用，这样无需等待牺牲帧的写出。牺牲帧写出到交换空间后，又会被添加到空闲帧缓冲池中。

此种方式的扩展之一是维护一个已经修改过的页面列表，当调页设备空闲时，就将一个修改过的页面写回到磁盘并重新设置其修改位，这样在真正需要置换时，牺牲页需要写入到磁盘的概率会降低。

另一种修改是保留一个空闲帧池（需要记录哪些页对应哪些帧），当页错误发生时先检查所需页是否在空闲帧池中，若在则无需 I/O，若不在则选择一个空闲帧并从硬盘读入所需页。这种技术通常和 FIFO 算法一起用于 VAX/VMX 系统，当 FIFO 错误置换了常用页时，被换出的页仍能够很快从空闲帧池中调出。很多 UNIX 系统也将这种方法和二次机会算法一起使用，降低因错误选择牺牲页引起的开销。

针对应用程序选择页置换

有些情况下操作系统提供的虚拟内存会让部分应用程序性能下降。例如数据库提供了自己的内存管理和 I/O 缓冲，若操作系统同时也提供了 I/O 缓冲，则用于 I/O 的资源加倍。此外，对于一个执行大量顺序磁盘读操作的行为，LRU 算法删除旧页保持新页，而应用程序可能更需要旧页，此时 MFU 比 LRU 更高效。

有些操作系统允许特殊程序绕过文件系统的数据结构，将磁盘视作逻辑块数组使用。这种数组称为 生磁盘（raw disk） ，针对这样的数组的 I/O 称为生 I/O。

缺段中断和处理（补充）

使用分段内存管理时，CPU 要访问的指令/数据不在内存中会产生缺段中断，操作系统会通过如下流程处理缺少段 X 的事件：

1. 考察内存中是否存在不小于 X 段长的空闲区，若存在则从该空闲区中为段 X 分配内存，转 4；

2. 若不存在，则考察内存中所有空闲区的总和是否小于 X 的段长，若总和大于 X 的段长则合并空闲区形成一个足够大的空闲区，并使用新空闲区为 X 分配内存，转 4；

3. 若空闲区总和仍小于 X 的段长，则按 FIFO 或 LRU 算法反复淘汰老段，形成一个长度不小于 X 段长的空闲区；

4. 将 X 段调入内存并修改段表

帧分配与系统颠簸

最少需要帧数

分配的帧不能超过可用帧的数量（除非存在页共享），但也不能少于满足进程继续运行的帧数（minimum number of frames）。分配帧数不能过少的原因包括：

• 性能：当分配给每个进程的帧数量减少时，页错误会增加从而减缓进程执行。
• 页错误会导致指令重启：必须由足够的帧来容纳单条指令执行所需要的全部页。例如某台机器的机器指令都只有一个内存地址作为参数，此时至少需要一帧用于存储指令所在的页空间，还需要分配一帧用于存储指令引用的数据所在的页。如果此时允许一级间接引用（地址间接引用），则进程至少需要三个帧才能完成指令的执行，如果仅两帧可用，则进程将陷入无穷尽的页错误中。这种问题的最坏情况出现在允许多层间接引用的计算机中，对于多级引用，必须等到所有所需页都位于内存中指令才能执行，这种困难的解决方案是限制指令的间接引用级数，超出引用级数时触发陷阱。

分配算法

平均分配（equal allocation/Fixed Allocation） ：给每个进程一个平均值，剩余的帧放置在空闲帧缓冲池中； 比例分配（proportional allocation/priority allocation） ：根据进程大小按比例分配内存。这两种分配方式，每个进程分配的数量都会随多道程序的级别而变化，当多道程序程度增加时，每个进程都需要失去一定数量的帧来提供给新进程，同理，多道程序程度降低时离开进程占有的帧可以分配给剩余的进程。

比例分配可以根据进程的优先级（或者是优先级和大小的结合）而不是进程的大小来分配，这样可以给高优先级的进程更多的内存以加速执行。

多个进程竞争帧时，可将页置换算法分为 全局置换（global replacement） 和 局部置换（local replacement） 。全局置换允许进程从所有帧的集合（包括其他进程持有的帧）中选择置换帧，这将导致某个进程所获得的帧的数量可能改变（从其他进程处选择了一个帧置换）；而局部置换只能允许进程选择分配给自己的某个帧，此时分配给每个进程的帧数量保持不变。

全局置换算法的一个问题在于进程不能控制自己的页错误率，进程位于内存的页集合会受到其他进程调页行为的影响。此外，相同进程执行所需的时间在不同环境下可能有很大差异。但由于局部置换不能使用其他进程不常用的内存，所以全局置换有更好的系统吞吐量，因此更为常用。

系统颠簸

当低优先级进程分配的帧数量少于体系结构所需的最少数量时，进程应当暂停执行并且换出分配的剩余帧，以使其他进程能够使用这部分帧空间。

对于分配帧数不足的进程，当进程缺少所需的页时触发页错误，此时必须置换某个页。如果当前所有页对于这个进程而言都是需要使用的页，则它置换出一个页后，又立刻需要这个页，因此它将频繁产生页错误并触发页调度行为。这称为 颠簸（thrashing） ： 如果一个进程在换页上用的时间多于执行时间，则这个进程在颠簸 。

系统颠簸的原因在于：操作系统监控 CPU 使用率，CPU 利用率过低时会引入新进程来增加多道程序程度。然而，采用全局置换算法时，一个进程会置换任意进程的帧，这可能导致被换出页所属的进程也触发页错误，它们会再从其他进程中获取帧。 这些链式反应带来的页调度行为将使进程排队等待换页设备，就绪队列变空，CPU 使用率降低，导致 CPU 调度程序随之增加多道程序程度，新进程将引发更多的页错误，CPU 使用率进一步降低 。系统颠簸现象如下图。

随着多道程序程度增加，CPU 使用率增加直到最大值，之后开始系统颠簸，此时必须降低多道程序程度才能增加 CPU 使用率并降低系统颠簸。 局部置换算法（local replacement algorithm） ，也称 优先置换算法（priority replacement） 可以限制系统颠簸：如果一个进程开始颠簸，则它不能从其它进程获得帧，但问题未得到彻底解决，一个进程颠簸时会花费大量时间等待调页设备，这将导致调页设备的平均等待队列变长，页错误的平均等待时间增加，此时其它未颠簸进程的有效访问时间也会增加。

要 防止颠簸 ，必须给进程提供足够多的帧。 局部模型（locality model） 可以帮助确定进程实际正在使用多少帧，该模型说明，进程执行时在局部之间移动。 局部是进程经常使用的页的集合，进程由多个不同局部组成且局部之间可能重叠 。如果进程分配的帧数小于现有局部的大小，则进程会颠簸，因为它无法把所有常用页都放置在内存中。例如，进程调用了一个子程序，则其进入新的局部，这个新局部中的内存引用包括子程序的指令、局部变量以及子程序使用到的部分全局变量；当子程序退出时，进程从该局部返回主程序的局部（也可能在之后再次调用子程序进入该局部）。因此，局部是由程序和数据结构定义的，它是缓存的基础（cache、LRU 置换算法其实也都是基于局部性原理，在访问序列完全随机的情况下性能甚至不如 FIFO 算法），如果对任意数据访问完全随机而没有局部性原理，则缓存完全无用。

工作集合模型

工作集合模型（working-set model） 基于局部性假设，使用参数 Δ 定义 工作集合窗口（working-set window）（一个滑动窗口） ，其思想是检查最近 Δ 个页的引用，这最近 Δ 个引用页的集合称为工作集合。工作集合是程序局部的近似：一个正在使用的页位于工作集合中，一旦它已经 Δ 个时间单位未被使用，则会从工作集合中删除。

工作集合的精确度和 Δ 有关，Δ 太小则无法包含整个局部，过大则可能包含多个局部。工作集合最重要的属性是它的大小，系统内每个进程的工作集合大小 WSSi（$working \,set\, of\, process\, P_i$）之和 D 就是所有进程总的帧需求量，每个进程都会经常使用位于其工作集合内的页。当 D > m （m 是系统最大可用帧数量）时，就会有进程得不到足够的帧从而出现颠簸。

使用工作集合模型的内存分配过程如下：操作系统跟踪每个进程的工作集合，并给每个进程分配大于其工作集合大小的帧数。如果尚有空闲帧则可加入新进程；如果需要分配的帧数大于可用帧数，则操作系统选择、暂停一个进程，这个进程的所有页写出到备份存储，其已经占有的帧会被分配给其他进程。

工作集合模型的难点在于 跟踪 ，每次内存引用都会增加新引用并丢弃老引用。 固定定时中断和引用位可以近似模拟工作集合模型 ，我们给每个页加引用位。例如 Δ = 10000 时，每 5000 个引用就产生一次定时中断，中断触发时将所有页的引用位复制到内存，复制完成后清除。当发生页错误，系统检查当前的引用位和位于内存中的引用位两个位（每次中断复制一位，10000 次引用中断 2 次因此复制了两个位）从而确定这一页是否在过去的 10000~15000 个引用中出现过（只要有至少一位为 1 就说明使用过，否则都为 0），若出现则认为该页在工作集合中。

这种模拟并不很准确，因为无法准确获取该页究竟在 5000 个引用中的具体哪个位置出现，增加中断频率和历史位的位数可以提高准确性，但相应的也会增加中断处理时间。

页错误频率

工作集合模型更适合用于预先调页，将其应用于控制颠簸有些不太灵活。 页错误频率（page-fault frequency，PFF） 策略能够通过测量、控制页错误率来更好的防止颠簸：颠簸有较高的页错误率，较高的页错误率说明进程需要更多帧，过低的页错误率说明进程可能分配了太多的帧。可以为页错误率设置上限和下限，超过上限就为进程分配更多帧，低于下限则移走帧。当页错误率过高而没有可用帧时，仍需要暂停一个进程并将其占有的帧释放、分配给具有过高页错误率的进程。

进程的工作集合和页错误率之间有直接关系，当进程从一个局部迁移到另一个局部时，工作集合改变，页错误率会进入波峰，随着需要调入的页逐步调入内存，页错误率又会下降。一个波峰的开始到下一个波峰的开始显示了工作集合的迁移。

其它

内存映射文件

通过虚拟内存技术将文件 I/O 作为普通内存访问的方法称为文件的 内存映射（memory mapping） 。文件的内存映射将一个磁盘块映射成内存的一页（或多页），开始时文件访问和普通的请求界面调度相同，并且产生页错误，这样一页大小的部分文件就会从文件系统读入到物理内存中（部分系统一次会读入多页大小内容）。通过内存操作文件而不是系统调用 read() 和 write() 能够简化文件访问和使用。

对映射到内存中的文件做写操作可能不会立刻写回到磁盘文件中。有的操作系统定期检查文件在内存中的映射是否被修改，并据此决定是否需要将内存的数据更新到磁盘上。关闭文件必然会导致内存映射的数据写回磁盘，同时从进程的虚拟内存中删除。

部分操作系统只能通过特定的系统调用提供内存映射，通过标准的系统调用处理所有其它的文件 I/O 请求；有的操作系统则一律将文件 I/O 视作内存映射，例如 Solaris 系统会将标明为内存映射的文件映射到进程的地址空间中，而对于采用普通系统调用（read、open 以及 write）访问的文件，Solaris 也会做内存映射，不过目标是内核地址空间。

一个文件可以同时映射到多个进程的虚拟地址空间中以实现 数据共享 ：任何一个进程对共享虚拟内存中数据的修改都会被那些同样映射了这部分文件的进程看见（注意这里是为了实现数据共享，因此才允许多个进程修改同一页）。每个共享进程的虚拟内存表指向了物理内存的同一页。内存映射也支持写时复制，进程可以共享只读模式的文件，对于需要改动的数据，进程需要维护各自独立的副本。

其他设备的 I/O 操作也可以通过内存映射的方式：操作系统将一组内存地址专门映射到设备寄存器，对这些内存地址的读写等同于对设备寄存器的读写，即 I/O 端口。CPU 和设备之间传递数据可以通过轮询或中断。轮询方式指 CPU 不断查询控制位判断接收设备是否准备就绪；中断驱动则由接收设备通知 CPU 数据已经就绪。

内核内存分配

普通用户进程获取额外内存时是从内核维护的空闲页帧链表中获取，该链表由页替换算法更新，这些页帧往往分散在物理内存中。

内核内存的分配通常从空闲内存池获取而非从普通用户进程的内存链表获取，原因：

• 内核要为不同大小的数据结构分配内存，有些数据结构远不到一页的大小。很多操作系统的内核代码并不受分页系统控制，内核可以也必须谨慎分配内存并尽量降低碎片浪费。
• 用户进程分配的页不一定非要在连续的物理内存中，但操作系统需要和硬件交流，需要内存常驻在连续的物理内存帧中。

Buddy 系统（Buddy system）将物理上连续并且大小固定的段划分成 2 的幂（4KB、8KB、16KB等），如果请求大小不为 2 的幂，实际分配的内存大小也会是 2 的幂。例如请求 11KB 将会得到 16KB。Buddy 系统的分配通过不断切割实现，例如内存段大小 256 KB，申请 21 KB，则将内存段不断划分成两半，最终得到一个 32KB 的小段满足 21KB 请求。其优缺点如下：

• 优点：可通过合并快速形成更大的段，例如上面分配的 32KB 内存释放后可以立刻得到原始的 256KB 段
• 缺点：碎片，可能有 50% 的内存因为碎片而浪费

slab 分配 ：slab 由一个或多个 物理上 连续的页组成，高速缓存 含有 一个或多个 slab。每个内核数据结构都有一个 cache （如进程描述符 cache 只存储进程描述符对象、文件对象和信号量等以此类推），每个 cache 包含 内核数据结构的 对象实例 。 slab 算法用 cache 存储内核对象，cache 创建之初会初始化一系列空闲的内核对象，这些对象的数量和 slab 的大小有关（例如 12KB 的 slab 可存储 4 个 3KB 大小的内核对象）。一旦操作系统需要内核结构的对象，就可以直接从 cache 上获取一个空闲的并将其标注为 已使用（used） 。下面这张图需要注意的地方有，物理内存连续分配，实线（带箭头）表示包含关系，每个 cache 都存储了一类内核数据结构对象

Linux 下的 slab 有三种状态：满的（slab 中所有对象都标记为使用），空的（均为空闲）以及部分。slab 分配的分配流程如下：首先从部分空闲的 slab 分配，若没有则从空的 slab 分配，如果仍没有则从物理连续页上分配新的 slab 并将其交付给一个 cache，并从新 slab 分配空间。

其优点主要有：

• 没有因为碎片引起的内存浪费。每个内核数据结构都有与自己的结构相对应的 cache，而每个 cache 由若干个 slab 组成， 每个 slab 又可分为若干个和对象大小相等的部分 ，所以内核请求对象所获得的内存刚好和对象大小一致；
• slab 中的对象预先创建，可以直接从 cache 快速分配。因为操作系统经常分配、释放内存，使用 slab 分配能够更快地使内存请求得到响应，用完对象释放时也只需要将内核对象标记为空闲并返回给 cache。

更多方面的考虑

预调页（prepaging） ：当进程开始时，所有页都在磁盘上，每个页都需要通过页错误来调入内存。预调页同时将所需要的所有页一起调入内存，从而阻止了大量的页错误。部分操作系统如 Solaris 对小文件就采取预调页调度。实际应用中，例如对于采用工作集合模型的系统，可以为每个进程维护一个当前工作集合中的页的列表，如果进程在暂停之后需要重启时，根据这个列表使用预调页将所有工作集合中的页一次性调入内存。预调页有时效果比较好，但成本不一定小于不使用预调页时发生页错误的成本，有很多预调页调入内存的页可能没有被使用。

页大小（page size）：许多因素会影响页面大小，不存在单一的最佳页大小。页面大小总为 2 的幂，通常在2^12到2^22字节之间（4KB ~ 4MB）。页面大小的考虑主要涉及如下几点，现代操作系统倾向于使用更大的页：

• 更大的页面大小能够减少页数量，从而减小页表大小；
• 更小的页面大小能够更好的利用内存，减少碎片；
• 页读写所需要的时间：传输时间和传输量（页大小）成正比，看起来似乎小页面更好，但实际上磁盘的寻道、延迟时间远超过传输时间，因此为了最小化 I/O 时间，需要采用较大的页；
• 局部性：采用较小的页能够更精准的定位程序局部，从而降低总的 I/O 量；
• 页错误数量：页面大小过小时，页错误会触发的更加频繁，页错误会带来大量的额外开销（处理中断、保存寄存器、置换页、排队等待调页设备、更新表），为了减少页错误数量，需要较大的页。

TLB 范围（reach） ：指通过 TLB 可访问的内存量，即 TLB 能够存储的条数和页面大小的乘积。理想情况下一个进程的全部工作集合都位于 TLB 中才能够减少地址转换、查页表浪费的时间，但是对于需要使用大量内存的应用程序，TLB 大小不足以存储全部局部。增加 TLB 范围可以通过增加 TLB 条数，也可以通过增加页面大小。增加页大小会带来更大的碎片，另一种选择是使用不同大小的页（如 UltraSPARC 支持 8、64、512KB 和 4MB 的不同大小的页面），对于绝大多数程序而言 8KB 的页足够，部分其它应用程序如数据库可以利用 4MB 大小的页。注意，现代操作系统趋势是不同大小的页由操作系统而不是硬件来管理，软件管理必然也会影响性能（PowerPC 和 Pentium 用硬件管理 TLB）。

程序结构 ：用户应当对按需调页足够了解，以使程序结构更好的适应系统，例如一个页大小为 128B 的系统按行存储数组，则下面的两类代码中，上面的代码会触发 128 x 128 = 16384 次页错误，而下面的代码只会触发 128 次。程序设计语言的特性对调页也会有影响，例如 C 和 C++ 经常使用指针，指针趋向于使内存访问随机，从而导致进程的局部性变差。此外， OOP 思想设计的程序引用的局部性也较差 。

int data[128][128];
for (int i = 0; i < 128; i++)
    for (int j =0; j < 128; j++)
        data[j][i] = 0;    // 每个字节都会触发一次，共 16384 次
        
for (int i = 0; i < 128; i++)
    for (int j =0; j < 128; j++)
        data[i][j] = 0;    // 每行触发一次，共128 次

I/O interlock：某一页可能正在执行IO，需要锁定在内存中，不能被置换出去。

第九章习题拾遗

课内习题

一、虚拟存储器

选B，虚拟内存容量不受存储限制，只与逻辑空间有关系，比如32位操作系统或64位。唯一关系是存储空间少后虚拟存储器慢。

二、页面大小与缺页

会减少，上面有讲。

三、操作系统对缺页的处理

I、II、III。因为涉及页在页表的置换，所以有分配页框

四、局部性与虚拟内存

C，显然

五、系统颠簸

I，内存不够与交换区无关。

六、虚拟存储器容量

显然，$2^{32}B$。

七、虚拟地址转换

快表的目的就是加快虚拟地址转换（将两次访存变为一次）。页表常驻显然也可以。交换区跟地址转换没有关系。

八、LRU

可以知道，内存中页表是5、4、8、2，置换掉距离7最远的，是2。

5次。

6次。

九、有效访存时间

全都相关，显然。

十、段

显然，段号为2的段长为300，会越界

十一、动态分配与碎片

动态分区分配，就是连续分配。C。因为分配的空间大小会恰好多出一点内存空间，就会成为碎片。

课外习题

多级页表

假设页大小为4KB，页表每个表项占用4B，对于一个64位地址空间系统，采用多级页表至少需要多少级页表。默认字长1B

64位地址空间大小为 $2^{64}\times1B$，每个页表有 $4KB\div4B=1K$个表项。假设有 n 级页表，那么 $2^{10n+12}\geq 2^{64}$，得出 n 最小为6。

利用率类习题

请求分页存储管理系统，相关设备利用率：CPU10%，磁盘交换区99.7%，其他IO设备5%，哪些操作能提高CPU利用率？

I、增大内存容量 II、增大磁盘交换区容量 III、减少多道程序度数

IV、增加多道程序度数 V、使用更快的交换区 VI、使用更快的CPU

这种情况说明系统频繁发生缺页中断，也就是系统抖动，我们需要降低系统缺页率。显然I正确，抖动与交换区无关，减少多道程序数相当于释放了部分内存，正确。其余显然错误。故I、III。

小总结：CPU利用率高而磁盘利用率低说明系统工作正常，CPU利用率低而磁盘利用率高说明出现抖动，CPU利用率和磁盘利用率都低说明可以增加多道程序度数。

地址与空间大小

设有8页逻辑空间，每页有1024B，被映射到32块物理存储区中，求逻辑地址和物理地址的有效位。

显然逻辑地址有效位13位，3位页号，10位页内偏移，注意物理块大小与页面大小一致，所以物理空间15位。

某页式管理系统中主存128K，分成32块，块号从0到31，某作业有5块，页号为0,1,2,3,4,5，装入主存的3,8,4,6,9块中，有一逻辑地址为[3,70]，求物理地址。

页大小为4K。第三页对应第六块，也就是说前面有6整块，所以起始地址+页内偏移= $4K\times 6+70=24646$

设有一页式存储管理系统，逻辑地址空间16页，每页2048B，内存共有8个存储块。求逻辑空间位数与内存空间大小。

内存8块，一块为2K，则内存空间大小为16K。逻辑空间4位页号（物理块号）11位块内偏移共15位。

一些细节问题

• 无论采用什么样的算法，缺页次数一定不会小于引用串中不同页号的个数。
• 存储保护的目的：防止各道作业相互干扰。两种方式：防越界、权限限制
• 操作系统实现多道程序并发中代价最小的是：分区管理
• 解决主存碎片问题较好的存储器管理方式是分页管理
• 对重定位存储管理方式应该在整个系统中设置一个重定位寄存器。而不是每个程序一个。
• 产生内存抖动的主要原因是页面置换算法不合理
• 页式管理存储对用户是透明的页式存储管理系统在运行中可能改变程序位置，不能使用静态重定位。

第十章、文件系统接口

文件系统

概念、属性和操作

信息可以在多种介质上存储，为了方便使用，操作系统为不同的信息存储设备提供了统一的逻辑接口：对存储设备的各类属性加以抽象，定义了逻辑存储单元（文件），之后再将文件映射到非易失性的物理设备上。

文件是 一系列有名称的、记录在二级存储器上的信息集合 。在用户眼里，文件是逻辑外存的最小分配单元，数据必须通过文件的形式才能写入到外存，用户眼中的文件地址空间是连续的。文件根据不同的类型有一定 结构（structure） ，例如 文本文件由行（页）组成，每行又由字符组成； 源文件 由子程序和函数组成，子程序和函数又由声明、执行语句组成； 目标文件 是一系列字节序列，按目标系统链接器所能理解的方式组成； 可执行文件 为一系列可以装入程序调入内存执行的代码段。

所有文件的信息都保存在文件系统的目录结构中，目录结构（必须也是非易失性的）也保存在外存中。

文件属性（file attributes）

• 名称：文件符号名称，按人类理解方式保存

• 标识符：文件系统内标识此文件的唯一标签，通常为数字

• 类型：此字段仅对于支持多类型文件系统有效

• 位置：指向设备和设备上该文件位置的指针

• 大小：文件当前大小，也可表示文件允许的最大容量

• 保护：读、写、执行控制权限

• 时间、日期、用户标识：文件创建、上次修改、最近访问等信息，用于保护、安全以及使用记录的追踪

操作

文件属于抽象数据类型（abstract data type），文件操作的最小集合包括如下六条，这六条基本操作可以组合以实现其他文件操作：

• 创建文件：包括在文件系统中为文件找到空间并分配、在文件目录中为新文件创建条目；

• 写文件：系统要为文件维护一个写位置的指针，一旦发生写操作就需要更新写指针（写方式 fopen 返回值就是一个写指针）；

• 读文件：系统也需要为文件维护读指针，一个进程通常只对一个文件读或写，故当前操作位置（读/写指针）可作为每个进程 当前文件位置指针（current-file-position pointer） ；

• 文件内重定位（repositioning within a file）：修改文件位置指针的值（seek 操作，文件寻址），这不需要执行真正的 I/O；

• 删除文件：需要在目录中搜索给定名称文件，释放其空间并删除文件目录中的条目；

• 截短（truncate）：删除文件内容而保留属性，将文件长度设为 0 并释放空间。

操作系统维护一个 打开文件表（open-file table） ，当需要一个文件时，操作系统根据这个表的索引来指定文件，避免了每次文件操作都要搜索文件目录。有的系统会在首次引用文件时隐式地打开它，绝大多数操作系统要求程序员通过 open() 操作显示地打开文件，并将文件条目复制到打开文件表中。当文件不再使用时，进程可以关闭这个文件，操作系统会从打开文件表删除文件对应的条目。系统调用 open() 会返回一个 指向打开文件表中一个条目的指针 ，所有 I/O 操作会通过使用该指针来进行。

多个进程同时打开同一文件的情况下，操作系统通常采用 两级内部表 ：单个进程的表和整个系统的表。其中单个进程的表追踪单个进程打开的所有文件（该进程对文件的使用信息，如该进程对该文件操作的指针位置、权限等），表中的每一个条目指向整个操作系统打开文件表中相对应的一项。而操作系统的打开文件表（整个系统的表）包含着与进程无关的文件信息（文件在磁盘的位置、大小等），一旦一个文件第一次被进程打开，操作系统会在打开文件表中增加相应的条目；而 一个已经被打开的文件再次被其它进程打开时，仅仅在进程的打开文件表中增加一个指向整个系统表的相应条目 。一般系统维护的打开文件表中，每个文件会有一个文件打开计数器，用来记录多少进程打开了该文件，当计数器降到 0 时标识文件不再使用，可以从打开文件表删除。

以上，每个打开文件应当包括如下信息：

• 文件指针：这个属性对于每个进程都可能不同，因此它保存在进程各自的打开文件表中，每个进程都需要为自己打开的每个文件维护一个文件指针。
• 文件打开计数器：此属性保存在操作系统的文件打开表中，操作系统等待所有进程均不在引用某文件（计数器为 0）后才会将其条目删除。
• 文件磁盘位置：这一属性用于定位磁盘上的文件位置，保存在操作系统的打开文件表中。
• 访问权限：此属性保存在进程各自的打开文件表中，操作系统根据进程各自的访问模式决定是否允许进程的 I/O 请求。

部分操作系统提供了 文件锁 以允许一个进程锁住文件，禁止其他进程访问。文件锁可以用于多个进程共享的文件（如多个进程访问、修改的系统日志）。其中， 共享锁（shared lock） 类似 进程同步 中读者-写者问题的读者锁，它允许多个进程并发获取； 专用锁（exclusive lock） 类似写者锁，只有一个进程可以获取此锁。有的操作系统只提供专用锁。另外，操作系统可以提供 强制（mandatory） 或者 建议（advisory） 文件加锁机制，如果文件锁是强制的，那么操作系统会禁止其它进程访问一个已经加锁的文件；如果文件锁是建议的，则操作系统不会禁止。因此，对于建议加锁，程序开发者要确保进程适当的获取、释放锁。通常 Windows 系统采用强制加锁，而 UNIX 系统采用建议加锁。

类型和结构

不同的应用程序可以使用不同的扩展名来指明文件。UNIX 系统采用 幻数（magic number） 表明文件类型，这部分数据保存在文件的开始位置（不是所有的文件都具有幻数）。UNIX 也不记录文件创建程序的名称，但仍允许通过文件扩展名来确定文件内容类型。

文件类型可用于表示文件的内部结构（例如源代码文件和目标文件都有一定的结构来适应对应处理程序的要求），这些文件必须符合操作系统要求的结构。随着操作系统支持文件结构种类的增加，操作系统也会增大。很多操作系统 支持最少数量的文件结构 （包括 UNIX、MS-DOS），如 UNIX 认为每个文件是 8 位字节序列组成，操作系统不会去试着解释这些位。这样的方案提供了很高的灵活性（但是操作系统本身并不提供任何支持），应用程序必须通过自己的代码去解释输入的文件。当然操作系统必须至少支持可执行文件结构。

磁盘系统通常有明确定义的块（由扇区大小决定），所有磁盘 I/O 均按块执行。因为物理块大小通常不会和文件操作的逻辑记录长度相同，因此文件系统将若干个逻辑记录 打包（packing） 成块再执行 I/O 操作。同样，由于磁盘空间按块划分，文件最后一块的部分空间通常会被浪费，产生内部碎片，块越大内部碎片也越大。

访问方法和文件系统挂载

访问方法

顺序访问（Sequential Access） ：文件信息按顺序处理。这种访问模式最常用，如编辑器、编译器等均按此种方式访问。大量文件操作都是读写操作，两种操作都会向某一方向移动文件指针。顺序访问基于文件的磁带模型（读写/倒回），对顺序访问设备和随机访问设备都适用。

直接访问（Direct Access） ：也称 相对访问（relative access），最主要的访问方式 ，文件由固定长度的 逻辑记录（logical records） 组成，因此程序可以直接计算出文件所在的块并快速读写（磁盘允许对任意块进行随机读写）。数据库通常使用这种类型的文件。因为随机读写以块为目标，故文件操作要经过修改从而将块号作为参数。有两种方式：一是将 读下一个字节 变成 读 n ，将 写下一个字节 变成 写 n ；另一种则是仍使用 读下一个 和 写下一个 ，但是增加了 定位文件到 n 的操作。用户向操作系统提交的块号是 相对块号（relative block number） ，是相对于文件开始的索引。

不是所有的操作系统都支持顺序访问和直接访问，部分系统只允许顺序或随机访问，有的则再文件创建时指定文件是顺序还是随机访问。对于直接访问的文件，可以非常容易的模拟出顺序访问，而在顺序访问文件中模拟直接访问是非常低效的。

其他访问方式通常建立在直接访问之上，涉及文件 索引（index） ，索引包含了各个块的指针。要查找文件记录，要先搜索索引，然后根据指针直接访问文件。

文件系统挂载

文件系统在使用前必须 挂载（mount） ，中文版翻译称为 安装 。操作系统需要知道设备名称，以及这个设备在文件系统中的挂载（安装）位置，这个位置称为挂载点（mount point），通常是一个空目录。

操作系统会验证一个挂载（安装）的设备是否包含一个有效文件系统，验证流程如下：通过设备驱动程序读入设备目录，验证目录是否符合操作系统期待的格式。验证通过后操作系统会在目录结构中记录这个文件系统已经被安装在挂载点上。

目录结构

磁盘（或其他大存储设备）可以当作整体运用在一个文件系统中，但有时需要在一个磁盘上安装多种文件系统。磁盘上各个部分称为 分区（partitions） 或 片（slices） ，或称为 小型磁盘（minidisk，IBM） 。每个磁盘分区可以创建一个文件系统，这些部分可以组合起来成为更大的结构 卷（volume） ，也可以在卷上创建文件系统。下面将 存储文件系统的一大块空间作为卷 ，卷可以存放多个操作系统。包含文件系统的卷需要记录文件系统中的信息，这些信息保存在 设备目录（device directory） 或 卷表（volume table of contents） 中，它记录了卷上所有文件信息（名称、位置、大小、类型等）。

最基本的，我们能根据文件名查找目录结构找到文件属性，根据属性到磁盘能够访问文件。

目录可以视作符号表，将文件名称转换成目录条目。目录需要支持如下操作：

• 在目录中搜索文件
• 创建文件
• 删除文件
• 遍历目录
• 重命名文件
• 跟踪文件系统：定期备份整个文件系统

目录结构与文件都驻留在磁盘之中。

组织目录结构的要求（补充）：

• 高效（能够快速定位文件）
• 命名（用户要方便命名、不同用户可以有同名文件、同一文件可以有多个名称）
• 成组（可以按照文件属性划分成组）

单层结构目录（single-level directory）

所有文件保存在同一目录中，便于理解和支持。但当文件类型增加或者系统需要为多个用户提供服务时，必须保证所有文件名称唯一，而且文件名称长度有限，MS-DOS 只允许 11 个字符，UNIX 允许 255 个字符，而且无法支持相同文件有不同的名字。而且有无法分组的问题。

通用图目录（general graph）

双单层目录结构会在不同用户直接引起文件名混淆，双层结构目录中，每个用户有自己的用户文件目录（user file directory，UFD），每个 UFD 都有相似的结构，但只包含所属用户的文件。用户作业执行/用户注册时，搜索主系统的主文件目录（master file directory，MFD）来检索到用户的 UFD，这允许多个用户拥有相同名称的文件。

双层结构目录有了路径概念，能够有效地对用户隔离，而且查找效率很高，但不利于用户之间的合作和文件共享。双层结构目录等价于一棵高度为 2 的倒置树。

对于系统库等每个进程都需要的文件，双层结构目录必须将这些系统文件复制到每个 UFD 下，这导致大量空间浪费，解决方法是修改搜索步骤，在根目录下定义一个特殊的用户目录，目录中包含所有的系统文件。当进程在 UFD 查找不到需要的文件时会搜索这个特殊用户目录。给定一个文件，搜索的一系列目录称为 搜索路径（search path） 。

树状目录结构（tree-structured directories）

允许用户创建自己的子目录，系统内每个文件有唯一路径名。目录包括一组文件和子目录，目录实际也是一个按特殊方式访问的文件，文件系统中每个条目都需要一位定义其为文件（0）还是子目录（1），并且删除目录条目需要特殊的系统调用。

通常每个进程有一个当前目录， 当前目录（current directory） 包括进程当前感兴趣的多数文件，引用文件时也会先搜索当前目录。

路径名分 绝对路径名（absolute path name） 和 相对路径名（relative path name） 。绝对路径名从根开始给出路径上的目录名，一直到指定文件；相对路径名从进程的当前目录开始定义路径。

删除目录：如果目录为空可以直接删除，若目录不为空，有的系统不允许删除不为空的目录（MS-DOS，要删除一个有内容的目录就必须先清空整个目录内的文件），有的系统则提供了选择（选择是否允许删除全部子目录和文件，这样更危险，比如 rm /* -rf）。

用户除了可以访问自己的文件，还可以通过路径名访问其他用户文件。

显然，这种方式支持分组，而且访问效率较高，但是不方便共享。

无环图目录（acyclic graph）

树状结构禁止共享文件和目录，无环图允许目录含有共享子目录和文件。无环图是树状结构目录的扩展。共享目录不同于文件复制，共享情况下任何一个用户对文件做出的改动都对其它共享用户可见。

注意到下面的目录结构可以指向同一个文件。

两种方法

• 创建一种称为 链接（link） 的新目录条目，链接实际是另一个文件/目录的指针，操作系统可以通过链接保存的路径名定位真实文件（这一行为称为 解析（resolve） 。

• 每个用户都有共享文件的副本，但这些副本时刻更新着所有被共享文件的信息。但这样做会使副本和原始的文件无法区分，并且一旦有用户修改了副本/原始文件，所有其它副本都需要修改以维护一致性。

三个问题

• 一个文件被共享，因此可能会有多个绝对路径指向了同一个文件，这时对于遍历文件系统/查找文件/统计文件数量/备份文件等操作，需要解决不重复计算的问题。

• 分配给共享文件的空间何时可以删除？若用户删除文件即删除，则会留下很多悬挂链接指向不存在的文件，如果删除部分的空间被其它文件使用，这样链接又会指向其他文件的某个部分。可以在文件删除时搜索并删除这些悬挂的链接，但相对耗时；或者直到某个进程使用了某个悬挂链接时再去清理（UNIX 和 Windows 系统均不会在删除文件时删除链接，而由用户意识到原来文件已经删除）

• 删除共享文件的另一种方式是保留文件直到所有指向该文件的引用都删除为止。这样需要为每个文件维护一个引用列表，这个引用列表可能很大。因此可以用一个计数器代替引用列表。UNIX 操作系统对 硬链接（hard links，非符号链接） 采用了这种方式。

通用图目录（general graph）

无环图结构必须确保没有环，而对于无环图的共享部分，如果搜索一个共享子目录没有找到文件，就应该避免通过其它链接再次搜索这个共享子目录（浪费时间）。如果目录中甚至有环存在（例如子目录又包含了到父目录的链接），就更要避免循环搜索。

• 避免循环搜索：限制搜索时访问目录的次数。
• 删除文件：可能出现文件自我引用，这时需要垃圾收集机制确定什么时候可以删除引用。垃圾收集需要遍历整个文件系统并将所有能够访问到的空间标记，之后第二次遍历将第一遍没有标记的位置收集到空闲空间链表上。
• 如何避免无环：仅允许链接到一个没有子目录的文件；垃圾回收；每次新链接加入都运行环检测算法判断。

文件共享

多用户操作系统必须控制文件共享。系统可以默认允许一个用户访问其他用户文件，也可以要求一个用户授予文件固定的访问权限。多用户系统需要比但用户系统维护更多的文件和目录属性，现在绝大多数系统采用了文件（目录） 拥有者（owner，user） 和 组（group） 的概念，其中拥有者控制权最高，拥有者的 ID 会和文件属性一起保存。同一组的成员具有相同的权限，并只能执行拥有者具有权限的子集。

远程文件系统的实现方式包括：

• 用户通过程序（ftp）在机器之间传输文件
• 分布式文件系统（Distributed Information System） ：远程目录可以从本机直接访问
• 万维网（和 ftp 类似，基本是 ftp 的包装）：用浏览器下载文件

C/S模型（客户机-服务器模型）：服务器包含文件，客户机访问文件。服务器需要表明目录和卷的哪些文件可用，而客户机的身份需要通过网络名称/IP 或者其它标识符鉴别（这些可能被欺骗/模仿），因此客户机需要通过加密密钥向服务器进行安全验证，安全验证也会遇到很多问题，所以多数情况还是使用不太安全的验证。

故障模式（Failure Modes） ：本地文件系统可能因为某些原因出错，比如包含文件系统的磁盘老化，目录结构或者其它磁盘管理信息（统称为 元数据，metadata ）损坏等。用户或管理员的冒失也会导致文件丢失/整个目录删除等。远程文件系统因为网络因素，需要有更多的故障模式，客户机和服务器之间 需要对每一次远程请求记录信息 以在故障发生时能够恢复。类似 NFS 的协议对每个请求的信息都加以记录，因此能够很容易的从故障中恢复，但安全性较差。

一致性语义（Consistency Semantics）：描述多用户同时访问共享文件时的语义，规定了一个用户修改的数据什么时候对另一个用户可见。

• UNIX 语义（UFS）：用户对已经打开的文件进行写操作会立刻被其它同时打开这一文件的用户可见，还有一种共享模式会共享文件指针的位置，一个文件移动了文件指针会影响其他用户，文件有一个映像，这个映像允许来自不同用户的交替访问（映像是互斥资源）。
• AFS 文件系统：用户对打开文件的写操作不会立刻被其他用户可见，一旦文件关闭，对文件的修改只能被以后打开的会话所见，已经打开文件的用户无法看到这些修改。一个文件会有多个物理映像，用户允许对自己的映像进行不受限制的读写操作（没有互斥）。
• 不可修改共享文件语义：文件不可修改，即只读（文件名不能重用、文件内容不可修改）。

保护

计算机系统中保存的信息必须能够免受物理损坏（可靠性）和非法访问（保护）。对于多用户系统尤其需要某些机制。

访问类型：需要 控制访问（controlled access） 来限制可以进行的文件访问类型，访问类型包括：读、写、执行、添加、删除、列表清单（获取文件名称、属性等）。更多操作（重命名、编辑等）都是这些底层操作的组合，因此保护只需要在底层提供，高层操作涉及的底层操作如果不满足保护的要求就会被拒绝。

访问控制：根据用户身份判断能否对某个文件访问。每个文件/目录都增加一个 访问控制列表（access-control list，ACL） 来指定每个用户对这个文件/目录具有的合法的访问类型。缺点是访问控制列表会较长，并且一般事先无法知道系统的用户列表，这将导致更复杂的空间管理。

操作系统为每个文件提供了三种用户类型：拥有者、组（一组需要共享文件并且具有相同访问需求的用户集合）、其他用户。Linux 中每种类型的用户都有 rwx 三个位。

第十一章、文件系统实现

文件系统结构

• 磁盘具有如下两个特点因而成为大容量多文件存储的方便介质：

  • 可以原地重写
  • 可以直接访问磁盘上任意一块信息

• 内存和磁盘之间的 I/O 转移以 块 为单位而非字节。每块为一个或多个扇区，扇区大小从 32 ~ 4096B 不等，通常是 512B。

• 文件系统包括多层，每一层利用较低层的功能创建新功能以为更高层提供服务。

  • I/O 控制 是最底层，由 设备驱动程序（device drivers） 与中断处理系统组成。可以作为翻译器，其输入由高层命令组成， 其输出由底层的、 硬件特定的命令组成， 这些命令用于控制硬件控制器， 通过硬件控制器可以使 I/O 设备与系统其他部分相连。 设备驱动程序通常在 I/O 控制器的特定位置写入特定位格式来通知控制器在什么位置采取什么动作。设备驱动程序和 I/O 结构将在第 13 章中讨论。

  • 基本文件系统（basic file system） 主要任务是向正确的设备驱动程序发送指令，从而执行对磁盘上的物理块的读写命令，同时会将这个IO的进程阻塞。其每个块由它的磁盘地址标识（驱动器 1，柱面 73，磁道 3，扇区 10）。

  • 文件组织模块（file-organization module） 知道文件和它的逻辑块、物理块。每个文件的逻辑块按从0或1到N来编号， 而包含数据的物理块并不与逻辑号匹配， 因此需要通过翻译来定位块。因为文件组织模块知道文件类型和位置，因此可以将逻辑块地址转换成基本文件系统用的物理块地址。它也包括 空闲空间管理器 用来追踪未分配的块。

  • 逻辑文件系统（logical file system） 管理元数据，元数据包括文件系统的全部结构数据而不包括文件的具体内容。逻辑文件系统为文件组织模块提供所需的信息，通过 文件控制块（file-control block，FCB） 来维护文件结构，同时也负责保护和安全。

  

• 目前多数操作系统都支持多个文件系统，UNIX 使用 UNIX文件系统（UFS），基于伯克利快速文件系统（FFS）。标准的 Linux 文件系统是 可扩展文件系统（extended file system） ，常见版本有 ext2 和 ext3。

实现

基本结构

磁盘上的文件系统涉及如下一些结构：

• （每个卷的）引导控制块（boot control block） ：从这个卷引导操作系统所需要的信息，如果这个卷没有安装操作系统则这一块内容为空。它通常是卷的第一块，UFS 称之为 引导块（boot block） ，NTFS 系统称之为 分区引导扇区（partition boot sector） 。
• （每个卷的）卷控制块（volume control block）：包括卷或分区的详细信息，如分区块数、块大小、空闲块数量和指针、空闲 FCB 的数量和指针等。UFS 称之为 超级块（superblock） ，在 NTFS 中存储在 主控文件表（Master File Table）。主控文件表采用关系型数据库，每个文件占据一行。
• 每个文件的 FCB 包含文件的详细信息（文件权限、拥有者、大小、位置）等，UFS 称之为 索引节点（inode） 。
• 每个文件系统的目录结构，这些目录结构用于组织文件。UFS 中目录结构包括文件名和相关的索引节点号，NTFS 则保存在主控文件表中。

内存内信息用于文件系统管理，可以通过缓存来提高性能。这部分数据在文件系统挂载（安装）的时候被加载，文件系统卸载的时候丢弃，可能包括：

• 内存中的安装表，含有所有已安装卷的信息
• 内存中的目录结构缓存，保存最近访问过的目录信息
• 系统范围内的打开文件表 ，在上一章介绍过，包括每个打开文件的 FCB 副本和其它信息
• 单个进程的打开文件表 ，每个条目包括指向系统范围内打开文件表的条目的指针以及与进程相关的其它文件信息

打开文件表的索引有多种名称，UFS 称之为 文件描述符（file descriptor） ，Windows 称之为 文件句柄（file handle） ，只要文件没有关闭，所有对文件的操作都是通过打开文件表执行的。

文件的打开与读取函数 open()、read()的流程

open()：我们提供文件名（路径），到内存中缓存的目录结构（就是文件名与FCB的对应关系）中查找，如果找不到才会到磁盘的目录结构查找，找到后，根据查到的目录结构表项查找FCB，找到后会将FCB复制到系统的打开目录表（如果已经打开，即在打开目录表中已经存在则不复制），然后将进程的打开目录表的表项（一个指针）指向这个FCB的地址，返回该表项在表内的偏移量（下标）。

read()：我们根据index去查找到FCB，根据FCB就可以算出块在硬盘上的位置（逻辑块->物理块）。

分区和挂载

一个磁盘可以分成多个分区，一个卷也可能横跨多个磁盘上的多个分区（RAID 的一种形式）。

没有文件系统的分区称作 生（raw） 磁盘，含有文件系统的分区称为 熟（cooked） 的。生磁盘通常用于没有合适的文件系统可以使用的地方，例如 UNIX 的交换空间，或者有的数据库使用生磁盘并将其格式化来满足自己的需求。

引导信息可以包含在多个分区中，通常是一组有序块，并作为镜像文件读入内存。镜像文件会按照预先指定的位置开始执行，它除了可以启动一个特定的操作系统，还可以支持 双引导（dual-booted） ，即启动加载器知道有哪些操作系统、文件系统位于引导区，并可以引导磁盘上不同分区的不同类型的操作系统。

根分区（root partition） 包括操作系统内核以及其它系统文件，它们在引导时装载到内存中，其它卷会根据操作系统的设定，要么在引导时自动装入，要么通过用户手动装入。当有一个新设备挂载（安装）时，操作系统会验证设备上的文件系统是否有效，并根据需要自动/手动纠正。验证通过后，操作系统会在内存中的 挂载表/装入表（mount table） 中标注该文件系统已经装入，并且存储与此文件系统有关的信息。

虚拟文件系统（Virtual File System，VFS）是文件系统接口和文件系统之间的一层，它的目的有：

• 定义一个 VFS 接口将文件系统的通用操作和具体实现划分，多个 VFS 接口的实现能够在同一台机器共存，因此它允许访问安装在本地的多种类型的文件系统；
• VFS 提供了在网络上唯一标识一个文件的机制。它基于 vnode 文件表示结构（包括一个唯一的数值标识符，它能够表明位于整个网络范围内的唯一文件，例如 UNIX 的索引节点 inode 在文件系统内是唯一的）。

目录实现

线性列表（linear list） 是实现目录最简单的方法，运行非常低效。查找文件需要线性搜索，排序列表可以二分搜索，但排序的需求使文件创建/删除复杂化，它的优点在于可直接生成排序目录信息，可用 B 树实现。

哈希表（hash table） ：在线性列表存储目录之上使用哈希表，根据文件名哈希出一个指向线性列表中元素的指针，需要一些措施避免 冲突（collision） 。其困难在于，如果使用固定大小的哈希表，当条目超出哈希表容量时需要扩充哈希表大小，并且设计新的哈希函数将文件名映射到新的范围内。可以使用 chained-overflow 哈希表，使表中元素为一个链表而非单个记录。虽然冲突将使每个链表长度较大，查找可能变慢，但仍比线性搜索快得多。

分配方法

连续分配

连续分配（contiguous allocation） 要求每个文件在磁盘上占据连续的块。磁盘地址有一个线性序列，如果只有一个作业按照这个序列的顺序访问磁盘，在访问了块 b 后访问块 b+1 就无需移动磁头，即使需要移动磁头也只需要移动一个磁道（从一个柱面的最后扇区到下个柱面第一扇区）。因此， 访问连续分配文件所需的寻道数最小，即使确实需要寻道，所花费的寻道时间也最小 。在文件连续分配中，一个文件的目录条目包括文件占有的第一个块的地址，以及该文件分配的块的数量（分配区域的长度）。

连续分配文件访问非常容易，既可以顺序访问也可以随机访问。它也存在问题，例如如何为新文件寻找空间，这个问题可看作内存管理中 动态存储分配 问题的一个具体应用，即如何从一个空闲的孔列表中寻找一个满足大小为 n 的空间，常用首次适应和最佳适应。但无论如何动态存储分配会有外部碎片问题。

连续分配方案的另一个问题是需要确定文件需要多少空间，这个知识是无法预知的。如果为一个文件分配的空间过小则文件可能无法原地扩展文件，这时要么终止用户程序并通知用户必须分配更多空间才能运行（这样用户就会过高的预估所需的磁盘空间造成浪费），要么找一个更大的孔，将文件复制到新空间，释放旧空间，但这比较耗时。

修正的连续分配方案：开始时为文件分配一块连续空间，一旦空间不够，另一块称为 扩展（extent） 的 连续空间 就会被分配给文件。这种情况下，文件块的位置就需要通过开始块地址、块数、指向下一个扩展的指针三项来确定。如果扩展太大，内部碎片会变得严重；随着扩展的分配、删除，外部碎片也将变得严重。

链接分配

链接分配（linked allocation） 解决了连续分配的全部问题。链接分配中，每个文件由分布在磁盘上各个位置的多个磁盘块组成，文件目录条目记录了一个文件第一块的指针和最后一块的指针。每一块都会有一个指向下一块的指针，用户无法使用存储这些指针的空间（例如一块有 512B，磁盘地址为 4B，则用户只可用 508B）。

（图里块中的数字有问题）

链接分配对于创建/读/写文件的操作如下：

• 创建新文件时只要简单的在目录中增加一个新条目，条目中有指向文件第一块的指针，初始化为 nil 以表明这是空文件，大小字段也是 0。
• 写文件时通过空闲空间管理器寻找一个空闲块，这个块会被写入数据、链接到文件最后一个块的尾部，同时要更新这个文件在目录中条目的记录值（大小、最后一个块的地址）。
• 读文件通过条目中存储的第一个块的地址，逐个向后寻找。

链接分配的缺点在于：

• 只能用于文件的顺序访问，要找到文件的第 i 块必须要从第一块开始寻找，每次访问都需要读磁盘，这还需要涉及磁盘寻道的延迟。因此 链接分配无法有效支持文件直接访问 。
• 指针需要空间，每一块都有一定空间被指针占用。这个问题的解决方法是将多个块组成 簇（cluster） ，按簇而不是块来分配（如一个簇有 4 块）。这样指针占用的磁盘空间百分比会下降，但增加了内部碎片。簇可以改善多数算法中的磁盘访问时间，因此在绝大多数操作系统中得到应用。
• 可靠性：文件通过指针链接，一旦有一个指针丢失/损坏，整个文件都将崩溃。一个逃避性的解决方案是采用双向链表，或者给每个块存上文件名和相对块数（相对第一块是第几块），但这又增加了过多的额外开销。

链接分配方法的一个变种是文件分配表（file-allocation table，FAT），它被应用于 MS-DOS 和 OS/2 操作系统。每个卷的开始部分存储文件分配表，卷内的每一块都在表中占有一项，这个表可以通过块号码索引，表中存储的值是这一块指向的下一块块号。

文件在目录中的条目只含有文件第一块的块号，访问文件时按照 FAT 表中存储的链接关系一直向下寻找，直到最后一块（最后一块在 FAT 表中标记为一个特殊的文件结束值，可以根据这个值判断是否为最后一块）。

要分配一个新的块，只需要在 FAT 表中找到第一个值为 0（值为 0 表示一个块没有被使用）的块，用新块的地址替换掉此前最后一块的文件结束值，并且用文件结束值替换 FAT 表中的 0。

FAT 需要采用缓存才能提高效率，否则可能导致大量的磁头寻道时间：磁头要移动到卷的开头读入 FAT 以获得块的位置，然后才能移动到块本身。最坏情况下每块的读取都要移动两次。但它的优点在于改善了随机访问时间， 因为 FAT 的存在，操作系统可以快速找到文件任意一块的位置 。

索引分配

如果不采用 FAT，链接分配就无法有效支持直接访问，因为块指针散布在整个磁盘，必须顺序读取。 索引分配（indexed allocation） 把所有指针放到一起，通过 索引块（index block） 解决此问题。

每个文件都有自己的索引块，它是一个磁盘块地址的数组。索引块的第 i 个条目代表文件的第 i 个块，条目中含有索引块的磁盘地址。要读取第 i 块只需要通过索引块第 i 个条目存储的指针来访问（类似第八章分页）。

• 创建文件：索引块中所有指针设为 nil（图中-1）。
• 第一次写入第 i 块：从空闲空间管理器获取一个空闲块，将数据写入块，并将块地址写到索引块的第 i 个条目中

索引分配支持直接访问且没有外部碎片问题，但索引分配会浪费空间 ：如果一个文件只有两块长，链接分配只需要每块浪费一个指针，而索引分配需要为这个只有两块的文件创建一个完整的索引块，这个索引块里只有两个指针被使用到。

索引块的大小需要经过仔细考量：每个文件都有一个索引块，索引块太大会造成浪费，太小又不足以满足大文件存储需求。针对这一问题的处理机制有如下几点：

• 链接方案（Linked scheme） ：一个索引块就是一个磁盘块。它本身能够直接读写，当遇到大文件存储时可以将多个索引块链接。例如一个索引块可以包含一个头部（头部包含文件名）以及 100 个磁盘块的地址。索引块的最后一个存储单元存储着指向下一个索引块的地址如果是小文件则这个指针为 nil，如果是大文件则指向了另一个索引块。

  

• 多层索引（Multilevel index） ：设置两层索引块，第一层指向第二层，第二层指向文件块。根据最大文件大小的不同，可以继续到第三/四层。对于块大小为 4KB 的情况，可以在一个索引块里装入 1024 个 4B 指针，两层索引就可以容纳 1048 576 个数据块，即最大文件为 4GB。

  

• 组合方案（Combined scheme） ：在 UFS 中使用了这种方案。将索引块的前 15 个指针存在文件的 inode 里，这 15 个指针中：前 12 个直接指向了数据块，这样不超过 12 块的文件就不需要其它索引块；后 3 个指针分别是一级间接块、二级间接块、三级间接块指针。这种方法允许一个文件的块数超过 4B 文件指针能访问的空间。许多 UNIX 系统支持 64 位文件指针，这时允许文件/文件系统达到数 T 字节。

  

  （前面的蓝色的值代表一些文件属性）

索引分配方案和链接分配方案在性能上都有欠缺，虽然索引块能够缓存在内存里，但数据块会分布到整个分区中。

性能

连续分配对于任意类型的访问都只需要访问一次，链接分配可以将下一块的地址放到内存中并能直接读取，但对于直接访问需要读多次磁盘。所以有些系统通过使用连续分配支持文件直接访问，通过链接分配支持顺序访问。这种系统在创建文件时就要指明文件的类型（顺序访问还是直接访问），如果是直接访问还必须说明最大文件大小。

索引分配非常复杂。如果索引块已在内存中则可以直接访问，但将索引块保存在内存中需要非常大的空间。尤其是多级索引，对于一个大文件来说，如果要访问文件末尾部分的数据，可能需要将所有索引块读入内存才能读到需要的数据库。所以索引分配的性能依赖于索引结构、文件大小和所需要的块的位置。

有的系统把连续分配和索引分配结合，对于小文件（3、4块大小的）采用连续分配，大文件切换到索引分配。因为文件系统中大多数文件较小，所以小文件连续分配效率较高，平均性能较好。

由于 CPU 和磁盘速度不等，花费数千条 CPU 指令来节省一些磁头移动都是值得的，随着时间推移，这种不等程度还会增加。

空闲空间管理

系统需要维护 空闲空间链表（free-space list） 以记录空闲磁盘空间，创建文件时会从空闲空间链表分配，删除文件时磁盘空间会加回到空闲空间链表上（称之为链表但不一定表现为链表）。

位向量

将空闲空间用 位图（bit map） 或 位向量（bit vector） 表示，每块用一位说明是否为空闲，1 表示空闲，0 表示已经分配。

位图上方的值代表块号。

此方式查找磁盘上第 1 个空闲块和 n 个连续空闲块时简单高效：

• 按顺序检查位图中的每个字是否为 0 即可确定对应的块是否已经全部分配，第一个非 0 的字中，第一个 1 位偏移就对应着第一个空闲块；
• 连续 n 个空闲块只需要判断是否有连续 [n / 字的位数] 个字均为最大值（如一个字就是一个字节时，只要连续有 [n / 8] 个字节全为 255 就说明这部分块都空闲）。

除非整个位向量都能保存在内存中，否则位向量的效率不高。对于小磁盘，位向量的大小可以接受，但对于大磁盘而言（如 40GB，每块 1KB）就需要超过 5MB 空间存储位图。

这种方式更容易分配连续的块，这会使得访问文件的速度加快。但显然，缺点就是占用空间。

链表和组

将所有空闲磁盘块用 链表（Linked List） 链接，将指向第一个空闲块的指针放在磁盘的一个特殊位置，同时也缓存到内存里。每一块空闲块中包含了指向下一个空闲磁盘块的指针。

此方案效率不高，要遍历整个空闲块列表需要从磁盘读出每一块，这要耗费大量 I/O 时间。不过通常操作系统只需要获得一个空闲块以提供给文件，因此一般只需要分配空闲表的第一块。而且不方便分配连续的块，因为随着空间的利用和回收，链表中的值不一定是有序的，导致在访问文件时效率会降低。

当然其优点是不需要额外空间，不会造成空间浪费。

组（grouping） 是对空闲链表的改进：将 n 个空闲块的地址存在第一个空闲块里，前 n-1 个地址都指向真正的空闲块， 最后一个地址指向了另一个包含另外 n 个空闲块的块地址 。

计数

通常会有多个连续的块需要同时分配、释放，尤其是采用了连续分配或簇的情况下。因此可以不记录 n 个空闲块地址，而是记录连续多块空闲块的第一块的地址，以及连续的空闲块的数量。这样空闲空间表的每个条目包含了第一个空闲块地址和连续空闲块数量，虽然每个条目占用的空间增长了，但表的总长度会缩短（连续空闲块的数量往往大于 1）。

UNIX 成组链接（补充）

将文件存储设备中的所有的空闲块 从后向前 按 50 块为一组进行划分，每组的第一块用于存放 前一组 的总块数和每块的块号，因为第一组前面已经没有其他组存在，所以第一组实际有 49 块。因为存储空间不一定正好是 50 的整数倍，所以最后一组可能不足 50 块。因为最后一组后面没有其他组，所以最后一组的总块数和每块块号的信息存放到管理文件存储设备的文件资源表中。

操作系统启动时将文件资源表复制到内存，此时文件资源表中包含了最后一组的空闲块总数以及空闲块的块号。操作系统还会设置一个用于空闲块分配、回收的堆栈，堆栈存储着空闲块的块号，栈指针 ptr 的初值等于最后一组的空闲块的总块数。

成组链接分配方法：申请者请求获得 n 块空闲块，操作系统将按照先进先出的原则，将栈顶指向的块号分配给请求者，同时 ptr 自减。重复此操作直到 n 块分配完毕，或者堆栈中只剩下最后一个空闲块的块号（此块实际存储的是下一组的空闲块块数和各块块号）。当堆栈只剩下最后一个空闲块的块号时：

• 从堆栈中弹出该块的块号，系统启动 I/O 设备，将该块存放的内容读入内存（即将下一组空闲块号和总块数读入空闲资源表），并设置 ptr 为下一组的空闲块数
• 文件存储设备的最后一个空闲块中设置有尾部标识，表示空闲块已经分配完毕

成组链接回收方法：用户删除某个文件时，ptr 自增并将空闲块号入栈。若 ptr 为 50 则表明当前已经凑足一组，该组回收结束。

• 如果还有空闲物理块 F 需要回收，则将块 F 回收，并且启动设备 I/O，把栈中记录的 50 个块号和块数（50）写入到块 F 中。设置 ptr 为 1，将块 F 的块号入栈，开始新的一组空闲块回收。
• 对空闲块的分配和回收操作必须互斥进行（栈操作要互斥）。

第十二章、大容量存储器结构

概览

磁盘（magnetic disk） 是现代计算机系统使用的大容量外存。磁盘片为扁平原盘，两面均涂有磁质材料，读写头在磁盘片的表面飞行，磁头和 磁臂（disk arm） 相连 ，磁臂将每个盘面两侧的全部磁头作为一个整体一起移动。磁盘片表面被逻辑划分为圆形 磁道（track） ，一圈磁道被进一步划分为 扇区（sector） 。同一圈磁道在不同盘片的集合组成了 柱面（cylinder） 。

硬盘分区其实就是柱面的划分。

多数驱动器每秒可旋转 60~200 圈，磁盘速度由 传输速率（transfer rate） 和 定位时间（positioning time） 决定。其中传输速率指驱动器和计算机之间的数据传输速率；定位时间又称 随机访问时间（random access time） ，包括 寻道时间（seek time） （移动磁臂到所需柱面所需的时间） 和 旋转等待时间（rotational latency） （等待磁盘驱动器将所需扇区旋转到磁头下的时间）。寻道时间和旋转等待时间通常为几毫秒，典型的磁盘能够以几兆每秒的速率传输。

磁盘的传输速率总是低于有效的传输速率。 磁盘表现的传输速率是磁盘头从磁性介质读取比特的速率 ，这不同于给操作系统传输块的速率（与操作系统之间传输的速率才是决定磁盘速度的传输速率）。

磁头飞行在盘片数微米上的空气层中，一旦磁头和盘片接触就会损坏磁盘表面，这称为 磁头碰撞（head crash） 。磁头碰撞不能修复，整个磁盘必须替换。

磁盘可移动或更换。 软盘（floppy disk） 是便宜的可移动磁盘，存储容量在 1.44MB 左右。

磁盘驱动器通过 I/O总线 和计算机相连，可用的总线包括 EIDE（enhanced integrated drive electronics） 、 ATA（advanced technology attachment） 和 串行 ATA（serial ATA，SATA） 、 USB（universal serial bus） 、 FC（fiber channel） 和 SCSI 总线。

控制器（controller） 是一个特殊处理器，用于执行总线上的数据传输。其中， 主机（host） 控制器是计算机上位于总线末端的控制器，而 磁盘（disk） 控制器位于磁盘驱动器内。

磁带（magnetic tape） 是早期次级存储介质，但访问速度过慢。典型磁带可以存储 20~200GB。

火线（FireWire） 指一个接口，这个接口可以将外部设备如磁盘驱动器、DVD 驱动器等连接到计算机系统。

磁盘结构和附属

现代磁盘驱动器可以看作一个一维的 逻辑块（logical blocks） 数组，逻辑块是最小的传输单位，通常为 512B，部分磁盘可以通过 低级格式化（low-level formatted） 来选择不同的逻辑块大小。

一维逻辑块数组按顺序映射到磁盘的扇区，扇区 0 是最外面柱面的第一个磁道的第一个扇区，这个映射关系先按磁道内的扇区顺序，之后按这一柱面上各个盘面的磁道顺序，最后按照从外向内的柱面顺序排序。通过这种映射，可以将逻辑块号转换为磁盘内的柱面号、柱面内的磁道号以及磁道内的扇区号。这种转换有一些问题，原因在于：

• 多数磁盘有一些缺陷扇区，这时候映射需要用其它空闲扇区替代这些缺陷扇区

• 有些磁盘每个磁道上的扇区数不是常量

对于使用 常量线性速度（constant linear velocity，CLV） 的介质，每个磁道的位密度均匀，离盘片中心更远的磁道的长度更长，容纳的扇区也就更多，这样从内向外的磁道所包含的扇区数就会逐渐增多，外部磁道的扇区数通常比内部磁道的扇区数多 40%。这时，盘片驱动器在磁头的不同位置的旋转速度将不同，磁头越靠近盘片中心则旋转速度越快。

硬盘中通常采用 恒定圆角速度（constant angular velocity，CAV） ，这时内磁道到外磁道的位密度会不断降低，以使磁盘驱动器转速恒定的情况下也能维持恒定的数据率。

计算机访问磁盘可通过 I/O 端口，或称 主机附属存储（host-attached storage） ，这一般在小系统中采用；或者通过分布式文件系统的远程主机，这称为 网络附属存储（network-attached storage） 。

磁盘调度

磁盘调度是调度进程对磁盘的访问（不是调度磁盘）

强调磁盘的几个参数：

• 两个主要的耗时操作：

  • 寻道时间 ：磁臂旋转以使磁头位于目标扇区所属的柱面上的时间
  • 旋转延迟 ：磁盘驱动器将盘片旋转以使目标扇区转动到磁头下的时间

• 磁盘带宽 ： 传输的总字节数除以从服务请求开始到传递结束的总时间。可以通过磁盘 I/O 请求调度来排列访问顺序，从而提高访问速度和带宽。

一来来说寻道时间与寻道距离（柱面之间来回移动的距离）成正比，旋转延迟一般是不可改变的，所以调度的目标其实就是减小寻道距离

进程需要磁盘 I/O 操作时会向操作系统发出系统调用，这个调用请求包括：

• 操作类型：输入/输出
• 本次传输的磁盘地址、内存地址、扇区数

多个进程的多道程序系统，磁盘队列可能有多个待处理请求，此时操作系统需对磁盘请求进行调度，包括 FCFS、SSTF、SCAN、C-SCAN、LOOK、C-LOOK。

调度案例样例

磁盘200个柱面，分别为0~199，初始时磁头在53，调度队列为98, 183, 37, 122, 14, 124, 65, 67

FCFS 调度

先来先服务算法，此算法比较公平但无法提供最快的服务。

移动了距离为640。

SSTF 调度

最短寻道时间优先法（shortest-seek-time-first，SSTF） 会先处理最靠近当前磁头位置的请求，即选择距离当前磁头位置所需寻道时间最短的请求来处理。

本质上是最短作业优先（SJF）调度，但与 SJF 类似，它可能导致一些请求得不到服务，如果待处理请求队列比较长，很有可能某个请求会产生饥饿。SSTF 调度相比 FCFS 调度有很大改善，但仍不是最优的。

移动距离236。

SCAN 和 C-SCAN 调度

SCAN 算法有时称为 电梯算法（elevator algorithm） ，磁臂会从磁盘的一端向另一端移动（按一维逻辑块数组的顺序），当磁头移动过每个柱面时就会处理这个柱面的服务请求。到达另一端后磁头会反向继续移动，如此往返。

一般来说读写头会先移动到磁盘一端最开始的位置，处理经过的请求，然后移动到磁盘另一端。

如果一个请求刚好在磁头移动到请求位置之前加入磁盘请求队列，则它会马上得到服务。如果一个请求刚好在磁头移动过请求位置后加入队列，则它需要等待磁头到达另一端并调转方向、返回后才能得到服务。

存在的一个问题就是会移动到头，显然是不必要的。

移动距离208.

C-SCAN（circular SCAN） 调度和 SCAN 类似，但当磁头从磁盘的 0 号扇区移动到磁盘的最后一个扇区（或者柱面）后不会调转方向，而是从 0 号重新开始扫描整个磁盘。

相对于SCAN，C-SCAN提供更统一的等待时间。

这两种算法都不会导致饥饿现象。

LOOK 和 C-LOOK 调度

LOOK 和 SCAN 算法类似，磁头向一个方向移动，但不会一直移动到最后一个柱面才折返，而是处理完这个方向上最后一个请求后就掉头。

C-LOOK 和 C-SCAN 类似，处理完最后一个请求后就会将磁头恢复到磁盘一端重新开始按固定顺序扫描。

算法选择

磁盘服务请求很大程度上受文件分配方法影响：一个连续分配文件会产生几个磁盘上相近位置的请求，而链接/索引文件会产生很多分散在磁盘上的块。

目录和索引块在磁盘上的位置也很重要，如果目录位于第一个柱面而文件数据位于最后一个柱面，则磁头需要横跨整个磁盘宽度。如果目录在中央柱面，则磁头只需要移动不到一半的磁盘宽度。

磁盘调度算法应该作为一个操作系统的独立模块，在必要的时候模块应该可以被替换。SSTF 或 LOOK 算法是比较合理的默认算法。而SCAN与C-SCAN在IO负载较高时性能更出色。

调度算法只考虑了寻道距离。旋转延迟几乎和寻道时间一样，但操作系统无法通过调度改善旋转延迟，因为现代磁盘并不透露逻辑块的物理位置。磁盘制造商会在磁盘控制器中加入磁盘调度算法缓解寻道时间和旋转延迟问题。

因为操作系统对请求服务的顺序有更多限制（如按需分页的 I/O 请求比普通应用程序的 I/O 请求优先级高），因此操作系统不能完全将磁盘调度交给磁盘控制器，而是选择自己的磁盘调度算法，将请求按调度好的顺序、按批次交给磁盘控制器。

磁盘管理

磁盘格式化

新磁盘仅仅是含有磁性记录材料的盘片，需要通过 低级格式化（物理格式化，physical formatting） 分为扇区。

低级格式化将磁盘的每个扇区按特定的数据结构填充数据，扇区的数据结构包括头、数据区（通常 512B）和尾部。头部和尾部包含磁盘控制器需要的信息，如扇区号码和 纠错代码（error-correcting code，ECC） 。

操作系统需要将自己的数据结构记录到磁盘上，首先需要将磁盘分为一个或多个柱面组成的分区，操作系统可以将每个分区视作独立的磁盘。分区之后，操作系统需要通过 逻辑格式化（logical formatting） 来创建文件系统，操作系统会将初始的文件系统数据结构存储到磁盘上。这些数据结构包括那些仍空闲的和已经分配的空间（如分配给 FAT 或者 inode）和一个初始为空的目录。（相当于建立文件系统）

为提高效率，多数操作系统将多个块集中到一大块，称为 簇（cluster） 。磁盘 I/O 通过块完成，文件系统 I/O 通过簇完成。

引导块

计算机开始运行时需要初始化（自举，bootstrap）程序，它负责初始化系统所需的各个方面，并找到磁盘上的操作系统内核，将其装入内存开始执行。

自举程序保存在 只读存储器（ROM） 中，其位置固定，并且只读（不受病毒影响），但改变自举代码就需要改变 ROM 硬件芯片。因此操作系统只在启动 ROM 中保留一个非常小的自举程序，这个小自举程序会从磁盘上调入更完整的自举程序。更完整的自举程序可以修改，并且保存在磁盘的启动块上。

磁盘的 启动块（boot blocks） 位于磁盘的固定位置，拥有启动分区的磁盘称为 启动磁盘（boot disk） 或者 系统磁盘（system disk） 。启动 ROM 中的代码将启动块中的代码装入内存并执行，启动块中的完整自举程序会从 非固定位置 装入整个操作系统并执行。

以 Windows 2000 为例，其启动代码放置在硬盘的第一个扇区，被称为 主引导记录（master boot record，MBR） ，MRB 中除了包含自举程序的代码，还包含硬盘分区列表和系统引导分区的具体标识。Win 2000 将硬盘分成多个分区，其中一个为 引导分区（boot partition） ，该分区包括了操作系统和设备驱动程序。MBR 确定引导分区的位置后就会读取引导分区的第一个扇区（引导扇区，boot sector）并继续剩余的启动过程。

坏块

磁盘有移动部件且容错能力小，容易出问题。多数磁盘从工厂出来就有 坏块（bad blocks） 。坏块中的数据会丢失。

简单磁盘可手动处理坏扇区。如 MS-DOS 的 format 命令执行逻辑格式化时，会扫描磁盘查找坏扇区，如果找到就在 FAT 的条目中写上特殊值以标明该块已损毁。

复杂磁盘（高端 PC、WorkStation 或服务器上的 SCSI 磁盘）需要控制器维护一个磁盘坏块链表，这个链表在磁盘出厂前进行低级格式化时就已经初始化，并在磁盘使用过程中不断更新。低级格式化会将一些块备用，操作系统无法看到这些块。当坏块出现时，控制器会用备用块替换这些坏块。这种方案称为 扇区备用（sector sparing） 或 转寄（forwarding） 。

典型的坏块区事务处理：

• 操作系统访问逻辑块 87
• 控制器计算该块的 ECC 值，发现该块已经损坏，因此将结果通知操作系统
• 下次操作系统重启时运行特殊程序告知 SCSI 控制器用备用块替代坏块
• 之后的每次系统访问逻辑块 87，请求都会被转换成替代后的备用块地址

扇区备用的另一方案是 扇区滑动（sector slipping） ：假定逻辑块 17 损坏，第一个可用的备用块是扇区 203，则将 18 ~ 202 扇区向下滑动一个扇区，变为 19 ~ 203 扇区。这样原本的扇区 18 变为空，用来替换扇区 17。

交换区管理

交换空间管理是操作系统的另一底层任务。虚拟内存使用磁盘空间作为内存的扩充。由于磁盘访问比内存访间要慢很多，所以使用交换空间会严重影响系统性能。交换空间设计和实现的主要目的是为虚拟内存提供最佳吞吐量。

注意，对交换空间数擞的高估要比低估更为安全。这是因为如果系统使用完了交换空间，那么可能会中断进程或使整个系统死机。高估只是浪费了 些空间（本可用于存储文件），但并没有造成什么损害。

交换空间可有两个位置：交换空间在普通文件系统上加以创建，或者是在 个独立的磁盘分区上进行。

如果交换空间是文件系统内的一个简单大文件，那么普通文件系统程序就可用来创建它、命名它并为它分配空间。这种方式实现简单但是效率较低。遍历目录结构和磁盘分配数据结构需要时间，可能多次访问磁盘。

另外一种方法是，交换空间可以创建在独立的生(raw)磁盘分区上。这里不需要文件系统和目录结构，只需要一个独立交换空间存储管理器以分配和释放块。这种管理器可使用适当算法以优化速度，而不是优化存储效率，因为交换空间比文件系统访问更频繁。内部碎片可能会增加，但还是可以接受的，这是因为交换空间内的数据的存储时间通常要比文件系统的文件的存储时间短很多。交换空间在启动的时候会初始化，因此任何碎片存在 的时间都很短。这种方法在磁盘分区时创建一定童的交换空间。增加更多交换空间可能需要重新进行磁盘分区（可能涉及移动或删除文件系统，以及利用备份以恢复文件系统），或在其他地方增加另外交换空间。

Linux实例

Linux允许建立一个或多个交换区。交换区可以是普通文件系统的交换文件或原始交换分区。每个交换区包含一系列的4KB的页槽(page slot)（与页面大小相等），用于存储交换页。每个交换区对应一个交换映射(swap map)一整数计数器数组，每个数对应于交换区的页槽。如果计数器值为0，对应页槽可用。值大于0表示页槽被交换页占据。计数器的值表示交换页的映射数目。 例如，值3表示交换页映射到3个不同进程（例如交换页存储3个进程的共享内存区）。

RAID

如何提高可靠性：冗余校验

如何提高读写性能：并行读写。（如原本用一个磁盘读写十个块，现在可以用十个硬盘并行读写十个块）

第十二章习题拾遗

第十三章、I/O 输入系统

I/O 硬件

设备驱动程序（device drivers） 为 I/O 子系统提供了统一设备的访问接口。

设备和计算机的通信通过 端口（port） ，一组被一个/多个设备共同使用的线称为 总线（bus） 。总线是一组线和一组严格定义的描述在线上传输信息的协议。 链环（daisy chaine） 形容的是多个设备相连，最终设备通过端口连接到计算机上的模式。链环常常按总线方式工作，一个典型的 PC 总线结构如下图。

上图中包含一个 PCI 总线 （最常用的 PC 系统总线）用于连接 CPU 和内存子系统/快速设备， 扩展总线（expansion bus） 用于连接串/并行端口和相对慢的设备（键盘）。

控制器（controller） 是用来操作端口、总线或者设备的一组电子器件，它的复杂程度和传输协议有关，如串行端口控制器比较简单，而 SCSI 总线控制器常实现为一个和计算机相连的独立的 主机适配器（host adapter） ，这个适配器会有处理器、微码以及一定的私有内存，从而能够处理 SCSI 协议信息。

控制器有一个/多个用于数据和控制信号的寄存器， 处理器通过读写这些寄存器来实现与控制器的通信 。这种通信的可以通过特殊的 I/O 指令向指定的 I/O 端口地址传输一个字节/字，也可以通过 内存映射 I/O 模式（在 虚拟内存 中介绍过），处理器能够通过标准数据传输指令完成对控制器的读写。部分系统同时采用这两种方式，例如图像控制器有 I/O 端口来完成基本控制操作，还有一个较大的内存映射区域来支持屏幕内容的接收和生成。

I/O 端口通常有 4 种寄存器，寄存器通常为 1 ~ 4B：状态寄存器、控制寄存器、数据输入寄存器和数据输出寄存器。有的控制器有 FIFO 芯片从而可以保留多个输入/输出数据。上述四种寄存器的主要功能有：

• 主机从 数据输入寄存器 读出数据
• 主机向 数据输出寄存器 写入数据
• 主机可从 状态寄存器 读出设备当前的状态
• 主机向 控制寄存器 写入数据来发送命令、改变设备状态

轮询

主机和控制器之间交互很复杂，但基本的握手（handshaking）比较简单。假设控制器的状态寄存器中有一位用于说明设备当前是否在忙，控制器正忙时就将这一位置位。控制器的命令寄存器中有一位说明主机是否有任务准备就绪，当主机需要控制器执行某个操作时，需要将命令寄存器的这一位置位。主机和控制器交互输出一个字节时的握手流程如下：

1. 主机不断读取状态寄存器，直到状态寄存器中的 忙位 为 0
2. 主机设置命令寄存器中的 写位 并把一个字节写到数据输出寄存器
3. 主机设置命令寄存器中的 就绪位
4. 控制器注意到命令寄存器中的就绪位被置位，因此将状态寄存器中的 忙位 置位
5. 控制器读取命令寄存器并发现 写位 被置位，因此了解到需要执行一条写命令。它从数据输出寄存器读出一个字节，并向设备执行 I/O 操作
6. 控制器操作完成后将命令寄存器中的 就绪位 清除，并清除状态寄存器中的 故障位 （这说明 I/O 设备成功完成任务），最后清除状态寄存器中的 忙位 表示本次字节传输操作结束

在步骤 1 中主机将处于 忙等待（busy-waiting） 或者 轮询（polling） 状态。多数计算机体系只需要三个 CPU 指令周期就可以完成基本的轮询操作，但不断地重复轮询会浪费处理器资源。

中断

中断（interrupt）是使外设通知 CPU 的硬件机制。CPU 硬件有一条中断请求线（Interrupt-request line，IRL），CPU 执行完每条指令都会检测 IRL 判断是否有控制器通过 IRL 发送了信号。如果有，CPU 会保存当前的状态并且跳转到中断处理程序（interrupt-handler）。中断处理程序会判断中断原因、进行处理、恢复状态并执行中断返回指令使 CPU 返回中断之前的执行状态。整个流程大致为：

• 设备控制器通过中断请求线 发送中断信号引起（raise）中断
• CPU 捕获（catch）中断并分发（dispatch）到中断处理程序
• 中断处理程序处理设备请求以 清除中断

CPU 和中断控制器（interrupt-controller）硬件提供了以下三个特性：

• 在 CPU 执行关键指令时可以延迟对中断的处理
• 能够将中断快速转发给适当的中断处理程序，而不必检查所有设备以确定是哪个设备引发了中断
• 支持多级中断，可以根据紧迫性来响应中断

多数 CPU 有两个中断请求线： 非屏蔽中断（nonmaskable） 用于处理非常严重的，不可以恢复的内存错误等问题， 可屏蔽中断（maskable） 可被设备控制器用来请求服务，如果 CPU 正在执行关键、不可中断指令，则可以屏蔽这一类中断线上的请求。

中断机制根据 中断向量（interrupt vector） 来选择中断服务程序。中断向量和中断服务程序被维护在一张表中，中断向量支持的地址数量有限（例如 8 位中断向量只能对应 256 个中断服务程序，奔腾即为 256 个中断向量，0~31 用于各种错误等非屏蔽中断，剩下的为可屏蔽中断）， 中断链接（interrupt chaining） 可解决这个问题：中断向量指向的不再是单一的中断服务程序，而是一个中断服务程序的链表，中断一旦发生，对应链表中的全部中断处理程序都会一一调用，直到发现了能够处理请求的中断服务程序为止。

中断优先级（interrupt priority） 使 CPU 可以在不屏蔽所有中断的情况下延迟处理低优先级的中断，并且也允许高优先级的中断抢占低优先级的中断处理。

现代操作系统启动时会探查硬件总线、确定哪些设备存在并将对应的中断处理程序安装到中断向量中。操作系统对于中断机制的应用非常广泛：

• 设备控制器通过中断表明自己已经准备好服务
• 通过中断机制处理例如被 0 除、违例内存访问等 异常（Exception）
• 使用中断进行虚拟内存分页，页错误会引发中断异常，这个中断会挂起当前进程并跳转到内核的页错误处理程序
• 程序执行系统调用会触发 软中断（software interrupt） 或者 陷阱指令（trap）

直接内存访问

使用通用处理器不断监听设备控制器的寄存器并按字节传输（ 程序控制 I/O ，Programmed I/O，PIO）是对计算资源的非常过分的浪费。计算机为了避免 PIO 增加 CPU 负担，将一部分数据传输任务交付 直接内存访问（direct-memory access，DMA） 控制器。

开始 DMA 传输时，主机向内存写入 DMA 命令块，块中包含传输的源、目的地址指针以及传输的字节数。 CPU 将该命令块的地址写到 DMA 控制器中 并继续其他工作，DMA 控制器会根据命令块直接操作内存总线完成传输（这段时间 CPU 无法使用总线）。传输完成后 DMA 控制器会中断 CPU 并交还给 CPU 总线控制权。

DMA 和设备控制器之间的握手通过 DMA-request 和 DMA-acknowledge 线进行，设备有数据需要传输时，设备控制器就通过 DMA-request 线通知 DMA 控制器，DMA 控制器会发出申请中断 CPU，在从 CPU 获取所需要的地址后将地址放到内存地址总线上，并通过 DMA-acknowledge 线通知设备控制器。设备控制器收到这个信号，向内存地址总线上的地址写入数据。交互过程如下图。

DMA 控制总线传输期间 CPU 不能访问主存（仍可访问 L1、L2 缓存），这称为 周期挪用（cycle stealing） ，会放慢 CPU 计算，但往往能够改善系统总体性能。有的 DMA 使用物理内存地址，有的使用虚拟内存地址（这时候需要有一个虚拟到物理地址的转换），使用虚拟内存地址的 DMA 称为 直接虚拟内存访问（direct virtual-memory access，DVMA） 。DVMA 可以直接实现两个内存映射设备之间的传输而无需 CPU 干涉。

I/O 应用接口及后面几节简单摘要

设备在很多方面有很大差异：

• 字符流或块：字符流设备按字节传输，块设备以块为单位传输
• 顺序访问或随机访问
• 同步或异步：同步设备按照一定响应时间进行数据传输，异步设备则呈现无规则/不可预测的响应时间
• 共享或专用：共享设备可以被多个进程/线程并发使用，专用设备则不可以
• 操作速度：设备速度不同
• 读写/只读/只写：设备支持的数据传输方向不同

块设备（block-device） 接口规定了访问磁盘驱动器以及其它块设备所需的各个方面。操作系统本身和特殊的应用程序（如数据库）倾向于将块设备当作简单的线性块数组访问，这种访问方式称为 原始（raw） I/O 。

阻塞和非阻塞 I/O：

• 应用程序发出 阻塞（blocking） I/O 类型的系统调用时，应用程序就会被挂起，移动到进程等待队列中。因为阻塞式的 I/O 容易理解，并且 I/O 设备执行所需的时间是异步的，执行时间不可预估，因此绝大多数操作系统给应用程序预留的接口都是阻塞系统调用。
• 有的用户级进程需要 非阻塞（nonblocking） I/O ，例如用户接口，它用来接收键盘/鼠标输入，同时还要在屏幕回显。又或者视频应用程序，它需要从磁盘读取帧并解码到显示器上。非阻塞 I/O 通常使用多线程实现，有的线程执行阻塞系统调用，其他线程继续执行。
• 异步系统调用（asynchronous system call） 不必等待 I/O 完成就可以立刻返回，应用程序继续执行。I/O 完成时会通知应用程序，比如设置程序空间里某个变量，或者触发信号/软件中断等。
• 

缓冲区（buffer）是用来保存两个设备之间或者设备和应用程序之间传输数据的内存区域。采用缓冲的理由有：

• 处理数据流的生产者与消费者之间的速度差异
• 协调传输数据大小不一致的设备
• 支持程序 I/O 的复制语义

I/O 内核子系统

（kernel’s I/O subsystem）提供了很多和 I/O 有关的服务，包括：

• 调度（scheduling）
• 缓冲（buffering）
• 高速缓存（caching）
• 假脱机（spooling）
• 设备预留（device reservation）
• 错误处理（error handling）
• 名称转换（name translation）

参考

主要来自 https://blog.forec.cn/

https://bbs.pediy.com/thread-76876.htm