进程管理 | OS

进程与线程

进程的概念和特征

程序顺序执行的特征

顺序性

严格按序。
封闭性

程序一旦开始运行，其结果不受外界因素影响。

程序运行时独占各种资源，这些资源的状态（除初始状态外）只有本程序才能改变。
可再现性

只要初始条件和执行环境相同。

程序并发执行的特征

间断

程序间相互制约关系导致走走停停。
失去封闭性

资源是共享的。

并发进程共享变量，其执行结果与速度有关。
不可再现性

失去封闭性导致的。

为使进程在并发运行时虽具有异步性，但仍能保证执行结果是可再现的，操作系统配置了相应的进程同步机制。

引入进程的目的

深刻描述程序动态执行过程的性质乃至更好地支持和管理多道程序的并发执行，提高资源利用率和系统吞吐量，实现操作系统的并发性和共享性（最基本的两个特性）。

进程的概念

程序的一次执行过程。

一个程序及其数据在处理机上顺序执行时所发生的活动。

具有独立功能的程序在一个数据集合上运行的过程。

进程实体的运行过程，系统进行资源分配和调度的一个独立单位。

“动态的”、“过程性的”。

进程映像/进程实体（组成）

程序段
相关数据段

原始数据、中间数据、结果数据。
进程控制块 PCB (Process Control Block)

进程存在的唯一标志。

常驻内存，任意时刻都可存取，并在进程结束时删除。

进程实体的一部分。

系统通过控制 PCB 来控制进程。

当进程被创建时，系统为它申请和构造一个相应的 PCB。

撤销进程，实际上是撤销进程的 PCB。

😚进程映像是静态的，进程是进程实体的运行过程。

进程的特征

动态性（最基本特征）

具有一定的生命周期，是动态地产生、变化和消亡的。
并发性

多个进程实体同时存于内存中，能在一段时间内同时运行。

引入进程的目的就是使程序能与其他程序并发执行，以提高资源利用率。
独立性

可独立调度和分派的基本单位（未引入线程的传统操作系统）。

系统进行资源分配的基本单位（根据 PCB）。
异步性

由于进程的相互制约，使得进程具有执行的间断性。

进程以各自独立的、不可预知的速度向前推进。

为使进程在并发运行时虽具有异步性，但仍能保证执行结果是可再现的，操作系统配置了相应的进程同步机制。
结构性

进程实体/进程映像(静态) = 程序段 + 数据段 + 进程控制块 PCB。

进程 vs 程序

进程动态，程序静态。进程是程序的执行，程序是有序代码的集合。
进程暂时，程序永久。
组成不同。
通过多次执行，一个程序可以产生多个不同的进程。

一个程序的一次执行可产生多个进程（例如创建子进程）。

通过调用关系，一个进程可以执行多个程序，只要在执行过程中改变其 CPU 状态和内存空间即可。

进程可创建其他进程，而程序不能形成新的程序。
进程具有并行特性（独立性、异步性），程序没有。

进程的组成

进程控制块 PCB

由操作系统在进程创建时新建，之后常驻内存，任一时刻可以存取，在进程结束时删除。

进程实体的一部分；进程存在的唯一标志。

主要内容

常用组织方式

线性方式

将所有 PCB 都组织在一张线性表中（即数组），将该表的首址存放在内存的一个专用区域中。

适合进程数目不多的系统。
链接方式

把具有相同状态进程的 PCB 通过 PCB 中的链接指针链接成一个队列。

队内通常按优先级高低进行排列。

可以形成就绪队列、若干个阻塞队列（阻塞原因不同）和空白队列等。

索引方式

将同一状态的进程组织在一个索引表中，索引表的表项指向相应的 PCB，不同状态对应不同的索引表。

PCB 的作用

当操作系统欲调度某进程运行时，要从该进程的 PCB 中查出其现行状态及优先级；

在调度到某进程后, 要根据其 PCB 中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其 PCB 中的程序和数据的内存始址，找到其程序和数据；

进程在运行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也需要访问 PCB；

当进程由于某种原因而暂停运行时，又需将其断点的处理机环境保存在 PCB 中。

可见，在进程的整个生命期中，系统总是通过 PCB 对进程进行控制，亦即系统唯有通过进程的 PCB 才能感知到该进程的存在。

关于寄存器上下文的保存（到底是在内核栈还是 PCB）

内核栈底部的数据结构 pt_regs 用于存放用户态的寄存器上下文。IA-32 的 pt_regs 定义如下：

c++

struct pt_regs {
    long ebx;
    long ecx;
    long edx;
    long esi;
    long edi;
    long ebp;
    long eax;
    int xds;
    int xes;
    long orig_eax;
    long eip;
    int xcs;
    long eflags;
    long esp;
    int xss;
};

task_struct（即 PCB）的成员 thread，类型为 thread_struct，包含了部分寄存器内容和其他信息，用于进程切换时（已处于内核态）保存和恢复部分寄存器上下文，以及更新新进程 TSS 中的内核栈指针 esp0 和 I/O 操作权限位图 io_bitmap。这部分寄存器包括浮点寄存器、调试寄存器（挂起前有使用过的话）以及两个段寄存器 FS 和 GS。

进程切换时必定处于内核态，此时用户态的所有寄存器上下文已被中断/异常/系统调用处理程序保存在内核栈/中断栈中。进程在进入内核态后到进行进程切换前的这段时间，可能使用到的一些寄存器内容也都基本上被压入内核栈保存。所以说用 thread（PCB）保存和恢复的寄存器上下文很少。不过在即将进程切换时（新旧进程的内核栈切换），thread 还会被用来对内核栈栈顶指针（thread.esp）以及手动设置的返回地址（thread.eip）进行保存和恢复。

以上实现基于 Linux + IA-32 平台，显然在该实现中寄存器上下文或者说现场信息的保存和恢复都是基于内核栈完成的，但是很多地方又说是保存在 PCB 中。如果说内核栈是属于 PCB 的一部分那还说得过去。

另外，中断/异常处理时寄存器上下文（除了硬件压栈的断点和 PSW）还可能保存在中断栈中，这要看具体平台的实现（x86 的中断栈独立于内核栈，且每个处理器都会有一个；ARM 上中断栈和内核栈是共享的）。

最后，要注意，进程上下文不只是寄存器上下文，除了寄存器上下文的进程上下文还是要靠 PCB 进行保存和恢复的。

程序段

程序段就是能被进程调度程序调度到 CPU 执行的程序代码段。

⚠程序可被多个进程共享，即多个进程运行同一个程序。

数据段

可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

🌱C 语言内存结构

正文段：二进制代码、常量（包括全局赋值变量）。

数据堆段：动态分配的存储区。

数据栈段：临时使用的变量。

进程的状态与转换

基本状态

就绪态

进程获得了除处理机外的一切所需资源。

就绪队列：处于就绪态的进程可能有多个。

单处理机中所有进程不可能都处于就绪态（有一个会去运行）。

就绪队列也可以有一个或多个（多级队列调度算法）。
运行态

进程正在处理机上运行。

单处理机每个时刻只有一个进程处于运行态。
阻塞态/等待态

进程正在等待某一事件（不包括等待处理机为可用）而暂停运行，即使 CPU 空闲。

同样存在阻塞队列，可能会根据阻塞原因的不同设置多个阻塞队列。

就绪态可视为特殊的阻塞态，即处于就绪态的进程缺少且仅缺少处理机这资源。“资源” 可以理解为，可以使用某设备、让其提供服务的 “时间”。

之所以将 CPU 和其他资源分开，是因为在分时系统的时间片轮转机制中，进程得到 CPU 的时间很短且非常频繁地转换到就绪态；而其他资源的使用和分配或某一事件的发生对应的事件相对来说很长，进程转换到阻塞态的次数也相对较少，这样来看，就绪态和阻塞态是进程生命周期中两个完全不同的状态。

创建态和结束态

创建态

进程正在被创建，尚未转到就绪态。

创建进程步骤：申请空白 PCB、向 PCB 填写用于控制和管理进程的信息、分配运行时所必需的资源、将该进程转入就绪态并插入就绪队列。
终止态

进程正从系统消失，可能是进程正常结束或其他原因退出运行。

系统先将进程置为结束态，然后进一步处理资源释放和回收等工作

五种状态的转换

就绪态 → 运行态

被动，进程被调度，获得处理机资源。
运行态 → 就绪态

时间片到（主动）；被剥夺（被动）。
运行态 → 阻塞态

主动，进程请求某一资源的使用和分配或等待某一事件的发生时。

进程以系统调用的形式请求操作系统提供服务，这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式。
阻塞态 → 就绪态

被动，需要其他相关进程的协助，由中断处理程序将状态从阻塞态转换为就绪态。

只有从运行态才能到终止态？

挂起态

将暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态。

进程控制

创建

创建形式

父进程创建子进程。

子进程可以继承父进程所拥有的资源。父进程可与子进程共享一部分资源，但不能共享虚拟地址空间。

子进程被撤销，归还资源给父进程/操作系统；父进程被撤销，其所有的子进程被撤销。

进程图/树

0 号进程（Linux）：由系统创建的第一个进程唯一一个没有通过 fork 或者 kernel_thread 产生的进程。其拥有的所有信息和资源都是 “手工设置”，不是复制的。

引起进程创建的典型事件

终端用户登录系统
作业调度/高级调度
系统提供服务
用户程序的应用请求

前三种都是系统内核为用户创建一个新进程。

创建过程

即创建原语 create() 的执行过程：

分配一个唯一的进程标识符，并申请一个空白的 PCB

PCB 有限，申请失败则创建失败。
分配运行时所需资源

包括各种物理和逻辑资源，如内存、文件、I/O 设备和 CPU 时间等（在 PCB 中体现）。

资源来源：操作系统（可能不需要）、父进程。

资源不足则继续处于创建态，等待资源。
初始化 PCB

主要包括初始化标识信息、初始化处理机状态信息、初始化处理机控制信息，以及设置进程优先级等。
若进程就绪队列能够接纳新进程，则将新进程插入就绪队列。

终止

引起进程终止的主要事件

正常结束

进程的任务已完成并准备退出运行。
异常结束

发生某种异常（如终止异常、不可恢复的故障异常）使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O 故障等。
外界干预

进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求、父进程终止。

终止过程

即终止原语 destroy() 的执行过程：

根据 PID 检索 PCB，读出该进程状态。
若为运行态，则立即终止，将处理机资源分配给其他进程。
终止所有子孙进程（若有），以防它们成为不可控的进程（有些系统无此要求）。
归还拥有的全部资源给父进程/操作系统。
将该 PCB 从所在队列（链表）删除。

阻塞和唤醒

阻塞的引发

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新任务可做等，进程便主动⚠调用阻塞原语，使自己由运行态变为阻塞态。

阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程才可能将其转为阻塞态。

阻塞过程

即阻塞原语 block() 的执行过程：

根据 PID 找到 PCB。
若为运行态，则保护其现场，状态转为阻塞态，停止运行。
把该 PCB 插入相应事件的等待队列。
转调度程序进行重新调度，将处理机资源分配给另一就绪进程。

唤醒的引发

当被阻塞进程所期待的事件发生时。

唤醒过程

即唤醒原语 wakeup() 的执行过程（由事件有关进程调用）：

在该事件的等待队列中找到相应进程的 PCB。
将其移出等待队列，状态置为就绪态。
把该 PCB 插入就绪队列，等待调度程序调度。

block 原语和 wakeup 原语作用相反，必须成对使用。即若在某进程中调用了阻塞原语，则必须在与之相合作的或其他相关的进程中安排一条相应的唤醒原语，否则阻塞进程将永久阻塞，再无机会运行。

🍀进程创建、撤销以及要求由系统设备完成的 I/O 操作都是利用系统调用而进入内核，再由内核中相应处理程序予以完成；进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

进程间通信

进程间通信 IPC (InterProcess Communication) 是指进程之间的信息交换。

进程互斥与同步需要在进程间交换一定的信息，这只能称为低级进程通信。以信号量机制（PV 操作）为例，之所以低级是在于：

效率低。生产者每次只能向缓冲池投放一个产品（消息），消费者每次只能从缓冲区取得一个消息；
通信对用户不透明。OS 只为进程之间的通信提供了共享存储器，而关于进程之间通信所需之共享数据结构的设置、数据的传送、进程的互斥和同步，都必须由程序员去实现。

高级通信方式是指以较高的效率传输大量数据且使用方便的通信方式。主要有以下三类：

共享存储

通信进程间存在一块可直接访问的共享空间，通过对这片共享空间进行读写实现信息交换。

对共享空间进行读写操作时需使用同步互斥工具（如 PV 操作）。

操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。

用户进程空间一般都是独立的，进程运行期间一般不能直接访问其他进程的空间，要想让两个用户进程共享空间，必须通过特殊的系统调用实现。

共享存储又分为两种：

基于共享数据结构的通信方式

操作系统仅提供共享存储器，由程序员负责对公用数据结构的设置及对进程间同步的处理。

通信效率低下，仅适于传递相对少量的数据，属于低级通信。

