一、进程
1.概述
我们编写的代码只是一个存储在硬盘上的静态文件，通过编译后生成二进制可执行文件后，它会被装载到内存之中，接着CPU会执行程序中的每一条指令，那么这个运行中的程序，就被称为进程
2.进程的状态
2.1.基本状态
在一个进程的活动期间至少具备三种基本状态，即运行状态，就绪状态，阻塞状态
各个状态的意义：
- 运行状态：该时刻进程占用CPU
- 就绪状态：可运行，由于其他进程处于运行状态而停止运行
- 阻塞状态：不可运行，该进程正在等待某一事件发生（I/O操作的完成）而暂时停止运行
2.2.完整基本状态
进程的状态变迁：
- NULL -> 创建状态：一个新进程被创建时的第一个状态
- 创建状态 -> 就绪状态：当新进程被创建完成并吃初始化之后，一切准备就绪后，变为就绪态
- 就绪状态 -> 运行状态：处于就绪状态的进程被操作系统的进程调度器选中之后，分配给CPU运行该进程
- 运行状态 -> 结束状态：当程序运行完成或者出错时，会被操作系统结束该进程
- 运行状态 -> 就绪状态：分配的运行时间片用完，操作系统会把该进程变为就绪状态，接着从就绪态中选择一个进程执行
- 运行状态 -> 阻塞状态：当进程请求某个时间必须等待时，比如I/O操作
- 阻塞状态 -> 运行状态：当进程等待的事件完成时，从阻塞态变为运行态
2.3.虚拟内存系统的完整状态
如果有大量处于阻塞状态的进程，进程可能会占用着物理内存，毕竟物理内存是有限的，被阻塞状态的进程占用着物理内存就是一种浪费内存的行为
所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存换出硬盘，等需要再次运行的时候，再从硬盘换出到物理内存
那么需要一个新的状态，来描述进程没有占用物理内存空间的情况，这个状态就是挂起状态
另外，挂起状态可以分为两种：
- 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
- 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；
3.进程的状态控制
在操作系统中，用进程控制块PCB数据结构来描述进程的
PCB是进程的唯一标识，随着进程的创建而创建，随着进程的消失而消失
3.1.PCB的结构
进程描述信息：
- 进程标识符：标识各个进程，每个进程都有唯一的标识符
- 用户标识符：进程归属的用户，主要为共享和保护服务
进程控制和管理信息：
- 进程当前的状态：如new, ready, running等等
- 进程优先级：进程抢占CPU时的优先级
资源分配清单：
- 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的I/O设备信息
CPU相关信息：
- CPU中各个寄存器的值，当进程被切换时，CPU的状态信息都会被保存在相应的PCB中，一边进程重新执行时，能从断点处继续执行
3.2.PCB如何组织
链表：通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列
例如：
- 将所有处于就绪状态的进程链在一起，称为就绪队列；
索引表：同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。
4.进程的控制
我们熟知了进程的状态变迁和进程的数据结构 PCB 后，再来看看进程的创建、终止、阻塞、唤醒的过程，这些过程也就是进程的控制。
1.创建进程
操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程的所有资源
创建过程如下：
- 申请一个空白的PCB，并且填写一些控制和管理进程的信息，比如进程的唯一标识等；
- 为该进程分配运行时所必须的资源，比如内存资源
- 将PCB插入到就绪队列，等待进程的调度
2.终止进程
进程可以有3种终止方式：正常结束、异常结束以及外界干预
当子进程被终止时，其在父进程所继承的资源应当归还于父进程，而当父进程被终止时，该父进程的子进程就会变成孤儿进程，会被1号进程收养，并由1号进程对它们完成状态收集工作
终止进程的过程如下：
- 查找需要终止的进程的PCB
- 如果处于运行状态，则立即终止该进程的运行，并将CPU资源分配给其他进程
- 如果还有子进程，则应将该进程的子进程交给一号进程接管
- 则该进程所有的资源应当归还操作系统
- 将其从PCB所在队列删除
3.阻塞队列
当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。
阻塞进程的过程如下：
- 找到将要被阻塞进程标识号对应的 PCB；
- 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
- 将该 PCB 插入到阻塞队列中去；
4.唤醒进程
进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的。
如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。
唤醒进程的过程如下：
- 在该事件的阻塞队列中找到相应进程的 PCB；
- 将其从阻塞队列中移出，并置其状态为就绪状态；
- 把该 PCB 插入到就绪队列中，等待调度程序调度；
5.进程的上下文切换
各个进程之间是共享CPU资源的，在不同的时候进程之间需要切换，让不同的进程可以在CPU执行，那么这个一个进程切换到另一个进程运行，称为进程的上下文切换
5.1.CPU的上下文切换
大多数操作系统都是多任务，通常支持大于CPU数量的任务同时运行；实际上，这些任务并不是同时运行的，只是因为系统在很短的时间内，让各个任务分别在CPU运行，于是就造成同时运行的错觉
任务是交给CPU运行的，那么在每个任务运行前，CPU需要知道任务从哪里加载，又从哪里开始运行
所以，操作系统需要事先帮CPU设置好CPU寄存器和程序计数器
CPU寄存器：CPU内部一个容量小，速度极快的内存
程序计数器：存储CPU正在执行的指令位置、或者即将执行的下一条指令位置
所以说，CPU寄存器和程序计数是CPU在运行任何任务前，所必须依赖的环境，这些环境就叫CPU上下文
那什么是CPU上下文切换呢？
CPU上下文切换就是先把前一个任务的CPU上下文保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳到程序计数器所指的新位置，运行新任务
系统内核会存储保持下来上下文信息，当次任务再次被分配给CPU运行时，CPU会重新浇在这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行
5.2.进程的上下文切换
进程是由内核管理和调度的，所以进程的切换只能发生在内核态
进程的上下文切换不仅包含了 虚拟内存、栈、全局变量等用户空间的资源，还包括了 内核堆栈、寄存器等内核空间的资源
通常，会把交换的信息保存在进程的PCB，当要运行另外一个进程的时候，我们需要从这个进程的PCB取出上下文、然后恢复到CPU中，这使得这个进程可以继续执行；
大家需要注意，进程的上下文开销是很关键的，我们希望它的开销越小越好，这样可以使得进程可以把更多时间花费在执行程序上，而不是耗费在上下文切换。
5.3.发生在那些场景？
- 当进程在系统资源不足(比如内存不足)时
- 当进程通过睡眠函数sleep()这样的方法将自己主动挂起时
- 当有优先级更高的进程运行时
- 发生硬件中断时
- 在公平调度时，当进程分配的时间片耗尽时
二、线程
1.概述
线程是进程当中的一条执行流程
同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈、这样可以确保线程的控制流是相对独立的
线程的优缺点？
线程的优点：
- 一个进程中可以同时存在多个线程
- 各个线程之间可以并发执行
- 各个线程之间可以共享地址空间和文件等资源
线程的缺点：
- 当进程中的一个线程崩溃时，会导致其所属的所有线程崩溃
2.线程与进程的比较
线程与进程的比较如下：
- 线程是资源分配的单位，线程是CPU调度的单位
- 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
- 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系
- 线程能减少并发执行的时间和空间开销
线程相比进程能减少开销，体现在：
- 线程的创建时间比进程快；进程的创建需要资源管理信息，而线程不需要，而是共享它们；
- 线程的终止时间要比进程快，因为线程释放的资源相比进程少很多
- 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间
- 由于同一个进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了
所以，不管是时间效率，还是空间效率线程比进程都要高
3.线程上下文切换
线程是调度的基本单位，而进程则是资源拥有的基本单位
所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源
对于线程和进程，我们可以这么理解：
- 当进程只有一个线程时，可以认为进程就等于线程；
- 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；
另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。
线程上下文切换的是什么？
这还得看线程是不是属于同一个进程：
- 当两个线程不是属于同一个进程，则切换的过程就跟进程上下位切换一样；
- 当两个线程属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据，寄存器等不共享的数据
4.线程的实现
主要有三种线程的实现方式：
- 用户线程（User Thread）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理
- 内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；
- 轻量级进程（LightWeight process）：在内核中支持用户线程
三、调度
选择一个进程运行这一功能是在操作系统中完成的，通常称为调度程序
1.调度时机
在进程的声明周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度
比如，以下状态的变化都会触发操作系统的调度：
- 从就绪态 -> 运行态：当进程被创建时，会进入到就绪队列，操作系统会从就绪队列选择一个进程运行；
- 从运行态 -> 阻塞态：当进程发生 I/O 事件而阻塞时，操作系统必须选择另外一个进程运行；
- 从运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外一个进程运行；
另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类
- 非抢占式调度算法挑选一个进程，然后让该进程运行知道被阻塞，或者该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情
- 抢占式调度算法挑选一个进程，，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。
2.调度原则
- CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
- 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
- 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
- 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
- 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。
3.调度算法
3.1.进程调度算法
3.1.1.先来先服务调度算法（FCFS）
最简单的一个调度算法：First Come First Severd
顾名思义，先来先到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或者被阻塞，才会继续从队列中选择第一个进程接着运行
这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。
3.1.2.最短作业优先调度算法（SJF）
最短作业优先（Shortest Job First）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。
这显然对长作业不利，很容易造成一种极端现象。
比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。
3.1.3.高响应比优先调度算法（HRRN）
前面的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和长作业。
那么，高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。
每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：
从上面的公式，可以发现：
- 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行；
- 如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；
3.1.4.时间片轮转调度算法（RR）
最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin）调度算法
每个进程被分配一个时间段，称为时间片，即允许改进程在该时间段中运行
- 如果时间片用完，进程还在运行，那么将会会把此进程从CPU释放出来，并把CPU分配另外一个进程
- 如果该进程在时间片结束前阻塞或者结束，则CPU立即进行切换
另外，时间片的长度就是一个很关键的点：
- 如果时间设的太短会导致过多的上下文切换，降低了CPU的效率
- 如果设的太长又可能引起短作业进程的响应时间变长
通常时间片设为20~50ms通常是一个比较合理的折中值
3.1.5.最高优先级调度算法（HPF）
对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。
进程的优先级可以分为，静态优先级或动态优先级：
- 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
- 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。
该算法也有两种处理优先级高的方法，非抢占式和抢占式：
- 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
- 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
但是依然有缺点，可能会导致低优先级的进程永远不会运行。
3.1.6.多级反馈队列调度算法（MFQ）
多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。
顾名思义：
- 多级：表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
- 反馈：表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；
工作流程：
- 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短
- 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一个级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，依次类推，直至完成
- 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行，如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行
可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。