操作系统面试题（史上最全、持续更新）

后续基本上，每一个月，都会发布一次，最新版本，可以联系构师尼恩获取， 发送 “领取电子书” 获取。

在信息化时代，软件被称为计算机系统的灵魂。而作为软件核心的操作系统，已经与现代计算机系统密不可分、融为一体。计算机系统自下而上可粗分为四个部分：硬件、操作系统、应用程序和用户。操作系统管理各种计算机硬件，为应用程序提供基础，并充当计算机硬件和用户的中介。

硬件，如中央处理器、内存、输入输出设备等，提供了基本的计算资源。应用程序，如字处理程序、电子制表软件、编译器、网络浏览器等，规定了按何种方式使用这些资源来解决用户的计算问题。操作系统控制和协调各用户的应用程序对硬件的使用。

综上所述，操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理的组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境集合。计算机操作系统是随着计算机研究和应用的发展逐步形成并发展起来的，它是计算机系统中最基本的系统软件。

操作系统是一种系统软件，但与其他的系统软件和应用软件有很大的不同，他有自己的特殊性即基本特征，操作系统的基本特征包括并发、共享、虚拟和异步。这些概念对理解和掌握操作系统的核心至关重要。

并发是指两个或多个事件在同一时间间隔内发生，在多道程序环境下，一段时间内宏观上有多个程序在同时执行，而在同一时刻，单处理器环境下实际上只有一个程序在执行，故微观上这些程序还是在分时的交替进行。操作系统的并发是通过分时得以实现的。操作系统的并发性是指计算机系统中同时存在多个运行着的程序，因此它具有处理和调度多个程序同时执行的能力。在操作系统中，引入进程的目的实施程序能并发执行。

资源共享即共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。共享可以分为以下两种资源共享方式。

系统中的某些资源，，如打印机、磁带机，虽然他们可以提供给多个进程使用，但为使所打印的内容不致造成混淆，应规定在同一段时间内只允许一个进程方位该资源。

为此，当进程a访问某资源时，必须先提出请求，如果此时该资源空闲，系统便可将之分配给进程a使用，伺候若再有其他进程也要访问该资源（只要a未用完）则必须等待。仅当进程a访问完并释放该资源后，才允许另一进城对该资源进行访问。计算机系统中的大所属物理设备，以及某些软件中所用的栈、变量和表格，都属于临界资源，他们都要求被互斥的共享。

系统中还有一种资源，允许在一段时间内由多个进程“同时”对它进行访问。这里所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替的对该资源进行访问即“分时共享”。典型的可供多个进程同时访问的资源是磁盘设备，一些用重入码编写的文件也可以被 “同时” 共享，即若干个用户同时访问该文件。

并发和共享是操作系统两个最基本的特征，这两者之间又是互为存在条件的：1资源共享是以程序的并发为条件的，若系统不允许程序并发执行，则自然不存在资源共享的问题；2若系统不能对资源共享实施有效地管理，也必将影响到程序的并发执行，甚至根本无法并发执行。

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体是实的，即实际存在的；而后者是虚的，是用户感觉上的事物。相应的，用于实现虚拟的技术，成为虚拟技术。在操作系统中利用了多种虚拟技术，分别用来实现虚拟处理器、虚拟内存和虚拟外部设备。

在虚拟处理器技术中，是通过多道程序设计技术，让多道程序并发执行的方法，来分时使用一台处理器的。此时，虽然只有一台处理器，但他能同时为多个用户服务，是每个终端用户都认为是有一个中央处理器在为他服务。利用多道程序设计技术，把一台物理上的 CPU 虚拟为多台逻辑上的 CPU，称为虚拟处理器。

类似的，可以通过虚拟存储器技术，将一台机器的物理存储器变为虚拟存储器，一边从逻辑上来扩充存储器的容量。当然， 这是用户所感觉到的内存容量是虚的，我们把用户所发哦绝倒的存储器程序虚拟存储器。

还可以通过虚拟设备技术，将一台物理IO设备虚拟为多台逻辑上的IO设备，并允许每个用户占用一台逻辑上的 IO 设备，这样便可使原来仅允许在一段时间内有一个用户访问的设备，变为在一段时间内允许多个用户同时访问的共享设备。

因此操作系统的虚拟技术可归纳为：时分复用技术和空分复用技术。

在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

异步性使得操作系统运行在一种随机的环境下，可能导致进程产生于时间有关的错误。但是只要运行环境相同，操作系统必须保证多次运行进程，都获得相同的结果。

一般来说，操作系统可以分为五大管理功能部分：

操作系统的类型也可以分为几种：批处理系统，分时操作系统，实时操作系统，网络操作系统等。下面将简单的介绍他们各自的特点：

操作系统是管理硬件和软件的一种应用程序。操作系统是运行在计算机上最重要的一种软件，它管理计算机的资源和进程以及所有的硬件和软件。它为计算机硬件和软件提供了一种中间层，使应用软件和硬件进行分离，让我们无需关注硬件的实现，把关注点更多放在软件应用上。

通常情况下，计算机上会运行着许多应用程序，它们都需要对内存和 CPU 进行交互，操作系统的目的就是为了保证这些访问和交互能够准确无误的进行。

一般来说，现代操作系统主要提供下面几种功能

软件访问硬件其实就是一种 IO 操作，软件访问硬件的方式，也就是 I/O 操作的方式有哪些。

硬件在 I/O 上大致分为并行和串行，同时也对应串行接口和并行接口。

随着计算机技术的发展，I/O 控制方式也在不断发展。选择和衡量 I/O 控制方式有如下三条原则

（1） 数据传送速度足够快，能满足用户的需求但又不丢失数据；

（2） 系统开销小，所需的处理控制程序少；

（3） 能充分发挥硬件资源的能力，使 I/O 设备尽可能忙，而 CPU 等待时间尽可能少。

根据以上控制原则，I/O 操作可以分为四类

上述两种方法的特点都是以 CPU 为中心，数据传送通过一段程序来实现，软件的传送手段限制了数据传送的速度。接下来介绍的这两种 I/O 控制方式采用硬件的方法来显示 I/O 的控制

操作系统是一种软件，它的主要目的有三种

操作系统通常预装在你购买计算机之前。大部分用户都会使用默认的操作系统，但是你也可以升级甚至更改操作系统。但是一般常见的操作系统只有三种：Windows、macOS 和 Linux。

这是一个老生常谈的问题了，在这里给出具体的回答。

其中一点是因为 Linux 系统和 Windows 系统的格式不同，格式就是协议，就是在固定位置有意义的数据。Linux 下的可执行程序文件格式是 elf，可以使用 readelf 命令查看 elf 文件头。

而 Windows 下的可执行程序是 PE 格式，它是一种可移植的可执行文件。

还有一点是因为 Linux 系统和 Windows 系统的 API 不同，这个 API 指的就是操作系统的 API，Linux 中的 API 被称为系统调用，是通过 int 0x80 这个软中断实现的。而 Windows 中的 API 是放在动态链接库文件中的，也就是 Windows 开发人员所说的 DLL ，这是一个库，里面包含代码和数据。Linux 中的可执行程序获得系统资源的方法和 Windows 不一样，所以显然是不能在 Windows 中运行的。

在大多数系统中，整个系统在内核态以单一程序的方式运行。整个操作系统是以程序集合来编写的，链接在一块形成一个大的二进制可执行程序，这种系统称为单体系统。

在单体系统中构造实际目标程序时，会首先编译所有单个过程（或包含这些过程的文件），然后使用系统链接器将它们全部绑定到一个可执行文件中

在单体系统中，对于每个系统调用都会有一个服务程序来保障和运行。需要一组实用程序来弥补服务程序需要的功能，例如从用户程序中获取数据。可将各种过程划分为一个三层模型

除了在计算机初启动时所装载的核心操作系统外，许多操作系统还支持额外的扩展。比如 I/O 设备驱动和文件系统。这些部件可以按需装载。在 UNIX 中把它们叫做 共享库(shared library)，在 Windows 中则被称为 动态链接库(Dynamic Link Library,DLL)。他们的扩展名为 .dll，在 C:\Windows\system32 目录下存在 1000 多个 DLL 文件，所以不要轻易删除 C 盘文件，否则可能就炸了哦。

分层系统使用层来分隔不同的功能单元。每一层只与该层的上层和下层通信。每一层都使用下面的层来执行其功能。层之间的通信通过预定义的固定接口通信。

为了实现高可靠性，将操作系统划分成小的、层级之间能够更好定义的模块是很有必要的，只有一个模块 — 微内核 — 运行在内核态，其余模块可以作为普通用户进程运行。由于把每个设备驱动和文件系统分别作为普通用户进程，这些模块中的错误虽然会使这些模块崩溃，但是不会使整个系统死机。

MINIX 3 是微内核的代表作，它的具体结构如下

在内核的外部，系统的构造有三层，它们都在用户态下运行，最底层是设备驱动器。由于它们都在用户态下运行，所以不能物理的访问 I/O 端口空间，也不能直接发出 I/O 命令。相反，为了能够对 I/O 设备编程，驱动器构建一个结构，指明哪个参数值写到哪个 I/O 端口，并声称一个内核调用，这样就完成了一次调用过程。

微内核思想的策略是把进程划分为两类：服务器，每个服务器用来提供服务；客户端，使用这些服务。这个模式就是所谓的 客户-服务器模式。

客户-服务器模式会有两种载体，一种情况是一台计算机既是客户又是服务器，在这种方式下，操作系统会有某种优化；但是普遍情况下是客户端和服务器在不同的机器上，它们通过局域网或广域网连接。

客户通过发送消息与服务器通信，客户端并不需要知道这些消息是在本地机器上处理，还是通过网络被送到远程机器上处理。对于客户端而言，这两种情形是一样的：都是发送请求并得到回应。

如果把软件结构进行分层说明的话，应该是这个样子的，最外层是应用程序，里面是操作系统内核。

应用程序处于特权级 3，操作系统内核处于特权级 0 。如果用户程序想要访问操作系统资源时，会发起系统调用，陷入内核，这样 CPU 就进入了内核态，执行内核代码。至于为什么是陷入，我们看图，内核是一个凹陷的构造，有陷下去的感觉，所以称为陷入。

用户态和内核态是操作系统的两种运行状态。

那么为什么要有用户态和内核态呢？

这个主要是访问能力的限制的考量，计算机中有一些比较危险的操作，比如设置时钟、内存清理，这些都需要在内核态下完成，如果随意进行这些操作，那你的系统得崩溃多少次。

所有的用户进程都是运行在用户态的，但是我们上面也说了，用户程序的访问能力有限，一些比较重要的比如从硬盘读取数据，从键盘获取数据的操作则是内核态才能做的事情，而这些数据却又对用户程序来说非常重要。所以就涉及到两种模式下的转换，即用户态 -> 内核态 -> 用户态，而唯一能够做这些操作的只有 系统调用，而能够执行系统调用的就只有 操作系统。

一般用户态 -> 内核态的转换我们都称之为 trap 进内核，也被称之为 陷阱指令(trap instruction)。

他们的工作流程如下：

在计算机中，内核是一个计算机程序，它是操作系统的核心，可以控制操作系统中所有的内容。内核通常是在 boot loader 装载程序之前加载的第一个程序。

这里还需要了解一下什么是 boot loader。

boot loader 又被称为引导加载程序，能够将计算机的操作系统放入内存中。在电源通电或者计算机重启时，BIOS 会执行一些初始测试，然后将控制权转移到引导加载程序所在的主引导记录(MBR) 。

实时操作系统对时间做出了严格的要求，实时操作系统分为两种：硬实时和软实时

硬实时操作系统规定某个动作必须在规定的时刻内完成或发生，比如汽车生产车间，焊接机器必须在某一时刻内完成焊接，焊接的太早或者太晚都会对汽车造成永久性伤害。

软实时操作系统虽然不希望偶尔违反最终的时限要求，但是仍然可以接受。并且不会引起任何永久性伤害。比如数字音频、多媒体、手机都是属于软实时操作系统。

你可以简单理解硬实时和软实时的两个指标：是否在时刻内必须完成以及是否造成严重损害。

当计算机电源通电后，BIOS会进行开机自检(Power-On-Self-Test, POST)，对硬件进行检测和初始化。因为操作系统的启动会使用到磁盘、屏幕、键盘、鼠标等设备。

下一步，磁盘中的第一个分区，也被称为 MBR(Master Boot Record) 主引导记录，被读入到一个固定的内存区域并执行。这个分区中有一个非常小的，只有 512 字节的程序。程序从磁盘中调入 boot 独立程序，boot 程序将自身复制到高位地址的内存从而为操作系统释放低位地址的内存。

复制完成后，boot 程序读取启动设备的根目录。boot 程序要理解文件系统和目录格式。然后 boot 程序被调入内核，把控制权移交给内核。直到这里，boot 完成了它的工作。系统内核开始运行。

