C语言基础
乘法逆元
信息安全算法基础
操作系统基础
x86汇编基础
信息论与编码

前言

这是电子科技大学计算机系的操作系统课程的总结，笔者已经基本理解这篇文章里的内容，但是如果有不准确之处，恳请指出。在操作系统这个成熟很久的领域中，有不少作者图文并茂的介绍了操作系统地基本知识。但是，笔者认为这里地总结相对精简，直接抵达核心概念，也是阅读学习的好资料。本文很多的总结和图片都来自老师的 PPT，笔者只是学习并且结合其他资料与自己的理解，加以阐释。

进程和线程

进程是操作系统最核心的概念，简单的说是正在运行的程序的抽象。进程的执行模型可以分成两类，顺序执行和并行执行，前者效率低，后者硬件要求高。我们整个课程都是只考虑并发执行，也就是微观上顺序执行，宏观上并行执行。进程＝进程控制块＋程序＋相关数据，进程之间各自独立、不可预知速度地并发执行。

进程的状态

进程有三种基本状态，进程都在内存中：

**就绪状态：**进程已分配到除 CPU 以外的所有必要资源后，只要再获得 CPU，便可立即执行。

**执行状态：**进程已获得 CPU，其程序正在执行。

**阻塞状态：**放弃处理机而处于暂停状态。处理机指计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件。

注意就绪不能直接到阻塞，阻塞也不能直接执行。

进程还有其他状态：

New：新建了进程对象，PCB（程序控制块）在内存，但是程序指令存储在硬盘。
Exit：进程彻底停止，并且释放内存。
挂起状态：进程被暂时调离内存。就绪挂起只要程序进入内存就可以运行；阻塞挂起定义模糊，等待事件就会变成就绪挂起。一般时放在交换区，不再竞争 CPU。

进程的描述

单独的进程可以拆解为：

进程映像：程序、数据、堆、栈的集合。
程序控制块。用于控制程序的行为，主要包括：
- 进程标识信息。每个进程都分配了唯一的标识符，用于引用进程，表示父进程和子进程的关系。
- 处理器状态信息。CPU 寄存器存储栈指针、程序计数器等执行信息，程序状态寄存器存储溢出、进位等程序状态。
- 进程控制信息。操作系统控制和协调各种活动进程所需的额外信息。比如优先级、进程运行态、调度算法相关信息、存储管理信息等。

映像名称                       PID 会话名              会话#       内存使用
========================= ======== ================ =========== ============
System Idle Process              0 Services                   0          8 K
System                           4 Services                   0      1,060 K
Secure System                  168 Services                   0     75,552 K
Registry                       248 Services                   0    227,004 K
smss.exe                       708 Services                   0      1,332 K
csrss.exe                      864 Services                   0      5,612 K
wininit.exe                   1168 Services                   0      6,716 K
csrss.exe                     1176 Console                    1     12,260 K
services.exe                  1240 Services                   0     17,772 K
LsaIso.exe                    1248 Services                   0      3,756 K

模式切换和进程切换

内核包含了重要的系统功能，常驻内存，管理资源和支撑系统。例如内核管理着进程的创建、终止、调度、同步、通信等，并且管理着存储空间中进程地址分配、内存交换、段页管理等功能。中断处理也是通过内核完成的。

在程序状态寄存器中存在指示执行模式的位。

内核模式。它由操作系统直接控制，具有更多的优先权和特权。部分底层的 IO 指令、寄存器操作指令、内存管理指令只能通过特权模式由内核发出。部分内存也只能通过特权模式由内核访问。
用户模式。它具备较少的优先权，用户在该模式下运行指令。

进程创建时，操作系统分配内存和用于管理进程的数据结构，然后对进程进行初始化，将新进程插入对应队列。

进程切换由系统中断和系统调用完成。系统中断又分为普通中断和陷阱。进程切换的详细步骤：

保存当前处理器的上下文环境，比如寄存器信息。
更新进程控制块的信息，将进程控制块移动到相应的队列。
选择另外一个进程，更新它的进程控制块信息。
更新内存管理数据结构。
执行结束后，恢复之前的上下文环境，载入之前寄存器的值。

模式切换的过程：当发生系统中断时，程序计数器置为中断处理程序开始地址，然后从用户模式切换成内核模式，以便执行特权指令。注意模式切换的过程可以不改变进程的状态。

线程

进程是拥有资源的最小单位，也是调度和执行的基本单位。线程是单个进程内更加细粒度的并发执行的单位，是调度的最小单位。线程的创建时间更短、终止花费的时间更短、线程切换时间比进程切换时间更短，因此线程更加轻量级，提高了不同程序间通信的效率。调度和分派是在线程的基础上完成的。

一个进程可能有多个线程，每个线程包括

执行状态（运行、就绪等）
未运行时保存的线程上下文
执行栈
用于局部变量的静态存储空间
与进程内其他线程共享的内存和资源访问

**一个进程中的所有线程共享一个地址空间和进程所拥有的资源。一个线程对共享资源的修改都将影响同一进程的其他线程的环境。**线程也包括了和进程类似的状态和基本操纵：派生、阻塞、解除阻塞、结束。

线程可以分为

用户级线程。线程的管理工作都由应用程序完成，内核意识不到线程的存在。因此，用户线程由应用程序决定，可以运行在任何操作系统上。但是当用户级线程请求系统调用时，会阻塞当前进程中所有的用户级线程。不能利用多处理器技术。
内核级线程。线程的管理工作由内核完成，允许同一进程内的多个线程被多处理器处理，一个线程阻塞时，内核可以调度其他线程。但是，内核级线程切换时，需要切换到内核模式，会有额外开销。

进程调度

当多个进程或者线程竞争 CPU 时，需要选择下一个要运行的进程或者线程，OS 中有完成这个工作的调度程序（scheduler）。

调度根据距离执行的远近，分为

长程调度。决定哪个程序可以进入系统中处理，创建进程
中程调度。内存的交换部分，主要是考虑并发度的限制和存储的限制。
短程调度。最为频繁的调度程序，直接决定下次执行哪个进程。

具体如下图所示

下面是一些会用到的概念：

响应时间。从用户提交一个请求开始，到接收响应之间的时间间隔。由输入传送时间、处理时间、响应传送时间构成。
截止时间。某任务必须开始执行的最迟时间，或必须完成的最迟时间。
系统吞吐量。在单位时间内，系统所完成的进程数。
处理器利用率。处理器处于忙状态的时间百分比。
周转时间。一个进程从提交到完成之间的时间间隔，等于等待资源的时间+执行时间。
平均周转时间。多个进程周转时间的平均值。
带权周转时间：进程的周转时间与系统为它提供的服务时间之比。服务时间是系统预计完成需要的时间。
平均带权周转时间：多个进程带权周转时间的平均值。

短期调度会直接影响系统性能，需要达到的目标是：用户感知的交互响应时间尽可能短、用户程序完成时间尽可能短、处理器利用效率尽可能高。具体如下图

调度算法

调度可以采用强制优先级，但是可能造成某些进程饥饿，也就是长时间得不到执行机会，因此可以采用动态优先级的方案。动态优先级调度算法分为抢占和非抢占，主要区别在于抢占式能中断正在执行的进程，然后执行新的进程。非抢占式需要等待当前进程执行完或者请求服务时被阻塞，新的进程才能执行。

在决定哪个就绪进程执行时，有三个关键参数。

w = 目前为止在系统里的等待时间
e = 目前为止花费的执行时间
s = 进程所需的总服务时间，包括 e; 这个参数需要估计或者由用户提供。

不同的目标就有不同的调度算法，下表是调度算法概览：

	FCFS	Round robin	SPN	SRT	HRRN	Feedbadk
选择函数	max[w]	常数	min[s]	min[s-e]	max[(w+s)/s]	参后描述
决策模式	非抢占	抢占(时间片完)	非抢占	抢占（到达时）	非抢占	抢占(时间片完)
吞吐量	不强调	时间片小时，吞吐量低	高	高	高	不强调
响应时间	可能很高，尤其在进程执行时间差别大时	为短进程提供较好的响应时间	为短进程提供较好的响应时间	提供较好的响应时间	提供较好的响应时间	不强调
开销	最小	最小	可能较大	可能较大	可能较大	可能较大
对进程影响	对短进程不利；对 I/O 密集型进程不利	公平对待	对长进程不利	对长进程不利	平衡性好	对 I/O 密集型进程可能有利
饥饿	无	无	可能	可能	无	可能

先来先服务 FCFS

选择就绪队列中存在时间最长的进程运行，即按请求 CPU 的顺序使用 CPU。对于下面的调度，结果如下图。

进程名	产生时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

平均周转时间 $(3+7+9+12+12)/5=8.6$ ，平均带权周转时间

$\frac{\frac{3}{3}+\frac{7}{6}+\frac{9}{4}+\frac{12}{5}+\frac{12}{2}}{5}=2.56$

FCFS 是非抢占调度算法，有利于 CPU 繁忙型的进程，而不利于 I/O 繁忙型的进程，平均周转时间长，不利于短进程，因为等待时间较长。

时间片轮转调度算法 RR

