操作系统知识点总结

进程管理

进程和线程

深入理解进程和线程

• 进程的调度和资源分配是操作系统负责。同一进程的所有线程共享以下资源：
  • 堆。堆是在进程空间开辟的，所以被共享。
  • 全局变量。与某一函数无关，与特定线程无关。
  • 静态变量。静态变量存放位置和全局变量一样，都存在于堆中开辟的 .bss 和 .data 段，是共享的。
  • 其他一些共用资源，比如文件。
• 线程的调度和资源分配是 CPU 负责。
  • 栈。线程运行的本质就是函数的执行，而函数的执行总会有一个源头，这个源头叫做入口函数，CPU 从入口函数开始一步一步向下执行，这个过程就叫做线程。由于函数运行时信息是保存在栈中的，比如返回值，参数，局部变量等等，所以栈是私有的。
  • 寄存器和程序计数器。CPU执行指令的信息会保存在寄存器中，这个寄存器叫做程序计数器。由于操作系统可以随时终止线程的运行，所以保存和恢复程序计数器的值就知道线程从哪里暂停的以及从哪里开始运行。
• 进程是操作系统资源分配 (包括 CPU、内存、磁盘 IO 等) 的基本单位，一个 CPU 同时刻只能执行一个进程。
  • 单 CPU 实现多进程——并发。 通过操作系统的进程调度算法，单 CPU 进行进程调度的时候，需要读取上下文+执行程序+保存上下文，即进程切换。
  • 多 CPU 实现多进程——并行。 不同的进程运行在不同的 CPU 上。
• 线程是 CPU 调度的基本单位，一个 CPU 核心同时刻只能执行一个线程。
  • 单核 CPU 实现多线程——并发。 不同线程为了使用 CPU 核心，则会进行线程切换，但是由于共享了程序执行环境，这个线程切换比进程切换开销少了很多。
  • 多核 CPU 实现多线程——并行。 CPU 可以将不同线程分配到不同的 CPU 核心处理器中。
• 并行的上限：进程与 CPU 个数有关，线程与 CPU 核心个数有关，并不是所有线程和所有进程都能同时运行。

  进程与 PCB

  进程

• 进程是操作系统的资源分配单位，实现操作系统的并发，对于一个进程，它在被执行前其实是一个可执行程序。这个程序是被放在磁盘上的，当它要被执行的时候，它先被加载到内存当中，然后再放入到寄存器中，最后再让 CPU 执行该程序，这个时候一个静态的程序就变成了进程。
• 进程创建时会分配 4G 的内存（32 位系统），其中 0-3G 是用户空间，3-4G 是内核空间。PCB 存放在操作系统内核中而不是进程内核空间中。
  • 操作系统内核负责管理系统的各种资源和进程的调度，而进程内核空间则提供了进程执行内核代码的环境和接口。
  • 当进程需要访问操作系统提供的服务或进行系统调用时，它会切换到内核模式，并在进程内核空间中执行相关的代码。
• 进程的用户空间是不同的，内核空间是不同但独立的。比如每个进程的不同系统调用，是陷入自己独立的内核空间里面，所以每个进程内核的堆栈肯定是不一样的。

  PCB

• PCB (Process Control Block) 进程控制块，描述进程的基本信息和运行状态，进程的创建和销毁都是对 PCB 进行操作，PCB 的具体内容如下：
  • 进程描述信息
    • 进程标识符 pid；
    • 用户标识符 uid；
  • 进程控制和管理信息
    • CPU、磁盘、网络流量使用情况统计…
    • 进程当前状态：就绪态/阻塞态/运行态…
  • 资源分配清单
    • 正在使用哪些文件
    • 正在使用哪些内存区域
    • 正在使用哪些 IO 设备
  • 处理机相关信息
    • 如 PSW、PC 等各种寄存器的值（用于实现进程切换）

• 每个进程的 PCB 都是存在所有进程共享的内核空间（操作系统内核）中，操作系统管理进程，也就是在内核空间中管理的，在内核空间中通过双向链表管理所有进程的 PCB，如果有一个进程要被创建，实际上多分配了这么一个 4G 的虚拟内存，并在共享的内核空间中的双向链表中加入了自己的 PCB。

  进程的各个状态

  

• 创建
  • 申请空白 PCB
  • 为新进程分配所需要的资源
  • 初始化 PCB
  • 将 PCB 插入就绪队列
• 终止
  • 从 PCB 集合中找到终止进程的 PCB
  • 若进程正在运行，立即剥夺 CPU，将 CPU 分配给其他进程
  • 终止其所有子进程
  • 将该进程拥有的所有资源归还给父进程或操作系统
  • 删除 PCB
