进程与线程

进程的概念和特征

进程的概念

引入了进程（Process）的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性

由程序段、相关数据段、PCB 三部分构成了进程映像（进程实体），所谓创建进程，实质上是创建进程映像中的 PCB；而撤销进程，实质上是撤销进程的 PCB，值得注意的是，进程映像是静态的，进程则是动态的

系统为每个运行的程序配置一个数据结构，称为进程控制块 PCB，用来描述进程的各种信息，PCB 是进程存在的唯一标志

引入进程实体的概念后，进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”

这里说的系统资源，指处理机、存储器、其他设备服务于某个进程的时间，处理机资源应理解为处理机的时间片

进程是这些资源分配和调度的独立单位，即时间片分配的独立单位，这就决定了进程一定是一个动态的、过程性的概念

进程的特征

进程是由多道程序的并发执行而引出的，它和程序是两个截然不同的概念

进程的基本特征是对比单个程序的顺序执行提出的，也是对进程管理提出的基本要求（只求理解）

动态性：进程是程序的一次执行，它具有一定的生命周期，是动态地产生、变化和消亡的；是进程最基本的特征
并发性：多个进程实体同时存于内存中，能在一段时间内同时运行，以提高资源利用率；是进程和操作系统的重要特征
独立性：指进程实体是一个能独立运行、获得资源、接受调度的基本单位；未建立 PCB 的程序，不能作为一个独立的单位参与运行
异步性：由于进程的相互制约，使得进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进
异步性会导致执行结果的不可再现性，为此在操作系统中必须配置相应的进程同步机制
结构性：每个进程都配置一个 PCB 对其进行描述，进程实体是由程序段、数据段、进程控制块三部分组成的

进程的状态与转换

在进程生命周期内，系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化

通常进程有以下 5 种状态，其中 1~3 种是进程的基本状态：

运行态：进程正在处理机上运行；单处理机，最多只有一个进程处于运行态
就绪态：进程获得了除处理机外的一切所需资源，得到处理机后立即运行；将就绪态的进程排成一个队列，称为就绪队列
阻塞态，等待态：进程正在等待某一事件而暂停运行，如 I/O，即使处理机空闲，该进程也不能运行
创建态：进程正在被创建，尚未转到就绪态，创建进程通常需要多个步骤：
1. 申请一个空白的 PCB，并填写一些控制和管理进程的信息
2. 由系统为该进程分配运行时所必需的资源
3. 把该进程转入就绪态
结束态：进程正从系统中消失，可能是进程正常结束或其他原因中断退出运行
系统必须先将该进程置为结束态，然后进一步处理资源释放和回收等工作

注意区别就绪态和等待态：就绪态是指进程仅缺少处理机；而等待态是指进程需要其他资源

进程在运行过程中频繁地转换到就绪态的；进程转换到等待态的次数就相对较少（等待态需要时间长）

基本状态之间的转换如下：

就绪态 → 运行态：就绪态的进程被调度后，获得处理机资源，于是进程由就绪态转换为运行态
运行态 → 就绪态：运行态的进程在时间片用完后，不得不让出处理机，从而进程由运行态转换为就绪态
可剥夺的操作系统中，当有更高优先级的进程就绪时，将正在执行的进程转换为就绪态，让更高优先级的进程执行
运行态 → 阻塞态：进程请求某一资源（如外设）的使用和分配或等待某一事件的发生时，它就从运行态转换为阻塞态
阻塞态 → 就绪态：进程等待的事件到来时（I/O 操作或中断结束）中断处理程序把相应进程的状态由阻塞态转换为就绪态

注意：从运行态变成阻塞态是主动的；从阻塞态变成就绪态是被动的，需要其他相关进程的协助

注意：不一定必须有进程处于运行态，可能所有进程都处于阻塞态，也可能没有进程任务 CPU 空闲

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，一般使用原语来控制进程，下面是进程控制的常用功能：

进程的创建

允许一个进程创建另一个进程，创建者称为父进程，被创建的进程称为子进程，子进程可以继承父进程所拥有的资源

当子进程被撤销时，向父进程归还从父进程获得的资源；在撤销父进程时，必须同时撤销其所有的子进程

在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建

操作系统创建一个新进程的过程如下（创建原语）：

为新进程分配唯一的进程标识号，并申请一个空白的 PCB（PCB 是有限的），若 PCB 申请失败，则创建失败
为进程分配资源，为新进程的程序和数据及用户栈分配必要的内存空间，若资源不足会处于阻塞态，等待内存资源
初始化 PCB，主要包括初始化标志信息、初始化处理机状态信息、初始化处理机控制信息、设置进程的优先级等
若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行

选择题：设备分配通过在系统中设置相应的数据结构实现的，不需要创建进程

进程的终止

引起进程终止的事件主要有：

正常结束，表示进程的任务已完成并准备退出运行
异常结束，表示进程在运行时，发生了某种异常事件，使程序无法继续运行
外界干预，指进程应外界的请求而终止运行

操作系统终止进程的过程如下（撤销原语）：

根据被终止进程的标识符，检索 PCB，读出该进程的状态
若处于执行状态，立即终止该进程的执行
若该进程还有子孙进程，则应将其所有子孙进程终止
将该进程所拥有的全部资源，归还给其父进程或操作系统
将该 PCB 从所在队列（链表）中删除

进程的阻塞和唤醒

正在执行的进程，由于期待的某些事件未发生，由系统自动执行阻塞原语由运行态变为阻塞态

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

阻塞原语的执行过程如下（Block）：

找到将要被阻塞的进程的标识号对应的 PCB
保护其现场，将其状态转为阻塞态，停止运行
把该 PCB 插入相应事件的等待队列，将处理机资源调度给其他就绪进程

当被阻塞进程所期待的事件出现时，有关进程（释放设备、提供数据的进程）调用唤醒原语，唤醒等待该事件的进程

唤醒原语的执行过程如下（Wakeup）：

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

注意：Block 原语和 Wakeup 原语是一对作用刚好相反的原语，必须成对使用

进程切换

任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的

进程切换是指处理机从一个进程的运行转到另一个进程上运行，在这个过程中，进程的运行环境产生了实质性的变化

进程切换的过程如下：

保存处理机上下文，包括程序计数器和其他寄存器，并更新 PCB 信息
把进程的 PCB 移入相应的队列，如就绪、在某事件阻塞等队列
选择另一个进程执行，并更新其 PCB
更新内存管理的数据结构
恢复处理机上下文

注意：处理机模式切换没有切换进程，虽然进入内核态有保存和恢复 CPU 现场，但没有改变环境信息

注意：调度和切换的区别：

调度是指决定资源分配给哪个进程的行为，是一种决策行为
切换是指实际分配的行为，是执行行为

一般来说，先有资源的调度，然后才有进程的切换

进程的组织

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位

不严谨的讲，进程由程序段、相关数据段、进程控制块组成，其中最核心的是进程控制块

进程控制块

进程创建时，操作系统为它新建一个 PCB，该结构之后常驻内存，PCB 是进程实体的一部分，是进程存在的唯一标志

进程执行时，系统通过 PCB 了解进程的现行状态信息
进程结束时，系统收回其 PCB，该进程随之消亡

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

当操作系统欲调度某进程运行时，要从该进程的 PCB 中查出其现行状态及优先级
调度到某进程后，根据其 PCB 中所保存的处理机状态信息恢复运行的现场，根据各段指针找到其程序和数据
进程在运行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也需要访问 PCB
当进程由于某种原因而暂停运行时，又需将其断点的处理机环境保存在 PCB 中

