计算机结构

现代计算机模型是基于-「冯诺依曼计算机模型」

计算机在运行时，先从内存中取出第一条指令，通过控制器的译码，按指令的要求，从存储器中取出数据进行指定的运算和逻辑操作等加工，然后再按地址把结果送到内存中去，接下来，再取出第二条指令，在控制器的指挥下完成规定操作，依此进行下去。直至遇到停止指令

程序与数据一样存贮，按程序编排的顺序，一步一步地取出指令，自动地完成指令规定的操作是计算机最基本的工作模型

「计算机五大核心组成部分」

控制器：是整个计算机的中枢神经，其功能是对程序规定的控制信息进行解释，根据其要求进行控制，调度程序、数据、地址，协调计算机各部分工作及内存与外设的访问等。

运算器：运算器的功能是对数据进行各种算术运算和逻辑运算，即对数据进行加工处理。

存储器：存储器的功能是存储程序、数据和各种信号、命令等信息，并在需要时提供这些信息。

输入：输入设备是计算机的重要组成部分，输入设备与输出设备合你为外部设备，简称外设，输入设备的作用是将程序、原始数据、文字、字符、控制命令或现场采集的数据等信息输入到计算机。

❝常见的输入设备有键盘、鼠标器、光电输入机、磁带机、磁盘机、光盘机等。

❞

输出：输出设备与输入设备同样是计算机的重要组成部分，它把外算机的中间结果或最后结果、机内的各种数据符号及文字或各种控制信号等信息输出出来，微机常用的输出设备有显示终端CRT、打印机、激光印字机、绘图仪及磁带、光盘机等。

「计算机结构分成以下 5 个部分：」

输入设备；输出设备；内存；中央处理器；总线。

内存

在冯诺依曼模型中，程序和数据被存储在一个被称作内存的线性排列存储区域。

存储的数据单位是一个二进制位，英文是 bit，最小的存储单位叫作字节，也就是 8 位，英文是 byte，每一个字节都对应一个内存地址。

内存地址由 0 开始编号，比如第 1 个地址是 0，第 2 个地址是 1， 然后自增排列，最后一个地址是内存中的字节数减 1。

我们通常说的内存都是随机存取器，也就是读取任何一个地址数据的速度是一样的，写入任何一个地址数据的速度也是一样的。

CPU

冯诺依曼模型中 CPU 负责控制和计算，为了方便计算较大的数值，CPU 每次可以计算多个字节的数据。

• 如果 CPU 每次可以计算 4 个 byte，那么我们称作 32 位 CPU；
• 如果 CPU 每次可以计算 8 个 byte，那么我们称作 64 位 CPU。

这里的 32 和 64，称作 CPU 的位宽。

「为什么 CPU 要这样设计呢？」

因为一个 byte 最大的表示范围就是 0~255。

比如要计算 20000*50，就超出了byte 最大的表示范围了。

因此，CPU 需要支持多个 byte 一起计算，当然，CPU 位数越大，可以计算的数值就越大，但是在现实生活中不一定需要计算这么大的数值，比如说 32 位 CPU 能计算的最大整数是 4294967295，这已经非常大了。

「控制单元和逻辑运算单元」

CPU 中有一个控制单元专门负责控制 CPU 工作；还有逻辑运算单元专门负责计算。

「寄存器」

CPU 要进行计算，比如最简单的加和两个数字时，因为 CPU 离内存太远，所以需要一种离自己近的存储来存储将要被计算的数字。

这种存储就是寄存器，寄存器就在 CPU 里，控制单元和逻辑运算单元非常近，因此速度很快。

常见的寄存器种类：

• 通用寄存器，用来存放需要进行运算的数据，比如需要进行加和运算的两个数据。
• 程序计数器，用来存储 CPU 要执行下一条指令所在的内存地址，注意不是存储了下一条要执行的指令，此时指令还在内存中，程序计数器只是存储了下一条指令的地址。
• 指令寄存器，用来存放程序计数器指向的指令，也就是指令本身，指令被执行完成之前，指令都存储在这里。

多级缓存

现代CPU为了提升执行效率，减少CPU与内存的交互(交互影响CPU效率)，一般在CPU上集成了多级缓存架构

「CPU缓存」即高速缓冲存储器，是位于CPU与主内存间的一种容量较小但速度很高的存储器

由于CPU的速度远高于主内存，CPU直接从内存中存取数据要等待一定时间周期，Cache中保存着CPU刚用过或循环使用的一部分数据，当CPU再次使用该部分数据时可从Cache中直接调用，减少CPU的等待时间，提高了系统的效率，具体包括以下几种：

「L1-Cache」

L1- 缓存在 CPU 中，相比寄存器，虽然它的位置距离 CPU 核心更远，但造价更低，通常 L1-Cache 大小在几十 Kb 到几百 Kb 不等，读写速度在 2~4 个 CPU 时钟周期。

「L2-Cache」

L2- 缓存也在 CPU 中，位置比 L1- 缓存距离 CPU 核心更远，它的大小比 L1-Cache 更大，具体大小要看 CPU 型号，有 2M 的，也有更小或者更大的，速度在 10~20 个 CPU 周期。

「L3-Cache」

L3- 缓存同样在 CPU 中，位置比 L2- 缓存距离 CPU 核心更远，大小通常比 L2-Cache 更大，读写速度在 20~60 个 CPU 周期。

L3 缓存大小也是看型号的，比如 i9 CPU 有 512KB L1 Cache；有 2MB L2 Cache； 有16MB L3 Cache。

当 CPU 需要内存中某个数据的时候，如果寄存器中有这个数据，我们可以直接使用；如果寄存器中没有这个数据，我们就要先查询 L1 缓存；L1 中没有，再查询 L2 缓存；L2 中没有再查询 L3 缓存；L3 中没有，再去内存中拿。

「总结：」

存储器存储空间大小：内存>L3>L2>L1>寄存器；

存储器速度快慢排序：寄存器>L1>L2>L3>内存；

安全等级

「CPU运行安全等级」

CPU有4个运行级别，分别为：

• ring0，ring1，ring2，ring3

ring0只给操作系统用，ring3谁都能用。

ring0是指CPU的运行级别，是最高级别，ring1次之，ring2更次之……

系统（内核）的代码运行在最高运行级别ring0上，可以使用特权指令，控制中断、修改页表、访问设备等等。

应用程序的代码运行在最低运行级别上ring3上，不能做受控操作。

如果要做，比如要访问磁盘，写文件，那就要通过执行系统调用（函数），执行系统调用的时候，CPU的运行级别会发生从ring3到ring0的切换，并跳转到系统调用对应的内核代码位置执行，这样内核就为你完成了设备访问，完成之后再从ring0返回ring3。