• 阻塞
  • 找到要阻塞的进程的 PCB
  • 保护进程和运行现场，将 PCB 状态信息设置为“阻塞态”，暂时停止运行进程
  • 将 PCB 插入到相应事件的等待队列
• 唤醒
  • 在事件等待队列中找到 PCB
  • 将 PCB 从等待队列中移除，设置进程为就绪态
  • 将 PCB 插入就绪队列，等待被调度
• 切换
  • 将运行环境信息存入 PCB
  • PCB 移入相应队列
  • 选择另一个进程执行，并更新其 PCB
  • 根据 PCB 恢复新进程所需的运行环境

    并行和并发

• 并发：在同一时刻只能有一条指令执行，但多个进程指令被快速轮换执行，使得在宏观上具有多个进程同时执行的效果。
• 并行：在同一时刻，有多条指令在多个处理器上同时执行

  CPU 及其核心数量

• 单核 CPU 和多核 CPU 都是一个 CPU，不同的是每个 CPU 上的核心数，一个核心只能同时执行一个线程
  • 单核 CPU：一个 CPU 中只有一个核心处理器
  • 多核 CPU：一个 CPU 有多个核心处理器，处理器之间通过CPU 内部总线进行通讯（多核 CPU 是多个 CPU 的替代方案，同时能减少功耗）
• 多 CPU：简单的多个 CPU 工作在同一个系统上，多个 CPU 之间通过主板上的总线进行通讯

  计算密集型任务和 I/O 密集型任务

• 计算密集型任务：
  • 特点是要进行大量的计算，消耗 CPU 资源，比如计算圆周率、对视频进行高清解码等等，全靠 CPU 的运算能力。
  • 虽然可以用多任务完成，但是任务越多，花在任务切换的时间就越多，CPU 执行任务的效率就越低，所以，要最高效地利用 CPU，计算密集型任务同时进行的数量应当等于 CPU 的核心数。
• I/O 密集型任务：
  • 涉及到网络、磁盘 I/O 的任务都是 I/O 密集型任务，这类任务的特点是 CPU 消耗很少，任务的大部分时间都在等待 I/O 操作完成（因为 I/O 的速度远远低于 CPU 和内存的速度）。
  • 对于 I/O 密集型任务，任务越多，CPU 效率越高，但也有一个限度。常见的大部分任务都是 IO 密集型任务，比如 Web 应用。$最佳线程数目 = ((线程等待时间 + 线程 CPU 时间) / 线程 CPU 时间 ) * CPU 数目$。线程等待时间所占比例越高，需要越多线程。线程 CPU 时间所占比例越高，需要越少线程。
• 混合型任务：
  • 混合型任务可以将任务分成 IO 密集型和 CPU 密集型任务，然后分别用不同的线程池去处理。只要分完之后两个任务的执行时间相差不大，那么就会比串行执行来的高效。因为如果划分之后两个任务执行时间相差甚远，那么先执行完的任务就要等后执行完的任务，最终的时间仍然取决于后执行完的任务，而且还要加上任务拆分与合并的开销，得不偿失。
• 针对任务类型来确定线程池线程数：
  • 高并发、任务执行时间短的业务：
    • 线程池线程数可以设置为 CPU 核数+1，减少线程上下文的切换。
  • 并发不高、任务执行时间长的业务：
    • 假如是业务时间集中在 I/O 操作上，也就是 I/O 密集型的任务，因为 I/O 操作并不占用 CPU，所以不要让所有的 CPU 闲下来，可以适当加大线程池中的线程数目，让 CPU 处理更多的业务；
    • 假如是业务时间长集中在计算操作上，也就是计算密集型任务，这个就没办法了，线程池中的线程数设置得少一些，减少线程上下文的切换；
  • 并发高、业务执行时间长：
    • 解决这种类型任务的关键不在于线程池而在于整体架构的设计，看看这些业务里面某些数据是否能做缓存是第一步，增加服务器是第二步
    • 最后，业务执行时间长的问题，也可能需要分析一下，看看能不能使用中间件对任务进行拆分和解耦。

什么时候使用多进程和多线程：

• 单核 CPU：
  • I/O 密集型任务：最好还是要用多线程，避免用户没法对计算机进行操作。
  • 计算密集型任务：此时的任务已经把 CPU 资源 100%消耗了，就没必要也不可能使用多线程来提高计算效率了。
• 多核 CPU：
  • I/O 密集型任务：任务越多，CPU 利用效率越高，尽量使用多线程。
  • 计算密集型任务：此时要尽量使用多线程，可以提高任务执行效率，例如加密解密，数据压缩解压缩（视频、音频、普通数据），否则只能使一个核心满载，而其他核心闲置。
• 优先使用线程：
  • 需要频繁创建和销毁；
  • 需要进行大量计算；
  • 强相关的处理；