如在生产者-消费者问题中的有界缓冲区。
基于共享存储区的通信方式

OS 在内存中划出一块共享存储区，数据的形式、位置甚至访问控制都是由进程负责，而不是 OS。

需要通信的进程在通信前，先向系统申请获得共享存储区中的一个分区，并将其附加到自己的地址空间中，便可对其中的数据进行正常读写。读写完成或不再需要时，将其归还给共享存储区。

消息传递

不必借助任何共享存储区或数据结构，而是以格式化的消息(Message)为单位，将通信的数据封装在消息中，并利用操作系统提供的发送消息和接收消息两个原语，在进程间进行消息传递，完成进程间的数据交换。

该方式隐藏了实现细节，通信过程对用户透明，降低了通信程序设计的复杂性和错误率，成为当前应用最为广泛的一类进程间通信的机制。例如：计算机网络中的报文；在微内核操作系统中，微内核与服务器之间的通信。

由于该机制能很好地支持多处理机系统、分布式系统和计算机网络，因此也成为这些领域最主要的通信工具😎。

消息传递也有两种：直接通信方式、间接通信方式/信箱通信方式。都属于高级通信方式。

直接通信方式

发送进程利用 OS 所提供的发送原语，直接把消息发送给目标进程。

发送进程直接把消息发送到接收进程的消息缓冲队列（位于内核空间，由 PCB 保存指向该队列的指针）。

🌱直接消息传递系统实例——消息缓冲队列通信机制

消息缓冲队列通信机制广泛应用于本地进程之间的通信中。在这种通信机制中，发送机制利用 Send 原语将消息直接发送给接收进程；接收进程则利用 Receive 原语接收消息。

消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区（队列），位于内核。

在 OS 采用了消息缓冲队列通信机制时，除了需要为进程设置消息缓冲队列外，还应在进程的 PCB 中增加消息队列队首指针，用于对消息队列进行操作，以及用于实现同步的互斥信号量 mutex 和资源信号量 sm。

发送进程在利用发送原语发送消息之前，应现在自己的内存空间设置一发送区 a，如下图所示，把带发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标（接收）进程。发送原语首先根据发送区 a 中所设置的消息长度 a.size 来申请一缓冲区 i，接着把发送区 a 中的信息复制到缓冲区 i 中。为了能将 i 挂在接受进程的消息队列 mq 上，应先获得接收进程的内部标识符 j，然后将 i 挂在 j.mq 上。由于 j.mq 队列属于临界资源，故在执行 insert 操作的前后都要执行 wait 和 signal 操作。

发送原语可描述如下：

c++

// receiver为接收进程标识符,a为发送区首址
void send(receiver, a) {
    getbuf(a.size, i);  // 根据a.size申请缓冲区
    copy(i.sender, a.sender);  // 将发送区a中的信息复制到消息缓冲区i中
    i.size = a.size;
    copy(i.text, a.text);
    i.next = 0;
    getid(PCBset, receiver.j);  // 获得接收进程内部的标识符
    wait(j.mutex);
    insert(&j.mq, i);  // 将消息缓冲区插入消息队列
    signal(j.mutex);
    signal(j.sm);
}

接收进程调用接收原语 receive(b)，从自己的消息缓冲队列 mq 中摘下第一个消息缓冲区 i，并将其中的数据复制到以 b 为首址的指定的消息接收区内。接收原语描述如下：

c++

void receive(b) {
    j=internal name;  // j为接收进程内部的标识符
    wait(j.sm);
    wait(j.mutex);
    remove(j.mq, i);  // 将消息队列中第一个消息移出
    signal(j.mutex);
    copy(b.sender, i.sender);  // 将消息缓冲区i中的信息复制到接收区b
    b.size = i.size;
    copy(b.text, i.text);
    releasebuf(i);  // 释放消息缓冲区
}

间接通信方式/信箱通信方式

发送和接收进程，都通过共享中间实体（称为信箱）的方式进行消息的发送和接收，完成进程间的通信。

信箱建立在随机存储器的公用缓冲区上，用来暂存发送进程发送给目标进程的消息。

消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。因此，利用信箱通信方式既可实现实时通信，又可实现非实时通信。

信箱定义为一种数据结构，在逻辑上可将其分为信箱头（有关信箱的描述信息，如信箱标识符、信箱拥有者等）和信箱体（由若干可以存放消息的信箱格组成）两个部分。

系统为信箱通信提供了若干条原语，分别用于信箱的创建和撤销、消息的发送和接收。

信箱可由操作系统创建，也可由用户创建，创建者是信箱的拥有者。据此可把邮箱分为私用邮箱（进程创建，类似消息队列）、公用邮箱（操作系统创建，在系统运行期间始终存在）、共享邮箱（进程创建，须指出可共享进程）。

在利用邮箱通信时，在发送进程和接收进程之间，存在以下四种关系：

一对一关系。发送进程和接收进程可以建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。
多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互。
一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式向接收者（多个）发送消息。
多对多关系。允许建立一个公用邮箱，让多个进程都能向邮箱中投递消息；也可从邮箱中取走属于自己的消息。

信箱通信方式广泛应用于计算机网络。

管道通信

管道通信是消息传递的一种特殊方式，也可以理解为共享存储的优化和发展。

管道（pipe 文件）

所谓 “管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名 pipe 文件。

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

管道实际上是一个固定大小的缓冲区。

利用管道进行通信

发送进程以字符流形式⚠将大量数据送入管道。
接收进程的读是一次性操作，读取即从管道抛弃。
数据在管道中先进先出。
只要管道非空，读进程就能从管道中读出数据；只要管道不满，写进程就能往管道中写入数据。
管道通信必然是半双工通信⚠。

管道机制必须提供的协调能力

为了协调双方通信，管道机制必须提供：

互斥

一个进程对管道进行读/写操作时，其他进程必须等待。
同步

写进程向管道写入一定数量的数据后，写进程阻塞，直到读进程取走数据后才将其唤醒。

读进程将管道中的数据取空后，读进程阻塞，直到写进程将数据写入管道后才将其唤醒。
确定对方的存在

管道和一般文件的不同

管道大小受限制，防止不加检验地增长。

当写进程比读进程工作得快，管道变满时，写满管道将默认地被阻塞，直到某些数据被读取
当读进程比写进程工作得快，管道变空时，读空管道将默认地被阻塞，等待某些数据被写入，而不是一读就直接返回 0（返回文件结束）。

管道只能由创建进程所访问

子进程会继承父进程的打开文件，而管道是一种特殊的文件，子进程自然会继承父进程的管道，并使用它来与父进程通信。

因此普通管道只能用于具有共同祖先的进程（具有亲缘关系的进程）之间通信。

🐚命名管道 FIFO 允许无亲缘关系的进程访问，不同于 PIPE 管道之处在于它提供一个路径名与之关联，以文件形式存放于文件系统中（即存储在磁盘上）。

信号

Linux 信号是一种更高层的软件形式的异常，它允许进程和内核中断其他进程。

一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件。

每种信号类型都对应于某种系统事件。低层的硬件异常是由内核异常处理程序处理的，正常情况下，对用户进程而言是不可见的。信号提供了一种机制，通知用户进程发生了这些异常，比如：

如果一个进程试图除以 0，那么内核就发送给它一个 SIGFPE 信号（序号 8）
如果一个进程执行一条非法指令，那么内核就发送给它一个 SIGILL 信号（序号 4）
如果进程进行非法内存引用，内核就发送给它一个 SIGSEGV 信号（序号 11）

其他信号对应于内核或者其他用户进程中较高层的软件事件。比如：

如果当进程在前台运行时键入 Ctrl + C，那么内核就会发送一个 SIGINT 信号（序号 2）给这个前台进程组中的每个进程。
一个进程可以通过向另一个进程发送一个 SIGKILL 信号（序号 9）强制终止它。
当一个子进程终止或者停止时，内核会发送一个 SIGCHLD 信号（序号 17）给父进程。

异常处理中的信号

在 IA-32 + Linux 中的异常处理程序的处理阶段，大部分异常处理函数会把硬件出错码和类型号保存在发生异常的当前进程的描述符中（即 PCB），然后向当前进程发送一个对应的信号。异常处理结束时，内核将检查是否发送过某种信号给当前进程。若没有发送，则进入恢复阶段；若发送过信号，则强制当前进程接收信号，而异常处理结束。当前进程接收到一个信号后，若有对应的信号处理程序，则转到信号处理程序执行，执行结束后，返回到当前进程的逻辑控制流的断点处继续执行；若没有对应的信号处理程序，则调用内核的 abort 例程终止当前进程。

Linux 采用向发生异常的进程发送信号的机制实现异常处理，其主要出发点是尽量缩短在内核态的处理时间，尽可能把异常处理过程放在用户态下的信号处理程序中进行。用信号处理程序来处理异常，使得用户进程有机会捕捉并自定义异常处理方法。实际上，各种高级编程语言（如 C++）中的运行时环境的异常处理机制就是基于信号处理来实现的。如果异常全部由内核来处理，那么高级编程语言的异常处理机制就无法实现。

信号的传送

传送一个信号到目的进程是由两个不同步骤组成的：

发送信号

内核通过更新目的进程上下文中的某个状态，发送（递送）一个信号给目的进程。

发送信号可以有如下两种原因：

1）内核检测到一个系统事件，比如除零错误或者子进程终止。

2）一个进程调用相关函数，显式地要求内核发送一个信号给目的进程。一个进程可以发送信号给它自己。
接收信号

当目的进程被内核强迫以某种方式对信号的发送做出反应时，它就接收了信号。进程可以忽略这个信号，终止或者通过执行一个称为信号处理程序的用户层函数捕获这个信号。下图给出了信号处理程序捕获信号的基本思想。

待处理信号

一个发出而没有被接收的信号叫做待处理信号(pendingsignal)。在任何时刻，一种类型至多只会有一个待处理信号。如果一个进程有一个类型为 k 的待处理信号，那么任何接下来发送到这个进程的类型为 k 的信号都不会排队等待，它们只是被简单地丢弃。

一个进程可以有选择性地阻塞接收某种信号。当一种信号被阻塞时，它仍可以被发送，但是产生的待处理信号不会被接收，直到进程取消对这种信号的阻塞。

一个待处理信号最多只能被接收一次。内核为每个进程在 pending 位向量中维护着待处理信号的集合，而在 blocked 位向量中维护着被阻塞的信号集合。只要传送了一个类型为 k 的信号，内核就会设置 pending 中的第 k 位，而只要接收了一个类型为 k 的信号，内核就会清除 pending 中的第 k 位。

信号的发送方式（进程主动）

用 /bin/kill 程序发送信号
shell
1
linux> /bin/kill -9 15312
从键盘发送信号

在键盘上输入 Ctrl+C 会导致内核发送一个 SIGINT 信号到前台进程组中的每个进程。默认情况下，结果是终止前台作业；

类似地，输入 Ctrl+Z 会发送一个 SIGTSTP 信号到前台进程组中的每个进程。默认情况下，结果是停止（挂起）前台作业。
用 kill 函数发送信号

进程通过调用 kill 函数（通过 kill 系统调用实现）发送信号给其他进程（包括它们自己）。
c
1
2
3
#include <sys/types.h>
#include <signal.h>
int kill(pid_t pid, int sig); // 成功返回0,错误返回1
用 raise 函数发送信号

进程通过调用 raise 函数（通过 raise 系统调用实现）发送信号给它自己。

调用 raise(signo) 等价于调用 kill(getpid(), signo)。
用 alarm 函数发送信号

进程可以通过调用 alarm 函数向它自己发送 SIGALRM 信号。
c
1
2
#include <unistd.h>
unsigned int alarm(unsigned int secs);
alarm 函数安排内核在 secs 秒后发送一个 SIGALRM 信号给调用进程。

注意，并不是系统中所有进程都可以向其他进程发送信号，只有核心和超级用户可以。普通进程只可以向拥有相同用户标识号 uid 和组标识号 gid 或者在相同进程组中的进程发送信号。

信号的接收与处理

当内核把进程 p 从内核模式切换到用户模式时（例如，从系统调用返回或是完成了一次上下文切换），它会检查进程力的未被阻塞的待处理信号的集合。如果这个集合为空（通常情况下），那么内核将控制传递到 p 的逻辑控制流中的下一条指令；如果集合是非空的，那么内核选择集合中的某个信号 k（通常是最小的 k），并且强制 p 接收信号 k。收到这个信号会触发进程采取某种行为，一旦进程完成了这个行为，那么控制就传递回 p 的逻辑控制流中的下一条指令。

进程收到信号后采取的行为有：

执行信号的默认操作

每个信号类型都有一个预定义的默认行为，是下面的一种：

① 进程终止
② 进程终止并转储内存（把代码和数据内存段的映像写到磁盘上）
③ 进程停止（挂起）直到被 SIGCONT 信号重启
④ 进程忽略该信号