这个过程也称作用户态和内核态的切换。

局部性原理

在CPU访问存储设备时，无论是存取数据抑或存取指令，都趋于聚集在一片连续的区域中，这就被称为局部性原理

「时间局部性（Temporal Locality）：」

如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。

比如循环、递归、方法的反复调用等。

「空间局部性（Spatial Locality）：」

如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

比如顺序执行的代码、连续创建的两个对象、数组等。

程序的执行过程

程序实际上是一条一条指令，所以程序的运行过程就是把每一条指令一步一步的执行起来，负责执行指令的就是 CPU 了。

「那 CPU 执行程序的过程如下：」

• 第一步，CPU 读取程序计数器的值，这个值是指令的内存地址，然后 CPU 的控制单元操作地址总线指定需要访问的内存地址，接着通知内存设备准备数据，数据准备好后通过数据总线将指令数据传给 CPU，CPU 收到内存传来的数据后，将这个指令数据存入到指令寄存器。
• 第二步，CPU 分析指令寄存器中的指令，确定指令的类型和参数，如果是计算类型的指令，就把指令交给逻辑运算单元运算；如果是存储类型的指令，则交由控制单元执行；
• 第三步，CPU 执行完指令后，程序计数器的值自增，表示指向下一条指令。这个自增的大小，由 CPU 的位宽决定，比如 32 位的 CPU，指令是 4 个字节，需要 4 个内存地址存放，因此程序计数器的值会自增 4；

简单总结一下就是，一个程序执行的时候，CPU 会根据程序计数器里的内存地址，从内存里面把需要执行的指令读取到指令寄存器里面执行，然后根据指令长度自增，开始顺序读取下一条指令。

CPU 从程序计数器读取指令、到执行、再到下一条指令，这个过程会不断循环，直到程序执行结束，这个不断循环的过程被称为 「CPU 的指令周期」。

总线

CPU 和内存以及其他设备之间，也需要通信，因此我们用一种特殊的设备进行控制，就是总线。

• 地址总线，用于指定 CPU 将要操作的内存地址；
• 数据总线，用于读写内存的数据；
• 控制总线，用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后自然进行响应，这时也需要控制总线；

当 CPU 要读写内存数据的时候，一般需要通过两个总线：

• 首先要通过地址总线来指定内存的地址；
• 再通过数据总线来传输数据；

输入、输出设备

输入设备向计算机输入数据，计算机经过计算，将结果通过输出设备向外界传达。

如果输入设备、输出设备想要和 CPU 进行交互，比如说用户按键需要 CPU 响应，这时候就需要用到控制总线。

基础知识

中断

「中断的类型」

• 按照中断的触发方分成同步中断和异步中断；
• 根据中断是否强制触发分成可屏蔽中断和不可屏蔽中断。

中断可以由 CPU 指令直接触发，这种主动触发的中断，叫作同步中断。

❝同步中断有几种情况。

❞

• 比如系统调用，需要从用户态切换内核态，这种情况需要程序触发一个中断，叫作陷阱（Trap），中断触发后需要继续执行系统调用。
• 还有一种同步中断情况是错误（Fault），通常是因为检测到某种错误，需要触发一个中断，中断响应结束后，会重新执行触发错误的地方，比如后面我们要学习的缺页中断。
• 最后还有一种情况是程序的异常，这种情况和 Trap 类似，用于实现程序抛出的异常。

另一部分中断不是由 CPU 直接触发，是因为需要响应外部的通知，比如响应键盘、鼠标等设备而触发的中断，这种中断我们称为异步中断。

CPU 通常都支持设置一个中断屏蔽位（一个寄存器），设置为 1 之后 CPU 暂时就不再响应中断。

对于键盘鼠标输入，比如陷阱、错误、异常等情况，会被临时屏蔽。

但是对于一些特别重要的中断，比如 CPU 故障导致的掉电中断，还是会正常触发。

「可以被屏蔽的中断我们称为可屏蔽中断，多数中断都是可屏蔽中断。」

内核态和用户态

「什么是用户态和内核态」

Kernel 运行在超级权限模式下，所以拥有很高的权限。

按照权限管理的原则，多数应用程序应该运行在最小权限下。

因此，很多操作系统，将内存分成了两个区域：

• 内核空间（Kernal Space），这个空间只有内核程序可以访问；
• 用户空间（User Space），这部分内存专门给应用程序使用。

用户空间中的代码被限制了只能使用一个局部的内存空间，我们说这些程序在用户态 执行。

内核空间中的代码可以访问所有内存，我们称这些程序在内核态 执行。

❝按照级别分：

❞

当程序运行在0级特权级上时，就可以称之为运行在内核态

当程序运行在3级特权级上时，就可以称之为运行在用户态

运行在用户态下的程序不能直接访问操作系统内核数据结构和程序。

当我们在系统中执行一个程序时，大部分时间是运行在用户态下的，在其需要操作系统帮助完成某些它没有权力和能力完成的工作时就会切换到内核态（比如操作硬件）

「这两种状态的主要差别」

处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理器是可被抢占的

处于内核态执行时，则能访问所有的内存空间和对象，且所占有的处理器是不允许被抢占的。

「为什么要有用户态和内核态」

由于需要限制不同的程序之间的访问能力，防止他们获取别的程序的内存数据，或者获取外围设备的数据，并发送到网络

「用户态与内核态的切换」

所有用户程序都是运行在用户态的，但是有时候程序确实需要做一些内核态的事情， 例如从硬盘读取数据，或者从键盘获取输入等，而唯一可以做这些事情的就是操作系统，所以此时程序就需要先操作系统请求以程序的名义来执行这些操作

「用户态和内核态的转换」

❝系统调用

❞

用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如fork()实际上就是执行了一个创建新进程的系统调用

而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现，例如Linux的int 80h中断

「举例：」

如上图所示：内核程序执行在内核态（Kernal Mode），用户程序执行在用户态（User Mode）。

当发生系统调用时，用户态的程序发起系统调用，因为系统调用中牵扯特权指令，用户态程序权限不足，因此会中断执行，也就是 Trap（Trap 是一种中断）。

发生中断后，当前 CPU 执行的程序会中断，跳转到中断处理程序，内核程序开始执行，也就是开始处理系统调用。

内核处理完成后，主动触发 Trap，这样会再次发生中断，切换回用户态工作。

❝异常

❞

当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常

❝外围设备的中断

❞

当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换

比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等

线程

线程：系统分配处理器时间资源的基本单元，是程序执行的最小单位