• 优先使用进程：
  • 弱相关的处理；
  • 追求稳定性；

    进程间通信方式

    每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，内核是可以共享的。在内核中开辟一块缓冲区，进程 1 把数据从用户空间拷到内核缓冲区，进程 2 再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC，InterProcess Communication）。
    进程间通信主要包括管道、系统 IPC（包括消息队列、信号、共享内存等）、本地套接字 socket。

    管道

管道允许进程以先进先出的方式传送数据，是半双工的，意味着数据只能往一个方向流动。因此当双方通信时，必须建立两个管道。管道的实质就是在内核中创建一个缓冲区，管道一端的进程进入管道写数据，另一端的进程进入管道读取数据。管道分为 PIPE（管道）和 FIFO（命名管道） 两种。

• 无名管道（PIPE）：
  • 一种半双工的通信方式，只能在具有亲缘关系的进程间使用（父子进程或兄弟进程）（最简单）。
  • 其本质是一个伪文件（实为内核缓冲区），由两个文件描述符引用，一个表示读端，一个表示写端，规定数据从管道的写端流入管道，从读端流出。管道中数据不可反复读取，一旦读走，管道中不再存在。
  • 读管道：
    • 管道中有数据，read 返回实际读到的数据；
    • 管道中无数据
      • 写端被全部关闭，read 返回 0（好像读到文件结尾）；
      • 写端没有被全部关闭，read 阻塞等待（不久的将来可能有数据抵达，此时会让出 CPU）；
  • 写管道：
    • 管道读端全部被关闭，进程异常终止；
    • 管道读端没有全部关闭：
      • 管道已满，write 阻塞；
      • 管道未满，write 将数据写入，并返回实际写入的字节数；
• 有名管道（FIFO）：
  • 一种半双工的通信方式，可以在非亲缘关系的进程间使用，任何进程可以根据管道的文件名将其打开和读写。
  • FIFO 是 Linux 基础文件类型中的一种。但是，FIFO 文件在磁盘上没有数据块，仅仅用来标识内核中的一条通道。各进程可以打开这个文件进行 read/write，实际上是在读写内核通道，这样就实现了进程间通信。
• 缺点：管道本质上是通过内核交换数据的，因此通信效率很低，不适合频繁交换数据的情况。

  消息队列

  消息队列是保存在内核中的链表，由一个个独立的数据块组成，消息的接收方和发送方要约定具体的消息类型。当进程从消息队列中读取了相关数据块，则内核会将该数据块删除。跟管道相比，消息队列不一定按照先进先出的方式读取，也可以按照消息类型进行读取。
• 消息队列是消息的链表，存放在内核中，并由消息队列标识符标识；
• 消息队列克服了信号传递信息少，管道缓冲区大小受限的缺点。
• 一个消息队列由一个标识符（即队列 ID）来标记。
• 缺点：不能实现实时通信。数据块是有大小限制的。消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

  共享内存

共享内存技术就是要解决用户态和内核态之间频繁发生拷贝过程的。现代操作系统对于内存管理普遍采用的是虚拟内存技术，每个进程都有自己独立的虚拟内存空间，不同进程的虚拟内存空间映射到不同的物理内存中。
共享内存技术的实质就是拿出一块虚拟地址空间，映射到相同的物理内存中。这样的好处是一个进程写入数据后另一个进程可以立刻看到，不用进行拷贝。因为数据不需要在不同进程之间进行复制，这是最快的一种 IPC。
共享内存使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。多个进程可以同时操作，所以需要进行同步，一般与信号量配合使用。
共享内存有两个，一个 mmap，一个 system V 的 shmget 。

• mmap 的原理：mmap 用于把文件映射到内存空间中，简单说 mmap 就是把一个文件的内容在内存里面做一个映射。映射成功后，用户对这段内存区域的修改可以直接反映到内核空间，同样，内核空间对这段区域的修改也直接反映用户空间。那么对于内核空间和用户空间两者之间需要大量数据传输等操作的话效率是非常高的。
• mmap 的步骤：
  • 将硬盘上文件的位置与进程逻辑地址空间中一块大小相同的区域之间的一一对应；
  • mmap() 会返回一个指针 ptr，它指向进程逻辑地址空间中的一个地址，这样以后，进程无需再调用 read 或 write 对文件进行读写，而只需要通过 ptr 就能够操作文件。但是 ptr 所指向的是一个逻辑地址，要操作其中的数据，必须通过 MMU（内存管理单元）将逻辑地址转换成物理地址；
  • 建立内存映射并没有实际拷贝数据，这时，MMU 在地址映射表中是无法找到与 ptr 相对应的物理地址的，也就是 MMU 失败，将产生一个缺页中断，缺页中断的中断响应函数会在 swap 中寻找相对应的页面，如果找不到（也就是该文件从来没有被读入内存的情况），则会通过 mmap() 建立的映射关系，从硬盘上将文件读取到物理内存中；
  • 如果在拷贝数据时，发现物理内存不够用，则会通过虚拟内存机制（swap）将暂时不用的物理页面交换到硬盘上。
