hxy的博客

Mia san Mia!

0%

操作系统

发表于 更新于 分类于 Valine：

这个部分用来介绍操作系统，作为非科班同学，这一块应该好好学习，不仅仅是应付面试，之前就突击了线程、进程、死锁的知识，别的就是一窍不通了，这次尽可能了解完整的操作系统知识体系。一个简单的例子：

  • 在我们的JS代码里，只需要输入 console.log(1 + 1); 就可以在浏览器面板中看到2，这其中发生了什么事情呢?
  • 首先键盘输入代码1 + 1到显示器输出2, 需要CPU控制键盘（输入设备），将获取的1 + 1指令放入内存
  • 然后CPU的控制器从内存中取出指令，并分析出指令是让计算机做一个1 + 1的加法运算
  • 此时CPU的控制将控制CPU的运算器做1 + 1的加法运算，并得出结果2
  • 最后CPU控制器控制运算器将结果返给内存，内存也在CPU控制器的控制下，将结果2返回给屏幕（输出设备）

好了，这里问题是，如果没有操作系统，一个简单的1+1运算，你的js代码还需要考虑这些硬件的协调工作，比如你的代码要协调CPU资源什么时候读取你的代码，什么时候把进程切换到别的进程。。。这些脏活累活都是操作系统帮你屏蔽了，要不这代码可咋写啊。。。

1. 操作系统简介

1.1 什么是操作系统(面试必背)

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

img

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

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

  • 管理计算机资源，这些资源包括 CPU、内存、磁盘驱动器、打印机等。
  • 提供一种图形界面，就像我们前面描述的那样，它提供了用户和计算机之间的桥梁。
  • 为其他软件提供服务，操作系统与软件进行交互，以便为其分配运行所需的任何必要资源。

1.2 操作系统的主要功能

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

  • 进程管理: 进程管理的主要作用就是任务调度，在单核处理器下，操作系统会为每个进程分配一个任务，进程管理的工作十分简单；而在多核处理器下，操作系统除了要为进程分配任务外，还要解决处理器的调度、分配和回收等问题
  • 内存管理：内存管理主要是操作系统负责管理内存的分配、回收，在进程需要时分配内存以及在进程完成时回收内存，协调内存资源，通过合理的页面置换算法进行页面的换入换出
  • 设备管理：根据确定的设备分配原则对设备进行分配，使设备与主机能够并行工作，为用户提供良好的设备使用界面。
  • 文件管理：有效地管理文件的存储空间，合理地组织和管理文件系统，为文件访问和文件保护提供更有效的方法及手段。
  • 提供用户接口：操作系统提供了访问应用程序和硬件的接口，使用户能够通过应用程序发起系统调用从而操纵硬件，实现想要的功能。

1.3 操作系统的四个特征

操作系统有以下四个特征：

  • 并发
  • 共享
  • 虚拟
  • 异步

接下来，我们分别来搞定每一个特征。

1.3.1 并发是什么？和并行有啥区别？

举个例子，假如你在语音跟同学玩英雄联盟：

  • 你一边用鼠标移动打游戏，同时语音嘴里说”队友挂机，真坑！”, 这叫并行（边移动鼠标边语音BB）
  • 你一边用鼠标移动打游戏，然后离开鼠标，去砸键盘, 这叫并发（先离开鼠标然后砸键盘）

并发只是把时间分成若干段，使多个任务交替的执行。 并行的关键是你有同时处理多个任务的能力。

  • 所以我认为它们最关键的点就是：是否是『同时』

那么对于操作系统而言，操作系统的并发性指计算机系统中同时存在多个运行着的程序。

  • 比如说以前的计算机是单核CPU，那么如何在操作系统上同时运行QQ、浏览器，记事本、ppt等多个程序呢，这就需要操作系统具有并发性
  • CPU时间片（操作系统分配给每个正在运行的进程微观上的一段CPU时间）轮着给进程执行的时间，因为执行速度很快，看起来就像浏览器能同时执行任务一样。
  • 有人会说，现在都多核CPU了，还需要并发吗，答案肯定是需要的，比如你有8核CPU，但是桌面要执行的任务很可能超过8个。

1.3.2 共享是什么？共享和并发有什么关系？

举一个例子： 你同时用QQ和微信发”年终述职.ppt”文件给领导，这时候QQ和微信都在读取这个ppt文件

  • 两个进程正在并发执行（并发性）
  • 需要共享地访问硬盘资源（共享性） 如果没有并发，也就是只有一个进程在运行，那就没有共享了。如果没有共享，QQ和微信就不能同时发文件，无法同时访问硬盘资源，也就无法并发。

其中共享分为两种情况：

img

  • 上面的例子，QQ和微信都要访问同一个文件，属于同时共享。
  • 对于互斥共享，比如打印机，只能同一时刻被一个进程控制，如打印机，虽然他可以提供多个进程使用，但是试想，同时打印多个东西，会造成打印结果的混乱，因此规定，某些资源在进行使用的时候，必须要先让某进程先使用，等使用完之后，再同一其他进程进行访问。
  • 我们把一段时间内只允许一个进程访问的资源称为独占资源，或临界资源。

1.3.3 虚拟是什么？

先举例，再说定义。

假如一个叫范桶的货车司机在玩英雄联盟，平时因为酒驾太多，自己装了很多次别人的车，住院也花了不少钱，所以家里没钱，只能买个1G内存的二手电脑玩游戏。可英雄联盟至少需要2G内存，这就奇怪了，老司机虽然一到团战就卡死，但是还是能运行英雄联盟。为什么需要2G内存的游戏，1G电脑还能运行呢？

这就是虚拟存储器技术。实际上只有1G内存，在用户看来远远大于1G。

还有，范桶的电脑还是单核的，但范桶居然能一边迅雷下着爱情动作片，一边听着网易云音乐，还在QQ上撩妹子，既然一个程序要被分配CPU才能正常执行，按道理来说同一时间只有1个程序在运行，为啥电脑能同时运行这么多程序呢？

这就是虚拟处理器技术。实际上只有一个CPU，在用户看来有3个CPU在同时服务。（因为CPU来回切换进程的速度特别块，感觉就像很多CPU在为我们服务）

虚拟这块的总结如下:

img

1.3.4 异步性是什么?

异步在JS里是很常见的，比如ajax请求，我们发出请求后并不是立马得到信息，也不会去等待ajax结果返回，而是继续执行下面的代码，等ajax结果回来，通知JS线程。这就跟CPU处理进程很类似。

比如，CPU正在执行一个进程，进程需要读取文件，读取文件可能要1个小时，那CPU不可能一直等一个小时，CPU会继续把时间片分给别的进程，等文件读取完成了（类似ajax返回结果了），CPU再继续执行之前被中断的进程。

所以异步性就是描述进程这种以不可预知的速度走走停停、何时开始何时暂停何时结束不可预知的性质。

1.4 软件访问硬件的几种方式

软件访问硬件其实就是一种 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 发出中断信号。

1.5 常见的操作系统

常见的操作系统只有三种：Windows、macOS 和 Linux。

1.5.1 Linux应用程序可以直接在Windows下运行吗

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

img

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

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

1.5.2 Linux 操作系统的启动过程

当计算机电源通电后，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 程序会在终端上输入

1
login:

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

整个系统启动过程如下

img

1.5.3 实时系统

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

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

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

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

1.6 操作系统结构

1.6.1 单体系统

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

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

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

img

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

1.6.2 分层系统

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

img

1.6.3 微内核

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

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

img

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

1.6.4 客户-服务器模式

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

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

img

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

1.7 操作系统运行机制和体系结构

预备知识： 什么是指令

比如说，如下图：

img

a+b是一段程序代码，a+b在CPU看来并不能一步完成，可以翻译成汇编语言：

1
2
3
4
5
6
// 意思是将内存的16号单元数据，放到A寄存器，
LOAD A, 16
// 意思是将内存的16号单元数据，放到B寄存器
LOAD B, 17
// 存器里的A,B数据相加，得到C
ADD C, A, B

这里就可以看得出来，指令是CPU能识别和执行的最基本命令。

1.7.1 两种指令、两种处理器状态、两种程序

假如说一个用户可以随意把服务器上的所有文件删光，这是很危险的。所以有些指令普通用户是不能使用的，只能是权限较高的用户能使用。此时指令就分为了两种，如下图：

img

这就引出一个问题：CPU如何判断当前是否可以执行特权指令？ 如下图:

img

CPU通常有两种工作模式即：内核态和用户态，而在PSW（这个不用管，就知道有一个寄存器的标志位0表示用户态，1表示核心态）中有一个二进制位控制这两种模式。

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

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

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

必背考点：内核态与用户态概念

  • 内核态：cpu 可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu 也可以将自己从一个程序切换到另一个程序。
  • 用户态：只能受限的访问内存，且不允许访问外围设备，占用 cpu 的能力被剥夺，cpu 资源可以被其他程序获取。

用户态和内核态是如何切换的？

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

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

他们的工作流程如下：

img

  • 首先用户程序会调用 glibc 库，glibc 是一个标准库，同时也是一套核心库，库中定义了很多关键 API。
  • glibc 库知道针对不同体系结构调用系统调用的正确方法，它会根据体系结构应用程序的二进制接口设置用户进程传递的参数，来准备系统调用。
  • 然后，glibc 库调用软件中断指令(SWI) ，这个指令通过更新 CPSR 寄存器将模式改为超级用户模式，然后跳转到地址 0x08 处。
  • 到目前为止，整个过程仍处于用户态下，在执行 SWI 指令后，允许进程执行内核代码，MMU 现在允许内核虚拟内存访问
  • 从地址 0x08 开始，进程执行加载并跳转到中断处理程序，这个程序就是 ARM 中的 vector_swi()。
  • 在 vector_swi() 处，从 SWI 指令中提取系统调用号 SCNO，然后使用 SCNO 作为系统调用表 sys_call_table 的索引，调转到系统调用函数。
  • 执行系统调用完成后，将还原用户模式寄存器，然后再以用户模式执行。

对于应用程序而言，有的程序能执行特权指令，有的程序只能执行非特权指令。所以操作系统里的程序又分为两种：

img

必背考点：用户态到内核态的切换

  • 异常事件： 当 CPU 正在执行运行在用户态的程序时，突然发生某些预先不可知的异常事件，这个时候就会触发从当前用户态执行的进程转向内核态执行相关的异常事件，典型的如缺页异常。
  • 外围设备的中断：当外围设备完成用户的请求操作后，会像 CPU 发出中断信号，此时，CPU 就会暂停执行下一条即将要执行的指令，转而去执行中断信号对应的处理程序，如果先前执行的指令是在用户态下，则自然就发生从用户态到内核态的转换。

1.7.2 操作系统内核简单介绍

从下图，我们先看看操作系统内核包含哪些

img

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

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

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

