进程管理

发表于 |

本文为操作系统复习笔记，临时上传以供移动端阅读。

[TOC]

进程管理

进程与线程

1. 进程

进程是==资源分配==的基本单位。下图显示了 4 个程序创建了 4 个进程，这 4 个进程可以并发地执行。

1563375046921
2. 线程

线程是==独立调度==的基本单位。一个进程中可以有多个线程，它们共享进程资源。 如 QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。

线程可以分为用户级线程和内核线程。

1563375068949
3. 进程与线程区别

在 Linux 系统中，进程和线程几乎没有区别。

(1) 资源与调度

进程是==资源分配==的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

线程是==独立调度==的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈段和数据段；线程没有独立的地址空间，它使用相同的地址空间共享数据。

(2) 系统开销

进程在创建、撤销、切换时的开销远大于线程。

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

(3) 通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC（Inter-Process Communication，进程间通信）。

(4) 其他

每个线程都有一个程序计数器（记录要执行的下一条指令）、一组寄存器（保存当前线程的工作变量）、堆栈（记录执行历史）。

4. 协程

协程（Coroutines）是一种比线程更加轻量级的存在，正如一个进程可以拥有多个线程一样，一个线程可以拥有多个协程。

协程不是被操作系统内核所管理的，而是完全由程序所控制，也就是在用户态执行。这样带来的好处是性能大幅度的提升，因为不会像线程切换那样消耗资源。

协程不是进程也不是线程，而是一个特殊的函数，这个函数可以在某个地方挂起，并且可以重新在挂起处外继续运行。所以说，协程与进程、线程相比并不是一个维度的概念。

上下文切换：协程的切换者是用户（编程者或应用程序），切换时机是用户自己的程序所决定的。协程的切换内容是硬件上下文，切换内存保存在用户自己的变量（用户栈或堆）中。协程的切换过程只有用户态，即没有陷入内核态，因此切换效率高。

5. Linux中的进程与线程

Linux 中线程和进程基本没有区别，因为Linux 内核并没有把线程和进程区别对待。

系统调用 fork() 可以新建一个子进程，函数 pthread() 可以新建一个线程。但无论线程还是进程，都是用 task_struct 结构表示的，唯一的区别就是共享的数据区域不同。线程看起来跟进程没有区别，只是线程的某些数据区域和其父进程是共享的，而子进程是拷贝副本，而不是共享。就比如说 mm 结构和 files 结构在线程中都是共享的。

进程与子进程：

进程与线程：

所以多线程程序要利用锁机制，避免多个线程同时往同一区域写入数据，否则可能造成数据错乱。

注意：只有 Linux 系统将线程看做共享数据的进程，不对其做特殊看待，其他的很多操作系统是对线程和进程区别对待的，线程有其特有的数据结构。

对于新建进程时内存区域拷贝的问题，Linux 采用了 copy-on-write 的策略优化，也就是并不真正复制父进程的内存空间，而是等到需要写操作时才去复制。所以 Linux 中新建进程和新建线程都是很迅速的。

进程概述

当一个可执行文件被加载到内存时，这个程序就成为进程。

进程包含内容：程序代码（文本段）、程序计数器、进程堆栈（临时数据如函数参数、返回参数与局部变量等）、数据段（全局变量等），还可能包含堆。

1. 进程控制块
(1) 概述

操作系统使用进程控制块表示每个进程。进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。下图是 PCB 的结构：

image-20200915132859237

它包含多个与特定进程相关的信息：

  • 进程状态：包含新的、就绪、运行、等待、停止等。
  • 程序计数器：表示进程将要执行的下一个指令的地址。
  • CPU 寄存器：中断时记录寄存器的值，这些状态信息与程序计数器需要一起保存，以便进程恢复后能够正确执行。
  • CPU 调度信息：包含进程优先级、调度队列的指针等。
  • 内存管理信息：根据操作系统使用的内存系统，这类信息可以包括基地址和界限寄存器的值、页表或段表等。
  • 记账信息：包括 CPU 使用时间、作业或者进程数量等统计信息。
  • IO 状态信息：包含分配给进程的 IO 设备列表、打开文件列表等。