• mmap 的效率：
  • read() 是系统调用，其中进行了数据拷贝，它首先将文件内容从硬盘拷贝到内核空间的一个缓冲区，然后再将这些数据拷贝到用户空间，在这个过程中，实际上完成了两次数据拷贝 ；
  • mmap() 也是系统调用，如前所述，mmap() 中没有进行数据拷贝，真正的数据拷贝是在缺页中断处理时进行的，由于 mmap() 将文件直接映射到用户空间，所以中断处理函数根据这个映射关系，直接将文件从硬盘拷贝到用户空间，只进行了一次数据拷贝 ；
• 基于 POSIX mmap 文件映射实现共享内存的注意事项：
  • 创建映射区的过程中，隐含着一次对映射文件的读操作，所以文件不能只有写权限；
  • 特别注意，当映射文件大小为 0 时，不能创建映射区，用于映射的文件必须要有实际大小；
  • 文件偏移量必须是 4K 的整数倍；
  • 映射区的释放与文件关闭无关。只要映射建立成功，文件可以立即关闭；

    信号

    上面那几种进程间通信，都是常规状态下的。异常状态下的需要用信号来通知进程（注意：信号和信号量完全是不一样的东西）。可以在任何时刻给进程发送信号，信号是进程间通信或操作的一种异步通信机制。信号和信号量的区别如下：
• 信号是一种异步通信机制，用于向进程或线程发送通知信号，让其进行相应的处理。信号通常由操作系统或其他进程发送，而接收信号的进程或线程则需要事先设置相应的信号处理函数来处理接收到的信号。
• 信号量则是一种同步机制，用于控制并发访问共享资源。信号量通常是一个整数值，可以用于表示某一资源的可用数量。在使用该资源时，进程或线程需要通过对信号量进行 P 操作（申请资源）来获得该资源，使用完后再通过对信号量进行 V 操作（释放资源）来释放该资源，以保证不会出现资源的竞争和互斥。

收到信号后进程对信号的处理有三种方式：

• 如果是系统定义的信号函数，执行默认操作。
  • SIGINT ：程序终止信号。程序运行过程中，按 Ctrl+C 键将产生该信号。进程接收到 SIGINT 信号后通常会进行一些清理工作，然后正常终止运行。
  • SIGQUIT ：程序退出信号。程序运行过程中，按 Ctrl+\| 键将产生该信号。默认情况下，进程接收到 SIGQUIT 信号后会立即终止运行，并在控制台输出一些调试信息，这通常用于快速退出当前进程或线程的调试。
  • SIGALRM ：定时器信号。
  • SIGTERM ：结束进程信号。shell 下执行 kill pid 发送该信号。
    • 使用 kill + pid 命令可以向进程发送 SIGTERM 信号，即请求进程正常终止。但是，如果进程在处理信号时没有响应，那么进程就不会终止。这可能是因为进程正在执行某个耗时操作，或者进程没有正确处理信号导致无法正常终止；
    • 此时，可以尝试使用 kill -9 + pid 命令向进程发送强制终止的信号，强制终止进程。但需要注意的是，强制终止进程可能会导致进程中未完成的操作未被正确地处理，从而引发一些问题；
• 捕捉信号。用户可以给信号定义信号处理函数，表示收到信号后该进程该怎么做。
• 忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

  Unix 域套接字

  socket API 原本是为网络通讯设计的，但后来在 socket 的框架上发展出一种 IPC 机制，就是 UNIX Domain Socket（UNIX 域间套接字）。虽然网络 socket 也可用于同一台主机的进程间通讯（通过 loopback 地址 127.0.0.1），但是 UNIX Domain Socket 用于 IPC 更有效率：不需要经过网络协议栈，不需要打包拆包、计算校验和、维护序号和应答等，只是将应用层数据从一个进程拷贝到另一个进程。

UNIX 域套接字与 TCP 套接字相比较，在同一台主机的传输速度前者是后者的两倍。这是因为，IPC 机制本质上是可靠的通讯，而网络协议是为不可靠的通讯设计的。UNIX Domain Socket 也提供面向流和面向数据包两种 API 接口，类似于 TCP 和 UDP，但是面向消息的 UNIX Domain Socket 也是可靠的，消息既不会丢失也不会顺序错乱。

