操作系统

操作系统简介篇

转载：https://www.zhihu.com/question/446980297/answer/1755892330

操作系统是管理硬件和软件的一种应用程序

操作系统的主要功能

进程管理: 进程管理的主要作用就是任务调度，在单核处理器下，操作系统会为每个进程分配一个任务，进程管理的工作十分简单；而在多核处理器下，操作系统除了要为进程分配任务外，还要解决处理器的调度、分配和回收等问题

内存管理：内存管理主要是操作系统负责管理内存的分配、回收，在进程需要时分配内存以及在进程完成时回收内存，协调内存资源，通过合理的页面置换算法进行页面的换入换出

设备管理：根据确定的设备分配原则对设备进行分配，使设备与主机能够并行工作，为用户提供良好的设备使用界面。

文件管理：有效地管理文件的存储空间，合理地组织和管理文件系统，为文件访问和文件保护提供更有效的方法及手段。

提供用户接口：操作系统提供了访问应用程序和硬件的接口，使用户能够通过应用程序发起系统调用从而操纵硬件，实现想要的功能。

软件访问硬件的几种方式

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

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

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

（1） 数据传送速度足够快，能满足用户的需求但又不丢失数据；
（2） 系统开销小，所需的处理控制程序少；
（3） 能充分发挥硬件资源的能力，使 I/O 设备尽可能忙，而 CPU 等待时间尽可能少。

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

• 直接访问：直接访问由用户进程直接控制主存或 CPU 和外围设备之间的信息传送。直接程序控制方式又称为忙/等待方式。
• 中断驱动：为了减少程序直接控制方式下 CPU 的等待时间以及提高系统的并行程度，系统引入了中断机制。中断机制引入后，外围设备仅当操作正常结束或异常结束时才向 CPU 发出中断请求。在 I/O 设备输入每个数据的过程中，由于无需 CPU 的干预，一定程度上实现了 CPU 与 I/O 设备的并行工作。

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

• DMA 直接内存访问：为了进一步减少 CPU 对 I/O 操作的干预，防止因并行操作设备过多使 CPU 来不及处理或因速度不匹配而造成的数据丢失现象，引入了 DMA 控制方式。
• 通道控制方式：通道，独立于 CPU 的专门负责输入输出控制的处理机，它控制设备与内存直接进行数据交换。有自己的通道指令，这些指令由 CPU 启动，并在操作结束时向 CPU 发出中断信号。

什么是用户态和内核态

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

• 内核态：处于内核态的 CPU 可以访问任意的数据，包括外围设备，比如网卡、硬盘等，处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况，一般处于特权级 0 的状态我们称之为内核态。
• 用户态：处于用户态的 CPU 只能受限的访问内存，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。

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

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

CPU运行安全等级

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

• ring0，ring1，ring2，ring3

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

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

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

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

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

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

进程和线程篇

什么是线程，线程和进程的区别

我们上面说到进程是正在运行的程序的实例，而线程其实就是进程中的单条流向，因为线程具有进程中的某些属性，所以线程又被称为轻量级的进程。浏览器如果是一个进程的话，那么浏览器下面的每个 tab 页可以看作是一个个的线程。

创建线程的开销要比进程小很多，因为创建线程仅仅需要堆栈指针和程序计数器就可以了，而创建进程需要操作系统分配新的地址空间，数据资源等，这个开销比较大。

多进程和多线程的区别

上下文切换

对于单核单线程 CPU 而言，在某一时刻只能执行一条 CPU 指令。上下文切换（Context Switch） 是一种 将 CPU 资源从一个进程分配给另一个进程的机制。从用户角度看，计算机能够并行运行多个进程，这恰恰是操作系统通过快速上下文切换造成的结果。在切换的过程中，操作系统需要先存储当前进程的状态（包括内存空间的指针，当前执行完的指令等等），再读入下一个进程的状态，然后执行此进程。

进程间的通信方式

管道（pipe）

管道包括三种：