下图是一个 PCB 的实例，各部分的主要说明如下：

进程描述信息：
- 进程标识符：标志各个进程，每个进程的唯一标识号
- 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
进程控制和管理信息：
- 进程当前状态：描述进程的状态信息，作为处理机分配调度的依据
- 进程优先级：描述进程抢占处理机的优先级，优先级高的进程可优先获得处理机
资源分配清单：说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入/输出设备信息
处理机相关信息：处理机中各寄存器的值，当进程被切换时，处理机状态信息都必须保存在相应的 PCB 中

为了方便进程的调控和管理，要将 PCB 组织起来，组织方式有：

链接方式：同一状态的 PCB 链接成一个队列，不同状态对应不同的队列
也可把处于阻塞态的 PCB，根据其阻塞原因的不同，排成多个阻塞队列
索引方式：同一状态的进程组织在一个索引表中，索引表的表项指向相应的 PCB，不同状态对应不同的索引表

选择题：进程时间片用完时，可降低其优先级以让其他进程被调度进入执行状态；优先级可能可以决定在就绪队列的排序

程序段和数据段

程序段就是能被进程调度程序调度到 CPU 执行的程序代码段，多个进程可以运行同一个程序

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

进程的通信

进程通信是指进程之间的信息交换，PV 操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式：

共享存储

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

两个进程对共享空间的访问必须是互斥的，互斥访问通过操作系统提供的工具实现（如 P、V 操作）

共享存储又分为两种：

低级方式的共享是基于数据结构的共享（共享空间的数据形式有所限制）
高级方式的共享则是基于存储区的共享

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

注意：要想让两个用户进程共享空间，必须通过特殊的系统调用实现

消息传递

在消息传递系统中，进程间的数据交换是以格式化的消息 Message 为单位的；若不能使用共享空间，就只能使用消息了

进程通过系统提供的发送消息和接收消息两个原语进行数据交换

直接通信方式：发送进程直接把消息发送给接收进程（到消息缓冲队列上），接收进程从消息缓冲队列中取得消息
间接通信方式：发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息
这种中间实体一般称为信箱，这种通信方式又称信箱通信方式，相应的通信系统称为电于邮件系统

管道通信

管道（消息传递的一种特殊方式）：实现读进程和写进程之间通信的一个共享文件，又名 pipe 文件

发送进程向管道提供输入，以字符流形式将数据送入管道；接收进程从管道中接收数据

为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步、确定对方的存在

在 Linux 中，管道是一种使用非常频繁的通信机制，管道可以克服使用文件进行通信的两个问题，具体表现如下：

管道是一个固定大小的缓冲区，在 Linux 中大小为 4KB，这使得它的大小不像文件那样不加检验地增长
当把管道写满后再写将默认地被阻塞，等待数据被读取，以腾出足够的空间来调用 write() 来写
当把管道读空后再读将默认地被阻塞，等待某些数据被写入，这解决了 read() 调用返回文件结束的问题

注意：从管道读数据是一次性操作，管道只能采用半双工通信，即某一时刻只能单向传输，要全双工需要定义两个管道

进程要访问共享存储空间，则必须没有其他进程在该共享存储空间中进行写操作，否则访问行为就会被阻塞

而管道通信中，缓冲区只允许一边写入、另一边读出，管道自带同步与互斥机制，写数据的时候不允许读数据，读数据的时候不允许写数据，这是为了解决数据的二义性问题；？写进程写满，读进程才会读，读进程读到没数据，写进程才会写？

线程概念和多线程模型

线程的基本概念

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

线程最直接的理解就是轻量级进程，它是一个基本的 CPU 执行单元，由线程 ID、程序计数器、寄存器集合、堆栈组成

线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源

一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行，线程也有就绪、阻塞、运行三种基本状态

引入线程后，进程只作为除 CPU 外的系统资源的分配单元，而线程则作为处理机的分配单元

选择题：整个系统只有一个键盘，键盘输入是人的操作，速度比较慢，完全可以使用一个线程来处理整个系统的键盘输入

线程与进程的比较

调度：在引入线程的操作系统中，线程是独立调度的基本单位，进程是拥有资源的基本单位
在同一进程中，线程的切换不会引起进程切换；在不同进程中进行线程切换，才会引起进程切换
拥有资源：进程是拥有资源的基本单位，而线程不拥有系统资源（拥有一点），但线程可以访问其隶属进程的系统资源
并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且多个线程之间也可以并发执行，从而使操作系统具有更好的并发性，提高了系统的吞吐量
系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，因此所付出的开销远大于创建或撤销线程时的开销
在进行进程切换时，要进行 CPU 环境等的切换开销大；线程切换时只需保存和设置少量寄存器内容，开销很小
同一进程内的多个线程共享进程的地址空间，线程之间的同步与通信非常容易实现，甚至无须操作系统的干预
地址空间和其他资源：进程的地址空间之间互相独立，同一进程的各线程间共享进程的资源
通信方面：进程间通信需要进程同步和互斥手段，以保证数据的一致性，而线程间可以直接读/写进程数据段来进行通信

线程的属性

多线程操作系统把线程作为独立运行或调度的基本单位，进程已不再是一个基本的可执行实体，但仍具有与执行相关的状态

所谓进程处于执行状态，实际上是指该进程中的某线程正在执行，线程的主要属性如下：

线程是一个轻型实体，每个线程都有一个唯一的标识符和一个线程控制块（记录了线程执行的寄存器和栈等现场状态）
不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程
线程是处理机的独立调度单位，多个线程是可以并发执行的，在单 CPU 的计算机系统中，各线程可交替地占用 CPU
在多 CPU 的计算机系统中，各线程可同时占用不同的 CPU，若一个进程占用多个 CPU，则可缩短进程的处理时间
一个线程被创建后，便开始了它的生命周期（阻塞态、就绪态、运行态），直至终止

线程切换时，可能会发生进程切换，也可能不发生进程切换，平均每次切换所需的开销就变小了，就能开更多的线程

线程的实现方式

用户级线程 User-Level Thread，ULT：有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在
应用程序可以通过使用线程库设计成多线程程序，但这样没经过操作系统内核只能使用一个 CPU
内核级线程 Kernel-Level Thread，KLT：线程管理的所有工作由内核完成，通过内核级线程的编程接口使用
内核为进程及其内部的每个线程维护上下文信息，调度也在内核基于线程架构的基础上完成（可用多个 CPU）
由于内核级线程调度要在内核态完成，要切换处理机模式，所以切换效率比用户级线程低
组合方式的多线程实现：线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行
一个应用程序中的多个用户级线程被映射到一些（小于等于用户级线程的数目）内核级线程上；详细

多线程模型

有些系统同时支持用户线程和内核线程，由此产生了不同的多线程模型，即实现用户级线程和内核级线程的连接方式

多对一模型：多个用户级线程映射到一个内核级线程，线程管理在用户空间完成，用户级线程对操作系统不可见
优点：线程管理是在用户空间进行的，因而调度效率比较高
缺点：一个线程在使用内核服务时被阻塞，整个进程都会被阻塞；多个线程不能并行地运行在多处理机上
一对一模型：每个用户级线程映射到一个内核级线程
优点：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强
缺点：每创建一个用户级线程都需要创建一个内核级线程，这样创建线程的开销比较大，会影响到应用程序的性能
多对多模型。将 n 个用户级线程映射到 m 个内核级线程上，要求 m ≤ n
特点：多对多模型是多对一模型和一对一模型的折中，既克服两者的缺点，还拥有两者各自的优点