线程可以看做轻量级的进程，共享内存空间，每个线程都有自己独立的运行栈和程序计数器，线程之间切换的开销小。

在同一个进程（程序）中有多个线程同时执行（通过CPU调度，在每个时间片中只有一个线程执行）

进程可以通过 API 创建用户态的线程，也可以通过系统调用创建内核态的线程。

用户态线程

用户态线程也称作用户级线程，操作系统内核并不知道它的存在，它完全是在用户空间中创建。

用户级线程有很多优势，比如：

• 管理开销小：创建、销毁不需要系统调用。
• 切换成本低：用户空间程序可以自己维护，不需要走操作系统调度。

但是这种线程也有很多的缺点：

• 与内核协作成本高：比如这种线程完全是用户空间程序在管理，当它进行 I/O 的时候，无法利用到内核的优势，需要频繁进行用户态到内核态的切换。
• 线程间协作成本高：设想两个线程需要通信，通信需要 I/O，I/O 需要系统调用，因此用户态线程需要额外的系统调用成本。
• 无法利用多核优势：比如操作系统调度的仍然是这个线程所属的进程，所以无论每次一个进程有多少用户态的线程，都只能并发执行一个线程，因此一个进程的多个线程无法利用多核的优势。

操作系统无法针对线程调度进行优化：当一个进程的一个用户态线程阻塞（Block）了，操作系统无法及时发现和处理阻塞问题，它不会更换执行其他线程，从而造成资源浪费。

内核态线程

内核态线程也称作内核级线程（Kernel Level Thread），这种线程执行在内核态，可以通过系统调用创造一个内核级线程。

内核级线程有很多优势：

• 可以利用多核 CPU 优势：内核拥有较高权限，因此可以在多个 CPU 核心上执行内核线程。
• 操作系统级优化：内核中的线程操作 I/O 不需要进行系统调用；一个内核线程阻塞了，可以立即让另一个执行。

当然内核线程也有一些缺点：

• 创建成本高：创建的时候需要系统调用，也就是切换到内核态。
• 扩展性差：由一个内核程序管理，不可能数量太多。
• 切换成本较高：切换的时候，也同样存在需要内核操作，需要切换内核态。

「用户态线程和内核态线程之间的映射关系」

如果有一个用户态的进程，它下面有多个线程，如果这个进程想要执行下面的某一个线程，应该如何做呢？

❝这时，比较常见的一种方式，就是将需要执行的程序，让一个内核线程去执行。

❞

毕竟，内核线程是真正的线程，因为它会分配到 CPU 的执行资源。

如果一个进程所有的线程都要自己调度，相当于在进程的主线程中实现分时算法调度每一个线程，也就是所有线程都用操作系统分配给主线程的时间片段执行。

❝这种做法，相当于操作系统调度进程的主线程；进程的主线程进行二级调度，调度自己内部的线程。

❞

这样操作劣势非常明显，比如无法利用多核优势，每个线程调度分配到的时间较少，而且这种线程在阻塞场景下会直接交出整个进程的执行权限。

由此可见，用户态线程创建成本低，问题明显，不可以利用多核。

内核态线程，创建成本高，可以利用多核，切换速度慢。

因此通常我们会在内核中预先创建一些线程，并反复利用这些线程。

协程

协程，是一种比线程更加轻量级的存在，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。

这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。

「子程序」

或者称为函数，在所有语言中都是层级调用，比如A调用B，B在执行过程中又调用了C，C执行完毕返回，B执行完毕返回，最后是A执行完毕。

所以子程序调用是通过栈实现的，一个线程就是执行一个子程序。

子程序调用总是一个入口，一次返回，调用顺序是明确的。

「协程的特点在于是一个线程执行，那和多线程比，协程有何优势？」

• 极高的执行效率：因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显；
• 不需要多线程的锁机制：因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

线程安全

如果你的代码所在的进程中有多个线程在同时运行，而这些线程可能会同时运行这段代码。

如果每次运行结果和单线程运行的结果是一样的，而且其他的变量的值也和预期的是一样的，就是线程安全的。

进程

在系统中正在运行的一个应用程序；程序一旦运行就是进程；是资源分配的最小单位。

在操作系统中能同时运行多个进程；

开机的时候，磁盘的内核镜像被导入内存作为一个执行副本，成为内核进程。

进程可以分成「用户态进程和内核态进程」两类，用户态进程通常是应用程序的副本，内核态进程就是内核本身的进程。

如果用户态进程需要申请资源，比如内存，可以通过系统调用向内核申请。

每个进程都有独立的内存空间，存放代码和数据段等，程序之间的切换会有较大的开销；

「分时和调度」

每个进程在执行时都会获得操作系统分配的一个时间片段，如果超出这个时间，就会轮到下一个进程（线程）执行。

❝注意，现代操作系统都是直接调度线程，不会调度进程。

❞

「分配时间片段」

如下图所示，进程 1 需要 2 个时间片段，进程 2 只有 1 个时间片段，进程 3 需要 3 个时间片段。

因此当进程 1 执行到一半时，会先挂起，然后进程 2 开始执行；进程 2 一次可以执行完，然后进程 3 开始执行，不过进程 3 一次执行不完，在执行了 1 个时间片段后，进程 1 开始执行；就这样如此周而复始，这个就是分时技术。

创建进程

用户想要创建一个进程，最直接的方法就是从命令行执行一个程序，或者双击打开一个应用，但对于程序员而言，显然需要更好的设计。

首先，应该有 API 打开应用，比如可以通过函数打开某个应用；

另一方面，如果程序员希望执行完一段代价昂贵的初始化过程后，将当前程序的状态复制好几份，变成一个个单独执行的进程，那么操作系统提供了 fork 指令。

也就是说，每次 fork 会多创造一个克隆的进程，这个克隆的进程，所有状态都和原来的进程一样，但是会有自己的地址空间。

如果要创造 2 个克隆进程，就要 fork 两次。

❝那如果我就是想启动一个新的程序呢？

❞

操作系统提供了启动新程序的 API。

如果我就是想用一个新进程执行一小段程序，比如说每次服务端收到客户端的请求时，我都想用一个进程去处理这个请求。

如果是这种情况，建议你不要单独启动进程，而是使用线程。

因为进程的创建成本实在太高了，因此不建议用来做这样的事情：要创建条目、要分配内存，特别是还要在内存中形成一个个段，分成不同的区域。所以通常，我们更倾向于多创建线程。

不同程序语言会自己提供创建线程的 API，比如 Java 有 Thread 类；go 有 go-routine（注意不是协程，是线程）。

进程状态

「创建状态」