但有两种信号不能被忽略：SIGKILL 和 SIGSTOP。这样做的原因是系统管理员需要能够杀死或停止进程的权利。
使用 signal 函数修改和信号相关联的默认行为（捕获并处理信号）
c
1
2
3
4
#include<signal.h>
typedef void(*sighandler_t)(int);

sighandler_t signal(int signum,sighandler_t handler);
如果 handler是 SIG_IGN，那么忽略类型为 signum 的信号；如果 handler 是 SIG_DFL，那么类型为 signum 的信号行为恢复为默认行为；否则，handler 就是用户定义的函数的地址，这个函数被称为信号处理程序，只要进程接收到一个类型为 signum 的信号，就会调用这个程序。通过把处理程序的地址传递到 signal 函数从而改变默认行为，这叫做设置信号处理程序。调用信号处理程序被称为捕获信号，执行信号处理程序被称为处理信号。

信号处理程序可以被其他信号处理程序中断。

同样地，SIGSKILL 和 SIGSTOP 的默认行为也是不能修改的。

Linux 支持的典型信号

SIGCHLD：当进程终止或停止时，内核会给进程的父进程发送此信号。在默认的情况下 SIGCHLD 是被忽略的，如果进程对它们的子进程是否存在感兴趣，那么进程必须显式地捕获并处理该信号。

SIGFPE：该信号代表所有的算术异常，且不仅仅指浮点数运算相关的异常，异常包括溢出、下溢和除以 0。默认的操作是终止进程并形成内存转储文件，但进程可以捕获并处理该信号。

SIGILL：当进程试图执行一条非法机器指令时，内核会发送该信号。默认操作是终止进程并进行内存转储进程可以选择捕获并处理 SIGILL。

SIGINT：当用户输入中断符（通常是 Ctr + C）时，该信号被发送给所有前台进程组中的进程。默认的操作是终止进程。进程可以选择捕获并处理该信号，通常是为了在终止前进行清理工作。

线程概念和多线程模型

基本概念

引入线程的目的

减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

进程 “太重”，在创建、撤销和切换中，系统要为之付出较大的时空开销。

不把可独立调度和分派的基本单位同时也作为系统进行资源分配的基本单位。

线程的主要属性

独立运行/调度的基本单位（多线程操作系统）、基本的 CPU 执行单元、程序执行流的最小单元。

线程处于 “执行” 状态 = 该进程的某线程正在执行。

线程是一个轻型实体。

不拥有系统资源，但应有一个唯一的标识符和一个线程控制块。

线程控制块记录线程执行的寄存器和栈等现场状态。
不同的线程可以执行相同的程序。
同一进程中的各个线程共享该进程所拥有的资源。

进程的代码段、进程打开的文件、进程的全局变量等都是进程的资源，可以共享；唯有进程中某线程的栈指针（包含在线程 TCB 中）是属于线程的，对其他线程透明。
线程是处理机的独立调度单位，可并发执行。
具有生命周期。

线程也有就绪、阻塞和运行三种基本状态，三者之间的转换与进程基本状态之间的转换一致。

一个线程可以创建和撤销另一个线程。

线程 vs 进程

定位

线程 —— 独立调度的基本单位（处理机的分配单元）。

进程 —— 拥有资源的基本单位（除 CPU 外的系统资源的分配单元）。
资源

线程本身不拥有系统资源（只有一点必不可少、能保证独立运行的资源）。

要知道，若线程也是拥有资源的单位，则切换线程就需要较大的时空开销，线程这个概念的提出就没有意义。

线程可以访问其隶属进程的系统资源，主要表现在属于同一进程的所有线程都具有相同的地址空间。

在每个线程中都应具有用于控制线程运行的线程控制块 TCB、用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。
独立性

每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。

线程没有自己独立的地址空间，于同一进程的所有线程都具有相同的地址空间。

每个线程都可以访问它们所属进程地址空间中的所有地址，一个线程的堆栈可以被同一进程的其他线程读写，甚至完全清除，由一个线程打开的文件可以供同一进程的其他线程读写。因为同一进程中的不同线程往往是为了提高并发性以及进行相互之间的合作而创建的。

某进程内的线程对其他进程不可见。
并发性

同一进程、不同进程的线程都能并发执行，这使得操作系统具有更好的并发性。

多线程进程可将多个线程分配到多处理机上执行。

原先多个任务分别由多个进程负责，现在让一个进程的多个线程负责，进程间并发 → 进程内并发，减少进程切换。
系统开销

线程创建、撤销和切换的开销远小于进程（只涉及少量寄存器）。

同一进程的线程间同步和通信非常容易实现：由于共享进程的地址空间，可以直接读/写进程数据段（如全局变量）来进行通信，无需同步和互斥手段的辅助。

在一些操作系统中，线程的切换、同步和通信甚至无需内核干预。
支持多处理器系统

传统单线程进程只能运行在一个 CPU 上；对于多线程进程，可将进程中的多个线程分配到多个 CPU 上执行。

线程又称轻量级进程，但并不能说所有线程都比进程小，当一个进程只有一个线程时，线程和进程就是一样大的（来源：王道 2.1.8 选择 40）。

线程的优点

提高系统并发性、节约系统资源、通信简便、设备并行度高等。

线程的缺陷

健壮性差：因为线程共享进程的地址空间和资源，若一个线程出错，则可能影响整个进程的运行。

线程的组织与控制

线程控制块 TCB

用于记录控制和管理线程的信息。

通常包括：

线程标识符；
一组寄存器，包括 PC、状态寄存器、通用寄存器；
线程运行状态；
优先级；
线程专有存储区，线程切换时用于保存现场等；
堆栈指针，用于过程调用时保存局部变量及返回地址等。

同一进程的各个线程都可以访问进程地址空间的每个单元，所以一个线程可以读、写或甚至清除另一个线程的堆栈。

线程的创建

应用程序启动时通常仅有一个线程在执行，称为 “初始化线程”，主要用于创建新线程。

创建新线程时需要利用一个线程创建函数或系统调用，并提供相应参数，如线程主程序的入口指针、堆栈的大小、线程优先级等。

线程创建函数执行完后，将返回一个线程标识符。

线程的终止

当一个线程完成任务或出现异常情况时，由终止线程调用相应的函数或系统调用执行对其终止操作。

有些线程（主要是系统线程）创建之后便一直运行下去而不被终止。

通常线程被终止后并不立即释放资源，只有当进程中的其他线程执行了分离函数后，被终止的线程才与资源分离，此时的资源才能被其他线程利用。

被终止但尚未释放资源的线程仍可被其他线程调用，以使被终止线程重新恢复运行。为此，调用者线程须调用一条被称为 “等待线程终止” 的连接命令来与该线程进行连接。若在一个调用者线程调用 “等待线程终止” 的连接命令，试图与指定线程相连接时，若指定线程尚未被终止，则调用连接命令的线程将会阻塞，直至指定线程被终止后，才能实现它与调用者线程的连接并继续执行；若指定线程已被终止，则调用者不会被阻塞而是继续执行。

线程的实现方式

内核级线程 KLT (Kernel-Level Thread)

也称内核支持线程 KST (Kernel-Supported Thread)，像进程一样（无论是系统进程还是用户进程），内核级线程也是在内核的支持下运行。

线程管理由内核负责（创建、撤销、切换、调度、通信、同步，下同），内核管理的所有工作在内核空间（核心态）实现的。

内核空间为每一个内核线程设置了一个线程控制块 TCB，内核根据该控制块感知某线程的存在，并对其加以控制。

内核线程只在内核地址空间范围活动。

优点：

能发挥多处理机优势，内核能够同时调度同一进程中的多个线程并行执行。
当一个线程被阻塞后，内核可以调度同进程的其他线程继续执行，当然也可运行其他进程中的线程。
上下文切换比较快、开销小（相对进程而言）。内核支持线程具有很小的数据结构和堆栈。
内核本身也可采用多线程技术，提高系统执行速度和效率。

缺点：KLT 切换会造成模式切换。用户进程的线程在用户态下运行，而线程管理在内核实现。这就导致同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大（相对 ULT 而言）。

用户级线程 ULT (User-Level Thread)

线程管理由用户应用程序负责，内核意识不到线程的存在。

用户级线程是在用户空间中实现的（用户态），线程管理的所有工作无须操作系统干预。

应用程序可以通过线程库设计成多线程程序。通常，应用程序从单线程开始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。

用户级线程甚至可以在不支持线程机制的操作系统平台上实现。

设置了用户级线程的系统，其调度仍是以进程为单位进行⚠。

进程包含的线程数量往往不同，采用轮转调度算法时，各进程轮流执行一个时间片，对线程多的进程中的线程不公平。

优点：线程管理开销小，效率高。

线程切换不需要转换到内核，节省了模式切换的开销（上下文切换还是有的，不过只涉及用户栈和少量寄存器等上下文的保存和恢复，不涉及内核栈和页表等内核上下文的切换）。
调度算法可以是进程专用的。在不干扰 OS 调度的情况下，不同的进程可以根据自身需要选择不同的调度算法，对自己的线程进行管理和调度，而与 OS 的低级调度算法是无关的。
用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分。在不同操作系统上不经修改就可直接运行。

缺点：

系统调用的阻塞问题：同一进程的线程一堵全堵（在基于进程机制的 OS 中）。
多线程应用不能利用多处理机进行多重处理（内核每次只给一个进程分配一个 CPU）。

组合方式

有些 OS 把用户级线程和内核支持线程两种方式进行组合，提供了组合方式 ULT/KST 线程。

在组合方式线程系统中，内核支持多个内核支持线程的建立、调度和管理，同时，也允许用户应用程序建立、调度和管理用户级线程。一些 KLT 对应多个 ULT，这是 ULT 通过时分多路复用 KLT 实现的。程序员可按应用需要和机器配置，对 KLT 数目进行调整，以达到较好效果。

同一进程的多个线程可以同时在多个处理机上并行执行，且在阻塞一个线程时不需要将整个进程阻塞，所以组合方式能结合 KLT 和 ULT 的优点并克服各自的不足。

由于用户级线程和内核支持线程连接方式的不同，从而形成了三种不同的模型：多对一型、一对一模型和多对多模型。

多对一模型

多个 ULT 映射到一个 KLT，这些 ULT 一般属于一个进程。

ULT 的调度和管理在用户空间完成，仅当 ULT 需要访问内核时，才将其映射到一个 KLT 上，但每次只允许一个 ULT 进行映射。

优点：线程管理效率比较高，开销小（线程管理在用户空间进行，无须切换到核心态）。

缺点：同一进程的 ULT 一堵全堵；并发较差，不能利用多处理机，在任一时刻只能有一个线程能访问内核。
一对一模型

优点：不会一堵全堵，并发性较强。

缺点：创建线程开销较大，每创建一个 ULT，相应地就需要创建一个 KLT，因此需要限制整个系统的线程数。
多对多模型

将许多 ULT 映射到同样数量或更少数量的 KLT 上。

内核支持线程的数目可以比用户线程少，也可以与之相同。

既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多 KLT 而开销太大的缺点。另外还拥有上述两种模型的优点，可以像一对一模型那样，使一个进程的多个线程并行地运行在多处理机系统上，也可像多对一模型那样，减少线程的管理开销和提高效率。多对多模型是上述两种模型的折中方案。

线程的实现

不论是进程还是线程，都必须直接或间接地取得内核的支持。由于内核支持线程可以直接利用系统调用为它服务，故线程的控制相当简单；而用户级线程必须借助于某种形式的中间系统的帮助方能取得内核的服务，故在对线程的控制上要稍复杂些。

内核支持线程的实现

在仅设置了内核支持线程的 OS 中，一种可能的线程控制方法是，系统在创建一个新进程时，便为它分配一个任务数据区 PTDA (Per TaskData Area)，其中包括若干个线程控制块 TCB 空间。在每一个 TCB 中可保存线程标识符、优先级、线程运行的 CPU 状态等信息。虽然这些信息与用户级线程 TCB 中的信息相同，但现在却是被保存在内核空间中。

内核支持线程的创建、撤销、调度、切换均与进程的相类似，但所花费的开销要比进程的小得多。

用户级线程的实现

用户级线程是在用户空间实现的。所有的用户级线程都具有相同的结构，它们都运行在一个中间系统上。当前有两种方式实现中间系统，即运行时系统和内核控制线程。

运行时系统(runtime system)

实质上是管理和控制线程的函数/过程集合，包括用于创建和撤销线程的函数、线程同步和通信的函数以及实现线程调度的函数等。

运行时系统中的所有函数驻留在用户空间，并作为 ULT 与内核之间的接口。正是有了这些函数，才能使用户级线程与内核无关。

用户级线程在切换时不须转入核心态，而是由运行时系统中的线程切换过程/函数来执行切换任务。该过程将线程的 CPU 状态保存在该线程的堆栈中，然后按照一定的算法，选择一个处于就绪状态的线程运行，将新线程堆栈中的 CPU 状态装入到 CPU 相应的寄存器中，一旦将栈指针和程序计数器切换后，便开始了新线程的运行。由于用户级线程的切换无须进入内核，且切换操作简单，因而使用户级线程的切换速度非常快。