进程间切换的时候会把进程信息全部保存到 PCB 中，等到 CPU 执行的时候又从 PCB 中重新加载状态。如下图所示为进程间 CPU 的切换过程。

image-20200915132952226

在支持多线程的系统中，PCB 被扩展到包括每个线程的信息。

(2) Linux进程表示

在 Linux 中，线程、进程使用的是相同的核心数据结构。Linux 中进程控制块使用一个 task_struct 结构来表示，包含了大量描述该进程的信息。

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
27
struct task_struct {
    volatile long state;	// 进程的状态!
    unsigned long flags;	// 与管理有关的状态信息
    int prio, static_prio, normal_prio;  // 优先级，静态优先级
    struct list_head tasks;            // 进程链表
    struct list_head ptrace_children;
    struct list_head ptrace_list;
    struct mm_struct *mm, *active_mm;  // 指向进程存储空间的指针
    pid_t pid;                         // 进程的pid
    pid_t tgid;
    struct task_struct *real_parent;    // 真父进程指针
    struct task_struct *parent;         // 父进程指针
    struct list_head children;	        // 子进程链表
    struct list_head sibling;	        // 兄弟进程链表
    struct task_struct *group_leader;	// threadgroup leader
    struct timespec start_time; 		// monotonic time
    struct timespec real_start_time;	// boot based time
    struct thread_struct thread;
    unsigned long rt_priority;          // 实时优先级
    struct fs_struct *fs;               // 进程所在文件目录
    struct files_struct *files;         // 进程打开文件信息
    struct dentry *proc_dentry;         // proc文件的dentry
    struct backing_dev_info *backing_dev_info;
    struct signal_struct *signal;       // 信号
    struct sighand_struct *sighand;
    //...
};

在 Linux 内核中，所有活动进程的表示都采用 task_struct 的双向链表表示。内核采用一个指针 current 指向当前正在执行的进程，通过这个指针就可以修改进程的状态。

image-20200915133041895
2. 进程描述符

用户编译好的那个可执行程序只是一个文件，不是进程，可执行文件必须要载入内存，包装成一个进程才能真正跑起来。进程是要依靠操作系统创建的，每个进程都有它的固有属性，比如进程号（PID）、进程状态、打开的文件等等，进程创建好之后，读入程序之后才被系统执行。

那么，操作系统是如何创建进程的？对于操作系统，进程就是一个数据结构，Linux 的部分源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct task_struct {
    // 进程状态
    long state;
    // 虚拟内存结构体
    struct mm_struct *mm;
    // 进程号
    pid_t pid;
    // 指向父进程的指针
    struct task_struct __rcu *parent;
    // 子进程列表
    struct list_head children;
    // 存放文件系统信息的指针
    struct fs_struct *fs;
    // 一个数组，包含该进程打开的文件指针
    struct files_struct *files;
    //....
};

task_struct 就是 Linux 内核对于一个进程的描述，也可以称为「进程描述符」。其中比较有意思的是 mm 指针和 files 指针。mm 指向的是进程的虚拟内存，也就是载入资源和可执行文件的地方； files 指针指向一个数组，这个数组里装着所有该进程打开的文件的指针。

3. 文件描述符

前面的 files 是一个文件指针数组。一般来说一个进程会从 files[0] 读取输入，将输出写入 files[1]，将错误信息写入 files[2]。

举个例子，C 语言的 printf 函数是向命令行打印字符，但是从进程的角度来看，就是向 files[1] 写入数据；同理 scanf 函数就是进程试图从 files[0] 这个文件中读取数据。

每个进程被创建时，files 指针数组的前三位被填入默认值，分别指向标准输入流、标准输出流、标准错误流。常说的「文件描述符」就是指这个文件指针数组的索引，所以程序的文件描述符默认情况下 0 是输入，1 是输出，2 是错误。见下图（来自 labuladong）。