每个进程被分配一个时间片，周期性产生时钟中断，中断时当前进程进入就绪队列末尾，基于 FCFS 选择下一个作业运行。如果进程在时间片内阻塞或结束，则 CPU 立即执行调度。

这是抢占式算法，时间片用完之后一定会被中断。

进程名	产生时间	服务时间	时间片
A	0	3	1
B	2	6	1
C	4	4	1
D	6	5	1
E	8	2	1

**先添加新进程到队尾，再把过了时间片的进程放在最后。**具体过程如下，需要每个时刻：

A2。这里标记的方法是，进程名字后的数字表示还剩下的服务时间。
B6A1
A1B5
B5C4
C4B4
B4D6C3

过程以此类推。RR 算法属于抢占性算法，常用于分时系统。时间片的长短会显著地影响系统的性能，太短则进程切换太频繁，太长则短进程会产生时间浪费。另外，由于 IO 会阻塞进程，所以对 IO 密集类型的进程不利，对 CPU 密集的类型有利。在 RR 算法的基础上，提出了改进后的 VRR 算法，用于改善 IO 密集类型进程的不利地位。

短进程优先 SJF/SPF/SPN

短进程优先算法是非抢占式的算法，每当当前进程结束，就会根据当前每个进程的服务时间选择执行哪一个进程。

进程名	产生时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

核心点在于进程结束之后，选择服务时间最短的进程执行。由于短进程优先，所以服务时间长的进程容易饥饿，同时也减少了平均周转时间。服务时间是用户估计的时间，但是不一定等于实际需要占用处理机的时间。由于没有抢占机制，可能不适合某些场景。

平均周转时间 (3+7+11+14+2)/5=7.4，平均带权周转时间 (3/3+7/6+11/4+14/5+2/2)/5=1.74

剩余时间最短优先 SRT

剩余时间最短优先算法是抢占式的算法，每当当前进程结束或者新进程到来，就会根据当前每个进程剩余的服务时间选择执行哪一个进程。数据与之前的相同，得到的结果如下。

时刻 2 时，A 剩下 1，B 剩下 6，执行 A
时刻 3 时，B 剩下 6，执行 B
时刻 4 时，B 剩下 5，C 剩下 4，所以抢占，执行 C。
时刻 6 时，B 剩下 5，C 剩下 2，D 剩下 5.
时刻 8 时，B 剩下 5，D 剩下 5，E 剩下 2，所以执行 E。
时刻 10 时，因为 B 和 D 剩下时间相同，按照入队顺序，执行 B
时刻 15 时，执行 D。

平均周转时间 (3+13+4+14+2)/5=7.2，平均带权周转时间 (3/3+13/6+4/4+14/5+2/2)/5=1.59。周转时间方面，SRT 比 SJF 性能要好，只要就绪，短作业可以立即被选择执行。但是仍然存在长进程饥饿等问题。

高响应比优先 HRRN

当前进程执行完毕或需要阻塞时，选择就绪队列中响应比最高的进程投入执行。他是非抢占性调度算法。响应比的计算 (等待时间+要求服务时间)/要求服务时间。

进程名	产生时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

时刻 3，A 执行结束，只剩下 B。所以执行 B。
时刻 9，B 执行结束，C 响应比(5+4)/4=2.25，D 响应比(3+5)/5=1.6，所以执行 C。
时刻 13，C 执行完，D 响应比(7+5)/5=2.4，E 响应比(5+2)/2，所以执行 E。

HRRN 算法其实是动态权重算法，既考虑了短进程不应该等待过长的时间，又考虑了长进程不至于饥饿。但是计算响应比会增加开销。

反馈调度 FB

采用了「惩罚运行时间较久的进程」的思想，算法有很多种，大致的思路是维护多个就绪队列，每个队列的优先级不同，进程根据一定的规则动态调整优先级。注意是抢占式调度算法。

下面介绍一种基于时间片轮转的反馈调度算法，具体规则如下：

设置多个就绪队列，每个队列赋予不同优先级。
1. 第一队列优先级最高，依次递减；
2. 各个队列中进程执行的时间片不相同，优先级越高的队列，时间片越小。
新进程进入时，首先放入第一个队列尾，按 FCFS 原则排队。
如果进程在当前队列规定的时间片内完成则退出，一般而言，从队列 $i$ 中调度的进程允许执行 $2^i$ 的时间，然后才被抢占，降级到下一个优先级队列（如果没有被抢占（无其他进程需调度），则当前进程不降级）。
到达最低优先级队列后，不再降级。
仅当第一队列空闲时，才调度第二队列中的进程，依次类推。

仍然是之前的例子，调度的结果如下，队列编号从 0 开始。

时刻 0，A 进入队列 0，允许执行的时间是 1。
时刻 1，因为没有其他进程，A 不降级，进入队列 0，允许执行时间 1。执行 A。
时刻 2，A 时间片用完，被抢占，队列 0 是 B，队列 1 是 A，所以 B 执行一个单位。
时刻 3，B 时间片用完，队列 1 是 AB，所以执行 A。
时刻 4，A 执行完退出，队列 0 是 C，队列 1 是 B，所以执行 C。
时刻 5，C 执行完，队列 1 是 BC，所以执行 B。
时刻 6，由于 B 允许执行 2 个单位才被抢占，所以继续执行。
时刻 7，队列 0 是 D，队列 1 是 C，队列 2 是 B。
以此类推

多级反馈队列调度算法性能较好，短进程可以在前面几个队列执行完，长进程允许执行的时间也能快速增长。但是如果一直提交短进程，长进程仍然可能饥饿。

实时系统的调度

实时系统能够即时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。规定的时间分为

开始截止时间：必须在某个时间之前执行任务。
完成截至时间：必须在某个时间之前完成任务。

实时任务

实时任务一般有如下信息：

就绪时间
启动的限期（starting deadline）
完成的限期（completion deadline）
处理的时间：任务执行到完成的时间
资源需求：任务执行过程中所需的资源集
优先级：度量任务的相对重要性
子任务结构：一个任务可分解为一个必须执行的子任务和一个可选执行子任务，前者有硬截止时间（hard deadline）

可以知道，越早执行就越容易满足期限。非抢占方式可以更好的安排任务，满足启动的期限。抢占的方式可以更好的满足完成的期限。

调度算法的组成

我们之前讨论的调度算法，都是实时系统的调度算法。实时系统的调度则是由调度方法和抢占的方式决定的。这一小节会从理论上概括调度算法。

调度方法可以分成如下几类：

静态表驱动：他用于调度周期性实时任务，根据任务周期到达的时间、执行时间、完成截止时间（ending deadline）以及任务的优先级，制订调度表。这种算法不灵活，静态的调度表要经常修改。
静态优先级抢占调度法：多用于非实时多道程序系统，根据系统时间的约束赋予优先级。多道程序系统是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插的运行。也就是一般意义上的单 CPU，微观串行模式。
基于动态规划的调度法：当实时任务到达后动态地创建一张调度表，如果能够满足当前任务地时间约束，那么立即执行新任务。
动态尽力调度法：广泛用于非周期性实时任务调度，当任务到达时，系统根据其属性赋予优先级，优先级高的先调度。但是可能难以兼顾任务的时间约束。

抢占方式可以分成如下几类：

基于时间片轮转的抢占式。响应时间一般为秒级。
基于优先级的非抢占式。响应时间为几百毫秒到几秒。
基于优先级的抢占式。响应时间几毫秒至几十毫秒
立即抢占式。响应时间微秒至毫秒级。

针对每种情况的调度算法就不细说了，内容确实很繁杂。

优先级反转

优先级反转，是指某同步资源被较低优先级的进程/线程所拥有，较高优先级的进程/线程竞争该同步资源未获得该资源，而使得较高优先级进程/线程反而推迟被调度执行的现象。这是是一种不希望发生的任务调度状态。在该种状态下，一个高优先级任务间接被一个低优先级任务所抢先(preempted)，使得两个任务的相对优先级被倒置。

有一种解决方法叫优先级继承，也就是占有了资源的进程的优先级，继承共享这个进程的优先级。

进程的同步

这里的进程的并发都是指多道程序系统，宏观并行，微观穿行，也就是单处理器交替执行。进程是独立的个体，可以异步、并发，但是 CPU、内存等资源只能有限地使用。

部分术语如下：

原子操作。由一个或多个指令序列实现的动作或函数，对外不可见，一组指令要么都执行，要么都不执行。
互斥。当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问共享资源的情形。
临界资源。不可同时访问，必须互斥访问的资源，如打印机。
临界区。访问临界资源的代码，任意时刻只能由一个进程在这段代码中运行。
忙等现象。当一个进程等待进入临界区时，它会继续消耗处理器的时间。
活锁。两个或两个以上的进程为响应其他进程而持续改变自己状态，但是不做有用工作的情形。
死锁。两个或两个以上的进程因等待其他进程做完某些事而不能继续执行的情形。
竞争条件。多个进程或线程读写共享的数据时，结果取决于多个进程的指令执行顺序。
饥饿。一个具备执行条件的进程，被调度程序无限期的忽视而不能调度的情形。