进程由创建而产生，创建进程是一个非常复杂的过程，一般需要通过多个步骤才能完成：如首先由进程申请一个空白的进程控制块(PCB)，并向PCB中填写用于控制和管理进程的信息；然后为该进程分配运行时所必须的资源；最后，把该进程转入就绪状态并插入到就绪队列中

「就绪状态」

这是指进程已经准备好运行的状态，即进程已分配到除CPU以外所有的必要资源后，只要再获得CPU，便可立即执行，如果系统中有许多处于就绪状态的进程，通常将它们按照一定的策略排成一个队列，该队列称为就绪队列，有执行资格，没有执行权的进程

「运行状态」

这里指进程已经获取CPU，其进程处于正在执行的状态。对任何一个时刻而言，在单处理机的系统中，只有一个进程处于执行状态而在多处理机系统中，有多个进程处于执行状态，既有执行资格，又有执行权的进程

「阻塞状态」

这里是指正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行的状态，即进程执行受到阻塞，此时引起进程调度，操作系统把处理机分配给另外一个就绪的进程，而让受阻的进程处于暂停的状态，一般将这个暂停状态称为阻塞状态

「终止状态」

进程间通信IPC

每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，在内核中开辟一块缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信

「管道/匿名管道」

管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道。

• 只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程);
• 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在与内存中。
• 数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出，写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

「有名管道(FIFO)」

匿名管道，由于没有名字，只能用于亲缘关系的进程间通信。

为了克服这个缺点，提出了有名管道(FIFO)。

有名管道不同于匿名管道之处在于它提供了一个路径名与之关联，以有名管道的文件形式存在于文件系统中，这样，即使与有名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信，因此，通过有名管道不相关的进程也能交换数据。

「信号」

信号是Linux系统中用于进程间互相通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。

如果该进程当前并未处于执行状态，则该信号就有内核保存起来，知道该进程回复执行并传递给它为止。

如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消是才被传递给进程。

「消息队列」

消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示。

与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。

另外与管道不同的是，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达

「共享内存」

使得多个进程可以直接读写同一块内存空间，是最快的可用IPC形式，是针对其他通信机制运行效率较低而设计的。

为了在多个进程间交换信息，内核专门留出了一块内存区，可以由需要访问的进程将其映射到自己的私有地址空间，进程就可以直接读写这一块内存而不需要进行数据的拷贝，从而大大提高效率。

由于多个进程共享一段内存，因此需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥。

共享内存示意图：

一旦这样的内存映射到共享它的进程的地址空间，这些进程间数据传递不再涉及到内核，换句话说是进程不再通过执行进入内核的系统调用来传递彼此的数据。

「信号量」

信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。

为了获得共享资源，进程需要执行下列操作：

1. 创建一个信号量：这要求调用者指定初始值，对于二值信号量来说，它通常是1，也可是0。
2. 等待一个信号量：该操作会测试这个信号量的值，如果小于0，就阻塞，也称为P操作。
3. 挂出一个信号量：该操作将信号量的值加1，也称为V操作。

「套接字(Socket)」

套接字是一种通信机制，凭借这种机制，客户/服务器（即要进行通信的进程）系统的开发工作既可以在本地单机上进行，也可以跨网络进行。也就是说它可以让不在同一台计算机但通过网络连接计算机上的进程进行通信。

信号

信号是进程间通信机制中唯一的异步通信机制，可以看作是异步通知，通知接收信号的进程有哪些事情发生了。

也可以简单理解为信号是某种形式上的软中断

可运行kill -l查看Linux支持的信号列表：

kill -l
 1) SIGHUP  2) SIGINT  3) SIGQUIT  4) SIGILL  5) SIGTRAP
 6) SIGABRT  7) SIGBUS  8) SIGFPE  9) SIGKILL 10) SIGUSR1
11) SIGSEGV 12) SIGUSR2 13) SIGPIPE 14) SIGALRM 15) SIGTERM
16) SIGSTKFLT 17) SIGCHLD 18) SIGCONT 19) SIGSTOP 20) SIGTSTP
21) SIGTTIN 22) SIGTTOU 23) SIGURG 24) SIGXCPU 25) SIGXFSZ
26) SIGVTALRM 27) SIGPROF 28) SIGWINCH 29) SIGIO 30) SIGPWR
31) SIGSYS 34) SIGRTMIN 35) SIGRTMIN+1 36) SIGRTMIN+2 37) SIGRTMIN+3
38) SIGRTMIN+4 39) SIGRTMIN+5 40) SIGRTMIN+6 41) SIGRTMIN+7 42) SIGRTMIN+8
43) SIGRTMIN+9 44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9 56) SIGRTMAX-8 57) SIGRTMAX-7
58) SIGRTMAX-6 59) SIGRTMAX-5 60) SIGRTMAX-4 61) SIGRTMAX-3 62) SIGRTMAX-2
63) SIGRTMAX-1 64) SIGRTMAX

「几个常用的信号：」

进程同步

「临界区」

通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问

优点：保证在某一时刻只有一个线程能访问数据的简便办法

缺点：虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程

「互斥量」

为协调共同对一个共享资源的单独访问而设计的

互斥量跟临界区很相似，比临界区复杂，互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限

优点：使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享

「信号量」

为控制一个具有有限数量用户资源而设计，它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目，互斥量是信号量的一种特殊情况，当信号量的最大资源数=1就是互斥量了

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作

• 「down」 : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
• 「up」 ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了 「互斥量（Mutex）」 ，0 表示临界区已经加锁，1 表示临界区解锁。

「事件」

用来通知线程有一些事件已发生，从而启动后继任务的开始

优点：事件对象通过通知操作的方式来保持线程的同步，并且可以实现不同进程中的线程同步操作

「管程」

管程有一个重要特性：在一个时刻只能有一个进程使用管程。

进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了 「条件变量」 以及相关的操作：「wait()」 和 「signal()」 来实现同步操作。

对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。

signal() 操作用于唤醒被阻塞的进程。

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

上下文切换

对于单核单线程CPU而言，在某一时刻只能执行一条CPU指令。

上下文切换(Context Switch)是一种将CPU资源从一个进程分配给另一个进程的机制。

从用户角度看，计算机能够并行运行多个进程，这恰恰是操作系统通过快速上下文切换造成的结果。

「在切换的过程中，操作系统需要先存储当前进程的状态(包括内存空间的指针，当前执行完的指令等等)，再读入下一个进程的状态，然后执行此进程。」

进程调度算法

「先来先服务调度算法」

该算法既可用于作业调度，也可用于进程调度，当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列

「短作业优先调度算法」

从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行

「时间片轮转法」