Linux 中一切都被抽象成文件，设备也是文件，可以进行读和写。一般计算机中输入流是键盘，输出流是显示器，错误流也是显示器，所以现在这个进程和内核连了三根线。因为硬件都是由内核管理的，进程需要通过「系统调用」让内核进程访问硬件资源。

如果写的程序需要其他资源，比如打开一个文件进行读写，这也很简单，进行系统调用，让内核把文件打开，这个文件就会被放到 files 指针数组的第 4 个位置：

到这里输入重定向就很好理解了，程序想读取数据的时候就会去 files[0] 读取，所以只要把 files[0] 指向一个文件，那么程序就会从这个文件中读取数据，而不是从键盘。

同理输出重定向就是把 files[1] 指向一个文件，那么程序的输出就不会写入到显示器，而是写入到这个文件中。

管道符其实也是异曲同工，把一个进程的输出流和另一个进程的输入流接起一条「管道」，数据就在其中传递。

不管是设备、另一个进程、socket 套接字还是真正的文件，全部都可以读写，统一装进一个简单的 files 数组，进程通过简单的文件描述符访问相应资源，具体细节交于操作系统，有效解耦，优美高效。

进程状态

1. 五状态模型
image-20191229210529060
  • 就绪状态（ready）：等待被调度
  • 运行状态（running）
  • 阻塞状态（waiting）：等待资源

应该注意以下内容：

  • 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
  • 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。
2. 进程创建

当一个新进程被创建时，操作系统需要在进程列表中为它创建一个与其他进程格式相同的数据结构用于记录和管理它的状态。通常有四种事件会导致进程的创建：

事件 说明
新的批处理作业 通常位于磁带或者磁盘中的批处理作业控制流程被提供给操作系统。当操作系统准备接纳新工作时，它将读取下一个作业控制命令
交互登陆 终端用户登录到系统
操作系统因为提供一项服务而被创建 操作系统可以创建一个进程，代表用户程序执行的一个功能，使用户无需等待(如控制打印机的进程)
由现有的进程派生 基于模块化的考虑，或者为了开发并行性，用户程序可以指示创建多个进程

当操作系统为另一个进程显式的请求创建一个新进程时，这个动作被称为进程派生。当一个进程派生另一个进程的时候，前一个称作父进程，被派生的叫做子进程。在大多数情况下，父子进程间需要进行通信和合作。

3. 进程结束

进程结束的典型原因如下。

image-20191229210049464

进程调度

进程调度器选择一个可用进程到 CPU 上执行。

1. 调度队列

进程进入操作系统时，会被加入到作业队列中，这个队列包括系统中的所有进程。两种队列：

就绪队列(Ready Queue)：驻留在内存中、就绪的、等待运行的进程保存在就绪队列中，这个队列通常用链表实现，其头结点有两个指针，分别指向链表的第一个和最后一个 PCB 块，每个 PCB 块还包含一个指针，指向就绪队列的下一个 PCB。

设备队列：如果进程执行后需要等待特点事件的发生，比如 IO 请求的完成，那么进程被加入到设备队列中，每个设备都有自己的设备队列，用于保存等待特定 IO 设备的进程列表。如下图中下面的几个都是设备队列，比如磁带单元，终端单元等。

image-20200915133156611

关系：新的进程放到就绪队列，进程执行过程中如果进程可能发出 IO 请求并被放到 IO 队列（属于设备队列）中，IO 完成之后进程再次被放到就绪队列中，重复上述的流程直到进程完成被删除。

image-20200915133310327

2. 调度程序

进程的整个生命周期中会在各种调度队列之间进行迁移，操作系统为了调度必须按一定方式从这些队列中选择进程。进程选择通过调度器或者调度程序来执行。

需要根据进程类型进行调度：IO 密集型进程与 CPU 密集型进程。

3. 上下文切换

中断导致 CPU 从执行当前任务改变到执行内核程序，当中断发生时，系统需要保存当前运行在 CPU 上的进程的上下文，以便在处理后能够恢复上下文，即先挂起进程，再恢复进程。进程上下文存储在进程的 PCB 中，包括 CPU 寄存器的值，进程状态和内存管理信息等。

