前言

NULL，基础部分，很长很多很麻烦

进程与线程

进程的概念

程序：是静态的，程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
进程（Process）：是动态的，是程序的一次执行过程。

进程的组成

系统使用 **PCB（进程控制块）**来描述进程的基本情况和运行状态，进而控制和管理进程。

image-20230303191359280

相应的，程序段，数据段和 PCB 三个部分构成了进程实体。进程是动态的，进程实体是静态的。

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

PCB 是进程存在的唯一标志

进程的特征

  1. 动态性：进程是动态产生，变化和消亡的
  2. 并发性：内存中有多个进程实体，各进程可以并发执行
  3. 独立性：独立运行，获得资源，进行调度的基本单位
  4. 异步性
  5. 结构性

进程的状态与转换

  1. 进程正在被创建时，其状态为“ 创建态 ”，这个阶段会分配资源，初始化 PCB
  2. 当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行
  3. 如果一个进程此时在CPU上运行，那么这个进程处于“运行态”。
  4. 在进程运行的过程中，可能会请求等待某个事件的发生。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”
  5. 一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。
image-20230303194359726

运行态→阻塞态\color{red}{运行态} \to 阻塞态 是一种进程自身做出的主动行为。阻塞态→运行态\color{red}{阻塞态} \to 运行态 不能由进程自身控制，是一种被动行为。

注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态

另外，在单核 CPU 情况下，同一时刻只会有一个进程处于运行态

补充：进程的挂起态和七状态模型

image-20230304181741819

进程的组织

链式方式

image-20230303194924225

索引方式

image-20230303201906700

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

进程状态的转换，需要通过原语转换，不可中断

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。可以用**“关中断指令”和“开中断指令”这两个特权指令**实现原子性。

因为 CPU 在执行指令后需要检查是否有外部中断信号，这个时候关闭中断指令，即使收到中断信号，也不会中断，这样就实现了原子性，等到执行完成后，进行开中断。

进程的创建

image-20230303202908058

进程的终止

image-20230303203152548

进程的阻塞和唤醒

image-20230303203341450

进程的切换

image-20230303203433572

进程的通信

进程间通信（Inter-Process Communication，IPC）是指两个进程 之间产生数据交互。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

进程的通信可以分为三种：共享存储，消息传递和管道通信

共享存储

即开辟一段共享的内存空间，这样不同的进程可以在这个共享的内存空间中，读取或者写入数据来完成通信。

为避免出错，各个进程对共享空间的访问应该是互斥的。

共享存储又可以分为：

  • 基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。**
  • 基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式。

消息传递

进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息／接收消息”两个原语进行数据交换。

image-20230303210524715

消息传递又可以分为

  • 直接通信方式：消息发送进程要指明接收进程的ID。

  • 间接通信方式：以“信箱”作为中间实体进行消息传递。

    可以多个进程往同一个信箱 send 消息，也可以多个进程，从同一个信箱中receive消息

  • 管道通信：“管道”是一个特殊的共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区

    1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
    2. 各进程要互斥地访问管道（由操作系统实现）
    3. 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
    4. 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：①一个管道允许多个写进程，一个读进程；②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux的方案）。

线程的概念

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）。
引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

image-20230303220256817

线程的属性

image-20230303220437107

线程的实现方式

用户级线程

早期的操作系统（如：早期Unix）只支持进程，不支持线程。当时的“线程”是由线程库实现的。

image-20230303221645391

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

内核级线程

大多数现代操作系统都实现了内核级线程，如Windows、Linux

image-20230303222328962

优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多线程模型

  • 一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
  • 多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。image-20230303222528761
  • 多对多模型：n用户及线程映射到m个内核级线程（n＞＝m）。每个用户进程对应m个内核级线程。image-20230303222627366

操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

线程的状态与转换

image-20230303222839798

管理线程是通过 TCB（线程控制块）。

image-20230303223133291

多个线程 TCB 组成一张线程表，进行分类管理。

处理机调度

调度的概念

在多到程序系统中，由于资源优先，来使用调度来分配资源来实现并发执行。

调度的层次

  1. 高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

    即将外存中的程序/作业，调入内存进行执行

  2. 低级调度（进程调度／处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它

  3. 中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。

    即将内存中挂起态的程序/作业，调入外存中以腾出内存空间

image-20230304181844478

进程调度的时机

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

需要进行进程调度的情况：

  1. 当前运行的进程主动放弃处理机
  2. 当前运行的进程被动放弃处理机

不能进行进程调度的情况：

  1. 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
  2. 进程在操作系统内核程序临界区中。
  3. 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区：访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的PCB组成）

进程调度的方式

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统。

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。