每次调度时，把CPU分配给队首进程，并令其执行一个时间片，时间片的大小从几ms到几百ms，当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾

然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片，这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间

「最短剩余时间优先」

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度，当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。

如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

「多级反馈队列调度算法」：

前面介绍的几种进程调度的算法都有一定的局限性，如「短进程优先的调度算法，仅照顾了短进程而忽略了长进程」，多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业迅速完成，因而它是目前「被公认的一种较好的进程调度算法」，UNIX 操作系统采取的便是这种调度算法。

❝举例：

❞

多级队列，就是多个队列执行调度，先考虑最简单的两级模型

上图中设计了两个优先级不同的队列，从下到上优先级上升，上层队列调度紧急任务，下层队列调度普通任务。

只要上层队列有任务，下层队列就会让出执行权限。

低优先级队列可以考虑抢占 + 优先级队列的方式实现，这样每次执行一个时间片段就可以判断一下高优先级的队列中是否有任务。

高优先级队列可以考虑用非抢占（每个任务执行完才执行下一个）+ 优先级队列实现，这样紧急任务优先级有个区分，如果遇到十万火急的情况，就可以优先处理这个任务。

上面这个模型虽然解决了任务间的优先级问题，但是还是没有解决短任务先行的问题，可以考虑再增加一些队列，让级别更多。

❝比如下图这个模型：

❞

紧急任务仍然走高优队列，非抢占执行。

普通任务先放到优先级仅次于高优任务的队列中，并且只分配很小的时间片；如果没有执行完成，说明任务不是很短，就将任务下调一层。

下面一层，最低优先级的队列中时间片很大，长任务就有更大的时间片可以用。

通过这种方式，短任务会在更高优先级的队列中执行完成，长任务优先级会下调，也就类似实现了最短作业优先的问题。

实际操作中，可以有 n 层，一层层把大任务筛选出来，最长的任务，放到最闲的时间去执行，要知道，大部分时间 CPU 不是满负荷的。

「优先级调度」

为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推，具有相同优先级的进程以 FCFS 方式执行，可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

守护进程

守护进程是脱离于终端并且在后台运行的进程，脱离终端是为了避免在执行的过程中的信息在终端上显示，并且进程也不会被任何终端所产生的终端信息所打断。

守护进程一般的生命周期是系统启动到系统停止运行。

Linux系统中有很多的守护进程，最典型的就是我们经常看到的服务进程。

当然，我们也经常会利用守护进程来完成很多的系统或者自动化任务。

孤儿进程

父进程早于子进程退出时候子进程还在运行，子进程会成为孤儿进程，Linux会对孤儿进程的处理，把孤儿进程的父进程设为进程号为1的进程，也就是由init进程来托管，init进程负责子进程退出后的善后清理工作

僵尸进程

子进程执行完毕时发现父进程未退出，会向父进程发送 SIGCHLD 信号，但父进程没有使用 wait/waitpid 或其他方式处理 SIGCHLD 信号来回收子进程，子进程变成为了对系统有害的僵尸进程

子进程退出后留下的进程信息没有被收集，会导致占用的进程控制块PCB不被释放，形成僵尸进程，进程已经死去，但是进程资源没有被释放掉

「问题及危害」

如果系统中存在大量的僵尸进程，他们的进程号就会一直被占用，但是系统所能使用的进程号是有限的，系统将因为没有可用的进程号而导致系统不能产生新的进程

任何一个子进程(init除外)在exit()之后，并非马上就消失掉，而是留下一个称为僵尸进程(Zombie)的数据结构，等待父进程处理，这是每个子进程在结束时都要经过的阶段，如果子进程在exit()之后，父进程没有来得及处理，这时用ps命令就能看到子进程的状态是Z。

如果父进程能及时处理，可能用ps命令就来不及看到子进程的僵尸状态，但这并不等于子进程不经过僵尸状态

产生僵尸进程的元凶其实是他们的父进程，杀掉父进程，僵尸进程就变为了孤儿进程，便可以转交给 init 进程回收处理

死锁

「产生原因」

系统资源的竞争：系统资源的竞争导致系统资源不足，以及资源分配不当，导致死锁。

进程运行推进顺序不合适：进程在运行过程中，请求和释放资源的顺序不当，会导致死锁。

「发生死锁的四个必要条件」

互斥条件：一个资源每次只能被一个进程使用，即在一段时间内某资源仅为一个进程所占有，此时若有其他进程请求该资源，则请求进程只能等待

请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求时，该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放

不可剥夺条件:进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)

循环等待条件: 若干进程间形成首尾相接循环等待资源的关系

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁

「只要我们破坏其中一个，就可以成功避免死锁的发生」

其中，互斥这个条件我们没有办法破坏，因为我们用锁为的就是互斥

1. 对于占用且等待这个条件，我们可以一次性申请所有的资源，这样就不存在等待了。
2. 对于不可抢占这个条件，占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源，这样不可抢占这个条件就破坏掉了。
3. 对于循环等待这个条件，可以靠按序申请资源来预防，所谓按序申请，是指资源是有线性顺序的，申请的时候可以先申请资源序号小的，再申请资源序号大的，这样线性化后自然就不存在循环了。

「处理方法」

主要有以下四种方法：

• 鸵鸟策略
• 死锁检测与死锁恢复
• 死锁预防，破坏4个必要条件
• 死锁避免，银行家算法

「鸵鸟策略」

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

「死锁检测」

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

1. 每种类型一个资源的死锁检测
2. 每种类型多个资源的死锁检测

「死锁恢复」

• 利用抢占恢复
• 利用回滚恢复
• 通过杀死进程恢复

哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。

哲学家的生活有两种交替活动：吃饭以及思考。

当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

如果所有哲学家同时拿起左手边的筷子，那么所有哲学家都在等待其它哲学家吃完并释放自己手中的筷子，导致死锁。

哲学家进餐问题可看作是并发进程并发执行时处理共享资源的一个有代表性的问题。

「为了防止死锁的发生，可以设置两个条件：」

• 必须同时拿起左右两根筷子；
• 只有在两个邻居都没有进餐的情况下才允许进餐。

银行家算法

银行家算法的命名是它可以用了银行系统，当不能满足所有客户的需求时，银行绝不会分配其资金。

当新进程进入系统时，它必须说明其可能需要的每种类型资源实例的最大数量这一数量不可以超过系统资源的总和。

当用户申请一组资源时，系统必须确定这些资源的分配是否处于安全状态，如何安全，则分配，如果不安全，那么进程必须等待指导某个其他进程释放足够资源为止。

「安全状态」

在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性，若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待

因此，避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态

Fork函数