内核启动代码是使用汇编语言完成的，主要包括创建内核堆栈、识别 CPU 类型、计算内存、禁用中断、启动内存管理单元等，然后调用 C 语言的 main 函数执行操作系统部分。

这部分也会做很多事情，首先会分配一个消息缓冲区来存放调试出现的问题，调试信息会写入缓冲区。如果调试出现错误，这些信息可以通过诊断程序调出来。

然后操作系统会进行自动配置，检测设备，加载配置文件，被检测设备如果做出响应，就会被添加到已链接的设备表中，如果没有相应，就归为未连接直接忽略。

配置完所有硬件后，接下来要做的就是仔细手工处理进程0，设置其堆栈，然后运行它，执行初始化、配置时钟、挂载文件系统。创建 init 进程(进程 1 ) 和 守护进程(进程 2)。

init 进程会检测它的标志以确定它是否为单用户还是多用户服务。在前一种情况中，它会调用 fork 函数创建一个 shell 进程，并且等待这个进程结束。后一种情况调用 fork 函数创建一个运行系统初始化的 shell 脚本（即 /etc/rc）的进程，这个进程可以进行文件系统一致性检测、挂载文件系统、开启守护进程等。

然后 /etc/rc 这个进程会从 /etc/ttys 中读取数据，/etc/ttys 列出了所有的终端和属性。对于每一个启用的终端，这个进程调用 fork 函数创建一个自身的副本，进行内部处理并运行一个名为 getty 的程序。

getty 程序会在终端上输入

等待用户输入用户名，在输入用户名后，getty 程序结束，登陆程序 /bin/login 开始运行。login 程序需要输入密码，并与保存在 /etc/passwd 中的密码进行对比，如果输入正确，login 程序以用户 shell 程序替换自身，等待第一个命令。如果不正确，login 程序要求输入另一个用户名。

整个系统启动过程如下

在未配置 OS 的系统中，程序的执行方式是顺序执行，即必须在一个程序执行完后，才允许另一个程序执行；在多道程序环境下，则允许多个程序并发执行。程序的这两种执行方式间有着显著的不同。也正是程序并发执行时的这种特征，才导致了在操作系统中引入进程的概念。进程是资源分配的基本单位，线程是资源调度的基本单位。

应用启动体现的就是静态指令加载进内存，进而进入 CPU 运算，操作系统在内存开辟了一段栈内存用来存放指令和变量值，从而形成了进程。早期的操作系统基于进程来调度 CPU，不同进程间是不共享内存空间的，所以进程要做任务切换就要切换内存映射地址。由于进程的上下文关联的变量，引用，计数器等现场数据占用了打段的内存空间，所以频繁切换进程需要整理一大段内存空间来保存未执行完的进程现场，等下次轮到 CPU 时间片再恢复现场进行运算。

这样既耗费时间又浪费空间，所以我们才要研究多线程。一个进程创建的所有线程，都是共享一个内存空间的，所以线程做任务切换成本就很低了。现代的操作系统都基于更轻量的线程来调度，现在我们提到的 “任务切换” 都是指 “线程切换”。

进程是操作系统对一个正在运行的程序的一种抽象，在一个系统上可以同时运行多个进程，而每个进程都好像在独占地使用硬件。所谓的并发运行，则是说一个进程的指令和另一个进程的指令是交错执行的。无论是在单核还是多核系统中，可以通过处理器在进程间切换，来实现单个 CPU 看上去像是在并发地执行多个进程。操作系统实现这种交错执行的机制称为上下文切换。

操作系统保持跟踪进程运行所需的所有状态信息。这种状态，也就是上下文，它包括许多信息，例如 PC 和寄存器文件的当前值，以及主存的内容。在任何一个时刻，单处理器系统都只能执行一个进程的代码。当操作系统决定要把控制权从当前进程转移到某个新进程时，就会进行上下文切换，即保存当前进程的上下文、恢复新进程的上下文，然后将控制权传递到新进程。新进程就会从上次停止的地方开始。

操作系统为每个进程提供了一个假象，即每个进程都在独占地使用主存。每个进程看到的是一致的存储器，称为虚拟地址空间。其虚拟地址空间最上面的区域是为操作系统中的代码和数据保留的，这对所有进程来说都是一样的；地址空间的底部区域存放用户进程定义的代码和数据。

程序代码和数据：对于所有的进程来说，代码是从同一固定地址开始，直接按照可执行目标文件的内容初始化。

堆：代码和数据区后紧随着的是运行时堆。代码和数据区是在进程一开始运行时就被规定了大小，与此不同，当调用如 malloc 和 free 这样的 C 语言 标准库函数时，堆可以在运行时动态地扩展和收缩。

共享库：大约在地址空间的中间部分是一块用来存放像 C 标准库和数学库这样共享库的代码和数据的区域。

栈：位于用户虚拟地址空间顶部的是用户栈，编译器用它来实现函数调用。和堆一样，用户栈在程序执行期间可以动态地扩展和收缩。

内核虚拟存储器：内核总是驻留在内存中，是操作系统的一部分。地址空间顶部的区域是为内核保留的，不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数。

在现代系统中，一个进程实际上可以由多个称为线程的执行单元组成，每个线程都运行在进程的上下文中，并共享同样的代码和全局数据。进程的个体间是完全独立的，而线程间是彼此依存的。多进程环境中，任何一个进程的终止，不会影响到其他进程。而多线程环境中，父线程终止，全部子线程被迫终止(没有了资源)。

而任何一个子线程终止一般不会影响其他线程，除非子线程执行了 exit() 系统调用。任何一个子线程执行 exit()，全部线程同时灭亡。多线程程序中至少有一个主线程，而这个主线程其实就是有 main 函数的进程。它是整个程序的进程，所有线程都是它的子线程；我们通常把具有多线程的主进程称之为主线程。

线程共享的环境包括：进程代码段、进程的公有数据、进程打开的文件描述符、信号的处理器、进程的当前目录、进程用户 ID 与进程组 ID 等，利用这些共享的数据，线程很容易的实现相互之间的通讯。线程拥有这许多共性的同时，还拥有自己的个性，并以此实现并发性：

线程 ID：每个线程都有自己的线程 ID，这个 ID 在本进程中是唯一的。进程用此来标识线程。

寄存器组的值：由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线程切换到另一个线程上时，必须将原有的线程的寄存器集合的状态保存，以便 将来该线程在被重新切换到时能得以恢复。

线程的堆栈：堆栈是保证线程独立运行所必须的。线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程必须拥有自己的函数堆栈， 使得函数调用可以正常执行，不受其他线程的影响。

错误返回码：由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调用后设置了 errno 值，而在该 线程还没有处理这个错误，另外一个线程就在此时 被调度器投入运行，这样错误值就有可能被修改。 所以，不同的线程应该拥有自己的错误返回码变量。

线程的信号屏蔽码：由于每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都共享同样的信号处理器。

线程的优先级：由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数就是线程的优先级。

当线程在用户空间下实现时，操作系统对线程的存在一无所知，操作系统只能看到进程，而不能看到线程。所有的线程都是在用户空间实现。在操作系统看来，每一个进程只有一个线程。过去的操作系统大部分是这种实现方式，这种方式的好处之一就是即使操作系统不支持线程，也可以通过库函数来支持线程。

在这在模型下，程序员需要自己实现线程的数据结构、创建销毁和调度维护。也就相当于需要实现一个自己的线程调度内核，而同时这些线程运行在操作系统的一个进程内，最后操作系统直接对进程进行调度。

这样做有一些优点，首先就是确实在操作系统中实现了真实的多线程，其次就是线程的调度只是在用户态，减少了操作系统从内核态到用户态的切换开销。这种模式最致命的缺点也是由于操作系统不知道线程的存在，因此当一个进程中的某一个线程进行系统调用时，比如缺页中断而导致线程阻塞，此时操作系统会阻塞整个进程，即使这个进程中其它线程还在工作。还有一个问题是假如进程中一个线程长时间不释放 CPU，因为用户空间并没有时钟中断机制，会导致此进程中的其它线程得不到 CPU 而持续等待。

内核线程就是直接由操作系统内核（Kernel）支持的线程，这种线程由内核来完成线程切换，内核通过操纵调度器（Scheduler）对线程进行调度，并负责将线程的任务映射到各个处理器上。每个内核线程可以视为内核的一个分身，这样操作系统就有能力同时处理多件事情，支持多线程的内核就叫做多线程内核（Multi-Threads Kernel）。

程序员直接使用操作系统中已经实现的线程，而线程的创建、销毁、调度和维护，都是靠操作系统（准确的说是内核）来实现，程序员只需要使用系统调用，而不需要自己设计线程的调度算法和线程对 CPU 资源的抢占使用。

在这种混合实现下，即存在用户线程，也存在轻量级进程。用户线程还是完全建立在用户空间中，因此用户线程的创建、切换、析构等操作依然廉价，并且可以支持大规模的用户线程并发。而操作系统提供支持的轻量级进程则作为用户线程和内核线程之间的桥梁，这样可以使用内核提供的线程调度功能及处理器映射，并且用户线程的系统调用要通过轻量级进程来完成，大大降低了整个进程被完全阻塞的风险。在这种混合模式中，用户线程与轻量级进程的数量比是不定的，即为 N:M 的关系：

Golang 的协程就是使用了这种模型，在用户态，协程能快速的切换，避免了线程调度的 CPU 开销问题，协程相当于线程的线程。

在 Linux 2.4 版以前，线程的实现和管理方式就是完全按照进程方式实现的；在 Linux 2.6 之前，内核并不支持线程的概念，仅通过轻量级进程（Lightweight Process）模拟线程；轻量级进程是建立在内核之上并由内核支持的用户线程，它是内核线程的高度抽象，每一个轻量级进程都与一个特定的内核线程关联。内核线程只能由内核管理并像普通进程一样被调度。这种模型最大的特点是线程调度由内核完成了，而其他线程操作（同步、取消）等都是核外的线程库（Linux Thread）函数完成的。

为了完全兼容 Posix 标准，Linux 2.6 首先对内核进行了改进，引入了线程组的概念（仍然用轻量级进程表示线程），有了这个概念就可以将一组线程组织称为一个进程，不过内核并没有准备特别的调度算法或是定义特别的数据结构来表征线程；相反，线程仅仅被视为一个与其他进程（概念上应该是线程）共享某些资源的进程（概念上应该是线程）。在实现上主要的改变就是在 task_struct 中加入 tgid 字段，这个字段就是用于表示线程组 id 的字段。在用户线程库方面，也使用 NPTL 代替 Linux Thread，不同调度模型上仍然采用 1 对 1 模型。

进程的实现是调用 fork 系统调用：pid_t fork(void);，线程的实现是调用 clone 系统调用：int clone(int (*fn)(void *), void *child_stack, int flags, void *arg, ...)。与标准 fork() 相比，线程带来的开销非常小，内核无需单独复制进程的内存空间或文件描写叙述符等等。这就节省了大量的 CPU 时间，使得线程创建比新进程创建快上十到一百倍，能够大量使用线程而无需太过于操心带来的 CPU 或内存不足。无论是 fork、vfork、kthread_create 最后都是要调用 do_fork，而 do_fork 就是根据不同的函数参数，对一个进程所需的资源进行分配。

内核线程是由内核自己创建的线程，也叫做守护线程（Deamon），在终端上用命令 ps -Al 列出的所有进程中，名字以 k 开关以 d 结尾的往往都是内核线程，比如 kthreadd、kswapd 等。与用户线程相比，它们都由 do_fork() 创建，每个线程都有独立的 task_struct 和内核栈；也都参与调度，内核线程也有优先级，会被调度器平等地换入换出。二者的不同之处在于，内核线程只工作在内核态中；而用户线程则既可以运行在内核态（执行系统调用时），也可以运行在用户态；内核线程没有用户空间，所以对于一个内核线程来说，它的 0~3G 的内存空间是空白的，它的 current->mm 是空的，与内核使用同一张页表；而用户线程则可以看到完整的 0~4G 内存空间。

在 Linux 内核启动的最后阶段，系统会创建两个内核线程，一个是 init，一个是 kthreadd。其中 init 线程的作用是运行文件系统上的一系列”init”脚本，并启动 shell 进程，所以 init 线程称得上是系统中所有用户进程的祖先，它的 pid 是 1。kthreadd 线程是内核的守护线程，在内核正常工作时，它永远不退出，是一个死循环，它的 pid 是 2。

协程是用户模式下的轻量级线程，最准确的名字应该叫用户空间线程（User Space Thread），在不同的领域中也有不同的叫法，譬如纤程(Fiber)、绿色线程(Green Thread)等等。操作系统内核对协程一无所知，协程的调度完全有应用程序来控制，操作系统不管这部分的调度；一个线程可以包含一个或多个协程，协程拥有自己的寄存器上下文和栈，协程调度切换时，将寄存器上细纹和栈保存起来，在切换回来时恢复先前保运的寄存上下文和栈。