操作系统内核中跟硬件紧密相关的部分有：

  • 时钟管理。操作系统的时钟管理是依靠硬件定时器的。时钟管理相当重要，比如我们获取时间信息，进程切换等等都是要依靠时钟管理。
  • 中断处理
  • 原语。可以简单理解为用来实现某个特定功能，在执行过程中不可被中断的指令集合。原语有一个非常重要的特性，就是原子性（其运行一气呵成，不可中断）。

1.7.3 陷入内核

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

img

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

1.8 中断

1.8.1 什么是中断

  • 在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。 下面举一个例子：

img

第一个应用程序在用户态执行了一段时间后

img

接着操作系统切换到核心态，处理中断信号

img

  • 操作系统发现中断的信号是第一个程序的时间片（每个程序不能一直执行，CPU会给每个程序一定的执行时间，这段时间就是时间片）用完了，应该换第二个应用程序执行了
  • 切换到第2个进程后，操作系统会将CPU的使用权交换给第二个应用程序，接着第二个应用程序就在用户态下开始执行。
  • 进程2需要调用打印机资源，这时会执行一个系统调用（后面会讲系统调用，这里简单理解为需要操作系统进入核心态处理的函数），让操作系统进入核心态，去调用打印机资源
  • 打印机开始工作，此时进程2因为要等待打印机启动，操作系统就不等待了（等到打印机准备好了，再回来执行程序2），直接切换到第三个应用程序执行
  • 等到打印机准备好了，此时打印机通过I/O控制器会给操作系统发出一个中断信号，操作系统又进入到核心态，发现这个中断是因为程序2等待打印机资源，现在打印机准备好了，就切换到程序2，切换到用户态，把CPU给程序2继续执行。

好了，现在可以给出一个结论，就是用户态、核心态之间的切换是怎么实现的?

  • “用户态 —> 核心态”是通过中断实现的。并且中断是实现其的唯一途径。
  • “核心态 —> 用户态”的切换时通过执行一个特权指令，将程序状态的标志位设为用户态。

1.8.2 中断的分类

举一个例子，什么是内中断和外中断：

接着说之前的范桶同学，小时候不爱学习，每次学习着学习着突然异想天开，回过神来已经过好好长一段时间，这是内部中断。想着想着老师走过来，给了范捅一嘴巴，这是外部中断。

官方解释如下：

img

  • 内中断常见的情况如程序非法操作(比如你要拿的的数据的内存地址不是内存地址，是系统无法识别的地址)，地址越界(比如系统给你的程序分配了一些内存，但是你访问的时候超出了你应该访问的内存范围)、浮点溢出(比如系统只能表示1.1到5.1的范围，你输入一个100, 超出了计算机能处理的范围)，或者异常，陷入trap（是指应用程序请求系统调用造成的，什么是系统调用，后面小节会举例讲）。
  • 外中断常见的情况如I/O中断（由I/O控制器产生，用于发送信号通知操作完成等信号，比如进程需要请求打印机资源，打印机有一个启动准备的过程，准备好了就会给CPU一个I/O中断，告诉它已经准备好了）、时钟中断（由处理器内部的计时器产生，允许操作系统以一定规程执行函数，操作系统每过大约15ms会进行一次线程调度，就是利用时钟中断来实现的）。

1.8.3 系统调用

为什么需要系统调用？

  • 比如你的程序需要读取文件信息，可读取文件属于读取硬盘里的数据，这个操作应该时CPU在内核态去完成的，我们的应用程序怎么让CPU去帮助我们切换到内核态完成这个工作呢，这里就需要系统调用了。
  • 这里就引出系统调用的概念和作用。
  • 应用程序通过系统调用请求操作系统的服务。系统中的各种共享资源都由操作系统统一管理，因此在用户程序中，凡是与资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。

以下内容简单看一下即可，系统调用的分类：

img

需要注意的是，库函数和系统调用容易混淆。

  • 库是可重用的模块 处于用户态
  • 进程通过系统调用从用户态进入内核态， 库函数中有很大部分是对系统调用的封装

举个例子：比如windows和linux中，创建进程的系统调用方法是不一样的。 但在node中的只需要调用相同函数方法就可以创建一个进程。例如

1
2
3
4
5
6
7
8
9
// 引入创建子进程的模块
const childProcess = require('child_process')
// 获取cpu的数量
const cpuNum = require('os').cpus().length

// 创建与cpu数量一样的子进程
for (let i = 0; i < cpuNum; ++i) {
	childProcess.fork('./worker.js')
}

2. 进程和线程

2.1 多处理系统的优势

随着处理器的不断增加，我们的计算机系统由单机系统变为了多处理系统，多处理系统的吞吐量比较高，多处理系统拥有多个并行的处理器，这些处理器共享时钟、内存、总线、外围设备等。

img

多处理系统由于可以共享资源，因此可以开源节流，省钱。整个系统的可靠性也随之提高。

2.2 为什么要引入进程

  • 早期的计算机只支持单道程序（是指所有进程一个一个排队执行，A进程执行时，CPU、内存、I/O设备全是A进程控制的，等A进程执行完了，才换B进程，然后对应的资源比如CPU、内存这些才能换B用）。

    img

  • 现代计算机是多道程序执行，就是同时看起来有多个程序在一起执行，那每个程序执行都需要系统分配给它资源来执行，比如CPU、内存。

  • 拿内存来说，操作系统要知道给A程序分配的内存有哪些，给B程序分配的内存有哪些，这些都要有小本本记录下来，这个小本本就是进程的一部分，进程的一大职责就是记录目前程序运行的状态。

  • 系统为每个运行的程序配置一个数据结构，称为进程控制块（PCB），用来描述进程的各种信息（比如代码段放在哪）。

2.3 进程和进程控制块的定义

2.3.1 进程

来源百度百科：

进程（Process） 是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。 在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。程序是指令、数据及其组织形式的描述，进程是程序的实体。

简要的说，进程就是具有独立功能的程序在数据集合上运行的过程(强调动态性)，换而言之，进程就是正在执行程序的实例，比如说 Web 程序就是一个进程，shell 也是一个进程，文章编辑器 typora 也是一个进程。

操作系统负责管理所有正在运行的进程，操作系统会为每个进程分配特定的时间来占用 CPU，操作系统还会为每个进程分配特定的资源。

必背考点

  • 进程是程序在一个数据集合上运行的过程。
  • 进程实体 = 程序段 + 数据段 + PCB
  • 进程是操作系统资源分配和资源调度的基本单位。
  • 孤儿进程和僵尸进程
    • 孤儿进程：
      • 一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
      • 孤儿进程并不会有什么危害。
    • 僵尸进程：
      • 一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。
      • 进程号就会一直被占用，但是系统所能使用的进程号是有限的。

2.3.2 进程控制块

操作系统为了跟踪每个进程的活动状态，维护了一个进程控制块。在进程控制块的内部，列出了每个进程的状态以及每个进程使用的资源等。

分别说明一下

img

  • 进程标识符PID相当于身份证。是在进程被创建时，操作系统会为该进程分配一个唯一的、不重复的ID，用于区分不同的进程。
  • 用户标识符UID用来表示这个进程所属的用户是谁。
  • 进程当前状态和优先级下一小节会详细介绍
  • 程序段指针是指当前进程的程序在内存的什么地方。
  • 数据段指针是指当前进程的数据在内存的什么地方。
  • 键盘和鼠标是指进程被分配得到的I/O设备。
  • 各种寄存器值是指比如把程序计数器的值，比如有些计算的结果算到一半，进程切换时需要把这些值保存下来

2.4 进程的状态

2.4.1 进程的组织

在一个系统中，通常由数十、数百乃至数千个PCB。为了对他们加以有效的管理，应该用适当的方式把这些PCB组织起来。这里介绍一种组织方式，类似数据结构里的链表。

img

2.4.2 进程的状态模型

进程是程序的一次执行。在这个执行过程中，有时进程正在被CPU处理，有时又需要等待CPU服务，可见，进程的 状态是会有各种变化。为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态。

进程的三态模型

当一个进程开始运行时，它可能会经历下面这几种状态

img

进程的三种基本状态详细图：

img

图中会涉及三种状态

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

逻辑上来说，运行态和就绪态是很相似的。这两种情况下都表示进程可运行，但是第二种情况没有获得 CPU 时间分片。第三种状态与前两种状态不同的原因是这个进程不能运行，CPU 空闲时也不能运行。

三种状态会涉及四种状态间的切换，在操作系统发现进程不能继续执行时会发生状态1的轮转，在某些系统中进程执行系统调用，例如 pause，来获取一个阻塞的状态。在其他系统中包括 UNIX，当进程从管道或特殊文件（例如终端）中读取没有可用的输入时，该进程会被自动终止。

转换 2 和转换 3 都是由进程调度程序（操作系统的一部分）引起的，进程本身不知道调度程序的存在。转换 2 的出现说明进程调度器认定当前进程已经运行了足够长的时间，是时候让其他进程运行 CPU 时间片了。当所有其他进程都运行过后，这时候该是让第一个进程重新获得 CPU 时间片的时候了，就会发生转换 3。

程序调度指的是，决定哪个进程优先被运行和运行多久，这是很重要的一点。已经设计出许多算法来尝试平衡系统整体效率与各个流程之间的竞争需求。

当进程等待的一个外部事件发生时（如从外部输入一些数据后），则发生转换 4。如果此时没有其他进程在运行，则立刻触发转换 3，该进程便开始运行，否则该进程会处于就绪阶段，等待 CPU 空闲后再轮到它运行。

进程的五态模型

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

进程的另新建 和 终止 状态：

img

img

  • 新建态：进程的新建态就是进程刚创建出来的时候

创建进程需要两个步骤：即为新进程分配所需要的资源和空间，设置进程为就绪态，并等待调度执行。

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

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

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

2.4.3 进程状态的转换

进程的状态并不是一成不变的，在一定情况下会动态转换。

img

以上的这些进程状态的转换是如何实现的呢，这就要引出下一个角色了，叫原语。

  • 原语是不可被中断的原子操作。我们举一个例子看看原语是怎么保证不可中断的。

img

原语采用关中断指令和开中断指令实现。

  • 首先执行关中断指令
  • 然后外部来了中断信号，不予以处理
  • 等到开中断指令执行后，其他中断信号才有机会处理。

2.4.4 进程的终止

进程在创建之后，它就开始运行并做完成任务。然而，没有什么事儿是永不停歇的，包括进程也一样。进程早晚会发生终止，但是通常是由于以下情况触发的

  • 正常退出(自愿的)
  • 错误退出(自愿的)
  • 严重错误(非自愿的)
  • 被其他进程杀死(非自愿的)

正常退出

多数进程是由于完成了工作而终止。当编译器完成了所给定程序的编译之后，编译器会执行一个系统调用告诉操作系统它完成了工作。这个调用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。面向屏幕中的软件也支持自愿终止操作。字处理软件、Internet 浏览器和类似的程序中总有一个供用户点击的图标或菜单项，用来通知进程删除它锁打开的任何临时文件，然后终止。

错误退出

进程发生终止的第二个原因是发现严重错误，例如，如果用户执行如下命令

1
cc foo.c