⚠用户级线程是不能利用系统调用的。当线程需要系统资源时，将要求传送给运行时系统，由后者通过相应的系统调用来获得系统资源。
内核控制线程/轻型进程 LWP (Light Weight Process)

轻型进程 LWP 是建立在内核之上并由内核支持的用户线程，它是内核线程的高度抽象，每一个轻型进程都与一个特定的内核线程关联。

LWP 和普通进程的区别在于，它没有独立的用户空间。一个进程内的所有 LWP 共享该进程所拥有的资源。

LWP 都有自己的数据结构（如 TCB），其中包括线程标识符、优先级、状态，另外还有栈和局部存储区等。

LWP 可通过系统调用获得内核服务。这样，当一个用户级线程运行时，只须将它连接到一个 LWP 上，此时它便具有了内核支持线程的所有属性。这种线程实现方式就是组合方式。

每个进程都可拥有一个或多个 LWP。

一个系统中的用户级线程数量可能很大，为了节省系统开销，不可能设置太多的可拥有多个 LWP，而是把这些 LWP 做成一个缓冲池，称 “线程池”。用户进程中的任一 ULT 都可以连接到 LWP 池中的任何一个 LWP 上。

为使每一 ULT 都能利用 LWP 与内核通信，可使多个 ULT 多路复用一个 LWP，但只有当前连接到 LWP 上的线程才能与内核通信，其余进程或者阻塞，或者等待 LWP。

每一个 LWP 都要连接到一个 KLT 上，这样，通过 LWP 可把 ULT 与 KLT 连接起来。ULT 可通过 LWP 来访问内核，但内核所看到的总是多个 LWP 而看不到用户级线程。亦即，由 LWP 实现了内核与用户级线程之间的隔离，从而使用户级线程与内核无关。

当用户级线程不需要与内核通信时，并不需要 LWP；而当要通信时，便须借助于 LWP，而且每个要通信的用户级线程都需要一个 LWP。例如，在一个任务中，如果同时有 5 个 ULT 发出了对文件的读、写请求，这就需要有 5 个 LWP 来予以帮助，即由 LWP 将对文件的读、写请求发送给相应的内核级线程，再由后者执行具体的读、写操作。如果一个任务中只有 4 个 LWP，则只能有 4 个用户级线程的读、写请求被传送给内核线程，余下的一个 ULT 必须等待。

在内核级线程执行操作时，如果发生阻塞，则与之相连接的多个 LWP 也将随之阻塞，进而使连接到 LWP 上的用户级线程也被阻塞。如果进程中只包含了一个 LWP，此时进程也应阻塞。这种情况与前述的传统 OS 一样，在进程执行系统调用时，该进程实际上是阻塞的。但若进程中含有多个 LWP，则当一个 LWP 阻塞时，进程中的另一个 LWP 可继续执行。即使进程中所有 LWP 全部阻塞，进程中的线程也仍能继续执行，只是不能再去访问内核。

线程库

线程库(thread library)是为程序员提供创建和管理线程的 API，实现线程库方法主要有两种：

在用户空间中提供一个没有内核支持的库

这种库的所有代码和数据结构都位于用户空间。

这意味着调用库内的一个函数只导致用户空间的一个本地函数的调用。
实现由操作系统直接支持的内核级的一个库

这种库的代码和数据结构位于内核空间，调用库中的一个 API 函数通常会导致对内核的系统调用。

目前使用的三种主要线程库：POSIX Pthreads、Windows API、Java。

Pthreads 作为 POSIX 标准的扩展，可提供用户级或内核级的库（类 UNIX 系统）。
Windows API 属于内核级线程库。
Java 线程 API 允许线程在 Java 程序中直接创建和管理。但由于 JVM 实例通常运行在宿主操作系统上，Java 线程 API 通常采用宿主系统的线程库来实现，因此在 Windows 系统中 Java 线程通常采用 Windows API 来实现，在类 UNIX 系统中采用 Pthread 来实现。

处理机调度

调度的概念

调度的基本概念

处理机调度是对处理机进行分配（进程数往往多于处理机数）。

即从就绪队列按照一定算法选择一个进程并将处理机分配给它运行，以实现进程并发执行。

只要对资源的请求大于资源本身的数量，就会涉及调度。

调度的目的

提高处理机利用率，合理地处理计算机软/硬件资源。

调度的层次

一个作业从提交开始直到完成，往往会经历以下三级调度：

作业调度/高级调度

从外存处于后备状态的作业挑选一个或多个，给其分配内存等必要资源，并建立相应进程，使其获得竞争处理机的机会。

是内存与辅存之间的调度。

每个作业只调入一次，调出一次。

主要用于多道批处理系统中，而在其他系统中通常不需要配置作业调度。

进程从创建态转换到就绪态是由高级调度完成的⚠。
内存调度/中级调度

暂时不能运行的进程会被调至外存等待（变成挂起态），而中级调度的对象是那些外存上的又已具备运行条件的挂起态进程。当内存稍有空闲后，中级调度挑选后将其重新调入内存，状态改为就绪态，挂在就绪队列等待。

引入中级调度的目的是提高内存利用率和系统吞吐量。

中级调度实际上是存储器管理中的对换功能。
进程调度/低级调度

按照某种算法从就绪队列中选取一个进程，将 CPU 分配给它。

其实就是处理机调度。

最基本调度，在各种操作系统中必须配置这级调度。

频率很高，一般几十毫秒一次。

⛄三级调度的关系

作业调度为进程活动做准备，进程调度使进程正常活动起来。
中级调度将暂时不能运行的进程挂起，处于作业调度和进程调度之间。
作业调度次数少，中级调度次数略多，进程调度频率最高。
进程调度是最基本的，不可或缺。

🐧作业 vs 进程

作业是从用户角度出发的，它由用户提交，以用户任务为单位；进程是从操作系统出发的，由系统生成，是操作系统的资源分配（和独立运行）的基本单位。

调度的目标

即对调度算法的评价准则。要从用户角度、系统整体效率、调度算法开销几个角度同时考虑，而且调度本身也有三种，角度不同，评价标准也有差别。

CPU 利用率

越忙越好。

系统吞吐量

单位时间内 CPU 完成作业的数量。

只看数量，比较狭隘。抛开算法的话，短作业占比越大系统吞吐量就越大。

周转时间

周转时间指从作业提交到作业完成所经历的时间。

周转时间 = 作业完成时间 - 作业到达时间 = 作业在后备队列中排队 (等待高级调度) + 进程在就绪队列中排队 (等待低级调度) + 在处理机上运行 + 进行输入/输出操作。

带权周转时间 = 作业周转时间 / 进程在处理机上实际运行时间。

平均周转时间 = 所有作业的周转时间总和 / 作业数。

平均带权周转时间 = 所有作业的带权周转时间总和 / 作业数。

王道 P82 应用题 06。

等待时间

进程等待处理机的时间之和。

处理机调度算法实际上并不影响作业执行或 I/O 操作的时间，只影响作业在就绪队列中等待所花的时间，因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。

响应时间

从用户提交请求到系统首次产生响应所经历的时间。

在交互式系统中，周转时间不是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围内。

要想得到一个满足所有用户和系统要求的算法几乎是不可能的。涉及调度程序，一方面要满足特定系统用户的要求（如某些实时和交互进程的快速响应要求），另一方面要考虑系统整体效率（如减少整个系统的进程平均周转时间），同时还要考虑调度算法的开销。

调度的实现

调度程序/调度器

用于调度和分派 CPU 的组件，属于操作系统内核程序，由排队器、分派器和上下文切换器三部分组成。

排队器

将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入到相应的就绪队列。

分派器

依据进程调度程序所选的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将 CPU 分配给新进程。

上下文切换器

对处理机进行切换时会发生两对上下文的切换操作：

将当前进程的上下文保存到其 PCB 中，再装入分派程序的上下文，以便分派程序运行。
移出分派程序的上下文，将新选进程的 CPU 现场信息装入处理机的各个相应寄存器中，以便新选进程运行。

结合 Linux + IA-32 任务切换的实现来看，第一对上下文切换由当前进程模式切换引起，在由用户态进入内核态时，用户栈指针 SS 和 ESP、断点 CS 和 EIP、程序状态字 EFLAGS 由硬件压栈，紧接着现场信息（其他所有定点寄存器）再由内核程序（中断/异常/系统调用处理程序）压入内核栈/中断栈，然后执行对应中断/异常/系统调用服务例程，在内核服务例程中调用 schedule 函数，即分派程序。按上面王道给出的说法（不知道从哪抄的），其实是将分派程序与当前进程分离开来，感觉有些欠妥，应该将分派程序的执行视作当前进程内核态的执行过程的一部分；

宏观整个 Linux 中的进程（任务）切换过程（进程 A 用户态 → 进程 B 用户态），用户态上下文（准确来说现场信息属于系统级上下文）的切换是硬件（CPU）和中断/异常/系统调用处理程序利用内核栈/中断栈完成的，而内核态上下文的切换是 schedule 函数利用内核栈（处理机上下文）和 PCB（非处理上下文）完成的。

上下文切换时需要执行大量 load 和 store 指令以保存和更新寄存器的内容，会花费较多时间（即使是现代计算机，每一次上下文切换所花费的时间大约可执行上千条指令）。为此，现已有硬件实现的方法来减少上下文切换时间：通常采用两组或多组寄存器，一组供内核使用，一组供用户使用。这样上下文切换时，只需改变指针让其指向当前寄存器组即可。

进程调度的方式

通常有以下两种进程调度方式：

非剥夺调度方式/非抢占方式

即使有更急更重要的进程进入就绪队列，也要等待当前正在运行的进程运行完成（如正常结束、异常终止）或进入阻塞态时，才将 CPU 分配给其他进程。

一旦把处理机分配给某进程后，就一直让它运行下去，绝不会因为时钟中断或任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成或发生某事件而使其无法再继续运行，才主动调用调度程序让出 CPU 的方式

优点：实现简单、系统开销小，适用于大多数的批处理系统。

缺点：不能用于分时系统和大多数的实时系统。

剥夺调度方式/抢占方式

优点：对提高系统吞吐率和响应效率都有明显的好处。

抢占不是任意性抢占，必须遵循一定原则（主要有优先级、短进程优先和时间片原则等）。

进程调度的时机

① 请求调度的事件发生 → ② 运行调度程序，调度新进程 → ③ 进程切换
🔥① 出现后，② 不一定马上进行；② 完成后，③ 往往立刻发生。🔥

不能马上进行进程调度与切换的情况

处理中断的过程中

中断处理过程复杂，很难实现切换。

中断处理是系统工作的一部分，逻辑上不属于任何进程，不应被剥夺处理机资源。
需要完全屏蔽中断的原子操作过程中

如加锁、解锁、中断现场保护、恢复等原子操作。

在原子操作中连中断都要屏蔽，更不应该进行进程调度和切换。

若在上述过程中发生了引起调度的条件，则不能马上进行调度与切换，而应置系统的请求调度标志（PCB 中），直到上述过程结束后才进行相应的调度与切换。

应该进行进程调度与切换的情况

创建新进程后，由于父进程和子进程都处于就绪态，因此需要决定是运行父进程还是子进程，调度程序可以合法地决定其中一个进程先运行。
进程正常结束后或者异常终止后，必须从就绪队列中选择某个进程运行。若没有就绪进程，则通常运行一个系统提供的闲逛进程。
当进程因 I/O 请求、信号量操作或其他原因而被阻塞时，必须调度其他进程运行。
中断/异常/系统调用处理结束后，返回被中断进程的用户态程序执行现场前，会检查当前进程的请求调度标志，若此时已置上请求调度标志，则进行进程调度（调度过程中会清除此请求调度标志），而非让被中断进程继续运行。

若操作系统支持这种情况下运行调度程序，则实现了剥夺式调度。

⛅总结

一定会：终止异常、时间片中断、正常结束、阻塞、新进程创建。

一定不会：中断处理中、完全屏蔽中断的原子操作过程中。

不一定：其他中断/异常（故障异常/自陷异常/外中断）处理结束返回用户态前。

线程的调度

用户级线程调度

由所属进程中的调度程序决定哪个 ULT 运行（内核不知道 ULT 的存在）。

用户级线程的线程切换在同一进程中进行，仅需少量的机器指令。

内核级线程调度

由内核负责，通常不用考虑该 KLT 属于哪个进程。

对被选择的 KLT 赋予一个时间片，如果超过了时间片，就会强制挂起该 KLT。

KLT 切换需要完整的上下文切换、修改内存映像、使高速缓存失效，这就导致了若干数量级的延迟。

闲逛进程 idle

当系统没有其他就绪进程可运行时，调度器会选择 idle 进程运行，以避免 CPU 空转。

现代操作系统的 idle 进程通常会调用 CPU 的节能指令，使 CPU 进入低功耗状态，减少能耗。

idle 进程的存在确保了调度器始终有一个进程可以调度，从而避免系统进入未定义状态。

PID 通常是 0，是操作系统启动时创建的第一个进程。