协程的优势如下：

比如 Golang 里的 go 关键字其实就是负责开启一个 Fiber，让 func 逻辑跑在上面。而这一切都是发生的用户态上，没有发生在内核态上，也就是说没有 ContextSwitch 上的开销。

Go 线程模型属于多对多线程模型，在操作系统提供的内核线程之上，Go 搭建了一个特有的两级线程模型。Go 中使用使用 Go 语句创建的 Goroutine 可以认为是轻量级的用户线程，Go 线程模型包含三个概念：

G: 表示 Goroutine，每个 Goroutine 对应一个 G 结构体，G 存储 Goroutine 的运行堆栈、状态以及任务函数，可重用。G 并非执行体，每个 G 需要绑定到 P 才能被调度执行。

P: Processor，表示逻辑处理器，对 G 来说，P 相当于 CPU 核，G 只有绑定到 P(在 P 的 local runq 中)才能被调度。对 M 来说，P 提供了相关的执行环境（Context），如内存分配状态（mcache），任务队列（G）等，P 的数量决定了系统内最大可并行的 G 的数量（物理 CPU 核数 >= P 的数量），P 的数量由用户设置的 GOMAXPROCS 决定，但是不论 GOMAXPROCS 设置为多大，P 的数量最大为 256。

M: Machine，OS 线程抽象，代表着真正执行计算的资源，在绑定有效的 P 后，进入 schedule 循环；M 的数量是不定的，由 Go Runtime 调整，为了防止创建过多 OS 线程导致系统调度不过来，目前默认最大限制为 10000 个。

在 Go 中每个逻辑处理器§会绑定到某一个内核线程上，每个逻辑处理器（P）内有一个本地队列，用来存放 Go 运行时分配的 goroutine。多对多线程模型中是操作系统调度线程在物理 CPU 上运行，在 Go 中则是 Go 的运行时调度 Goroutine 在逻辑处理器（P）上运行。

Go 的栈是动态分配大小的，随着存储数据的数量而增长和收缩。每个新建的 Goroutine 只有大约 4KB 的栈。每个栈只有 4KB，那么在一个 1GB 的 RAM 上，我们就可以有 256 万个 Goroutine 了，相对于 Java 中每个线程的 1MB，这是巨大的提升。Golang 实现了自己的调度器，允许众多的 Goroutines 运行在相同的 OS 线程上。就算 Go 会运行与内核相同的上下文切换，但是它能够避免切换至 ring-0 以运行内核，然后再切换回来，这样就会节省大量的时间。

在 Go 中存在两级调度:

使用 Go 语句创建一个 Goroutine 后，创建的 Goroutine 会被放入 Go 运行时调度器的全局运行队列中，然后 Go 运行时调度器会把全局队列中的 Goroutine 分配给不同的逻辑处理器（P），分配的 Goroutine 会被放到逻辑处理器（P)的本地队列中，当本地队列中某个 Goroutine 就绪后待分配到时间片后就可以在逻辑处理器上运行了。

进程是操作系统对一个正在运行的程序的一种抽象，在一个系统上可以同时运行多个进程，而每个进程都好像在独占地使用硬件。

在现代系统中，一个进程实际上可以由多个称为线程的执行单元组成，每个线程都运行在进程的上下文中，并共享同样的代码和全局数据。

协程是用户模式下的轻量级线程，最准确的名字应该叫用户空间线程（User Space Thread）。

进程是系统资源分配的最小单位, 系统由一个个进程(程序)组成 一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。

文本区域存储处理器执行的代码，数据区域存储变量和进程执行期间使用的动态分配的内存，堆栈区域存储着活动过程调用的指令和本地变量。

因此进程的创建和销毁都是相对于系统资源,所以是一种比较昂贵的操作。 进程有三个状态:

进程是抢占式的争夺 CPU 运行自身,而 CPU 单核的情况下同一时间只能执行一个进程的代码，但是多进程的实现则是通过 CPU 飞快的切换不同进程，因此使得看上去就像是多个进程在同时进行。

通信问题:由于进程间是隔离的，各自拥有自己的内存内存资源, 因此相对于线程比较安全, 所以不同进程之间的数据只能通过 IPC(Inter-Process Communication) 进行通信共享。

线程属于进程，线程共享进程的内存地址空间并且线程几乎不占有系统资源。

通信问题: 进程相当于一个容器，而线程而是运行在容器里面的，因此对于容器内的东西，线程是共同享有的，因此线程间的通信可以直接通过全局变量进行通信。但是由此带来的例如多个线程读写同一个地址变量的时候则将带来不可预期的后果，因此这时候引入了各种锁的作用，例如互斥锁等。

同时多线程是不安全的，当一个线程崩溃了，会导致整个进程也崩溃了，即其他线程也挂了, 但多进程而不会，一个进程挂了，另一个进程依然照样运行。

进程是系统分配资源的最小单位，线程是 CPU 调度的最小单位。由于默认进程内只有一个线程，所以多核 CPU 处理多进程就像是一个进程一个核心。

协程是属于线程的。协程程序是在线程里面跑的，因此协程又称微线程和纤程等，协没有线程的上下文切换消耗。协程的调度切换是用户(程序员)手动切换的，因此更加灵活，因此又叫用户空间线程。

原子操作性。由于协程是用户调度的，所以不会出现执行一半的代码片段被强制中断了，因此无需原子操作锁。

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。每个进程都有自己的独立内存空间，不同进程通过进程间通信来通信。由于进程比较重量，占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、虚拟内存、文件句柄等）比较大，但相对比较稳定安全。

线程是进程的一个实体,是 CPU 调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。线程间通信主要通过共享内存，上下文切换很快，资源开销较少，但相比进程不够稳定容易丢失数据。

协程是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

线程图解如下：

协程图解如下：

进程是系统资源分配的最小单位, 系统由一个个进程(程序)组成 一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。

线程属于进程，线程共享进程的内存地址空间并且线程几乎不占有系统资源。

协程是属于线程的。协程程序是在线程里面跑的，因此协程又称微线程和纤程等，协没有线程的上下文切换消耗。协程的调度切换是用户(程序员)手动切换的，因此更加灵活，因此又叫用户空间线程。

如果父进程先退出，子进程还没退出那么子进程将被托孤给 init 进程，这时子进程的父进程就是 init 进程（1 号进程）。

我们在 Linux 下使用 vim 新建一个 childprocess.c 的文件，编写如下 C 语言 代码如下：

我们使用 gcc 编译上述程序，具体命令如下：

编译完成后，会在当前目录生成一个 childprocess 的二进制可执行文件，我们使用 ls 命令，查看，如下：

此时，我们直接运行该二进制文件，输入以下命令：

运行成功后，控制台输出如下：

此时，我们在另一终端，使用 ps 命令，查看当前进程的状态，具体命令如下：

此时，运行后，控制台输出如下：

此时，我们可以看到，有两个 childprocess 进程在运行，稍等一会，我们再次使用 ps 命令查看当前进程状态，此时，运行后，控制台输出如下：

此时，我们可以看到，只有一个 childprocess 进程在运行了，而且此时的 childprocess 进程的父进程变成了 1，也就是我们说的 init 进程。

如果我们了解过 Linux 进程状态及转换关系，我们应该知道进程这么多状态中有一种状态是僵死状态，就是进程终止后进入僵死状态（zombie）等待告知父进程自己终止后才能完全消失。

但是如果一个进程已经终止了，但是其父进程还没有获取其状态，那么这个进程就称之为僵尸进程。

僵尸进程还会消耗一定的系统资源，并且还保留一些概要信息供父进程查询子进程的状态可以提供父进程想要的信息，一旦父进程得到想要的信息，僵尸进程就会结束。

我们在 Linux 下使用 vim 新建一个 zombie.c 的文件，编写如下 C 语言 代码如下：

我们使用 gcc 编译上述程序，具体命令如下：

编译完成后，会在当前目录生成一个 zombie 的二进制可执行文件，我们使用 ls 命令，查看，如下：

此时，我们直接运行该二进制文件，输入以下命令：

运行成功后，控制台输出如下：

此时，我们在另一终端，使用 ps 命令，查看当前进程的状态，具体命令如下：

此时，运行后，控制台输出如下：

此时，我们可以看到，zombie 进程后面的状态为 defunct，即此时的 zombie 进程即为僵尸进程。

看程序被注释的那句 signal(SIGCHLD,SIG_IGN)，加上就不会出现僵尸进程了。

这是 signal() 函数 的声明 sighandler_t signal(int signum, sighandler_t handler)，我们可以得出 signal 函数的第一个函数是 Linux 支持的信号，第二个参数是对信号的操作 ，是系统默认还是忽略或捕获。

我们这是就可以知道 signal(SIGCHLD,SIG_IGN) 是选择对子程序终止信号选择忽略，这是僵尸进程就是交个内核自己处理，并不会产生僵尸进程。

守护进程就是在后台运行，不与任何终端关联的进程。

通常情况下守护进程在系统启动时就在运行，它们以 root 用户或者其他特殊用户（apache 和 postfix）运行，并能处理一些系统级的任务。习惯上守护进程的名字通常以 d 结尾（sshd），但这些不是必须的。

我们在 Linux 下使用 vim 新建一个 daemon.c 的文件，编写如下 C 语言 代码如下：

通过 gcc 编译之后执行，输出：

从输出来看，if 和 else 居然都执行了，因为用 fork() 有个神奇的地方，一次调用，两次返回。

调用 fork() 之后，会出现两个进程，一个是子进程，一个是父进程，在子进程中，fork() 返回 0，在父进程中，fork() 返回新创建的子进程的进程 ID，我们可以通过 fork() 函数的返回值来判断当前进程是子进程还是父进程。两个进程都会从调用 fork() 的地方继续执行。

fork 进程之后，父进程中的数据怎么办？常规思路是，给子进程重新开辟一块物理内存，将父进程的数据拷贝到子进程中，拷贝完之后，父进程和子进程之间的数据段和堆栈是相互独立的。这样做会带来两个问题：

也就是说，绝大部分情况下，fork 一个子进程会耗费 CPU 和内存资源，但是马上又被子进程抛弃不用了，那么资源的开销就显得毫无意义，于是出于效率考虑，Linux 引入了 copy-on-write 技术。

在 fork() 调用之后，只会给子进程分配虚拟内存地址，而父子进程的虚拟内存地址虽然不同，但是映射到物理内存上都是同一块区域，子进程的代码段、数据段、堆栈都是指向父进程的物理空间。

并且此时父进程中所有对应的内存页都会被标记为只读，父子进程都可以正常读取内存数据，当其中某个进程需要更新数据时，检测到内存页是 read-only 的，内存管理单元（MMU）便会抛出一个页面异常中断，（page-fault），在处理异常时，内核便会把触发异常的内存页拷贝一份（其他内存页还是共享的一份），让父子进程各自持有一份。

这样做的好处不言而喻，能极大的提高 fork 操作时的效率，但是坏处是，如果 fork 之后，两个进程各自频繁的更新数据，则会导致大量的分页错误，这样就得不偿失了。

Java 中有两个容器：CopyOnWriteArrayList 和 CopyOnWriteArraySet，从名字就可以看出，其实现思想也是参考了 copy-on-write 技术。

当我们往一个 CopyOnWrite 的容器中添加数据的时候，并不会直接添加到当前容器中，而是会拷贝出一个新的容器，然后往新的容器里添加数据，在添加过程中，所有的读操作都会指向旧的容器，添加操作完成之后，再将原容器的引用指向新的容器。为了避免同时有多个线程更新数据，从而拷贝出多个容器的副本，会在拷贝容器的时候进行加锁。

这样做的好处是对 CopyOnWrite 容器进行读操作的时候并不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，读和写不同的容器。

C98/C03 中的 std::string 使用了 copy-on-write 技术，在 C++11 标准中为了提高并行性取消了这一策略。

C++ 在分配一个 string 对象时，会在数据区的前面多分配一点空间，用于存储 string 的引用计数。

当触发一个 string 的拷贝构造函数或者赋值函数时，便会对这个引用计数加一。需要修改内容时，如果引用计数不为零，表示有人在共享这块内存，那么自己需要先做一份拷贝，然后把引用计数减去一，再把数据拷贝过来。

Redis 中，执行 BGSAVE 命令，来生成 RDB 文件时，本质就是调用了 Linux 的系统调用 fork() 命令，Linux 下 fork() 系统调用，实现了 copy-on-write 写时复制。

fork() 之后，kernel 把父进程中所有的内存页的权限都设为 read-only，然后子进程的地址空间指向父进程。当父子进程都只读内存时，相安无事。当其中某个进程写内存时，CPU 硬件检测到内存页是 read-only 的，于是触发页异常中断（page-fault），陷入 kernel 的一个中断例程。中断例程中，kernel 就会把触发的异常的页复制一份，于是父子进程各自持有独立的一份。