调度器

调度程序进行调度的时机：

  1. 创建新进程
  2. 进程退出
  3. 运行进程阻塞
  4. I/O中断发生
  • 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
  • 抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作

闲逛进程

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程（idle）

闲逛进程的特性：

  • 优先级最低
  • 可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
  • 能耗低

调度算法的评价指标

CPU利用率：指CPU“忙碌”的时间占总时间的比例。

利用率=忙碌的时间总时间\large 利用率 = \frac{忙碌的时间}{总时间}

系统吞吐量：单位时间内完成作业的数量。

系统吞吐量=中共完成了多少道作业总共花了多少时间\large 系统吞吐量 = \frac{中共完成了多少道作业}{总共花了多少时间}

周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

周转时间=作业完成时间−作业提交时间周转时间=作业完成时间 - 作业提交时间

平均周转时间=各作业周转时间之和作业数\large 平均周转时间 = \frac{各作业周转时间之和}{作业数}

带权周转时间=作业周转时间作业实际运行时间=作业完成时间−作业提交时间作业实际运行时间\large 带权周转时间 = \frac{作业周转时间}{作业实际运行时间} = \frac{作业完成时间 - 作业提交时间}{作业实际运行时间}

带权周转时间必然是 ⩾1\geqslant 1

带权周转时间与周转时间是越小越好

平均带权周转时间=各作业带权周转时间之和作业数\large 平均带权周转时间 = \frac{各作业带权周转时间之和}{作业数}

等待时间，指进程／作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I／O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

响应时间，指从用户提交请求到首次产生响应所用的时间。

调度算法

先来先服务（FCFS）

类目 说明
算法思想 主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）
算法规则 按照作业/进程到达的先后顺序进行服务
用于作业/进程调度 用于作业调度时，考虑的是哪个作业先到达后备队列（外存）；
用于进程调度时，考虑的是哪个进程先到达就绪队列（内存）；
是否可以抢占 非抢占式算法（即阻塞或者结束进程）
优缺点 优点：公平、算法实现简单
缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利
是否会导致饥饿 不会

短作业优先（SJF）

短作业／进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业／进程。

类目 说明
算法思想 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间
算法规则 最短的作业／进程优先得到服务（所谓“最短”，是指要求服务时间最短）
用于作业/进程调度 即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF，Shortest Process First）算法”
是否可以抢占 SJF 和 SPF是非抢占式算法。但是也有抢占式的版本——最短剩余时间优先算法(SRTN,Shortes
st Remaining Time Next)
优缺点 优点：“最短的”平均等待时间、平均周转时间
缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业／进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
是否会导致饥饿 会。如果源源不断地有短作业／进程到来，可能使长作业／进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”

最短剩余时间优先算法（SPF）：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

  1. 如果题目中未特别说明，所提到的“短作业／进程优先算法**”默认是非抢占式的**
  2. 很多书上都会说“SJF调度算法的平均等待时间、平均周转时间最少”（严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少
    应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”）
  3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间

高响应比优先（HRRN）

高响应比优先算法：非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。

类目 说明
算法思想 要综合考虑作业/进程的等待时间和要求服务的时间
算法规则 在每次调度时先计算各个作业／进程的响应比，选择响应比最高的作业／进程为其服务
响应比=等待时间+要求服务时间要求服务时间\large 响应比 = \frac{等待时间 + 要求服务时间}{要求服务时间}
用于作业/进程调度 即可用于作业调度，也可用于进程调度
是否可以抢占 非抢占式的算法。因此只有当前运行的作业／进程主动放弃处理机时，才需要调度，才需要计算响应比
优缺点 综合考虑了等待时间和运行时间（要求服务时间）
等待时间相同时，要求服务时间短的优先（SJF的优点）
要求服务时间相同时，等待时间长的优先（FCFS的优点）
对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
是否会导致饥饿 不会

时间片轮转调度算法

类目 说明
算法思想 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
用于作业/进程调度 用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
是否可以抢占 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到
优缺点 优点：公平；响应快，适用于分时操作系统；
缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
是否会导致饥饿 不会

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

优先级调度算法

类目 说明
算法思想 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则 每个作业／进程有各自的优先级，调度时选择优先级最高的作业／进程
用于作业/进程调度 既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I／0调度中
是否可以抢占 抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
优缺点 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业／进程的偏好程度。
缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
是否会导致饥饿 会

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

  • 静态优先级：创建进程时确定，之后一直不变。
  • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。

【如何合理地设置各类进程的优先级？】

  • 系统进程优先级 高于 用户进程
  • 前台进程优先级 高于 后台进程
  • 操作系统更偏好I／O型进程（或称I／0繁忙型进程）