处理机调度

调度的概念

调度的基本概念

在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免

处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行

处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题

调度的层次

一个作业从提交开始直到完成，往往要经历以下三级调度（注意理解图片）：

作业调度

又称高级调度，按一定的原则从**外存上处于后备状态的作业中挑选一个或多个作业**，给它分配内存、输入/输出设备等必要的资源，并建立相应的进程，并送入就绪队列，以使它获得竞争处理机的权利；对于每个作业只调入一次、调出一次

多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度

作业调度的执行频率较低，通常为几分钟一次

额外：通常把用户要求计算机完成的这一串任务称为作业，作业运行时会创建一个或多个进程

内存调度

又称中级调度，其作用是提高内存利用率和系统吞吐量

将那些暂时不能运行的进程调至外存等待（PCB 不会被调出），把此时的进程状态称为挂起态

当它们已具备运行条件且内存又稍有空闲时，由中级调度把外存上的进程重新调入内存，并设置好设置为就绪态所需

理解：内存不够时，把暂时不用的进程调出内存，再加载新进程来运行；等内存宽松时，再把可运行的已挂载的进程唤醒

进程调度

又称低级调度，按照某种方法和策略从就绪队列中选取一个进程，改状态为运行态，并将处理机分配给它

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度

进程调度的频率很高，一般几十毫秒一次

三级调度的联系

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

调度的时机、切换与过程

请求调度的事件发生后，才可能运行进程调度程序，调度了新的就绪进程后，才会进行进程间的切换

现代操作系统中，不能进行进程的调度与切换的情况有以下几种：

在处理中断的过程中：中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源
进程在操作系统内核程序临界区中：进入操作系统内核临界区后，需要独占式地访问共享数据，在解锁前不应切换到其他进程运行，以加快该共享数据的释放
注意：普通临界区可以进行处理机调度，在普通临界区中处理器是不用的，如打印机；而在内核临界区中处理机仍然要用，如访问就绪队列；临界区：访问临界资源的那段代码
其他需要完全屏蔽中断的原子操作过程中：在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换

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

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

发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换
中断处理或自陷处理结束后，返回用户态程序执行现场前，若置上请求调度标志，则进行进程调度与切换

进程切换在调度完成后立刻发生，切换时内核把原进程现场信息放入其内核的堆栈，并用新进程的内核堆栈恢复现场信息

进程调度方式

指当某个进程正在处理机上执行时，若有优先权更高的进程进入就绪队列，此时应如何分配处理机

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

非剥夺调度方式

又称非抢占方式：仍然执行当前进程，直到该进程结束或进入阻塞态时，才把处理机分配给更为重要或紧迫的进程

非剥夺调度方式下，进程拿到 CPU 后就会保持 CPU 直到终止或转换到等待态

这种方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统

剥夺调度方式

又称抢占方式：立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程

采用剥夺式的调度，对提高系统吞吐率和响应效率都有明显的好处

剥夺必须遵循一定的原则，主要有优先权、短进程优先、时间片原则等

调度的基本准则

下面介绍主要的几种比较处理机调度算法的性能准则：

CPU 利用率 = 周转时间 / CPU 占用时间：应尽可能使 CPU 保持忙状态，使 CPU 资源利用率最高
系统吞吐量：表示单位时间内 CPU 完成作业的数量；调度算法和方式的不同，会对系统的吞吐量产生较大的影响
长作业执行时间长，系统的吞吐量小；短作业执行时间短，系统的吞吐量大
周转时间：周转时间是指从作业提交到作业完成所经历的时间
- 周转时间 = 作业完成时间 - 作业提交时间
- 平均周转时间 = (作业 1 的周转时间 + … + 作业 n 的周转时间) / n
- 带权周转时间 = $\frac{作业周转时间}{作业实际运行时间}$
- 平均带权周转时间 = (作业 1 的带权周转时间 + .…. + 作业 n 的带权周转时间) / n
等待时间：进程处于等处理机状态的时间之和，等待时间越长，用户满意度越低
处理机调度算法只影响作业在就绪队列中等待所花的时间；因此衡量一个调度算法的优劣，只需简单地考察等待时间
响应时间：从用户提交请求到系统首次产生响应所用的时间
在交互式系统中，一般采用响应时间作为衡量调度算法的重要准则之一
从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内

得到一个满足所有用户和系统要求的算法几乎是不可能的，设计调度程序要考虑：

① 特定系统用户的要求；② 系统整体效率；③ 调度算法的开销

典型的调度算法

先来先服务 FCFS 调度算法

FCFS 是最简单的调度算法，它属于不可剥夺算法，它既可用于作业调度，又可用于进程调度：

作业调度：从后备作业队列中选择最先进入该队列的一个或几个作业，对它们进行作业调度
进程调度：从就绪队列中选择最先进入该队列的进程，对它进行进程调度

系统中有 4 个作业，它们的提交时间分别是 8、8.4、8.8、9，运行时间依次是 2、1、0.5、0.2，性能为下表

若一个长作业先到达系统，就会使后面的许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略

FCFS 调度算法的特点：

算法简单，但效率低
对长作业比较有利，但对短作业不利
有利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业

短作业优先 SJF 调度算法

短作业优先：从后备队列中选择一个或若干估计运行时间最短的作业，将它们调入内存运行
短进程优先：从就绪队列中选择一个估计运行时间最短的进程，进行进程调度

SJF 算法属于不可剥夺算法，使用 FCFS 的例子的数据，来描述 SJF 算法的性能：

SJF 调度算法也存在不容忽视的缺点：

SJF 调度算法中长作业的周转时间会增加，对长作业不利；更严重的是，可能导致长作业长期不被调度饥饿现象
该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理
由于作业的长短只是根据用户所提供的估计执行时间而定的，致使该算法不一定能真正做到短作业优先调度

注意：SJF 调度算法的平均等待时间、平均周转时间最少

优先级调度算法

又称优先权调度算法，该算法中的优先级用于描述作业运行的紧迫程度

作业调度：从后备作业队列中选择优先级最高的一个或几个作业，进行作业调度
进程调度：从就绪队列中选择优先级最高的进程，进行进程调度

当有更急迫的进程进入就绪队列时，有两种优先级调度算法：

非剥夺式优先级调度算法：仍然运行当前进程，直到其主动让出处理机时，才把处理机分给更急迫的进程
剥夺式优先级调度算法：立即暂停当前进程，把处理机分给更急迫的进程

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

静态优先级：优先级是在创建进程时确定的，且在进程的整个运行期间保持不变
确定静态优先级的主要依据：进程类型、进程对资源的要求、用户要求
动态优先级：在进程运行过程中，根据进程情况的变化动态调整优先级
动态调整优先级的主要依据：进程占有 CPU 时间的长短、就绪进程等待 CPU 时间的长短

一般来说，进程优先级的设置可以参照以下原则：

系统进程 > 用户进程
交互型进程 > 非交互型进程（或前台进程 > 后台进程）
I/O 型进程 > 计算型进程，若 I/O 型进程的优先级更高，I/O 设备就更早开始工作，进而提升系统的整体效率

高响应比优先调度算法

HRRN 主要用于作业调度，是对 FCFS 和 SJF 的一种综合平衡，考虑了每个作业的等待时间和估计的运行时间

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