COW 技术可减少分配和复制大量资源时带来的瞬间延时。

COW 技术可减少不必要的资源分配。比如 fork 进程时，并不是所有的页面都需要复制，父进程的代码段和只读数据段都不被允许修改，所以无需复制。

如果在 fork() 之后，父子进程都还需要继续进行写操作，那么会产生大量的分页错误(页异常中断 page-fault)，这样就得不偿失。

fork 出的子进程共享父进程的物理空间，当父子进程有内存写入操作时，read-only 内存页发生中断，将触发的异常的内存页复制一份(其余的页还是共享父进程的)。

fork 出的子进程功能实现和父进程是一样的。如果有需要，我们会用 exec() 把当前进程映像替换成新的进程文件，完成自己想要实现的功能。

静态连接库就是把(lib)文件中用到的函数代码直接链接进目标程序，程序运行的时候不再需要其它的库文件；动态链接就是把调用的函数所在文件模块（DLL）和调用函数在文件中的位置等信息链接进目标程序，程序运行的时候再从DLL中寻找相应函数代码，因此需要相应 DLL 文件的支持。

通常情况下，对函数库的链接是放在编译时期（compile time）完成的。所有相关的对象文件 （object file）与牵涉到的函数库（library）被链接合成一个可执行文件 （executable file）。程序在运行时，与函数库再无瓜葛，因为所有需要的函数已拷贝到自己门下。

所以这些函数库被成为静态库（static libaray），通常文件 名为 “libxxx.a” 的形式。其实，我们也可以把对一些库函数的链接载入推迟到程序运行的时期（runtime）。这就是如雷贯耳的动态链接库（dynamic link library）技术。

动态链接方法：LoadLibrary()/GetProcessAddress() 和 FreeLibrary()，使用这种方式的程序并不在一开始就完成动态链接，而是直到真正调用动态库代码时，载入程序才计算(被调用的那部分)动态代码的逻辑地址，然后等到某个时候，程序又需要调用另外某块动态代码时，载入程序又去计算这部分代码的逻辑地址，所以，这种方式使程序初始化时间较短，但运行期间的性能比不上静态链接的程序。

静态链接方法：#pragma comment(lib, "test.lib") ，静态链接的时候，载入代码就会把程序会用到的动态代码或动态代码的地址确定下来。

静态库的链接可以使用静态链接，动态链接库也可以使用这种方法链接导入库。

在软件开发的过程中，大家经常会或多或少的使用别人编写的或者系统提供的动态库或静态库，但是究竟是使用静态库还是动态库呢？他们的适用条件是什么呢？

简单的说，静态库和应用程序编译在一起，在任何情况下都能运行，而动态库是动态链接，顾名思义就是在应用程序启动的时候才会链接，所以，当用户的系统上没有该动态库时，应用程序就会运行失败。再看它们的特点：

如果你的系统上有多个应用程序都使用该库的话，就把它编译成动态库，这样虽然刚启动的时候加载比较慢，但是多任务的时候会比较节省内存；如果你的系统上只有一到两个应用使用该库，并且使用的 API 比较少的话，就编译成静态库吧，一般的静态库还可以进行裁剪编译，这样应用程序可能会比较大，但是启动的速度会大大提高。

Linux 的设计哲学之一就是：对不同的操作赋予不同的执行等级，就是所谓特权的概念，即与系统相关的一些特别关键的操作必须由最高特权的程序来完成。

Intel 的 X86 架构的 CPU 提供了 0 到 3 四个特权级，数字越小，特权越高，Linux 操作系统中主要采用了 0 和 3 两个特权级，分别对应的就是内核态(Kernel Mode)与用户态(User Mode)。

Linux 中任何一个用户进程被创建时都包含 2 个栈：内核栈，用户栈，并且是进程私有的，从用户态开始运行。内核态和用户态分别对应内核空间与用户空间，内核空间中存放的是内核代码和数据，而进程的用户空间中存放的是用户程序的代码和数据。不管是内核空间还是用户空间，它们都处于虚拟空间中。

所有用户程序都是运行在用户态的，但是有时候程序确实需要做一些内核态的事情，例如从硬盘读取数据等。而唯一可以做这些事情的就是操作系统，所以此时程序就需要先操作系统请求以程序的名义来执行这些操作。这时需要一个这样的机制：用户态程序切换到内核态，但是不能控制在内核态中执行的指令。

这种机制叫系统调用，在 CPU 中的实现称之为陷阱指令(Trap Instruction)。

当 CPU 正在执行运行在用户态的程序时，突然发生某些预先不可知的异常事件，这个时候就会触发从当前用户态执行的进程转向内核态执行相关的异常事件，典型的如缺页异常。

当外围设备完成用户的请求操作后，会向 CPU 发出中断信号，此时，CPU 就会暂停执行下一条即将要执行的指令，转而去执行中断信号对应的处理程序，如果先前执行的指令是在用户态下，则自然就发生从用户态到内核态的转换。

注意：系统调用的本质其实也是中断，相对于外围设备的硬中断，这种中断称为软中断，这是操作系统为用户特别开放的一种中断，如 Linux int 80h 中断。所以从触发方式和效果上来看，这三种切换方式是完全一样的，都相当于是执行了一个中断响应的过程。但是从触发的对象来看，系统调用是进程主动请求切换的，而异常和硬中断则是被动的。

每个进程都有自己独立的 4G 内存空间，各个进程的内存空间具有类似的结构。

一个新进程建立的时候，将会建立起自己的内存空间，此进程的数据，代码等从磁盘拷贝到自己的进程空间，哪些数据在哪里，都由进程控制表中的 task_struct 记录，task_struct 中记录中一条链表，记录中内存空间的分配情况，哪些地址有数据，哪些地址无数据，哪些可读，哪些可写，都可以通过这个链表记录。

每个进程已经分配的内存空间，都与对应的磁盘空间映射，但是：

每个进程的 4G 内存空间只是虚拟内存空间，每次访问内存空间的某个地址，都需要把地址翻译为实际物理内存地址。

所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。进程要知道哪些内存地址上的数据在物理内存上，哪些不在，还有在物理内存上的哪里，需要用页表来记录。

页表的每一个表项分两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存页的地址（如果在的话）。当进程访问某个虚拟地址，去看页表，如果发现对应的数据不在物理内存中，则缺页异常。

缺页异常的处理过程，就是把进程需要的数据从磁盘上拷贝到物理内存中，如果内存已经满了，没有空地方了，那就找一个页覆盖，当然如果被覆盖的页曾经被修改过，需要将此页写回磁盘

既然每个进程的内存空间都是一致而且固定的，所以链接器在链接可执行文件时，可以设定内存地址，而不用去管这些数据最终实际的内存地址，这是有独立内存空间的好处。

当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存。

在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片。

另外，事实上，在每个进程创建加载时，内核只是为进程 “创建” 了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如 .text .data 段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。

还有进程运行过程中，要动态分配内存，比如 malloc 时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

可以认为虚拟空间都被映射到了磁盘空间中，（事实上也是按需要映射到磁盘空间上，通过 mmap），并且由页表记录映射位置，当访问到某个地址的时候，通过页表中的有效位，可以得知此数据是否在内存中，如果不是，则通过缺页异常，将磁盘对应的数据拷贝到内存中，如果没有空闲内存，则选择牺牲页面，替换其他页面。

mmap 是用来建立从虚拟空间到磁盘空间的映射的，可以将一个虚拟空间地址映射到一个磁盘文件上，当不设置这个地址时，则由系统自动设置，函数返回对应的内存地址（虚拟地址），当访问这个地址的时候，就需要把磁盘上的内容拷贝到内存了，然后就可以读或者写，最后通过 manmap 可以将内存上的数据换回到磁盘，也就是解除虚拟空间和内存空间的映射，这也是一种读写磁盘文件的方法，也是一种进程共享数据的方法 共享内存

在内核态申请内存比在用户态申请内存要更为直接，它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请内存，那么就必须立刻满足该申请内存的请求，并且这个请求一定是正确合理的。相反，对于用户态申请内存的请求，内核总是尽量延后分配物理内存，用户进程总是先获得一个虚拟内存区的使用权，最终通过缺页异常获得一块真正的物理内存。

IA32 架构中内核虚拟地址空间只有 1GB 大小（从 3GB 到 4GB），因此可以直接将 1GB 大小的物理内存（即常规内存）映射到内核地址空间，但超出 1GB 大小的物理内存（即高端内存）就不能映射到内核空间。为此，内核采取了下面的方法使得内核可以使用所有的物理内存。

高端内存不能全部映射到内核空间，也就是说这些物理内存没有对应的线性地址。不过，内核为每个物理页框都分配了对应的页框描述符，所有的页框描述符都保存在 mem_map 数组中，因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用 alloc_pages() 和 alloc_page() 来分配高端内存，因为这些函数返回页框描述符的线性地址。

内核地址空间的后 128MB 专门用于映射高端内存，否则，没有线性地址的高端内存不能被内核所访问。这些高端内存的内核映射显然是暂时映射的，否则也只能映射 128MB 的高端内存。当内核需要访问高端内存时就临时在这个区域进行地址映射，使用完毕之后再用来进行其他高端内存的映射。

由于要进行高端内存的内核映射，因此直接能够映射的物理内存大小只有 896MB，该值保存在 high_memory 中。内核地址空间的线性地址区间如下图所示

基于物理内存在内核空间中的映射原理，物理内存的管理方式也有所不同。内核中物理内存的管理机制主要有伙伴算法，slab 高速缓存和 vmalloc 机制。其中伙伴算法和slab高速缓存都在物理内存映射区分配物理内存，而 vmalloc 机制则在高端内存映射区分配物理内存。

内核通过 vmalloc() 来申请非连续的物理内存，若申请成功，该函数返回连续内存区的起始地址，否则，返回NULL。

vmalloc() 和 kmalloc() 申请的内存有所不同，kmalloc() 所申请内存的线性地址与物理地址都是连续的，而 vmalloc() 所申请的内存线性地址连续而物理地址则是离散的，两个地址之间通过内核页表进行映射。

vmalloc() 的内存分配原理与用户态的内存分配相似，都是通过连续的虚拟内存来访问离散的物理内存，并且虚拟地址和物理地址之间是通过页表进行连接的，通过这种方式可以有效的使用物理内存。

但是应该注意的是，vmalloc() 申请物理内存时是立即分配的，因为内核认为这种内存分配请求是正当而且紧急的；

相反，用户态有内存请求时，内核总是尽可能的延后，毕竟用户态跟内核态不在一个特权级。

操作系统中的页面置换算法主要包括最佳置换算法（OPT，Optimal）、先进先出置换算法（FIFO）、最近最久未使用置换算法（LRU，Least Recently Used）、时钟置换算法和改进型的时钟置换算法。

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。

按照此算法依次执行，最后的结果如下：

结果图：

整个过程缺页中断发生了 9 次，页面置换发生了 6 次。缺页率 = 9 / 20 = 45%。

注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。

最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的。

每次选择淘汰的页面是最早进入内存的页面。

该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为 3,2,1,0,3,2,4,3,2,1,0,4。

分配三个内存块的情况：

分配三个内存块时，缺页次数：9 次。

分配四个内存块的情况：

分配四个内存块时，缺页次数：10 次。当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为贝莱迪（Belay）异常。

只有 FIFO 算法会产生 Belay 异常。另外，FIFO 算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此，算法性能差。

每次淘汰的页面是最近最久未使用的页面。

赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间 t。当需要淘汰一个页面时，选择现有页面中 t 最大的页面，即最近最久未使用。

加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7

这里先直接给出答案：

这里前 10 次都 1、8、7、2 这四个页，四个内存块号正好可以满足，当第 11 次要访问的 3 号页进入内存时，需要从 1、8、7、2 这四个页淘汰一个页，按照该算法，从页号为3的开始，从右往左一次找到这 4 个页第一次出现的地方，在最左边的就是最近最少使用的页。

如下图所示，所以该算法最终淘汰的是 7 号页。同时直接从第十次的访问结果 7 2 1 8 也可以直接看出，7 号页在最前面，是最久没有被访问过的，所以淘汰应该是 7 号页。

结果图

最佳置换算法性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近 OPT 算法性能的，但是实现起来需要专门的硬件支持，算法开销大。时钟置换算法是一种性能和开销均平衡的算法。又称 CLOCK 算法，或最近未用算法（NRU，Not Recently Used）。

简单 CLOCK 算法算法思想：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某个页被访问时，其访问位置 1。当需要淘汰一个页面时，只需检查页的访问位。如果是 0，就选择该页换出；如果是 1，暂不换出，将访问位改为 0，继续检查下一个页面，若第一轮扫描中所有的页面都是 1，则将这些页面的访问位一次置为 0 后，再进行第二轮扫描（第二轮扫描中一定会有访问位为 0 的页面，因此简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）。