• UNIX 域套接字是通过文件系统实现的一种进程间通信机制，它不依赖于网络协议栈。在内核中，UNIX 域套接字会被当做一种特殊的文件类型，它使用文件系统的 inode 来实现通信。当一个进程需要使用 UNIX 域套接字进行进程间通信时，它会创建一个 UNIX 域套接字文件，并将其与一个进程关联起来。另外一个进程也可以打开该文件，这样它们就可以进行通信了。
• UNIX 域套接字通过本地地址（Local Address）来确定通信的双方，本地地址是一个文件路径，用于标识 UNIX 域套接字文件的位置。每个 UNIX 域套接字都有一个独特的文件描述符（File Descriptor），通过这个文件描述符可以进行读写操作。同时，UNIX 域套接字也支持类似于网络套接字的事件驱动模型，可以使用 select 等函数进行事件监听。

  进程同步

  在多道程序环境下，当程序并发执行时候，由于资源共享和进程间相互协作的关系，同一个系统中的诸进程之间会存在一下两种相互制约的关系：
• 间接相互制约。主要是资源共享这种情况。
• 直接相互制约。源于进程间的相互合作，例如 A 进程向 B 进程提供数据，当 A 缓存没数据的时候 B 就阻塞，A 缓存满时 A 就阻塞。

临界区与进程同步：

• 临界区：许多硬件资源如打印机，磁带机等，都属于临界资源，诸进程应该采取互斥方式，实现对这种资源的共享。人们把在每个进程中访问临界资源的那段代码称为临界区，显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。
• 同步机制遵循的原则：
  • 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效的利用临界资源。
  • 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其他视图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
  • 有限等待。对要求访问临界资源的进程，应保证在有限时限内能进入自己的临界区，以免陷入死等状态。
  • 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态。
• 进程同步的实现机制：
  • 提高临界区代码执行中断的优先级： 在传统操作系统中，打断进程对临界区代码的执行只有中断请求、中断一旦被接受，系统就有可能调用其它进程进入临界区，并修改此全局数据库。所以用提高临界区中断优先级方法就可以屏蔽其它中断，保证临界区的执行不被打断，从而实现了互斥。
  • 自旋锁：内核（处理器也如此）被保持在过渡状态「旋转」，直到它获得锁，「自旋锁」由此而得名。自旋锁像它们所保护的数据结构一样，储存在共用内存中。为了速度和使用任何在处理器体系下提供的锁定机构，获取和释放自旋锁的代码是用汇编语言写的。
  • 信号量机制：信号量其实是一个计数器，表示资源的数量，用于实现进程间的互斥和同步。
    • P 操作 会把信号量减一，减一之后如果信号量的值小于零，则表示资源已经被占用，进程需要阻塞等待；如果信号量减一后大于等于 0，表明进程可以正常执行。
    • V 操作跟 P 操作正好相反。

注：信号量和互斥量之间的区别

• 互斥量用于线程的互斥，信号量用于线程的同步。这是互斥量和信号量的根本区别，也就是互斥和同步之间的区别。
  • 互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
  • 同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问
• 互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。

进程同步经典问题

生产者消费者问题

问题描述：两个进程（生产者和消费者）共享一个公共的固定大小的缓冲区。生产者将数据放入缓冲区，消费者从缓冲区中取数据。也可以扩展成 m 个生产者和 n 个消费者。当缓冲区空的时候，消费者因为取不到数据就会睡眠，知道缓冲区有数据才会被唤醒。当缓冲区满的时候，生产者无法继续往缓冲区中添加数据，就会睡眠，当缓冲区不满的时候再唤醒。

哲学家就餐问题

读写者问题

进程调度算法

进程调度算法也称 CPU 调度算法，因为进程是由 CPU 调度的。
调度分为两大类：抢占式调度和非抢占式调度。抢占式调度说明程序正在运行时可以被打断，把 CPU 让给其他进程。非抢占式调度表示一个进程正在运行时，只有当进程完成或者阻塞的时候把 CPU 让出来。

批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

• 先来先服务调度算法（first-come first-serverd，FCFS）。
  • 非抢占式的调度算法。每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
  • FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。
• 最短作业优先调度算法（shortest job first，SJC）。
  • 非抢占式的调度算法。按估计运行时间最短的顺序进行调度
  • 长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
• 最短剩余时间优先调度算法（shortest remaining time next，SRTN）。
  • 最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。
  • 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

• 时间片轮转调度算法。
  • 将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。
  • 当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
• 优先级调度算法。
  • 为每个进程分配一个优先级，按优先级进行调度。
  • 为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
• 多级反馈队列调度算法。
  • 一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
  • 多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1, 2, 4, 8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。
  • 每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
  • 可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

    僵尸进程和孤儿进程