切换 CPU 到另一个进程需要保存当前进程状态和恢复另一个进程的状态，这个过程为上下文切换。上下文切换的开销是纯粹的时间开销，因为这个时间内啥都没干就是保存进程状态。

进程运行

1. 进程创建

进程在执行过程中可以创建多个新的进程，原来的进程就是父进程，新的进程称为子进程，从而形成一颗进程树。

一般使用进程标识符（PID）来唯一标识进程。比如 Linux 的 init 进程的 pid 就是 1，它是所有用户进程的根进程或父进程。

当进程创建新进程时，可有两种执行可能：

  • 父进程与子进程并发执行。
  • 父进程等待直到某个子进程或全部子进程执行完。

通过系统调用 fork() 创建新进程。新进程的地址空间复制了原来进程的地址空间，这种机制允许父进程与子进程直接轻松通信。对于新进程，系统调用 fork() 返回值为 0，而对于创建这个新进程的 fork() 返回值为新创建子进程的进程标识符 PID。

下图是通过系统调用 fork() 创建进程。

image-20200915134907383

2. 进程终止

父进程可以通过系统调用 wait() 来等待子进程的终止。系统调用 wait() 可以通过参数让父进程获得子进程的退出状态以及子进程的进程标识符 PID，这样父进程就知道是哪个子进程终止了。

当一个进程执行完毕之后，可以通过系统调用 exit() 请求操作系统删除自己，这时候进程终止。这时候进程返回状态值给父进程（通过系统调用 wait()），这样父进程就知道子进程的终止信息。进程终止后所有的进程资源会被操作系统释放。

虽然进程终止后所有的进程资源会被操作系统释放，但是它在进程表中的条目依然存在，直到它的父进程调用了 wait()，这是因为进程表也包含了进程的退出状态。当进程已经终止但是其父进程尚未调用 wait() 系统调用时，这种进程就成为僵尸进程。所有进程终止时都会过渡到这种状态，但是一般而言僵尸只是短暂的存在。一旦父进程调用了 wait() 系统调用，僵尸进程的进程标识符和它在进程表中的条目就会被完全释放。

如果父进程没有调用 wait() 系统调用自己就终止了，那么子进程就变成孤儿进程。 Linux 下会将 init 进程作为孤儿进程的父进程，init 进程会定时调用 wait()，以便收集任何孤儿进程的退出状态，并释放孤儿进程的进程标识符和进程表条目。

进程间通信

1. 概述

IPC 即进程间通信。进程同步与进程通信很容易混淆，它们的区别在于：

  • 进程同步：控制多个进程按一定顺序执行。
  • 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

2. 进程间通信的模型

进程间通信有两个常用模型：消息传递模型与共享内存模型。

image-20200915140808640

消息传递模型：通信的进程通过相互交换消息来传递消息，消息交换可以直接进行也可以通过一个共同的邮箱（如消息队列）来间接进行。可以适用于分布式的系统间进程通信。

共享内存模型：建立一块供协作进程共享的内存区域，进程通过向此共享区域读出或写入数据来交换信息。进程通过系统调用 shared_memory_create() 和 shared_memory_attach() 创建共享内存，并访问其他进程拥有的内存区域。共享内存模型的速度最快。共享内存系统仅在建立共享内存区域时需要进行系统调用，一旦共享内存建立完成，所有的访问都可以作为常规的内存访问，无需借助内核。不过共享内存模型容易出现数据保护与同步方面的问题，即数据不一致的问题。

1. 普通管道

普通管道允许两个进程按标准的生产者-消费者模式进行通信：生产者向管道的一端写，消费者从管道的另一端读。所以普通管道只允许单向通信，如果需要双向通信需要采用两个管道，而每个管道向不同的方向发送数据。

管道是通过系统调用 ==pipe== 函数创建的，并通过文件描述符 int fd[] 来访问，fd[0] 为管道的读出端，fd[1] 为管道的写入端。

1
2
#include <unistd.h>
int pipe(int fd[2]);

Unix 将管道作为一种特殊类型的文件，因此可以用普通的系统调用 read() 和 write() 来访问管道。

