（一）进程与线程
1. 进程和线程基本概念
1.1. 前趋图和程序执行
前趋图：有向无环图（DAG），约定不同进程的执行顺序；
程序的执行
顺序执行：
各个程序段按照顺序依次执行，约定用 I 代表输入操作，C 代表计算操作，P 代表打印操作；可用前趋图描述各个程序段的执行关系；
性质：顺序性，封闭性，可再现；
顺序性：字面意思；
封闭性：程序执行时，独占系统资源，系统资源状态只由程序改变，执行结果不受外界影响；
可再现性：程序的环境和初始条件相同时，无论中途是否暂停，执行结果都相同；
并发执行：
实例：有 4 道 “I-C-P" 程序时，前趋图如图所示：
从图中可以看出，
， 等程序段没有约束关系，可以并发执行 性质：间断性，非封闭性，不可再现性；
间断性：字面意思，一个程序可能在执行途中暂停，让其他程序段先执行；
非封闭性：系统资源非单一程序占有，程序执行途中，系统状态可能被其他程序改变；
不可再现性：对于单个程序，即使环境和初始条件相同，因为其他并发程序的变化和执行过程的变化，重复执行时不一定保证结果相同；
1.2. 进程的概念
为了使程序能够正确地并发执行，引入 “进程” 的概念，存储程序运行信息，对并发执行的程序加以描述和控制；
进程的定义：
进程是程序的一次执行；
进程是一个程序及其数据在处理机上顺序执行时所发生的活动；
进程是具有独立功能的程序在一个数据集合上运行的过程；
进程是系统资源分配和调度的独立单位；
进程的特征：
动态性：进程的地址空间是动态的，包含：代码，数据，系统控制信息；
并发性：不同进程共享内存，并发执行；
独立性：不同进程的地址空间互相独立；
异步性：各个进程按照独立的，不可预知的速度向前执行；
进程的基本属性：
可拥有资源的基本单位：包括内存空间（存放程序，数据等）和系统资源（文件等）
可独立调度和分派的基本单位：系统根据进程唯一的 PCB 感知其存在，调度 CPU 执行；
- PCB 还可用于存放进程的断点信息，在进程恢复运行时复原现场数据；
进程并发执行的时空开销：
创建进程：分配资源，建立 PCB；
销毁进程：回收资源，撤销 PCB；
切换进程：保留当前进程环境，设置 CPU 环境为新进程的环境；
1.3. 线程的概念
为了尽量减少切换进程的开销，引入 “线程” 的概念，是在进程内的概念；
现代 OS 中，线程继承了进程调度分派的职能，进程只保有资源分配的职能；
性质：
切换：一进程中线程的切换并不会引起进程切换，不同的则会引起进程切换；
并发：同一进程内可有多个线程，这多个线程可并发执行；
资源：单个线程并不拥有系统资源（仅有一小部分必要资源）；线程可以访问所在进程的全部资源；
独立：相对进程而言独立性低，不能脱离进程独立执行；
开销：线程切换（同进程）的开销远小于进程切换；
多处理器：支持多核 CPU，多处理器系统；
1.4. 进程/线程的状态及转换
进程的三种基本状态：就绪（Ready），执行（Running）和阻塞（Block）；
就绪（Ready）：资源分配完毕，等待调度 CPU 执行；
执行（Running）：正在执行中；
阻塞（Block）：因为 CPU 以外的原因（如 IO），使得进程不能继续执行；
三状态的转换：
- 注意：从阻塞态恢复时，是先恢复到就绪态，而不是直接到执行态
创建状态和终止状态
创建：申请空白 PCB > 写入控制信息 > 分配运行时资源 > 转为就绪态，并加入就绪队列；
- 若资源不够，将卡在分配资源这一步，不能进入就绪态；
终止：OS 进行处理（回收资源等）> PCB 清空 > 回收空白 PCB
- 进入终止态的程序不能再执行，但是 OS 会保留一个记录（记录退出码和运行时间等数据），方便其他进程读取，完毕后将清空 PCB 并回收；
挂起（Suspend）状态
挂起操作的原因：(1) 用户需要，(2) 父进程操作，(3) 负载调节需要，(4) OS 调度；
挂起操作会将进程数据从内存移到外存，其逆操作激活（Active）将外存的数据拉回内存；
加入挂机操作后的状态转移图
2. 线程的实现方式
2.1. 线程的分类
用户级线程
内核支持线程
2.2. 内核支持线程（KST，Kernel Supported Threads）
概念：由 OS 内核支持运行的线程
其创建，撤销，切换等操作是在内核空间完成；
设置有线程控制块 TCB，用以被内核感知和调度；
优点：主要体现在多处理器 OS
多处理器 OS 中，内核能够同时调度同一进程中多个线程并行执行；
一个进程中，某线程阻塞不影响其他线程正常执行，也不影响其他进程中的线程；
KST 的数据结构和堆栈小，切换开销小，切换快；
内核本身也可以是多线程实现，提高 OS 执行效率；
2.3. 用户级线程（ULT，User Level Threads）
概念：用户层面的线程
其创建，撤销，切换等操作均在用户空间完成，与内核无关；
无法被内核感知，可以同时存在大量 ULT；
优点
线程切换无需进入内核态；
线程调度算法可由进程自定义；
由于其实现与 OS 内核无关，因此跨平台性，通用性好；
- ULT 线程管理代码是属于用户程序的一部分，所有应用程序都可以共享；
缺点
阻塞问题：由于系统层面并不是真正的多线程调度，可能发生某线程执行系统调用被阻塞，导致整个进程阻塞，进而其他线程也被阻塞的局面；
在 OS 层面，不能充分得到多 CPU 资源的分配，利用多 CPU 的性能；
2.4. 组合模式
建立不同的线程模型，将 KST 和 ULT 相互对应；
2.5. 用户级线程 ULT 的实现
运行时系统（Runtime System）：提供一个库或集合，实现线程的创建，撤销，同步，通信，调度等功能；
内核控制线程：又称轻型进程（LWP，Lightweight Process）：LWP 类似线程，可访问所属进程的全部资源，可被 OS 独立调度，可调用系统接口；因此将一个 ULT 对应到一个 LWP 即可；
3. 进程和线程的组织与控制
3.1. 进程控制块 PCB
作用
作为独立运行基本单位的标志；
保存断点信息，实现进程间断运行；
提供 OS 管理和调度进程所需的信息；
进程间的同步与通信；
组成：4 个方面
进程标识符：用于唯一标识一个进程，包含内部和外部标识符；
外部标识符（Name）：用户可见可读的进程名称，不用于 OS 识别；
内部标识符（PID）：一个整数，用于 OS 识别进程；
处理机状态（上下文）：主要是寄存器的内容
通用寄存器（AX，BX，CX 等）；
指令计数器 PC；
程序状态字 PSW；
栈指针 SP；
调度信息：
当前进程状态和进程优先级；
其他信息（如 CPU 时间和已等待时间等），主要用于调度算法；
事件：指进程由执行变为阻塞所发生的事件（原因）
控制信息：
程序和数据的地址；
用于进程同步和通信的数据结构等（如消息队列，信号量）；
资源清单（全部资源清单和已分配资源清单）；
指向调度队列中上一个和下一个 PCB 的指针（双向链表）；
3.2. 线程控制块 TCB
- 包括：(1) 线程标识符，(2 )寄存器状态，(3) 线程运行状态；(4) 线程优先级，(5) 线程专用存储器，(6) 信号屏蔽；
3.3. PCB 的组织方式
线性方式：用数组（线性表）存放所有 PCB 信息，将首地址存放在专有区域中；
- 该方式实现简单，开销小，但查找 PCB 时需要扫描整个数组，只适合进程数不多的系统；
链接方式：将具有相同状态的 PCB 链接成一个队列，形成就绪队列，阻塞队列等；
就绪队列可按照优先级进行排序；
阻塞队列可以按照阻塞原因细分成多个队列；
索引方式：根据 PCB 状态的不同，建立多张索引表，表中存储 PCB 的地址；
3.4. 进程的控制
包括：进程的创建和销毁，进程状态的切换等；
实现：由 OS 内核中的**原语（原子操作）**实现；
原语：由若干条指令组成，用于完成特定的操作；原语一旦开始，不可中断，是一个不可分割的基本单位；
原语在管态下执行，常驻内存；
3.5. 进程的创建
进程的层次结构：OS 中，允许进程创建另一个进程，创建进程的称为父进程，被创建的称为子进程，子进程又可以创建其他进程，最终形成一棵树的结构；
进程图：描述进程间关系的有向树；
导致一个进程创建另一个的经典 4 类事件：用户登录，作业调度，提供服务，应用请求；
步骤：申请空白 PCB > 分配系统资源 > 初始化 PCB > 插入就绪队列；
3.6. 进程的终止
引起进程终止的事件：正常结束，异常结束，外界干预；
步骤：
检索对应 PCB，读取进程状态；
若该进程处于执行，则立即终止，并置位调度标志，指示终止进程后重新调度；
若有子进程，也要予以终止；
将该进程资源全部归还父进程或系统；
将对应 PCB 从队列中移出，等待其他进程读取相关信息（此时不清空和回收 PCB）；
3.7. 进程的阻塞和唤醒
引起阻塞和唤醒的事件：有以下基本的 4 类事件
向 OS 请求资源失败；
等待某个操作完成（如 IO）；
等待要处理的数据和任务；
进程阻塞是一种进程主动行为，且不是因为 CPU 原因；
阻塞过程：进程状态改为阻塞 > 将 PCB 加入阻塞队列 > 重新调度，切换进程；
唤醒过程：将 PCB 从阻塞队列中移除 > 进程状态改为就绪 > PCB 插入就绪队列；
3.8. 进程的挂起和激活
挂起过程：活动就绪 > 静止就绪，活动阻塞 > 静止阻塞，内存 > 外存；
激活过程：反过来即可；
4. 进程间通信
4.1. 进程间通信的类型
共享存储器系统（Shared Memory System）：又分为共享数据结构和共享存储区；
管道通信系统（Pipe）
管道：一个用于连接读进程和写进程的共享文件，称为 pipe 文件；
首创于 UNIX 系统，由于能够有效传输数据，被引入其他 OS；
管道通信的机制：
互斥：同一时刻只能有一个进程进行读写，其他进程必须等待；
同步：当写进程写入了一定量的数据，应当先睡眠等待，等到读进程读取一定量的数据后再继续写入；当读进程将数据读完时，也应先睡眠等待，等到写进程写入后再继续读取；
确定都写进程双方存在；
消息传递系统（Message Passing System）
进程间不借助共享数据区，而以格式化的消息为单位，借助 OS 提供的通信原语，进行数据交换；可分为两类：
直接通信方式：使用 OS 的通信原语；
间接通信方式：借助中间实体；
信箱通信
信箱是一种数据结构，包含：信箱头和信箱体；
信箱可由 OS 提供，也可以由用户进程创建，因此可分为：(1) 私有邮箱，(2) 公有邮箱，(3) 共享邮箱；