为了能够编译 foo.c 但是该文件不存在，于是编译器就会发出声明并退出。在给出了错误参数时，面向屏幕的交互式进程通常并不会直接退出，因为这从用户的角度来说并不合理，用户需要知道发生了什么并想要进行重试，所以这时候应用程序通常会弹出一个对话框告知用户发生了系统错误，是需要重试还是退出。

严重错误

进程终止的第三个原因是由进程引起的错误，通常是由于程序中的错误所导致的。例如，执行了一条非法指令，引用不存在的内存，或者除数是 0 等。在有些系统比如 UNIX 中，进程可以通知操作系统，它希望自行处理某种类型的错误，在这类错误中，进程会收到信号（中断），而不是在这类错误出现时直接终止进程。

被其他进程杀死

第四个终止进程的原因是，某个进程执行系统调用告诉操作系统杀死某个进程。在 UNIX 中，这个系统调用是 kill。在 Win32 中对应的函数是 TerminateProcess（注意不是系统调用）。

2.5 进程的通信

为什么需要进程间通信呢？

因为进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

img

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

进程间通信模型

进程间的通信方式比较多，首先你需要理解下面这几个概念

  • 竞态条件：即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(race condition)。

  • 临界区：不仅共享资源会造成竞态条件，事实上共享文件、共享内存也会造成竞态条件、那么该如何避免呢？或许一句话可以概括说明：禁止一个或多个进程在同一时刻对共享资源（包括共享内存、共享文件等）进行读写。换句话说，我们需要一种 互斥(mutual exclusion) 条件，这也就是说，如果一个进程在某种方式下使用共享变量和文件的话，除该进程之外的其他进程就禁止做这种事（访问统一资源）。

    一个好的解决方案，应该包含下面四种条件

    1. 任何时候两个进程不能同时处于临界区
    2. 不应对 CPU 的速度和数量做任何假设
    3. 位于临界区外的进程不得阻塞其他进程
    4. 不能使任何进程无限等待进入临界区

    img

  • 忙等互斥：当一个进程在对资源进行修改时，其他进程必须进行等待，进程之间要具有互斥性，我们讨论的解决方案其实都是基于忙等互斥提出的。

进程间的通信用专业一点的术语来表示就是 Inter Process Communication，IPC，它主要有下面 7种通信方式

img

必背考点：进程有哪些通信方式

  • 消息传递：消息传递是进程间实现通信和同步等待的机制，使用消息传递，进程间的交流不需要共享变量，直接就可以进行通信；消息传递分为发送方和接收方
  • 先进先出队列：先进先出队列指的是两个不相关联进程间的通信，两个进程之间可以彼此相互进程通信，这是一种全双工通信方式
  • 管道：管道用于两个相关进程之间的通信，这是一种半双工的通信方式，如果需要全双工，需要另外一个管道。
  • 直接通信：在这种进程通信的方式中，进程与进程之间只存在一条链接，进程间要明确通信双方的命名。
  • 间接通信：间接通信是通信双方不会直接建立连接，而是找到一个中介者，这个中介者可能是个对象等等，进程可以在其中放置消息，并且可以从中删除消息，以此达到进程间通信的目的。
  • 消息队列：消息队列是内核中存储消息的链表，它由消息队列标识符进行标识，这种方式能够在不同的进程之间提供全双工的通信连接。
  • 共享内存：共享内存是使用所有进程之间的内存来建立连接，这种类型需要同步进程访问来相互保护。
  • 套接字： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。
  • 信号：用于Linux系统中，信号可以在任何时候发给某一进程，而无需知道该进程的状态。
  • 信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

详细介绍3种

2.5.1 共享内存

因为两个进程的存储空间不能相互访问，所以操作系统就提供的一个内存空间让彼此都能访问，这就是共享存储的原理。

img

其中，介绍一下基于存储区的共享。

  • 在内存中画出一块共享存储区，数据的形式、存放位置都是由进程控制，而不是操作系统。

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

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

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

      延伸阅读：Linux支持的主要三种共享内存方式：mmap()系统调用、Posix共享内存，以及System V共享内存实践

      共享内存原理图

2.5.2 管道/匿名管道(pipe)

img

  • 管道数据是以字符流（注意不是字节流）的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道。

  • 如果没写满就不允许读。如果都没空就不允许写。

  • 只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程);

  • 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在与内存中。

  • 数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。数据一旦被读出，就从管道中被丢弃，这就意味着读进程最多只能有一个。

    进程间管道通信模型

    管道的实质：
    管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据，管道一端的进程顺序的将数据写入缓冲区，另一端的进程则顺序的读出数据。
    该缓冲区可以看做是一个循环队列，读和写的位置都是自动增长的，不能随意改变，一个数据只能被读一次，读出来以后在缓冲区就不复存在了。
    当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写。

    管道的局限：
    管道的主要局限性正体现在它的特点上：

    • 只支持单向数据流；
    • 只能用于具有亲缘关系的进程之间；
    • 没有名字；
    • 管道的缓冲区是有限的（管道制存在于内存中，在管道创建时，为缓冲区分配一个页面大小）；
    • 管道所传送的是无格式字节流，这就要求管道的读出方和写入方必须事先约定好数据的格式，比如多少字节算作一个消息（或命令、或记录）等等；

2.5.3 消息(Message)队列

进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的"发送消息/接收消息"两个原语进行数据交换。

其中消息是什么意思呢？就好像你发QQ消息，消息头的来源是你，消息体是你发的内容。如下图：

img

接下来我们介绍一种间接通信的方式（很像中介者模式或者发布-订阅模式）, 如下图：中介者是信箱，进程通过它来收发消息。

img

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

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

  • 另外与管道不同的是，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达。延伸阅读：消息队列C语言的实践

    消息队列特点总结：
    （1）消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识.
    （2）消息队列允许一个或多个进程向它写入与读取消息.
    （3）管道和消息队列的通信数据都是先进先出的原则。
    （4）消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比FIFO更有优势。
    （5）消息队列克服了信号承载信息量少，管道只能承载无格式字 节流以及缓冲区大小受限等缺。
    （6）目前主要有两种类型的消息队列：POSIX消息队列以及System V消息队列，系统V消息队列目前被大量使用。系统V消息队列是随内核持续的，只有在内核重起或者人工删除时，该消息队列才会被删除。

    2.5.4 有名管道(FIFO)

    匿名管道，由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道(FIFO)。
    有名管道不同于匿名管道之处在于它提供了一个路径名与之关联，以有名管道的文件形式存在于文件系统中，这样，即使与有名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信，因此，通过有名管道不相关的进程也能交换数据。值的注意的是，有名管道严格遵循先进先出(first in first out),对匿名管道及有名管道的读总是从开始处返回数据，对它们的写则把数据添加到末尾。它们不支持诸如lseek()等文件定位操作。有名管道的名字存在于文件系统中，内容存放在内存中。

匿名管道和有名管道总结：
（1）管道是特殊类型的文件，在满足先入先出的原则条件下可以进行读写，但不能进行定位读写。
（2）匿名管道是单向的，只能在有亲缘关系的进程间通信；有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
（3）无名管道阻塞问题：无名管道无需显示打开，创建时直接返回文件描述符，在读写时需要确定对方的存在，否则将退出。如果当前进程向无名管道的一端写数据，必须确定另一端有某一进程。如果写入无名管道的数据超过其最大值，写操作将阻塞，如果管道中没有数据，读操作将阻塞，如果管道发现另一端断开，将自动退出。
（4）有名管道阻塞问题：有名管道在打开时需要确实对方的存在，否则将阻塞。即以读方式打开某管道，在此之前必须一个进程以写方式打开管道，否则阻塞。此外，可以以读写（O_RDWR）模式打开有名管道，即当前进程读，当前进程写，不会阻塞。

延伸阅读：该博客有匿名管道和有名管道的C语言实践

2.5.5 信号(Signal)

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

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

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

    Linux系统中常用信号：
    （1）SIGHUP：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。
    （2）SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。
    （3）SIGQUIT：程序退出信号。程序运行过程中，按Ctrl+\\键将产生该信号。
    （4）SIGBUS和SIGSEGV：进程访问非法地址。
    （5）SIGFPE：运算中出现致命错误，如除零操作、数据溢出等。
    （6）SIGKILL：用户终止进程执行信号。shell下执行kill -9发送该信号。
    （7）SIGTERM：结束进程信号。shell下执行kill 进程pid发送该信号。
    （8）SIGALRM：定时器信号。
    （9）SIGCLD：子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。

信号来源
信号是软件层次上对中断机制的一种模拟，是一种异步通信方式，，信号可以在用户空间进程和内核之间直接交互，内核可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件主要有两个来源：

  • 硬件来源：用户按键输入Ctrl+C退出、硬件异常如无效的存储访问等。
  • 软件终止：终止进程信号、其他进程调用kill函数、软件异常产生信号。

信号生命周期和处理流程
（1）信号被某个进程产生，并设置此信号传递的对象（一般为对应进程的pid），然后传递给操作系统；
（2）操作系统根据接收进程的设置（是否阻塞）而选择性的发送给接收者，如果接收者阻塞该信号（且该信号是可以阻塞的），操作系统将暂时保留该信号，而不传递，直到该进程解除了对此信号的阻塞（如果对应进程已经退出，则丢弃此信号），如果对应进程没有阻塞，操作系统将传递此信号。
（3）目的进程接收到此信号后，将根据当前进程对此信号设置的预处理方式，暂时终止当前代码的执行，保护上下文（主要包括临时寄存器数据，当前程序位置以及当前CPU的状态）、转而执行中断服务程序，执行完成后在回复到中断的位置。当然，对于抢占式内核，在中断返回时还将引发新的调度。

信号的生命周期

2.5.6 信号量(semaphore)

信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。
为了获得共享资源，进程需要执行下列操作：
（1）创建一个信号量：这要求调用者指定初始值，对于二值信号量来说，它通常是1，也可是0。
（2）等待一个信号量：该操作会测试这个信号量的值，如果小于0，就阻塞。也称为P操作。
（3）挂出一个信号量：该操作将信号量的值加1，也称为V操作。

为了正确地实现信号量，信号量值的测试及减1操作应当是原子操作。为此，信号量通常是在内核中实现的。Linux环境中，有三种类型：Posix（可移植性操作系统接口）有名信号量（使用Posix IPC名字标识）、Posix基于内存的信号量（存放在共享内存区中）、System V信号量（在内核中维护）。这三种信号量都可用于进程间或线程间的同步。

两个进程使用一个二值信号量

一个进程两个线程共享基于内存的信号量

两个进程所以用一个Posix有名二值信号量

信号量与普通整型变量的区别：
（1）信号量是非负整型变量，除了初始化之外，它只能通过两个标准原子操作：wait(semap) , signal(semap) ; 来进行访问；
（2）操作也被成为PV原语（P来源于荷兰语proberen”测试”，V来源于荷兰语verhogen”增加”，P表示通过的意思，V表示释放的意思），而普通整型变量则可以在任何语句块中被访问；