普通管道只能被创建它的进程访问。通常父进程创建一个管道，并使用它来与其子进程进行通信（该子进程通过 fork() 创建）。由于子进程继承了父进程的打开文件，而普通管道也是一种特殊的文件，所以子进程也继承了父进程的管道。

普通管道可用于具有亲缘关系进程间的通信，允许一个进程和另一个与它有共同祖先的进程之间进行通信。它具有以下限制：

  • 只支持半双工通信（单向交替传输）。
  • 只能在父子进程中使用。
  • 普通管道仅在进程相互通信时才存在，一旦进程完成通信并且终止了那么普通管道就不存在了。
1563375313528

Unix 命令行下，管道经常用于将一个命令的输出作为另一个命令的输入。

2. 命名管道

命名管道也叫 FIFO，没有了管道只能在父子进程中使用的限制。命名管道克服了管道没有名字的限制，因此除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信，一个典型的场景是一个命名管道有几个写者。

命名管道通过命令 mkfifo 或系统调用 mkfifo 来创建。命名管道在文件系统中有对应的文件名，其表现就类似于文件系统上的一个文件，因此当进程通信完成之后，命名管道将继续存在，直到被显式的删除。通过系统调用 open()、read()、write()、close() 等进行操作。

命名管道虽然运行双向通信，但是是半双工的。

1
2
3
#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

1563375327590
3. 消息队列

消息队列是消息的链表，具有特定的格式，存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取。比 FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字 节流以及缓冲区大小受限等缺。

相比于 FIFO，消息队列具有以下优点：

  • 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难。
  • 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法。
  • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。
4. 信号量

它是一个计数器，用于为多个进程提供对共享数据对象的访问。信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。主要作为进程间以及同一进程不同线程之间的同步手段。

5. 共享内存

允许多个进程共享一个给定的存储区，不同进程可以及时看到对方进程中对共享内存中数据的更新。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。这种方式需要依靠某种同步操作，如互斥锁和信号量等。需要使用信号量用来同步对共享存储的访问。

多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。

6. 套接字

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

Java 提供三种不同类型的套接字。面向连接的 TCP 套接字使用 Socket 类实现的，无连接的 UDP 套接字使用 DatagramSocket 类，最后 MulticastSocket 类是 DatagramSocket 的子类，多播允许数据发送到多个接收者。

进程调度算法

CPU 调度处理的问题是：从就绪队列中选择进程以便为其分配 CPU，如何选择进程就是进程调度算法。不同操作系统的调度算法目标不同，因此需要针对不同系统环境来讨论调度算法。

1. 批处理系统

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

(1) 先来先服务first-come first-serverd（FCFS）

先请求 CPU 的进程首先分配到 CPU，可以通过 FIFO 队列实现。当一个进程进入就绪队列时，这个进程的 PCB 就会被链接到队列尾部。FCFS 算法是非抢占的。

按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，可能造成短作业等待时间过长，同时造成所有进程的平均等待时间较长。

(2) 短作业优先shortest job first（SJF）

按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。最短作业优先算法的平均等待时间是较低的，这个算法真正的困难点是如何知道下次 CPU 执行的长度。

(3) 最短剩余时间优先shortest remaining time next（SRTN）

按估计剩余时间最短的顺序进行调度。

2. 交互式系统

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

(1) 时间片轮转算法

将所有就绪进程按 FCFS (先来先服务)的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

  • 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
  • 而如果时间片过长，那么实时性就不能得到保证。
1563375145745
(2) 优先级调度算法

为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

(3) 多级反馈队列算法

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1, 2, 4, 8 ,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

新就绪的进程总是进入最高优先级队列的队尾，并按 FCFS 原则等待调度；当轮到该进程执行时，若它能在规定的时间片内完成，便可准备撤离系统，否则将其转入第二级队列末尾，再同样按 FCFS 原则等待调度；如果它在第二级队列上运行一个时间片后仍未完成，再依次将它转入第三级队列，……，如此下去，当一个长作业从第一级队列降到最后一级队列时，便在该队列中采取 RR 算法运行。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的==结合==。

1563375163679