例如，假设某系统为某进程分配了五个内存块，并考虑有以下页面号引用串：1,3,4,2,5,6,3,4,7。刚开始访问前 5 个页面，由于都是刚刚被访问所以它们的访问位都是 1，在内存的页面如下图所示：

此时页面 6 需要进入内存，那么需要从中淘汰一个页面，于是从循环队列的队首（1 号页）开始扫描，尝试找到访问位为 0 的页面。经过一轮扫描发现所有的访问位都是 1，经过一轮扫描后，需要将所有的页面标志位设置为 0，如下图：

之后进行第二轮扫描，发现 1 号页的访问位为 0，所以换出 1 号页，同时指针指向下一页，如下图：

接下来是访问 3 号页和 4 号页，这两个页都在内存中，直接访问，并将访问位改为 1。在访问 3 号页和 4 号页时指针不需要动，指针只有在缺页置换时才移动下一页。如下图：

最后，访问 7 号页，此时从 3 号页开始扫描循环队列，扫描过程中将访问位为 1 的页的访问位改为 0，并找到第一个访问位为 0 的页，即 2 号页，将 2 号页置换为 7 号页，最后将指针指向 7 号页的下一页，即 5 号页。如下图：

这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存。只有淘汰的页面被修改过时，才需要写回外存。因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。

改进型时钟置换算法的算法思想：在其他在条件相同时，应该优先淘汰没有被修改过的页面，从而来避免 I/O 操作。为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。

将所有可能被置换的页面排成一个循环队列：

由于第二轮已将所有的页的访问位都设为 0，因此第三轮、第四轮扫描一定会选中一个页，因此改进型 CLOCK 置换算法最多会进行四轮扫描。

第一轮就找到替换的页的情况

假设系统为进程分配了 5 个内存块，某时刻，各个页的状态如下图：

如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

第二轮就找到替换的页的情况

某一时刻页面状态如下:

如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。

然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为 0，第二轮扫描找到了要替换的页。

第三轮就找到替换的页的情况

某一时刻页面状态如下:

第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。

然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为 1，第二轮扫描后，状态为下图：

接着开始第三轮扫描，尝试找状态为（0，0）的页，此轮扫描不修改标志位，第三轮扫描就找到了要替换的页。

第四轮就找到替换的页的情况

某一时刻页面状态如下：

具体的扫描过程和上面相同，这里只给出最后的结果，如下图：

所以，改进型的 CLOCK 置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的 CLOCK 置换算法：

第三、四优先级为什么是访问过的？因为如果到了第三轮扫描，所有页的访问位都在第二轮扫描被设置为了 0，如果访问位不是0的话，也达到不了第三轮扫描，前两轮就会被淘汰。

所以到了第三轮，第四轮淘汰的页都是最近被访问过的。

中断是指计算机在执行期间，系统内发生任何非寻常的或非预期的急需处理事件，使得 CPU 暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。引起中断发生的事件被称为中断源。中断源向 CPU 发出的请求中断处理信号称为中断请求，而 CPU 收到中断请求后转到相应的事件处理程序称为中断响应。

在有些情况下，尽管产生了中断源和发出了中断请求，但 CPU 内部的处理器状态字 PSW 的中断允许位已被清除，从而不允许 CPU 响应中断。这种情况称为禁止中断。CPU 禁止中断后只有等到 PSW 的中断允许位被重新设置后才能接收中断。禁止中断也称为关中断，PSW 的中断允许位的设置也被称为开中断。开中断和关中断是为了保证某段程序执行的原子性。

还有一个比较常用的概念是中断屏蔽。中断屏蔽是指在中断请求产生之后，系统有选择地封锁一部分中断而允许另一部分中断仍能得到响应。不过，有些中断请求是不能屏蔽甚至不能禁止的，也就是说，这些中断具有最高优先级，只要这些中断请求一旦提出，CPU 必须立即响应。例如，电源掉电事件所引起的中断就是不可禁止和不可屏蔽的。

根据系统对中断处理的需要，操作系统一般对中断进行分类并对不同的中断赋予不同的处理优先级，以便在不同的中断同时发生时，按轻重缓急进行处理。

根据中断源产生的条件，可把中断分为外中断和内中断。外中断是指来自处理器和内存外部的中断，包括 IO 设备发出的 IO 中断、外部信号中断(例如用户键人 ESC 键)。各种定时器引起的时钟中断以及调试程序中设置的断点等引起的调试中断等。外中断在狭义上一般被称为中断。

内中断主要指在处理器和内存内部产生的中断。内中断一般称为陷阱(trap)或异常。它包括程序运算引起的各种错误，如地址非法、校验错、页面失效、存取访问控制错、算术操作溢出、数据格式非法、除数为零、非法指令、用户程序执行特权指令、分时系统中的时间片中断以及从用户态到核心态的切换等都是陷阱的例子。

为了按中断源的轻重缓急处理响应中断，操作系统为不同的中断赋予不同的优先级。例如在 UNIX 系统中，外中断和陷阱的优先级共分为 8 级。为了禁止中断或屏蔽中断，CPU 的处理器状态字 PSW 中也设有相应的优先级。如果中断源的优先级高于 PSW 的优先级，则 CPU 响应该中断源的请求；反之，CPU 屏蔽该中断源的中断请求。

各中断源的优先级在系统设计时给定，在系统运行时是固定的。而处理器的优先级则根据执行情况由系统程序动态设定。

除了在优先级的设置方面有区别之外，中断和陷阱还有如下主要区别：

一旦 CPU 响应中断，转人中断处理程序，系统就开始进行中断处理。下面对中断处理过程进行详细说明：

再者，不同的中断源也对应着不同的处理器状态字 PSW。这些不同的 PSW 被放在相应的内存单元中，与中断处理子程序人口地址一起构成中断向量。显然，根据中断或陷阱的种类，系统可由中断向量表迅速地找到该中断响应的优先级、中断处理子程序(或陷阱指令)的入口地址和对应的 PSW。

在操作系统中引入核心态和用户态这两种工作状态后，就需要考虑这两种状态之间如何切换。操作系统内核工作在核心态，而用户程序工作在用户态。但系统不允许用户程序实现核心态的功能，而它们又必须使用这些功能。因此，需要在核心态建立一些 “门”，实现从用户态进入核心态。

在实际操作系统中，CPU 运行上层程序时唯一能进入这些 “门” 的途径就是通过中断或异常。当中断或异常发生时，运行用户态的 CPU 会立即进入核心态，这是通过硬件实现的（例如，用一个特殊寄存器的一位来表示 CPU 所处的工作状态，0 表示核心态，1 表示用户态。若要进入核心态，只需将该位置 0 即可)。中断是操作系统中非常重要的一个概念，对一个运行在计算机上的实用操作系统而言，缺少了中断机制，将是不可想象的。

中断(Interruption)，也称外中断，指来自 CPU 执行指令以外的事件的发生，如设备发出的 I/O 结束中断，表示设备输入/输出处理已经完成，希望处理机能够向设备发下一个输入 / 输出请求，同时让完成输入/输出后的程序继续运行。时钟中断，表示一个固定的时间片已到，让处理机处理计时、启动定时运行的任务等。这一类中断通常是与当前程序运行无关的事件，即它们与当前处理机运行的程序无关。

异常(Exception)，也称内中断、例外或陷入(Trap)，指源自 CPU 执行指令内部的事件，如程序的非法操作码、 地址越界、算术溢出、虚存系统的缺页以及专门的陷入指令等引起的事件。对异常的处理一般要依赖于当前程序的运行现场，而且异常不能被屏蔽，一旦出现应立即处理。关于内中断和外中断的联系与区别如下图所示：

相同点： 最后都是由CPU发送给内核，由内核去处理，处理程序的流程设计上是相似的

不同点：

当允许进程动态增长时，操作系统必须对内存进行更有效的管理，

操作系统使用如下两种方法之一来得知内存的使用情况，分别为

使用位图，将内存划为多个大小相等的块，比如一个32K的内存1K一块可以划为32块，则需要32位（4字节）来表示其使用情况，使用位图将已经使用的块标为1，位使用的标为0.而使用链表，则将内存按使用或未使用分为多个段进行链接，这个概念如图4所示。

使用位图表示内存简单明了，但一个问题是当分配内存时必须在内存中搜索大量的连续0的空间，这是十分消耗资源的操作。

相比之下，使用链表进行此操作将会更胜一筹。还有一些操作系统会使用双向链表，因为当进程销毁时，邻接的往往是空内存或是另外的进程。使用双向链表使得链表之间的融合变得更加容易。

还有，当利用链表管理内存的情况下，创建进程时分配什么样的空闲空间也是个问题。

通常情况下有如下几种算法来对进程创建时的空间进行分配。

轮询：CPU对特定设备轮流询问。中断：通过特定事件提醒CPU。

轮询：效率低等待时间长，CPU利用率不高。中断：容易遗漏问题，CPU利用率不高。

虚拟内存是现代操作系统普遍使用的一种技术。

很多情况下，现有内存无法满足仅仅一个大进程的内存要求(比如很多游戏，都是10G+的级别)。

在早期的操作系统曾使用覆盖(overlays)来解决这个问题，将一个程序分为多个块，基本思想是先将块0加入内存，块0执行完后，将块1加入内存。

依次往复，这个解决方案最大的问题是需要程序员去程序进行分块，这是一个费时费力让人痛苦不堪的过程。

后来这个解决方案的修正版就是虚拟内存。

虚拟内存的基本思想是，每个进程有用独立的逻辑地址空间，内存被分为大小相等的多个块,称为页(Page).

每个页都是一段连续的地址。对于进程来看,逻辑上貌似有很多内存空间，其中一部分对应物理内存上的一块(称为页框，通常页和页框大小相等)，还有一些没加载在内存中的对应在硬盘上。

而虚拟内存和物理内存的匹配是通过页表实现，页表存在MMU中，页表中每个项通常为32位，既4byte,除了存储虚拟地址和页框地址之外，还会存储一些标志位，比如是否缺页，是否修改过，写保护等。

可以把MMU想象成一个接收虚拟地址项返回物理地址的方法。

因为页表中每个条目是4字节，现在的32位操作系统虚拟地址空间会是2的32次方，即使每页分为4K，也需要2的20次方*4字节=4M的空间，为每个进程建立一个4M的页表并不明智。

因此在页表的概念上进行推广，产生二级页表,二级页表每个对应4M的虚拟地址，而一级页表去索引这些二级页表，因此32位的系统需要1024个二级页表，虽然页表条目没有减少，但内存中可以仅仅存放需要使用的二级页表和一级页表，大大减少了内存的使用。

快表（TLB - translation lookaside buffer），直译为旁路快表缓冲，也可以理解为页表缓冲，地址变换高速缓存。

由于页表存放在主存中，因此程序每次访存至少需要两次：一次访存获取物理地址，第二次访存才获得数据。提高访存性能的关键在于依靠页表的访问局部性。当一个转换的虚拟页号被使用时，它可能在不久的将来再次被使用到。

TLB 是一种高速缓存，内存管理硬件使用它来改善虚拟地址到物理地址的转换速度。当前所有的个人桌面，笔记本和服务器处理器都使用 TLB 来进行虚拟地址到物理地址的映射。使用 TLB 内核可以快速的找到虚拟地址指向物理地址，而不需要请求 RAM 内存获取虚拟地址到物理地址的映射关系。这与 data cache 和 instruction caches 有很大的相似之处。

当 cpu 要访问一个虚拟地址/线性地址时，CPU 会首先根据虚拟地址的高 20 位（20 是 x86 特定的，不同架构有不同的值）在 TLB 中查找。如果是表中没有相应的表项，称为 TLB miss，需要通过访问慢速 RAM 中的页表计算出相应的物理地址。同时，物理地址被存放在一个 TLB 表项中，以后对同一线性地址的访问，直接从 TLB 表项中获取物理地址即可，称为 TLB hit。

想像一下 x86_32 架构下没有 TLB 的存在时的情况，对线性地址的访问，首先从 PGD 中获取 PTE（第一次内存访问），在 PTE 中获取页框地址（第二次内存访问），最后访问物理地址，总共需要 3 次 RAM 的访问。如果有 TLB 存在，并且 TLB hit，那么只需要一次 RAM 访问即可。

TLB 内部存放的基本单位是页表条目，对应着 RAM 中存放的页表条目。页表条目的大小固定不变的，所以 TLB 容量越大，所能存放的页表条目越多，TLB hit 的几率也越大。但是 TLB 容量毕竟是有限的，因此 RAM 页表和 TLB 页表条目无法做到一一对应。因此 CPU 收到一个线性地址，那么必须快速做两个判断：