信号量与互斥量之间的区别：
（1）互斥量用于线程的互斥，信号量用于线程的同步。这是互斥量和信号量的根本区别，也就是互斥和同步之间的区别。
互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。
在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源
（2）互斥量值只能为0/1，信号量值可以为非负整数。
也就是说，一个互斥量只能用于一个资源的互斥访问，它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。当信号量为单值信号量是，也可以完成一个资源的互斥访问。
（3）互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。

2.5.7 套接字(socket)

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

Socket是应用层和传输层之间的桥梁

套接字是支持TCP/IP的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。

套接字特性
套接字的特性由3个属性确定，它们分别是：域、端口号、协议类型。
（1）套接字的域
它指定套接字通信中使用的网络介质，最常见的套接字域有两种：
一是AF_INET，它指的是Internet网络。当客户使用套接字进行跨网络的连接时，它就需要用到服务器计算机的IP地址和端口来指定一台联网机器上的某个特定服务，所以在使用socket作为通信的终点，服务器应用程序必须在开始通信之前绑定一个端口，服务器在指定的端口等待客户的连接。
另一个域AF_UNIX，表示UNIX文件系统，它就是文件输入/输出，而它的地址就是文件名。
（2）套接字的端口号
每一个基于TCP/IP网络通讯的程序(进程)都被赋予了唯一的端口和端口号，端口是一个信息缓冲区，用于保留Socket中的输入/输出信息，端口号是一个16位无符号整数，范围是0-65535，以区别主机上的每一个程序（端口号就像房屋中的房间号），低于256的端口号保留给标准应用程序，比如pop3的端口号就是110，每一个套接字都组合进了IP地址、端口，这样形成的整体就可以区别每一个套接字。
（3）套接字协议类型
因特网提供三种通信机制，
一是流套接字，流套接字在域中通过TCP/IP连接实现，同时也是AF_UNIX中常用的套接字类型。流套接字提供的是一个有序、可靠、双向字节流的连接，因此发送的数据可以确保不会丢失、重复或乱序到达，而且它还有一定的出错后重新发送的机制。
二个是数据报套接字，它不需要建立连接和维持一个连接，它们在域中通常是通过UDP/IP协议实现的。它对可以发送的数据的长度有限制，数据报作为一个单独的网络消息被传输,它可能会丢失、复制或错乱到达，UDP不是一个可靠的协议，但是它的速度比较高，因为它并一需要总是要建立和维持一个连接。
三是原始套接字，原始套接字允许对较低层次的协议直接访问，比如IP、 ICMP协议，它常用于检验新的协议实现，或者访问现有服务中配置的新设备，因为RAW SOCKET可以自如地控制Windows下的多种协议，能够对网络底层的传输机制进行控制，所以可以应用原始套接字来操纵网络层和传输层应用。比如，我们可以通过RAW SOCKET来接收发向本机的ICMP、IGMP协议包，或者接收TCP/IP栈不能够处理的IP包，也可以用来发送一些自定包头或自定协议的IP包。网络监听技术很大程度上依赖于SOCKET_RAW。

原始套接字与标准套接字的区别在于：
原始套接字可以读写内核没有处理的IP数据包，而流套接字只能读取TCP协议的数据，数据报套接字只能读取UDP协议的数据。因此，如果要访问其他协议发送数据必须使用原始套接字。

套接字通信的建立

Socket通信基本流程

服务器端
（1）首先服务器应用程序用系统调用socket来创建一个套接字，它是系统分配给该服务器进程的类似文件描述符的资源，它不能与其他的进程共享。
（2）然后，服务器进程会给套接字起个名字，我们使用系统调用bind来给套接字命名。然后服务器进程就开始等待客户连接到这个套接字。
（3）接下来，系统调用listen来创建一个队列并将其用于存放来自客户的进入连接。
（4）最后，服务器通过系统调用accept来接受客户的连接。它会创建一个与原有的命名套接不同的新套接字，这个套接字只用于与这个特定客户端进行通信，而命名套接字（即原先的套接字）则被保留下来继续处理来自其他客户的连接（建立客户端和服务端的用于通信的流，进行通信）。

客户端
（1）客户应用程序首先调用socket来创建一个未命名的套接字，然后将服务器的命名套接字作为一个地址来调用connect与服务器建立连接。
（2）一旦连接建立，我们就可以像使用底层的文件描述符那样用套接字来实现双向数据的通信（通过流进行数据传输）。
延伸阅读 ：Java socket编程

参考引用

1. 进程间通信–管道
2. Linux进程间通信——使用共享内存
3. 进程间通信—共享内存
4. 信号量与互斥锁
5. 信号量

2.6 进程的同步和互斥

同步。是指多个进程中发生的事件存在某种先后顺序。即某些进程的执行必须先于另一些进程。

比如说进程A需要从缓冲区读取进程B产生的信息，当缓冲区为空时，进程B因为读取不到信息而被阻塞。而当进程A产生信息放入缓冲区时，进程B才会被唤醒。概念如图1所示。

img

互斥。是指多个进程不允许同时使用同一资源。当某个进程使用某种资源的时候，其他进程必须等待。

比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源,进程B才可以继续执行。概念如图3所示。

img

必背考点：进程同步的原则

  • 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
  • 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
  • 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区。
  • 让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

2.6.1 信号量（了解概念即可）

信号量主要是来解决进程的同步和互斥的，我们前端需要了解，如果涉及到同步和互斥的关系（我们编程大多数关于流程的逻辑问题，本质不就是同步和互斥吗？）

在操作系统中，常用P、V信号量来实现进程间的同步和互斥，我们简单了解一下一种常用的信号量，记录型信号量来简单了解一下信号量本质是怎样的。（c语言来表示，会有备注）

1
2
3
4
5
/*记录型信号量的定义*/
typedef struct {
    int value; // 剩余资源
    Struct process *L // 等待队列
} semaphore

意思是信号量的结构有两部分组成，一部分是剩余资源value，比如目前有两台打印机空闲，那么剩余资源就是2，谁正在使用打印机，剩余资源就减1。

Struct process *L意思是，比如2台打印机都有人在用，这时候你的要用打印机，此时会把这个打印机资源的请求放入阻塞队列，L就是阻塞队列的地址。

1
2
3
4
5
6
7
/*P 操作，也就是记录型信号量的请求资源操作*/
void wait (semaphore S) {
    S.value--;
    if (S.value < 0){
        block (S.L);
    }
}

需要注意的是，如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量S的等待队列中。

1
2
3
4
5
6
7
/*V 操作，也就是记录型信号量的释放资源操作*/
void singal (semaphore S) {
    S.value++;
    if (S.value <= 0){
        wakeup (S.L);
    }
}

释放资源后，若还有别的进程在等待这个资源，比如打印机资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为继续态。

2.6.2 生产者消费者问题（了解概念即可）

为什么要讲这个呢，主要是node的流的机制，本质就是生产者消费者问题，可以简单的看看这个问题如何解决。

img

如上图，生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

这里我们需要两个同步信号量和一个互斥信号量

1
2
3
4
5
6
// 互斥信号量，实现对缓冲区的互斥访问
semaphore mutex = 1;
// 同步信号量，表示目前还可以生产几个产品
semaphore empty = n;
// 同步信号量，表示目前可以消耗几个产品
semaphore full = 0;

生产者代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
producer () {
    while(1) {
        // 生产一个产品
        P(empty);
        // 对缓冲区加锁
        P(mutex);
        这里的代码是生产一个产品
        // 解锁
        V(mutex);
        // 产出一个产品
        V(full);
    }
}

消费者代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
producer () {
    while(1) {
        // 消费一个产品
        P(full);
        // 对缓冲区加锁
        P(mutex);
        这里的代码是消费一个产品
        // 解锁
        V(mutex);
        // 消费一个产品
        V(empty);
    }
}

2.7 线程和协程

2.7.1 为什么要引入线程

  • 比如你在玩QQ的时候，QQ是一个进程，如果QQ的进程里没有多线程并发，那么QQ进程就只能同一时间做一件事情（比如QQ打字聊天）
  • 但是我们真实的场景是QQ聊天的同时，还可以发文件，还可以视频聊天，这说明如果QQ没有多线程并发能力，QQ能够的实用性就大大降低了。所以我们需要线程，也就是需要进程拥有能够并发多个事件的能力。

img

引入线程后带来的变化

img

2.7.2 线程的定义

来源百度百科：

线程（thread） 是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

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

下面是线程和进程持有资源的区别

img

线程不像进程那样具有很强的独立性，线程之间会共享数据

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

这里重新理解一下进程

必背考点：什么是线程？

  • CPU调度的基本单位。
  • 更小的能独立运行的基本单位，程序执行的最小单位。
  • 一个进程中可以有多个线程。
    • 内核支持线程KST（Kernel Supported Threads）
      • 在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行。
      • 如果进程中的一个线程被阻塞了，内核可以知晓，并分配处理机给该进程中的其他线程。
      • 线程切换快，开销小。
      • 但是对于用户的线程切换，需要从用户态切换到内核态，开销大。
    • 用户级线程ULT（User Level Threads）
      • 线程的创建、撤销、同步、通信都无需内核的支持，内核甚至完全不知道用户级线程的存在。
      • 用户的线程阻塞了，则会导致整个进程阻塞，因为内核只知道进程，不知道线程，就会认为是这个进程阻塞了。

必背考点：进程和线程的区别

  • 基本单位：进程是资源分配和调度的基本单位，线程是CPU调度的基本单位。
  • 系统开销：进程的切换涉及进程上下文的切换，线程切换的代价远小于进程切换。
  • 拥有资源：线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源（程序计数器PC、一组寄存器和栈）。此外还允许多个线程共享该进程所拥有的资源。而进程拥有比线程更多的资源。
  • 独立性：线程间的独立性比进程间的独立性要低得多，因为线程是提高并发性而合作的，它们共享进程的内存地址空间和资源。而进程一般是独占某块内存。

进程(线程+内存+文件/网络句柄)

在这里插入图片描述

我们通过上面的图片进行进一步理解：

内存：

我们通常所理解的内存是我们所见到的(2G/4G/8G/16G)物理内存,它为什么会在进程之中呢？ 实际上，这里的内存是逻辑内存。指的是内存的寻址空间。每个进程的内存是相互独立的。 否则的话会出现一个问题：我们把指针的值改一改就指向其他进程的内存了，通过这样我们岂不是就可以看到其他进程中”微信”或者是”网上银行”的信息， 这样的话，那我们的微信聊天记录或者是银行账户的信息就都被别人找到了，这是一个很危险的信号！显然这样是不可能的。

文件/网络句柄：

它们是所有的进程所共有的，例如打开同一个文件，去抢同一个网络的端口这样的操作是被允许的。

线程(栈+PC+TLS)

栈:

我们通常都是说调用堆栈，其实这里的堆是没有含义的，调用堆栈就是调用栈的意思。 那么我们的栈里面有什么呢？ 我们从主线程的入口main函数，会不断的进行函数调用， 每次调用的时候，会把所有的参数和返回地址压入到栈中。

PC：