1. 普通管道：通常有两种限制,一是单工,只能单向传输;二是只能在父子或者兄弟进程间使用
2. 流管道：去除了第一种限制,为半双工，只能在父子或兄弟进程间使用，可以双向传输
3. 命名管道：可以在许多并不相关的进程之间进行通讯

信号量（semophore）

信号量是一个计数器，可以用来控制多个进程对共享资源的访问，它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同进程之间的同步手段。

消息队列（message queue）

消息队列是消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信号少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

共享内存（shared memory）

共享内存就是映射一段能被其他进程锁访问的内存。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制如信号量配合使用。

套接字（socket）

可以用于不同机器间的进程通信。

各进程通信方式的原理

管道：管道是由内核管理的一个缓冲区，相当于我们放入内存中的一个纸条。管道的一端连接一个进程的输出。这个进程会向管道中放入信息。管道的另一端连接一个进程的输入，这个进程取出被放入管道的信息。一个缓冲区不需要很大，它被设计成为环形的数据结构，以便管道可以被循环利用。当管道中没有信息的话，从管道中读取的进程会等待，直到另一端的进程放入信息。当管道被放满信息的时候，尝试放入信息的进程会等待，直到另一端的进程取出信息。当两个进程都终结的时候，管道也自动消失。

信号量：临界区域是指执行数据更新的代码需要独占式地执行。而信号量就可以提供这样的一种访问机制，让一个临界区同一时间只有一个线程在访问它，也就是说信号量是用来调协进程对共享资源的访问的。信号量是一个特殊的变量，程序对其访问都是原子操作，且只允许对它进行等待（即P）和发送（即V）信息操作。最简单的信号量是只能取0和1的变量，这也是信号量最常见的一种形式，叫做二进制信号量。而可以取多个正整数的信号量被称为通用信号量。

消息队列：消息队列是消息的链表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。消息队列是随内核持续的。

共享内存：两个不同进程A、B共享内存的意思是，同一块物理内存被映射到进程A、B各自的进程地址空间。进程A可以即时看到进程B对共享内存中数据的更新，反之亦然。由于多个进程共享同一块内存区域，必然需要某种同步机制，互斥锁和信号量都可以。

套接字：两个基本概念：客户方和服务方。当两个应用之间需要采用SOCKET通信时，首先需要在两个应用之间（可能位于同一台机器，也可能位于不同的机器）建立SOCKET连接。

进程的三态模型

1. 运行态：运行态指的就是进程实际占用 CPU 时间片运行时
2. 就绪态：就绪态指的是可运行，但因为其他进程正在运行而处于就绪状态
3. 阻塞态：阻塞态又被称为睡眠态，它指的是进程不具备运行条件，正在等待被 CPU 调度。

进程的五态模型

在三态模型的基础上，增加了两个状态，即 新建 和 终止 状态。

• 新建态：进程的新建态就是进程刚创建出来的时候（分配所需要的资源和空间）

• 终止态：进程的终止态就是指进程执行完毕，到达结束点，或者因为错误而不得不中止进程。

终止一个进程需要两个步骤：

1. 先等待操作系统或相关的进程进行善后处理。
2. 然后回收占用的资源并被系统删除。

调度算法

调度算法分为三大类：批处理中的调度、交互系统中的调度、实时系统中的调度

批处理中的调度

先来先服务

缺点：没有优先级关系

最短作业优先

在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。

缺点：会饿死时间长的进程

最短剩余时间优先

交互式系统中的调度

轮询调度

优先级调度

彩票调度：把彩票理解为 buff，这个 buff 有 15% 的几率能让你产生 速度之靴 的效果

公平分享调度：无论一个用户有多少个进程，都将获得相同的 CPU 份额

RR 调度算法：主要针对分时系统，RR 的调度算法会把时间片以相同的部分并循环的分配给每个进程，RR 调度算法没有优先级的概念

内存管理篇

虚拟内存的实现方式

• 分页存储管理。
• 分段存储管理。
• 段页式存储管理。

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