UNIX 操作系统采取的便是这种调度算法。

3. 实时操作系统

实时系统要求一个请求在一个确定时间内得到响应。比如 UCOSII。分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。常用调度算法有单调速率调度算法、最早截止期限优先调度算法、比例分享调度算法等。

4. Linux进程调度算法

Linux 内核 V2.6 中，完全公平调度程序（CFS）成为默认的调度算法。Linux 系统的调度基于调度类，每个类都有一个特定的优先级。内核针对不同的调度类采用不同的调度算法，以便满足系统与进程的需要。

每个可运行的任务放置在红黑树上，它的键是基于 vruntime 值的，当一个任务变为可运行的时候，它被添加到树上，当任务变成不可运行时（比如阻塞等待 IO 时），它从树上被删除。一般来说，得到较少处理时间的任务（vruntime 值较小）会偏向树的左侧，得到较多处理时间的任务会偏向树的右侧。

image-20200924162719766

进程同步

进程协作能够通过直接共享逻辑地址空间（即代码和数据）或者通过文件与消息等方式来实现共享。前一种情况能够通过线程实现，然而共享数据的并发访问可能导致数据不一致的问题。

进程同步即控制多个进程按一定顺序执行。

区分两个概念：

  • 同步：多个进程按一定顺序执行。
  • 互斥：多个进程在同一时刻只有一个进程能进入临界区。
1. 临界区

对临界资源进行访问的那段代码称为临界区。当一个进程在临界区内执行时，其他进程不允许在他们的临界区内执行，也就是说没有两个进程能够同时在他它们的临界区内同时执行。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

1
2
3
// entry section
// critical section;
// exit section

临界区问题的解决方案通常有两种：一是基于软件的解决方案，如 Peterson 解决方案，其适用于两个进程交错执行临界区和剩余区，但是基于软件的解决方案并不保证能够在现代计算机体系结构上正确工作。另一种方案是基于硬件同步的解决方案，典型的代表是通过加锁来保护临界区，使用 CAS 硬件指令来解决临界区问题。

2. 互斥锁

临界区问题的基于硬件的解决方案不但复杂而且不能为程序员直接使用。因此操作系统构造了相关的软件工具，最简单的就是互斥锁。可以用互斥锁保护临界区，从而防止竞争条件。一个进程在进入临界区时应该获取到锁，它在退出临界区是释放锁。

互斥锁可以通过 acquire() 获取锁和 release() 释放锁，每个互斥锁都有一个布尔类型的变量 available 表示锁是否可用。

3. 信号量

信号量通常用于控制访问具有多个实例的某种资源。信号量的初值为可用资源数量。

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

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

wait 和 signal 等对于整型变量的操作需要是原子的，不能分割，通常的做法是在执行这些操作的时候屏蔽中断。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

使用==信号量==实现生产者-消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

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
27
#define N 100
typedef int semaphore;	// semaphore 信号量
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}
4. 管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。信号量机制的不足：编写困难，易出错，所以才出现了管程。管程是一种高级的同步工具，算是一种数据结构。

进程与管程的关系：进程只能通过调用管程中的过程来间接的访问管程中的数据结构。

c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

使用==管程==实现生产者-消费者问题：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;
5. 经典同步问题
(1) 读者-写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

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
typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}
(2) 哲学家进餐问题
image-20200924152352247

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

下面是一种错误的解法，考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。

1
2
3
4
5
6
7
8
9
10
11
12
#define N 5

void philosopher(int i) {
    while(TRUE) {
        think();
        take(i);       // 拿起左边的筷子
        take((i+1)%N); // 拿起右边的筷子
        eat();
        put(i);
        put((i+1)%N);
    }
}

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

  • 必须同时拿起左右两根筷子；
  • 只有在两个邻居都没有进餐的情况下才允许进餐；
  • 最多允许 4 个哲学家同时坐在桌子上。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think();
        take_two(i);
        eat();
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    test(i);
    up(&mutex);
    down(&s[i]);
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);
    test(RIGHT);
    up(&mutex);
}