为了尽量减少 CPU 做出这些判断所需的时间，那么就必须在 TLB 页表条目和内存页表条目之间的对应方式做足功夫。

在这种组织方式下，TLB cache 中的表项和线性地址之间没有任何关系，也就是说，一个 TLB 表项可以和任意线性地址的页表项关联。这种关联方式使得 TLB 表项空间的利用率最大。但是延迟也可能相当的大，因为每次 CPU 请求，TLB 硬件都把线性地址和 TLB 的表项逐一比较，直到 TLB hit 或者所有 TLB 表项比较完成。特别是随着 CPU 缓存越来越大，需要比较大量的 TLB 表项，所以这种组织方式只适合小容量 TLB。

每一个线性地址块都可通过模运算对应到唯一的 TLB 表项，这样只需进行一次比较，降低了 TLB 内比较的延迟。但是这个方式产生冲突的几率非常高，导致 TLB miss 的发生，降低了命中率。

比如，我们假定 TLB cache 共包含 16 个表项，CPU 顺序访问以下线性地址块：1, 17 , 1, 33。当 CPU 访问地址块 1 时，1 mod 16 = 1，TLB 查看它的第一个页表项是否包含指定的线性地址块 1，包含则命中，否则从 RAM 装入；然后 CPU 方位地址块 17，17 mod 16 = 1，TLB 发现它的第一个页表项对应的不是线性地址块 17，TLB miss 发生，TLB 访问 RAM 把地址块 17 的页表项装入 TLB；CPU 接下来访问地址块 1，此时又发生了 miss，TLB 只好访问 RAM 重新装入地址块 1 对应的页表项。因此在某些特定访问模式下，直接匹配的性能差到了极点。

为了解决全相连内部比较效率低和直接匹配的冲突，引入了组相连。这种方式把所有的 TLB 表项分成多个组，每个线性地址块对应的不再是一个 TLB 表项，而是一个 TLB 表项组。CPU 做地址转换时，首先计算线性地址块对应哪个 TLB 表项组，然后在这个 TLB 表项组顺序比对。按照组长度，我们可以称之为 2 路，4 路，8 路。

经过长期的工程实践，发现 8 路组相连是一个性能分界点。8 路组相连的命中率几乎和全相连命中率几乎一样，超过 8 路，组内对比延迟带来的缺点就超过命中率提高带来的好处了。

这三种方式各有优缺点，组相连是个折衷的选择，适合大部分应用环境。当然针对不同的领域，也可以采用其他的 cache 组织形式。

TLB 表项更新可以有 TLB 硬件自动发起，也可以有软件主动更新：

在 Linux kernel 软件层，提供了丰富的 TLB 表项刷新方法，但是不同的体系结构提供的硬件接口不同。比如 x86_32 仅提供了两种硬件接口来刷新 TLB 表项：

页表是内存管理系统中的数据结构，用于向每个进程提供一致的虚拟地址空间，每个页表项保存的是虚拟地址到物理地址的映射以及一些管理标志。应用进程只能访问虚拟地址，内核必须借助页表和硬件把虚拟地址翻译为对物理地址的访问。

在使用虚拟地址空间的 Linux 操作系统上，每一个进程都工作在一个 4G 的地址空间上，其中 0~3G 是应用进程可以访问的 user 地址空间，是这个进程独有的，其他进程看不到也无法操作这个地址空间；3G~4G 是 kernel 地址空间，所有进程共享这部分地址空间。

由于每个进程都有 3G 的私有进程空间，所以系统的物理内存无法对这些地址空间进行一一映射，因此 kernel 需要一种机制，把进程地址空间映射到物理内存上。当一个进程请求访问内存时，操作系统通过存储在 kernel 中的进程页表把这个虚拟地址映射到物理地址，如果还没有为这个地址建立页表项，那么操作系统就为这个访问的地址建立页表项。最基本的映射单位是 page，对应的是页表项 PTE。

页表项和物理地址是多对一的关系，即多个页表项可以对应一个物理页面，因而支持共享内存的实现（几个进程同时共享物理内存）。

实现虚拟地址到物理地址转换最容易想到的方法是使用数组，对虚拟地址空间的每一个页，都分配一个数组项。但是有一个问题，考虑 IA32 体系结构下，页面大小为 4KB，整个虚拟地址空间为 4GB，则需要包含 1M 个页表项，这还只是一个进程，因为每个进程都有自己独立的页表。因此，系统所有的内存都来存放页表项恐怕都不够。

相像一下进程的虚拟地址空间，实际上大部分是空闲的，真正映射的区域几乎是汪洋大海中的小岛，因次我们可以考虑使用多级页表，可以减少页表内存使用量。实际上多级页表也是各种体系结构支持的，没有硬件支持，我们是没有办法实现页表转换的。

为了减少页表的大小并忽略未做实际映射的区域，计算机体系结构的设计都会靠虑将虚拟地址划分为多个部分。具体的体系结构划分方式不同，比如 ARM7 和 IA32 就有不同的划分，在这里我们不讨论这部分内容。

Linux 操作系统使用 4 级页表：

图中 CR3 保存着进程页目录 PGD 的地址，不同的进程有不同的页目录地址。进程切换时，操作系统负责把页目录地址装入 CR3 寄存器。

这个地址翻译过程完全是由硬件完成的。

在地址转换过程中，有两种情况会导致失败发生。

CPU 的 Memory management unit(MMU) cache 了最近使用的页面映射。我们称之为 translation lookaside buffer(TLB)。TLB 是一个组相连的 cache。当一个虚拟地址需要转换成物理地址时，首先搜索 TLB。如果发现了匹配（TLB命中），那么直接返回物理地址并访问。然而，如果没有匹配项（TLB miss），那么就要从页表中查找匹配项，如果存在也要把结果写回 TLB。

页目录项和页表项大小都是 32bit(4 bytes)，由于 4KB 地址对齐的原因，页目录项和页表项只有 bit12 ~ bit31 用于地址，剩余的低 12bits 则用来描述页有关的附加信息。尽管这些位是特定于 CPU 的，下列位在 Linux 内核支持的大部分 CPU 都能找到：

页目录项和页表项都包含这个位。

虚拟地址对应的物理页面不在内存中，比如页被交换出去，此时页表项的其他部分通常会代表不同的含义，因为不需要描述页在物理内存中的地址，相反，需要信息来找到换出的页。

如果页目录或者页表项的 Present 位为 0， 那么 CPU 分页单元把虚拟地址存储到 CR2 中，然后生成一个异常 14：page fault 异常。

每次分页单元访问页面时，都会自动设置 Accessed 位，内核会定期检查该位，以便确定页的活跃程度，内核会选择不活跃的页面 swapout 到交换空间。注意分页单元只负责置位，清除位操作要内核自己执行。

仅仅存在于页表项，每当向页帧写入数据分页单元都会设置 dirty 标志，swap 进程可以通过这个位来决定是否选择这个页面进行交换。记住，分页单元不会清除这个标记，所以必须由操作系统来清除这个标记。

包含了页面的读写权限，如果设置为 0，那么只有读权限；设置为 1，则有读写权限。

User 允许用户空间代码访问该页；Supervisor 只有内核才可以访问。

在较新的 64 bit 处理器上，分页单元支持 No eXec 位，因此 2.6.11 内核开始加入了这个标志。

所有体系结构都要实现下面的页表项创建，释放和操作函数，以便于内存管理代码创建和销毁页表：

假设某计算机系统按字节寻址，支持 32 位逻辑地址，采用分页存储管理，页面大小为 4KB，页表项长度为 4B。4KB = 212 B，因此页内地址要用 12 位表示，剩余 20 位表示页号。

因此，该系统中用户进程最多有 220 页。相应的，一个进程的页表中，最多会有 220 个页表项，所以一个页表最大需要 220 * 4B = 222B。一个页框（内存块）大小为 4B，所以需要 222/212 = 210 个页框存储该页表。而页表的存储是需要连续存储的，因为根据页号查询页表的方法：K 号页对应的页表项的位置 = 页表起始地址 + K * 4B（页表项长度），所以这就要求页表的存储必须是连续的。

回想一下，当初为什么使用页表，就是要将进程划分为一个个页面可以不用连续的存放在内存中，但是此时页表就需要 1024 个连续的页框，似乎和当时的目标有点背道而驰了…

此外，根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此也没有必要让整个页面都常驻内存。所以，单级页表存在以上两个问题。

如何解决页表过大需要连续存储的问题呢？这个问题可以参考进程太大需要连续存储的答案。因为页表必须连续存放，所以可以将页表再分页。

解决方案：可以将长长的页表进行分组，使每个页面中刚好可以放下一个分组（如上面的例子中，页面的大小 4KB），每个页表项 4B，所以每个页面中可以存放 1K 个（1024）个页表项，因此每 1K 个连续的页表项为一组，每组刚好占一个页面，再讲各组离散的放在各个内存块中）。这样就需要为离散的页表再建立一张页表，称为页目录表，或外层页表，或顶层页表。

还是上面的例子，32 位的逻辑地址空间，页表项大小为 4B，页面大小 4KB，则页内地址占 12 位，单级页表结构逻辑结构图如下图所示：

使用单级页表的情况：

将页表分为分为 1024 个表，每个表中包含 1024 个页表项，形成二级页表。二级页表结构的逻辑地址结构如下图:

两级页表如何实现地址转换：

下面以一个逻辑地址为例。将逻辑地址（0000000000,0000000001,11111111111）转换为物理地址的过程。

在解决了页必须连续存放的问题后，再看如何第二个问题：没有必要让整个页表常驻内存，因为进程一段时间内可能只需要访问某几个特定的页面。

解决方案：可以在需要访问页面时才把页面调入内存——虚拟存储技术（后面再说）。可以在页表中增加一个标示位，用于表示该页表是否已经调入内存。

1.若采用多级页表机制，则各级页表的大小不能超过一个页面。

举例说明，某系统按字节编址，采用 40 位逻辑地址，页面大小为 4KB，页表项大小为 4B，假设采用纯页式存储，则要采用（）级页表，页内偏移量为（）位？

页面大小 = 4KB，按字节编址，因此页内偏移量为 12 位。

页号 = 40 - 12 = 28位。

页面大小 = 4KB，页表项大小 = 4B，则每个页面可存放 1024 个页表项。因此各级页表最多包含 1024 个页表项，需要 10 个二进制位才能映射到 1024 个页表项，因此每级页表对应的页号应为 10 位二进制。共 28 位的页号至少要分为 3 级。

从上面可以看出，两级页表虽然解决了页表需要连续存储的问题，但是同时也增加了内存的访问次数。

当然，在这种情况下，使用多级页表确实是可以节省内存的。但是，我们需要注意另一种情况，如果进程的虚拟地址空间是 4GB，而进程真正使用的内存也是 4GB，如果是使用一级页表，则只需要 4MB 连续的内存空间存放页表，我们就可以寻址这 4GB 内存空间。而如果使用的是二级页表的话，我们需要 4MB 内存存放页表，还需要 4KB 内存来存放页目录项，此时多级页表反倒是多占用了内存空间。注意在大多数情况都是进程的 4GB 虚拟地址空间都是没有使用的，实际使用的都是小于 4GB 的，所以我们说多级页表可以节省页表内存。

那么使用多级页表比使用以及页表有没有什么劣势呢？

当然是有的。比如：使用以及页表时，读取内存中一页内容需要 2 次访问内存，第一次是访问页表项，第二次是访问要读取的一页数据。但如果是使用二级页表的话，就需要 3 次访问内存了，第一次访问页目录项，第二次访问页表项，第三次访问要读取的一页数据。访存次数的增加也就意味着访问数据所花费的总时间增加。

多级页表优势：

多级页表劣势：

虚拟存储器的核心思路是根据程序运行时的局部性原理：一个程序运行时，在一小段时间内，只会用到程序和数据的很小一部分，仅把这部分程序和数据装入主存即可，更多的部分可以在需要用到时随时从辅存调入主存。在操作系统和相应硬件的支持下，数据在辅存和主存之间按程序运行的需要自动成批量地完成交换。

局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。早在 1968 年的时候，就有人指出我们的程序在执行的时候往往呈现局部性规律，也就是说在某个较短的时间段内，程序执行局限于某一小部分，程序访问的存储空间也局限于某个区域。

局部性原理表现在以下两个方面：

时间局部性： 如果程序中的某条指令一旦执行，不久以后该指令很可能再次执行；如果某数据被访问过，不久以后该数据很可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。

空间局部性： 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存-外存” 的两级存储器的结构，利用局部性原理实现髙速缓存。

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其他部分留在外存，就可以启动程序执行。由于外存往往比内存大很多，所以我们运行的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。

可见，内-外存交换技术本质是一种时间换空间的策略，你用 CPU 的计算时间，页的调入调出花费的时间，换来了一个虚拟的更大的空间来支持程序的运行。