• 一定容量的内存和外存。
• 页表机制（或段表机制），作为主要的数据结构。
• 中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。
• 地址变换机构，逻辑地址到物理地址的变换。

程序中需要用到哪块内存，就需要先加载合适的段到段基址寄存器中，再给出相对于该段基址的段偏移地址即可。CPU 中的地址加法器会将这两个地址进行合并，从地址总线送入内存。

物理地址、逻辑地址、有效地址、线性地址、虚拟地址的区别

物理地址就是内存中真正的地址，它就相当于是你家的门牌号，你家就肯定有这个门牌号，具有唯一性。不管哪种地址，最终都会映射为物理地址。

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

但是在保护模式下，段基址 + 段内偏移被称为线性地址，不过此时的段基址不能称为真正的地址，而是会被称作为一个选择子的东西，选择子就是个索引，相当于数组的下标，通过这个索引能够在 GDT 中找到相应的段描述符，段描述符记录了段的起始、段的大小等信息，这样便得到了基地址。如果此时没有开启内存分页功能，那么这个线性地址可以直接当做物理地址来使用，直接访问内存。如果开启了分页功能，那么这个线性地址又多了一个名字，这个名字就是虚拟地址。

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

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

空闲内存管理的方式

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

位图进行管理

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

空闲链表

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

页面置换算法

• 最优算法在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。
• NRU 算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好。存在更好的算法。
• FIFO 会跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面，因此这个算法也不是一个很好的选择。
• 第二次机会算法是对 FIFO 的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进大大提高了性能。
• 时钟 算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法。
• LRU 算法是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法。
• NFU 算法是一种近似于 LRU 的算法，它的性能不是非常好。
• 老化 算法是一种更接近 LRU 算法的实现，并且可以更好的实现，因此是一个很好的选择
• 最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。WSClock 是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现。

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

文件系统篇

提高文件系统性能的方式

高速缓存

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

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

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

块提前读

只适用于实际顺序读取的文件。对随机访问的文件，提前读丝毫不起作用。

减少磁盘臂运动

把有可能顺序访问的块放在一起，当然最好是在同一个柱面上，从而减少磁盘臂的移动次数。

磁盘碎片整理

Windows 有一个程序 defrag 就是做这个事。固态硬盘并不受磁盘碎片的影响

磁盘臂调度算法

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

• 寻道时间 - 寻道时间指的就是将磁盘臂移动到需要读取磁盘块上的时间
• 旋转延迟 - 等待合适的扇区旋转到磁头下所需的时间
• 实际数据的读取或者写入时间

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

一种对先来先服务的算法改良的方案是使用 最短路径优先(SSF) 算法

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

RAID

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

RAID 有不同的级别

• RAID 0 - 无容错的条带化磁盘阵列
• RAID 1 - 镜像和双工
• RAID 2 - 内存式纠错码
• RAID 3 - 比特交错奇偶校验
• RAID 4 - 块交错奇偶校验
• RAID 5 - 块交错分布式奇偶校验
• RAID 6 - P + Q冗余

IO 篇

操作系统中的时钟是什么

时钟(Clocks) 也被称为定时器(timers)，时钟/定时器对任何程序系统来说都是必不可少的。时钟负责维护时间、防止一个进程长期占用 CPU 时间等其他功能。时钟软件(clock software)也是一种设备驱动的方式。

时钟硬件

由晶体振荡器、计数器和寄存器组成，示意图如下所示

这种时钟称为可编程时钟 ，可编程时钟有两种模式，一种是 一键式(one-shot mode)，当时钟启动时，会把存储器中的值复制到计数器中，然后，每次晶体的振荡器的脉冲都会使计数器 -1。当计数器变为 0 时，会产生一个中断，并停止工作，直到软件再一次显示启动。还有一种模式时 方波(square-wave mode) 模式，在这种模式下，当计数器变为 0 并产生中断后，存储寄存器的值会自动复制到计数器中，这种周期性的中断称为一个时钟周期。

设备控制器的主要功能