fork函数用于创建一个与当前进程一样的子进程，所创建的子进程将复制父进程的代码段、数据段、BSS段、堆、栈等所有用户空间信息，在内核中操作系统会重新为其申请一个子进程执行的位置。

fork系统调用会通过复制一个现有进程来创建一个全新的进程，新进程被存放在一个叫做任务队列的双向循环链表中，链表中的每一项都是类型为task_struct的进程控制块PCB的结构。

每个进程都由独特换不相同的进程标识符（PID），通过getpid()函数可获取当前进程的进程标识符，通过getppid()函数可获得父进程的进程标识符。

一个现有的进程可通过调用fork函数创建一个新进程，由fork创建的新进程称为子进程child process，fork函数被调用一次但返回两次，两次返回的唯一区别是子进程中返回0而父进程中返回子进程ID。

「为什么fork会返回两次呢？」

因为复制时会复制父进程的堆栈段，所以两个进程都停留在fork函数中等待返回，因此会返回两次，一个是在父进程中返回，一次是在子进程中返回，两次返回值是不一样的。

• 在父进程中将返回新建子进程的进程ID
• 在子进程中将返回0
• 若出现错误则返回一个负数

因此可以通过fork的返回值来判断当前进程是子进程还是父进程。

「fork执行执行流程」

当进程调用fork后控制转入内核，内核将会做4件事儿：

1. 分配新的内存块和内核数据结构给子进程
2. 将父进程部分数据结构内容（数据空间、堆栈等）拷贝到子进程
3. 添加子进程到系统进程列表中
4. fork返回开始调度器调度

「为什么pid在父子进程中不同呢？」

其实就相当于链表，进程形成了链表，父进程的pid指向子进程的进程ID，因此子进程没有子进程，所以PID为0，这里的pid相当于链表中的指针。

设备管理

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

• 旋转时间
• 寻道时间实际的数据传输时间

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

❝先来先服务 FCFS, First Come First Served

❞

按照磁盘请求的顺序进行调度，优点是公平和简单，缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

❝最短寻道时间优先，SSTF, Shortest Seek Time First

❞

优先调度与当前磁头所在磁道距离最近的磁道， 虽然平均寻道时间比较低，但是不够公平，如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的 磁道请求会一直等待下去，也就是出现饥饿现象，具体来说，两边的磁道请求更容易出现饥饿现象。

❝电梯算法，SCAN

❞

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向， 电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘 请求，然后改变方向，因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题

内存管理

「逻辑地址和物理地址」

我们编程一般只有可能和逻辑地址打交道，比如在 C 语言中，指针里面存储的数值就可以理解成为内存里的一个地址，这个地址也就是我们说的逻辑地址，逻辑地址由操作系统决定。

物理地址指的是真实物理内存中地址，更具体一点来说就是内存地址寄存器中的地址，物理地址是内存单元真正的地址。

编译时只需确定变量x存放的相对地址是100 ( 也就是说相对于进程在内存中的起始地址而言的地址)。

CPU想要找到x在内存中的实际存放位置，只需要用进程的起始地址+100即可。

相对地址又称逻辑地址，绝对地址又称物理地址。

「内存管理有哪几种方式」

1. 「块式管理」：将内存分为几个固定大小的块，每个块中只包含一个进程，如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了，这些在每个块中未被利用的空间，我们称之为碎片。
2. 「页式管理」：把主存分为大小相等且固定的一页一页的形式，页较小，相对相比于块式管理的划分力度更大，提高了内存利用率，减少了碎片，页式管理通过页表对应逻辑地址和物理地址。

1. 「段式管理」： 页式管理虽然提高了内存利用率，但是页式管理其中的页实际并无任何实际意义， 段式管理把主存分为一段段的，每一段的空间又要比一页的空间小很多 ，段式管理通过段表对应逻辑地址和物理地址。
2. 「段页式管理机制：「段页式管理机制结合了段式管理和页式管理的优点，简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说」段页式管理机制」中段与段之间以及段的内部的都是离散的。

虚拟地址

现代处理器使用的是一种称为**虚拟寻址(Virtual Addressing)**的寻址方式

「使用虚拟寻址，CPU 需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。」

实际上完成虚拟地址转换为物理地址转换的硬件是 CPU 中含有一个被称为**内存管理单元（Memory Management Unit, MMU）**的硬件

「为什么要有虚拟地址空间」

没有虚拟地址空间的时候，「程序都是直接访问和操作的都是物理内存」。

但是这样有什么问题？

1. 用户程序可以访问任意内存，寻址内存的每个字节，这样就很容易破坏操作系统，造成操作系统崩溃。
2. 想要同时运行多个程序特别困难，比如你想同时运行一个微信和一个 QQ 音乐都不行，为什么呢？举个简单的例子：微信在运行的时候给内存地址 1xxx 赋值后，QQ 音乐也同样给内存地址 1xxx 赋值，那么 QQ 音乐对内存的赋值就会覆盖微信之前所赋的值，这就造成了微信这个程序就会崩溃。

「通过虚拟地址访问内存有以下优势：」

• 程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
• 程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。
• 不同进程使用的虚拟地址彼此隔离，一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

「MMU如何把虚拟地址翻译成物理地址的」

对于每个程序，内存管理单元MMU都为其保存一个页表，该页表中存放的是虚拟页面到物理页面的映射。

每当为一个虚拟页面寻找到一个物理页面之后，就在页表里增加一条记录来保留该映射关系，当然，随着虚拟页面进出物理内存，页表的内容也会不断更新变化。

虚拟内存

很多时候我们使用点开了很多占内存的软件，这些软件占用的内存可能已经远远超出了我们电脑本身具有的物理内存

通过 「虚拟内存」 可以让程序可以拥有超过系统物理内存大小的可用内存空间。

另外，虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间），这样会更加有效地管理内存并减少出错。

「虚拟内存」是计算机系统内存管理的一种技术，我们可以手动设置自己电脑的虚拟内存

「虚拟内存的重要意义是它定义了一个连续的虚拟地址空间」，并且 「把内存扩展到硬盘空间」

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

1. 「请求分页存储管理」 ：请求分页是目前最常用的一种实现虚拟存储器的方法，请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行，假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
2. 「请求分段存储管理」 ：请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
3. 「请求段页式存储管理」

不管是上面那种实现方式，我们一般都需要：

❝一定容量的内存和外存：在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了；

❞

缺页中断

如果「需执行的指令或访问的数据尚未在内存」（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段「调入到内存」，然后继续执行程序；

在分页系统中，一个虚拟页面既有可能在物理内存，也有可能保存在磁盘上。

