操作系统

用户态和内核态

为什么需要区分

最简单的运行程序的方式是“直接执行”，即直接在 CPU 上执行任意程序。直接执行的问题是：

1. 如何限制代码行为？比如禁止：设置特殊寄存器的值、访问存储器的任意位置、I/O 请求、申请更多系统资源等
2. 在运行这个程序的时候，如何切换到另一个程序？进程调度应该是 OS 才有的权限

因此引入用户态和内核态和两种模式。用户态无法执行受限操作，如 I/O 请求，执行这些操作会引发异常。内核态只能由操作系统运行，可以执行特权操作。用户程序通过系统调用 system call 执行这些特权操作。OS 执行前会判断进程是否有权限执行相应的指令。

区分用户态和内核态的执行机制称为“受限直接执行”（Limited Direct Execution）。

陷入内核态的时机

系统调用（trap）、中断（interrupt）和异常（exception）。

系统调用是用户进程主动发起的操作。发起系统调用，陷入内核，由操作系统执行系统调用，然后再返回到进程。

中断和异常是被动的，无法预测发生时机。中断包括 I/O 中断、外部信号中断、各种定时器引起的时钟中断等。异常包括程序运算引起的各种错误如除 0、缓冲区溢出、缺页等。

陷阱、中断、异常、信号

陷阱

陷阱是有意造成的“异常”，是执行一条指令的结果。陷阱是同步的。

陷阱的主要作用是实现系统调用。比如，进程可以执行 syscall n 指令向内核请求服务。当进程执行这条指令后，会中断当前的控制流，陷入到内核态，执行相应的系统调用。内核的处理程序在执行结束后，会将结果返回给进程，同时退回到用户态。进程此时继续执行下一条指令。

中断

中断由处理器外部的硬件产生，不是执行某条指令的结果，也无法预测发生时机。由于中断独立于当前执行的程序，因此中断是异步事件。

中断包括 I/O 设备发出的 I/O 中断、各种定时器引起的时钟中断、调试程序中设置的断点等引起的调试中断等。

每个中断都有一个中断号。操作系统使用中断描述符表（Interrupt Descriptor Table，IDT）来保存每个中断的中断处理程序的地址。当发生中断时，操作系统会根据中断号，在中断描述表中查找并执行相应的中断处理程序。当处理程序返回后，进程继续执行下一条指令，就好像没有发生过中断一样。

异常

异常是一种错误情况，是执行当前指令的结果，可能被错误处理程序修正，也可能直接终止应用程序。异常是同步的。

注意这里的“异常”和上文一开始说的“异常”的区别。上文的“异常”是一个通用的术语，表示因为某些事件/操作而引起的控制流的改变，包括陷阱、中断和异常。这里的“异常”特指因为执行当前指令而产生的错误情况，比如除法异常、缺页异常等。有些书上为了区分，也将这类“异常”称为“故障”。

当发生异常时，操作系统会将控制转移给相应的异常处理程序。如果处理程序能够修正这个错误情况，就将返回到引起异常的指令重新执行。否则，终止该应用程序。

异常处理程序的地址也保存在中断描述符表（IDT）中。

常见的异常类型及处理：

• 除法错误（异常 0）：当应用程序试图除以零，或者一个除法指令结果溢出的时候，就会发生除法错误。Linux 会直接终止程序。Linux shell 报告为“浮点异常（Floating exception）”
• 一般保护故障（异常 13）：当应用程序访问一个未定义的虚拟内存区域（如访问空指针），或者试图写一个只读的文本段时，会发生一般保护故障。Linux 会直接终止程序。Linux shell 报告为“段错误（Segmantation fault）”
• 缺页异常（异常 14）：当应用程序访问未加载的页面时，会引起缺页异常。缺页处理程序会加载适当的页面，然后重新执行引起异常的指令

信号

信号是一种更高层的软件形式的异常，同样会中断进程的控制流，可以由进程进行处理。一个信号代表了一个消息。信号的作用是用来通知进程发生了某种系统事件。

上文的陷阱、中断和异常都是低层异常机制，由内核的异常处理程序进行处理，正常情况下对用户进程是不可见的。信号提供了一种机制，通知用户进程发生了这些异常。比如，如果一个进程试图除以 0，那么内核会收到一个除零异常，内核会给进程发送一个 SIGFPE 信号（=8）

进程间的通信方式

信号 管道 信号量 共享内存 消息队列 套接字

信号

信号是 Linux 系统响应某些条件而产生的一个事件，由操作系统事先定义，接收到该信号的进程可以采取自定义的行为。这是一种“订阅-发布”的模式。