• 孤儿进程：当父进程先结束，子进程此时就会变成孤儿进程，孤儿进程会自动向上被 init 进程收养，init 进程完成对状态收集工作。而且这种过继的方式也是守护进程能够实现的因素。
• 僵尸进程：如果子进程先结束，父进程并未调用 wait 或者 waitpid 获取进程状态信息，回收进程资源，那么子进程描述符就会一直保存在系统中，这种进程称为僵尸进程。
  • 僵尸进程是每个子进程退出时必然经历的过程。
  • 僵尸进程的危害：
    • 在每个进程退出的时候，内核释放该进程所有的资源，包括打开的文件，占用的内存等。但是仍然为其保留一定的信息（包括进程号，退出状态，运行时间等）。直到父进程通过 wait 或 waitpid 来获取时才释放。
    • 如果进程不调用 wait / waitpid 的话，那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号是有限的，如果大量的产生僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程。
  • 如何消除僵尸进程：
    • kill 发送 SIGTERM 或者 SIGKILL 信号消灭产生僵尸进程的进程，它产生的僵尸进程就变成了孤儿进程，这些孤儿进程会被 init 进程接管。
    • 子进程退出时向父进程发送 SIGCHILD 信号，父进程通过 std::signal() 函数注册处理函数来处理 SIGCHILD 信号。在信号处理函数中调用 wait 进行处理僵尸进程。

      线程间通信方式

      锁机制（互斥量）

• 互斥锁。确保同一时间内只有一个线程能访问共享资源。当资源被占用时其他试图加锁的线程会进入阻塞状态。当锁释放后，哪个线程能上锁取决于内核调度。
  • pthread_mutex_init ：初始化互斥锁
  • pthread_mutex_destroy ：销毁互斥锁
  • pthread_mutex_lock ：以原子操作的方式给一个互斥锁加锁，如果目标互斥锁已经被上锁，pthread_mutex_lock 调用将阻塞，直到该互斥锁的占有者将其解锁。
  • pthread_mutex_unlock ：以一个原子操作的方式给一个互斥锁解锁。
• 读写锁。当以写模式加锁的时候，任何其他线程不论以何种方式加锁都会处以阻塞状态。当以读模式加锁时，读状态不阻塞，但是写状态阻塞。「读模式共享，写模式互斥」。
• 自旋锁。上锁受阻时线程不阻塞而是在循环中轮询查看能否获得该锁，没有线程的切换因而没有切换开销，不过对 CPU 的霸占会导致 CPU 资源的浪费。

  信号量

  信号量是一种特殊的变量，可用于线程同步。它只取自然数值，并且只支持两种操作：

• P(SV) : 会把信号量SV减一，减一之后如果信号量的值小于零，则表示资源已经被占用，进程需要阻塞等待；如果信号量减一后大于等于 0，表明进程可以正常执行。
• V(SV) ：将信号量 SV 加一，加一后如果信号量的值小于等于零，则表明有进程需要唤醒。
  相关系统调用：

• sem_wait（sem_t *sem） ：以原子操作的方式将信号量减 1，如果信号量值为 0，则 sem_wait 将被阻塞，直到这个信号量具有非 0 值。
• sem_post（sem_t *sem) ：以原子操作将信号量值加 1。当信号量大于 0 时，其他正在调用 sem_wait 等待信号量的线程将被唤醒。
  信号量和互斥量的区别：
• 信号量是用于多线程多任务同步的，一个线程完成某一个动作就通过信号量告诉别的线程，别的线程再进行某些动作。
• 而互斥量是用于多线程多任务互斥的，一个线程占用了某一资源，那么别的线程就无法访问，直到这个线程解锁，其他线程才可以利用这个资源。比如对全局变量的访问，有时要加锁，操作完再解锁。
• 不难看出，mutex 是 semaphore 的一种特殊情况（n=1 时）。也就是说，完全可以用后者替代前者。但是，因为 mutex 较为简单，且效率高，所以在必须保证资源独占的情况下，还是采用这种设计。
• 简而言之，锁是服务于共享资源的；而 semaphore 是服务于多个线程间的执行的逻辑顺序的。

  条件变量

  条件变量，用于在线程之间同步共享数据的值。条件变量提供一种线程间通信机制：当某个共享数据达到某个值时，唤醒等待这个共享数据的一个/多个线程。即，当某个共享变量等于某个值时，调用 signal/broadcast。此时操作共享变量时需要加锁。

• 系统调用
  • pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr) : 初始化条件变量。
  • pthread_cond_destroy(pthread_cond_t *cond) ：销毁条件变量。
  • pthread_cond_signal(pthread_cond_t *cond) ：唤醒一个等待目标条件变量的线程。哪个线程被唤醒取决于调度策略和优先级。
  • pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) ：等待目标条件变量。需要一个加锁的互斥锁确保操作的原子性。该函数在进入 wait 状态前会首先进行解锁，然后在接收到信号后会再加锁，保证该线程对共享资源正确访问。

    死锁

    死锁产生的条件

    死锁是多个并发进程因争夺系统资源而产生相互等待的现象，其产生条件如下：