如果CPU发出的虚拟地址对应的页面不在物理内存，就将产生一个缺页中断，而缺页中断服务程序负责将需要的虚拟页面找到并加载到内存。

缺页中断的处理步骤如下，省略了中间很多的步骤，只保留最核心的几个步骤：

页面置换算法

当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。

用来选择淘汰哪一页的规则叫做页面置换算法，我们可以把页面置换算法看成是淘汰页面的规则

• 「OPT 页面置换算法（最佳页面置换算法）」 ：该置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率，但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现，一般作为衡量其他置换算法的方法。
• 「FIFO（First In First Out） 页面置换算法（先进先出页面置换算法）」 : 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。
• 「LRU （Least Currently Used）页面置换算法（最近最久未使用页面置换算法）」 ：LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。
• 「LFU （Least Frequently Used）页面置换算法（最少使用页面置换算法）」 : 该置换算法选择在之前时期使用最少的页面作为淘汰页。

局部性原理

局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。

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

1. 「时间局部性」 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问，产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
2. 「空间局部性」 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

时间局部性是通过将近来使用的指令和数据保存到「高速缓存存储器」中，并使用高速缓存的层次结构实现。

空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。

页表

操作系统将虚拟内存分块，每个小块称为一个页（Page）；真实内存也需要分块，每个小块我们称为一个 Frame。

Page 到 Frame 的映射，需要一种叫作页表的结构。

上图展示了 Page、Frame 和页表 （PageTable）三者之间的关系。

Page 大小和 Frame 大小通常相等，页表中记录的某个 Page 对应的 Frame 编号。

页表也需要存储空间，比如虚拟内存大小为 10G， Page 大小是 4K，那么需要 10G/4K = 2621440 个条目。

如果每个条目是 64bit，那么一共需要 20480K = 20M 页表，操作系统在内存中划分出小块区域给页表，并负责维护页表。

「页表维护了虚拟地址到真实地址的映射。」

每次程序使用内存时，需要把虚拟内存地址换算成物理内存地址，换算过程分为以下 3 个步骤：

• 通过虚拟地址计算 Page 编号；
• 查页表，根据 Page 编号，找到 Frame 编号；
• 将虚拟地址换算成物理地址。

多级页表

引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中

「一级页表：」

假如物理内存中一共有1048576个页，那么页表就需要总共就是1048576 * 4B = 4M。

也就是说我需要4M连续的内存来存放这个页表，也就是一级页表。

随着虚拟地址空间的增大，存放页表所需要的连续空间也会增大，在操作系统内存紧张或者内存碎片较多时，这无疑会带来额外的开销。

页表寻址是用寄存器来确定一级页表地址的，所以一级页表的地址必须指向确定的物理页，否则就会出现错误，所以如果用一级页表的话，就必须把全部的页表都加载进去。

「二级页表：」

而使用二级页表的话，只需要加载一个页目录表(一级页表)，大小为4K，可以管理1024个二级页表。

可能你会有疑问，这1024个二级页表也是需要内存空间的，这下反而需要4MB+4KB的内存，反而更多了。

其实二级页表并不是一定要存在内存中的，内存中只需要一个一级页表地址存在存器即可，二级页表可以使用缺页中断从外存移入内存。

「多级页表属于时间换空间的典型场景」

快表

为了解决虚拟地址到物理地址的转换速度，操作系统在「页表方案」基础之上引入了「快表」来加速虚拟地址到物理地址的转换

我们可以把快表理解为一种特殊的「高速缓冲存储器（Cache）」，其中的内容是页表的一部分或者全部内容，作为页表的 Cache，它的作用与页表相似，但是提高了访问速率，由于采用页表做地址转换，读写内存数据时 CPU 要访问两次主存，有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

「使用快表之后的地址转换流程是这样的：」

1. 根据虚拟地址中的页号查快表；
2. 如果该页在快表中，直接从快表中读取相应的物理地址；
3. 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
4. 当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

内存管理单元

在 CPU 中一个小型的设备——内存管理单元（MMU）

当 CPU 需要执行一条指令时，如果指令中涉及内存读写操作，CPU 会把虚拟地址给 MMU，MMU 自动完成虚拟地址到真实地址的计算；然后，MMU 连接了地址总线，帮助 CPU 操作真实地址。

在不同 CPU 的 MMU 可能是不同的，因此这里会遇到很多跨平台的问题。

解决跨平台问题不但有繁重的工作量，更需要高超的编程技巧。

动态分区分配算法

内存分配算法，大体来说分为：「连续式分配 与 非连续式分配」

连续式分配就是把所以要执行的程序 「完整的，有序的」 存入内存，连续式分配又可以分为「固定分区分配 和 动态分区分配」

非连续式分配就是把要执行的程序按照一定规则进行拆分，显然这样更有效率，现在的操作系统通常也都是采用这种方式分配内存

所谓动态分区分配，就是指「内存在初始时不会划分区域，而是会在进程装入时，根据所要装入的进程大小动态地对内存空间进行划分，以提高内存空间利用率，降低碎片的大小」

动态分区分配算法有以下四种：

❝首次适应算法（First Fit）

❞

空闲分区以地址递增的次序链接，分配内存时顺序查找，找到大小满足要求的第一个空闲分区就进行分配

❝邻近适应算法（Next Fit）

❞

又称循环首次适应法，由首次适应法演变而成，不同之处是分配内存时从上一次查找结束的位置开始继续查找

❝最佳适应算法（Best Fit）

❞

空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区就进行分配

❝最坏适应算法（Next Fit）

❞

又称最大适应算法，空闲分区以容量递减的次序链接，找到第一个能满足要求的空闲分区（也就是最大的分区）就进行分配

「总结」

首次适应不仅最简单，通常也是最好最快，不过首次适应算法会使得内存低地址部分出现很多小的空闲分区，而每次查找都要经过这些分区，因此也增加了查找的开销。

邻近算法试图解决这个问题，但实际上，它常常会导致在内存的末尾分配空间分裂成小的碎片，它通常比首次适应算法结果要差。

最佳适应算法导致大量碎片，最坏适应算法导致没有大的空间。

内存覆盖

覆盖与交换技术是在程序用来扩充内存的两种方法。

早期的计算机系统中，主存容量很小，虽然主存中仅存放一道用户程序，但是存储空间放不下用户进程的现象也经常发生，这一矛盾可以用覆盖技术来解决。

「覆盖的基本思想是：」

由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可以把用户空间分成一个固定区和若干个覆盖区。

将经常活跃的部分放在固定区，其余部分按调用关系分段。

首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

覆盖技术的特点是打破了必须将一个进程的全部信息装入主存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行。