闲逛进程的优先级最低，没有就绪进程时才会运行。只要有进程就绪，就会立即让出处理机。

闲逛进程不需要 CPU 之外的资源，它不会被阻塞。

idle 进程通常不运行用户态代码，它只在内核态执行。

典型的调度算法

设计调度算法时考虑的指标有很多，比较常见的有公平性、资源利用率、平均周转时间、平均等待时间、平均响应时间等。

先来先服务调度算法 FCFS（作业/进程）

属于不可剥夺算法。

特点：

简单但效率低。系统开销最小⚠。
表面公平：对长作业比较有利，对短作业不利（相对 SJF 和高响应比）。
有利于 CPU 繁忙型作业，不利于 I/O 繁忙型作业⚠。

CPU 繁忙型作业类似于长作业；I/O 繁忙型作业是指作业执行时需频繁请求 I/O 操作，即可能频繁放弃 CPU，所以占用 CPU 的时间不会太长，一旦放弃 CPU，则必须重新排队等待调度，故采用 SJF 比较合适。

不能作为分时系统和实时系统的主要调度策略。

常被结合在其他调度策略中使用。

短作业优先调度算法 SJF / 短进程优先调度算法 SPF

SPF：从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时才释放 CPU。

SJF：从后备队列中选择一个或几个估计运行时间最短的作业调入内存运行。

可视为一种特殊的优先级算法。

优点：平均等待时间、平均周转时间最少⚠。

缺点：

对长作业/进程不利，可能会引起长进程/作业的饥饿。
完全未考虑紧迫程度。
预估运行时间是用户提供的（这就很……，相当于让用户手动设置优先级了）。

SPF 算法默认为非抢占式的。抢占式 SPF 调度算法也称最短剩余时间有限调度算法。

优先级调度算法（作业/进程）

优先级用于描述作业/进程的紧迫程度。

在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调度内存，分配必要的资源，创建进程并放入就绪队列。

在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将 CPU 分配给它，使之投入运行。

根据新的更高优先级进程进入就绪队列后能否抢占正在执行的进程，可分为非剥夺式优先级调度算法和剥夺式优先级调度算法两种。

根据进程创建后其优先级是否可以改变，进程优先级也可分为两种：

静态优先级

创建时确定，运行期间不变。

主要依据：进程类型、进程对资源的要求、用户要求。

优点：简单易行，系统开销小。

缺点：不够精确，可能出现优先级低的进程长期得不到调度的情况。
动态优先级

运行期间根据进程情况的变化动态调整。

主要依据：进程占有 CPU 时间的长短、就绪进程等待 CPU 时间的长短。

优先级设置一般原则：

系统进程＞用户进程
交互进程＞非交互型进程（前台进程＞后台进程）
I/O 型进程＞计算型进程（让处理速度相对较慢的 I/O 设备尽早开始工作，进而提升系统的整体效率）

刚执行过（即时间片用完时）的进程优先级应该降低。

高响应比优先调度算法（主要用于作业调度）

每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

响应比 $R_{p} = \frac{等待时间 + 要求服务时间}{要求服务时间}$ 。

是对 FCFS 和 SJF 的一种综合平衡，克服了 SJF 可能会产生的饥饿现象。根据公式可知：

1）作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业，因而类似于 SJF。

2）要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而类似于 FCFS。

3）对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，也可获得 CPU，克服了 SJF 中长作业可能 “饥饿” 的现象。

时间片轮转调度算法 RR（进程）

属于抢占式算法。主要适用于分时系统。

系统将所有的就绪进程按 FCFS 策略排成一个就绪队列。系统可设置每隔一定时间（如 30ms）便产生一次中断，去激活进程调度程序进行调度，把 CPU 分配给就绪队列队首进程，并令其执行一个时间片。在使用完一个时间片后，即使进程并未运行完成，它也必须释放出（被剥夺）处理机给当前就绪队列的队首进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次执行。

进程调度时机：① 一个时间片用完；② 一个时间片尚未用完而正在运行的进程便已完成。

时间片的大小对系统性能影响很大：太大以致所有进程都能在一个时间片内执行完毕，便会退化成 FCFS；小了会使进程切换过于频繁，使 CPU 开销增大，而真正用于运行用户进程的时间将减少。

时间片的大小通常由以下因素确定：响应时间、系统开销、进程数量、进程运行时间等。

多级队列调度算法

前述的各种算法，在系统中仅设置一个进程的就绪队列，即调度算法是固定且单一的，无法满足系统中不同用户对进程调度策略的不同要求。在多处理机系统中，这种单一调度策略实现机制的缺点更为突出。

多级队列调度算法在系统中设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列。每个队列可实施不同的调度算法，队列本身也可以设置不同的优先级。在多处理机系统中，可以很方便为每个处理机设置一个单独的就绪队列。

多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的总和和发展。

实现思想：

第 1 ~ $n - 1$ 级采用 FCFS，第 $n$ 级采用 RR。不同队列间采用剥夺式优先级调度。
每个新进程进入内存后首先被放入第 1 级队列的末尾。到它执行时，若能在一个时间片内完成则完成后撤离系统，否则调度程序将其转入下一级队列的末尾。后序队列以此类推，直到降至第 $n$ 级，采取 RR。
仅当 1 ~ $i - 1$ 级队列均为空时，才会调度第 $i$ 级队列中的进程运行。若此时有新进程进入 1 ~ $i - 1$ 级队列，则该进程会抢占处理机⚠，即由调度程序把正在运行的进程放回第 $i$ 级队列的末尾，把处理机分配给新的更高优先级的进程。

设计多级反馈队列调度算法需要考虑：

就绪队列的数量：影响长进程的最终完成时间。
就绪队列的优先级：影响进程执行的顺序。
各就绪队列的调度算法：影响各队列中进程的调度顺序。
进程在就绪队列中的迁移条件：影响各进程在各队列中的执行时间。

☺优势：通过动态调整进程优先级和时间片大小，多级反馈队列可以兼顾多方面的系统目标，能较好地满足各类用户的需要。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的 I/O 设备利用率和缩短响应时间而照顾 I/O 进程；同时，也不必事先估计进程的执行时间。

对于终端型作业用户：由于它们提交的作业大多属于交互型作业，作业通常比较短小，系统只要能使这些作业在第 1 级队列所规定的时间片内完成，便可使终端型用户感到满意；
对于短批处理作业用户：它们的作业开始时像终端型作业一样，若仅在第 1 级队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。对于稍长的作业，通常也只需要在第 2 级队列和第 3 级队列中各执行一个时间片即可完成，其周转时间仍然较短；
对于长批处理作业用户：长作业经过前面几个队列得到部分执行，不会长期得不到处理。

😖缺点：系统开销大。该算法需要设置多个就绪队列，并且要在不同的队列之间进行进程的转移和抢占，因此增加了系统开销。

调度算法特点总结

实时：优先级 + 抢占式；

分时：时间片轮转、多级反馈队列、高响应比优先。

调度算法的系统开销

高响应比优先和多级反馈队列开销都较大：高响应比优先需要根据进程的等待时间和服务时间来计算响应比；多级反馈队列涉及多个队列的管理，以及进程在队列之间的转移；

时间片轮转算法虽然简单，但它需要为每个进程分配一个固定的时间片，并且在时间片用完时进行上下文切换，因此它的系统开销也不小；

先来先服务是一种最简单的调度算法，它只需按照进程到达的先后顺序进行调度，无须进行任何优先级或时间片的判断和分配，因此系统开销最小。

饥饿

优先级算法和短作业优先算法都可能出现饥饿现象；

先来先服务算法和时间片轮转算法都不会出现饥饿现象。

时间片与时钟中断

时钟中断是频率性发出的信号，两次时钟中断的间隔时间称为节拍，即时钟周期。时间片是若干时钟周期的片段。时钟中断发生后，系统会修改当前进程在时间片内的剩余时间，即减去一个时钟周期。若剩余时间减到 0，就进行进程调度（因此分时系统实现时间片轮转调度需要使用时钟中断处理程序）。

进程在时间片用完之前主动让出 CPU 的时候，进程调度模块会记录下时间片剩余时间，在该进程下次再获得 CPU 时，继续运行之前时间片的剩余时间。

进程运行结束不必等待当前进程的时间片全部用完。

进程切换

上下文

进程上下文

进程的物理实体（代码和数据等）和支持进程运行的环境合称为进程的上下文。

进程上下文 = 用户级上下文 + 系统级上下文。

用户级上下文

指由用户进程的程序块、数据块、运行时的堆和用户栈（统称为用户堆栈）等组成的用户空间信息。
系统级上下文

指由进程标识信息、进程现场信息、进程控制信息和系统内核栈等组成的内核空间信息。

进程控制信息包含各种内核数据结构，例如，记录有关进程信息的进程表、页表、打开文件列表等。

用户级上下文地址空间和系统级上下文地址空间一起构成了一个进程的整个存储器映像，实际上它就是进程的虚拟地址空间。

处理机上下文/寄存器上下文/硬件上下文

指处理机中各个寄存器的内容。

模式切换

模式切换实际上包含在中断/异常的响应和返回过程，本身没有进程上下文切换，因为只涉及到一个进程，只是同一进程的用户栈与内核栈的使用转换。但模式切换往往伴随着寄存器上下文切换，因为响应之后，不管是异常处理程序、中断服务程序，还是系统调用处理程序，在执行的最开始和最后，都会通过内核栈/中断栈对现场信息（处理器上下文）进行保存和恢复。

⚠模式切换的由硬件（CPU）自动完成。

用户态 → 核心态

以 IA-32 处理器为例：

切换处理器特权级（CPU）

处理器只有通过 “门结构” 才能由低特权级转移到高特权级（大多数的现代操作系统使用的是中断门）。

通过特权级检查和使用门后，处理器将以目标代码段 DPL 为当前特权级 CPL（CS.RPL）。

未通过特权级检查将引发通用保护错异常。
将进程所使用的栈从用户栈转换为内核栈

处理器先找个地方临时保存用户栈的栈段选择子和栈指针（Linux 是保存在 per-CPU 变量中），之后将内核栈的栈段选择子和栈指针（取自 TSS 中的 ss0 和 esp0 字段）加载到栈段寄存器 SS 和栈指针寄存器 ESP，这样便启用了内核栈。

per-CPU 变量是 Linux 的特性。在多核系统中，每个 CPU 都有自己的本地内存缓存，为了提高效率，某些数据结构会被分配到每个 CPU 的核心上，称为 per-CPU 变量，从而避免了处理器之间的互斥和同步。
保存用户栈的栈段选择子和栈指针到内核栈（CPU）

使用内核栈后，将之前临时保存的用户栈的栈段选择子和栈指针压入内核栈中。
保存 PSW 到内核栈（CPU）

IA-32 处理器中 PSW 对应 EFLAGS 寄存器的内容。
保存断点到内核栈（CPU）

因为接下来要运行内核代码，这意味着代码段寄存器 CS 和指令指针寄存器 EIP 会被重新加载，所以需要将当前代码段 CS 和 EIP 都备份在栈中，作为从内核中返回时的地址。
某些异常会有错误码，此错误码用于报告异常是在哪个段上发生的，也就是异常发生的位置，所以错误码中包含选择子等信息。错误码会紧跟在 EIP 之后入栈，记作 ERROR_CODE。
更新 PC 为内核服务程序地址

将门描述符中的内核服务程序目标代码段描述符选择子和偏移量分别装载到代码段寄存器 CS 和指令指针寄存器 EIP 中。

内核服务程序包括：异常处理程序、中断服务程序、系统调用处理程序。

至此，处理器从用户程序转移到内核服务程序上，实现特权级由用户态到核心态的转移，从下一个时钟开始，就执行内核服务程序的第一条指令。

核心态 → 内核态

依次弹出 32 位数据到寄存器 EIP、CS、EFLAGS、ESP、SS 中，实现处理器特权级与相应栈的切换。

执行中断返回指令时，当前栈指针 esp 必须指向内核栈中备份的 EIP 所在的位置，这样处理器才能将栈中的数据对号入座，弹出到各自对应的寄存器中。

内核栈的栈段选择子和栈指针无需保存（TSS 中的 ss0 和 esp0 无需更新）。内核栈只是用来保存进程在内核态运行的相关信息以及用户栈地址，一旦进程返回到用户态后，内核栈中保存的信息就会失效，因此每次进程从用户态陷入内核的时候得到的内核栈都是空的。

上下文切换

上下文切换一般特指进程上下文切换。

上下文切换伴随的 CPU 运行模式的变化过程：进程 A 用户态 → 进程 A 内核态 → 进程 B 内核态 → 进程 B 用户态。显然进程切换发生在内核态。

上下文切换的流程

挂起一个进程，保存 CPU 上下文到该进程的 PCB，包括程序计数器和其他寄存器。
将 PCB 移入相应的队列（如就绪、在某事件阻塞等队列）。
选择新进程执行，并更新其 PCB。
恢复新进程的 CPU 上下文。
跳转到新进程 PCB 中的程序计数器所指向的位置执行。