响应比的变化规律可描述为： $相应比 R_{p} = \frac{等待时间 + 要求服务时间}{要求服务时间}$

根据公式可知：

等待时间相同时，要求服务时间越短，响应比越高，有利于短作业
要求服务时间相同时，响应比由其等待时间决定，因此它实现的是先来先服务
对于长作业，等待时间足够长时也可获得处理机，因此克服了饥饿状态，兼顾了长作业

时间片轮转 RR 调度算法

就绪进程按时间的先后次序排成一个队列，总选择就绪队列的第一个进程执行（FCFS 原则）且仅运行一个时间片

使用完一个时间片后，它**必须释放出处理机给下一个进程**，然后回到就绪队列的末尾重新排队，等候再次运行

这种算法主要适用于分时系统，在时间片轮转调度算法中，时间片的大小对系统性能的影响很大：

时间片足够：所有进程都能在一个时间片内执行完毕，就相当于先来先服务调度算法
时间片很小：处理机在进程间过于频繁地切换，而切换进程需要时间，导致用于运行用户进程的时间变小

时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目、系统的处理能力

应用题：一个进程的时间片用完了，先开始计时下一个时间片，再进行进程的调度和切换

多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法、优先级调度算法的综合与发展

通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标：

为提高系统吞吐量和缩短平均周转时间，而照顾短进程
为获得较好的 I/O 设备利用率和缩短响应时间，而照顾 I/O 型进程

多级反馈队列调度算法的实现思想如下：

设置多个就绪队列，并为各个队列赋予不同的优先级，如第 1 级队列的优先级最高，第 2 级队列次之
各队列的时间片大小各不相同，在优先级越高的队列时间片越小
如 i + 1 级队列的时间片要比 i 级队列的时间片长 1 倍
每个队列使用的调度算法可以不一样，如前面的队列是 FCFS，最后一级队列是时间分片轮询调度
新进程首先放入 1 级队列；若它不能在该时间片内完成，就放入 2 级队列；但最后一级队列放回最后一级
仅当第 1 级队列为空时，调度程序才调度第 2 级队列中的进程运行
有新进程进入优先级较高的队列，则新进程将抢占正在运行进程的处理机，当前进程放回当前队列

多级反馈队列的优势有以下几点：

终端型作业用户：短作业优先
短批处理作业用户：周转时间较短
长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理

进程同步

进程同步的基本概念

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系，而进程同步用于协调进程间的制约关系

同步即制定一定的机制去约束一个进程的某个任务，让它在另一个进程完成某个任务之后才发生

注意：多个线程访问同一个全局变量的时候可以同时读，但不能一写一读，或者两个写（进程也一样）

临界资源

我们将一次仅允许一个进程使用的资源称为临界资源，如打印机等物理设备，和可以被若干进程共享的变量、数据等

对临界资源的访问，必须互斥地进行，为了保证临界资源的正确使用，可把临界资源的访问过程分成 4 个部分：

进入区：先检查可否进入临界区，若能进入临界区，则设置正在访问临界区的标志，以阻止其他进程同时进入临界区
临界区：进程中访问临界资源的那段代码，又称临界段
退出区：清除正在访问临界区的标志
剩余区：代码中的其余部分

do {
    entry section;  // 进入区
    critical section;  // 临界区
    exit section;  // 退出区
    remainder section;  // 剩余区
} while (true)

同步

同步亦称直接制约关系，是指为多个进程为需要在某些位置上协调它们的工作次序而等待

进程间的直接制约关系源于它们之间的相互合作

例如，进程 A 的 a 任务必须在进程 B 的 b 任务之后，那么进程 A 运行到 a 时就要等待进程 B 运行完 b 才继续运行

互斥

互斥也称间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待直到它退出临界区

例如，程序 A 在使用一个临界资源，这时程序 B 也要使用，那么程序 B 就要等程序 A 用完了才能使用

思考：同步是解决任务先后顺序的问题；互斥是解决两个任务不能同时进行的问题

同步准则

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

空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待：对请求访问的进程，应保证能在有限时间内进入临界区
让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待

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

软件实现方法

在进入区检查及设置标志，退出区修改标志的方法达到互斥，下面有介绍 4 种算法：

单标志法

该算法设置一个公用整型变量 turn，用于指示被允许进入临界区的进程编号，即若 turn = 0，则允许 $P_{0}$ 进程进入临界区

该算法可确保每次只允许一个进程进入临界区，但两个进程必须交替进入临界区

若 $P_{0}, P_{1}, P_{1}$ 的顺序进入，那么第二次 $P_{1}$ 进入时会被卡住，违背了空闲让进

双标志法先检查

算法的基本思想：在每个进程访问临界区资源之前，先查看临界资源是否正被访问，访问则等待；否则进入临界区

设置一个数据 flag[i]，其第 i 个元素表示 $P_{i}$ 进程是否进入了临界区，TRUE 已为入临界区

优点：不用交替进入，可连续使用

缺点：可能同时进入临界区，按如序列 1234 执行时，会同时进入临界区违背忙则等待

双标志法后检查

算法基本思想：先将自己的标志设置为 TRUE，再检测对方的状态标志

两个进程几乎同时都想进入临界区时，双方会互相谦让，结果谁也进不了临界区，从而导致饥饿现象

Peterson's Algorithm

使用单标志的思想实现一次只能进一个进程，使用双标志后检查的思想实现不用交替进入，本算法就是这两个的结合

为了防止双标志后检查的饥饿现象，加入了 turn 变量，利用 turn 总会设置成另一个值，来谦让另一个进程先行

具体：两进程同时进入，且同时设置各自的 flag 为 TRUE； $P_{i}$ 设置 turn = i 后进入 while 阻塞， $P_{j}$ 设置 turn = j 后 $P_{i}$ 就跳出了 while 循环，而 $P_{j}$ 进入 while 循环，当 $P_{i}$ 完成后设置 flag 为 FALSE， $P_{j}$ 也跳出 while

硬件实现方法

通过硬件支持实现临界段问题的方法称为低级方法，或称元方法

中断屏蔽方法

防止两个进程同时进入临界区的最简方法是：禁止一切中断发生，或称之为屏蔽中断、关中断

CPU 只在发生中断时引起进程切换，因此屏蔽中断能够保证当前进程不会被切换，进而保证互斥的正确实现

:
关中断;
临界区;
开中断;
:

这种方法限制了处理机交替执行程序的能力，因此执行的效率会明显降低（中间的临界区不能切换进程）

在多处理器中，仍会出现两个进程同时进入临界区，一个处理器运行关中断代码并不影响其他处理器切换进程

将关中断的权力交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止

硬件指令方法

`TestAndSet` 指令

TSL 指令利用硬件实现的这条指令是原子操作，即执行该代码时不允许被中断，逻辑代码为：

java

boolean TestAndset (boolean * lock) {
    boolean old;
    old = *lock;
    *lock = true;
    return old;
}

利用 TestAndSet 指令实现进程互斥的算法描述如下：

// 共享 bool 变量 lock 初始值 false
while TestAndSet (&lock);  // 若 lock 空闲(为 false 时)，lock->true,ret false 跳出循环
进程的临界区代码段;
lock = false;
进程的其他代码;

Swap 指令

XCHG 的功能是交换两个字（字节）的内容，逻辑代码为：

java

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

注意：TestAndSet 和 Swap 指令是由硬件直接实现的，不会被中断，上面只是逻辑功能