• 互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源；
• 请求和保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源；
• 不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放；
• 循环等待条件：进程发生死锁后，必然存在一个进程和资源之间的环形链，环路中每个进程都在等待下一个进程所占有的资源；

  如何避免死锁

• 破坏请求和等待条件。 所有的进程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源；
• 破坏不可抢占条件。 当进程新的资源未得到满足时，释放已占有的资源；
• 破坏循环等待条件。 系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反；

  内存管理

  虚拟内存

  虚拟内存就是来解决「程序大于内存的问题」，即如何不把程序全部装进内存而运行。
• *虚拟内存的基本思想是每个程序都拥有自己的地址空间，这些空间被分割成多个块儿。每一块儿被称作一页或者页面。每一个页面有连续的地址范围。这些页面被映射到物理内存，但是并不是一个程序的所有的页面都必须在内存中才能运行**。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失部分装入物理内存并重新执行指令。
• *虚拟内存使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间）**，而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如 RAM）的使用也更有效率。

  分段

  程序是由若⼲个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就⽤分段（Segmentation）的形式把这些段分离出来。
  分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量。
  

• 段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
• 虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

分段使得程序本身不需要关心具体的物理内存地址问题，但它也有一些不足之处：

• 分段带来了内存碎片问题
  • 外部内存碎片：内存中产生了多个不连续的小空闲内存地址空间，导致新的程序无法装载到内存；
  • 内部内存碎片：虽然程序的各个部分通过分段后装载到了内存的不同位置，但是这个程序的很多部分可能并不是经常使用的，这也会带来内存的浪费；
• 分段方式的内存交换效率较低
  • 解决外部内存碎片的问题就是内存交换。这个内存交换空间，在 Linux 系统里，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。对于多进程的系统来说，用分段的方式，内存碎片是很容易产生的，产生了内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。
  • 因为硬盘的访问速度要比内存慢太多了，每一次内存交换，我们都需要把一大段连续的内存数据写到硬盘上。所以，如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。**为了解决内存分段的内存碎片和内存交换效率低的问题，就出现了内存分页。

分页

分段的好处就是能产⽣连续的内存空间，但是会出现内存碎⽚和内存交换的空间太⼤的问题。一种解决方式时使用更小的内存加载粒度和交换粒度，这种方式就是内存分页。
分⻚是把整个虚拟和物理内存空间切成⼀段段固定尺⼨的⼤⼩。这样⼀个连续并且尺⼨固定的内存空间，我们叫⻚（Page）。在 Linux 下，每⼀⻚的⼤⼩为 4KB 。

• ⻚表是存储在内存⾥的，内存管理单元 （MMU）就做将虚拟内存地址转换成物理地址的⼯作。
• ⽽当进程访问的虚拟地址在⻚表中查不到时，系统会产⽣⼀个缺⻚异常，进⼊系统内核空间分配物理内存、将数据加载到内存、更新进程⻚表，最后再返回⽤户空间，恢复进程的运⾏。
• 虚拟地址分为两部分，⻚号和⻚内偏移。⻚号作为⻚表的索引，⻚表包含物理⻚每⻚所在物理内存的基地址，这个基地址与⻚内偏移的组合就形成了物理内存地址。
  
  分页存在的问题：
• 在 32 位的环境下，每个进程的虚拟地址空间共有 4GB，假设⼀个⻚的⼤⼩是 4KB（2^12），那么就需要⼤约 100 万 （2^20） 个⻚，每个「⻚表项」需要 4 个字节⼤⼩来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储⻚表，也即每个进程都需要一个 4MB 的内存来存储其页表。

  分表

  要解决普通分页（单级页表）带来的内存占用问题，一种解决方式是通过采用多级页表的方法来减少页表的内存开销。
• 对于单⻚表的实现⽅式，在 32 位和⻚⼤⼩ 4KB 的环境下，⼀个进程的 ⻚表需要装下 100 多万个「⻚表项」，并且每个⻚表项是占⽤ 4 字节⼤⼩的，于是相当于每个⻚表需占⽤ 4MB ⼤⼩的空间
• 把这个 100 多万个「⻚表项」的单级⻚表再分⻚，将⻚表（⼀级⻚表）分为 1024 个⻚ 表（⼆级⻚表），每个表（⼆级⻚表）中包含 1024 个「⻚表项」，形成⼆级分⻚。但如果某个⼀级⻚表的⻚表项没有被⽤到，也就不需要创建这个⻚表项对应的⼆级⻚表了，即可以在需要时才创建 ⼆级⻚表。
• 我们可以把⼆级分⻚再推⼴到多级⻚表，就会发现⻚表占⽤的内存空间更少了，这⼀切都要归功于对局部性原理的充分应⽤。
  

  快表 TLB

  多级⻚表虽然解决了空间上的问题，但增加了虚拟地址到物理地址转换步骤，这会降低地址转换速度增加时间开销。我们同样可以基于局部性原理来减少这部分时间开销。
  利用局部性原理，我们可以将最常访问的部分页表项存储到访问速度更快的硬件，当前的 CPU 芯片中大多加入了一个专门存放这部分页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer），通常也被称为页表缓存、转址旁路缓存、快表。