由于进程执行的相对速度不可预测，资源的共享和协调就较为困难。比如某个变量被多个进程共享，那么每个进程读取这个变量时获得的值，可能不确定。所以需要设计控制访问共享资源的方法。

除了基于资源共享的进程之间的合作，还有基于通信的进程之间的合作。一个进程执行的结果可能由其他进程提供的信息决定。比如必须等接收到特定的信号之后，某个进程才能开始执行。

互斥

为了控制进程对临界资源的访问，提出了互斥的概念，互斥的性质如下：

空闲让进：如临界区空闲，则有进程申请就立即进入。
忙则等待：每次只允许一个进程处于临界区。
有限等待：保证进程在有限时间内能进入临界区。
让权等待：进程在临界区不能长时间阻塞等待某事件。

软件方法

在编程中我们可以用最原始的方法实现互斥，这叫做实现互斥的软件方法。他的核心思想在于：

进入临界区时，设置和检查一些标志，判断临界区是否被占有。
若已有进程在临界区，则在临界区的入口，循环地检查标志，等待临界区空闲后访问。
进程离开临界区时，需要修改标志。

这是单 CPU 的背景下的进程调度，就是说每个时刻只能运行一个进程，微观串行。下面不同的进程中是访问同样的临界区。

单标志法

进程访问完临界资源后会把使用临界资源的权限主动转让给另一个进程。即每个进程进入临界区的权限只能被另一个进程赋予。通过一个标志表示应该执行哪一个进程。

int trun = 0;                      //共享的全局变量

//进程P0
do {
    while (turn != 0) ;           //进入区
    //进程P0的临界区代码； 			//临界区
    turn = 1;                     //退出区
    //进程P0的其它代码				 //剩余区
} while (true);

//进程P1
do {
    while (turn != 1) ;           //进入区
    //进程P1的临界区代码； 			//临界区
    turn = 0;                     //退出区
    //进程P1的其它代码          	 //剩余区
} while (true);

这是最容易想到的，一个全局变量，然后两个进程之间轮换，但是违反了空闲让进的原则。如果是 P1 先进入，那么就会在 while 处执行空的循环，直到时间片用完。但是这个期间，虽然 P1 没有访问临界区，但是 P0 也无法访问临界区，这就违反了空闲让进的原则了。

也就是必须按照一定的顺序执行才行，每个进程执行的权限来自其他进程，如果其他进程没有先执行，就会违反空闲让进原则。

双标志先检查法

通过设置一个数组，表示每个进程进入临界区的意愿，每个进程在使用资源之前先检查是否有别的进程想进入临界区。如果没有则将自身对应的标志 flag[i] 置为 true，并开始访问临界区；有则先让其他进程使用。

boolean flag[2] = {false, false};   //共享的全局变量

//进程P0
do {
    while (flag[1]) ;               //进入区
    flag[0] = true;                 //进入区
    //进程P0的临界区代码； 			  //临界区
    flag[0] = false;                //退出区
    //进程P0的其它代码          	   //剩余区
} while (true);

//进程P1
do {
    while (flag[0]) ;               //进入区
    flag[1] = true;                 //进入区
    //进程P1的临界区代码； 			  //临界区
    flag[1] = false;                //退出区
    //进程P1的其它代码				   //剩余区
} while (true);

但是如果执行 #5 和 #14 的检查之后，#6 之后执行 #15，就会造成同时访问临界区的情况，违反了忙则等待的原则。这是因为检查和上锁之间，其他进程可能已经通过了检查，也在准备上锁。把检查和上锁结合在一块，形成原子操作，是可行的办法。

双标志后检查法

和上一个方法类似，差别在于先上锁后检查。但是如果在上锁和检查之间，另外一个进程也上锁了，就会造成死锁。

boolean flag[2] = {false, false};    //共享的全局变量

//进程P0
do {
    flag[0] = true;                  //进入区
    while (flag[1]) ;                //进入区
    //进程P0的临界区代码；			   //临界区
    flag[0] = false;                 //退出区
    //进程P0的其它代码          		//剩余区
} while (true);

//进程P1
do {
    flag[1] = true;                  //进入区
    while (flag[0]) ;                //进入区
    //进程P1的临界区代码； 			   //临界区
    flag[1] = false;                 //退出区
    //进程P1的其它代码         	    //剩余区
} while (true);

Dekker 互斥算法

这个算法结合了单标志法和双标志法，在使用临界资源前，判断对方是否想使用资源，而且资源的使用权是否已经给了对方。如果都是，则自己暂时不想使用资源，等待对方释放资源后，再想要资源。重复进行这样的等待，直到对方不想使用资源。

boolean flag[2] = {false, false};              //共享的全局变量
int turn = 1;                                  //共享的全局

//进程P0
do {
    flag[0] = true;                            //进入区
    while (flag[1]) {
       if (turn == 1)  {
           flag[0] = false;
           while  (turn == 1) ;                //等待
           flag[0] = true;
        }
     }                                         //进入区
    //进程P0的临界区代码；            			 //临界区
    turn = 1;
    flag[0] = false;                           //退出区
    //进程P0的其它代码                   		  //剩余区
} while (true);

//进程P1
do {
    flag[1] = true;                            //进入区
    while (flag[0]) {
       if (turn == 0)  {
           flag[1] = false;
           while  (turn == 0) ;           	   //等待
           flag[1] = true;
        }
     }                                         //进入区
    //进程P1的临界区代码；          				 //临界区
    turn = 0;
    flag[1] = false;                           //退出区
    //进程P1的其它代码                   		  //剩余区
} while (true)

上述所有的软件方法，都是依靠循环实现，所以没有遵循让权等待的原则

硬件方法

硬件方法分为中断禁用和机器指令。中断禁用，就是屏蔽中断，利用「开/关中断指令」实现互斥。「关中断」和「开中断」之间的代码就是临界区。由于关中断后 CPU 会屏蔽中断，而进程切换依赖于中断，因此可以保证其他进程不会访问到这个临界区，避免了资源竞争。

但是中断禁用的办法只能在单 CPU 计算机使用，不同 CPU 之间的进程需要额外的协调机制。

机器指令是指在设计 CPU 时就设计了一些指令，用于保证两个动作的原子性。比较典型的例子是 compare&swap ，比较一个内存单元的值和一个测试值，如果相等，则发生交换。这个操作就必须保持原子性。再比如 Exchange，原子性地交换寄存器和内存的值。它涉及到两次写入，也是需要保持原子性。

采用机器指令可以支持多 CPU、多临界区计算机，而且简单易证明。但是使用不当也会造成死锁。

信号量

两个或多个进程可以通过传递信号进行合作，主要功能是：

迫使进程在某个位置暂时停止执行（阻塞）
直到它收到一个可以“向前推进”的信号（被唤醒）

这样的机制就叫做信号量机制。表示这样的信号的变量就叫做信号量。信号量是一个值为整数的变量，只能进行下面的三类操作：

初始化为非负数。
semWait （Wait 或 P）操作使信号量的值减少 1。若值变为负数，则阻塞执行 semWait( Wait 或 P)操作的进程。
semSignal（Signal 或 V）操作使信号量的值增加 1，若值小于等于零，则被 semWait(Wait 或 P)阻塞的进程解除阻塞。

信号量里 count 值可以解释如下

s.count ≥ 0, s.count 表示执行 semWait(s)操作而不被阻塞的进程数（或可看作可用资源数）。这种情形信号量可支持同步与互斥。
s.count < 0, s.count 表示阻塞在 s.queue 队列上的进程数。

生产者/消费者问题

生产者/消费者问题是信号量使用的经典方式，描述如下：

一个或者多个生产者产生数据，并放入缓冲区。
每次只能有一个消费者从缓冲中取出数据。
任何时候只能由一个生产者或消费者访问缓冲。（互斥关系）
保证缓冲区满时，生产者不会往缓冲区中增加数据。（同步关系）
保证缓冲区空时，消费者不能从缓冲区中取走数据。（同步关系）

上面的条件中包括了两个同步关系和一个互斥关系。所以需要三个信号量表示。

semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量，表示空闲缓冲单位的数量
semaphore full = 0;  //同步信号量，表示产品的数量，也即非空缓冲单位的数量

