进程、线程基础知识
一、进程
我们编写的代码是存在硬盘的静态文件，编译后生成二进制可执行文件，当我们运行这个可执行文件后，他会被装载到内存中，接着 CPU 会执行这个执行文件的每一行指令，而 这个运行中的程序，被称为【进程】
为了优化进程执行的速度，我们的 CPU 会频繁的切换进程，比如：
并行和并发的区别在哪呢？
1. 进程的状态
传统来讲，对于进程，已知有：运行 - 暂停 - 运行 的活动规律。
所以，一个进程的活动期间，如图所示：
- 就绪状态：可运行，由于其他进程处于运行状态而停止运行
- 运行状态：该进程时刻占有 CPU
- 阻塞状态：该进程等待某一事件的发生（如等待输入/输出操作的完成）而暂时停止运行。这个时候，即使给他CPU控制权，也无法运行。
当然，进程还有 创建、结束 两个状态：
我们细节性的描述下状态变迁的过程：
- **NULL --> 创建状态：**一个新进程被创建的第一个状态
- **创建状态 --> 就绪状态：**当一个进程被创建完成并完成初始化后，一切准备就绪
- **就绪状态 --> 运行状态：**当前进程被操作系统的进程调度器选中，得到 CPU 的时间片，分配给 CPU 运行
- **运行状态 --> 阻塞状态：**当进程请求某个事件且必须等待时，例如 请求 I/O 事件
- **运行状态 --> 就绪状态：**当前 CPU 分配给该进程的时间片已用完
- **运行状态 --> 结束状态：**当前进程已经运行完成或出错
- **阻塞状态 --> 就绪状态：**当前进程等待的事件已完成，进程由阻塞状态切换到就绪状态
- 另外，为了防止 大量处于阻塞的线程影响内存的使用，需要一个新的状态：来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态，继而变成如下：
2. 进程的控制结构
在操作系统中，使用 进程控制块（Process control block，PCB） 的数据结构来描述进程的
PCB 是进程存在的唯一标识，，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。
PCB 具体包含什么信息呢？
进程描述信息
- 进程标识符：每一个进程拥有一个标识符
- 用户标识符：进程归属的用户
进程控制和管理信息
- 进程当前状态：如 new、ready、running、waiting等状态
- 进程优先级：进程抢占 CPU 的优先级
- 资源分配清单
- 有关内存地址空间或虚拟空间的信息，使用的 I/O 设备
CPU相关信息
- CPU 各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行
- PCB 是如何组织的呢？
以链表的方式，把具有相同状态的进程连接在一起，组成各种队列。
- 将所有处于有绪状态的进程链在一起，称为就绪队列
- 因等待事件而处于阻塞状态的进程链在一起，称为阻塞队列
除了链接的组织方式，还有索引方式，他的工作原理：将同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。
因为我们的进程不断的创建、销毁，所以链表更加灵活的实现插入和删除的功能。
3. 进程的控制
我们来看一下进程创建、终止、阻塞、唤醒的过程
第一步：创建进程
操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源，当子进程被终止时，会将资源返还给父进程。。同时，终止父进程的同时也会终止其所有的子进程（PS：这里不同的操作系统实现不同）
创建进程的过程：
- 为新进程分配唯一的进程标识号，申请一个空白的PCB
- 为进程分配资源，如果资源不足，进程进入等待状态，等待资源
- 初始化 PCB
- 将当前的进程放入到 就绪队列 中，等待被 CPU 调度运行
第二步：终止进程
进程可以有 3 种终止方式：正常结束、异常结束以及外界干预（信号 kill 掉）。
终止进程的过程：
- 查找该进程的PCB
- 如果处于执行状态，则立即终止执行，并将 CPU资源分配给别的进程
- 如果拥有子进程，则终止子进程
- 将该进程所拥有的资源返还给父进程或操作系统，然后将其 PCB 从队列中删除掉
第三步：阻塞进程
当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。
阻塞进程的过程：
- 找到将要被阻塞进程标记的 PCB
- 如果该进程为运行状态，保护其现场，变为阻塞状态，停止运行
- 将该 PCB 插入到阻塞队列中去
第四步：唤醒进程
如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。
唤醒进程的过程：
- 在阻塞队列中找到该进程的 PCB，将其从阻塞队列移除，并将其置为就绪状态
- 放入就绪队列中，等待 CPU 的调度
4. 进程的上下文切换
各个进程共享CPU的资源，进程之间互相切换，让不同的进程可以在CPU执行，一个进程切换到另一个进程运行，称为：进程的上下文切换
CPU 上下文切换是什么？
我们的任务是交给 CPU 来执行的，每个任务运行之前，CPU 需要知道任务从哪里加载，又从哪里开始运行。
所以，操作系统需要事先帮 CPU 设置好 CPU 寄存器和程序计数器
- CPU 寄存器：存储指令、数据的地方
- 程序计数器：存储当前CPU执行指令的地址或是即将执行的下一条指令的地址
CPU的上下文指的就是CPU寄存器和程序计数器及其所在的环境，而上下文的切换指的就是：CPU保存当前任务的寄存器和程序计数器的信息，然后加载新的寄存器和程序计数器，最后跳转到该程序计数器所指的新的指令位置，开始新的任务。
当然，这里提到的任务，主要包含进程、线程、中断。
所以，根据任务的不同，把CPU的上下文切换分为：进程上下文切换、线程上下文切换、中断上下文切换
进程的上下文切换到底是切换什么呢？
进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。
发生进程上下文切换的场景？
- 进程分配的时间片已经用完，需要轮换到下一个进程
- 系统当前的资源不足，不足以支持该进程的运行
- 进程通过
sleep将自己主动挂起 - 比自己更高优先级的进程需要运行时
- 发生硬件中断时，当前进程会被挂起
二、线程
早期科学家们以进程为基本单位，后来发现进程的一些资源过于庞大，不太利于维护，于是出现了更小能独立运行的单位： 线程
1. 为什么使用线程？
我们举个例子，假设你要编写一个视频播放器软件，那么该软件功能的核心模块有三个：
- 从视频文件当中读取数据（I/O）
- 对读取的数据进行解压缩（CPU）
- 把解压缩后的视频数据播放出来（显卡）
对于单进程的实现方式，我想大家都会是以下这个方式：
main(){ while(1){ // 读取数据，主要使用I/O进行操作 Read(); // 数据解压缩，主要使用CPU进行操作 Decompress(); // 播放视频数据 Play(); } }
这样会造成 CPU解压缩这个操作，有可能在等待着读取数据的进行，毕竟读取数据是一个I/O操作，有可能会进行堵塞。同样，由于不是并发执行，浪费了资源的使用效率。
而多并发的进程也会存在一下问题：
- 资源开销大，毕竟需要创建虚拟内存，分配资源，切换PCB所在的队列类型，还有回收资源，保存现场
- 进程间如何频繁进行通信，共享数据？
2. 什么是线程？
线程是进程当中的一条执行流程。
同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。
3. 线程与进程的比较
- 进程是资源分配的单位，线程是CPU调度的单位
- 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如：寄存器和栈
线程相对进程能减少开销，体现在：
进程在创建的过程中，需要资源管理信息，比如：内存管理信息、文件管理信息等，而线程仅仅是共享他们
同一进程线程切换比进程切换的开销小，因为线程占用同样的虚拟内存，不需要重新切页表，只需要保存自己的寄存器和栈即可
由于同一进程的各线程共享内存和文件资源，在数据传递的过程中，不需要内核的参与，效率变高
4. 线程的上下文切换
操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。
对于线程和进程，我们可以这么理解：
当进程只有一个线程时，可以认为进程就等于线程；
当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；
另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。
程上下文切换指什么？
- 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
- 当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；
5. 线程的实现
- 用户线程：在用户空间进行实现，由用户控制 TCB 的信息。
- 内核线程：在内核中实现的线程，由内核控制
- 轻量级线程：内核支持用户线程
三、调度
之前讲过的进程时间片用完之后，怎么分配时间片就被称为：调度算法
1. 调度时机
- 就绪态 —> 运行态
- 运行态 —> 阻塞态
- 运行态 —> 结束态
根据时钟的中断可以把调度算法分为两类：
- 非抢占式中断调度算法：挑选一个进程，直到该进程运行完毕
- 抢占式调度算法：每个进程分配相应的时间片，当时间片用完之后，轮到下一个进程
2. 调度原则
原则一：提高 CPU 利用率，这种发送 I/O 事件致使 CPU 空闲的情况下，调度程序需要从就绪队列中选择一个进程来运行。
原则二：提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。
原则三：如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生。
原则四：就绪队列中进程的等待时间也是调度程序所需要考虑的原则。
原则五：对于交互式比较强的应用，响应时间也是调度程序需要考虑的原则。
3. 调度算法
3.1 先来先服务（First Come First Serve, FCFS）
每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
3.2 最短作业优先（Shortest Job First, SJF）
优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。
3.3 高响应比优先 （Highest Response Ratio Next, HRRN）
每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：
.4 时间片轮转（Round Robin, RR）
每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。
一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值。
3.5 最高优先级（Highest Priority First，HPF）
希望调度程序能从就绪队列中选择最高优先级的进程进行运行
进程的优先级分为，静态优先级和动态优先级：
- 静态优先级：进程创建的时候，已经确定了优先级
3.6 多级反馈队列（Multilevel Feedback Queue）
**多级反馈队列（*Multilevel Feedback Queue*）**是「时间片轮转算法」和「最高优先级算法」的综合和发展。
顾名思义：
- 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
- 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；
来看看，它是如何工作的：
- 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
- 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
- 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
- 可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。