Program Counter 程序计数器，操作系统真正运行的是一个个的线程， 而我们的进程只是它的一个容器。PC就是指向当前的指令，而这个指令是放在内存中。 每个线程都有一串自己的指针，去指向自己当前所在内存的指针。 计算机绝大部分是存储程序性的，说的就是我们的数据和程序是存储在同一片内存里的 这个内存中既有我们的数据变量又有我们的程序。所以我们的PC指针就是指向我们的内存的。

缓冲区溢出

例如我们经常听到一个漏洞：缓冲区溢出 这是什么意思呢？ 例如：我们有个地方要输入用户名，本来是用来存数据的地方。 然后黑客把数据输入的特别长。这个长度超出了我们给数据存储的内存区，这时候跑到了 我们给程序分配的一部分内存中。黑客就可以通过这种办法将他所要运行的代码 写入到用户名框中，来植入进来。我们的解决方法就是，用用户名的长度来限制不要超过 用户名的缓冲区的大小来解决。

TLS:

全称：thread local storage 之前我们看到每个进程都有自己独立的内存，这时候我们想，我们的线程有没有一块独立的内存呢?答案是有的，就是TLS。 可以用来存储我们线程所独有的数据。 可以看到：线程才是我们操作系统所真正去运行的，而进程呢，则是像容器一样他把需要的一些东西放在了一起，而把不需要的东西做了一层隔离，进行隔离开来。

2.7.3 什么是上下文切换

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

2.7.4 使用多线程的好处是什么

多线程是程序员不得不知的基本素养之一，所以，下面我们给出一些多线程编程的好处

  • 能够提高对用户的响应顺序
  • 在流程中的资源共享
  • 比较经济适用
  • 能够对多线程架构有深入的理解

2.7.5 协程是什么

  • 协程是一种比线程更加轻量级的存在，协程处在线程的环境中，一个线程可以存在多个协程，可以将协程理解为线程中的一个个任务。
  • 不像进程和线程，协程并不受操作系统的管理，而是被具体的应用程序代码所控制。
  • 协程属于用户态，协程之间的切换不需要系统调用，
  • 其本质就是控制流主动让出和恢复机制，让控制流更加流畅

2.7.6 线程和协程的区别

  • 调度方式：线程是操作系统调度，协程是应用程序自己调度（用户态）
  • 栈空间：协程的栈空间是可以动态调整的
  • 并发/并行：
    • 协程是协作式多任务，只能并发
    • 线程是抢占式多任务，可以并发也可以并行

2.8 调度算法

2.8.1 调度算法有哪些

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

2.8.2 批处理中的调度

先来先服务(FCFS)

很像是先到先得。。。可能最简单的非抢占式调度算法的设计就是 先来先服务(first-come,first-serverd)。使用此算法，将按照请求顺序为进程分配 CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后。

img

这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。

不过，先来先服务也是有缺点的，那就是没有优先级的关系，试想一下，如果有 100 个 I/O 进程正在排队，第 101 个是一个 CPU 密集型进程，那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。

最短作业(进程)优先（SJF和SPF）

批处理中，第二种调度算法是 最短作业优先(Shortest Job First)，我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法

img

如上图 a 所示，这里有 4 个作业 A、B、C、D ，运行时间分别为 8、4、4、4 分钟。若按图中的次序运行，则 A 的周转时间为 8 分钟，B 为 12 分钟，C 为 16 分钟，D 为 20 分钟，平均时间内为 14 分钟。

现在考虑使用最短作业优先算法运行 4 个作业，如上图 b 所示，目前的周转时间分别为 4、8、12、20，平均为 11 分钟，可以证明最短作业优先是最优的。考虑有 4 个作业的情况，其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束，第二个在时间 a + b 结束，以此类推。平均周转时间为 (4a + 3b + 2c + d) / 4 。显然 a 对平均值的影响最大，所以 a 应该是最短优先作业，其次是 b，然后是 c ，最后是 d 它就只能影响自己的周转时间了。

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

最短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

最短剩余时间优先

最短作业优先的抢占式版本被称作为 最短剩余时间优先(Shortest Remaining Time Next) 算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式能够使短期作业获得良好的服务。

2.8.3 交互式系统中的调度

交互式系统中在个人计算机、服务器和其他系统中都是很常用的，所以有必要来探讨一下交互式调度

轮询调度

一种最古老、最简单、最公平并且最广泛使用的算法就是 轮询算法(round-robin)。每个进程都会被分配一个时间段，称为时间片(quantum)，在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话，则抢占一个 CPU 并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表，就像下图中的 a，当一个进程用完时间片后就被移到队列的末尾，就像下图的 b。

img

优先级调度

事实情况是不是所有的进程都是优先级相等的。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度(priority scheduling)

img

它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。

但是也不意味着高优先级的进程能够永远一直运行下去，调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发生进程切换。或者，可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后，下一个高优先级的进程会得到运行的机会。

最短进程优先

对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，一种方式是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 T0，现在假设测量到其下一次运行时间为 T1，可以用两个值的加权来改进估计时间，即aT0+ (1- 1)T1。通过选择 a 的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当 a = 1/2 时，可以得到下面这个序列

img

可以看到，在三轮过后，T0 在新的估计值中所占比重下降至 1/8。

有时把这种通过当前测量值和先前估计值进行加权平均从而得到下一个估计值的技术称作 老化(aging)。这种方法会使用很多预测值基于当前值的情况。

彩票调度

有一种既可以给出预测结果而又有一种比较简单的实现方式的算法，就是 彩票调度(lottery scheduling)算法。他的基本思想为进程提供各种系统资源的彩票。当做出一个调度决策的时候，就随机抽出一张彩票，拥有彩票的进程将获得资源。比如在 CPU 进行调度时，系统可以每秒持有 50 次抽奖，每个中奖进程会获得额外运行时间的奖励。

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

公平分享调度

如果用户 1 启动了 9 个进程，而用户 2 启动了一个进程，使用轮转或相同优先级调度算法，那么用户 1 将得到 90 % 的 CPU 时间，而用户 2 将之得到 10 % 的 CPU 时间。

为了阻止这种情况的出现，一些系统在调度前会把进程的拥有者考虑在内。在这种模型下，每个用户都会分配一些CPU 时间，而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证，那么无论一个用户有多少个进程，都将获得相同的 CPU 份额。

2.8.4 影响调度程序的指标

会有下面几个因素决定调度程序的好坏

  • CPU 使用率：

CPU 正在执行任务（即不处于空闲状态）的时间百分比。

  • 等待时间

这是进程轮流执行的时间，也就是进程切换的时间

  • 吞吐量

单位时间内完成进程的数量

  • 响应时间

这是从提交流程到获得有用输出所经过的时间。

  • 周转时间

从提交流程到完成流程所经过的时间。

2.8.5 RR 调度算法

RR(round-robin) 调度算法主要针对分时系统，RR 的调度算法会把时间片以相同的部分并循环的分配给每个进程，RR 调度算法没有优先级的概念。这种算法的实现比较简单，而且每个线程都会占有时间片，并不存在线程饥饿的问题

3. 内存管理

3.1 内存的基础知识和概念

为什么需要内存

内存是计算机其它硬件设备与CPU沟通的桥梁、中转站。程序执行前需要先放到内存中才能被CPU处理。

3.1.1 cpu如何区分执行程序的数据在内存的什么地方

  • 是通过给内存的存储单元编址实现的。（存储单元一般是以字节为单位）
  • 如下图，内存的存储单元，就像一个酒店的房间，都有编号，比如程序一的数据都在1楼，1楼1号存储着程序里let a = 1这段代码。

img

3.1.2 内存管理-内存空间的分配与回收

  • 内存分配分为连续分配和非连续分配，连续分配是指用户进程分配的必须是一个连续的内存空间。
  • 这里我们只讲连续分配中的动态分区分配。
  • 什么是动态分区分配呢，这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。（比如，某计算机内存大小64MB，系统区8MB，用户区56MB…，现在我们有几个进程要装入内存，如下图）

img

  • 随之而来的问题就是，如果此时进程1使用完了，相应在内存上的数据也被删除了，那么空闲的区域，后面该怎么分配（也就是说随着进程退出，会有很多空闲的内存区域出现）

我们讲一种较为简单的处理方法叫空闲分区表法来解决这个问题。如下图，右侧的表格就是一个空闲分区表。

img

当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配呢，例如下图，分别有20MB，10MB，4MB三个空闲分区块，现在进程5需要4MB空闲分区，改怎么分配呢？

我们需要按照一定的动态分区分配算法，比如有首次适应算法，指的是每次都从低地址开始查找，找到第一个能满足大小的空闲分区。还有比如最佳适应算法，指的是从空闲分区表中找到最小的适合分配的分区块来满足需求。

img

连续分配缺点很明显，大多数情况，需要分配的进程大小，不能跟空闲分区剩下的大小完全一样，这样就产生很多很难利用的内存碎片。

这里我们介绍一种更好的空闲分区的分配方法，基本分页存储。如下图

img

将内存空间分为一个个大小相等的分区（比如：每个分区4KB）.每个分区就是一个“页框”。页框号从0开始。

将用户进程的地址空间分为与页框大小相等的一个个区域，称为“页”。每个页也是从0开始。

进程的页与内存的页框有着一一对应的关系。各个页不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

3.2 虚拟内存

3.2.1 什么是虚拟内存

虚拟内存是一种内存分配方案，是一项可以用来辅助内存分配的机制。我们知道，应用程序是按页装载进内存中的。但并不是所有的页都会装载到内存中，计算机中的硬件和软件会将数据从 RAM 临时传输到磁盘中来弥补内存的不足。如果没有虚拟内存的话，一旦你将计算机内存填满后，计算机会对你说，对不起，您无法再加载任何应用程序，请关闭另一个应用程序以加载新的应用程序。对于虚拟内存，计算机可以执行操作是查看内存中最近未使用过的区域，然后将其复制到硬盘上。复制是自动进行的，你无法感知到它的存在。

3.2.2 虚拟内存的实现方式

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

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

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

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

3.2.3 按需分页

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

3.3 内存管理

3.3.1 分析内存为什么要分段

内存是随机访问设备，对于内存来说，不需要从头开始查找，只需要直接给出地址即可。内存的分段是从 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 的寻址能力。所以内存分段的第二个目的就是能够访问到所有内存。

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

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

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

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

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

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

img

3.3.3 空闲内存管理的方式

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

使用位图进行管理

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

img

图 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)是按照地址排序的。这种方式的优点是，当进程终止或被交换时，更新列表很简单。一个终止进程通常有两个邻居（除了内存的顶部和底部外）。相邻的可能是进程也可能是空闲区，它们有四种组合方式。