上面是通过理论来说明的，下面我们通过一段代码来看看局部性原理：

不同的逻辑地址可以映射到同一个线性地址上；不同的线性地址也可以映射到同一个物理地址上；所以是多对一的关系。另外，同一个线性地址，在发生换页以后，也可能被重新装载到另外一个物理地址上。所以这种多对一的映射关系也会随时间发生变化。

虚拟内存就是说，让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。虚拟内存使用部分加载的技术，让一个进程或者资源的某些页面加载进内存，从而能够加载更多的进程，甚至能加载比内存大的进程，这样看起来好像内存变大了，这部分内存其实包含了磁盘或者硬盘，并且就叫做虚拟内存。

把内存空间划分为大小相等且固定的块，作为主存的基本单位。因为程序数据存储在不同的页面中，而页面又离散的分布在内存中，因此需要一个页表来记录映射关系，以实现从页号到物理块号的映射。

访问分页系统中内存数据需要两次的内存访问 (一次是从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址；第二次就是根据第一次得到的物理地址访问内存取出数据)。

分页是为了提高内存利用率，而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享，数据保护，动态链接等)。

分段内存管理当中，地址是二维的，一维是段号，二维是段内地址；其中每个段的长度是不一样的，而且每个段内部都是从0开始编址的。由于分段管理中，每个段内部是连续内存分配，但是段和段之间是离散分配的，因此也存在一个逻辑地址到物理地址的映射关系，相应的就是段表机制。

假设每个进程都占用了4G的线性地址空间，页表共含1M个表项，每个表项占4个字节，那么每个进程的页表要占据4M的内存空间。为了节省页表占用的空间，我们使用两级页表。每个进程都会被分配一个页目录，但是只有被实际使用页表才会被分配到内存里面。一级页表需要一次分配所有页表空间，两级页表则可以在需要的时候再分配页表空间。

两级表结构的第一级称为页目录，存储在一个4K字节的页面中。页目录表共有1K个表项，每个表项为4个字节，并指向第二级表。线性地址的最高10位(即位31~位32)用来产生第一级的索引，由索引得到的表项中，指定并选择了1K个二级表中的一个表。

两级表结构的第二级称为页表，也刚好存储在一个4K字节的页面中，包含1K个字节的表项，每个表项包含一个页的物理基地址。第二级页表由线性地址的中间10位(即位21~位12)进行索引，以获得包含页的物理地址的页表项，这个物理地址的高20位与线性地址的低12位形成了最后的物理地址，也就是页转化过程输出的物理地址。

首次适应算法：从低地址开始查找，找到第–个能满足大小的空闲分区。

原理：空闲分区以地址递增的次序排列，每次分配内存时顺序查找

最佳适应算法：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。

因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区,即，优先使用更小的空闲区。原理：空闲分区按容量递增次序链接。每次分配内存时顺序查找

最坏适应算法：为了解决最佳适应算法的问题—即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小。原理：空闲分区按容量递减次序链接，每次分配内存时顺序查找

邻近适应算法：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。原理：空闲分区以地址递增的顺序排列(可排成-一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区

总结：

磁盘块的时间的影响因素有：

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。通俗的说刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。

原因：进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够) 为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并 发度，降低某些资源的利用率

为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程工作集” 的概念

总结：

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

包括以下算法：

在地址映射过程中，如果在页面中发现所要访问的页面不在内存中，那么就会产生一条缺页中断。

当发生缺页中断时，如果操作系统内存中没有空闲页面，那么操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

下面我汇总的这些页面置换算法比较齐全，只给出简单介绍，算法具体的实现和原理读者可以自行了解。

最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的。

在操作系统中，进程是以页为单位加载到内存中的，按需分页是一种虚拟内存的管理方式。在使用请求分页的系统中，只有在尝试访问页面所在的磁盘并且该页面尚未在内存中时，也就发生了缺页异常，操作系统才会将磁盘页面复制到内存中。

虚拟内存 是一种内存分配方案，是一项可以用来辅助内存分配的机制。

我们知道，应用程序是按页装载进内存中的。

但并不是所有的页都会装载到内存中，计算机中的硬件和软件会将数据从 RAM 临时传输到磁盘中来弥补内存的不足。

如果没有虚拟内存的话，

一旦你将计算机内存填满后，计算机会对你说

呃，不，对不起，您无法再加载任何应用程序，请关闭另一个应用程序以加载新的应用程序。

对于虚拟内存，计算机可以执行操作是查看内存中最近未使用过的区域，然后将其复制到硬盘上。

虚拟内存通过复制技术实现了 。

复制是自动进行的，你无法感知到它的存在。

虚拟内存中，允许将一个作业分多次调入内存。釆用连续分配方式时，会使相当一部分内存空间都处于暂时或永久的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实需要建立在离散分配的内存管理方式的基础上。

虚拟内存的实现有以下三种方式：

不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：

内存是随机访问设备，对于内存来说，不需要从头开始查找，只需要直接给出地址即可。内存的分段是从 8086 CPU 开始的，8086 的 CPU 还是 16 位的寄存器宽，16 位的寄存器可以存储的数字范围是 2 的 16 次方，即 64 KB，8086 的 CPU 还没有 虚拟地址，只有物理地址，也就是说，如果两个相同的程序编译出来的地址相同，那么这两个程序是无法同时运行的。为了解决这个问题，操作系统设计人员提出了让 CPU 使用 段基址 + 段内偏移 的方式来访问任意内存。这样的好处是让程序可以 重定位，这也是内存为什么要分段的第一个原因。

那么什么是重定位呢？

简单来说就是将程序中的指令地址改为另一个地址，地址处存储的内容还是原来的。

CPU 采用段基址 + 段内偏移地址的形式访问内存，就需要提供专门的寄存器，这些专门的寄存器就是 CS、DS、ES 等

也就是说，程序中需要用到哪块内存，就需要先加载合适的段到段基址寄存器中，再给出相对于该段基址的段偏移地址即可。

CPU 中的地址加法器会将这两个地址进行合并，从地址总线送入内存。

8086 的 CPU 有 20 根地址总线，最大的寻址能力是 1MB，而段基址所在的寄存器宽度只有 16 位，最大为你 64 KB 的寻址能力，64 KB 显然不能满足 1MB 的最大寻址范围，所以就要把内存分段，每个段的最大寻址能力是 64KB，但是仍旧不能达到最大 1 MB 的寻址能力，所以这时候就需要 偏移地址的辅助，偏移地址也存入寄存器，同样为 64 KB 的寻址能力，这么一看还是不能满足 1MB 的寻址，所以 CPU 的设计者对地址单元动了手脚，将段基址左移 4 位，然后再和 16 位的段内偏移地址相加，就达到了 1MB 的寻址能力。

所以内存分段的第二个目的就是能够访问到所有内存。

物理地址就是内存中真正的地址，它就相当于是你家的门牌号，你家就肯定有这个门牌号，具有唯一性。

不管哪种地址，最终都会映射为物理地址。

在实模式下，段基址 + 段内偏移经过地址加法器的处理，经过地址总线传输，最终也会转换为物理地址。

但是在保护模式下，段基址 + 段内偏移被称为线性地址，不过此时的段基址不能称为真正的地址，而是会被称作为一个选择子的东西，选择子就是个索引，相当于数组的下标，通过这个索引能够在 GDT 中找到相应的段描述符，段描述符记录了段的起始、段的大小等信息，这样便得到了基地址。

如果此时没有开启内存分页功能，那么这个线性地址可以直接当做物理地址来使用，直接访问内存。如果开启了分页功能，那么这个线性地址又多了一个名字，这个名字就是虚拟地址。

不论在实模式还是保护模式下，段内偏移地址都叫做有效地址。有效抵制也是逻辑地址。

线性地址可以看作是虚拟地址，虚拟地址不是真正的物理地址，但是虚拟地址会最终被映射为物理地址。

下面是虚拟地址 -> 物理地址的映射。

操作系统在动态分配内存时（malloc，new），需要对空间内存进行管理。一般采用了两种方式：位图和空闲链表。

使用位图方法时，内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0 表示空闲， 1 表示占用（或者相反）。一块内存区域和其对应的位图如下

图 a 表示一段有 5 个进程和 3 个空闲区的内存，刻度为内存分配单元，阴影区表示空闲（在位图中用 0 表示）；图 b 表示对应的位图；图 c 表示用链表表示同样的信息

分配单元的大小是一个重要的设计因素，分配单位越小，位图越大。然而，即使只有 4 字节的分配单元，32 位的内存也仅仅只需要位图中的 1 位。32n 位的内存需要 n 位的位图，所以1 个位图只占用了 1/32 的内存。如果选择更大的内存单元，位图应该要更小。如果进程的大小不是分配单元的整数倍，那么在最后一个分配单元中会有大量的内存被浪费。

位图提供了一种简单的方法在固定大小的内存中跟踪内存的使用情况，因为位图的大小取决于内存和分配单元的大小。这种方法有一个问题，当决定为把具有 k 个分配单元的进程放入内存时，内容管理器(memory manager) 必须搜索位图，在位图中找出能够运行 k 个连续 0 位的串。在位图中找出制定长度的连续 0 串是一个很耗时的操作，这是位图的缺点。（可以简单理解为在杂乱无章的数组中，找出具有一大长串空闲的数组单元）

另一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表，段会包含进程或者是两个进程的空闲区域。可用上面的图 c 来表示内存的使用情况。链表中的每一项都可以代表一个 空闲区(H) 或者是进程(P)的起始标志，长度和下一个链表项的位置。

在这个例子中，段链表(segment list)是按照地址排序的。这种方式的优点是，当进程终止或被交换时，更新列表很简单。一个终止进程通常有两个邻居（除了内存的顶部和底部外）。相邻的可能是进程也可能是空闲区，它们有四种组合方式。

当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以为创建的进程（或者从磁盘中换入的进程）分配内存。

操作系统把物理内存(physical RAM)分成一块一块的小内存，每一块内存被称为页(page)。当内存资源不足时，Linux把某些页的内容转移至硬盘上的一块空间上，以释放内存空间。硬盘上的那块空间叫做交换空间(swap space),而这一过程被称为交换(swapping)。物理内存和交换空间的总容量就是虚拟内存的可用容量。

用途：

缓冲区溢出是指当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上。

危害有以下两点：

造成缓冲区溢出的主要原因是程序中没有仔细检查用户输入。

用户态和系统态是操作系统的两种运行状态：

内核态：内核态运行的程序可以访问计算机的任何数据和资源，不受限制，包括外围设备，比如网卡、硬盘等。处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况。切换进程，拥有最高权限。 用户态：用户态运行的程序只能受限地访问内存，只能直接读取用户程序的数据，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。大部分用户直接面对的程序都是运行在用户态

将操作系统的运行状态分为用户态和内核态，主要是为了对访问能力进行限制，防止随意进行一些比较危险的操作导致系统的崩溃，比如设置时钟、内存清理，这些都需要在内核态下完成 。

用户模式和内核模式最根本区别就是是否拥有对硬件的控制权。

如果用户模式想操作硬件，这时操作系统可以暴露一些借口给我们，比如创建销毁进程，让用户分配更多内存等操作。等几百个API供用户模式使用。

访问磁盘的效率要比内存慢很多，具体如下图

所以磁盘优化是很有必要的，下面我们会讨论几种优化方式

最常用的减少磁盘访问次数的技术是使用 块高速缓存(block cache) 或者 缓冲区高速缓存(buffer cache)。高速缓存指的是一系列的块，它们在逻辑上属于磁盘，但实际上基于性能的考虑被保存在内存中。

管理高速缓存有不同的算法，常用的算法是：检查全部的读请求，查看在高速缓存中是否有所需要的块。如果存在，可执行读操作而无须访问磁盘。如果检查块不再高速缓存中，那么首先把它读入高速缓存，再复制到所需的地方。之后，对同一个块的请求都通过高速缓存来完成。

高速缓存的操作如下图所示

由于在高速缓存中有许多块，所以需要某种方法快速确定所需的块是否存在。常用方法是将设备和磁盘地址进行散列操作。然后在散列表中查找结果。具有相同散列值的块在一个链表中连接在一起（这个数据结构是不是很像 HashMap?），这样就可以沿着冲突链查找其他块。

如果高速缓存已满，此时需要调入新的块，则要把原来的某一块调出高速缓存，如果要调出的块在上次调入后已经被修改过，则需要把它写回磁盘。这种情况与分页非常相似。

第二个明显提高文件系统的性能是在需要用到块之前试图提前将其写入高速缓存从而提高命中率。许多文件都是顺序读取。如果请求文件系统在某个文件中生成块 k，文件系统执行相关操作并且在完成之后，会检查高速缓存，以便确定块 k + 1 是否已经在高速缓存。如果不在，文件系统会为 k + 1 安排一个预读取，因为文件希望在用到该块的时候能够直接从高速缓存中读取。