另一种说法：进程切换往往在调度完成后立刻发生，它要求保存原进程当前断点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设 PC 寄存器等相关工作后，开始运行新的进程。

上下文切换的开销

通常是计算密集型，即它需要相当可观的 CPU 时间。在每秒几十上百次的切换中，每次切换都需要纳秒量级的时间，所以上下文切换对系统来说意味着需要消耗大量的 CPU 时间。

有些处理器提供多个寄存器组，这样上下文切换就只需简单改变当前寄存器组的指针。

上下文切换 vs 模式切换

处理机模式切换时，处理机逻辑上可能还在同一进程中运行。

上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性。

线程上下文切换

同进程内的线程切换，要比进程间的切换消耗开销更少，因为需要保存和设置的寄存器内容很少。

不同进程的两个线程切换会引起进程切换。

KLT 的切换会引起模式切换（即使是同一进程的 KLT），而同一进程的 ULT 的切换不会引起模式切换。

多处理机调度

基本概念

多处理机是共享存储多处理机的简称。

根据系统中所用处理器的相同与否，可将多处理器系统 MPS 分为如下两类：

对称多处理器系统 SMPS (Symmetric Multiprocessor System)

在系统中所包含的各处理器单元，在功能和结构上都是相同的。
非对称多处理器系统 ASMPS (Asymmetric Multiprocessor System)

在系统中有多种类型的处理单元，它们的功能和结构各不相同。

系统中只有一个主处理器，有多个从处理器。

进程分配方式

ASMPS 中的进程分配方式

对于非对称 MPS，其 OS 大多采用主从式 OS，即 OS 的核心部分驻留在一台主机上，而从机上只是用户程序，进程调度只由主机执行。

调度过程

每当从机空闲时，便向主机发送一索求进程的信号，然后，便等待主机为它分配进程。
在主机中保持有一个就绪队列，只要就绪队列不空，主机便从其队首摘下一进程分配给请求的从机。
从机接收到分配的进程后便运行该进程，该进程结束后从机又向主机发出请求。

优点

在非对称 MPS中，主从式的进程分配方式的优点是系统处理比较简单，因为所有的进程分配都由一台主机独自处理。

问题

由一台主机控制一切，也存在问题：

主机一旦出现故障，将会导致整个系统瘫痪。
很容易因主机太忙，来不及处理而形成系统瓶颈。

SMPS 中的进程分配方式

在 SMP 系统中，所有的处理机都是相同的，可以将任何一个进程分配任何一个处理机。对于这种进程分配，可采用：静态分配方式、动态分配方式、混合方式。

静态分配方式

该方式下，一个进程从开始执行直至其完成，都被固定地分配到一个处理器上去执行。

此时，须为每一处理器设置一专用的就绪队列，该队列中的就绪进程先后都是被分配到该处理器上执行。

在进程阻塞后再次就绪时，也仍被挂在这个就绪队列中，因而下次它仍在此处理器上执行。

其优点是进程调度的开销小；缺点是会使各处理器的忙闲不均。

换言之，可能有些处理机的就绪队列很快就变成空队列，使处理器处于空闲状态，而另一些处理器则可能一直忙碌。

动态分配方式

为了防止系统中的多个处理器忙闲不均，可以在系统中仅设置一个公共的就绪队列，系统中的所有就绪进程都被放该队列中。分配进程时，可将进程分配到任何一个处理器上。

对一个进程的整个运行过程而言，在每次被调度执行时，都是随机地被分配到当时是空闲的某一处理器上去执行。例如，某进程一开始是被分配到处理器 0 上去执行，后来因阻塞而放弃处理器 0。当它又恢复为就绪状态后，就被挂到公共的就绪队列上，在下次被调度时，就可能被分配到处理器 1 上去执行，也有可能被分配到处理器 2 或处理器 3 上去执行。

动态分配方式的主要优点是消除了各处理器忙闲不均的现象。

然而，该方案下不容易实现处理器亲和性。

处理器亲和性：指的是绑定某一进程或线程到特定的 CPU 或 CPU 集合，从而使得该进程或线程只能运行在绑定的 CPU 或 CPU 集合上.

CPU 亲和性利用了这样一个事实：进程上一次运行后的残余信息会保留在 CPU 的状态中（也就是指 CPU 的缓存）。如果下一次仍然将该进程调度到同一个 CPU 上，就能避免缓存未命中等对 CPU 处理性能不利的情况，从而使得进程的运行更加高效。

CPU 亲和性分为两种：软亲和性和硬亲和性。

软亲和性主要由操作系统来实现，操作系统的调度器会倾向于保持一个进程不会频繁的在多个 CPU 之间迁移，通常情况下调度器都会根据各个 CPU 的负载情况合理地调度运行中的进程，以减轻繁忙 CPU 的压力，提高所有进程的整体性能。
硬亲和性指用户可以通过调用系统API实现自定义进程运行在哪个 CPU 上，从而满足特定进程的特殊性能需求。

混合方式

这种方式下，同时使用本地队列和全局队列。本地队列是每个 CPU 所独享的，而全局队列是所有 CPU 所共享的。

全局队列用于保证负载均衡，即每个 CPU 都有公平的进程份额去执行。
本地队列减少了进程调度开销的影响，保证了亲和性。

除了全局队列，还有两种实现负载均衡的技术：

基于推的迁移(Push Migration)

一个特定的任务周期性检査每个处理器的负载平衡。如果发现不平衡，那么通过将进程从超载处理器推到空闲或不太忙的处理器上来实现负载平衡。

基于推的迁移(Pull Migration)

空闲处理器从一个忙的处理器上拉一些就绪进程到自己的继续队列中。

进程/线程调度方式

自调度方式

自调度方式是最简单的一种调度方式。

在系统中设置有一个公共的进程或线程就绪队列，所有的处理器在空闲时，都可自己到该队列中取得一进程或线程来运行。在自调度方式中，可采用在单处理机环境下所用的调度算法，如先来先服务调度算法等。

自调度方式的主要优点表现为：只要公共就绪队列不空，就不会出现处理机空闲的情况，也不会发生处理机忙闲不
均的现象，因而有利于提高处理机的利用率。

然而，由于在整个系统中只设置一个就绪队列，这些处理器必须互斥地访问该队列，这很容易形成系统瓶颈。

另外，通常一个应用中的多个线程都属于相互合作型的，但在采用自调度方式时，这些线程很难同时获得处理器而同时运行，这将会使某些线程因其合作线程未获得处理器运行而阻塞，进而被切换下来，导致线程切换频繁。

成组调度方式

为了解决在自调度方式中线程被频繁切换的问题，产生了成组调度方式。该方式将一个进程中的一组线程分配到一组处理器上去执行。在成组调度时，如何为应用程序分配处理器时间，可考虑采用以下两种方式：

面向所有应用程序平均分配处理器时间，如下图 a。
面向所有线程平均分配处理机时间，如下图 b。

可见，按线程平均分配处理机时间的方法更有效。

成组调度方式的主要优点是：如果一组相互合作的进程或线程能并行执行，则可有效地减少进程或线程阻塞情况的发生，从而可以减少进程或线程的切换，使系统性能得到改善；此外，因为每次调度都可以解决一组线程的处理机分配问题，因而可以显著地减少调度频率，从而也减少了调度开销。可见，成组调度的性能优于自调度，目前已获得广泛的认可，并被应用到许多种处理机 OS 中。

评价调度性能的因素

任务流时间

把完成任务所需要的时间定义为任务流时间。

调度流时间

一个调度流时间是系统中所有处理机上的任务流时间的总和。

平均流时间

平均流时间等于调度流时间除以任务数。

处理机利用率

处理机的利用率等于该处理机上任务流之和除以最大有效时间单位。

示例

如图所示，图中有三台处理机 P1~~P3 和五个任务 T1~~T5，调度从时间 0 开始，共运行了 7 个时间单位，在处理机 P1 上运行任务 T1 和 T2，分别需要 5 个和 1.5 个时间单位；在处理机 P2 上运行任务 T2 和 T1，分别用了 5 个和 2 个时间单位；在处理机 P3 上运行任务 T3、T4 和 T5，每一个都需要 2 个时间单位。

任务 T1 任务流时间：5 + 2 = 7 个时间单位

任务 T2 任务流时间：5 + 1.5 = 6.5 个时间单位

任务 T3 任务流时间：2 个时间单位

任务 T4 任务流时间：2 个时间单位

任务 T5 任务流时间：2 个时间单位

三台处理机的调度流时间：7 + 6.5 + 2 + 2 + 2 = 19.5 个时间单位

平均流时间：19.5 ÷ 5 = 3.9 个时间单位、

最大有效单位时间：7.0 个时间单位

处理机 P1 的利用率：6.5 ÷ 7.0 = 0.93

处理机 P2 的利用率：7.0 ÷ 7.0 = 1.00

处理机 P3 的利用率：6.0 ÷ 7.0 = 0.86

三台处理机平均利用率：(0.93+1.00+0.86) ÷ 3 = 0.93

同步与互斥

在多道程序共同执行的条件下，进程与进程是并发执行的，不同进程之间存在不同的相互制约关系，为了协调进程之间的相互制约关系，引入了进程同步的概念。

进程同步的基本概念

临界资源(critical resource)

一次仅允许一个进程使用的资源。

临界资源的访问过程

进入区(entry section)

在进入区要检查可否进入临界区，若进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
临界区(critical section)

进程中访问临界资源的那段代码，又称临界段。
退出区(exit section)

将正在访问临界区的标志清除。
剩余区(remainder section)

代码中的剩余部分。

两种形式的进程间制约关系

同步（直接制约关系）

为完成某种任务而建立的两个或多个进程，这些进程因需要协调它们的工作次序而等待、传递信息所产生的制约关系。

同步关系源于进程之间的相互合作。
互斥（间接制约关系）

并发进程访问同一临界资源形成的制约关系。

实现临界区互斥应遵循的准则

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

空闲让进

临界区空闲时，允许一个请求进入临界区的进程立即进入。
忙则等待

当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
有限等待

对请求访问的进程，应保证能在有限时间内进入临界区，防止进程无限等待。
让权等待

当进程不能进入临界区时，应立即释放处理机，防止进程忙等。

忙等：等待进程一直轮询某个变量直到符合条件，浪费时间片。

实现临界区互斥，“让权等待” 非必须遵循，其他三条必须遵循。

实现临界区互斥的基本方法

软件实现方法（标志）

单标志法

设置一个公用整型变量 turn，指示允许进入临界区的进程编号。进程退出临界区时把接下来进入的 “机会” 指名让给另一个进程。

该算法要求进程必须交替进入临界区。若被指名的进程不打算进入临界区，其他进程就都没法再进入临界区，即使临界区是空闲的，因此该方法违背了 “空闲让进”。

双标志法先检查

每个进程都有一个布尔类型的标志，标志为 true 时意味着宣布自己想要进入临界区。

每个进程在进入区会先会检查其它进程的标志来确认是否已有进程表达了想要进入临界区的意愿。若有，则等待；否则，设置自己的标志为 true 后再进入临界区，在退出临界区时再设置为 false。

优点：不要求进程交替进入，可连续使用。

缺点：检查和设置是分开的，不能一次进行，两个进程按 ①②③④ 的顺序执行时就会同时进入临界区，违背了 “忙则等待”。

双标志法后检查

先设置自己的标志再检查别人的标志，若对方的标志为 true，则等待，否则，进入临界区。

虽然避免了会同时进入临界区的情况，但又可能会导致两个进程饥饿（互等，但其实谁都没进去），违背了 “空闲让进” 和 ”有限等待“。

Peterson 算法

结合了单标志法和双标志后检查法的思想，利用 flag[] 解决互斥访问问题，利用 turn 解决饥饿问题。

每个进程在进入临界区前，先设置自己的 flag 标志为 true，再将 turn 标志指明给对方（“我想进，但还是让 j 先来吧”）。

之后，再同时检查对方的 flag 标志和 turn 标志。

只有表达了想进临界区的意愿并且被指名允许进入时，才可以进入临界区。由于每个进程都在表达想要进入临界区的意愿后又把机会 “谦让” 给对方，但只 “谦让” 一次，所以不难看出先 “谦让” 的进程会先进入临界区。

“我想进，但你先吧” “我也想进，还是你先吧” “那我不客气了”
“我想进，但你先吧” “我现在不想” “那我不客气了”

先 “谦让” 的进程是在假客气😒

Peterson 算法很好地遵循了 “空闲让进”、“忙则等待”、“有限等待”，但与前三种算法一样，依然未遵循 “让权等待”。

硬件实现方法（低级方法/元方法）

中断屏蔽方法

当有进程在执行它的临界区代码时，直接暴力关中断，执行完再开。

因为 CPU 只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完。

如此简单粗暴，自然存在很多缺点：

将关中断的权力交给用户很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止。
限制了处理机交替执行程序的能力，执行的效率会明显降低。
对多处理机系统没用，因为在一个 CPU 上关中断并不能防止进程在其他 CPU 上执行相同的临界区代码。