利用 Swap 指令实现进程互斥的算法描述如下：

// 共享 bool 变量 lock 初始值 false
key = true;
while (key != false)  // 若 lock 空闲，swap 后 key->false,lock->true 跳出循环
	Swap (&lock, &key);
进程的临界区代码段;
lock = false;
进程的其他代码;

硬件方法的优点：

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

硬件方法的缺点：

进程等待进入临界区时要耗费处理机时间，不能实现让权等待（软件方法也一样）
从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致饥饿现象

无论是软件实现方法还是硬件实现方法，读者只需理解它的执行过程即可，关键是软件实现方法

信息量

信号量只能被两个标准的原语 wait(S) 和 signal(S) 访问，也可记为 Р 操作和 V 操作，用于解决进程同步与互斥问题

若能够找到一种解决临界区问题的元方法，就可以实现对共享变量操作的原子性

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量 S，wait 和 signal 操作可描述为：

wait(S) {
	while (S <= 0);
    S = S - 1;
}

signa1(S) {
	S = S + 1;
}

该机制并未遵循让权等待的准则，而是使进程处于忙等的状态

记录型信号量

记录型信号量是不存在忙等现象的进程同步机制，记录型信号量得名于采用了记录型的数据结构：

typedef struct {
    int value;  // 代表资源数目
    struct process *L;  // 进程链表，用于链接所有等待该资源的进程
} semaphore;

相应的 wait(S) 和 signal(S) 的操作如下:

void wait(semaphore S) {  // 相当于申请资源
    S.value--;  // 进程请求一个该类资源
    if(S.value < 0) {  // 若该类资源已分配完毕
        add this process to S.L;  // 插入该类资源的等待队列
	    block(S.L);  // 自我阻塞，放弃处理机
    }
}
void signal(semaphore S)(  // 相当于释放资源
    S.value++;  // 进程释放一个资源
    if (S.value <= 0) {  // 若仍有等待该资源的进程被阻塞
        remove a process P from S.L;  // 弹出 S.L 的第一个进程
        wakeup(P);  // 唤醒弹出的进程
    }
}

由于调用了 block 方法自我阻塞，可见该机制遵循了让权等待的准则

利用信号量实现同步

设 S 为实现进程 $P_{1}, P_{2}$ 同步的公共信号量，初值为 0；其中 P 和 V 就是上面的 wait 和 signal

当 P1 进程的 x 执行完后才可以执行 P2 进程的 y，其实现进程同步的算法如下：

semaphore S = 0;
// 初始化信号量
P1() {
    X;
    V(S);  // 告诉进程 P2，语句 x 已经完成
    …
}
P2() {
    …
	P(S);  // 检查语句 x 是否运行完成
    y;  // 检查无误，运行 y 语句
    …
}

利用信号量实现进程互斥

由于可用资源数为 1，所以 S 的初值应为 1，只需把临界区置于 P(S) 和 V(S) 之间，即可实现互斥，其算法如下：

semaphore S = 1;  // 初始化信号量
P1() {
    …
    P(S);  // 准备开始访问临界资源，加锁
    进程 P1 的临界区;
    V(S);  // 访问结束，解锁
    …
}
P2() {
    …
    P(S);  // 准备开始访问临界资源，加锁
    进程 P2 的临界区;
    V(S);  // 访问结束，解锁
    …
}

下面简单总结一下 PV 操作在同步互斥中的应用：

同步问题：在要用到某种资源前进行 P 操作；在提供某种资源后进行 V 操作
互斥问题：PV 操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码

利用信号量实现前驱关系

使用信号量来描写下图的前驱关系，其实就是多重同步的关系，为每个向量设置一个信号量就可以

实现算法如下:

semaphore a1 = a2 = b1 = b2 = c = d = e = 0;  // 初始化信号量
S1() {
    …;
    v(a1); V(a2);  // S1 已经运行完成
}
S2() {
    P(a1);  // 检查 S1 是否运行完成
    …;
    V(b1); V(b2);  // S2 已经运行完成
}
s3() {
    P(a2);  // 检查 S1 是否已经运行完成
    …;
    V(c);  // S3 已经运行完成
}
S4() {
    P(b1);  // 检查 S2 是否已经运行完成
    …;
    V(d);  // S4 已经运行完成
}
S5() {
    P(b2);  // 检查 S2 是否已经运行完成
    …;
    v(e);  // S5已经运行完成
}
S6() {
    P(c);  // 检查 S3 是否已经运行完成
    P(d);  // 检查 S4 是否已经运行完成
    P(e);  // 检查 S5 是否已经运行完成
    …;
}

分析问题的方法步骤

关系分析：找出问题中的进程数，并分析它们之间的同步和互斥关系，参照上面例子的范式改写
整理思路：找出解决问题的关键点，根据进程的操作流程确定 Р 操作、V 操作的大致顺序
设置信号量：根据上面的两步，设置需要的信号量，确定初值，完善整理

管程

在信号量机制中，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致系统死锁，因此管程诞生了

管程的定义

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节

管程 monitor 是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化和改变管程中的数据以及同步进程

由上述定义可知，管程由 4 部分组成：

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

管程的定义描述举例如下：

monitor Demo { // 1 定义一个名称为 Demo 的管程
    // 2 定义共享数据结构，对应系统中的某种共享资源
    共享数据结构 S;
    // 4 对共享数据结构初始化的语句
    init_code() {
		S = 5;  // 初始资源数等于 5
    }

	// 3 过程 1: 申请一个资源
    take_away() {
        对共享数据结构 x 的一系列处理;
        S--;  // 可用资源数 - 1
        ...
	}

    // 3 过程 2: 归还一个资源
    give_back() {
        对共享数据结构 x 的一系列处理;
        S++;  // 可用资源数 + 1
        ...
	}
}

不难注意到，管程很像一个类；管程的基本特征：

局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程进入管程，从而实现进程互斥

选择题：管程是有编译语言支持的进程同步机制

条件变量

管程用使用条件变量 condition 来释放管程（阻塞）和唤醒管程，对应有 wait 和 signal，条件变量可以有多个

每个条件变量仅保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程

x.wait：当 x 对应的条件不满足时，调用 x.wait 将自己（进程）插入 x 条件的等待队列，并释放管程
x.signal：x 对应的条件发生了变化，则调用 x.signal，唤醒一个因 x 条件而阻塞的进程

下面给出条件变量的定义和使用：

monitor Demo{
	共享数据结构 S;
    condition x;  // 定义一个条件变量 x
    init_code() { ... }
    take_away() {
        if(S <= 0) x.wait();  // 资源不够, 在条件变量 x 上阻塞等待
        资源足够,分配资源,做一系列相应处理;
    }
    give_back() {
        归还资源,做一系列相应处理;
        if(有进程在等待) x.signal();  // 唤醒一个阻塞进程
    }
}

条件变量和信号量的比较：

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

不同点：

条件变量是没有值的，仅实现了排队等待功能
信号量是有值的，信号量的值反映了剩余资源数
在管程中，剩余资源数用共享数据结构记录

*例子

用管程解决生产者消费者问题，这是管程代码：

monitor ProducerConsumer
    condition full, empty;  // 条件变量用来实现同步（排队)
	int count = 0;  // 缓冲区中的产品数
    
    void insert(Item item) {  // 把产品 item 放入缓冲区
        if(count == N)
        	wait(full);
        count++;
        insert_item(item);
        if(count == 1)
            signal(empty);
    }
    
    Item remove(){  // 从缓冲区中取出一个产品
        if(count == 0)
	        wait(empty);
        count--;
        if(count == N - 1)
            signal(full);
        return remove_item();
    }