img

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

  • 首次适配算法：在链表中进行搜索，直到找到最初的一个足够大的空闲区，将其分配。除非进程大小和空间区大小恰好相同，否则会将空闲区分为两部分，一部分为进程使用，一部分成为新的空闲区。该方法是速度很快的算法，因为索引链表结点的个数较少。
  • 下次适配算法：工作方式与首次适配算法相同，但每次找到新的空闲区位置后都记录当前位置，下次寻找空闲区从上次结束的地方开始搜索，而不是与首次适配放一样从头开始；
  • 最佳适配算法：搜索整个链表，找出能够容纳进程分配的最小的空闲区。这样存在的问题是，尽管可以保证为进程找到一个最为合适的空闲区进行分配，但大多数情况下，这样的空闲区被分为两部分，一部分用于进程分配，一部分会生成很小的空闲区，而这样的空闲区很难再被进行利用。
  • 最差适配算法：与最佳适配算法相反，每次分配搜索最大的空闲区进行分配，从而可以使得空闲区拆分得到的新的空闲区可以更好的被进行利用。

3.3.4 分页和分段式的存储管理方式

分页式

  • 页内碎片：内零头
  • 页（逻辑）
  • 块（物理）
  • 页表：系统为每个进程建立的一张页面映射表，页->块（页号->块号）
  • 快表：高速缓冲寄存器，存放最近访问的页号/块号映射对。
  • 寻址（逻辑地址 -> 物理地址）
  • 两级/多级页表

image

image

分段式

  • 在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。
  • 每个段都有自己的名字。
  • 每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。
  • 段表：段号，该段在内存中的起始地址（基址），段的长度。

image

分段和分页的区别

外零头：可变分区时，可能会形成大量较小的，难以再分配的分区。动态划分没有内零头，静态划分有内零头

分页 分段
信息的物理单位，减少外零头，提高内存利用率。 段是信息的逻辑单位，方便用户。
大小固定，由系统决定 长度不固定，取决于用户所编写的程序。
作业地址空间是一维的，因为页是连续的，逻辑地址空间是一维的，一张页表走到底就行了。（直接根据逻辑地址可以算出页号和页内地址，取余和除法取整） 作业地址空间是二维的，数据段、代码段、堆栈段等段号连续，但物理地址空间不连续。（二维：哪个段+段内地址）
减少了外零头，但不能避免内零头 内零头不清楚，但是因为物理地址空间不连续，可能会产生一些外零头

段页式的存储管理方式

先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。（先分段，段内再分页）

image

段号->段表->页表地址-> + 页号->块号-> +页内地址 => 物理地址

3.4 页面置换算法

在地址映射过程中，如果在页面中发现所要访问的页面不在内存中，那么就会产生一条缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，那么操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

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

img

3.4.1 最佳置换算法(OPT，Optlmal)

最佳置换算法又称作最优算法，在当前页面中置换最后要访问的页面。是所选择被淘汰的页面，将是以后永不使用的，或许是在最长时间内不再被访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，理想化，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。

3.4.2最近未使用算法(NRU)

NRU 算法根据 R 位和 M 位的状态将页面分为四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好。存在更好的算法。

3.4.3 先进先出置换算法（FIFO，First In First Out）

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰 。跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面

页面调入的先后并不能反映页面的使用情况。所以这个效率差。

第二次机会算法是对 FIFO 的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进大大提高了性能。

3.4.4 最近最久未使用置换算法（LRU，Least Recently Used）

  • 选择最近最久未使用的页面予以淘汰。
  • 硬件支持：寄存器 和 栈

LRU 算法是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法。

  • NFU 算法是一种近似于 LRU 的算法，它的性能不是非常好。
  • 老化 算法是一种更接近 LRU 算法的实现，并且可以更好的实现，因此是一个很好的选择。使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。

3.4.5 最不经常使用算法（Least Frequently Used，LFU）

使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。

3.4.6 时钟置换算法（Clock）：

  • 每页设置一个访问位，该页第一次装入内存或者被重新访问到时，置 = 1
  • 置换时，检查每一页：
    • 若 = 1，则置 = 0；
    • 若 = 0，则换出。
  • 其实就是多给被访问过的页面一次机会。

时钟 算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法。

3.4.7 改进的时钟置换算法（Clock）：

  • 除了访问位，还要考虑是否被修改过：

    • 访问过，修改过：别搞我
    • 访问过，未修改：最好也别搞我
    • 未访问，但修改过：也还是别搞我
    • 未访问，也未修改：搞我搞我

  • 扫描：

    • 先扫描第一遍：找第四种，
    • 没有的话扫描第二遍，访问位置0，寻找未访问，但修改过的。
    • 没有的话第三遍，这个时候一定能成功

    是时钟置换算法的一种变体，它不仅能够提供良好的性能，而且可以高效地实现。

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

4.文件系统

4.1 文件的定义和属性

文件就是一组有意义的信息/数据集合。

计算机中存放了各种各样的文件，文件的属性包括：

img

  • 文件名。即文件的名字，需要注意的是，同一目录下不允许有重名的文件。
  • 标识符。操作系统用于区分各个文件的一种内部的名称。
  • 类型。文件的类型。
  • 位置。文件存放的路径，同时也是在硬盘里的位置（需要转换成物理硬盘上的地址）
  • 创建时间、上次修改时间、文件所有者就是字面意思。
  • 保护信息。比如对这个文件的执行权限，是否有删除文件权限，修改文件权限等等。

4.2 文件的组织方式

文件内部的数据应该怎样组织起来？文件之间又该怎么组织起来？

4.2.1 文件内部数据如何组织在一起

如下图，文件主要分为有结构文件和无结构文件。

img

4.2.2 文件之间如何组织起来

通过树状结构组织的。例如windows的文件间的组织关系如下：

img

接下来我们详细的了解一下文件的逻辑结构

4.2.3 文件的逻辑结构

逻辑结构是指，在用户看来，文件内部的数据是如何组织起来的，而“物理结构”是在操作系统看来，文件是如何保存在外存，比如硬盘中的。

img

比如，“线性表”就是一种逻辑结构，在用户看来，线性表就是一组有先后关系的元素序列，如：a,b,c,d,e....

  • “线性表”这种逻辑结构可以用不同的物理结构实现，比如：顺序表/链表。顺序表的各个元素在逻辑上相邻，在物理上也相邻：而链表的各个元素在物理上可以是不相邻的。
  • 因此，顺序表可以实现“随机访问”，而“链表”无法实现随机访问。

接下来我了解一下有结构文件的三种逻辑结构

4.2.3.1 顺序文件

什么是顺序文件

指的是文件中的记录一个接一个地在逻辑上是顺序排列，记录可以是定长或变长，各个记录在物理上可以顺序存储或链式存储

img

  • 顺序文件按结构来划分，可以分为串结构和顺序结构。
  • 串结构是指记录之间的顺序与关键字无关，通常都是按照记录的时间决定记录的顺序。
  • 顺序结构就必须保证记录之间的先后顺序按关键字排列。

这里需要注意的知识点是，顺序文件的存储方式和是否按关键字排列，会影响数据是否支持随机存取和是否可以快速按关键字找到对应记录的功能。

img

4.2.3.2 索引文件

对于可变长记录文件，要找到第i个记录，必须先顺序查找前i-1个记录，但是很多场景中又必须使用可变长记录，如何解决这个问题呢？这就引出来马上讲的索引文件

img

  • 给这些变长的记录都用一张索引表来记录，一个索引表项包括了索引号，长度和指针。
  • 其中，可以将关键字作为索引号的内容，如果关键字本身的排列是有序的，那么还可以按照关键字进行折半查找。
  • 但是建立索引表的问题也很明显，首先若要删除/增加一个记录，同时也要对索引表操作，其次，如果增加一条记录才1KB，但是索引表增加i一条记录可能有8KB，以至于索引表的体积大大多于记录。存储空间的利用率就比较低。

4.2.3.3 索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是，并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

img

4.2.4 文件目录

首先，我们需要了解一下文件控制块是什么。我们假设目前在windows的D盘，如下图

img

可以看到，目录本身就是一种有结构的文件，记录了目录里的文件和目录的信息，比如名称和类型。而这些一条条的记录就是一个个的“文件控制块”（FCB）。

文件目录的结构通常是树状的，例如linux里/是指根路径，/home是根路径下的二级目录

img

  • 需要注意的是，树状目录不容易实现文件共享，所以在树形目录结构的基础上，增加了一些指向同一节点的有向边（可以简单理解为引用关系，就跟js里的对象一样）
  • 也就是说需要为每个共享节点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。只有共享计数器减为0，才删除该节点。

4.2.5 文件存储空间管理

首先，我们了解一下磁盘分为目录区和文件区。

img

接着，我们了解一下常见的两种文件存储空间的管理算法，如下图，假如硬盘上空闲的数据块是蓝色，非空闲的数据块是橙色。

img

对分配连续的存储空间，可以采用空闲表法（只讲这种较简单的方法）来分配和回收磁盘块。对于分配，可以采用首次适应，最佳适应等算法来决定要为文件分配哪个区间。（空闲表表示如下）

img

  • 首次适应是指当要插入数据的时候，空闲表会依次检查空闲表中的表项，然后找到第一个满足条件的空闲区间。
  • 最佳适应算法是指当要插入数据的时候，空闲表会依次检查空闲表中的表项，然后找到满足条件而且空闲块最小的空闲区间。

如何回收磁盘块呢，主要分为以下4中情况

  • 回收区的前后没有相邻空闲区
  • 回收区前后都是空闲区
  • 回收区前面是空前去
  • 回收区后面是空闲区

最重要的是要注意表项合并的问题。(比如说回收区前后都有空闲区就将其一起合并为一个空闲区)

4.3 文件共享

文件共享分为两种

img

  • 注意，多个用户共享同一个文件，意味着系统只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件的变化。
  • 软连接可以理解为windows里的快捷方式。
  • 硬链接可以理解为js里的引用计数，只有引用为0的时候，才会真正删除这个文件。

4.4 文件保护

操作系统需要保护文件的安全，一般有如下3种方式：

  • 口令保护。是指为文件设置一个“口令”（比如123），用户请求访问该文件时必须提供对应的口令。口令一般放在文件对应的FCB或者索引结点上。
  • 加密保护。使用某个"密码"对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
  • 访问控制。在每个文件的FCB或者索引节点种增加一个访问控制列表，该表中记录了各个用户可以对该文件执行哪些操作。

img

4.5 提高文件系统性能的方式

访问磁盘的效率要比内存慢很多，是时候又祭出这张图了

img

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

4.5.1 高速缓存

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

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

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

img

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

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

4.5.2 块提前读

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

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

4.5.3 减少磁盘臂运动

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

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

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

img

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

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

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

4.5.4 磁盘碎片整理

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

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

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

4.6 磁盘臂调度算法

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

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

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

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

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

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

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

img

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

img

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

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

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

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

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

img

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

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

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

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

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

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

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

4.7 RAID 的不同级别

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

RAID 有不同的级别

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

5. IO设备

5.1 I/O设备的定义与分类

5.1.1 I/O设备定义

I/O就是输入输出(Input/Output)的意思，I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

img

5.1.2 I/O设备分类——按使用特性

  • 人机交互类设备，这类设备传输数据的速度慢

img

  • 存储设备，这类设备传输数据的速度较快

img

  • 网络通信设备，这类设备的传输速度介于人机交互设备和存储设备之间