• 有了 TLB 之后，CPU 在寻址时，会先通过 MMU 将虚拟地址转为物理地址，然后查询TLB；
• 如果在 TLB 中找不到对应的页表项，MMU 将从内存中加载相应的页表，并将其存储到 TLB 中，以便下一次访问；
• 可以说 TLB 是 MMU 的一部分，它加速了虚拟地址到物理地址的转换，提高了系统性能；

  缺页置换算法

• 先进先出 (FIFO) 算法：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。
• 最近最少使用（LRU）算法: 置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。

  虚拟内存布局

  

32 位系统下，Linux 的每个进程都有各自独立的 4G 虚拟内存空间（逻辑地址），其中 0-3G 是用户态空间，3~4G 是内核空间，不同进程相同的逻辑地址会映射到不同的物理地址中。如上图所示，该虚拟内存空间的布局自下而上可以分为以下几个区域：

• 代码段（.text 和 .rodata 段）。分为只读存储区和代码区，存放字符串常量和程序机器代码和指令
• 数据段（.data 段）。存储已初始化的全局变量和静态变量。
• .bss 段（Block Started by Symbol Segment，BSS 段）。也称为未初始化数据段，用于存放程序中未被初始化的全局变量和静态变量。这些变量在程序启动时会被自动初始化为0或空指针。
• 堆（heap）。用于存放动态分配的内存，例如通过 malloc 和 realloc 函数分配的内存。当进程未调用 malloc 时是没有堆段的，malloc开辟的内存空间向上生长。堆是由程序员手动管理的，需要手动分配和释放内存。
• 映射区。存储动态链接库以及调用 mmap 函数进行的文件映射
• 栈（stack）。存储函数的返回地址、参数、局部变量、返回值，向下生长。栈是由编译器自动管理的，不需要手动分配和释放内存。
• 环境变量区：用于存放进程的环境变量，例如 PATH 和 HOME 等变量。
  

堆和栈

在进程的虚拟内存布局场景下，堆和栈表示两种内存管理方式：

• 栈是由操作系统自动分配的，用于存放函数参数值，局部变量。存储在栈中的数据的生命周期随着函数的执行结束而结束。栈的内存生长方向与堆相反，由高到低，按照变量定义的先后顺序入栈。栈的大小是固定的，通常在程序启动时由操作系统分配（栈的大小由操作系统决定，一般取决于硬件平台和操作系统版本等因素）。
• 堆是由用户自己分配的。如果用户不回收，程序结束后由操作系统自动回收。堆的内存地址生长方向与栈相反，由低到高。堆的大小是动态变化的，它可以在程序运行时向上增长，直到达到操作系统的限制。

  内存映射

  Linux 通过将一个虚拟内存区域与一个磁盘上的对象（object）关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射（memory mapping）。
  实现这样的映射关系后，进程就可以采用指针的方式读写操作这一段内存，而系统会自动回写脏页面到对应的文件磁盘上，即完成了对文件的操作而不必再调用 read， write 等系统调用函数。相反，内核空间对这段区域的修改也直接反映用户空间，从而可以实现不同进程间的文件共享。
  
  虚拟内存区域可以映射到两种类型的对象中的一种：
• Linux 文件系统中的普通文件：一个虚拟内存区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区（section）被分成页大小的片，每一片包含一个虚拟页面的初始内容。因为按需进行页面调度，所以这些虚拟页面没有实际交换进入物理内存，直到 CPU 第一次引用到页面（即发射一个虚拟地址，落在地址空间这个页面的范围之内）。
• 匿名文件：一个虚拟内存区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。CPU 第一次引用这样一个区域内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页面，如果该页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为是驻留在内存中的。注意在磁盘和内存之间并没有实际的数据传送。因为这个原因，映射到匿名文件的区域中的页面有时也叫做请求二进制零的页（demand-zero page）。
  无论在哪种情况中，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件（swap file）之间换来换去。交换文件也叫做交换空间（swap space）或者交换区域（swap area）。

  共享对象

  一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。
• 如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。而且，这些变化也会反映在磁盘上的原始对象中。如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。而且，这些变化也会反映在磁盘上的原始对象中。
• 另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。