原语功能的不被中断执行特性在单处理机上可由软件通过屏蔽中断方法实现。

硬件指令方法

TestAndSet 指令

TestAndSet 指令简称 TS 指令，其功能是读出指定标志后将该标志设置为真。指令的功能描述如下：
c
1
2
3
4
5
boolean testAndSet(boolean *lock) {
boolean old = *lock;
*lock = true; // 无论之前是否已加锁,都将lock置为true
return old;
}
当用 TS 指令管理临界区时，为每个临界资源设置一个共享布尔变量 lock，true 表示正被占用（已加锁），false 表示空闲（未加锁）。

利用该指令实现互斥的过程描述如下：
c
1
2
3
4
while (testAndSet(&look));
critical section;
lock = false;
remainder section;
优点：相比于软件实现方法，TS 指令将 “检查” 和 “加锁” 操作用硬件的方式变成了一气呵成的原子操作；相比于关中断方法，由于 “锁” 是共享的，这种方法适用于多处理器系统。

缺点：违背 “让权等待”，暂时无法进入临界区的进程会占用 CPU 循环执行 TS 指令。

Swap 指令

Swap 指令的功能是交换两个字的内容。

void Swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

为每个临界资源设置一个共享布尔变量 lock，每个进程中再设置一个局部布尔变量 key。

key = true;
while (key) {
	Swap(&lock, &key);   
}
critical section;
lock = false;
remainder section;

以上对两个指令的描述仅为功能描述，它们由硬件逻辑实现，不会被中断。

两个硬件指令实现互斥的方法并无太大区别，都是先记录此时临界区是否已加锁，再将锁标志 lock 置为 true，最后检查记录的 lock 旧值，如果原来就是 true，那就等，之前的设置 true 没什么影响；如果原来是 false，那正好，没白设置，接下来直接进入就行。

😀硬件指令方法实现互斥的优点：

适用于任意数目的进程，支持多处理器系统。
简单、容易验证其正确性。
支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。

😞硬件指令方法实现互斥的缺点：

违反 “让权等待”，等待进入临界区的进程会占用 CPU 执行 while 循环。
违反 “有限等待”，可能发生饥饿，因为是随机从等待进程中选择一个进入临界区，有的进程可能一直选不上。

互斥锁

互斥锁(mutex lock)是解决临界区最简单的工具。

进程在进入临界区应获得锁，在退出临界区时释放锁。

acquire() {
    while (!available);  // 忙等
    available = false;  // 拿到锁
}

release() {
    available = true;  // 释放锁
}

acquire() 和 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制实现⚠。

上面描述的互斥锁也称自旋锁，主要缺点是会忙等，违反 “让权等待”，因此通常用于多处理器系统

自旋锁的优点是，进程在等待锁期间，没有上下文切换（忙等当然不会切换😅），若上锁的时间较短，则等待代价不高💩。

信号量

可用来解决互斥与同步问题。

信号量只能被两个标准的原语 wait() 和 signal() 访问，也可简写为 P() 和 V()，或者简称 P 操作和 V 操作。

P、V 操作都是低级的进程通信原语。

P 操作 — Passeren/Pass — wait() 原语
V 操作 — Verhoog/Increment — signal() 原语

原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件实现（如 TS 指令和 Swap 指令），在单处理机上可由软件通过屏蔽中断方法实现。

原语之所以不能被中断执行，是因为原语对变量的操作过程若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量 S。

相比于普通整型变量，对整型信号量的操作只有三种：初始化、wait 操作、signal 操作。

void wait(S) {  // 相当于进入区
    while (S <= 0);  // 忙等
    S--;  // 资源数够,占用一个资源
}

void signal(S) {  // 相当于退出区
    S++;  // 使用完后,释放一个资源
}

依然没有遵循 “让权等待”。

记录型信号量

一种不存在忙等现象的进程同步机制。

除了需要一个用于代表资源数目的整型变量 value 外，再增加一个进程链表 L，用于链接所有等待该资源的进程。

记录型信号量得名于采用了记录型的数据结构。

typedef struct {
    int value;  // 资源数目
    struct process *L;  // 等待该资源的进程链表
} semaphore;

void wait(semaphore S) {  // 相当于申请资源
    S.value--;
    if (S.value < 0) {
        add this process to S.L;
        block(this process);  // 自我阻塞
    }
}

void signal(semaphore* S) {  // 相当于释放资源
    S.value++;
    if (S.value <= 0) {
        remove a process P from S.L;
        wakeup(P);
    }
}

记录型信号量由于引入阻塞机制，遵循了 “让权等待”。

利用信号量实现互斥

semaphore S = 1;
P1() {
    ...
    P(S);
    critical section;
    V(S);
    ...
}
P2() {
    ...
    P(S);
    critical section;
    V(S);
    ...
}

利用信号量实现同步

例如，P2 中的语句 y 要在 P1 中的语句 x 执行完后才可以执行：

semaphore S = 0;
P1() {
    ...
    x;
    V(S);
    ...
}
P2() {
    ...
    P(S);
    y;
    ...
}

利用信号量实现前驱关系

semaphore a1 = a2 = b1 = b2 = c = d = e = 0;
S1() {
    ...;
    V(a1); V(a2);
}
S2() {
    P(a1);
    ...;
    V(b1); V(b2);
}
S3() {
    P(a2);
    ...;
    V(c);
}
S4() {
    P(b1);
    ...;
    V(d);
}
S5() {
    P(b2);
    ...;
    V(e);
}
S6() {
    P(c);
    P(d);
    P(e);
    ...;
}

经典同步问题

生产者-消费者问题

最简单的生产者-消费者问题

问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为 $n$ 的缓冲区。

只有当缓冲区不满时，生产者才能将消息放入缓冲区，否则必须阻塞，等待消费者从缓冲区中取出消息后将其唤醒；只有当缓冲区不空时，消费者才能从缓冲区中取出消息，否则必须阻塞，等待生产者将消息放入缓冲区后将其唤醒。

由于缓冲区是临界资源，因此必须互斥访问。
问题分析

互斥：缓冲区是临界资源。

同步：缓冲池满了就不能生产，缓冲池空了就不能消费。
解决思路

mutex 作为互斥信号量，用于控制互斥访问缓冲池，初值为 1。

信号量 full 用于记录缓冲池中的满缓冲区数，初值为 0。

信号量 empty 用于记录当前缓冲池中的空缓冲区数，初值为 n。

算法描述

semaphore mutex = 1, empty = n, full = 0;
producer() {
    while (1) {
        produce an item in nextp;  // 生产数据
        P(empty);
        P(mutex);
        add nextp to buffer;
        V(mutex);
        V(full);
    }
}
consumer() {
    while (1) {
        P(full);
        P(mutex);
        remove an item in nextp;
        V(mutex);
        V(empty);
        consume the item;  // 消费数据
    }
}

注意，对 empty 和 full 的 P 操作要放在对 mutex 的 P 操作之前，不然会出现消费者/生产者把自己锁在空/满缓冲池里阻塞，生产者/消费者怎么也进不去的画面（即要先同步后互斥）。

复杂点的生产者-消费者问题

问题描述

桌上有一盘，每次只能放一个水果。爸爸负责放苹果，妈妈负责放橘子。女儿只吃苹果，儿子只吃橘子。
问题分析

互斥：盘子是临界资源，爸妈互斥放，子女互斥拿。

同步：爸爸放橘子 → 女儿吃橘子，妈妈放苹果 → 儿子吃苹果。
解决思路

抽象为两个生产者和两个消费者被连接到大小为 1 的缓冲区上。

算法描述

semaphore plate = 1, apple = 0, orange = 0;
dad() {
    while (1) {
        prepare an apple;
        P(plate);
        put the apple on the plate;
        V(apple);
    }
}
mom() {
    while (1) {
        prepare an orange;
        P(plate);
        put the orange on the plate;
        V(orange);
    }
}
son() {
    while (1) {
        P(orange);
        take an orange from the plate;
        V(plate);
        eat the orange;
    }
}
daughter() {
    while (1) {
        P(apple);
        take an apple from the plate;
        V(plate);
        eat the apple;
    }
}

读者-写者问题

问题描述

有读者和写者两组并发进程，共享一个文件。

允许同时读，不允许同时写，也不允许在写的时候读。
问题分析

互斥：读写互斥，写写互斥（即写进程与其他读/写进程需要互斥访问文件）。
解决思路

写者与读写都互斥，只使用一把互斥锁 lock 即可。

读者只需与写者竞争锁 lock，因此设置一个信号量 count 为读者计数器（初值为 0），用它来判断当前是否有读者在读，再设置一把互斥锁 mutex 保护 count 的访问。

算法描述

读者优先

int count = 0;
semaphore lock = 1, mutex = 1;
writer() {
    while (1) {
        P(lock);
        writing;
        V(lock);
    }
}
reader () {
    while (1) {
        P(mutex);
        if (count == 0) {
            P(lock);  // 只有第一个读者需要获取lock锁
        }
        count++;
        V(mutex);
        reading;
        P(mutex);
        count--;
        if (count == 0) {
            V(lock);  // 直到最后一个读者再释放lock锁
        }
        V(mutex);
    }
}

一旦有读者在读，那后面来的读者可以无视写者直接插队。只有当没有读者排队时才能轮到写者，所以容易导致写者饥饿。

读写公平

不能再让读者无脑插队了，当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求。

只需再加一把互斥锁 queue 即可，读写进程一开始都要在 queue 的阻塞队列上排队。

int count = 0;
semaphore mutex = 1, lock = 1, queue = 1;
writer() {
    while (1) {
        P(queue);
        P(lock);
        writing;
        V(lock);
        V(queue);
    }
}
reader() {
    while (1) {
        P(queue);
        P(mutex);
        if (count == 0) {
            P(lock);
        }
        count++;
        V(mutex);
        V(queue);
        reading;
        P(mutex);
        count--;
        if (count == 0) {
            V(lock);
        }
        V(mutex);
    }
}

写者优先

semaphore readLock = 1;  // 互斥信号量,用于给读者上锁
semaphore writeLock = 1;  // 互斥信号量,用于给写者上锁
semaphore rmutex = 1;  // 互斥信号量,实现对readCount互斥访问
semaphore wmutex = 1;  // 互斥信号量,实现对writeCount互斥访问
int readCount = 0, writeCount = 0;
writer(){
    while(1){
    	P(wmutex);
    	writeCount++;
    	if (writeCount == 1) P(readCount);  // 第一个到达的写者对读者上锁
    	V(wmutex);
    	P(writeLock);
    	writing;
    	V(writeLock);
    	P(wmutex);
    	writeCount--;
    	if (writeCount == 0) V(readCount);  // 最后一个写者写完后对读者解锁
    	V(wmutex);
    }
}
reader(){
    while(1){
    	P(readLock);  // 每个读者达到时先对read上锁
    	P(rmutex);
    	readCount++;
    	if (readCount == 1) P(writeCount);  // 第一个到达的读者对写者上锁
    	V(rmutex);
    	V(readLock);  // 每个读者读之前对read解锁
    	reading;
    	P(rmutex);
    	readCount--;
    	if (readCount == 0) V(writeLock);  // 最后一个读者读完后对写者解锁
    	V(rmutex);
    }
}

哲学家进餐问题

问题描述
问题分析

相邻两个哲学家对其中间的叉子是互斥访问。

要避免死锁和饥饿。
解决思路

思路一：需要同时拿两个叉子，即当一名哲学家左右两边都有叉子时才允许他去拿。

思路二：对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。如对哲学家编号，奇数号先拿左边的叉子，偶数号先拿右边的叉子。

算法描述（思路一）