设备控制器是一个可编址的设备，当它仅控制一个设备时，它只有一个唯一的设备地址；如果设备控制器控制多个可连接设备时，则应含有多个设备地址，并使每一个设备地址对应一个设备。

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

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

• 接收和识别命令：设备控制器可以接受来自 CPU 的指令，并进行识别。设备控制器内部也会有寄存器，用来存放指令和参数
• 进行数据交换：CPU、控制器和设备之间会进行数据的交换，CPU 通过总线把指令发送给控制器，或从控制器中并行地读出数据；控制器将数据写入指定设备。
• 地址识别：每个硬件设备都有自己的地址，设备控制器能够识别这些不同的地址，来达到控制硬件的目的，此外，为使 CPU 能向寄存器中写入或者读取数据，这些寄存器都应具有唯一的地址。
• 差错检测：设备控制器还具有对设备传递过来的数据进行检测的功能。

中断处理过程

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

• 保存所有没有被中断硬件保存的寄存器
• 为中断服务程序设置上下文环境，可能包括设置 TLB、MMU 和页表，如果不太了解这三个概念，请参考另外一篇文章
• 为中断服务程序设置栈
• 对中断控制器作出响应，如果不存在集中的中断控制器，则继续响应中断
• 把寄存器从保存它的地方拷贝到进程表中
• 运行中断服务程序，它会从发出中断的设备控制器的寄存器中提取信息
• 操作系统会选择一个合适的进程来运行。如果中断造成了一些优先级更高的进程变为就绪态，则选择运行这些优先级高的进程
• 为进程设置 MMU 上下文，可能也会需要 TLB，根据实际情况决定
• 加载进程的寄存器，包括 PSW 寄存器
• 开始运行新的进程

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

DMA

DMA 的中文名称是直接内存访问，它意味着 CPU 授予 I/O 模块权限在不涉及 CPU 的情况下读取或写入内存。也就是 DMA 可以不需要 CPU 的参与。这个过程由称为 DMA 控制器（DMAC）的芯片管理。由于 DMA 设备可以直接在内存之间传输数据，而不是使用 CPU 作为中介，因此可以缓解总线上的拥塞。DMA 通过允许 CPU 执行任务，同时 DMA 系统通过系统和内存总线传输数据来提高系统并发性。

直接内存访问的特点

DMA 方式有如下特点：

• 数据传送以数据块为基本单位
• 所传送的数据从设备直接送入主存，或者从主存直接输出到设备上
• 仅在传送一个或多个数据块的开始和结束时才需 CPU 的干预，而整块数据的传送则是在控制器的控制下完成。

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

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

死锁

僵尸进程和孤儿进程

正常情况下，子进程是通过父进程创建的，子进程在创建新的进程。子进程的结束和父进程的运行是一个异步过程,即父进程永远无法预测子进程 到底什么时候结束。 当一个 进程完成它的工作终止之后，它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程（进程号为1）所收养，并由init进程对它们完成状态收集工作。

僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。

死锁产生的原因

资源竞争和程序执行顺序不当

死锁产生的必要条件

1.互斥条件:一个资源每次只能被一个进程使用;

2.请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放;

3.不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺;

4.循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系;

死锁的恢复方式

通过抢占进行恢复

这种恢复方式一般比较困难而且有些简单粗暴，并不可取。

通过回滚进行恢复

定期检查流程，记录检测点。检测点不仅包含存储映像(memory image)，还包含资源状态(resource state)。一种更有效的解决方式是不要覆盖原有的检测点，而是每出现一个检测点都要把它写入到文件中，这样当进程执行时，就会有一系列的检查点文件被累积起来。

杀死进程恢复

但是杀死一个进程可能照样行不通，这时候就需要杀死别的资源进行恢复。

另外一种方式是选择一个环外的进程作为牺牲品来释放进程资源。

如何破坏死锁

破坏互斥条件

两个打印机同时使用一个资源会造成混乱

破坏保持等待的条件

果我们能阻止持有资源的进程请求其他资源，我们就能够消除死锁。一种实现方式是让所有的进程开始执行前请求全部的资源。无法合理有效利用资源。