【如果采用的是动态优先级，什么时候应该调整？】

  • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
  • 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
  • 如果发现一个进程频繁地进行1/0操作，则可适当提升其优先级

多级反馈队列调度算法

FCFS算法的优点是公平，SJF 算法的优点是能尽快处理完短作业，平均等待／周转时间等参数很优秀，时间片轮转调度算法可以让各个进程得到及时的响应，优先级调度算法可以灵活地调整各种进程被服务的机会，能否对其他算法做个折中权衡？得到一个综合表现优秀平衡的算法呢？这就是多级反馈队列调度算法。

image-20230306210318660

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。

只有第 kk 级队列为空时，才会为 k＋1k＋1 级队头的进程分配时间片。

被抢占处理机的进程重新放回原队列队尾。

类目 说明
算法思想 对其他调度算法的折中权衡
算法规则 1．设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
3．只有第 kk 级队列为空时，才会为 k＋1k＋1 级队头的进程分配时间片
用于作业/进程调度 用于进程调度
是否可以抢占 抢占式的算法。在k级队列的进程运行过程中，若更上级的队列（1～k—1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
优缺点 对各类型进程相对公平（FCFS的优点）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I／O密集型进程
【拓展：可以将因I／O而阻塞的进程重新放回原队列，这样I／O型进程就可以保持较高优先级】
是否会导致饥饿 会

时间片轮转调度算法，优先级调度算法，多级反馈队列调度算法适合用于交互式系统。

多级队列调度算法

image-20230306210932286

队列之间可采取固定优先级，或时间片划分：

  • 固定优先级：高优先级空时低优先级进程才能被调度

  • 时间片划分：如三个队列分配时间50％、40％、10％

各队列可采用不同的调度策略，如：

  • 系统进程队列采用优先级调度
  • 交互式队列采用RR
  • 批处理队列采用FCFS

同步与互斥

同步与互斥基本概念

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

do{
    entry section;	//进入区,检查是否可以访问临界区
    critical section;	//临界区，访问临界资源的diamond
    exit section;	//退出区，解除“正在访问临界资源的标志”（解除上锁）
    remainder section;	//剩余区,其他处理
}while(true)

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

  1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
  2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
  3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
  4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

image-20230306220721552

该算法可以实现“同一时刻最多只允许一个进程访问临界区”

单标志法存在的主要问题是：违背“空闲让进”原则。

双标志先检查

算法思想：设置一个布尔型数组flagl］，数组中各个元素用来标记各进程想进入临界区的意愿，比如 flag[0]＝ture 意味着 0 号进程 P0P_0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。

image-20230306221149962

双标志先检查法的主要问题是：违反“忙则等待”原则，在并发运行的时候，可能会出现多个进程同时访问的情况。

原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

双标志后检查

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

image-20230306221637462

因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

Paterson 算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。

image-20230306223519981

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

进程互斥的硬件实现方法

中断屏蔽方法

利用“开／关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）

image-20230306224414667

优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

TestAndSet (TS指令/TSL指令)

简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

image-20230306224655818

若刚开始lock是false，则 TSL 返回的old值为false， while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true， while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

Swap指令 (XCHG指令)

有的地方也叫Exchange指令，或简称XCHG指令。

Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

image-20230306225543780

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old变量上），再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

互斥锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。

每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acqiure()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

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

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如TSL指令、swap指令、单标志法。

特性：

  • 需忙等，进程时间片用完才下处理机，违反“让权等待”
  • 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
  • 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
  • 不太适用于单处理机系统，忙等的过程中不可能解锁
image-20230306233055402

信号量机制

  1. 在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；
  2. 所有的解决方案都无法实现“让权等待”。

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制。

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断／开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和 signal，括号里的信号量S其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、V操作（来自荷兰语 proberen和verhogen）。因此，做题的时候常把 wait(S)、signal(S)两个操作分别写为P（S）、V（S）。

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

与普通整数变量的区别：对信号量的操作只有三种，即 初始化、P操作、V操作

image-20230307181547864

记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

image-20230307182220128

S.value的初值表示系统中某种资源的数目。

对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value--，表示资源数减1，当S.value＜0时表示该类资源已分配完毕，因此进程应调用block 原语进行自我阻塞（当前运行的进程从运行态→阻塞态），主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。

对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value＋＋，表示资源数加1，若加1后仍是S.value＜＝0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）。

实现进程互斥

  1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
  2. 设置互斥信号量mutex, 初值为1
  3. 在进入区P(mutex)——申请资源
  4. 在退出区V(mutex)——释放资源

注意：对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

实现进程同步