semaphore fork[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Pi() {
    do {
        P(mutex);
        P(fork[i]);
        P(fork[(i+1)%5]);
        V(mutex);
        eat;
        V(fork[i);
        V(fork[(i+1)%5]);
        think;
    } while (1);
}

吸烟者问题

问题描述

三个抽烟者进程和一个供应者进程。烟草、纸和胶水各一个可合成一支烟。供应者拥有三种材料，三个抽烟者各拥有一种资源。供应者每次提供两种材料各一个放到桌子上，拥有剩下一种材料的抽烟者就卷成一支烟并抽掉它。
问题分析

互斥：三个抽烟者对抽烟这个动作互斥。

同步：供应者与三个抽烟者分别同步。

算法描述

int num = 0;
semaphore offer1 = 0, offer2 = 0, offer3 = 0;
semaphore finish = 0;
P0() {
    while (1) {
        num = (num + 1) % 3;
        if (num == 0)
            V(offer1);  // 提供烟草和纸
        else if (num == 1)
            V(offer2);  // 提供烟草和胶水
        else
            V(offer3);  // 提供纸和胶水
        P(finish);  // 阻塞自己,防止过量提供材料造成多个吸烟者吸烟(实现吸烟互斥)
    }
}
P1() {  // 只有烟草
    P(offer3);
    V(finish);
}
P2() {  // 只有纸
    P(offer2);
    V(finish);
}
P3() {  // 只有胶水
    P(offer1);
    V(finish);
}

管程

信号量机制虽然方便有效，但每个要访问临界资源的进程都必须自备 PV 操作，使得大量同步操作分散在各个进程中，不仅给系统管理带来了麻烦，还可能因使用不当而导致系统死锁。

包含面向对象思想的进程同步工具 —— 管程(monitor) ，保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。

管程的定义

将表征共享资源的数据结构及其对该数据结构操作的一组过程（对共享资源的申请、释放等），包括同步机制，全都集中封装在一个对象内部，隐藏实现细节。这个对象即为管程的一个实例。

管程是语法范围，无法创建和撤销。

管程的组成

管程的名称；
局部于管程内部的共享数据结构说明；
对该数据结构设置初始值的语句；
对该数据结构进行操作的一组过程/函数。

在管程的设计中还要包含：

一把基于 mutex 的锁

确保进程互斥进入管程。
多个条件变量 condition

管程也是一种 “资源”。当一个进程进入管程后被阻塞，它应该释放管程，让其他进程有机会进入管程，而自己挂到临界资源的等待队列上。

将阻塞原因定义为条件变量 condition。

通常一个进程被阻塞的原因有多个，因此在管程中设置了多个条件变量，相应地会也会对应有多个等待队列。每个条件变量保存了一个等待队列，同时提供了 wait 和 signal 两个原子操作。

对于条件变量 x：

x.wait：当 x 对应的条件不满足时，该进程调用 x.wait 将自己挂在 x 条件的等待队列，并释放管程。此时其他进程可以使用该管程。

x.signal：当 x 对应的条件发生了变化，当前进程调用 x.signal 唤醒一个因 x 条件而阻塞的进程（若有）。

条件变量 vs 信号量

相似点：条件变量的 wait/signal 操作类似于信号量的 PV 操作，可以实现进程的阻塞/唤醒。

不同点：条件变量 “没有值”，仅实现了 “排队等待”，剩余资源数由管程中的共享数据结构记录；而信号量是 “有值” 的，信号量的值反映了剩余资源数。

死锁

概念

死锁的定义

多个进程因竞争资源而造成的一种僵局（互相等待别人手里的资源），使得各个进程都被阻塞，若无外力作用，这些进程都将无法向前推进。

死锁产生原因

对系统中数量不足以满足多个进程运行需要的不可剥夺资源的竞争。
进程推进顺序非法。

进程请求和释放资源的顺序不当、信号量使用不当。

死锁产生的必要条件（即需全部满足才可能死锁⚠）

互斥条件

进程要求对所分配的资源进行排他性使用。

即在一段时间内某资源仅为一个进程所占有。
不剥夺条件

进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己主动释放。
请求并保持条件

进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
循环等待条件

存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

资源分配图含圈（循环等待）而系统又不一定有死锁的原因：同类资源大于 1。

若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。

饥饿 vs 死锁

共同点：进程无法顺利向前推进。

不同点：

进入饥饿状态的进程可以只有一个，而因循环等待条件而进入死锁状态的进程却必须大于或等于两个。
发生饥饿的进程的状态可能是就绪态（长期得不到处理机），也可能是阻塞态；而发生死锁的进程的状态必定是阻塞态。

关系：死锁属于饥饿。饥饿并不代表系统一定死锁，但死锁一定导致饥饿。

死锁处理策略

死锁预防和避免死锁都属于事先预防策略，死锁预防的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低；避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

死锁预防

通过设立一些限制条件，破坏产生死锁必要条件中的一个或几个，让死锁无法发生。

破坏互斥条件

不太可行。有些资源做不到同时访问。

而且为了系统安全，很多时候还必须保护这种互斥性。

破坏不剥夺条件

当一个已保持某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已保持的所有资源，待以后需要时再申请。

实现起来比较复杂：

释放已获得资源可能造成前一阶段工作失效；
反复申请、释放资源既影响进程推进速度，又增加系统开销，进而降低系统吞吐量。

适用：状态易于保存和恢复的资源（如处理机的寄存器及内存资源），一般不能用于打印机之类的资源。

破坏请求并保持条件

要求进程在请求资源时不能持有不可剥夺资源，可以通过两种方法实现：

预先静态分配方法

即进程在运行前一次申请完它所需要的全部资源。

所需资源未满足前，不投入运行；运行期间，不许再提出其他资源请求。

在等待期间，进程不占有任何资源，从而破坏了 “保持” 条件；在运行期间，破坏了 “请求” 条件。

实现简单，但缺点也显而易见：

1）系统资源被严重浪费（有些资源仅在运行初期或快结束时才使用，甚至不一定使用）。

2）可能会导致饥饿现象。由于个别资源长期被其他进程占用，导致等待该资源的进程迟迟不能开始运行。
允许进程只获得运行初期所需的资源后，便可开始运行。进程在运行过程中再逐步释放使用完毕的资源，且只有在释放完已分配给自己的全部资源后，才能请求新的资源。

此方法改进了预先静态分配方法的缺点。

破坏循环等待条件

采用顺序资源分配法：系统中的所有资源按种类统一编号，申请时必须以上升的次序（即某进程前面申请过的资源种类以后不能再申请）。

系统要求申请进程：

同类资源（同一个编号）一次申请完；
申请不同类资源时，按各类设备的编号依次申请。

按此规则，已持有大编号资源的进程不可能再逆向申请小编号的资源，因此不会产生循环等待的现象。

存在问题：

编号必须相对稳定 → 限制了新类型设备的增加。
尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费。
按规定次序申请资源的方法必然会限制用户简单、自主地编程。

死锁避免

同样属于事先预防策略：在每次分配资源的过程中，都要分析此次分配是否会带来死锁风险，只有在不产生死锁的情况下，系统才会为其分配资源。

这种方法所施加的限制条件较弱，可以获得较好的系统性能。

系统安全状态

安全状态：至少有一个资源分配序列不会导致死锁。

不安全状态：系统中不存在任何一个安全序列，使得所有进程都能够运行完。

🚩不安全状态 ≠ 死锁状态，不安全状态 ≠ 死锁不可避免，安全状态 = 可避免死锁。

关于 “不安全状态 ≠ 死锁不可避免” 的解释：

1）不安全状态不意味着相关的所有进程都提出了新的资源申请，不意味着所有进程都因资源请求没有得到满足而进入阻塞态。只有当所有进程提出资源申请且全部进入阻塞态时，系统才处于死锁状态。

2）有的进程获取了一部分资源之后，并不是一定会在获得所需要的所有资源之后才会释放之前所占用的资源。

🚩死锁状态一定是不安全状态，安全状态不可能成为死锁状态。

银行家算法（一种死锁避免算法）

工作原理：银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行试分配，并对预分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免了死锁现象的发生。

数据结构描述：

可利用资源向量 Available
最大需求矩阵 Max
分配矩阵 Allocation
需求矩阵 Need

🍔Need = Max - Allocation

算法描述：

进程请求不超过其 Need，继续；否则出错。
进程请求不超过 Available，继续；否则让该进程等待。
系统进行试探性分配（设定分配后为 T 时刻）。
系统执行安全性算法，检测 T 时刻系统是否处于安全状态。若是，则正式分配；若不是，则分配作废，让该进程等待。

安全性算法（银行家算法的核心）：

找 T 时刻 Available 能满足 Need 的不在安全序列的进程，将该进程 Allocation 加到 Available，并将其放进安全序列。
循环执行上一步，若到最后所有进程都能在安全序列中，则 T 时刻处于安全状态。

死锁检测和解除

不采取任何限制性措施，允许进程在运行过程中发生死锁，只检测当前系统有没有发生死锁，若有则采取措施解除死锁。

资源分配图

用圆圈节点表示一个进程，用框节点表示一类资源，用框节点中的一个圆表示该类资源中的一个资源。

从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的有向边称为分配边，表示该类资源已有一个资源分配给了该进程。

死锁定理

系统状态 S 为死锁状态的条件是：当且仅当 S 状态的资源分配图是不可完全简化的。

资源分配图的简化：找出既不阻塞又不孤立的进程（即该进程申请的资源够给它的），消去它所有的请求边和分配边，使之成为孤立的结点。若能消去图中所有的边，则称该图是可完全简化的。

死锁解除

一旦检测出死锁，就应立即采取相应的措施来解除死锁。死锁解除的主要方法有：

资源剥夺法

挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。

但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。
撤销进程法

强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。

撤销的原则可以按进程优先级和撤销进程代价的高低进行。

这种方式实现简单，但付出的代价可能很大，因为有些进程可能已经接近结束，一旦被终止，以后还得从头再来。
进程回退法

让一个或多个死锁进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。

要求系统保持进程的历史信息，设置还原点。

在资源分配图中，用死锁定理化简后，还有边相连的那些进程就是死锁进程。

死锁避免 vs 死锁检测

死锁避免需要在进程的运行过程中一直保证之后不可能出现死锁，因此需要知道进程从开始到结束的所有资源请求。

死锁检测检测某个时刻是否发生死锁，不需要知道进程在整个生命周期中的资源请求，只需知道对应时刻的资源请求。

刷题总结

周转时间从作业到达时间（进入后备队列）开始算起。

多数题计算周转时间的题目不考虑作业调度的排队时间，只关注低级调度，或者说不用作业调度，默认作业到达时间等于作业进入内存/进程进入就绪队列的时间。

高级调度与低级调度全部考虑的题目：王道 P82 06。
运行时甘特图示例

用信号量机制实现互斥时，互斥信号量的初值为 1；

用信号量机制实现前驱关系时，信号量的初值为 0；

用信号量机制实现进程同步时，信号量的初值由用户确定。
关于生产者-消费者问题的唤醒操作：生产者有可能唤醒其他生产者或消费者，消费者也有可能唤醒其他生产者或消费者。
哲学家进餐问题与死锁

1）采取 “同时检查两支筷子是否可用” 的方法属于死锁预防—破坏请求并保持条件—预先静态分配法。

预先静态分配法的缺点是会造成系统资源的浪费和导致饥饿现象，这是相对于系统运行期间的所有进程而言。一般肯定是会导致饥饿，但是否会导致饥饿还需要具体分析。预先静态分配法是在 “个别资源长期被其他进程占用” 的情况下才会导致饥饿现象，而哲学家进餐问题这里不会出现，除非特别说明，哲学家进餐默认不会很久。会导致资源浪费是因为可能有一些空闲筷子无法使用。

2）采取 “奇数号哲学家先拿左筷子，偶数号哲学家先拿右筷子” 或 “同时存在左撇子、右撇子哲学家” 或 “限制允许拿起筷子的哲学家数量” 等方法都属于死锁预防—破坏循环等待条件。
进程回退 → 释放资源 √

释放资源 → 进程回退 ×
m 个同类资源供 n 个并发进程共享（即这些进程至少申请 1 个），采用银行家算法分配资源，为保证系统不发生死锁，则各进程的最大需求量之和应为 m+n-1，即 n-1 个进程申请 1 个，剩下 1 个进程申请 m 个。
n 个并发进程共需要 x 个同类资源，则该系统必然不会发生死锁的最少资源数是 n(x-1) + 1。
判断某个时刻系统状态是否安全时首先把 Need 矩阵列出来。

可以不用一个进程一个进程看，若能满足多个（不是总和，是单独每个都满足），则一次性把它们的资源都释放，这样可以简化计算。
常见的银行家算法考题只考安全性算法，即判断某个时刻系统状态是否安全。

银行家算法不只是安全性算法，安全性算法是用在试探性分配某进程提出的一次资源申请后，用于判断满足其请求后是否会导致系统不安全。

试探性分配也是有条件的。另外应该知道该进程此次申请的资源数不一定就是其尚需的最大资源量，不要做题做傻了。

王道 P162 应用题 06。
资源分配图，已满足的申请边不要画了，有相应的分配边就行。

王道 P163 09。

进程与线程

进程的概念和特征

进程的组成

进程控制块 PCB

程序段

数据段

进程的状态与转换

进程控制

创建

终止

阻塞和唤醒

进程间通信

共享存储

消息传递

管道通信

信号

线程概念和多线程模型

基本概念

线程的组织与控制

线程的实现方式

线程的实现

线程库

处理机调度

调度的概念

调度的目标

调度的实现

调度程序/调度器

进程调度的方式

进程调度的时机

线程的调度

闲逛进程 idle

典型的调度算法

进程切换

上下文

模式切换

上下文切换

多处理机调度

基本概念

进程分配方式

ASMPS 中的进程分配方式

SMPS 中的进程分配方式

进程/线程调度方式

自调度方式

成组调度方式

评价调度性能的因素

任务流时间

调度流时间

平均流时间

处理机利用率

同步与互斥

进程同步的基本概念

实现临界区互斥的基本方法

软件实现方法（标志）

硬件实现方法（低级方法/元方法）

互斥锁

信号量

经典同步问题

生产者-消费者问题

读者-写者问题

哲学家进餐问题

吸烟者问题

管程

死锁

概念

死锁处理策略

死锁预防

死锁避免

死锁检测和解除

刷题总结

微信扫一扫：分享