允许进程只获得运行初期需要的资源，便开始运行，在运行过程中逐步释放掉分配到的已经使用完毕的资源，然后再去请求新的资源。这样的话，资源的利用率会得到提高，也会减少进程的饥饿问题。

破坏不可抢占条件

当一个已经持有了一些资源的进程在提出新的资源请求没有得到满足时，它必须释放已经保持的所有资源，待以后需要使用的时候再重新申请。这就意味着进程已占有的资源会被短暂地释放或者说是被抢占了。

该种方法实现起来比较复杂，且代价也比较大。释放已经保持的资源很有可能会导致进程之前的工作实效等，反复的申请和释放资源会导致进程的执行被无限的推迟，这不仅会延长进程的周转周期，还会影响系统的吞吐量。

破坏循环等待条件

制定一个标准，一个进程在任何时候只能使用一种资源。如果需要另外一种资源，必须释放当前资源。

还可以通过定义资源类型的线性顺序来预防，可将每个资源编号，当一个进程占有编号为i的资源时，那么它下一次申请资源只能申请编号大于i的资源。如图所示：

这样虽然避免了循环等待，但是这种方法是比较低效的，资源的执行速度回变慢，并且可能在没有必要的情况下拒绝资源的访问，比如说，进程c想要申请资源1，如果资源1并没有被其他进程占有，此时将它分配个进程c是没有问题的，但是为了避免产生循环等待，该申请会被拒绝，这样就降低了资源的利用率

避免死锁

在使用前进行判断，只允许不会产生死锁的进程申请资源

银行家算法

银行家算法的相关数据结构：

可利用资源向量Available：用于表示系统里边各种资源剩余的数目。由于系统里边拥有的资源通常都是有很多种（假设有m种），所以，我们用一个有m个元素的数组来表示各种资源。数组元素的初始值为系统里边所配置的该类全部可用资源的数目，其数值随着该类资源的分配与回收动态地改变。

最大需求矩阵Max：用于表示各个进程对各种资源的额最大需求量。进程可能会有很多个（假设为n个），那么，我们就可以用一个nxm的矩阵来表示各个进程多各种资源的最大需求量

分配矩阵Allocation：顾名思义，就是用于表示已经分配给各个进程的各种资源的数目。也是一个nxm的矩阵。

需求矩阵Need：用于表示进程仍然需要的资源数目，用一个nxm的矩阵表示。系统可能没法一下就满足了某个进程的最大需求（通常进程对资源的最大需求也是只它在整个运行周期中需要的资源数目，并不是每一个时刻都需要这么多），于是，为了进程的执行能够向前推进，通常，系统会先分配个进程一部分资源保证进程能够执行起来。那么，进程的最大需求减去已经分配给进程的数目，就得到了进程仍然需要的资源数目了。

银行家算法通过对进程需求、占有和系统拥有资源的实时统计，确保系统在分配给进程资源不会造成死锁才会给与分配。

死锁避免的优点：不需要死锁预防中的抢占和重新运行进程，并且比死锁预防的限制要少。

死锁避免的限制：

1. 必须事先声明每个进程请求的最大资源量
2. 考虑的进程必须无关的，也就是说，它们执行的顺序必须没有任何同步要求的限制
3. 分配的资源数目必须是固定的。
4. 在占有资源时，进程不能退出

死锁类型

两阶段加锁

虽然很多情况下死锁的避免和预防都能处理，但是效果并不好。随着时间的推移，提出了很多优秀的算法用来处理死锁。例如在数据库系统中，一个经常发生的操作是请求锁住一些记录，然后更新所有锁定的记录。当同时有多个进程运行时，就会有死锁的风险。

一种解决方式是使用 两阶段提交(two-phase locking)。顾名思义分为两个阶段，一阶段是进程尝试一次锁定它需要的所有记录。如果成功后，才会开始第二阶段，第二阶段是执行更新并释放锁。第一阶段并不做真正有意义的工作。