当然，块提前读取策略只适用于实际顺序读取的文件。对随机访问的文件，提前读丝毫不起作用。甚至还会造成阻碍。

高速缓存和块提前读并不是提高文件系统性能的唯一方法。另一种重要的技术是把有可能顺序访问的块放在一起，当然最好是在同一个柱面上，从而减少磁盘臂的移动次数。当写一个输出文件时，文件系统就必须按照要求一次一次地分配磁盘块。如果用位图来记录空闲块，并且整个位图在内存中，那么选择与前一块最近的空闲块是很容易的。如果用空闲表，并且链表的一部分存在磁盘上，要分配紧邻的空闲块就会困难很多。

不过，即使采用空闲表，也可以使用 块簇 技术。即不用块而用连续块簇来跟踪磁盘存储区。如果一个扇区有 512 个字节，有可能系统采用 1 KB 的块（2 个扇区），但却按每 2 块（4 个扇区）一个单位来分配磁盘存储区。这和 2 KB 的磁盘块并不相同，因为在高速缓存中它仍然使用 1 KB 的块，磁盘与内存数据之间传送也是以 1 KB 进行，但在一个空闲的系统上顺序读取这些文件，寻道的次数可以减少一半，从而使文件系统的性能大大改善。若考虑旋转定位则可以得到这类方法的变体。在分配块时，系统尽量把一个文件中的连续块存放在同一个柱面上。

在使用 inode 或任何类似 inode 的系统中，另一个性能瓶颈是，读取一个很短的文件也需要两次磁盘访问：一次是访问 inode，一次是访问块。通常情况下，inode 的放置如下图所示

其中，全部 inode 放在靠近磁盘开始位置，所以 inode 和它所指向的块之间的平均距离是柱面组的一半，这将会需要较长时间的寻道时间。

一个简单的改进方法是，在磁盘中部而不是开始处存放 inode ，此时，在 inode 和第一个块之间的寻道时间减为原来的一半。另一种做法是：将磁盘分成多个柱面组，每个柱面组有自己的 inode，数据块和空闲表，如上图 b 所示。

当然，只有在磁盘中装有磁盘臂的情况下，讨论寻道时间和旋转时间才是有意义的。现在越来越多的电脑使用 固态硬盘(SSD)，对于这些硬盘，由于采用了和闪存同样的制造技术，使得随机访问和顺序访问在传输速度上已经较为相近，传统硬盘的许多问题就消失了。但是也引发了新的问题。

在初始安装操作系统后，文件就会被不断的创建和清除，于是磁盘会产生很多的碎片，在创建一个文件时，它使用的块会散布在整个磁盘上，降低性能。删除文件后，回收磁盘块，可能会造成空穴。

磁盘性能可以通过如下方式恢复：移动文件使它们相互挨着，并把所有的至少是大部分的空闲空间放在一个或多个大的连续区域内。Windows 有一个程序 defrag 就是做这个事儿的。Windows 用户会经常使用它，SSD 除外。

磁盘碎片整理程序会在让文件系统上很好地运行。Linux 文件系统（特别是 ext2 和 ext3）由于其选择磁盘块的方式，在磁盘碎片整理上一般不会像 Windows 一样困难，因此很少需要手动的磁盘碎片整理。而且，固态硬盘并不受磁盘碎片的影响，事实上，在固态硬盘上做磁盘碎片整理反倒是多此一举，不仅没有提高性能，反而磨损了固态硬盘。所以碎片整理只会缩短固态硬盘的寿命。

一般情况下，影响磁盘快读写的时间由下面几个因素决定

这三种时间参数也是磁盘寻道的过程。一般情况下，寻道时间对总时间的影响最大，所以，有效的降低寻道时间能够提高磁盘的读取速度。

如果磁盘驱动程序每次接收一个请求并按照接收顺序完成请求，这种处理方式也就是 先来先服务(First-Come, First-served, FCFS) ，这种方式很难优化寻道时间。因为每次都会按照顺序处理，不管顺序如何，有可能这次读完后需要等待一个磁盘旋转一周才能继续读取，而其他柱面能够马上进行读取，这种情况下每次请求也会排队。

通常情况下，磁盘在进行寻道时，其他进程会产生其他的磁盘请求。磁盘驱动程序会维护一张表，表中会记录着柱面号当作索引，每个柱面未完成的请求会形成链表，链表头存放在表的相应表项中。

一种对先来先服务的算法改良的方案是使用 最短路径优先(SSF) 算法，下面描述了这个算法。

假如我们在对磁道 6 号进行寻址时，同时发生了对 11 , 2 , 4, 14, 8, 15, 3 的请求，如果采用先来先服务的原则，如下图所示

我们可以计算一下磁盘臂所跨越的磁盘数量为 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51，相当于是跨越了 51 次盘面，如果使用最短路径优先，我们来计算一下跨越的盘面

跨越的磁盘数量为 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ，相比 51 足足省了两倍的时间。

但是，最短路径优先的算法也不是完美无缺的，这种算法照样存在问题，那就是优先级 问题，

这里有一个原型可以参考就是我们日常生活中的电梯，电梯使用一种电梯算法(elevator algorithm) 来进行调度，从而满足协调效率和公平性这两个相互冲突的目标。电梯一般会保持向一个方向移动，直到在那个方向上没有请求为止，然后改变方向。

电梯算法需要维护一个二进制位，也就是当前的方向位：UP(向上)或者是 DOWN(向下)。当一个请求处理完成后，磁盘或电梯的驱动程序会检查该位，如果此位是 UP 位，磁盘臂或者电梯仓移到下一个更高跌未完成的请求。如果高位没有未完成的请求，则取相反方向。当方向位是 DOWN时，同时存在一个低位的请求，磁盘臂会转向该点。如果不存在的话，那么它只是停止并等待。

我们举个例子来描述一下电梯算法，比如各个柱面得到服务的顺序是 4，7，10，14，9，6，3，1 ，那么它的流程图如下

所以电梯算法需要跨越的盘面数量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22

电梯算法通常情况下不如 SSF 算法。

一些磁盘控制器为软件提供了一种检查磁头下方当前扇区号的方法，使用这样的控制器，能够进行另一种优化。如果对一个相同的柱面有两个或者多个请求正等待处理，驱动程序可以发出请求读写下一次要通过磁头的扇区。

这里需要注意一点，当一个柱面有多条磁道时，相继的请求可能针对不同的磁道，这种选择没有代价，因为选择磁头不需要移动磁盘臂也没有旋转延迟。

对于磁盘来说，最影响性能的就是寻道时间和旋转延迟，所以一次只读取一个或两个扇区的效率是非常低的。出于这个原因，许多磁盘控制器总是读出多个扇区并进行高速缓存，即使只请求一个扇区时也是这样。一般情况下读取一个扇区的同时会读取该扇区所在的磁道或者是所有剩余的扇区被读出，读出扇区的数量取决于控制器的高速缓存中有多少可用的空间。

磁盘控制器的高速缓存和操作系统的高速缓存有一些不同，磁盘控制器的高速缓存用于缓存没有实际被请求的块，而操作系统维护的高速缓存由显示地读出的块组成，并且操作系统会认为这些块在近期仍然会频繁使用。

当同一个控制器上有多个驱动器时，操作系统应该为每个驱动器都单独的维护一个未完成的请求表。一旦有某个驱动器闲置时，就应该发出一个寻道请求来将磁盘臂移到下一个被请求的柱面。如果下一个寻道请求到来时恰好没有磁盘臂处于正确的位置，那么驱动程序会在刚刚完成传输的驱动器上发出一个新的寻道命令并等待，等待下一次中断到来时检查哪个驱动器处于闲置状态。

RAID 称为 磁盘冗余阵列，简称 磁盘阵列。利用虚拟化技术把多个硬盘结合在一起，成为一个或多个磁盘阵列组，目的是提升性能或数据冗余。

RAID 有不同的级别

时钟(Clocks) 也被称为定时器(timers)，时钟/定时器对任何程序系统来说都是必不可少的。

时钟负责维护时间、防止一个进程长期占用 CPU 时间等其他功能。

时钟软件(clock software) 也是一种设备驱动的方式。

下面我们就来对时钟进行介绍，一般都是先讨论硬件再介绍软件，采用由下到上的方式，也是告诉你，底层是最重要的。

在计算机中有两种类型的时钟，这些时钟与现实生活中使用的时钟完全不一样。

这种时钟称为可编程时钟 ，可编程时钟有两种模式，

一种是 一键式(one-shot mode)，当时钟启动时，会把存储器中的值复制到计数器中，然后，每次晶体的振荡器的脉冲都会使计数器 -1。当计数器变为 0 时，会产生一个中断，并停止工作，直到软件再一次显示启动。

还有一种模式时 方波(square-wave mode) 模式，在这种模式下，当计数器变为 0 并产生中断后，存储寄存器的值会自动复制到计数器中，这种周期性的中断称为一个时钟周期。

设备控制器是一个可编址的设备，当它仅控制一个设备时，它只有一个唯一的设备地址；

如果设备控制器控制多个可连接设备时，则应含有多个设备地址，并使每一个设备地址对应一个设备。

设备控制器主要分为两种：字符设备和块设备

设备控制器的主要功能有下面这些

中断处理方案有很多种，下面是 《ARM System Developer’s Guide

Designing and Optimizing System Software》列出来的一些方案

下面是一些通用的中断处理程序的步骤，不同的操作系统实现细节不一样

上面我们罗列了一些大致的中断步骤，不同性质的操作系统和中断处理程序能够处理的中断步骤和细节也不尽相同，下面是一个嵌套中断的具体运行步骤

在计算机中，设备驱动程序是一种计算机程序，它能够控制或者操作连接到计算机的特定设备。驱动程序提供了与硬件进行交互的软件接口，使操作系统和其他计算机程序能够访问特定设备，不用需要了解其硬件的具体构造。

DMA 的中文名称是直接内存访问，它意味着 CPU 授予 I/O 模块权限在不涉及 CPU 的情况下读取或写入内存。也就是 DMA 可以不需要 CPU 的参与。

这个过程由称为 DMA 控制器（DMAC）的芯片管理。由于 DMA 设备可以直接在内存之间传输数据，而不是使用 CPU 作为中介，因此可以缓解总线上的拥塞。

DMA 通过允许 CPU 执行任务，同时 DMA 系统通过系统和内存总线传输数据来提高系统并发性。

DMA 方式有如下特点：

DMA 方式和中断驱动控制方式相比，减少了 CPU 对 I/O 操作的干预，进一步提高了 CPU 与 I/O 设备的并行操作程度。

DMA 方式的线路简单、价格低廉，适合高速设备与主存之间的成批数据传送，小型、微型机中的快速设备均采用这种方式，但其功能较差，不能满足复杂的 I/O 要求。

IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取，它就通知该进程。IO多路复用适用如下场合：

大端模式（Big-Endian）：指的是数据的低位保存在内存的高地址中，而数据的高位保存在内存的低地址中.

小端模式（Little-Endian）：指的是数据的低位保存在内存的低地址中，而数据的高位保存在内存的高地址中

本文收录于《尼恩Java面试宝典》

《Docker面试题（史上最全 + 持续更新）》 《 场景题：假设10W人突访，你的系统如何做到不 雪崩？》 《尼恩Java面试宝典》 《Springcloud gateway 底层原理、核心实战 (史上最全)》 《Flux、Mono、Reactor 实战（史上最全）》 《sentinel （史上最全）》 《Nacos (史上最全)》 《分库分表 Sharding-JDBC 底层原理、核心实战（史上最全）》 《TCP协议详解 (史上最全)》 《clickhouse 超底层原理 + 高可用实操 （史上最全）》 《nacos高可用（图解+秒懂+史上最全）》 《队列之王： Disruptor 原理、架构、源码 一文穿透》 《环形队列、 条带环形队列 Striped-RingBuffer （史上最全）》 《一文搞定：SpringBoot、SLF4j、Log4j、Logback、Netty之间混乱关系（史上最全） 《单例模式（史上最全） 《红黑树（ 图解 + 秒懂 + 史上最全）》 《分布式事务 （秒懂）》 《缓存之王：Caffeine 源码、架构、原理（史上最全，10W字 超级长文）》 《缓存之王：Caffeine 的使用（史上最全）》 《Java Agent 探针、字节码增强 ByteBuddy（史上最全）》 《Docker原理（图解+秒懂+史上最全）》 《Redis分布式锁（图解 - 秒懂 - 史上最全）》 《Zookeeper 分布式锁 - 图解 - 秒懂》 《Zookeeper Curator 事件监听 - 10分钟看懂》 《Netty 粘包 拆包 | 史上最全解读》 《Netty 100万级高并发服务器配置》 《Springcloud 高并发 配置 （一文全懂）》