信号来源分为硬件来源和软件来源。

1. 硬件来源。如按下 CTRL+C、除 0、非法内存访问等等
2. 软件来源。如 Kill 命令、Alarm Clock 超时、当 Reader 中止之后又向管道写数据，等等

信号也可以作为进程间通信的一种方式，明确地由一个进程发送给另一个进程。

• 进程如何发送信号？

  • 操作系统提供发送信号的系统调用
  • 该系统调用会将信号放到目标进程的信号队列中
  • 如果目标进程未处于执行状态，则该信号就由内核保存起来，直到该进程恢复执行并传递给它为止。如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消时才被传递给进程

• 进程如何接收信号？

  • 每个进程有一个信号队列，放其他进程发给它、等待它处理的信号
  • 进程在执行过程中的特定时刻，检查并处理自己的信号队列。如从系统空间返回到用户空间之前
  • 发送信号时，必须指明发送目标进程的号码。一般用在具有亲缘关系的进程之间

管道 Pipe

管道命令，在 Linux Shell 中经常使用

管道是一种半双工的通信方式，数据只能单向流动，上游进程往管道中写入数据，下游进程从管道中接收数据。如果想实现双方通信，那么需要建立两个管道。

管道适合于传输大量信息。管道发送的内容是以字节为单位的，没有格式的字节流。

管道就是一个文件，是一种只存在于内存中的特殊的文件系统。

在 Linux 中，管道借助了文件系统的 File 结构实现。父进程使用 File 结构保存向管道写入数据的例程地址，子进程保存从管道读出数据的例程地址。这解释了上文所说的：

单向流动
只能用于具有亲缘关系的进程之间

命名管道 FIFO

命名管道（FIFO）可用于没有亲缘的进程间。Pipe 和 FIFO 除了建立、打开、删除的方式不同外，二者几乎一模一样。

建立命名管道时，会在磁盘中创建一个索引节点，命名管道的名字就相当于索引节点的文件名。索引节点设置了进程的访问权限，但是没有数据块。命名管道实质上也是通过内核缓冲区来实现数据传输。有访问权限的进程，可以通过磁盘的索引节点来读写这块缓冲区。

信号量 Semaphore

信号量是一种特殊的变量，对它的操作都是原子的，有两种操作：V（signal()）和 P（wait()）。V 操作会增加信号量 S 的数值，P 操作会减少它。

• V(S)：如果有其他进程因等待 S 而被挂起，就让它恢复运行，否则 S 加 1
• P(S)：如果 S 为 0，则挂起进程，否则 S 减 1

信号量可以用于实现进程或线程的互斥和同步。

共享内存 Shared Memory

共享内存顾名思义，允许两个或多个进程共享同一段物理内存。不同进程可以将同一段共享内存映射到自己的地址空间，然后像访问正常内存一样访问它。不同进程可以通过向共享内存端读写数据来交换信息。

• 共享内存的优点是简单且高效，访问共享内存区域和访问进程独有的内存区域一样快，原因是不需要系统调用，不涉及用户态到内核态的转换，也不需要对数据不必要的复制。

• 共享内存的缺点是存在并发问题，有可能出现多个进程修改同一块内存，因此共享内存一般与信号量结合使用。

消息队列 Message Queue

消息队列是一个消息的链表，保存在内核中。消息队列中的每个消息都是一个数据块，具有特定的格式。操作系统中可以存在多个消息队列，每个消息队列有唯一的 key，称为消息队列标识符。

• 和信号相比，消息队列能够传递更多的信息。
• 与管道相比，消息队列提供了有格式的数据，但消息队列仍然有大小限制。

消息队列允许一个或多个进程向它写入与读取消息。消息的发送者和接收者不需要同时与消息队列交互。消息会保存在队列中，直到接收者取回它。也就是说，消息队列是异步的，但这也造成了一个缺点，就是接收者必须轮询消息队列，才能收到最近的消息。

套接字 Socket

• 不同的计算机的进程之间通过 socket 通信，也可用于同一台计算机的不同进程
• 需要通信的进程之间首先要各自创建一个 socket，内容包括主机地址与端口号，声明自己接收来自某端口地址的数据
• 进程通过 socket 把消息发送到网络层中，网络层通过主机地址将其发到目的主机，目的主机通过端口号发给对应进程

进程和线程

进程切换是一个开销很大的操作。进程切换的开销主要包括：

• 处理机的上下文切换：保存和恢复相关寄存器的内容
• 与进程相关的数据结构更改：存储管理有关的记录信息（如页表）、文件管理有关数据（如文件描述符）、进程控制块中的各种队列（如阻塞队列、就绪队列、通信队列）等