进程同步：要让各并发进程按要求有序地推进。

用信号量实现进程同步：

  1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
  2. 设置同步信号量S，初始为0.
  3. 在“前操作”之后执行V(S).
  4. 在“后操作”之前执行P(S).
image-20230307185525671

实现进程的前驱关系

image-20230307185852766

其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）因此，

  1. 要为每一对前驱关系各设置一个同步信号量。
  2. 在“前操作”之后对相应的同步信号量执行V操作。
  3. 在“后操作”之前对相应的同步信号量执行P操作。

管程

信号量机制存在的问题：编写程序困难、易出错，为了更加易用，出现了管程。

管程是一种特殊的软件模块，有这些部分组成：

  1. 局部于管程的共享数据结构说明；
  2. 对该数据结构进行操作的一组过程；
  3. 对局部于管程的共享数据设置初始值的语句；
  4. 管程有一个名字。

管程的基本特征：

  1. 局部于管程的数据只能被局部于管程的过程所访问；
  2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
  3. 每次仅允许一个进程在管程内执行某个内部过程。

【用管程解决生产者消费者问题】

image-20230307204053789

经典同步问题

生产者消费者问题

问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）

  • 生产者、消费者共享一个初始为空、大小为 nn 的缓冲区。
  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
  • 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
  • 缓冲区是临界资源，各进程必须互斥地访问。
image-20230307192202837

多生产者多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

互斥关系：

  1. 对缓冲区（盘子）的访问要互斥地进行

同步关系（一前一后）：

  1. 父亲将苹果放入盘子后，女儿才能取苹果。
  2. 母亲将橘子放入盘子后，儿子才能取橘子。
  3. 只有盘子为空时，父亲或母亲才能放入水果。
image-20230307193942825

吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）

同步关系（从事件的角度来分析）：

  1. 桌上有组合一→第一个抽烟者取走东西
  2. 桌上有组合二→第二个抽烟者取走东西
  3. 桌上有组合三→第三个抽烟者取走东西
  4. 发出完成信号→供应者将下一个组合放到桌上
image-20230307195157566

读者写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

因此要求：

  1. 允许多个读者可以同时对文件执行读操作；
  2. 只允许一个写者往文件中写信息；
  3. 任一写者在完成写操作之前不允许其他读者或写者工作；
  4. 写者执行写操作前，应让已有的读者和写者全部退出。

互斥关系：写进程一写进程、写进程一读进程。读进程与读进程不存在互斥问题。

哲学家进餐问题

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

死锁

死锁的概念

在并发环境下**，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象**，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

饥饿：由于长期得不到想要的资源，某进程无法问前推进的现象。比如：在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

区别

  • 死锁一定是“循环等待对方手里的资源”导致的，因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态。
  • 可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态（如长期得不到需要的I／O设备），也可能是就绪态（长期得不到处理机）
  • 可能只有一个进程发生死循环。死循环的进程可以上处理机运行（可以是运行态），只不过无法像期待的那样顺利推进。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题。

死锁产生的必要条件

产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。

  • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
  • 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
  • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
  • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

注意！发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

死锁的处理策略

  1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
  2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
  3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
image-20230307210257718

预防死锁

破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术。操作系统可以采用SPOOLing 技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备…

image-20230307210459458

该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

破坏不剥夺条件

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）

该策略的缺点：

  1. 实现起来比较复杂。
  2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
  3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
  4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

破坏请求和保持条件

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

可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

该策略实现起来简单，但也有明显的缺点：

  1. 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

破坏循环等待条件

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

可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。

原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

该策略的缺点：

  1. 不方便增加新的设备，因为可能需要重新分配所有的编号：
  2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
  3. 必须按规定次序申请资源，用户编程麻烦。

避免死锁（银行家算法）

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

银行家算法是荷兰学者Dijkstra为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。

核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

死锁的检测和解除

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：

  1. 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。
  2. 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

死锁的检测

为了能对系统是否已发生了死锁进行检测，必须：

  1. 用某种数据结构来保存资源的请求和分配信息；
  2. 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。
image-20230308223754219

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。

相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…

如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）

如果最终不能消除所有边，那么此时就是发生了死锁。最终还连着边的那些进程就是处于死锁状态的进程。

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。

死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。

并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程

解除死锁的主要方法有：

  1. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
  2. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
  3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

【如何绝对“对谁下手”？】

  1. 进程优先级
  2. 已执行多长时间
  3. 还要多久能完成
  4. 进程已经使用了多少资源
  5. 进程是交互式的还是批处理式的

End

Q.E.D.

赤脚踩在明媚的沙滩上，我看见了你闪耀的双眼，柔软的头发，我便心有所属