内存交换

「交换的基本思想」

把处于等待状态（或在CPU调度原则下被剥夺运行权利）的程序从内存移到辅存，把内存空间腾出来，这一过程又叫换出；

把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称为换入。

❝例如，有一个CPU釆用时间片轮转调度算法的多道程序环境。

❞

时间片到，内存管理器将刚刚执行过的进程换出，将另一进程换入到刚刚释放的内存空间中。

同时，CPU调度器可以将时间片分配给其他已在内存中的进程。

每个进程用完时间片都与另一进程交换。

理想情况下，内存管理器的交换过程速度足够快，总有进程在内存中可以执行。

❝交换技术主要是在不同进程（或作业）之间进行，而覆盖则用于同一个程序或进程中。

❞

由于覆盖技术要求给出程序段之间的覆盖结构，使得其对用户和程序员不透明，所以对于主存无法存放用户程序的矛盾

现代操作系统是通过虚拟内存技术来解决的，覆盖技术则已成为历史；而交换技术在现代操作系统中仍具有较强的生命力。

常见面试题

「进程、线程的区别」

操作系统会以进程为单位，分配系统资源（CPU时间片、内存等资源），进程是资源分配的最小单位。

调度：线程作为CPU调度和分配的基本单位，进程作为拥有资源的基本单位；

并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行；

❝拥有资源：

❞

进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源。

进程所维护的是程序所包含的资源（静态资源）， 如：地址空间，打开的文件句柄集，文件系统状态，信号处理handler等；

线程所维护的运行相关的资源（动态资源），如：运行栈，调度相关的控制信息，待处理的信号集等；

❝系统开销：

❞

在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。

但是进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。

线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个进程死掉就等于所有的线程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。

「一个进程可以创建多少线程」

理论上，一个进程可用虚拟空间是2G，默认情况下，线程的栈的大小是1MB，所以理论上最多只能创建2048个线程。

如果要创建多于2048的话，必须修改编译器的设置。

在一般情况下，你不需要那么多的线程，过多的线程将会导致大量的时间浪费在线程切换上，给程序运行效率带来负面影响。

「外中断和异常有什么区别」

外中断是指由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求，此外还有时钟中断、控制台中断等。

而异常时由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。

「解决Hash冲突四种方法」

开放定址法

• 开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

链地址法

• 将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。

再哈希法

• 当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。

建立公共溢出区

• 将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

「分页机制和分段机制有哪些共同点和区别」

共同点

• 分页机制和分段机制都是为了提高内存利用率，较少内存碎片。
• 页和段都是离散存储的，所以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的。

区别

• 页的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序。
• 分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段，数据段，能够更好满足用户的需要。
• 分页是一维地址空间，分段是二维的。

「介绍一下几种典型的锁」

❝读写锁

❞

• 可以同时进行多个读
• 写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
• 写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）

❝互斥锁

❞

一次只能一个线程拥有互斥锁，其他线程只有等待

互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒，而操作系统负责线程调度，为了实现锁的状态发生改变时唤醒阻塞的线程或者进程，需要把锁交给操作系统管理，所以互斥锁在加锁操作时涉及上下文的切换。

互斥锁实际的效率还是可以让人接受的，加锁的时间大概100ns左右，而实际上互斥锁的一种可能的实现是先自旋一段时间，当自旋的时间超过阀值之后再将线程投入睡眠中，因此在并发运算中使用互斥锁（每次占用锁的时间很短）的效果可能不亚于使用自旋锁

❝条件变量

❞

互斥锁一个明显的缺点是他只有两种状态：锁定和非锁定。

而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足，他常和互斥锁一起使用，以免出现竞态条件。

当条件不满足时，线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。

一旦其他的某个线程改变了条件变量，他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。

总的来说「互斥锁是线程间互斥的机制，条件变量则是同步机制。」

❝自旋锁

❞

如果进线程无法取得锁，进线程不会立刻放弃CPU时间片，而是一直循环尝试获取锁，直到获取为止。

如果别的线程长时期占有锁，那么自旋就是在浪费CPU做无用功，但是自旋锁一般应用于加锁时间很短的场景，这个时候效率比较高。

虽然它的效率比互斥锁高，但是它也有些不足之处：

• 自旋锁一直占用CPU，在未获得锁的情况下，一直进行自旋，所以占用着CPU，如果不能在很短的时间内获得锁，无疑会使CPU效率降低。
• 在用自旋锁时有可能造成死锁，当递归调用时有可能造成死锁。

「如何让进程后台运行」

1.命令后面加上&即可，实际上，这样是将命令放入到一个作业队列中了

2.ctrl + z 挂起进程，使用jobs查看序号，在使用bg %序号后台运行进程

3.nohup + &，将标准输出和标准错误缺省会被重定向到 nohup.out 文件中，忽略所有挂断（SIGHUP）信号

nohup ping 

4.运行指令前面 + setsid，使其父进程变成init进程，不受SIGHUP信号的影响

[root@pvcent107 ~]# setsid ping 
[root@pvcent107 ~]# ps -ef |grep 
root     31094     1  0 07:28 ?        00:00:00 ping 
root     31102 29217  0 07:29 pts/4    00:00:00 grep 

上例中我们的进程 ID(PID)为31094，而它的父 ID（PPID）为1（即为 init 进程 ID），并不是当前终端的进程 ID。

❝5.将命令+ &放在()括号中，也可以是进程不受HUP信号的影响

❞

[root@pvcent107 ~]# (ping )

「异常和中断的区别」

❝中断

❞

当我们在敲击键盘的同时就会产生中断，当硬盘读写完数据之后也会产生中断，所以，我们需要知道，中断是由硬件设备产生的，而它们从物理上说就是电信号，之后，它们通过中断控制器发送给CPU，接着CPU判断收到的中断来自于哪个硬件设备（这定义在内核中），最后，由CPU发送给内核，有内核处理中断。

下面这张图显示了中断处理的流程：

❝异常

❞

CPU处理程序的时候一旦程序不在内存中，会产生缺页异常；当运行除法程序时，当除数为0时，又会产生除0异常。

「异常是由CPU产生的，同时，它会发送给内核，要求内核处理这些异常」

下面这张图显示了异常处理的流程：

❝相同点

❞

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

❝不同点

❞

• 产生源不相同，异常是由CPU产生的，而中断是由硬件设备产生的
• 内核需要根据是异常还是中断调用不同的处理程序
• 中断不是时钟同步的，这意味着中断可能随时到来；异常由于是CPU产生的，所以它是时钟同步的
• 当处理中断时，处于中断上下文中；处理异常时，处于进程上下文中