5.1.3 设备驱动程序

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

5.1.4 五种I/O模型

image

5.2 I/O控制

5.2.1 I/O控制器

CPU无法直接控制I/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的“中介”，用于实现CPU对设备的控制。这个电子部件就是I/O控制器。I/O控制器是一个可编址的设备，当它仅控制一个设备时，它只有一个唯一的设备地址；如果I/O控制器控制多个可连接设备时，则应含有多个设备地址，并使每一个设备地址对应一个设备。

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

img

  • 接收和识别CPU发出的指令：设备控制器可以接受来自 CPU 的指令，并进行识别。设备控制器内部也会有寄存器，用来存放指令和参数
  • 向cpu报告设备的状态是指，I/O控制器会有相应的状态寄存器，用来记录I/O设备是否空闲或者忙碌
  • 数据交换：CPU、控制器和设备之间会进行数据的交换，CPU 通过总线把指令发送给控制器，或从控制器中并行地读出数据；控制器将数据写入指定设备。
  • 地址识别：为了区分I/O控制器中的各个寄存器中的各个寄存器，也需要给各个寄存器设置一个特性的“地址”，为使 CPU 能向寄存器中写入或者读取数据，这些寄存器地址唯一。I/O控制器通过CPU提供的“地址”来判断CPU要读写的是哪个寄存器
  • 差错检测：I/O控制器还具有对设备传递过来的数据进行检测的功能。

5.2.2 I/O控制方式

  • 这里我们指讲一下目前比较先进的方式，通道控制方式。

  • 通道可以理解为一种“弱鸡版CPU”。通道可以识别并执行一系列通道指令。

img
通道最大的优点是极大的减少了CPU的干预频率，I/O设备完成任务，通道会向CPU发出中断，不需要轮询来问I/O设备是否完成CPU下达的任务。

5.3 操作系统中的时钟

时钟(Clocks) 也被称为定时器(timers)，时钟/定时器对任何程序系统来说都是必不可少的。时钟负责维护时间、防止一个进程长期占用 CPU 时间等其他功能。时钟软件(clock software) 也是一种设备驱动的方式。下面我们就来对时钟进行介绍，一般都是先讨论硬件再介绍软件，采用由下到上的方式，也是告诉你，底层是最重要的。

5.3.1 时钟硬件

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

  • 比较简单的一种时钟被连接到 110 V 或 220 V 的电源线上，这样每个电压周期会产生一个中断，大概是 50 - 60 HZ。这些时钟过去一直占据支配地位。
  • 另外的一种时钟由晶体振荡器、计数器和寄存器组成，示意图如下所示

img

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

5.4 操作系统的中断处理过程

中断处理方案有很多种，下面是 《ARM System Developer’s Guide Designing and Optimizing System Software》列出来的一些方案

  • 非嵌套的中断处理程序按照顺序处理各个中断，非嵌套的中断处理程序也是最简单的中断处理
  • 嵌套的中断处理程序会处理多个中断而无需分配优先级
  • 可重入的中断处理程序可使用优先级处理多个中断
  • 简单优先级中断处理程序可处理简单的中断
  • 标准优先级中断处理程序比低优先级的中断处理程序在更短的时间能够处理优先级更高的中断
  • 高优先级 中断处理程序在短时间能够处理优先级更高的任务，并直接进入特定的服务例程。
  • 优先级分组中断处理程序能够处理不同优先级的中断任务

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

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

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

img

5.5 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 要求。

6. 死锁

6.1 产生死锁的原因

死锁产生的原因大致有两个：资源竞争和程序执行顺序不当

必背考点：死锁产生的原因

  • 死锁：进程间因为竞争资源而导致的一种僵持状态。
  • 竞争资源（不可抢占性资源、可消耗性资源）
  • 进程间推进顺序非法。（进程在运行过程中，请求和释放资源的顺序不当）

6.2 死锁的原因

死锁产生的原因大致有两个：资源竞争和程序执行顺序不当

资源死锁可能出现的情况主要有

  • 互斥条件：每个资源都被分配给了一个进程或者资源是可用的
  • 保持和等待条件：已经获取资源的进程被认为能够获取新的资源
  • 不可抢占条件：分配给一个进程的资源不能强制的从其他进程抢占资源，它只能由占有它的进程显示释放
  • 循环等待：死锁发生时，系统中一定有两个或者两个以上的进程组成一个循环，循环中的每个进程都在等待下一个进程释放的资源。

必背考点：死锁产生的必要条件

  • 互斥：进程对所分配的资源排他性使用
  • 请求和保持：进程有一/多个资源了，还在请求新的资源
  • 不可抢占：进程所分配的资源，用完之前不能被剥夺，只能在用完的时候进程自己释放。
  • 循环等待：发生死锁的时候，必然存在一个进程与资源的环形链

6.3 死锁的恢复方式

所以针对检测出来的死锁，我们要对其进行恢复，下面我们会探讨几种死锁的恢复方式

6.3.1 通过抢占进行恢复

在某些情况下，可能会临时将某个资源从它的持有者转移到另一个进程。比如在不通知原进程的情况下，将某个资源从进程中强制取走给其他进程使用，使用完后又送回。这种恢复方式一般比较困难而且有些简单粗暴，并不可取。

6.3.2 通过回滚进行恢复

如果系统设计者和机器操作员知道有可能发生死锁，那么就可以定期检查流程。进程的检测点意味着进程的状态可以被写入到文件以便后面进行恢复。检测点不仅包含存储映像(memory image)，还包含资源状态(resource state)。一种更有效的解决方式是不要覆盖原有的检测点，而是每出现一个检测点都要把它写入到文件中，这样当进程执行时，就会有一系列的检查点文件被累积起来。

为了进行恢复，要从上一个较早的检查点上开始，这样所需要资源的进程会回滚到上一个时间点，在这个时间点上，死锁进程还没有获取所需要的资源，可以在此时对其进行资源分配。

6.3.3 杀死进程恢复

最简单有效的解决方案是直接杀死一个死锁进程。但是杀死一个进程可能照样行不通，这时候就需要杀死别的资源进行恢复。

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

6.4 如何破坏死锁

和死锁产生的必要条件一样，如果要破坏死锁，也是从下面四种方式进行破坏。

6.4.1 破坏互斥条件

我们首先考虑的就是破坏互斥使用条件。如果资源不被一个进程独占，那么死锁肯定不会产生。如果两个打印机同时使用一个资源会造成混乱，打印机的解决方式是使用 假脱机打印机(spooling printer) ，这项技术可以允许多个进程同时产生输出，在这种模型中，实际请求打印机的唯一进程是打印机守护进程，也称为后台进程。后台进程不会请求其他资源。我们可以消除打印机的死锁。

后台进程通常被编写为能够输出完整的文件后才能打印，假如两个进程都占用了假脱机空间的一半，而这两个进程都没有完成全部的输出，就会导致死锁。

因此，尽量做到尽可能少的进程可以请求资源。

6.4.2 破坏保持等待的条件

第二种方式是如果我们能阻止持有资源的进程请求其他资源，我们就能够消除死锁。一种实现方式是让所有的进程开始执行前请求全部的资源。如果所需的资源可用，进程会完成资源的分配并运行到结束。如果有任何一个资源处于频繁分配的情况，那么没有分配到资源的进程就会等待。

很多进程无法在执行完成前就知道到底需要多少资源，如果知道的话，就可以使用银行家算法；还有一个问题是这样无法合理有效利用资源。

还有一种方式是进程在请求其他资源时，先释放所占用的资源，然后再尝试一次获取全部的资源。

6.4.3 破坏不可抢占条件

破坏不可抢占条件也是可以的。可以通过虚拟化的方式来避免这种情况。

6.4.4 破坏循环等待条件

现在就剩最后一个条件了，循环等待条件可以通过多种方法来破坏。一种方式是制定一个标准，一个进程在任何时候只能使用一种资源。如果需要另外一种资源，必须释放当前资源。

另一种方式是将所有的资源统一编号，如下图所示

img

进程可以在任何时间提出请求，但是所有的请求都必须按照资源的顺序提出。如果按照此分配规则的话，那么资源分配之间不会出现环。

img

必背考点 预防死锁

  • “互斥”：必不可少，无法打破。

  • “请求和保持”：一次性分配所有所需的资源

    • （或者 需要什么就请求什么，不再需要什么就释放什么）
    • 简单、易实现、安全
    • 资源被浪费、进程延迟运行

  • “不可抢占”：进程已经获得一些资源的时候，如果请求新的资源失败，则放弃当前已经拥有的资源

    • 实现复杂、代价大，可能前功尽弃、进程前后两次运行的信息不连续

  • “循环等待”：系统将资源按类型先行排序，并且赋予不同的序号。进程对资源的请求必须严格按照资源的序号递增的次序提出，这样就不会出现环路。

    • 进程使用资源的顺序，可能与系统规定的顺序不同，造成资源的浪费。

  • 序号稳定之后，限制了新设备的增加

6.5 孤儿进程和僵尸进程

6.5.1 父进程与子进程

在学习接下来的内容之前，需要对父进程和子进程有一个清晰的认识

在Linux里，除了进程0（即PID=0的进程）以外的所有进程都是由其他进程使用系统调用fork创建的，这里调用fork创建新进程的进程即为父进程，而相对应的为其创建出的进程则为子进程，因而除了进程0以外的进程都只有一个父进程，但一个进程可以有多个子进程。

fork函数包含在unistd.h库中，其最主要的特点是，调用一次，返回两次，当父进程fork()创建子进程失败时，fork()返回-1，当父进程fork()创建子进程成功时，此时，父进程会返回子进程的pid，而子进程返回的是0。所以可以根据返回值的不同让父进程和子进程执行不同的代码

img

如上图所示，当fork()函数调用后，父进程中的变量pid赋值成子进程的pid(pid>0)，所以父进程会执行else里的代码，打印出”This is the parent”，而子进程的变量pid赋值成0，所以子进程执行if(pid == 0)里的代码，打印出”This is the child”

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

知道了这些，我们再来了解两种特殊的进程

6.5.2 僵尸进程

僵尸进程是已完成且处于终止状态，但在进程表中却仍然存在的进程。僵尸进程通常发生在父子关系的进程中，由于父进程仍需要读取其子进程的退出状态所造成的。

当一个子进程结束运行（一般是调用exit、运行时发生致命错误或收到终止信号所导致）时，子进程的退出状态（返回值）会回报给操作系统，系统则以SIGCHLD信号将子进程被结束的事件告知父进程，此时子进程的进程控制块（PCB）仍驻留在内存中。一般来说，收到SIGCHLD后，父进程会使用wait系统调用以获取子进程的退出状态，然后内核就可以从内存中释放已结束的子进程的PCB；而如若父进程没有这么做的话，子进程的PCB就会一直驻留在内存中，也即成为僵尸进程

简单来说，当进程退出但是父进程并没有调用wait或waitpid获取子进程的状态信息时就会产生僵尸进程