把一个进程分为多个执行任务的单元体，只为其分配处理机，这些执行任务的单元体就是线程。

线程的上下文切换过程

线程有自己的寄存器和栈。当上下文切换的时候，正在运行的线程会将寄存器的状态保存到 TCB（Thread Control Block）里（进程是 PCB，Process Control Block），然后恢复另一个线程的上下文。

和进程的区别是，线程只需要切换处理机执行的上下文，不会改变地址空间。这意味着：

1. 不需要重新加载页表，切换开销少，提高效率
2. 多个线程共享地址空间，有利有弊

####独占资源，以及为什么需要独占：

• 线程 ID：在本进程中唯一，进程用来标识此线程
• 一组寄存器的值
• 栈：每个线程中的函数调用过程是独立的，因此需要有独立的栈
• 错误返回码：系统调用或库函数发生错误时，会设置全局变量 error，各个线程的错误返回码应该是独立的
• 信号屏蔽码：每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己管理；但每个线程都共享本进程的信号处理器

僵尸进程、孤儿进程、守护进程

• 僵尸进程是指终止但还未被回收的进程。如果子进程退出，而父进程并没有调用 wait() 或 waitpid() 来回收，那么就会产生僵尸进程。僵尸进程是一个已经死亡的进程，但是其进程描述符仍然保存在系统的进程表中。

危害：占用进程号，系统所能使用的进程号是有限的，可能导致不能产生新的进程；占用一定的内存。

• 孤儿进程：如果某个进程的父进程先结束了，那么它的子进程会成为孤儿进程。每个进程结束的时候，系统都会扫描是否存在子进程，如果有则用 Init 进程（pid = 1）接管，并由 Init 进程调用 wait 等待其结束，完成状态收集工作。孤儿进程不会对系统造成危害。

• 守护进程：一种在后台执行的电脑程序。此类程序会被以进程的形式初始化。

死锁的预防、检测、避免、解除

• 死锁产生的四个必要条件

1. 互斥条件
2. 占有且等待条件：线程占有已经分配给它们的资源（如锁）并且等待其他的资源（也就是说不会主动释放）
3. 不可抢占条件（也就是说不会被动释放）
4. 环路等待条件：每个进程都在等待下一个进程占有的资源

这四个条件缺少一个就不会有死锁。

• 预防死锁就是破坏上面四个条件任意一个

• 避免死锁：系统要分析满足该资源请求后，系统是否会发生死锁，若不会发生则实施分配，否则拒绝分配。银行家算法。

• 检测死锁：画出资源分配图，检测是否存在环路。

• 解除死锁： 破坏除了“互斥条件”之外的其他三个条件

1. 回退执行：系统定期对各个进程进行检查，将检查点的有关信息写入文件。死锁时，让某占有必要资源的进程回退到取得资源之前的一个检查点，释放的资源分配给一个死锁进程（破坏“占有且等待”）
2. 抢占资源：剥夺占有进程的资源，分配给另外某些进程，直至死锁环路被打破（破坏“不可抢占”）
3. 杀掉进程：一次终止一个进程，直至消除死锁环路（破坏“循环等待”）

写时复制

写时复制（Copy-on-write，COW），有时也称为隐式共享（implicit sharing）。COW 将复制操作推迟到第一次写入时进行：在创建一个新副本时，不会立即复制资源，而是共享原始副本的资源；当修改时再执行复制操作。通过这种方式共享资源，可以显著减少创建副本时的开销，以及节省资源；同时，资源修改操作会增加少量开销。

写时复制技术。内核不会复制进程的整个地址空间，而是只复制其页表，fork 之后的父子进程的地址空间指向同样的物理内存页。

假如所有进程都只读取其内存页，那么就可以继续共享物理内存中的同一个副本；然而只要有一个进程试图写入共享区域的某个页面，那么就会为这个进程创建该页面的一个新副本。

写时复制技术将内存页的复制延迟到第一次写入时，更重要的是，在很多情况下不需要复制。

栈和堆

虚地址组成

整体上，操作系统将每个进程的虚拟地址空间划分成两个部分：内核空间和用户空间。内核空间存放的是内核代码和数据，用户空间存放的是用户程序的代码和数据。在 32 位操作系统中，一般将最高的 1G 字节作为内核空间，而将较低的 3G 字节作为用户空间。

进程运行在内核空间时，处于内核态，此时可以执行任何特权指令。每个进程的内核空间都是相同的，用户代码无法访问内核空间。