如果在第一阶段某个进程所需要的记录已经被加锁，那么该进程会释放所有锁定的记录并重新开始第一阶段。从某种意义上来说，这种方法类似于预先请求所有必需的资源或者是在进行一些不可逆的操作之前请求所有的资源。

不过在一般的应用场景中，两阶段加锁的策略并不通用。如果一个进程缺少资源就会半途中断并重新开始的方式是不可接受的。

通信死锁

我们上面一直讨论的是资源死锁，资源死锁是一种死锁类型，但并不是唯一类型，还有通信死锁，也就是两个或多个进程在发送消息时出现的死锁。进程 A 给进程 B 发了一条消息，然后进程 A 阻塞直到进程 B 返回响应。假设请求消息丢失了，那么进程 A 在一直等着回复，进程 B 也会阻塞等待请求消息到来，这时候就产生死锁。

尽管会产生死锁，但是这并不是一个资源死锁，因为 A 并没有占据 B 的资源。事实上，通信死锁并没有完全可见的资源。根据死锁的定义来说：每个进程因为等待其他进程引起的事件而产生阻塞，这就是一种死锁。相较于最常见的通信死锁，我们把上面这种情况称为通信死锁(communication deadlock)。

通信死锁不能通过调度的方式来避免，但是可以使用通信中一个非常重要的概念来避免：超时(timeout)。在通信过程中，只要一个信息被发出后，发送者就会启动一个定时器，定时器会记录消息的超时时间，如果超时时间到了但是消息还没有返回，就会认为消息已经丢失并重新发送，通过这种方式，可以避免通信死锁。

但是并非所有网络通信发生的死锁都是通信死锁，也存在资源死锁，下面就是一个典型的资源死锁。

当一个数据包从主机进入路由器时，会被放入一个缓冲区，然后再传输到另外一个路由器，再到另一个，以此类推直到目的地。缓冲区都是资源并且数量有限。如下图所示，每个路由器都有 10 个缓冲区（实际上有很多）。

假如路由器 A 的所有数据需要发送到 B ，B 的所有数据包需要发送到 D，然后 D 的所有数据包需要发送到 A 。没有数据包可以移动，因为在另一端没有缓冲区可用，这就是一个典型的资源死锁。

活锁

某些情况下，当进程意识到它不能获取所需要的下一个锁时，就会尝试礼貌的释放已经获得的锁，然后等待非常短的时间再次尝试获取。可以想像一下这个场景：当两个人在狭路相逢的时候，都想给对方让路，相同的步调会导致双方都无法前进。

现在假想有一对并行的进程用到了两个资源。它们分别尝试获取另一个锁失败后，两个进程都会释放自己持有的锁，再次进行尝试，这个过程会一直进行重复。很明显，这个过程中没有进程阻塞，但是进程仍然不会向下执行，这种状况我们称之为 活锁(livelock)。

收集的题目

page fault

内存映射，其实就是将虚拟内存地址映射到物理内存地址。为了完成内存映射，内核为每个进程都维护了一张页表，记录虚拟地址与物理地址的映射关系。页表实际上存储在 CPU 的内存管理单元 MMU 中。而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行，这是一个次缺页异常（minor page fault）。minor page fault 也称为 soft page fault, 指需要访问的内存不在虚拟地址空间，但是在物理内存中，只需要MMU建立物理内存和虚拟地址空间的映射关系即可。

major page fault指需要访问的内存不在虚拟地址空间，也不在物理内存中，进入内核空间分配物理内存，更新进程页表，还需要swap从磁盘中读取数据换入物理内存中。

1. 当一个进程在调用 malloc 获取虚拟空间地址后，首次访问该地址会发生一次soft page fault。
2. 通常是多个进程访问同一个共享内存中的数据，可能某些进程还没有建立起映射关系，所以访问时会出现soft page fault

invalid fault 也称为 segment fault，指进程需要访问的内存地址不在它的虚拟地址空间范围内，属于越界访问，内核会报 segment fault错误。