上文中提到的进程的僵死状态Z(zombie)就是僵尸进程对应的状态

我们可以写一个程序来查看一下僵尸进程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>

int main(){
  printf("pid = %d\n",getpid());
  pid_t pid = fork();
  if(pid < 0){
    printf("fork error\n");
    return -1;
  }else if(pid == 0){
    //这段代码只有子进程能够运行到，因为在子进程中fork的返回值为0
    printf("This is the child!pid = %d\n",getpid());
    sleep(5);
    exit(0); //退出进程
  }else if(pid > 0){
    //这段代码只有父进程能运行到
    printf("This is the parent!pid = %d\n",getpid());
  }
  //当fork成功时下面的代码父子进程都会运行到
  while(1){
    printf("-------------pid = %d\n",getpid());
    sleep(1);
  }
  return 0;
}

程序的运行结果：

1
2
3
4
5
6
7
8
ubuntu@VM-0-7-ubuntu:~/c_practice$ ./zombie 
pid = 24816
This is the parent!pid = 24816
-------------pid = 24816
This is the child!pid = 24817
-------------pid = 24816
-------------pid = 24816
.....

在程序开始运行时立即查看进程：

(这里我分别运行了两次，分别使用ps -ef和ps -aux查看了进程状态，所以两次的进程PID是不同的)

1
2
3
4
5
6
7
ubuntu@VM-0-7-ubuntu:~$ ps -ef | grep -v grep | grep zombie
ubuntu   23797 15818  0 14:53 pts/0    00:00:00 ./zombie
ubuntu   23798 23797  0 14:53 pts/0    00:00:00 ./zombie

ubuntu@VM-0-7-ubuntu:~$ ps -aux | grep -v grep | grep zombie
ubuntu   24288  0.0  0.0   4352   648 pts/0    S+   14:56   0:00 ./zombie
ubuntu   24289  0.0  0.0   4352    80 pts/0    S+   14:56   0:00 ./zombie

在进程运行五秒后再次查看进程：

1
2
3
4
5
6
7
ubuntu@VM-0-7-ubuntu:~$ ps -ef | grep -v grep | grep zombie
ubuntu   23797 15818  0 14:53 pts/0    00:00:00 ./zombie
ubuntu   23798 23797  0 14:53 pts/0    00:00:00 [zombie] <defunct>

ubuntu@VM-0-7-ubuntu:~$ ps -aux | grep -v grep | grep zombie
ubuntu   24288  0.0  0.0   4352   648 pts/0    S+   14:56   0:00 ./zombie
ubuntu   24289  0.0  0.0      0     0 pts/0    Z+   14:56   0:00 [zombie] <defunct>

可以看出当进程运行五秒后，子进程状态变成Z，就是僵死状态，子进程就成了僵尸进程

其实，僵尸进程是有危害的。进程的退出状态必须被维持下去，因为它要告诉关心它的进程（父进程），你交给我的任务，我办的怎么样了。可父进程如果一直不读取，那子进程就一直处于Z状态。维护退出状态本身就是要用数据维护，也属于进程基本信息，所以保存在task_struct(PCB)中，换句话说，当一个进程一直处于Z状态，那么它的PCB也就一直都要被维护。因为PCB本身就是一个结构体会占用空间，僵尸进程也就会造成资源浪费，所以我们应该避免僵尸进程的产生

6.5.3 孤儿进程

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

来段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<errno.h>

int main(){ 
  pid_t pid;
  pid = fork();
  if(pid < 0){  
    perror("fork error");
    exit(1);
  }
  if(pid == 0){ 
    printf("This is the child!\n");
    printf("pid = %d,ppid = %d\n",getpid(),getppid());//父进程退出前的pid和ppid
    sleep(5);
    printf("\npid = %d,ppid = %d\n",getpid(),getppid());//父进程退出后的pid和ppid
  }else{  
    printf("This is the father!\n");
    sleep(1);
    printf("father process is exited!\n");
  }
  return 0;
}

运行结果：

1
2
3
4
5
6
7
ubuntu@VM-0-7-ubuntu:~/c_practice$ ./orphan 
This is the father!
This is the child!
pid = 2338,ppid = 2337
father process is exited!
ubuntu@VM-0-7-ubuntu:~/c_practice$ 
pid = 2338,ppid = 1

我们可以看到结果和我们预见的是一样的，孤儿进程在父进程退出后会被init进程领养，直到自己运行结束为止。这个程序很容易理解,先输出子进程的pid和父进程的pid，再然后子进程开始睡眠父进程退出，这时候子进程变成孤儿进程，再次输出时，该进程的父进程变为init

孤儿进程由于有init进程循环的wait()回收资源，因此并没有什么危害。

6.6 死锁类型

6.6.1 两阶段加锁

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

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

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

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

6.6.2 通信死锁

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

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

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

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

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

img

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

6.6.3 活锁

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

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

6.6.4 饥饿

与死锁和活锁的一个非常相似的问题是 饥饿(starvvation)。想象一下你什么时候会饿？一段时间不吃东西是不是会饿？对于进程来讲，最重要的就是资源，如果一段时间没有获得资源，那么进程会产生饥饿，这些进程会永远得不到服务。

我们假设打印机的分配方案是每次都会分配给最小文件的进程，那么要打印大文件的进程会永远得不到服务，导致进程饥饿，进程会无限制的推后，虽然它没有阻塞。

7. Linux常用命令

7.1 Linux系统

  • pwd 打印当前工作目录
  • cd 改变目录
1
2
3
4
5
cd /usr/bin  绝对路径从根目录出发，到达目标目录
cd ./usr 相对路径从工作目录出发，到达目标目录
cd .. 到达父目录
cd(cd ~) 到达家目录，如果未root用户，pwd会打印出 /root，其上一层为 根目录/
cd / (cd -) 回到根目录
  • ls 列出目录内容
1
2
3
4
5
6
ls -l 使用长格式显示结果
ls -t 按修改时间排序
ls -r 以相反的顺序显示
ls -S 按文件大小对结果进行排序
ls -R [文件夹] 列出文件树
......
  • file 确定文件类型
1
file filename
  • less 查看文件内容
1
less /etc/passwd
  • touch 新建文件

7.2 操作文件与目录

  • mkdir 创建目录
1
2
3
4
mkdir dir1              创建单个目录
mkdir dir1 dir2 dir3    创建多个目录
mkdir -p dir{1..9}      创建多个目录a1到a9
mkdir -p a{1..3}/b{1..3}创建多个目录a1到a3，并且在每个目录下创建b1到b3
  • cp 复制文件或目录
1
2
3
cp file1 file2          将文件file1复制到file2中,file2内容将会被覆盖
cp -r dir1 dir2         复制目录时一定要加 -r，如果dir2目录存在，则会复制到dir2目录下和mv是一样的道理
cp file1 file2 dir1     将多个文件复制到一个目录下

cp命令选项

cp在覆盖已存在的文件时默认情况下是 cp -i，即需要用户确认，我们可以这样 \cp 即可无需确认

1
2
3
4
-i          在覆盖一个已存在的文件前，提示用户进行确认。
-r          递归复制目录及其内容。复制目录时需要这个选项
-u          将文件从一个目录复制到另一个目录时，只会复制目标目录不存在的文件或是目标目录相应文件的更新文件
-v          复制文件时显示信息性消息
  • mv 重命名或移动文件和目录
1
2
mv item1 item2              将文件或目录item1移动或重命名为item2
mv item1 item2 item3 dir1   将多个条目移动到dir1目录下

mv命令选项与cp大致相同，mv没有-r选项

1
2
3
-i          在覆盖一个已存在的文件前，提示用户进行确认。
-u          将文件从一个目录移动到另一个目录时，只会移动目标目录不存在的文件或是目标目录相应文件的更新文件
-v          移动时显示信息性消息
  • rm 删除文件或目录
1
2
rm -r item1 item2 item3         删除item1,item2,item3,删除目录时需要-r
rm *.html                       删除以.html结尾的文件

rm命令选项

1
2
3
4
-i          删除前提示用户确认
-r          递归删除目录及其内容。删除目录时需要这个选项
-f          忽略不存在的文件，并无需提示确认
-v          删除时显示信息性消息
  • ln 创建硬链接和符号链接
1
2
ln file hard-link-name      创建file文件的硬链接
ln -s file sym-link-name    创建file文件的符号链接，符号链接指向源文件，与源文件内容保持一致

file为相对于sym-link-name的文件，即为相对路径，当然也可以是绝对路径

1
ln -s ../file sym-link-name     file在当前目录的父目录中，即file相对于sym-link-name的位置

7.3 读写文件

1.grep 搜索文本 文件名 搜索文本内容
-n 显示行号； -v 不包括该内容的 ； ^a查找以a开头的行； a$ 查找以a结尾的行

2.cat 显示文件完整内容

3.more 分屏显示文件内容

4.less 分屏显示文件内容，上下键控制翻页

5.head 打印文件中的前n行

6.tail 打印文件中的末尾几行
显示10~15行内容 tail 文件名 +10| head +5

7.find
find 目录 -name 搜索字符 搜索名字为xxx的文件 可以使用通配符
find 目录 -size 数据块 搜索大小为xxx的文件，1数据块=0.5kB
+n 大于 -n 小于 n等于
组合条件：-o 或者；-a 并且
find \ -size +163840 -a -size -204800 查找根目录下大于80MB小于100MB的文件
find 目录 -group xxx 查询所属组为xxx的文件
find 目录 -user xxx 查询所属者为xxx的文件

8.wc
wc 文件 -l 统计文件的行数
wc 文件 -w 统计文件的单词数
wc 文件 -c 统计文件的字节数

例子

1
2
3
4
5
6
7
echo "I am fine"                        打印 I am fine
echo "I am fine" > /root/test.txt       将 I am fine写入/root/test.txt中
echo "I am fine" >> /root/test.txt      将 I am fine追加到/root/test.txt末尾
grep "关键字" test.txt                  在test.txt中查找含有关键字的行并打印
grep -v "关键字" test.txt               在test.txt中查找不含有关键字的行并打印
grep ^"关键字" test.txt                 在test.txt中查找以关键字开头的行并打印
grep $"关键字" test.txt                 在test.txt中查找以关键字结尾的行并打印

7.4 管道

1
ls -l | grep "关键字" > /root/test.txt  列出当前目录文件信息并交给grep过滤，最后写入/root/test.txt

7.5 进程与内存相关

1.top 动态实时显示cpu、内存、进程使用情况

2.ps 列出进程

1
2
3
4
ps -ef | grep xxx 查看xx进程，可以获得pid
ps -a 列出所有运行中的进程
pgrep -l xxx 查看xx进程的pid
netstat -atnp| grep xxx 查询pid

3.kill 杀死进程

1
kill -9 pid 强制杀死某进程

4.netstat

1
2
3
netstat -atnp | grep xxxx 查看端口号/状态的进程pid
查看端口占用情况 lsof -i
查看指定端口占用情况 lsof -i:端口号

5.free 显示当前内存使用情况

6.df 以字节形式显示磁盘使用情况

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道