void test(i) {         // 尝试拿起两把筷子
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

线程

1. 概述

每个线程是 CPU 使用的一个基本单元，它包括线程 ID、程序计数器、寄存器组和堆栈。它与同一个进程的其他线程共享代码段、数据段与其他操作系统资源，如打开文件和信号等。下图是多线程进程。

image-20200924094449070
2. 多线程模型

线程分为用户线程与内核线程。用户线程位于内核之上，它的管理无需内核支持，而内核线程由操作系统支持与管理。用户线程与内核线程之间必然存在某种关系。

多对一模型：多个用户线程映射到一个内核线程。

一对一模型：每个用户线程映射到一个内核线程。

多对多模型：多路复用多个用户级线程到同样数量或者更少数量的内核线程。

3. 线程同步

线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。操作系统一般有下面三种线程同步的方式：

  1. 信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。就像 JDK 中的 Semphare 类。
  2. 互斥量(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。互斥量是信号量的一种特殊形式。
  3. 事件(Event) : Wait/Notify 机制，通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

死锁

当一个进程申请资源时，如果这时候资源不可用，那么进程进入等待状态。有时候如果申请的资源被其他的等待进程所占有，那么该等待进程就有可能再也无法改变状态，这就产生死锁。

正常情况下资源访问步骤：申请、使用、释放。

1. 死锁的特征
(1) 死锁的必要条件
1563375370357

发生死锁的四个必要条件：

  1. 互斥条件：一个资源在任意一个时刻只能由一个进程使用。
  2. 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
  3. 不可抢占条件：线程已获得的资源在末使用完之前不能被其他线程强行剥夺，只有自己使用完毕后才释放资源。
  4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

这四个条件必须同时成立才能形成死锁。

(2) 资源分配图

系统资源分配图可以更精确的描述死锁，它是一个有向图。其中进程为 P，资源为 R。P → R 说明进程正在申请这个资源，R → P 说明这个资源的一个实例已经分配给了这个进程。

如果资源分配图没有环，那么就没有进程死锁，如果分配图有环，那么可能存在死锁（不是一定）。如果一个资源只有一个实例，那么如果有环就肯定出现死锁了；如果一个资源有多个实例，即使存在环也不一定存在死锁（如下右图）。

image-20200924152810480
2. 死锁处理方法

处理死锁主要有以下几种方法：

  • 死锁预防

  • 鸵鸟策略

  • 死锁检测

  • 死锁恢复

  • 死锁避免

3. 死锁预防

在程序运行之前预防发生死锁。避免死锁只要破坏产生死锁的四个条件中的其中一个就可以了。

(1) 破坏互斥条件

这个条件没有办法破坏，因为用锁本来就是想让他们互斥的（临界资源需要互斥访问）。

(2) 破坏请求与保持条件

一次性申请所有的资源。

(3) 破坏不可抢占条件

占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源。

(4) 破坏环路等待

靠按序申请资源来预防。按某一顺序申请资源，释放资源则反序释放。破坏循环等待条件。

4. 鸵鸟策略

把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

5. 死锁检测

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

(1) 每种类型一个资源的死锁检测
1563375435171

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过==检测有向图是否存在环==来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

(2) 每种类型多个资源的死锁检测
1563375453688

上图中，有三个进程四个资源，每个数据代表的含义如下：

  • E 向量：资源总量。
  • A 向量：资源剩余量。
  • C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量。
  • R 矩阵：每个进程请求的资源数量。

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

  1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
  2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
  3. 如果没有这样一个进程，算法终止。
6. 死锁恢复
  • 利用抢占恢复。
  • 利用回滚恢复。
  • 通过杀死进程恢复。
7. 死锁避免

在程序运行时避免发生死锁。

(1) 安全状态
1563375488859

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使所有进程都能成功运行，因此可以称图 a 所示的状态是安全的。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

(2) 单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

1563375577700

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

(3) 多个资源的银行家算法
1563375616191

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

  • 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
  • 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
  • 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

参考资料

  • 协程：jianshu.com/p/6dde7f92951e
  • labuladong文章：Linux的进程、线程、文件描述符是什么