producer(){
    while(1){
        //生产1个产品;
        P(empty);    // 消耗一个空闲缓冲单位
        P(mutex);	 // 访问缓冲区
        //把产品放入缓冲区;
        V(mutex);
        V(full);	 // 增加一个产品
    }


consumer(){
    while(1){
        P(full);     // 消耗一个缓存区中的产品
        P(mutex);	 // 访问缓冲区
        //从缓冲区取出产品;
        V(mutex);
        V(empty);	 // 增加一个可用缓冲区单位
        //使用产品;
    }
}

注意：

先申请资源信号量，再申请互斥信号量。如果反过来的话，会发生死锁。因为当缓冲区满之后，生产者的 P(empty) 会阻塞，同时上一句的 P(mutex) 会导致消费者的 P(mutex) 阻塞。
消费者的 V(mutex) 和 V(empty) 顺序可以互换。

来看下面这个实际练习.

桌子上有一只盘子，最多可以放入 N（N>0）个水果。爸爸随机向盘中放入苹果或桔子。儿子只吃盘中的桔子，女儿只吃盘中的苹果。只有盘子中水果数目小于 N 时，爸爸才可以向盘子中放水果（两个同步关系）；仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出相应的水果（同步关系）；每次只能放入或取出一个水果，且不允许多人同时使用盘子（互斥关系）。

semaphore mutex = 1; //一个盘子只能被一个人使用
semaphore orange = 0; //必须有橘子，儿子才能取橘子
semaphore apple = 0; //必须有苹果，女儿才能取苹果
semaphore empty = N;//必须有空位，爸爸才能放水果

//爸爸放水果
P1(){
    while(1){
        //选择水果类型
        P(empty);
        P(mutex);
        //放入水果进盘子
        V(mutex)
        V(orange or apple)
    }
}

//儿子取桔子
sun(){
    while(1){
        P(orange);
        P(mutex);
        //取出苹果
        V(mutex);
        V(empty);
    }
}

//女儿取走苹果
sun(){
    while(1){
        P(apple);
        P(mutex);
        //取出苹果
        V(mutex);
        V(empty);
    }
}

如果改变条件，爸爸放苹果，妈妈放桔子，其他不变。那么只要增加一个和生产者类似的进程即可。

读者和写者问题

多个进程访问一个共享数据区（可为文件、内存空间、寄存器），其中有些进程只能读取数据，有些只能写入数据，有些则有读写权限。规定进程可以同时读、互斥写(不能同时写)、互斥读写（不能同时读写）。这个问题和消费者/生产者问题的区别在于，它可以同时读取。

为了完成互斥，就可以选择读者优先、写者优先，或者公平读写的策略。

读者优先就是必须全部读者都完成了，才能写入。很显然，容易造成写者饥饿的问题。此时需要，读写互斥锁、读者的数量，由于读者数量是没有限制的，我们采用加互斥锁和变量来实现。

int readCount=0；
semaphore readCountMutex = 1, wMutex=1;

void reader(){
    while(1){
        P(readCountMutex);
        readCount++;
        if(readCount==1) P(wMutex); //读写互斥
        V(readCountMutex);
        //读取
        P(readCountMutex);
        readCount--;
        if(readCount == 0) V(wMutex);
        V(readCountMutex)
    }
}

void writer() {
	while (1) {
        P(wMutex);
        //写入
        V(wMutex);
    }
}

写者优先就是存在写者声明需要读取数据时，之前的读者必须先完成，之后的新的读者暂时不能读取数据，需要等待写入完毕之后才行。但是如果又有新的写入进程，那么会接着上一个写入进程执行。显然，由于读者被推迟，系统的并发性能较差。并发时需要考虑：

之前的读者必须完成，所以需要记录之前读者的数量。
写入数据需要互斥锁。
之后的读者需要阻塞，需要互斥锁。
新来的写者可能要「插队」，需要记录写者数量。

int writeCount = 0, readCount = 0;
semaphore wMutex=1, rmutex=1, writeCountMutex=1, readCountMutex=1

void reader() {
	while(1){
        P(rMutex); //被阻塞则不能进行任何操作
        P(readCountMutex);
        readCount++;
        if(readCount == 1) P(wMutex); // 等待之前的读者完成
        V(readCountMutex);
        //读取
        P(readCountMutex);
        readCount--;
        if(readCount == 0) V(wMutex); //之前的读者完毕
        V(readCountMutex);
    }
}

void writer(){
	while ( 1 ){
		P(writeCountMutex); //为了保证自增和判断的原子性
		writecount++;
		if (writecount == 1) P(rMutex); //写入时阻塞读取
		V(writeCountMutex);
		P(wMutex);
		//写入
		V(wMutex);
		P(writeCountMutex);
		writecount--;
		if (writecount == 0) V(rMutex);
		V(writeCountMutex);
	}
}

公平读写则按照先来后到的顺序，处理读者和写者。那么

读者读取时不能有写者。需要互斥。
新进程到达时，都应该阻塞。
写者之前的读者，应该全部完成，写者才能开始。
写者之间应该互斥。

int readCount = 0;
semaphore wrMutex = 1, wMutex = 1, readCountMutex = 1,

void reader(){
    P(wrMutex); //读者和写者串行，但是读者之间并发
    P(readCountMutex);
    readCount++;
    if(readCount == 1) P(wMutex); // 读取时加写锁
    V(readCountMutex);
    V(wrMutex); //在这里解开读写锁很有讲究，读者可以并发读取
    //读取
    P(readCountMutex);
    readCount--;
    if(readCount == 0) V(wMutex)//解开写锁
    V(readCountMutex);
}

void wirter(){
    P(wrMutex); //读者和写者串行
    p(wMutex);
    // 写入
    V(wMutex);
    V(wrMutex);
}

例题 1：

有一座东西方向的独木桥，桥很窄只能单向通行，而且承载能力有限，最多 4 个人同时在桥上。当某一方向有行人过桥时，另一方向行人必须等待。东、西两端各有若干行人在等待过桥。请用 P、V 操作来实现东西两端行人过桥问题。

这是需要公平地过桥，两边地人互斥而且各自可以并发。每一边需要等另外一边的人通过才能开始。考虑进程之间的通信，需要的信息如下

东西两个方向，需要互斥锁，只能走一个方向。
东西两个方向都需要自己的数量锁，防止并发造成 count 修改和读取不一致。
东西两个方向需要表示自己的数量。

int countA = 0, countB = 0
semaphore lockCountA = 1, lockCountB = 1, mutex = 1, count = 4;

void eastToWest(){
    P(lockCountA);
    countA++;
    if(countA==1) P(mutex);
    V(lockCountA);
    P(count);
    //过桥
    V(count);
    P(lockCountA);
    countA--;
    if(countA==0) V(mutex);
    V(lockCountA);
}

void westToEast(){
    P(lockCountB);
    countB++;
    if (countB==1) P(mutex);
    V(lockCountB);
    P(count);
    //过桥
    V(count);
    P(lockCountB);
    countB--;
    if (countB==0) V(mutex);
    V(mutexB);
}

经验：

想象进程时独立个体，同类进程之间、不同类别进程之间合作需要哪些信息。
宁愿多一些信号量，尽量避免少量信号量组合使用，这样尽管精妙，但是不容易写和理解。
以上的例子都是可以拓展的，进程之间通过信号量同步，进程内部可以用更小的协程等同步，然后把每个小部分都视作对象，就构建并发的高性能程序了。

管程

管程是一个程序设计语言结构，采用了集中式的进程同步方法，提供了与信号量同样的功能，但更易于控制。这里强调「集中式」，是因为信号量的操作分散在各个进程种，代码维护和心智负担都比较大。

管程定义了数据通信的数据结构和并发控制的操作（比如阻塞、接触阻塞、队列长度控制），并且局部的数据只能被管程访问，这样完成通信数据和局部数据的区分。同一时刻，只能有一个进程再管程中执行，其他调用管程的进程都会被阻塞，直到这个进程阻塞或者退出。这样实现了临界资源的互斥访问。

管程需要条件变量实现队进程的管理，因为管程中只能由一个进程执行，如果进程到达顺序不对，那么就不满足条件变量，进程就会阻塞。这时管程的调用权就交给了其他进程，直到另外的进程满足了条件变量，才能顺利执行。管程中的条件变量是同步的，因此由于其他进程修改了条件变量，这样被阻塞的进程也可以解除阻塞继续执行。这样，就完成了进程之间的同步。

管程中最常见的操作就是阻塞和解除阻塞：

cwait©：调用进程的执行在条件 c 上阻塞，管程可供其它进程使用。
csignal©：恢复在条件 c 上阻塞的一个进程，若不存在阻塞进程，则什么都不做。

消息传递

我们之前都是直接默认了信号量在不同进程中是同步的，用来实现互斥或者同步。这样传递消息的方式，具有一些规律和模式。这一小节我们就是学习消息传递的基本原理。

消息传递由两条基本原语（原语是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断）：发送和接收。简单的说就是来自谁、发给谁，还有一些控制信息等。

上图的消息的数据结构中可以看到一些参数，特别是源 ID 和发送 ID，它们的确定的方式，在不同场景下也不同。直接寻址时直接包含目标程序 ID，接收报文时根据需要选择是否要指明源程序 ID。间接寻址时消息会发送到公共的队列，然后接收的进程从公共队列中取走消息。

对于发送消息的进程，在发送消息之后可能阻塞，也可能不阻塞，继续执行。对于接收消息的进程，可能必须等待消息到达才能解除阻塞，也可能不接收消息直接执行。总的来说，有以下 3 种模式：

阻塞发送，阻塞接收 。发送者和接受者都阻塞，直到完成消息投递。一般需要进程紧密地同步时，比如流水线调度，会采用这种模式。
**不阻塞发送，阻塞接收 **。发送者不阻塞，但是接收者阻塞直到请求的消息到达。这是最常见的请求的模式。
**不阻塞发送，不阻塞接收 **。这就是各自执行各自的。

死锁

进程同步的小节已经介绍过死锁了，当一组进程中的每个进程都在等待某事件，而只有同组进程中阻塞的其他进程能够促发该事件时，死锁发生。比如进程之间循环等待，或者内存不足，各自执行一般后阻塞。

严格的说，死锁的发送必须具备一些条件。必要条件：

互斥。存在资源是临界资源，一次只有一个进程可以使用这个资源。
占用等待。当进程等待其他资源时，继续占有已经分配的资源。
不可抢占。不能强行抢占进程已经占有的资源。

这些都是容易理解的，必须要存在临界资源才会造成等待，等待的时候如果释放资源或者资源被抢占，也是无法发生死锁的。有个充分条件则是循环等待：存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。

死锁预防

死锁预防是指通过不满足上述三个条件防止死锁的发生。死锁的避免是指允许上述三个条件，但是通过设计不发生死锁。

互斥这个条件无法禁止，因为有些资源只能被独占。占用等待则可以要求进程一次性请求所有资源，并阻塞这个进程直到所有资源请求能够满足。但是，得到所有资源才开始执行，效率很低，而且某些进程执行时不知道需要哪些资源。

为了改善不可抢占的条件，就可以要求一个占有某些资源的进程进一步申请资源时若被拒绝，则释放最初占有的资源，或者要求占用自己需要的资源的进程释放资源给自己用。但是资源的状态如果不容易保存的话，会造成其他的程序中断，可能不得不重新执行被中断的进程。

从防止循环等待的角度说，可以把资源排序，申请资源的进程，必须先按照资源的序号申请，比如申请了 5 号资源就不能回过头申请 4 号资源。这样就避免了资源的冲突，但是显然申请资源的顺序可能和进程需要请求的资源的顺序不一样，这样需要额外的处理，效率较低。

死锁避免

死锁的避免是指允许上述三个条件，但是通过设计不发生死锁。一般有两种办法：

资源分配拒绝。若一个进程增加的资源请求会导致死锁，则不允许这一资源分配。
进程启动拒绝。若一个进程请求会导致死锁，则不启动该进程

简单的说，就是动态地检测，避免资源竞争地发生。比较典型的算法是银行家算法，它的基本思想是当进程申请资源时，必须保证分配出去之后，系统还是处于安全状态。否则就不分配，阻塞这个申请资源的进程。这里的「安全状态」指至少有一个资源分配的序列（表示进程申请资源顺序）不会导致死锁，能够让所有进程运行结束。安全状态一定不会发生死锁，不安全的状态不一定会发生死锁。

银行家算法需要使用到如下的数据结构：

声明需要资源的矩阵（C 矩阵）。表示每个进程需要每种类型的资源的数量。
分配矩阵（A 矩阵）。表示当前每个进程分配到的资源的数量。
C-A 矩阵。表示每个进程还需要的资源的数量。
资源向量。表示当前系统拥有的每类资源的数量。
可用资源向量。表示当前还可以分配的每类资源的数量。

根据逻辑和上述原理，可以发现分配矩阵中每类资源的和就是已经分配出去的资源数量，相当于资源向量减可用资源向量。图上的所有信息，就是初始的系统状态。

每次更新时，可用资源向量（的每个元素）必须大于 C-A 矩阵中的某个进程，这样才能让一个进程获得所需的所有资源。但是可能出现有多个满足条件的进程，这就像一棵树一样，有多条路径。就是通过这样类似深度优先搜索的方法，找到一条可以遍历每个进程一次的路径。例如上图只有 P2 满足条件，当 P2 运行结束后，状态如下图。

记住需要更新分配矩阵、C-A 矩阵、可用资源向量。需求矩阵对应进程需要的资源设置为 0。

可以知道都可以分配了，不妨选择 P1，P1 运行结束后如下

之后的选择完全是类似的，P2, P1, P3, P4 这个顺序是安全的，其他的顺序，比如 P2, P1, P4, P3 也是安全的。需要注意的是，如果进程并不一次性分配的需要所有资源，这也是可以的，但是需要满足分配之后，存在一个进程可以分配得到所有它需要的资源。比如，下图中，如果给 P1 分配了(1, 0, 1)的资源，那么后续就无法分配了，没有一个进程可以执行结束，这是不允许的，会拒绝分配。

根据上面的例子可以发现，死锁避免采用的银行家算法，并没有改变三个必要条件中的要求，而是通过策略控制资源分配给进程的多少和顺序，从而达到死锁避免。这样做的限制更少，而且更加灵活。但是，这需要每个进程需要在执行前声明自己需要的所有资源有哪些，而且进程之间是独立的，不能有执行顺序的要求。特别是频繁的检测会消耗处理器很多的时间。

如果发现不存在安全的路径，通常有三种办法：

撤销进程。撤销被永久阻塞的进程，直到不发生死锁。
回退。把进程的状态回滚到之前的检查点，从检查的开始重新执行。
抢占。通过抢占资源，来保证某个进程能顺利执行。

哲学家就餐问题

哲学家就餐问题是经典的死锁问题。场景如下 5 把叉子，五份食物，每个人必须要两把叉子才能进食。显然，如果每个人都拿起了一把叉子，就每个人都没办法进食。直观的想法是，如果一个人拿不到左边或者右边的叉子，那么就把手上的另一个叉子也放下，让其他人使用。但是，没有规则的互相谦让，可能让每个人都无法进食，形成活锁。

所以我们需要给资源建立偏序关系，让资源按照一定的顺序申请和释放。

方案一：就餐前，先取用编号较低的餐叉，再取用编号较高的餐叉。这样就会有同一个叉子被两个人竞争，导致至少一个人由于竞争失败，不去取另外一个叉子。这样就可以保证有一个人能拿到两把叉子。

方案二：奇数号的哲学家必须首先拿左边的餐叉，偶数号的哲学家必须首先拿右边的餐叉。同样的道理。

方案三：最多允许四个人同时进食，这样至少一个人会拿到两把叉子。

semaphore fork[5] = {1, 1, 1, 1, 1}, room = 4;
void main()
{
        cobegin {philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4);}coend;
}
void philosopher(int i)
{
    while(1) {
        wait(room);                             //占据就餐位置
        wait(fork[i]);                           //拿起左边的叉子
        wait(fork[(i+1)%5]);               //拿起右边的叉子
        eat();
        signal(fork[(i+1)%5]);            //放回右边的叉子
        signal(fork[(i]);                        //放回左边的叉子
        signal(room);                          //释放就餐位置
    }
}

哲学家就餐问题，实际上代表着对每一个进程，临界资源要么全部分配到位或者一个资源都不分配。

基本内存管理

这一部分的前提是，要求默认读者清楚计算机存储的基本结构。对于存档的存储，是不能直接访问的。ROM 这些是可以作为永久性记忆的，可以用来存储。对于快速的临时存储，按照 CPU 读取的亲近关系，可以分成寄存器、Cache、主存（内存）。它们的速度是从金字塔顶端下降的，但是容量是逐渐上升。

内存管理的关注点

内存管理需要关注重定位、保护、共享、逻辑组织方式、物理组织方式。

重定位是指编程时程序员设置的内存位置和实际程序运行的位置的映射，程序员不知道系统可能在哪些位置有哪些程序，所以就需要重定位技术，让程序按照内存空闲情况，重新定位到内存中不同的位置。重定位的方式，其实就是地址转化的方式，也会影响进程寻址的方式。

保护是指进程以外的其他进程中的程序不能未经授权地访问（进行读操作或写操作）该进程的内存单元。这是非常重要的技术，如果黑客可以访问并修改 root 用户所在的内存，刻意修改内存，可能会造成严重后果。所以，windows 也推出了让内存中程序的位置不可预测的功能。

共享是指多个进程可以执行同一个程序，多个进程拥有同一个副本，通过共享可以大大节省内存。

逻辑组织方式是应用程序访问内存时，看到的内存的组织方式。属于软件层面的支持。

物理组织方式是硬件层面的编码方式，它和逻辑组织方式之间的转化由操作系统完成，而不是由程序员完成。最典型的就是虚拟内存和物理内存之间的映射方式。

高级语言需要转化成实际的可以运行的程序，一般需要对单个文件的源代码进行编译，然后链接编译后的单个模块和库函数等形成一个完整程序。之后才能装入内存，程序直接包含了静态库，但是动态库需要在程序装入时跟着装入。

在装入主存的过程中，程序内的地址将会发生重定位，将逻辑地址转化成内存中的物理地址。

加载过程

装入主存的过程，根据逻辑地址和物理地址的映射关系，可以分成：绝对加载方式、静态重定位方式、动态重定位（运行时）方式。

绝对加载方式逻辑地址和物理地址完全相同，编译时就确定了程序将运行在内存中的具体的位置，在程序内可能用一些符号地址代替地址的编号，编译时就会转化成绝对地址。非常显然的是，内存中程序的安排必须是完全确定的，也就是这样的系统是专用的。其次，多处理器系统在运行这个程序产生的多个进程时，可能会造成存储位置冲突。

静态重定位编译时采用相对地址的方式，编译器假设加载是从 0 地址开始的，加载时程序代码内的所有地址拥有相同的偏移量，运行之后地址不能改变。由于运行后地址固定，不方便重新分配内存，导致内存空余的间隙不能充分利用。·

动态重定位的地址转换过程发生在运行时，为了不影响运行速度，一般使用硬件支持。这样程序不必连续的存放在内存中，而且可以共享某一段内存，这也是现代计算机的主流方式。缺点也显然，就是更加复杂，地址转化的计算也更复杂。

链接过程

静态链接在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块。静态链接时需要考虑各个模块的地址的统一、外部引用地址的统一。显然，这样编译出来的程序会很大，因为需要的东西都塞进去了，也不方便对每个模块升级，而且链接的库函数在实际执行中，可能不会全部同时用到。但是，这样做也避免了一些环境依赖。

加载时动态链接待加载的模块在加载内存时，如果该模块中有到外部模块的引用，加载程序将查找这些模块并加载内存，并把这些引用修改为相对应用程序模块开始处的相对地址。各个模块相对独立，可以升级，不同程序也可以共享库函数。但是，加载确定之后，模块是不能变动的。

运行时动态链接在程序执行中需要某目标模块时，由操作系统去找到该模块并将之加载内存，随后把它链接到调用者模块上。这是很主流的方式，比如 windows 的 ddl 文件就是一些用于加载时动态链接的库函数。模块就是动态的可拆卸的，可以加快加载过程，也可以节省内存空间。

内存分区

使用过的内存分区技术如下，从开始的简单分区，到后来的分页分段和虚拟内存方案，体现了技术进步的过程。我们在这节只介绍前面两种，段和页将在虚拟内存管理中学习。

内存管理技术	使用
固定分区	IBM MFT
动态分区	IBM MVT
简单分页	没有使用，但为虚存分页的基础
简单分段	没有使用，但为虚存分段的基础
虚存分页	现代操作系统广泛实际使用
虚存分段	现代操作系统广泛实际使用

固定分区的分区数量固定，操作系统占据内存的固定部分，其他每个分区装入一个进程。分区的大小肯能相等也可能不相等。如果分区大小相等，那么程序可能无法恰好占满分区，导致内存中有很对碎片，浪费空间。分区大小不等，则需要一定的算法进行分配。

动态分区的分区大小和数量都不固定，可以按照进程的需求分配内存空间。但是由于进程在内存中的分配和取消分配，也会产生大量内存碎片，例如下图进程 2 退出后的空隙就无法被填满。因此，提出了压缩技术，通过移动进程，使得进程占用的空间连续。但是这样也浪费了处理器的时间。

简要介绍动态分区的算法：

首次匹配。从头开始扫描内存，选择大小足够的第一个可用块。
下次匹配。从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块。
最佳匹配。选择空间大小与需求最接近的空闲块分配。
最差匹配。选择满足需求的最大的空闲分区分配。

伙伴系统是固定分区和动态分区的折中方案。简单的说，分区的大小既不是精确按进程的需要决定，也不是按照预先确定的固定方式决定，而是按照 2 的幂次分配空间，找到满足进程需要的最小的 2 的幂次的空间。

分页

（这一小节，如果完全没有接触过虚拟内存，可能需要较长时间理解）

页是进程中的块，页框是内存中的块。因此，进程和内存都分成了大小相等的块，便于映射和寻址。页和页框之间的映射，就可以在逻辑上进程的内存空间连续，物理存储上可以分开。这样就非常灵活，也避免了内存的小碎片的产生，实现了内存的离散分配。

页和页框的对应关系，由页表储存着，处理器会访问页表，用硬件的方式将页表项中的逻辑地址，转换成物理地址。页表项的基本结构如下图，页号表示第几个页，业内偏移量则是在一个页内的地址偏移量，这样就可以定位到某一个字节。

逻辑地址到物理地址的转换过程非常的直接，偏移量部分不变，逻辑地址会根据页表查找到页框号。这样页框号和偏移量拼接起来，就是物理地址了。

页表储存在内存中，进程管理块（PCB）记录着页表的起始地址，页表寄存器存放当前运行进程的页表的起始地址。我们看一个示例，内存容量共 256K，存储块的大小为 1K，那么就有 256 个页框。第 0 ～ 4 块为操作系统所使用。现有 2 个用户作业，作业 1 和作业 2，其逻辑地址空间分别占 2k 和 2.5k。那么就分别需要 2 页和 3 页。那么一种可能的内存布局方式，就如下图所示。进程左边的数字表示地址，页表中存在页号到页框号的对应。

对于虚拟地址 09C4H（注意末尾的 H 表示十六进制），二进制为 0000 1001 1100 0100B（末尾 B 表示二进制）。注意虚拟地址的页的数量不一定等于页框的数量，一般是会大于，也有可能小于。所以虚拟地址页号占几位一般是通过偏移量和机器字长计算的。假设这是 16 位的机器，那么低 10 位是偏移量（对应页的大小），29C4H，高 6 位 2H 是页号，对应页框号 10，所以物理地址为 18 位 00 0010 1001 1100 0100.

分段

一个程序可以分成大小不等的几个段，每个段都从 0 开始编址，并占用一段连续的地址空间。逻辑地址则由两部分构成，段号+段内偏移量。分段可以被程序员控制，但是分页不行，这样可以让程序运行时实现模块化。分段也可以避免内存的内部碎片，段之间可以动态连接。

因为段的大小不等，所以逻辑地址和物理地址之间的对应关系比较复杂，但是寻址过程和分页是完全相同的。

分页存储管理系统不易实现「共享」，不支持「运行时动态链接」，而分段系统易于实现「共享」和「动态链接」。

虚拟内存管理

虚拟内存最主流的就是分段和分页，他们都需要硬件支持，而且操作系统必须实现管理页和段的软件算法。虚拟内存是指外存（比如机械硬盘、固态硬盘）可以看作是内存的一部分来寻址，这样实现了对内存的拓展。

需要注意，分段和分页不需要一个程序的所有页或者段都在内存中，只需要加载正在运行的部分即可，这也是非常重要的节省内存空间的方法。分段或分页式的进程执行过程：进程在执行过程中，会从程序的入口加载若干块进入内存，当前驻留在内存中的部分叫做驻留集。如果逻辑地址对应的物理地址上的内容标记为失效，那么就会产生中断，进程进入阻塞阶段。接着，操作系统就会生成磁盘 IO 请求，在这个过程中，会调度其他进程执行，当磁盘 IO 完成之后，内存上就有了需要的资源，被阻塞的进程进入就绪状态。

按照上面的执行过程，可以发现找到尽可能的减少缺页的发生的方法，是非常重要的。如果外存加载进内存和释放的过程太频繁，就会造成抖动，大量缺页。经典的办法是利用局部性原理，短时间内程序在外存中的存储一般是连续的，也就是说具备集簇倾向。那么从外存加载数据时，就可以预测下一个需要的数据，在已经加载的数据的附近。

基于虚拟内存技术，内存可以实现拓展，运行更多的进程，调度效率高。分段分页即使可以实现运行时按需调配资源，可以提高内存利用效率。

分页细节

之前介绍的分页，只是提到页表中逻辑地址到物理地址的对应关系，而实际的使用中还存在一些常用的优化技术。例如增加控制位，存在位 P 表示对应的页是否在内存中，M 表示距离上次装入内存中的页框的内容是否修改过。

由于虚拟内存可以非常大，远大于内存，所以页表也可能很大，因此页表会存储在虚拟内存中。比如一个虚拟空间 32GB，每个页大小 1KB，那么需要 2^(35 - 10)=2^25 的页表项，非常大。

页表大了起来，检索速度也会变慢，因此提出了多级页表的方式，加快速度。以两级页表为例，第一层页表的每一项，指向第二层的一个页表。其中第一层页表又被叫做页目录。总共的页表项的数量是每一层级页表项数量的乘积。如下图，假设每个页表项为 4 字节，页大小 4KB，那么 4GB 的虚拟地址空间（也叫做用户地址空间）就需要 2^20 的页表项，需要 4MB 的页表。为了加快检索，而不用遍历那么多页表项去寻找匹配的虚拟地址，就采用了根页表，同时页表可以存放在虚拟内存中。

根页表的每一项的数据结构和普通页表类似，也是通过根页表的编号（也被称作页目录号）找到对应的页号（比如上图 4MB 的页表）,然后根据偏移地址确定具体对应页框号的页表项。

如果从虚拟地址的角度出发，那么就可以将虚拟地址分成 3 部分，第一个部分是根页表的项的编号，第二部分是第二级页表项的编号，第三部分是虚拟地址。同时第二部分也是根页表中的页内偏移量。也就是，单层页表的页表编号被拆分成两部分了。

另外一种优化技术是倒置页表，之前提到每个进程需要分配一个页表，所有进程的 PCB 记录着页表的起始地址。当进程很多时，多个页表也会占据大量内存空间。因此，通过虚拟地址寻找物理地址的数据的方式做了一些更改，首先计算 HASH(逻辑页号+进程ID)，然后在哈希表中通过链接指针找到（类似链表的方式）找到对应的一项，然后在这一项中获得页框号。这个哈希表就叫做倒置页表。

TLB 快表

之前的介绍中，通过页表查询的方式，往往需要两个步骤，首先是根据逻辑页号读取虚拟内存中的页表项，然后通过页表项中的物理页框号读取内存中的数据。实际上，我们可以通过高速缓存的方式提高速度。快表转换过程如下：一个虚拟地址寻找物理地址时，首先检查 TLB 中是否有页表项，如果有则直接得到物理页框号。如果没有，那么需要寻找到这个进程所在的页表，然后找到页表中的页表项，得到物理页框号，最后更新 TLB。

因此，完整的虚拟地址到物理地址的转过过程如下图

虽然 TLB 速度很快，但是空间有限。究竟哪些页表项需要放入 cache，页表项和 cache 的对应关系、更新方式等，都已经在计算机组成原理中学习过了。由于计算机操作系统的课程考核不要求这一部分，全相联、组相联这些内容暂时跳过。读者感兴趣的话，可以评论，日后我继续补充。

分段和段页式

类似于分页，每个进程一个段表，段表项也有存在位（对于段是否存在内存）、修改位（上次装入后是否修改）、其他控制位、段长度、段基址。和分页不同德是，物理地址的确定是段基址加上偏移量。分段的机制每个段都有长度和基址，那么限制只能访问当前段的内存，就可以控制非法访问，实现保护。一个段可以被多个进程引用，实现共享。

段页式的方式是分段和分页的结合，虚拟地址空间（也叫做用户地址空间）被程序员分成若干段，每段划分成若干页。每个进程一个段表、每个段一个页表。段表项包含了段长和页表起始地址等信息，页表项则包含了页框号等信息。

具体寻址过程如下，需要注意的就是段号寻找段表项，页号寻找页表项，都是需要加法。可以看到，访问段表、访问页表、读取内存数据，至少需要访问 3 次内存。

系统的存储管理

为了实现虚拟内存，操作系统需要实现读取策略（如何调入页）、放置策略（放在内存的哪个位置）、置换策略（把不需要的数据从内存置换出去）、驻留集管理（需要加载进程的哪些资源）等等。

读取策略主要关注请求调页和预调页。请求调页是指如何将需要的页面调入内存，避免缺页的发生和如何处理缺页。预调页是额外读取页面，相当于做好缓存，但是需要确定命中。如果额外读取的页面未使用，则低效。

放置策略是确定进程驻留在内存中的哪个位置，比如分区系统中的首次匹配、下次匹配等算法，就是属于这一类策略。

置换策略是读取新页时，选择淘汰哪些页面。置换做的好，把最不可能访问的页面淘汰，可以合理分配内存。锁定一些页框不淘汰，也可以降低缺页率。基本的置换算法如下：

最佳置换。置换下次访问距当前时间最长的页面。但是这很理想化，因为可能不知道所有页面未来读取的时间，除非已经知道未来页面的访问顺序了。
最近最少使用。置换最长时间未引用的页面。这就需要给页面增加最近访问的时间戳，开销大。
先进先出。采取严格的单向队列，按照循环的方式，删除最先进来的页面，也就是驻留在内存中时间最长的页面。问题明显，驻留时间最长，不代表不需要。
时钟置换。本质上是淘汰最近没有使用的页。规则如下：
- 当页面载入或者再次读取时，页面的使用位设置为 1。未使用的缓冲区，使用未设位 0.
- 当访问的页面不存在时，就会从指针的位置开始旋转，如果当前指针指向的页面的使用位为 1，那么就置为 0，继续到下一个位置。如果当前指向的页面使用位为 0，那么就就装入。
- 当命中时，指针位置不变。

驻留集管理指进程运行过程中哪些页面需要加载进来。这需要确定进程当前活动需要多少个页框，这可以固定分配，也可变分配。当发生缺页时，需要确定置换的范围，是在一个进程的空间中置换，还是允许整个内存的范围内置换。具体细节暂时放下。

IO 管理和磁盘调度

IO 控制方式

IO 的基本控制方式有轮询(忙等方式)、中断驱动、DMA、通道控制。

轮询是通过程序完成的，需要 IO 时会通过 CPU 给 IO 控制器发出命令，然后进程阻塞，CPU 不断轮询控制器的状态，直到就绪之后经过 CPU 读入内存。

中断驱动则智能一些，CPU 发送指令之后，如果是非阻塞的指令，那么继续执行进程，如果是阻塞的指令，则当前进程被换出，调度其他进程。CPU 不用轮询其他进程，而是等待 IO 控制器返回消息后，再执行需要这 IO 的程序。每次传输一个数据就会发送中断。

DMA 这个模块会直接和 IO 控制器通信，CPU 可以去做其他事情，DMA 直接向存储器读或写数据，等待 DMA 完成了所有事情，再通知 CPU 处理，这时 CPU 处理的工作切换了，发送中断。

	中断驱动	DMA
中断频率	每次传输一个数据即产生中断。	一块数据全部传送结束时才中断 CPU。
数据传输	数据传送在中断处理时由 CPU 控制完成。	数据传送在 DMA 控制器的控制下完成。

可以知道，中断适合小数据快速传输，DMA 适合大数据传输。

通道控制，某些 IO 设备（如存储器）需要被多用户共用，那么就可能存在多通道，每个通道又由多个控制器管理，每个控制器又连接多个设备。通道控制是 DMA 的升级版本，有自己的 IO 指令集，甚至自己就是微型计算机，并行的操作，读取速度更加快。

IO 缓冲

缓冲是指发出读取请求之前就开始读取数据，发出写入请求一段时间后才开始写入数据。

没有缓冲时，数据单次的到达进程或者从进程送出，那么每次数据传输都需要计算和整个 IO 过程的时间。
当采用单缓冲时，进程的多次数据请求时，就可以一边计算一边缓冲，然后整个的传输到进程。这节省了传输时间。
双缓冲有两个缓冲区，系统使用一个缓冲区传输数据时，就可以填充另外一个缓冲区，这样切换着执行，就几乎感受不到数据存设备读取到内存的时间。多个缓冲区时，原理也是类似的。

缓冲缓解了 IO 设备速度太慢的问题，相比 CPU 的执行速度，IO 设备先攒一波，再传输数据，可以减少 CPU 等待时间和中断数量。

磁盘中的缓冲技术中典型的有SPOOLing，它在磁盘中建立 IO 缓冲区，对 IO 设备的输入和从 IO 设备的读取，都在磁盘的这个区域进行。也就是说，在计算机中开辟一块存储位置，用来缓冲 IO，程序实际读取的数据来此这个缓冲区（更具体的是通过输入井和输出井），而缓冲区作为操作系统和 IO 设备之间的中介或者代理。所以 SPOOLing 的全称叫做 Simultaneous Peripheral Operation On-Line，同步同时的外设操作。国内翻译直接叫做假脱机，也是这个意思。

另外，磁盘内部可能也存在缓冲区，在缓存没有用光的情况下，速度会快很多。管理缓冲区的策略有 LRU(Least Recently Used)，它置换出最近最久没有使用的块；也有 LFU (Least Frequently Used)，置换出最近访问次数最少的块。

磁盘的结构和读取过程

磁盘存储器的基本结构包括了物理盘片，每个磁盘片可能有一个或者两个存储面。每个存储面被划分成若干个同心圆，每个圆环就叫做磁道。每条圆环状的磁道划分成若干个扇区，层叠起来的不同盘片的相同的磁道就叫做柱面。

读取和写入数据的是磁头，有的是每个盘面一个磁头，有的则更加高级，一个盘面上多个磁头，对应着盘面上的磁道。磁头有固定读取某个磁道的类型，也有可以移动到指定磁道的类型。磁盘会高速旋转，这样就实现了读取全盘。

磁盘的读取过程大致如下：在磁头可移动系统中，将磁头臂移动到指定磁道，磁头定位到指定磁道后，等待磁盘旋转，将待访问的扇区移动到磁头位置，向磁盘传送或从磁盘传送数据的时间，取决于磁盘的旋转速度。

因此磁盘的读取的时间主要有三部分：寻道时间、旋转延迟、传输时间。寻道时间一般是给定的。旋转延迟一般取平均，也就是 $T_r=1/(2r)$ ，其中 r 表示磁盘旋转速度，一般单位是每分钟多少转 rpm。 $T_t$ 为传输时间，b 表示要传送的字节数，r 表示旋转速度，N 表示一个磁道中的字节数，那么传输时间为 $T_t=b/(rN)$ 。

根据以上的规则，看一个示例：考虑一个典型的磁盘，平均寻道时间为 4ms，转速为 7500r/m，每个磁道有 500 个扇区，每个扇区有 512 个字节。假设有一个文件存放在 2500 个扇区上，估算下列两种情况下读取该文件需要的时间。（1）2500 个扇区分别位于 5 个相邻磁道上，且文件按扇区顺序存放；（2）2500 个扇区随机分布。

（1）转速换算 7500rpm=0.125r/ms，寻道时间 4ms，旋转延迟 1/(2*0.125)=4ms，读取一个扇区的时间 512/(500*512*0.125)=0.016ms。所以连续读取 5 个磁道需要 4ms+4ms*5+0.016ms*2500= 64 ms。相邻磁道的寻道时间可以忽略

（2）如果随机分布的话，读写的三个过程必须都出现，2500*(4+4+0.016)ms=20040ms

磁盘调度策略

因为磁头的位置一次只能处理一个请求，如果能够合理调度请求，让上面提到的时间综合起来最短，这就是磁盘调度得目标。

FIFO 先进先出，根据进程请求访问磁盘的先后顺序，处理访问的需求。但是大量进程竞争磁盘时，性能接近随机调度。

PRI 优先级，根进程读取磁盘安排优先级。

LIFO 后进先出优先处理新到的请求。

SSTF 最短寻道时间优先选择移动到距离前位置最近的磁道。

SCAN 电梯算法磁头只沿着一个方向移动到尽头，然后再往反方向走。

**C-SCAN (Circular SCAN)**当磁臂沿指定方向扫描到磁盘最后一个磁道时，磁臂返回到反方向末端，再次沿指定方向扫描。记住这是单方向扫描。因为在末端位置的时候，已经扫描过的边缘位置，可能没有必要立即再扫描一遍。

C-LOOK 在 C-SCAN 基础上改进，当前方向没有其他请求时，直接到另外一个方向最末端的请求，然后重新开始单方向扫描。

FSCAN 使用两个子队列，扫描开始时，所有请求放在一个队列中，另外一个队列为空。在扫描过程中，新到来的请求放在另外一个队列中，当原来队列里的请求处理完毕之后，才会处理另外一个队列。

RAID

独立磁盘冗余阵列（RAID）是将多个独立的磁盘组成在一起形成一个大的磁盘系统，从而实现比单块磁盘更好的存储性能和更高的可靠性。具体来说，操作系统的眼中它是一个单一设备，但是它的整体性使得单一设备失效的时候，可以通过奇偶校验信息恢复数据，数据并不是单纯地存放在物理驱动器中，而是分布在各个硬盘中，实现条带化，进而实现高性能读取和容错。

RAID 分成多个等级

level 0 不提供冗余功能，数据被划分成多个条带，条带映射到物理磁盘中。
level 1 通过简单映像提供冗余功能，没有校验恢复功能，相当于直接备份。写入无优势，但是读取时会快一些。
level 2 实现了并行访问数据，提供了数据的校验。往往条带非常小，通过存储每个条带的汉明码确保数据的完整性。
…更多的不细究了。

文件系统

这一节，我们更像是了解文件系统是任何设计的，如果读者可以结合自身对 Windows 和 Linux 文件的经验，那么许多部分将会非常好理解。

文件系统是操作系统的重要组成部分，文件需要以一定的方式组织成特定的结构，然后长期的储存并且被进程访问。文件系统需要提供文件操作的接口，最典型的就是创建、删除、打开、关闭、读写等。文件系统还需要满足数据的管理、权限管理、IO 需求、多用户支持、性能优化等需求。

设备驱动处于最底层，直接和外设通信，负责和控制器通信，给设备发出 IO 请求。基本文件系统则是处理数据存放在外存哪个位置。基本 IO 管理程序则关注磁盘调度、IO 设备调度。逻辑 IO 则是访问记录（记录是指一组基本数据单元的集合）和维护文件储存的基本数据。最上面一层则应给用户提供 IO 的接口，支持各自操作。

文件组织

文件组织关注文件中记录的逻辑结构，一般需要满足五个原则：快速访问、易于修改、节约存储空间、易于维护、可靠。

堆文件是最简单的文件组织方式，数据按照任意顺序排列，记录是变长的，就像随意堆积一样，搜索文件时只能穷举。

顺序文件顾名思义就是按照一定的顺序排序，记录是定长的。

索引顺序文件在顺序文件的基础上（比如还是保持顺序），添加了文件的关键特征，也就是文件的索引。当添加新的文件时，可以使用索引指向这个文件（溢出文件），然后插入在主文件中，不必实际地移动溢出文件。

索引文件则只能通过索引访问记录。

**直接文件（散列文件）**可以通过哈希直接访问任何地址地数据块。

文件目录

根据常识，文件的目录需要包括文件名、文件类型（比如文本文件或者二进制文件）、文件组织（比如目录层级）。从存储的地址方面，需要指示存储在哪个设备（卷）、外存的起始物理地址、文件存储的实际大小、文件大小最大限制。从访问控制的角度来说，需要确定所有者、访问信息（比如密码之类的）、各类用户权限信息。从使用信息来说，需要包括文件的创建时间、创建者、最后一次访问时间、最后一次访问用户、最后一次修改日期、最后一次修改者身份等。

目录的结构包括单级结构、两级结构、层次结构等。

单级目录相当于简单的列表，整个文件系统只有一张目录表，每个目录项对应一个文件。可知，文件名字是不准重复的，而且查找速度慢。

两级结构则分成主目录和用户目录。主目录给每个用户一个目录项，用户目录则是简单的列表

树状结构则可以包含多级目录，每个目录可以包含文件，也可以包含目录。所有的目录都是由根目录引出。任何文件都可以从根目录向下到各个分支来定位。多个文件可以同名，但是确保路径名是唯一的。

无循环图结构在树型目录的基础上，允许多个目录项指向同一个数据文件或者目录文件，相当于多了软链接。

文件共享

当文件允许共享时时，就会出现权限控制和并发控制的问题。权限可以大致分成读、写、执行，更加细化可以分成追加、更新、改变权限、删除等。和文件权限相关的用户身份有所有者、特定用户、组用户和全部。 Unix 一般是通过链接实现文件共享。

硬链接是将多个文件名链接到同一个索引节点，索引节点会记录引用次数，如果减到 0 那么文件就会被删除。链接文件和被链接文件必须位于同一个文件系统中，而且不允许目录链接。

软链接又叫符号链接，软链接文件完全不会影响原文件，它们是互相独立的。

外存管理

外存就是各种磁盘之类的存储设备，在外存中，文件由许多的块组成。这些块有三种组织方式定长组块（每个块大小相同）、变长非跨越组块（每个块大小不同且物理上必须连续）、变长跨越组块。

文件系统会将外存分成一个或多个由一组连续分配的块组成的区域，叫做分区。FAT（文件分配表）会跟踪分区中的数据结构。文件分配到分区的过程中有预分配和动态分配两种方式。预分配需要在文件创建时声明文件的最大尺寸，动态分配在需要时才给文件分配空间。文件分配时，连续分配的方式是文件由在外存中连续的块组成，隐式的链式分配则是类似链表，块串在一块，如果要优化读写也可以合并，变成连续分配。显式链接则有些不同，不是采用链表，而是将物理块的指针存储在 FAT 表中。早期的 DOS 系统 FAT12 文件系统，FAT 表里每个项用于表示物理块号的位数是 12 比特，所以如果采用显式链接的链式分配，最多支持有 2^12 个物理块。

实际在操作系统中，并不会精确到每一个扇区去存储，可是采用簇作为最小单位，一个文件的占用空间大小只能是簇的整数倍。簇越大，越适合大文件的存储，可以节省 FAT 的表项，便于管理。但是存储小文件时，占用空间可能会远超过实际大小。

除了 FAT（文件分配表）会记录哪些块被使用了，**DAT（磁盘分配表）**用于记录哪些空间没有被使用。DAT 的结构有如下几种情况：

位表，Bit Tables。使用一个很长的比特向量，向量的每一位对应磁盘中的每一块，用 0 表示空闲，1 表示占用。
链接空闲分区。采取类似链表的方式，记录下一个空闲区的位置和长度，只需要知道第一个空闲分区的信息即可。
索引。使用索引表记录空闲空间。
空白块列表。每个块指定一个序号，把所有空闲块的序号保存在磁盘中。

卷在本质上是指逻辑磁盘，是一组在外存上可寻址的扇区的集合，操作系统或应用程序用卷来存储数据。而分区是连续物理块的集合。

UNIX 文件管理

UNIX 将文件分成 6 类：

普通文件（Regular, or ordinary），可以视作字节流，可以存储任意数据。
目录（Directory），包含文件名的列表和指向它的索引节点的指针。
特殊文件（Special），不包含数据，用于物理设备映射到一个文件名。
命名管道（Named pipes），用于进程间通信。
链接文件（Links），硬链接，相当于文件别名。
符号链接（Symbolic links），相当于软链接。

UNIX 的所有文件都是通过所有节点管理的，索引节点包含了操作系统需要的文件的所有关键信息。下图就是一个索引节点，它自身就有很多的控制信息，然后包括了指向其他指针的指针和数据的指针。

值得关注的是，指针可以分成多级，每一级可以管理数据的数量指数级增加。而且数据的存储是采用动态分配的方式，按需分配大小。

示例：设文件索引节点中有 7 个地址项，其中 4 个地址项为直接地址索引，2 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4 字节，若磁盘索引块和磁盘数据块大小均为 256 字节，则可表示的单个文件的最大长度是？

根据上图的结构可以看到，直接地址直接指向数据块，也就是 4*256=1024 字节=1KB。一级间接地址项指向的索引项（注意地址项指向索引块）大小为 256 字节，4 字节一个地址，那么就有 64 个地址项，指向了 64 个数据块。所以支持 2*64*256 B= 32KB。二级间接地址以此类推，1*64*64*256B=1024KB。所以这个索引节点最大支持的文件大小是直接块和间接块之后，也就是 1+32+1024=1057KB。