end monitor;

生产者和消费者的代码：

// 生产者进程
producer() {
    while(1) {
        item = 生产一个产品;
        ProdecerConsumer.insert(item);
    }
}
// 消费者进程
consumer() {
    while(1) {
        item = ProdecerConsumer.remove();
        消费产品 item;
    }
}

经典同步问题

生产者 - 消费者问题

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息

这里较为简单，所以关系分析、整理思路、设置信号量就跳过了

semaphore mutex = 1;  // 临界区互斥信号量
semaphore empty = n;  // 空闲缓冲区
semaphore ful1 = 0;  // 缓冲区初始化为空
producer() {  // 生产者进程
    while(1) {
        produce an item in nextp;  // 生产数据
        P(empty);(要用什么,P一下)  // 获取空缓冲区单元
        P(mutex);(互斥夹紧)  // 进入临界区
        add nextp to buffer;(行为)  // 将数据放入缓冲区
        V(mutex);(互斥夹紧)  // 离开临界区,释放互斥信号量
        V(full);(提供什么,V一下)  // 满缓冲区数加 1
    }
}
consumer() {  // 消费者进程
    while(1) {
        P(fu11);  // 获取满缓冲区单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  // 从缓冲区中取出数据
        V(mutex);  // 离开临界区, 释放互斥信号量
        V(empty);  // 空缓冲区数加 1
        consume the item;  // 消费数据
    }
}

家庭水果问题

问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出

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;
    }
}

读者 - 写者问题

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

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

int count = 0;  // 用于记录当前的读者数量
semaphore mutex = 1;  // 用于保护更新 count 变量时的互斥
semaphore rw = 1;  // 用于保证读者和写者互斥地访问文件
semaphore w = 1;  // 用于实现“写优先”
writer() {  // 写者进程
    while(1) {
        P(w);  // 在无写进程请求时进入
        P(rw);  // 互斥访问共享文件
        writing;  // 写入
        V(rw);  // 释放共享文件
        v(w);  // 恢复对共享文件的访问
    }
}
reader() {  // 读者进程
    while(1) {
        P(w);  // 在无写进程请求时进入
        P(mutex);  // 互斥访问 count 变量
        if(count == 0)  // 当第一个读进程读共享文件时
        	P(rw);  // 阻止写进程写
        count++;  // 读者计数器加 1
        v(mutex);  // 释放互斥变量 count
        V(w);  // 恢复对共享文件的访问
        reading;  // 读取
        P(mutex);  // 互斥访问 count 变量
        count--;  // 读者计数器减 1
        if(count == 0)  // 当最后一个读进程读完共享文件
         	V(rw);  // 允许写进程写
        v(mutex);  // 释放互斥变量 count
    }
}

这是读写公平法，如果把信号 w 去掉的话就是读优先法了

哲学家进餐问题

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

semaphore chopstick[5] = {1, 1, 1, 1, 1};  // 初始化信号量
semaphore mutex = 1;  // 设置取筷子的信号量
Pi() {  // i 号哲学家的进程
    do {
        P(mutex);  // 在取筷子前获得互斥量
        P(chopstick[i]);  // 取左边筷子
        P(chopstick (i + 1) % 5]);// 取右边筷子
        v(mutex);// 释放取筷子的信号量
        eat;  // 进餐
        V(chopstick[i]);  // 放回左边筷子
        V(chopstick[(i + 1) % 5]);  // 放回右边筷子
        think;  // 思考
    } while(1);
}

吸烟者问题

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

int num = 0;  // 存储随机数
semaphore offer1 = 0;  // 定义信号量对应烟草和纸组合的资源
semaphore offer2 = 0;  // 定义信号量对应烟草和胶水组合的资源
semaphore offer3 = 0;  // 定义信号量对应纸和胶水组合的资源
semaphore finish = 0;  // 定义信号量表示抽烟是否完成

process P1() {  // 供应者
    while(1) {
        num++;
        num = num % 3;
        if(num == 0)
	        V(offer1);  // 提供烟草和纸
        else if (num == 1)
         	V(offer2);  // 提供烟草和胶水
        else
	        V(offer3);  // 提供纸和胶水
        任意两种材料放在桌子上;
        P(finish);
    }
}

process P2() {  // 拥有烟草者
    while(1) {
        P(offer3);
        拿纸和胶水,卷成烟,抽掉;
        V(finish);
    }
)
    
process P3() {  // 拥有纸者
    while(1) {
        P(offer2);
        拿烟草和胶水,卷成烟,抽掉;
        V(finish);
    }
)

process P4() {  // 拥有胶水者
    while(1) {
        P(offer1);
        拿烟草和纸，卷成烟,抽掉;
        V(finish);
    }
}

死锁

死锁的概念

死锁的定义

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，但也带来了死锁

死锁：指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进

例子：有一座仅供一辆汽车使用的桥，若有两辆汽车分别同时从桥的左右两端驶上该桥，那么谁也过不了只能干等着

思考：操作系统只会处理多个进程访问有限资源产生死锁的情况；而信号和死循环是程序员的问题

死锁产生的原因

系统资源的竞争

通常系统中的不可剥夺资源的数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局

如磁带机、打印机等；只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的

进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁

例子：并发进程 $P_{1}, P_{2}$ 分别保持了资源 $R_{1}, R_{2}$ ，而进程 $P_{1}$ 申请资源 $R_{2}$ 、进程 $P_{2}$ 申请资源 $R_{1}$ 时，这时两者都会陷入阻塞

信号量使用不当也会造成死锁，如进程间彼此相互等待对方发来消息

死锁产生的必要条件

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

互斥条件：在一段时间内某资源只能为一个进程所占有（其他进程只能等待）
不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走（自己的资源只能由自己来释放）
请求并保持条件：请求新资源而被阻塞时，仍保持原有的资源不放
循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求
存在一个处于等待态的进程集合 $P_{1}, P_{2}, \dots, P_{n}$ ，其中 $P_{i}$ 等待的资源被 $P_{i + 1}, i \in [0, n - 1]$ 占有， $P_{n}$ 等待的资源被 $P_{0}$ 占有

按死锁定义构成等待环所要求的条件更严，它要求 $P_{i}$ 等待的资源必须由 $P_{i + 1}$ 来满足，而循环等待条件则无此限制

如 $P_{k}$ 不在循环圈，但它有其中一个 $P_{i}$ 需要的资源，等 $P_{k}$ 释放后 $P_{i}$ 就拿到资源可以执行，从而打破循环等待

循环等待只是死锁的必要条件，含圈不死锁是因为同类资源数大于 1

因此死锁的充要条件是系统中每类资源只有一个资源，且出现循环等待

死锁的处理策略

死锁预防：设置某些限制条件，破坏产生死锁的 4 个必要条件中的一个，即可防止发生死锁
避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁
死锁的检测及解除：
无须采取任何限制性措施，允许进程在运行过程中发生死锁
通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁

预防死锁和避免死锁都属于事先预防策略：

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

死锁预防

破坏互斥条件（不可行）

若允许系统资源都能共享使用，则系统不会进入死锁状态

但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用，而且在有的场合应该保护这种互斥性

破坏不剥夺条件

进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请，从而破坏不剥夺条件