从上往下依次是：

• 内核虚拟内存：所有进程共享内核的代码和全局数据结构，独享与进程相关的数据结构，Linux 会将内核虚拟内存的共享区域映射到被所有进程共享的物理页面上
• 用户栈：从高地址向低地址增长
• 共享库：动态链接阶段
• 运行时堆：从低地址向高地址增长
• 程序代码和数据：从可执行文件中加载（代码段、数据段、BSS 段）

栈

栈的大小是有限的，如默认 8M

用户栈其实就是函数调用栈，作用主要是：

• 保存函数的局部变量
• 保存某些寄存器的值
• 向被调用函数传递参数
• 返回函数的返回值
• 保存函数的返回地址

每个函数在执行过程中都需要使用一块栈内存用来保存上述这些值，这块栈内存为该函数的栈帧（stack frame）。栈的增长和收缩由编译器插入的代码自动完成，随着函数的调用而分配，随函数的返回而自动释放。程序员无需关心，这一点与堆不同。

堆

栈内存的分配需要实现确定其大小，而堆内存允许程序在运行时动态申请某个大小的内存空间。申请的内存在函数退出后依然保留，需要手动释放。

如果反复向操作系统申请堆内存而不释放，会导致内存泄漏。在 C / C++ 中，必须由程序员手动释放堆内存。而 Java / Golang 中有垃圾回收器，会定期主动回收内存。但是即使有垃圾回收器，也有内存泄漏的风险，比如长期持有某个大对象的引用。

物理内存管理

内部碎片和外部碎片：

内部碎片是固定分区法产生的，指被占用分区上未被利用的空间，由于该分区被占用，因此无法被分配使用

外部碎片是动态分区法产生的，指被占用分区之间的小空间，虽然可以被使用，但是由于太小而无法被分配

• 等长固定分区法：每个分区大小相同，在系统启动时分配好，系统运行期间保持不变；每次给进程分配一整块区域，因此进程的大小必须 ≤ 分区的大小

  优点：系统需要维护的管理信息非常少，只要维护一个固定行数的表格，记载分区的使用情况；内存分配算法很简单，有足够大空闲分区就分配，否则就拒绝

  缺点：不同进程需要的空间不同，内部碎片多，浪费空间；分区总数固定，限制了并发执行的程序数量

• 不等长固定分区法：每个分区大小不同，在系统启动时分配好，系统运行期间保持不变；分配时，需要根据进程的大小在空闲分区中选择一个大小合适的分区（优缺点同上）

• 动态分区法：在系统运行中，根据每个进程需要的空间大小确定分区大小；通过空闲分区链表进行组织

  优点 ：并发执行的程序数量不受限制，只取决于是否有大小合适的内存块可以分配

  缺点：管理空闲快的复杂度增加；分配算法的时间开销增加，可能需要遍历多次才能找到合适的内存块

不同的动态分区放置算法及其优缺点

• 最佳适应算法

  • 检查所有空闲分区，选择和新进程申请内存大小最接近的空闲分区
    • 优点：该算法保留大的空闲区
    • 缺点：
      • 检查所有空闲分区需要时间
      • 外部碎片多：会留下许多难以利用的，很小的空闲分区，称为外部碎片
      • 可以采用内存紧凑的方法，将被使用的分区都移动到一起，减少外部碎片。但是移动内存中的代码和数据也需要很多时间

• 最差适应算法

  • 每次为进程分配分区时，都选择最大的空闲分区分配
  • 最差适应算法使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统
    • 优点：该算法保留小的空闲区，尽量减少外部碎片的产生
    • 缺点：检查比较所有的空闲区间需要时间；系统中不会存在面积很大的空闲区间，难满足大进程的要求

• 首次适应法

  • 只要发现能用的分区就分配。这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区
    • 优点：可以剩下大的分区
    • 缺点：外部碎片多，集中在低址部分；并且每次查找都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销

• 下一个适应法

  • 由于上面的放置算法每次都需要从头检查，有可能浪费很多时间。因此“下一个适应法”就是操作系统记住接下来该检查的空闲分区的位置，给进程分配分区时，系统从记录的分区开始依次向后查找直到碰到能用的分区为止，如果到链表尾还没有找到，就再从头开始
  • 缺点：上面的三个放置算法都是按照分区大小来分配，或是留下大区间（首次适应，最佳适应），或是留下小区间（最差适应）。下一个适应法很难剩下面积很大的区间，会使剩余分区的大小比较平均

参考：https://imageslr.com/2020/07/08/tech-interview.html