缺点：

该策略实现起来比较复杂
释放已获得的资源可能造成前一阶段工作的失效
常用于状态易于保存和恢复的资源（如 CPU 的寄存器），一般不能用于打印机等
反复地申请和释放资源会增加系统开销，降低系统吞吐量
可能一直把资源谦让给其他进程导致自己饥饿

破坏请求并保持条件

采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行

一旦投入运行，这些资源就一直归它所有，不用提出其他资源请求，这样就可以保证系统不会发生死锁

缺点：

系统资源被严重浪费，其中有些资源可能仅在运行初期使用
会导致饥饿现象，由于需要一次性申请完全部资源，那么需要资源多的进程，可能一直不能一次性申请完资源

破坏循环等待条件

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

缺点：

编号必须相对稳定，这就限制了新类型设备的增加，可能需要重新分配所有编号
造成资源的浪费，如程序 A 先使用 7 再使用 5，但申请时会先申请 5 再申请 7，造成 5 时间上的浪费
这种按规定次序申请资源的方法，会给用户的编程带来麻烦，如两个 OS 的资源编号不一样

死锁避免

避免死锁属于事先预防策略，是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁

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

系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性，若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待

安全序列：指根据当前资源的分配状况和剩余情况，计算出一种可以顺利推进进程运行的序列，这个序列叫安全序列

安全状态：若系统能找到一个安全序列，那么就处于安全状态，否则系统处于不安全状态，安全状态判断的例子

注意：不安全状态不一定是死锁状态，在不安全状态进程继续申请资源导致阻塞后才是死锁；但死锁必定是不安全状态，而安全状态必定不是死锁状态

银行家算法

银行家算法是最著名的死锁避免算法，其思想是：

进程运行之前先声明对各种资源的最大需求量
在运行中不允许进程获得超过其声明的最大需求量，且不允许系统进入不安全状态

数据结构猫述

下面的二维矩阵一行代表一个进程，一列代表一类资源

可利用资源向量 Available：含有 m 个元素的数组，其中每个元素代表一类可用的资源数目
如 Available[j] = K 表示系统中现有 $R_{j}$ 类资源 K 个
最大需求矩阵 Max：n × m 矩阵，定义系统中 n 个进程中的每个进程对 m 类资源的最大需求
Max[i, j] = K 表示进程 i 需要 $R_{j}$ 类资源的最大数目为 K
分配矩阵 Allocation：n × m 矩阵，定义系统中每类资源当前已分配给每个进程的资源数
Allocation[i, j] = K 表示进程 i 当前已分得 $R_{j}$ 类资源的数目为 K
需求矩阵 Need：n × m 矩阵，表示每个进程接下来最多还需要多少资源
Need[i, j] = K 表示进程 i 还需要 $R_{j}$ 类资源的数目为 K
上述三个矩阵间存在下述关系：Need = Max - Allocation

银行家算法描述

设 $R e q u e s t_{i}$ 是进程 $P_{i}$ 的请求向量， $R e q u e s t_{i} [j] = K$ 表示进程 $P_{i}$ 需要 j 类资源 K 个

当 $P_{i}$ 发出资源请求后，系统按下述步骤进行检查：

检查请求不能大于需要 $R e q u e s t_{i} \leq N e e d [i]$ ，若它所需要的资源数超过它所宣布的最大值，则认为出错
检查请求不能大于可用 $R e q u e s t_{i} \leq A v a i l a b l e$ ，若无足够资源 $P_{i}$ 等待
系统试探着把资源分配给进程 $P_{i}$ ，并修改下面数据结构中的数值：
1. $A v a i l a b l e = A v a i l a b l e - R e q u e s t_{i}$
2. $A l l o c a t i o n [i] = A l l o c a t i o n [i] + R e q u e s t_{i}$
3. $N e e d [i] = N e e d [i] - R e q u e s t_{i}$
系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态
若安全，才正式将资源分配给进程 $P_{i}$ ；否则，分配作废，恢复原来的资源分配状态，让进程 $P_{i}$ 等待

安全性算法

设置工作向量 Work，有 m 个元素，表示系统中的剩余可用资源数目，开始时 Work = Available

初始时安全序列为空
从 Need 矩阵中找出符合下面条件的行：
该行对应的进程不在安全序列中，而且该行小于等于 Work 向量
找到后，把对应的进程 $P_{i}$ 加入安全序列；若找不到，则执行步骤 4
执行 Work = Work + Allocation[i]（因为 $P_{i}$ 已获得需要的资源，可以顺利完成）返回步骤 2
若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态

应用题：在计算过程中，将每步可满足需求的进程作为一个集合，同时执行并释放资源，可以简化计算

安全性算法举例

假定系统中有 5 个进程 ${P_{0}, P_{1}, P_{2}, P_{3}, P_{4}}$ 和三类资源 {A, B, C}，各种资源的数量分别为 10, 5, 7：

利用安全性算法判断 $T_{0}$ 时刻的资源分配是否安全：

求 Need 矩阵 Need = Max - Allocation：
将 Work 向量与 Need 矩阵的各行进行比较，找出比 Work 矩阵小的行
$(3, 3, 2) > (1, 2, 2) (3, 3, 2) > (0, 1, 1)$
找到 $P_{1}$ 和 $P_{3}$ ，这里我们选择 $P_{1}$ （也可以选择 $P_{3}$ ）暂时加入安全序列
释放 $P_{1}$ 所占的资源，即把 $P_{1}$ 进程对应的 Allocation 矩阵中的一行与 Work 向量相加：
$(3, 3, 2) + (2, 0, 0) = (5, 3, 2) = W o r k$
此时需求矩阵更新为（去掉了 $P_{1}$ 对应的一行）：
再用更新的 Work 向量和 Need 矩阵重复步骤 2

最后得到一个安全序列 ${P_{1}, P_{3}, P_{4}, P_{2}, P_{0}}$ ，利用安全性算法分析 $T_{0}$ 时刻的资源分配情况如下：

银行家算法举例

先使用银行家算法的前三步，拿到更新的 Allocation 和 Need，再按照安全性算法进行判断，就能知道系统能否满足资源请求

假设当前系统中资源的分配和剩余情况如下表：

$P_{1}$ 请求资源： $P_{1}$ 发出请求向量 $R e q u e s t_{1} (1, 0, 2)$ ，系统按银行家算法进行检查：
$R e q u e s t_{1} (1, 0, 2) \leq N e e d_{1} (1, 2, 2)$ ，请求小于需要
$R e q u e s t_{1} (1, 0, 2) \leq A v a i l a b l e (3, 3, 2)$ ，请求小于可用
系统先假定可为 $P_{1}$ 分配资源，并修改：
$A v a i l a b l e = A v a i l a b l e - R e q u e s t_{1} = (2, 3, 0)$
$A l l o c a t i o n_{1} = A l l o c a t i o n_{1} + R e q u e s t_{1} = (3, 0, 2)$
$N e e d_{1} = N e e d_{1} - R e q u e s t_{1} = (0, 2, 0)$
令 Work = Available = (2 ,3, 0)，再利用安全性算法检查此时系统是否安全，如下表：
可找到一个安全序列 ${P_{1}, P_{3}, P_{4}, P_{2}, P_{0}}$ ，系统是安全的，可以立即将 $P_{1}$ 所申请的资源分配给它
$P_{4}$ 请求资源： $P_{4}$ 发出请求向量 $R e q u e s t_{4} (3, 3, 0)$ ，系统按银行家算法进行检查：
$R e q u e s t_{4} (3, 3, 0) \leq N e e d_{4} (4, 3, 1)$
$R e q u e s t_{4} (3, 3, 0) > A v a i l a b l e (2, 3, 0)$ ，让 $P_{4}$ 等待
$P_{0}$ 请求资源： $P_{0}$ 发出请求向量 $R e q u s t_{0} (0, 2, 0)$ ，系统按银行家算法进行检查：
$R e q u e s t_{0} (0, 2, 0) \leq N e e d_{0} (7, 4, 3)$
$R e q u e s t_{0} (0, 2, 0) \leq A v a i l a b l e (2, 3, 0)$
系统暂时先假定可为 $P_{0}$ 分配资源，并修改有关数据：
$A v a i l a b l e = A v a i l a b l e - R e q u e s t_{0} = (2, 1, 0)$
$A l l o c a t i o n_{0} = A l l o c a t i o n_{0} + R e q u e s t_{0} = (0, 3, 0)$
$N e e d_{0} = N e e d_{0} - R e q u e s t_{0} = (7, 2, 3)$ ，结果如下表：
进行安全性检查：可用资源 $A v a i l a b l e (2, 1, 0)$ 已不能满足任何进程的需要，系统进入不安全状态，因此拒绝 $P_{0}$ 的请求，让 $P_{0}$ 等待，并将 $A v a i l a b l e, A l l o c a t i o n_{0}, N e e d_{0}$ 恢复为之前的值

死锁检测和解除

资源分配图

系统死锁可利用资源分配图来描述，用圆圈代表一个进程，用框代表一类资源，框中的一个圆代表一类资源中的一个资源

从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源

从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程

如图所示：

进程 $P_{1}$ 已经分得了两个 $R_{1}$ 资源，并又请求一个 $R_{2}$ 资源
进程 $P_{2}$ 分得了一个 $R_{1}$ 资源和一个 $R_{2}$ 资源，并又请求一个 $R_{1}$ 资源

死锁定理

简化资源分配图可检测系统状态 S 是否为死锁状态，简化方法如下：

在资源分配图中，找出既不阻塞又不孤点的进程 $P_{i}$ 消去它所有的请求边和分配边，使之成为孤立的结点
在上图 a 中， $P_{1}$ 是满足这一条件的进程结点，将 $P_{1}$ 的所有边消去，便得到图 b 所示的情况
注意：一个资源的空闲数量等于它的资源数量减去它在资源分配图中的出度
进程 $P_{i}$ 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程，如图中 $P_{2}$
进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的，如图 c 所示
S 为死锁的条件是当且仅当 S 状态的资源分配图是不可完全简化的，该条件为死锁定理

死锁解除

死锁解除的主要方法有：

资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程
但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态
撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源
进程回退法：让一或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺
要求系统保持进程的历史信息，设置还原点

*应该对哪个进程使用进程解除：

进程优先级：优先对进程优先级低的进程下手
已执行多长时间：执行时间越长下手的代价越大
还要多久能完成：牺牲还需要时间较长的进程
进程已经使用了多少资源：把有很多资源的进程干掉可以释放很多资源
进程是交互式的还是批处理式的：撤销批处理式的进程用户感觉不明显

📝 个人补充与原笔记精华

NOTE

用户级线程中，线程切换在用户态即可完成，无需操作系统干预。用户级线程对操作系统是透明的（即看不见）。

NOTE

同步亦称直接制约关系。同步是由于并发进程之间需要协调完成同一个任务时引起的一种关系，是一个进程等待另一个进程向它直接发送消息或数据时的一种制约关系。

NOTE

互斥亦称间接制约关系。互斥是由并发进程之间竞争系统的临界资源引起的，是一个进程等待另一个进程已经占有的必须互斥使用的资源时的一种制约关系。

进程与线程 ​

进程的概念和特征 ​

进程的概念 ​

进程的特征 ​

进程的状态与转换 ​

进程控制 ​

进程的创建 ​

进程的终止 ​

进程的阻塞和唤醒 ​

进程切换 ​

进程的组织 ​

进程控制块 ​

程序段和数据段 ​

进程的通信 ​

共享存储 ​

消息传递 ​

管道通信 ​

线程概念和多线程模型 ​

线程的基本概念 ​

线程与进程的比较 ​

线程的属性 ​

线程的实现方式 ​

多线程模型 ​

处理机调度 ​

调度的概念 ​

调度的基本概念 ​

调度的层次 ​

作业调度 ​

内存调度 ​

进程调度 ​

三级调度的联系 ​

调度的时机、切换与过程 ​

进程调度方式 ​

非剥夺调度方式 ​

剥夺调度方式 ​

调度的基本准则 ​

典型的调度算法 ​

先来先服务 FCFS 调度算法 ​

短作业优先 SJF 调度算法 ​

优先级调度算法 ​

高响应比优先调度算法 ​

时间片轮转 RR 调度算法 ​

多级反馈队列调度算法 ​

进程同步 ​

进程同步的基本概念 ​

临界资源 ​

同步 ​

互斥 ​

同步准则 ​

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

软件实现方法 ​

单标志法 ​

双标志法先检查 ​

双标志法后检查 ​

Peterson's Algorithm ​

硬件实现方法 ​

中断屏蔽方法 ​

硬件指令方法 ​

TestAndSet 指令 ​

Swap 指令 ​

信息量 ​

整型信号量 ​

记录型信号量 ​

利用信号量实现同步 ​

利用信号量实现进程互斥 ​

利用信号量实现前驱关系 ​

分析问题的方法步骤 ​

管程 ​

管程的定义 ​

条件变量 ​

*例子 ​

经典同步问题 ​

生产者 - 消费者问题 ​

家庭水果问题 ​

读者 - 写者问题 ​

哲学家进餐问题 ​

吸烟者问题 ​

死锁 ​

死锁的概念 ​

死锁的定义 ​

进程与线程

进程的概念和特征

进程的概念

进程的特征

进程的状态与转换

进程控制

进程的创建

进程的终止

进程的阻塞和唤醒

进程切换

进程的组织

进程控制块

程序段和数据段

进程的通信

共享存储

消息传递

管道通信

线程概念和多线程模型

线程的基本概念

线程与进程的比较

线程的属性

线程的实现方式

多线程模型

处理机调度

调度的概念

调度的基本概念

调度的层次

作业调度

内存调度

进程调度

三级调度的联系

调度的时机、切换与过程

进程调度方式

非剥夺调度方式

剥夺调度方式

调度的基本准则

典型的调度算法

先来先服务 FCFS 调度算法

短作业优先 SJF 调度算法

优先级调度算法

高响应比优先调度算法

时间片轮转 RR 调度算法

多级反馈队列调度算法

进程同步

进程同步的基本概念

临界资源

同步

互斥

同步准则

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

软件实现方法

单标志法

双标志法先检查

双标志法后检查

Peterson's Algorithm

硬件实现方法

中断屏蔽方法

硬件指令方法

`TestAndSet` 指令

Swap 指令

信息量

整型信号量

记录型信号量

利用信号量实现同步

利用信号量实现进程互斥

利用信号量实现前驱关系

分析问题的方法步骤

管程

管程的定义

条件变量

*例子

经典同步问题

生产者 - 消费者问题

家庭水果问题

读者 - 写者问题

哲学家进餐问题

吸烟者问题

死锁

死锁的概念

死锁的定义