mirror of
https://github.com/Didnelpsun/CS408.git
synced 2026-02-10 06:05:51 +08:00
1885 lines
106 KiB
Markdown
1885 lines
106 KiB
Markdown
# 进程管理
|
||
|
||
## 进程与线程
|
||
|
||
### 进程概念
|
||
|
||
+ 程序指一个指令序列。
|
||
+ 进程为了满足操作系统的并发性和共享性。
|
||
+ 进程和程序的根本区别在于其动态性。（<span style="color:orange">注意：</span>所以进程不能与程序相等）
|
||
+ 系统为每个运行的程序配置一个数据结构，称为**进程控制块PCB**，用来描述进程的各种信息，如程序代码存放位置。
|
||
+ $PCB$、程序段、数据段三个部分构成了进程实体（进程映像），简称为进程。
|
||
+ 创建进程就是创建$PCB$，销毁进程就是销毁$PCB$，$PCB$是进程存在的唯一标志。
|
||
+ 进程映像是静态的，而进程是动态的。
|
||
+ 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
|
||
+ 系统资源这里指处理机、存储器和其他设备服务于某个进程的时间单位。
|
||
|
||
#### 进程结构
|
||
|
||
+ 程序段（代码段）：包括程序代码，程序运行时使用、产生的运算数据，往往是只读的。
|
||
+ 数据段：存放程序运行过程中处理的各种数据。如全局变量、静态变量、宏定义的常量。
|
||
+ $PCB$：操作系统用$PCB$来管理进程，所以$PCB$包含所有管理进程所需的信息。
|
||
+ 进程描述信息：
|
||
+ 进程标识符$PID$：标识进程。
|
||
+ 用户标识符$UID$：标识进程归属的用户，用于共享和保护服务。
|
||
+ 进程控制和管理信息：
|
||
+ 进程当前状态：进程状态信息，作为处理机发分配调度的依据。
|
||
+ 进程优先级：进程抢占处理机的优先级。
|
||
+ 代码运行入口地址。
|
||
+ 程序外存地址。
|
||
+ 进入内存时间。
|
||
+ 处理机占用时间。
|
||
+ 信号量使用。
|
||
+ 资源分配清单：说明有关内存地址空间或虚拟地址空间的状况，打开文件的列标与使用的输入输出设备信息。
|
||
+ 代码段指针。
|
||
+ 数据段指针。
|
||
+ 堆栈段指针。
|
||
+ 文件描述符。
|
||
+ 键盘。
|
||
+ 鼠标。
|
||
+ 处理机相关信息：主要处理机中各种寄存器值。
|
||
+ 通用寄存器值。
|
||
+ 地址寄存器值。
|
||
+ 控制寄存器值。
|
||
+ 标志寄存器值。
|
||
+ 状态字。
|
||
+ 堆：用来存放动态分配的变量，如调用`malloc`函数动态地向高地址分配空间。
|
||
+ 栈：用来实现函数调用，保存局部变量、函数传递参数，从用户空间的高地址向低地址增长。
|
||
|
||
#### 进程特征
|
||
|
||
+ 动态性：是进程最基本的特征，进程是程序的一次执行过程，是动态地产生、变化和消亡的。
|
||
+ 并发性：内存中有多个进程实体，各进程可并发执行。
|
||
+ 独立性：进程是资源分配、接受调度、能独立运行、独立获得资源、独立接受调度的基本单位。
|
||
+ 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题。
|
||
+ 结构性：每个进程都会配置一个$PCB$。结构上看，进程由程序段、数据段、$PCB$组成。
|
||
|
||
#### 进程组织
|
||
|
||
当一个系统中存在多个$PCB$时，需要以适当的方式组织$PCB$。
|
||
|
||
+ 链接方式：
|
||
+ 按照进程状态将$PCB$分为多个队列。如执行指针（指针数为最大执行并行数）、就绪队列指针（一般会把优先级高的进程放在队头）、阻塞队列指针（许多操作系统会根据阻塞原因的不同将其分为多个阻塞队列）。
|
||
+ 操作系统持有指向各个队列的指针。
|
||
+ 索引方式：
|
||
+ 根据进程状态的不同建立索引表。如执行指针、就绪表指针、阻塞表指针。
|
||
+ 操作系统持有指向各个索引表的指针。
|
||
|
||
#### 进程与程序
|
||
|
||
执行一条命令或运行一个应用程序时，进程和程序之间形成一对一的关系。进程在执行过程中可以加载执行不同的应用程序，从而形成一对多的关系；以不同的参数或数据多次执行同一个应用程序时，形成多对一的关系；并发地执行不同的应用程序时，形成多对多的关系。
|
||
|
||
### 进程状态
|
||
|
||
#### 基本进程状态
|
||
|
||
具有三种基本状态和其他两种状态：
|
||
|
||
+ 运行态：占有$CPU$并已经在$CPU$上运行。
|
||
+ 就绪态：已经具备运行条件（除处理机外的一切所需资源），但是由于没有空闲$CPU$，导致暂时不能运行。
|
||
+ 阻塞态（等待态）：因等待某一事件而暂时不能运行，只有分配其他资源到位才能考虑分配$CPU$。
|
||
+ 创建态（新建态）：为进程分配所需的内存空间等系统资源，将转为就绪态。
|
||
+ 申请一个空白$PCB$。
|
||
+ 向$PCB$填写一些控制和管理进程的信息。
|
||
+ 系统为进程分配运行所需资源。
|
||
+ 进程转为就绪态。
|
||
+ 终止态（结束态）：进程运行结束或出现错误导致进程被撤销，操作系统需要回收进程资源，撤销$PCB$等工作，以防止内存泄漏。
|
||
+ 挂起态：暂时不能获得服务，进程映像调到外存等待（对应进程的$PCB$还在内存中等待并允许被修改）。分为：
|
||
+ 就绪挂起态：准备好后在外存中，只要允许可以随时进入内存。
|
||
+ 阻塞挂起态：等待事件在外存中，必须等待一定时间发生。
|
||
|
||
#### 进程状态转换
|
||
|
||
+ 创建态到就绪态：系统完成创建进程等工作并准备好处理机等资源。
|
||
+ 就绪态到运行态：占有$CPU$资源，进程被调用。
|
||
+ 运行态到就绪态：时间片到或处理机（包含$CPU$和内存的一系列硬件）被抢占。
|
||
+ 运行态到阻塞态：进程主动用系统调用的方式申请某种系统资源（由用户态程序调用操作系统内核），或请求等待某个事件发生。
|
||
+ 阻塞态到就绪态：申请的资源被分配或等待的事件发生，是被动发生。
|
||
+ 运行态到终止态：进程运行结束或运行过程中遇到不可修复的错误。
|
||
+ 就绪挂起态到就绪态：激活。
|
||
+ 就绪态到就绪挂起态：挂起。
|
||
+ 阻塞挂起态到阻塞态：激活。
|
||
+ 阻塞态到阻塞挂起态：挂起。
|
||
+ 阻塞挂起态到就绪挂起态：阻塞事件发生。
|
||
+ 运行态到就绪挂起态：运行中内存空间不足，或优先级更高的进程进入队列。
|
||
+ 创建态到就绪挂起态：创建后发现内存空间不足。
|
||
|
||
### 进程控制
|
||
|
||
#### 进程控制概念
|
||
|
||
+ 进程控制指对系统中的所有进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换功能。
|
||
+ 如进程组织所说，通过将$PCB$指针放入各种状态的进程队列中转换进程状态来实现控制。
|
||
+ 进程控制由**原语**实现。
|
||
+ 特点是执行期间不能中断。
|
||
+ 这种不能中断的操作就是原子操作。
|
||
+ 原语采取“关中断指令”（不监听外部中断信息）和“开中断指令”（开始监听外部中断信息）实现。
|
||
+ 关/开中断指令的权限很大，所以必然是核心态下执行的特权指令。从而原语必然运行在核心态。
|
||
|
||
#### 父子进程
|
||
|
||
允许一个进程创建另一个进程。此时创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。此外，在撤销父进程时，必须同时撤销其所有的子进程。
|
||
|
||
父进程创建子进程后，父进程与子进程同时执行（并发）。主程序调用子程序后，主程序暂停在调用点，子程序开始执行，直到子程序返回，主程序才开始执行。
|
||
|
||
父进程和子进程可以共享一部分资源，但是不能共享虚拟地址空间，因为这是逻辑地址。且其有不同的$PCB$用于区分进程。
|
||
|
||
#### 进程控制原语
|
||
|
||
前四种是必要的。
|
||
|
||
+ 过程创建：
|
||
+ 创建原语：
|
||
+ 分配一个唯一的进程标识号$PID$，申请空白$PCB$，若申请失败，则创建失败。
|
||
+ 为新进程分配所需资源，若资源不足，则进入阻塞态。
|
||
+ 初始化$PCB$，主要包括标志信息、处理机状态信息、处理机控制信息、进程优先级。
|
||
+ 将$PCB$插入就绪队列。
|
||
+ 引起进程创建的事件：
|
||
+ 用户登录：分时系统中，用户登录成功，系统会为其建立一个新进程。
|
||
+ 作业调度：多道批处理系统中，有新的作业进入内存时，会为其创建一个新进程。
|
||
+ 提供服务：用户向系统提出请求时，会创建一个新进程来处理请求。
|
||
+ 应用请求：由用户进程主动请求创建一个子进程。
|
||
+ 进程终止：
|
||
+ 撤销原语：
|
||
+ 根据被终止进程的标识符，从$PCB$集合中找到终止进程的$PCB$，读取进程的状态。
|
||
+ 若进程正在运行，则立刻剥夺其$CPU$交给其他进程。
|
||
+ 若是普通的终止，父进程终止时会将其子进程交给$init$进程收养。
|
||
+ 若是整个进程组的进程，则终止其所有子进程。
|
||
+ 将进程所有的资源交给父进程或操作系统。
|
||
+ 从所在队列或链表中删除$PCB$。
|
||
+ 引起进程终止的事件：
|
||
+ 正常结束：任务完成。
|
||
+ 异常结束：内部异常，如存储区越界、保护错、运行超时等。
|
||
+ 外界干预：外部请求而终止运行，如操作员或操作系统干预、父进程请求、父进程终止。
|
||
+ 进程阻塞：
|
||
+ 阻塞原语：
|
||
+ 找到要阻塞的进程对应的$PCB$。
|
||
+ 保护进程运行现场，将$PCB$状态信息设置为阻塞态，暂停进程。
|
||
+ 将$PCB$插入事件等待队列，将处理机资源调度给其他就绪态进程。
|
||
+ 引起进程阻塞的事件：
|
||
+ 需要等待系统分配资源。
|
||
+ 需要等待相互合作的其他进程完成工作。
|
||
+ 进程唤醒：
|
||
+ 唤醒原语：
|
||
+ 在事件等待队列中找到$PCB$。
|
||
+ 将$PCB$从等待队列中移除，设置进程为就绪态。
|
||
+ 将$PCB$插入就绪队列，等待被调度。
|
||
+ 引起进程唤醒的事件：
|
||
+ 等待的事件的发生（因何事被阻塞因何事被唤醒）。
|
||
+ 进程切换：
|
||
+ 切换原语：
|
||
+ 将处理机上下文信息，包括程序计数器$PC$和其他寄存器信息存入$PCB$。
|
||
+ $PCB$移入相应队列。
|
||
+ 选择另一个进程执行，并更新其$PCB$。
|
||
+ 更新内存管理的数据结构。
|
||
+ 根据$PCB$恢复新进程所需的运行环境。
|
||
+ 引起进程切换的事件：
|
||
+ 当前时间片到。
|
||
+ 有更高优先级进程到达。
|
||
+ 当前进程主动阻塞。
|
||
+ 当前进程终止。
|
||
|
||
### 进程通信
|
||
|
||
进程通信是进程之间的信息交换。
|
||
|
||
为了保证安全，一个进程不能直接访问另一个进程的地址空间，但是又必须有进程通信。$PV$操作是低级通信方式，高级通信方式有：
|
||
|
||
+ 共享存储：分配一个可以共同使用的共享空间，进程对其的使用必须是互斥的（使用同步互斥工具如$PV$操作）。
|
||
+ 基于数据结构：共享空闲只能放固定的数据结构如数组等。速度慢，限制多，是低级通信方式。
|
||
+ 基于存储：内存中划出一块共享存储区，数据的形式、存放位置都由进程控制而非操作系统。速度更快，限制少，是高级通信方式。
|
||
+ 信息传递：进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
|
||
+ 消息包括消息头和消息体，消息头包括：发送进程$ID$、接受进程$ID$、消息类型、消息长度等格式化的信息。
|
||
+ 消息传递包括：
|
||
+ 直接通信方式：消息直接挂到接受进程的信息缓冲队列上。
|
||
+ 间接通信方式：消息先发送到中间实体（信箱）中，因此也称为信箱通信方式，如计算机网络中的电子邮件系统。
|
||
+ 管道通信：是消息传递的特殊方式，指用于链接各自一个的读写进程的一个共享文件，又名$pipe$文件，其实就是内存中开辟一个大小**固定**的缓冲区。
|
||
+ 只能使用半双工的通信，某一时间段内只能单向传输，若要双向同时通信则必须设置两个管道。
|
||
+ 进程需要互斥访问管道，需要满足互斥、同步、确定对方存在。
|
||
+ 数据以字符流的形式写入管道，当满时，写进程的$write()$系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的$read()$系统调用将被阻塞。
|
||
+ 如果没有**写满**则不允许读，如果没有**读空**则不允许写。所以读写都可能被堵塞。
|
||
+ 数据一旦被读出就被管道抛弃，所以读进程只能**至多**有一个，否则可能会读错。
|
||
+ 共享文件（文件系统）：利用操作系统提供的文件共享功能实现进程之间的通信。
|
||
+ 信号量：也需要信号量来解决文件共享操作中的同步和互斥问题。
|
||
|
||
由于不同进程拥有不同代码段和数据段，全局变量是针对同一个进程而言，所以全局变量不能用来交换数据。
|
||
|
||
### 线程
|
||
|
||
#### 线程概念
|
||
|
||
传统而看，进程是程序的一次执行，但是程序的多个功能不能由一个程序顺序处理就能完成，所以一个进程需要同时进行多个任务，所以就引入了线程来增加并发度。
|
||
|
||
由线程$ID$、程序计数器$PC$、寄存器集合和堆栈组成。
|
||
|
||
线程是$CPU$**执行**的基本单元，是程序执行流的最小单位，是处理机的分配单元。进程只作为除$CPU$之外的系统资源的分配单元，即打印机等都是分配给线程而不是进程。
|
||
|
||
#### 线程与进程
|
||
|
||
+ 系统分配调度：
|
||
+ 传统进程机制中，进程是资源分配、调度的基本单位。
|
||
+ 引入线程后，进程是**资源分配**的基本单位，线程是**调度**的基本单位。
|
||
+ 同一进程中，线程切换不会导致进程切换，在不同进程进行线程切换才会引起进程切换。
|
||
+ 拥有资源：
|
||
+ 进程都是拥有资源的基本单位，线程除了必备的资源不拥有系统资源。
|
||
+ 线程可以拥有同进程的所有资源。
|
||
+ 同进程的所有线程共享进程地址空间。
|
||
+ 并发性：
|
||
+ 传统进程机制中，只能进程间并发。
|
||
+ 引入线程后，各线程间也能并发，提升了并发度。
|
||
+ 系统开销：
|
||
+ 传统的进程间并发，需要切换进程的运行环境，系统开销很大。
|
||
+ 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小。
|
||
+ 引入线程后，并发所带来的系统开销减小。
|
||
+ 同一进程多个线程共享进程地址空间，所以线程同步通信非常容易。
|
||
+ 地址空间和其他资源：
|
||
+ 进程间不可见，同一进程的线程间可见。
|
||
+ 通信：
|
||
+ 进程间通信$IPC$需要进程同步和互斥来保证一致性。
|
||
+ 线程间可以直接读写进程数据段如全局变量完成。
|
||
|
||
#### 线程属性
|
||
|
||
+ 线程是处理机调度的单位。
|
||
+ 多$CPU$计算机中，各个线程可占用不同的$CPU$。
|
||
+ 每个线程都有一个线程$ID$、线程控制块$TCB$（记录线程执行的寄存器和栈等现场状态）。
|
||
+ 线程也有就绪、阻塞、运行三种基本状态。
|
||
+ 线程几乎不拥有系统资源。
|
||
+ 同一进程的不同线程间共享进程的资源。
|
||
+ 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预。
|
||
+ 没有独立地址空间。
|
||
+ 同一进程中的线程切换，不会引起进程切换。
|
||
+ 不同进程中的线程切换，会引起进程切换。
|
||
+ 切换同进程内的线程，系统开销很小。
|
||
+ 切换进程，系统开销较大。
|
||
+ 只有执行、就绪、阻塞三种状态。
|
||
|
||
#### TCB
|
||
|
||
线程控制块$TCB$是与进程的控制块$PCB$相似的子控制块，只是$TCB$中所保存的线程状态比$PCB$中保存少而已：
|
||
|
||
+ 线程标识符。
|
||
+ 寄存器。
|
||
+ 运行状态。
|
||
+ 优先级。
|
||
+ 专有存储区。
|
||
+ 堆栈指针。
|
||
|
||
实际上只有内核级线程才有$TCB$。
|
||
|
||
#### 线程实现
|
||
|
||
线程库（$thread\,library$）是为程序员提供创建和管理线程的$API$。线程库中的线程都是单例模式，所以不同的进程使用线程库中的同名线程都是同一个线程。实现线程库主要的方法有如下两种：
|
||
|
||
1. 在用户空间中提供一个没有内核支持的库。这种库的所有代码和数据结构都位于用户空间中。这意味着，调用库内的一个函数只导致用户空间中的一个本地函数的调用。
|
||
2. 实现由操作系统直接支持的内核级的一个库。对于这种情况，库内的代码和数据结构位于内核空间。调用库中的一个$API$函数通常会导致对内核的系统调用。
|
||
|
||
用户级线程$ULT$：
|
||
|
||
+ 用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责（包括线程切换）。
|
||
+ 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
|
||
+ 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。用户级线程对用户不透明，对操作系统透明。
|
||
+ 所以操作系统无法操作用户级线程，就不会给用户级线程分配$TLB$。
|
||
<!-- + 操作系统无法进行线程调度，只能进行进程调度。 -->
|
||
|
||
优点：
|
||
|
||
+ 线程切换不需要转换到内核空间，节省了模式切换的开销。
|
||
+ 调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法。
|
||
+ 用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分。
|
||
|
||
缺点：
|
||
|
||
+ 系统调用的阻塞问题，当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都被阻塞。
|
||
+ 不能发挥多处理机的优势，内核每次分配给一个进程的仅有一个$CPU$，因此进程中仅有一个线程能执行。
|
||
|
||
内核级线程（内核支持的线程）$KLT$：
|
||
|
||
+ 内核级线程的管理工作由操作系统内核完成。
|
||
+ 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
|
||
+ 内核级线程就是从操作系统内核视角看能看到的线程。
|
||
<!-- + 由于操作系统只能看见内核级线程，所以只有内核级线程才是处理机分配的单位，此时操作系统才能进行线程调度。 -->
|
||
|
||
优点：
|
||
|
||
+ 能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行。
|
||
+ 如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可运行其他进程中的线程。
|
||
+ 内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小。
|
||
+ 内核本身也可采用多线程技术，可以提高系统的执行速度和效率。
|
||
|
||
缺点：
|
||
|
||
+ 同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大。这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的。
|
||
|
||
组合方式：
|
||
|
||
+ 有些系统使用组合方式的多线程实现。
|
||
+ 在组合实现方式中，内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程。
|
||
+ 一些内核级线程对应多个用户级线程，这是用户级线程通过时分多路复用内核级线程实现的。
|
||
+ 同一进程中的多个线程可以同时在多处理机上并行执行，且在阻塞一个线程时不需要将整个进程阻塞。
|
||
|
||
#### 多线程模型
|
||
|
||
组合方式同时支持用户线程和内核线程，对于用户级线程如何映射到内核级线程的问题出现了“多线程模型”问题。
|
||
|
||
+ 多对一模型：
|
||
+ 多个用户级线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。多个用户级线程共用一个线程控制块。
|
||
+ 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。
|
||
+ 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
|
||
+ 一对一模型：
|
||
+ 一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。操作系统给每个用户线程建立一个线程控制块。
|
||
+ 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
|
||
+ 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
|
||
+ 多对多模型：
|
||
+ 在同时支持用户级线程和内核级线程的系统中，可以使用二者结合的方式，将$n$个用户级线程映射到$m$个内核级线程上（$n\geqslant m$）。
|
||
+ 克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
|
||
|
||
## 处理机调度
|
||
|
||
### 处理机调度的概念
|
||
|
||
+ 处理机：包括中央处理器，主存储器，输入输出接口，加接外围设备就构成完整的计算机系统。处理机是处理计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件。
|
||
+ 处理机调度：在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
|
||
|
||
### 处理机调度的层次
|
||
|
||
|工作内容|发生位置|发生频率|对进程状态的影响
|
||
:----:|:------:|:-----:|:-----:|:-------------:
|
||
高级调度（作业调度）|按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程|外存→内存（面向作业）|一个作业一个调入一次调出|无→创建态→就绪态
|
||
中级调度（内存调度）|按照某种规则，从挂起队列中选择合适的进程将其数据调回内存|外存→内存（面向进程）|中等|挂起态→就绪态（阻塞挂起→阻塞态）
|
||
低级调度(进程调度）|按照某种规则，从就绪队列中选择一个进程为其分配处理机|内存→$CPU$|最高|就绪态→运行态
|
||
|
||
#### 高级调度
|
||
|
||
即作业调度：
|
||
|
||
+ 由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业从外存调入内存的顺序。一般一个作业包含多个进程。
|
||
+ 高级调度按一定的原则从外存上处于后备队列的作业中挑选一个(或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立$PCB$），以使它（们）获得竞争处理机的权利。
|
||
+ 高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的$PCB$，作业调出时才撤销$PCB$。
|
||
+ 多道批处理系统多具备，其他系统一般不需要。
|
||
+ 高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。
|
||
+ 调动执行频率低。
|
||
|
||
#### 中级调度
|
||
|
||
即内存调度：
|
||
|
||
+ 引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。
|
||
+ 目的是为了提高内存利用率和系统吞吐量。
|
||
+ 暂时调到外存等待的进程状态为挂起状态。值得注意的是，$PCB$并不会一起调到外存，而是会常驻内存。$PCB$中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的$PCB$来保持对各个进程的监控、管理。被挂起的进程$PCB$会被放到内存里的挂起队列中，当条件具备转为就绪态。
|
||
+ 中级调度就是要决定将哪个处于挂起状态的进程重新调入内存。
|
||
+ 一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。
|
||
|
||
#### 低级调度
|
||
|
||
即进程调度：
|
||
|
||
+ 其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。
|
||
+ 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
|
||
+ 进程调度的频率很高，一般几十毫秒一次。
|
||
|
||
### 进程调度
|
||
|
||
进程调度是最低级的调度也是其他调度的基础，是内核程序。
|
||
|
||
#### 调度程序
|
||
|
||
即调度器，用于调度和分派$CPU$的组件。
|
||
|
||
+ 排队器。
|
||
+ 分派器。
|
||
+ 上下文切换器。
|
||
|
||
#### 进程调度的时机
|
||
|
||
需要进行进程调度和切换：
|
||
|
||
+ 当前运行程序主动放弃处理机（非剥夺调度）：
|
||
+ 进程正常终止。
|
||
+ 出现异常终止。
|
||
+ 进程主动请求阻塞（如等待$I/O$）。
|
||
+ 当前运行程序被动放弃处理机（剥夺式调度）：
|
||
+ 分配时间片用完。
|
||
+ 有更紧急的事件需要处理（如$I/O$中断）。
|
||
+ 优先级更高进程进入就绪队列。
|
||
+ 中断处理结束。
|
||
+ 自陷处理结束。
|
||
|
||
不能进行进程调度和切换：
|
||
|
||
+ 在处理中断的过程中。中断处理过程复杂，很难做到在中断处理过程中进行进程切换；与硬件密切相关，不属于某一进程。
|
||
+ 进程在操作系统**内核程序临界区**中。
|
||
+ 临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
|
||
+ 临界区：访问临界资源的那段代码。
|
||
+ 内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的$PCB$组成）。
|
||
+ 进程访问时会上锁，而如果还没退出临界区（还没解锁）就进行进程调度但是进程调度相关的程序也需要访问就绪队列，但此时就绪队列被锁住了，因此无法顺利进行进程调度。
|
||
+ 内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。
|
||
+ 而如果是普通程序临界区时，如在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致$CPU$一直空闲，所以为了保证效率进程在操作系统普通程序临界区时运行进程调度。
|
||
+ 在原子操作过程中（原语）。原子操作不可中断，更不能切换进程，要一气呵成（如修改$PCB$中进程状态标志，并把$PCB$放到相应队列）。
|
||
|
||
进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。
|
||
|
||
现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。
|
||
|
||
内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设$PC$寄存器等相关工作之后，开始运行新的进程。
|
||
|
||
#### 进程调度的方式
|
||
|
||
针对操作系统是否可以剥夺进程处理机，进程调度方式分为：
|
||
|
||
+ 非剥夺调度方式，又称非抢占方式：
|
||
+ 只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
|
||
+ 实现简单，系统开销小但是无法及时处理紧急任务。
|
||
+ 适合于早期的批处理系统。
|
||
+ 剥夺调度方式，又称抢占方式：
|
||
+ 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
|
||
+ 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。
|
||
+ 适合于分时操作系统、实时操作系统。
|
||
|
||
#### 闲逛进程
|
||
|
||
在进程切换时，如果系统中没有就绪进程，就会调度闲逛进程（$idle$）运行，如果没有其他进程就绪，该进程就一直运行，并在执行过程中测试中断。闲逛进程的优先级最低，没有就绪进程时才会运行闲逛进程，只要有进程就绪，就会立即让出处理机。
|
||
|
||
闲逛进程不需要$CPU$之外的资源，它不会被阻塞。
|
||
|
||
#### 线程调度
|
||
|
||
+ 用户级线程调度：
|
||
+ 由于内核并不知道线程的存在，所以内核还是和以前一样，选择一个进程，并给予时间控制。
|
||
+ 由进程中的调度程序决定哪个线程运行。
|
||
+ 用户级线程的线程切换在同一进程中进行，仅需少量的机器指令。
|
||
+ 内核级线程调度：
|
||
+ 内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程。
|
||
+ 对被选择的线程赋予一个时间片，如果超过了时间片，就会强制挂起该线程。
|
||
+ 内核级线程的线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效，这就导致了若干数量级的延迟。
|
||
|
||
### 调度算法
|
||
|
||
指作业与进程的调度算法。
|
||
|
||
+ 批处理系统算法：
|
||
+ $FCFS$。
|
||
+ $SJF/SPF/SRTN$。
|
||
+ $HRRN$。
|
||
+ 交互式系统算法：
|
||
+ $RR$。
|
||
+ $PS$。
|
||
+ $MFQ$。
|
||
|
||
|先来先服务|短作业优先|高响应比优先|时间片轮转|多级反馈队列
|
||
:----:|:--------:|:--------:|:----------:|:----:|:---------:
|
||
能否是可抢占|否|是|是|是|队列内算法不一定
|
||
优点|公平，实现简单|平均等待时间最少，效率最高|兼顾长短作业|兼顾长短作业|兼颐长短作业，有较好的响应时间，可行性强|
|
||
缺点|不利于短作业|长作业会饥饿，估计时间不易确定|计算响应比的开销大|平均等待时间较长，上下文切换浪费时间|无
|
||
适用于|无|作业调度，批处理系统|无|分时系统|通用
|
||
默认决策模式|非抢占|非抢占|非抢占|抢占|抢占
|
||
|
||
$CPU$繁忙型更接近于长作业，少$I/O$所以少中断。而$I/O$繁忙型需要大量$I/O$，等待输入输出数据时会阻塞从而重新排队，所以更接近短作业。
|
||
|
||
#### 算法评价指标
|
||
|
||
+ $CPU$利用率：$CPU$忙碌时间占总时间的比例。其中利用率=$CPU$忙碌（运行）时间÷进程运行总时间。
|
||
+ 系统吞吐量：单位时间内完成作业的数量。系统吞吐量=总共完成多少道作业÷总时间。
|
||
+ 周转时间：从作业被提交到系统开始到作业完成为止的时间间隔。
|
||
+ 它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在$CPU$上执行的时间、进程等待$I/O$操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。
|
||
+ （作业）周转时间=作业完成时间-作业提交时间。
|
||
+ 平均周转时间=各作业周转时间之和÷作业数。
|
||
+ 带权周转时间=作业周转时间÷作业实际运行的时间=(作业完成时间-作业提交时间)÷作业实际运行的时间（$\geqslant1$）。是一个比值，越靠近$1$越合理。
|
||
+ 平均带权周转时间=各作业带权周转时间之和÷作业数。
|
||
+ 等待时间：指进程或作业处于等待处理机状态时间之和。
|
||
+ 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待$I/O$完成的期间其实进程也是在被服务的，所以不计入等待时间。
|
||
+ 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
|
||
+ 一个作业总共需要被$CPU$服务多久，被$I/O$设备服务多久一般是确定不变的，因此调度算法其实只会影响作业或进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。
|
||
+ 如果一个进程到达后要么等待要么运行，则等待时间=周转时间-运行时间。
|
||
+ 如果一个进程又有计算又有$I/O$操作，则等待时间=周转时间-运行时间-$I/O$操作时间。
|
||
+ 响应时间：从用户提交请求到首次产生响应所用的时间。主要用于交互式系统。
|
||
|
||
#### 先来先服务
|
||
|
||
即$FCFS$算法。
|
||
|
||
+ 算法思想：主要从“公平”的角度考虑。
|
||
+ 算法规则：按照作业/进程到达的先后顺序进行服务。
|
||
+ 用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。
|
||
+ 是否可抢占：非抢占式的算法。
|
||
+ 特点：
|
||
+ 优点：公平、算法实现简单。
|
||
+ 缺点：排在长作业(进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。
|
||
+ 即$FCFS$算法对长作业有利，对短作业不利。
|
||
+ 不能作为分时系统和实时系统的主要调度策略。
|
||
+ 利于$CPU$繁忙型作业，不利于$I/O$繁忙型作业（即适用于长作业类型）。
|
||
+ 是否会导致饥饿：不会。
|
||
|
||
#### 短作业优先
|
||
|
||
即$SJF$算法。
|
||
|
||
+ 算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间。
|
||
+ 算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）。
|
||
+ 用于作业/进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先($SPF$，$Shortest\,Process\,First$）算法”。
|
||
+ 特点：
|
||
+ 优点：“最短的”平均等待时间、平均周转时间。
|
||
+ 缺点：
|
||
+ 不公平。对短作业有利，对长作业不利。
|
||
+ 可能产生饥饿现象。
|
||
+ 未考虑作业紧迫性。
|
||
+ 另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
|
||
+ 是否可抢占：$SJF$和$SPF$是非抢占式的算法。但是也有抢占式的版本―——最短剩余时间优先算法（$SRTN$, $Shortest\,Remaining\,Time\,Next$）。
|
||
+ 是否会导致饥饿：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”。
|
||
|
||
1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的。
|
||
2. 很多书上都会说“$SJF$调度算法的平均等待时间、平均周转时间最少”，严格来说，这个表述是错误的，不严谨的。最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。应该加上一个条件“在所有进程同时可运行时，采用$SJF$调度算法的平均等待时间、平均周转时间最少”，或者说“在所有进程都几乎同时到达时，采用$SJF$调度算法的平均等待时间、平均周转时间最少”。如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先，$SRNT$算法）的平均等待时间、平均周转时间最少”。
|
||
3. 虽然严格来说，$SJF$的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如$FCFS$），$SJF$依然可以获得较少的平均等待时间、平均周转时间。
|
||
4. 如果选择题中遇到“$SJF$算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项。
|
||
|
||
#### 高响应比优先
|
||
|
||
即$HRRN$算法。
|
||
|
||
+ 算法思想：要综合考虑作业/进程的等待时间和要求服务的时间，是$FCFS$和$SJF$的综合。
|
||
+ 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。响应比=(等待时间+要求服务时间)/要求服务时间（响应比$\geqslant1$）。
|
||
+ 用于作业/进程调度：即可用于作业调度，也可用于进程调度，但是主要用于作业调度。
|
||
+ 是否可抢占：非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。
|
||
+ 特点：
|
||
+ 综合考虑了等待时间和运行时间（要求服务时间）。
|
||
+ 等待时间相同时，要求服务时间短的优先($SJF$的优点）。
|
||
+ 要求服务时间相同时，等待时间长的优先（$FCFS$的优点）。
|
||
+ 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。
|
||
+ 是否会导致饥饿：不会。
|
||
|
||
#### 时间片轮转
|
||
|
||
即$RR$算法。
|
||
|
||
+ 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。
|
||
+ 算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如$100ms$）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
|
||
+ 用于作业/进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。
|
||
+ 是否可抢占：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知$CPU$时间片已到。
|
||
+ 特点：
|
||
+ 优点：
|
||
+ 公平。
|
||
+ 响应快，适用于分时操作系统。
|
||
+ 缺点：
|
||
+ 由于高频率的进程切换，因此有一定开销。
|
||
+ 不区分任务的紧急程度。
|
||
+ 是否会导致饥饿：不会。
|
||
|
||
+ 常用于分时操作系统，更注重响应时间，所以不怎么关系周转时间。
|
||
+ 如果时间片太大，每个进程在一个时间片内就可以完完成，则时间片轮转算法会退化为先来先服务算法，增大进程响应时间，所以时间片不能太大。
|
||
+ 如果时间片太小，进程切换会频繁发生，需要保存现场恢复环境，增加时间开销。
|
||
+ 时间片分片因素：系统响应时间、就绪队列中的进程数目、系统处理能力。
|
||
+ 一般设计时间片段时要让切换进程的开销不超过$1\%$。
|
||
|
||
#### 优先级
|
||
|
||
也称为优先权调度算法，即$PS$算法。
|
||
|
||
+ 算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
|
||
+ 算法规则：调度时选择优先级最高的作业/进程。$I/O$繁忙型作业要优于计算繁忙型作业（因为$I/O$操作需要及时完成，其无法长时间保存输入输出数据），系统进程的优先权应高于用户进程优先权。
|
||
+ 用于作业/进程调度：既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的$I/O$调度中。
|
||
+ 是否可抢占：抢占式、非抢占式都有。做题时的区别在于：
|
||
+ 非抢占式只需在进程主动放弃处理机时进行调度即可。
|
||
+ 抢占式还需在就绪队列变化时，检查是否会发生抢占，若优先级更高的进程进入就绪队列，则立刻暂停正在运行的进行。
|
||
+ 特点：
|
||
+ 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
|
||
+ 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。
|
||
+ 是否会导致饥饿：会。
|
||
|
||
+ 优先数与优先级的关系要看具体情况，如$Windows$优先级与优先数成正比，$UNIX$中成反比。
|
||
+ 优先级调度算法中就绪队列未必只有一个，可以按照不同优先级来组织。
|
||
+ 可以把优先级更高的进程排在队头位置。
|
||
+ 根据优先级是否可以动态改变，分为：
|
||
+ 静态优先级：创建进程时确定，一直保持不变。依据：进程类型、进程对资源的要求、用户要求。
|
||
+ 动态优先级：创建进程时有初始值，之后根据情况动态调整优先级。依据有进程占用$CPU$时间的长短、就绪进程等待$CPU$时间的长短。
|
||
+ 设置进程优先级：
|
||
+ 系统进程高于用户进程。
|
||
+ 前台进程高于后台进程。即交互性进程高于非交互性进程。
|
||
+ 操作系统更偏好$I/O$型进程（$I/O$繁忙型进程）而不是计算型进程（$CPU$繁忙型进程），$I/O$设备和$CPU$可以并行工作。如果优先让$I/O$繁忙型进程优先运行的话，则越有可能让$I/O$设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。
|
||
+ 调整动态优先级：
|
||
+ 若进程在就绪队列中等待了很长时间，则提升其优先级。
|
||
+ 若进程占用处理机很长时间，则降低其优先级。
|
||
+ 若进程频繁进行$I/O$操作，则提升其优先级。
|
||
|
||
#### 多级反馈队列
|
||
|
||
即$MFQ$算法。
|
||
|
||
+ 算法思想：对时间片轮转调度算法和优先级调度算法的折中权衡，动态调整进程优先级和时间片大小。
|
||
+ 算法规则：
|
||
1. 设置多级就绪队列，各级队列优先级从$1$到$k$依次递减，时间片从小到大依次变大一倍。
|
||
2. 新进程到达时先进入第$1$级队列队尾，按$FCFS$原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。若是被剥夺，则回退到该队列队尾。
|
||
3. 只有第$k$级队列为空时，才会为$k+1$级队头的进程分配时间片，当又有新进程进入优先级较高的队列则立刻抢占给更够优先级的进程。
|
||
+ 用于作业/进程调度：用于进程调度。
|
||
+ 是否可抢占：抢占式的算法。在$k$级队列的进程运行过程中，若更上级的队列（$1\sim k-1$级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回$k$级队列队尾。
|
||
+ 优缺点：
|
||
+ 对各类型进程相对公平（$FCFS$的优点）。
|
||
+ 每个新到达的进程都可以很快就得到响应（$RR$的优点）。
|
||
+ 短进程只用较少的时间就可完成($SPF$的优点）。
|
||
+ 不必实现估计进程的运行时间（避免用户作假）。
|
||
+ 可灵活地调整对各类进程的偏好程度，比如$CPU$密集型进程、$I/O$密集型进程（拓展：可以将因$I/O$而阻塞的进程重新放回原队列，这样$I/O$型进程就可以保持较高优先级）
|
||
+ 是否会导致饥饿：会。
|
||
|
||
各就绪队列的调度算法也可能不是时间片调度算法而是别的，但是基本上都是差不多的计算方式。
|
||
|
||
### 进程切换
|
||
|
||
#### 上下文切换
|
||
|
||
切换$CPU$到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个就是上下文切换。进程切换主要需要完成上下文切换的任务。上下文切换实质上是指处理机从一个进程的运行转到另一个进程上运行，在这个过程中，进程的运行环境产生了实质性的变化。
|
||
|
||
进程切换的过程主要完成了：
|
||
|
||
+ 对原来运行进程各种数据的保存。
|
||
+ 对新的进程各种数据的恢复。
|
||
（如程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）。
|
||
|
||
过程如下：
|
||
|
||
1. 挂起一个进程，保存$CPU$上下文，包括程序计数器和其他寄存器。
|
||
2. 更新$PCB$信息。
|
||
3. 把进程的$PCB$移入相应的队列，如I就绪、在某事件阻塞等队列。
|
||
4. 选择另一个进程执行，并更新其$PCB$。
|
||
5. 跳转到新进程$PCB$中的程序计数器所指向的位置执行。
|
||
6. 恢复处理机上下文。
|
||
|
||
#### 进程切换消耗
|
||
|
||
进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
|
||
|
||
可以使用多个寄存器组，这样切换时只需要简单改变当前寄存器组的指针。
|
||
|
||
#### 进程调度与进程切换区别
|
||
|
||
+ 狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）。
|
||
+ 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
|
||
+ 广义的进程调度包含了选择一个进程和进程切换两个步骤。
|
||
+ 调度是一个决策，而切换是一个实际行为。
|
||
|
||
#### 模式切换与进程切换区别
|
||
|
||
模式切换指从用户态切换到核心态或相反，其进程中断或异常，本身没有改变当前进程所以没有进程切换。
|
||
|
||
进程切换只能在核心态中完成。
|
||
|
||
## 进程同步与互斥
|
||
|
||
### 进程同步与互斥的基本概念
|
||
|
||
#### 进程同步
|
||
|
||
+ 同步也称为直接制约关系。
|
||
+ 在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，如等待、传递信息等，引入了进程同步的概念。进程同步是为了解决进程的异步问题。
|
||
+ 异步性：进程具有异步性的特征。指各并发执行的进程以各自独立的、不可预知的速度向前推进。
|
||
|
||
#### 进程互斥
|
||
|
||
+ 互斥也称间接制约关系。
|
||
+ 进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
|
||
+ 资源共享方式分为：
|
||
+ 互斥共享方式：允许多个进程使用，但是同一个时间段内只允许一个进程访问该资源。
|
||
+ 同时共享方式：允许一个时间短内由多个进程在宏观上同时对其访问。
|
||
|
||
#### 临界资源
|
||
|
||
+ 我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
|
||
+ 对临界资源的访问，必须互斥地进行，从逻辑上分为四个部分：
|
||
+ 进入区：负责检查是否可进入临界区，若可进入则应设置**正在访问临界资源**的标志（上锁），以阻止其他进程同时进入临界区。
|
||
+ 临界区（临界段）：实际访问临界资源的代码。
|
||
+ 退出区：负责解除**正在访问临界资源**的标志（解锁）。
|
||
+ 剩余区：做其他处理。
|
||
+ 进入区和退出区是实现互斥的代码段。
|
||
|
||
#### 互斥访问的原则
|
||
|
||
1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
|
||
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
|
||
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）。
|
||
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
|
||
|
||
### 进程互斥软件实现
|
||
|
||
即在进入区设置并检查一些标志来表明是否有进程在临界区，若有则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。
|
||
|
||
#### 单标志法
|
||
|
||
算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。所以设置一个公用整型变量`turn`用来表示允许进入临界区的进程编号，若`turn=0`则允许$P_0$进入临界区。
|
||
|
||
```cpp
|
||
// turn表示当前允许进入临界区的进程号
|
||
int turn = 0;
|
||
|
||
// P0进程
|
||
// 进入区
|
||
while (turn != 1); // ①
|
||
// 临界区
|
||
critical section; // ②
|
||
// 退出区
|
||
turn = 1; // ③
|
||
// 剩余区
|
||
remainder section; // ④
|
||
|
||
// P1进程
|
||
// 进入区
|
||
while(turn != 0); // ⑤
|
||
// 临界区
|
||
critical section; // ⑥
|
||
// 退出区
|
||
turn = 0; // ⑦
|
||
// 剩余区
|
||
remainder section;// ⑧
|
||
```
|
||
|
||
优点：
|
||
|
||
+ `turn`的初值为$0$，即刚开始只允许$0$号进程进入临界区。
|
||
+ 若$P_1$先上处理机运行，则会一直卡在⑤，无法使用临界资源。
|
||
+ 直到$P_1$的时间片用完，发生调度，切换$P_0$上处理机运行。
|
||
+ 而代码①不会卡住$P_0$，$P_0$可以正常访问临界区，在$P_0$访问临界区期间即时切换回$P_1$，$P_1$依然会卡在⑤。
|
||
+ 只有$P_0$在退出区将`turn`改为$1$后，$P_1$才能进入临界区。
|
||
+ 因此，该算法可以实现同一时刻最多只允许一个进程访问临界。
|
||
|
||
缺点：
|
||
|
||
+ `turn`表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改`turn`的值。
|
||
+ 也就是说，对于临界区的访问，一定是按$P_0\rightarrow P_1\rightarrow P_0\rightarrow P_1\rightarrow\cdots$这样轮流访问。
|
||
+ 如果一个进程一直不访问临界区，那么临界资源会被这个进程一直占用。
|
||
+ 违背了空闲让进的原则。
|
||
|
||
#### 双标志先检查法
|
||
|
||
算法思想：设置一个布尔型数组`flag[]`，数组中各个元素用来标记各进程想进入临界区的意愿，比如`flag[0]=ture`意味着$0$号进程 $P_0$现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志`flag[i]`设为`true`，之后开始访问临界区。
|
||
|
||
```cpp
|
||
// 表示进入临界区意愿的数组
|
||
bool flag[2];
|
||
//刚开始设置为两个进程都不想进入临界区
|
||
flag [0] = false;
|
||
flag [1] = false;
|
||
|
||
// P0进程
|
||
// 进入区
|
||
while (flag[1]); // ①
|
||
flag[0] = true; // ②
|
||
// 临界区
|
||
critical section; // ③
|
||
// 退出区
|
||
flag [0] = false; // ④
|
||
// 剩余区
|
||
remainder section;
|
||
|
||
// P1进程
|
||
// 进入区
|
||
while (flag[0]); // ⑤
|
||
flag[1] = true; // ⑥
|
||
// 临界区
|
||
critical section; // ⑦
|
||
// 退出区
|
||
flag[1] = false; // ⑧
|
||
// 剩余区
|
||
remainder section;
|
||
```
|
||
|
||
优点：不需要交替进入。
|
||
|
||
缺点：若按照①⑤②⑥③⑦……的顺序执行，若$P_0$和$P_1$同时检查，发现可以访问，$P_0$和$P_1$将会同时访问临界区，违反忙则等待原则。即在检查对方的$flag$后和切换自己的$flag$前之间有一段时间，结果都会检查通过，检查和修改操作不能一次性进行。
|
||
|
||
#### 双标志后检查法
|
||
|
||
算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。即先将自己标志位设置为`true`再检查对方的标志位，若对方也为`true`则等待，否则进入临界区。
|
||
|
||
```cpp
|
||
// 表示进入临界区意愿的数组
|
||
bool flag[2];
|
||
//刚开始设置为两个进程都不想进入临界区
|
||
flag [0] = false;
|
||
flag [1] = false;
|
||
|
||
// P0进程
|
||
// 进入区
|
||
flag[0] = true; // ①
|
||
while (flag[1]); // ②
|
||
// 临界区
|
||
critical section; // ③
|
||
// 退出区
|
||
flag [0] = false; // ④
|
||
// 剩余区
|
||
remainder section;
|
||
|
||
// P1进程
|
||
// 进入区
|
||
flag[1] = true; // ⑤
|
||
while (flag[0]); // ⑥
|
||
// 临界区
|
||
critical section; // ⑦
|
||
// 退出区
|
||
flag[1] = false; // ⑧
|
||
// 剩余区
|
||
remainder section;
|
||
```
|
||
|
||
若进程同时想进入临界区，按照①⑤②⑥③⑦……的顺序执行，则都发现对方标志位是`true`，$P_0$和$P_1$都不能访问临界区都卡死。
|
||
|
||
因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。
|
||
|
||
#### Peterson算法
|
||
|
||
算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。$Gary\,L.Peterson$想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。每个进程再设置自己的标志后再设置一个变量`turn`不允许进入标志的值，再同时检测另一个进程的状态标志位与不允许进入标志。
|
||
|
||
```cpp
|
||
// 表示进入临界区意愿的数组，初始值都是false
|
||
bool flag[2];
|
||
// turn表示优先让哪个进程进入临界区
|
||
int turn = 0;
|
||
|
||
// P0进程:
|
||
// 进入区
|
||
flag[0] = true; // ①
|
||
turn = 1; // ②
|
||
// 当对方也想进且本进程已经让出优先权就等待
|
||
while (flag[1] && turn==1); //③
|
||
// 临界区
|
||
critical section; // ④
|
||
// 退出区
|
||
flag[0] = false; // ⑤
|
||
// 剩余区
|
||
remainder section;
|
||
|
||
// P1进程:
|
||
// 进入区
|
||
flag[1] = true; // ⑥ 表示自己想进入临界区
|
||
turn = 0; // ⑦ 可以优先让对方进入临界区
|
||
while (flag[0] && turn==0); // ⑧ 对方想进，且最后一次是自己“让梨"，那自己就循环等待
|
||
// 临界区
|
||
critical section; // ⑨
|
||
// 退出区
|
||
flag[1] = false; // ⑩ 访问完临界区，表示自己已经不想访问临界区了
|
||
// 剩余区
|
||
remainder section;
|
||
```
|
||
|
||
如果出现两个进程并发的情况，则其中一个进程必然被卡住，另一个进程必然会执行，所以不存在饥饿和死锁问题。
|
||
|
||
$Peterson$算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。
|
||
|
||
### 进程互斥硬件实现
|
||
|
||
称为**低级方法**，或**元方法**。
|
||
|
||
#### 中断屏蔽
|
||
|
||
+ 利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）。
|
||
+ 关中断后即不允许当前进程被中断，也必然不会发生进程切换。
|
||
+ 直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区。
|
||
+ 优点：简单、高效。
|
||
+ 缺点：
|
||
+ 不适用于多处理机。
|
||
+ 只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）。
|
||
|
||
#### 硬件指令
|
||
|
||
$TS$指令，也有地方称$TestAndSetLock$指令，或$TSL$指令。
|
||
|
||
$TSL$指令是用硬件实现的原子操作，执行的过程不允许被中断，只能一气呵成。
|
||
|
||
读出指定标志后把该标志设置为真。
|
||
|
||
```cpp
|
||
// 布尔型共享变量lock表示当前临界区是否被加锁
|
||
// true表示已加锁，false表示未加锁
|
||
bool TestAndSet (bool *lock){
|
||
bool old;
|
||
old = *lock; // old用来存放lock原来的值
|
||
*lock = true; // 无论之前是否已加锁，都将lock设为true
|
||
return old; // 返回lock原来的值
|
||
}
|
||
|
||
// 以下是使用TSL指令实现互斥的算法逻辑
|
||
while (TestAndSet (&lock)); // ""上锁"并"检查”
|
||
临界区代码段...
|
||
lock = false; // "解锁""
|
||
剩余区代码段...
|
||
```
|
||
|
||
+ 每个临界资源都有一个共享布尔变量`lock`，`true`表示被占用，`false`表示空闲，是初值。
|
||
+ 若刚开始`lock`是`false`，则$TSL$返回的`old`值为`false`，`while`循环条件不满足，直接跳过循环，进入临界区。
|
||
+ 若刚开始`lock`是`true`，则执行$TSL$后`old`返回的值为`true`，`while`循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
|
||
+ $lock$负责唤醒处于就绪态的进程。
|
||
|
||
相比软件实现方法，$TSL$指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
|
||
|
||
+ 优点：
|
||
+ 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞。
|
||
+ 适用于多处理机环境。
|
||
+ 缺点：
|
||
+ 不满足“让权等待”原则。
|
||
+ 暂时无法进入临界区的进程会占用$CPU$并循环执行$TSL$指令，从而导致“忙等”。
|
||
|
||
$Swap$指令有的地方也叫$Exchange$指令，或简称$XCHG$指令。
|
||
|
||
$Swap$指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
|
||
|
||
```cpp
|
||
// Swap指令的作用是交换两个变量的值
|
||
Swap (bool *a,bool *b){
|
||
bool temp;
|
||
temp = *a;
|
||
*a=*b;
|
||
*b = temp;
|
||
}
|
||
|
||
// 以下是用Swap指令实现互斥的算法逻辑
|
||
// lock表示当前临界区是否被加锁
|
||
// 上锁
|
||
bool old = true;
|
||
while (old == true){
|
||
Swap (&lock,&old);
|
||
}
|
||
临界区代码段...
|
||
// 解锁
|
||
lock = false;
|
||
剩余区代码段...
|
||
```
|
||
|
||
逻辑上来看$Swap$和$TSL$并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在`old`变量上），再将上锁标记`lock`设置为`true`，最后检查`old`，如果`old`为`false`则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
|
||
|
||
### 信号量
|
||
|
||
之前软硬件实现的进程互斥都无法解决让权等待问题，所以$Dijkstra$提出实现进程互斥和同步的方法——信号量机制。
|
||
|
||
#### 信号量机制的基础概念
|
||
|
||
+ 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
|
||
+ 信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为$1$的信号量。
|
||
+ 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
|
||
+ 一对原语：`wait(S)`原语和`signal(S)`原语（`S`表示整型量），可以把原语理解为我们自己写的函数，函数名分别为`wait`和`signal`，括号里的信号量`S`其实就是函数调用时传入的一个参数。
|
||
+ $wait$、$signal$原语常简称为$P$、$V$操作（来自荷兰语$proberen$和$verhogen$）。因此，做题的时候常把$wait(S)$、$signal(S)$两个操作分别写为$P(S)$、$V(S)$。
|
||
|
||
#### 整型信号量
|
||
|
||
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
|
||
|
||
与普通整数变量的区别:对信号量的操作只有三种，即初始化、$P$操作、$V$操作。
|
||
|
||
```cpp
|
||
// 加入某计算机系统中有一台打印机，打印机被争用，如果有n台打印机则S初始为为n
|
||
//初始化整型信号量S，表示当前系统中可用的打印机资源数
|
||
#define n 1;
|
||
int S = n;
|
||
// wait原语，相当于“进入区”
|
||
void wait (int &S){
|
||
while (S <= 0); // 如果资源数不够，就一直循环等待
|
||
S=S-1; // 如果资源数够，则占用一个资源
|
||
}
|
||
|
||
// signal原语,相当于“退出区”
|
||
void signal (int &S) {
|
||
S=S+1; // 使用完资源后，在退出区释放资源
|
||
}
|
||
|
||
// 进程
|
||
...
|
||
wait(S); // 进入区，申请资源
|
||
使用打印机资源... // 临界区，访问资源
|
||
signal(S); // 退出区，释放资源
|
||
```
|
||
|
||
“检查”和“上锁”一气呵成，避免了并发、异步导致的问题。
|
||
|
||
存在的问题：只要信号量$S\leqslant0$就不断测试，不满足“让权等待”原则，会发生“忙等”。
|
||
|
||
#### 记录型信号量
|
||
|
||
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。
|
||
|
||
```cpp
|
||
// 记录型信号量的定义
|
||
typedef struct {
|
||
int value;// 剩余资源数
|
||
struct process *L; // 等待队列
|
||
}semaphore;
|
||
|
||
// 某进程需要使用资源时，通过wait原语申请
|
||
void wait (semaphore S) {
|
||
S.value--;
|
||
// 如果剩余资源数不够,使用block原语使进程从运行态进入阻塞态,并把挂到信号量S的等待队列（即阻塞队列）中。
|
||
if (S.value < 0) {
|
||
block(S.L);
|
||
}
|
||
}
|
||
|
||
// 进程使用完资源后，通过signal原语释放
|
||
void signal (semaphore S) {
|
||
S.value++;
|
||
// 释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等德队列中一个进程,该进程从阻塞态变为就绪态
|
||
if (S.value <= 0) {
|
||
wakeup(S.L);
|
||
}
|
||
}
|
||
```
|
||
|
||
+ 在考研题目中`wait(S)`、`signal(S)`也可以记为`P(S)`、`V(S)`，这对原语可用于实现系统资源的“申请”和“释放”。
|
||
+ `S.value`的初值表示系统中某种资源的数目。
|
||
+ 对信号量`S`的一次$Р$操作意味着进程请求一个单位的该类资源，因此需要执行`S.value--`，表示资源数减$1$，当`S.value<0`时表示该类资源已分配完毕，因此进程应调用`block`原语进行自我阻塞（当前运行的进程从运行态变为阻塞态），主动放弃处理机，并插入该类资源的等待队列`S.L`中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
|
||
+ 对信号量`S`的一次$V$操作意味着进程释放一个单位的该类资源，因此需要执行`S.value++`，表示资源数加$1$，若加$1$后仍是`S.value<=0`，表示依然有进程在等待该类资源，因此应调用`wakeup`原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）。
|
||
|
||
#### 信号量机制实现进程互斥
|
||
|
||
互斥信号量默认设置为$1$。
|
||
|
||
1. 分析并发进程的关键活动，划定临界区（如对临界资源打印机的访问就应放在临界区）。
|
||
2. 设置互斥信号量`mutex`，初值为$1$，表示一次只能有一个进程访问。
|
||
3. 互斥信号量取值为$0$或$1$，$0$代表上锁，$1$代表释放。
|
||
4. 在临界区之前执行`P(mutex)`。
|
||
5. 在临界区之后执行`V(mutex)`。
|
||
6. 注意：对不同的临界资源需要设置不同的互斥信号量。
|
||
|
||
```cpp
|
||
// 信号量机制实现互斥
|
||
// 要会自己定义记录型信号量,但如果题目中没特别说明,可以把信号量的声明简写成这种形式
|
||
semaphore mutex=1; // 初始化信号量
|
||
|
||
P1(){
|
||
...
|
||
P(mutex); // 使用临界资源前需要加锁
|
||
临界区代码段...
|
||
V(mutex); // 使用临界资源后需要解锁
|
||
...
|
||
}
|
||
|
||
P2(){
|
||
...
|
||
P(mutex);
|
||
临界区代码段...
|
||
V(mutex);
|
||
...
|
||
}
|
||
```
|
||
|
||
#### 信号量机制实现进程同步
|
||
|
||
进程同步：要让各并发进程按要求有序地推进。
|
||
|
||
同步信号量设置应该分为两种情况，如果期望消息未产生则设置为$0$，若已经产生，则应该设为非$0$的正整数。
|
||
|
||
1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）。如先$P_1$后$P_2$。
|
||
2. 设置同步信号量`S`，初始为$0$。
|
||
3. 同步信号量为整数，释放加一，占用减一。
|
||
4. 在“前操作”之后执行`V(S)`。
|
||
5. 在“后操作”之前执行`P(S)`。
|
||
|
||
```cpp
|
||
// 信号量机制实现同步
|
||
// 初始化同步信号量，初始值为0
|
||
semaphore S=0;
|
||
P1(){
|
||
代码1;
|
||
代码2;
|
||
V(S);
|
||
代码3;
|
||
}
|
||
P2(){
|
||
P(S);
|
||
代码4;
|
||
代码5;
|
||
代码6;
|
||
}
|
||
```
|
||
|
||
+ 若先进行进程$P_1$：
|
||
+ 执行到`V(S)`操作，则`S++`后`S=1`。
|
||
+ 之后当进行$P_2$，执行到`P(S)`操作时，由于`S=1`，表示有可用资源，会执行`S--`，`S`的值变回$0$，$P_2$进程不会执行`block`原语，而是继续往下执行代码$4$。
|
||
+ 若先进行进程$P_2$：
|
||
+ 执行到`P(S)`操作，由于`S=0`，`S--`后`S=-1`，表示此时没有可用资源，因此$P$操作中会执行`block`原语，主动请求阻塞。
|
||
+ 时间片用完后进行进程$P_1$，之后当执行完代码$2$，继而执行`V(S)`操作，`S++`，使`S`变回$0$。
|
||
+ 由于此时有进程在该信号量对应的阻塞队列中，因此会在$V$操作中执行`wakeup`原语，唤醒$P_2$进程。这样$P_2$就可以继续执行代码$4$了。
|
||
|
||
#### 信号量机制实现前驱关系
|
||
|
||
前驱关系其实是多组同步。
|
||
|
||
进程$P_1$中有句代码$S_1$，$P_2$中有句代码$S_2$……$P_6$中有句代码$S_6$。这些代码要求按如下前驱图所示的顺序来执行：
|
||
|
||
```terminal
|
||
|-S4-|
|
||
|-S2-| |
|
||
S1-| |-S5-|-S6
|
||
| |
|
||
|----S3---|
|
||
```
|
||
|
||
其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）因此：
|
||
|
||
1. 要为每一对前驱关系各设置一个同步变量。
|
||
2. 在“前操作”之后对相应的同步变量执行$V$操作。类似表示当前动作$S_i$已经完成。
|
||
3. 在“后操作”之前对相应的同步变量执行$Р$操作。类似检测前一个动作$S_i$是否完成。
|
||
|
||
令$S_1-S_2$之间信号量为$a=0$，$S_1-S_3$之间的信号量$b=0$，$S_2-S_4$之间信号量为$c=0$，$S_2-S_5$之间信号量为$d=0$，$S_4-S_6$之间信号量为$e=0$，$S_5-S_6$之间信号量为$f=0$，$S_3-S_6$之间信号量为$g=0$。
|
||
|
||
每个$S_i$操作都设置一个进程$P_i$。
|
||
|
||
每一条线段靠近根的对当前信号量进行$V$操作，靠近尾的对当前信号量进行$P$操作。
|
||
|
||
再将每个代码结点旁边的操作聚拢在一起，就是每个进程所应该执行的操作。
|
||
|
||
```cpp
|
||
P1() {
|
||
...
|
||
S1;
|
||
V(a);
|
||
V(b);
|
||
...
|
||
}
|
||
P2() {
|
||
...
|
||
P(a);
|
||
S2;
|
||
V(c);
|
||
V(d);
|
||
...
|
||
}
|
||
P3() {
|
||
...
|
||
P(b);
|
||
S3;
|
||
V(g);
|
||
...
|
||
)
|
||
P4() {
|
||
...
|
||
P(c);
|
||
S4;
|
||
V(e);
|
||
...
|
||
}
|
||
P5() {
|
||
...
|
||
P(d);
|
||
S5;
|
||
V(f);
|
||
...
|
||
}
|
||
P6() {
|
||
...
|
||
P(e);
|
||
P(f);
|
||
P(g);
|
||
S6;
|
||
...
|
||
}
|
||
```
|
||
|
||
#### 信号量数值
|
||
|
||
+ $value>0$表示某类可用资源的数量。每次$Р$操作，意味着请求分配一个单位的资源。
|
||
+ $value<=0$表示某类资源已经没有，或者说还有因请求该资源而被阻塞的进程。
|
||
+ $value<=0$时的绝对值，表示等待进程数目。
|
||
|
||
### 进程同步与互斥应用
|
||
|
||
$PV$操作题目分析步骤：
|
||
|
||
1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
|
||
2. 整理思路。根据各进程的操作流程确定$P$、$V$操作的大致顺序。
|
||
3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。
|
||
4. 互斥信号量初值一般为$1$，同步信号量的初始值要看对应资源的初始值是多少。
|
||
|
||
#### 单生产者单消费者多资源问题
|
||
|
||
+ 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（这里的“产品”理解为某种数据）
|
||
+ 生产者、消费者共享一个初始为空、大小为$n$的缓冲区。
|
||
+ 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
|
||
+ 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
|
||
+ 缓冲区是临界资源，各进程必须互斥地访问。
|
||
|
||
关系分析：
|
||
|
||
+ 由缓冲区是临界资源，所以对其访问是互斥关系。
|
||
+ 缓冲区满时，生产者要等待消费者取走产品，消费者取必须在生产者放之前，所以是同步关系。
|
||
+ 缓冲区空时（即没有产品时），消费者要等待生产者放入产品，消费者取必须在生产者放之后，所以是同步关系。
|
||
+ 所以分析得到一共两个实体缓冲区与产品和两个进程，生产者每次要消耗$P$一个空闲缓冲区，并生产$V$一个产品。消费者每次要消耗$P$一个产品，并释放一个空闲缓冲区$V$。往缓冲区放入/取走产品需要互斥。
|
||
|
||
所以设置三个变量，不能合并：
|
||
|
||
```cpp
|
||
semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问
|
||
semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量，交给生产者判断
|
||
semaphore full = 0; // 同步信号量，表示产品的数量，也即非空缓冲区的数量，交给消费者判断
|
||
|
||
// 生产者
|
||
producer() {
|
||
// 不断循环
|
||
while(1){
|
||
生产一个产品;
|
||
P(empty); // 获取一个空闲缓冲区
|
||
// 进入临界区
|
||
P(mutex); // 上锁缓冲区
|
||
把产品放入缓冲区;
|
||
V(mutex); // 解锁缓冲区
|
||
// 离开临界区
|
||
V(full); // 增加一个产品
|
||
}
|
||
}
|
||
// 消费者
|
||
consumer() {
|
||
while (1){
|
||
P(full); //消耗一个产品（非空缓冲区）
|
||
P(mutex); // 上锁缓冲区
|
||
从缓冲区取出一个产品;
|
||
V(mutex); // 解锁缓冲区
|
||
V(empty); // 增加一个空闲缓冲区
|
||
使用产品;
|
||
}
|
||
}
|
||
```
|
||
|
||
若调换$P$操作顺序会怎么样？（$empty$和$full$的$P$操作必然在$mutex$的$P$操作之前，如果先上锁再获取会有问题）
|
||
|
||
+ 若此时缓冲区内已经放满产品，则`empty=0`，`full=n`。
|
||
+ 则生产者进程执行`P(mutex)`使`mutex`变为`0`上锁，再执行`P(empty)`，由于已没有空闲缓冲区，因此生产者被阻塞。
|
||
+ 由于生产者阻塞，因此切换回消费者进程。消费者进程执行`P(mutex)`，由于`mutex`为`0`，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。
|
||
+ 这就造成了生产者等待消费者对产品消费来释放空闲缓冲区，而消费者又等待生产者解锁临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。
|
||
+ 同样的，若缓冲区中没有产品，即`full=0`，`empty=n`，按先消费者后生产者的顺序执行也会发生死锁。
|
||
+ 因此，实现互斥的$P$操作一定要在实现同步的$P$操作之后。可以理解为要先拿到这个空间再上锁，若没有就拿到就上锁，那么其他进程也用不了这个空间。
|
||
|
||
而由于$V$操作是释放不会导致进程阻塞，所以两个$V$操作可以交换顺序。
|
||
|
||
+ 生产者消费者问题是一个互斥、同步的综合问题。
|
||
+ 对于初学者来说最难的是发现题目中隐含的两对同步关系。
|
||
+ 有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的“一前一后问题”，因此也需要设置两个同步信号量。前生产者$V$后消费者$P$的关系就是`full`，前消费者$V$后生产者$P$的关系就是`empty`。
|
||
|
||
#### 多生产者多消费者指定单资源问题
|
||
|
||
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用$PV$操作实现上述过程。
|
||
|
||
关系分析：
|
||
|
||
+ 父母分别为两个生产者进程，子女分别为两个消费者进程。
|
||
+ 实体有三个，盘子、苹果、橘子。
|
||
+ 盘中是一个大小为$1$，初始为空的缓冲区，对缓冲区盘子需要互斥使用。
|
||
+ 只有父亲放入苹果女儿才能取出，所以是同步关系。
|
||
+ 只有母亲放入橘子儿子才能取出，所以是同步关系。
|
||
+ 只有盘子空时，父亲或母亲才能放水果，所以也是同步关系。
|
||
+ 而儿子女儿之间没有同步和互斥关系，所以不用管。
|
||
|
||
所以对于互斥关系设置一个互斥信号量`mutex=1`，对于苹果设置为`apple=0`，对于橘子设置为`orange=0`，对于向拍子放水果设置`plate=1`（也可以设置为$0$，后面的处理不同）。
|
||
|
||
```cpp
|
||
// 实现互斥访问盘子（缓冲区）
|
||
semaphore mutex = 1;
|
||
// 盘子中有几个苹果
|
||
semaphore apple = 0;
|
||
// 盘子中有几个橘子
|
||
semaphore orange= 0;
|
||
// 盘子中还可以放多少个水果
|
||
semaphore plate = 1;
|
||
|
||
// 先准备一个苹果，放苹果之前，先判断盘子里是否为空（P一下盘子，检查盘子中还可以放多少个水果），如果盘子为空进行加锁，然后再将苹果放入进去（V一下苹果，数量+1）
|
||
dad () {
|
||
while (1){
|
||
准备一个苹果;
|
||
P(plate);
|
||
P(mutex);
|
||
把苹果放入盘子;
|
||
V(mutex);
|
||
V(apple);
|
||
}
|
||
}
|
||
|
||
// 先准备一个橘子，放橘子之前，先判断盘子里是否为空（P一下盘子，检查盘子中还可以放多少个水果），如果盘子为空进行加锁，然后再将橘子放入进去（V一下橘子，数量+1）
|
||
mom() {
|
||
while (1){
|
||
准备一个橘子;
|
||
P(plate);
|
||
P(mutex);
|
||
把橘子放入盘子;
|
||
V(mutex);
|
||
V(orange);
|
||
}
|
||
}
|
||
|
||
// 拿苹果之前，先判断盘子里有没有苹果（P一下苹果，若没有苹果，自己被阻塞），如果有就锁定盘子，取出苹果，解锁，然后告诉父母，盘子为空了（V一下盘子）
|
||
daughter() {
|
||
while (1){
|
||
P(apple);
|
||
P(mutex);
|
||
从盘中取出苹果;
|
||
V(mutex);
|
||
V(plate);
|
||
吃掉苹果;
|
||
}
|
||
}
|
||
|
||
// 拿橘子之前，先判断盘子里有没有橘子（P一下橘子，若没有橘子，自己被阻塞），如果有就锁定盘子，取出橘子，解锁，然后告诉父母，盘子为空了（V一下盘子）
|
||
son(){
|
||
while (1){
|
||
P(orange);
|
||
P(mutex);
|
||
从盘中取出橘子;
|
||
V(mutex);
|
||
V(plate);
|
||
吃掉橘子;
|
||
}
|
||
}
|
||
```
|
||
|
||
`P(plate/apple/orange)`和`V(plate/apple/orange)`实现了同步使用盘子/苹果/橘子，而`P(mutex)`和`V(mutex)`实现互斥使用盘子。
|
||
|
||
如果不使用互斥量会怎么样？
|
||
|
||
+ 刚开始，儿子、女儿进程即使上处理机运行也会被阻塞（$apple$和$orange$刚开始都是$0$，所以被阻塞）。
|
||
+ 如果刚开始是父亲进程先上处理机运行，则父亲`P(plate)`，可以访问盘子→母亲`P(plate)`，阻塞等待盘子→父亲放入苹果`V(apple)`→女儿进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源（盘子）→女儿`P(apple)`，访问盘子，`V(plate)`，等待盘子的母亲进程被唤醒→母亲进程访问盘子（其他进程暂时都无法进入临界区）→后续操作。
|
||
+ 即使不设置专门的互斥信号量`mutex`，也不会出现多个进程同时访问盘子的现象。
|
||
+ 原因在于本题中的缓冲区大小为`1`，在任何时刻，`apple`、`orange`、`plate`三个同步信号量中最多只有一个是$1$。因此在任何时刻，最多只有一个进程的$P$操作不会被阻塞，并顺利地进入临界区，此时互斥关系全部变成同步关系。
|
||
+ 而如果缓冲区大于$1$，则父母两个可以同时访问临界区，可能导致数据覆盖，所以必须使用互斥信号量。
|
||
|
||
解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系：
|
||
|
||
+ 在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。
|
||
+ 比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：
|
||
+ 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果，如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果。
|
||
+ 这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了?
|
||
+ 正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”。将苹果和橘子都归为水果，而互斥的是盘子而不是不同的水果，同步的是先盘子再水果。
|
||
+ 盘子变空事件→放入水果事件。“盘子变空事件”既可由儿子引发，也可由女儿引发；“放水果事件"既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了。
|
||
|
||
#### 读者写者问题
|
||
|
||
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求:
|
||
|
||
1. 允许多个读者可以同时对文件执行读操作。
|
||
2. 只允许一个写者往文件中写信息。
|
||
3. 任一写者在完成写操作之前不允许其他读者或写者工作写。
|
||
4. 写者执行写操作前，应让已有的读者和写者全部退出。
|
||
|
||
关系分析：
|
||
|
||
+ 具有两类进程：写进程、读进程。
|
||
+ 互斥关系：写进程-写进程、写进程-读进程。
|
||
+ 读进程与读进程不存在互斥问题。写者进程和任何进程都互斥，设置一个互斥信号量`rw`，在写者访问共享文件前后分别执行$P$、$V$操作。
|
||
+ 读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对`rw`执行$P$、$V$操作。
|
||
+ 如果所有读者进程在访问共享文件之前都执行$P(rw)$操作，那么会导致各个读进程之间也无法同时访问文件。所以读者写者问题的核心思想――怎么处理该读者共享的问题呢？即读同步。
|
||
+ `P(rw)`和`V(rw)`其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量`count`来记录当前有几个读进程在访问文件，这个也需要保持读进程互斥，避免多个读进程同时操作导致计数错误。
|
||
|
||
```cpp
|
||
// 用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件，1代表空闲
|
||
semaphore rw = 1;
|
||
// 记录当前有几个读进程在访问文件
|
||
int count = 0;
|
||
// 用于保证对count变量的互斥访问
|
||
semaphore mutex = 1;
|
||
|
||
writer() {
|
||
while(1){
|
||
P(rw); // 写之前”加锁”
|
||
写文件...
|
||
V(rw); // 写之后"解锁”
|
||
}
|
||
}
|
||
|
||
reader() {
|
||
while(1){
|
||
P(mutex); // 各读进程互斥访问count
|
||
if(count==0){
|
||
P(rw); //第一个读进程负责"加锁”
|
||
}
|
||
count++; // 访问文件的读进程数+1
|
||
V(mutex); // 释放对count的锁
|
||
读文件...
|
||
P(mutex); // 各读进程互斥访问count
|
||
count--; // 访问文件的读进程数-1
|
||
if(count==0){
|
||
v(rw); // 最后一个读进程负责”解锁"
|
||
}
|
||
V(mutex); // 释放对count的锁
|
||
}
|
||
}
|
||
```
|
||
|
||
这个算法中读进程是优先的，（因为只要有读进程读写进程就永远无法写而读进程可以一直读），所以写进程可能饥饿。
|
||
|
||
若希望写进程优先，则当读进程读共享文件时，有写进程访问就立刻禁止后续读进程的请求，当前所有读进程都执行完毕后立刻执行写进程，只有无写进程执行再执行读进程。
|
||
|
||
所以需要再添加一个信号量并进行一对$PV$操作。
|
||
|
||
```cpp
|
||
// 用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件，1代表空闲
|
||
semaphore rw = 1;
|
||
// 记录当前有几个读进程在访问文件
|
||
int count = 0;
|
||
// 用于保证对count变量的互斥访问
|
||
semaphore mutex = 1;
|
||
// 用于实现"写优先"
|
||
semaphore w=1;
|
||
|
||
writer() {
|
||
while(1){
|
||
P(w); // 当无其他写进程时进入写
|
||
P(rw); // 写之前”加锁”
|
||
写文件...
|
||
V(rw); // 写之后"解锁”
|
||
V(w); // 恢复对共享文件的可读可写
|
||
}
|
||
}
|
||
|
||
reader() {
|
||
while(1){
|
||
P(w); // 当无写进程时进入，若当前有写进程就不允许有新的读进程读，在这里堵塞
|
||
P(mutex); // 各读进程互斥访问count
|
||
if(count==0){
|
||
P(rw); //第一个读进程负责"加锁”
|
||
}
|
||
count++; // 访问文件的读进程数+1
|
||
V(mutex); // 释放对count的锁
|
||
V(w); // 恢复对共享文件的可读可写，w的V操作位置无所谓
|
||
读文件...
|
||
P(mutex); // 各读进程互斥访问count
|
||
count--; // 访问文件的读进程数-1
|
||
if(count==0){
|
||
v(rw); // 最后一个读进程负责”解锁"
|
||
}
|
||
V(mutex); // 释放对count的锁
|
||
}
|
||
}
|
||
```
|
||
|
||
当前实现的是实际上是按照进程进入顺序来执行，是**读写公平法**，若有多个读进程下一个执行的进程仍是读进程，没有真正实现写进程最优先。
|
||
|
||
+ 读者写者问题为我们解决复杂的互斥问题提供了一个参考思路。
|
||
+ 其核心思想在于设置了一个计数器`count`用来记录当前正在访问共享文件的读进程数。我们可以用`count`的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。
|
||
+ 另外，对`count`变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量对`count`进行$PV$操作。
|
||
+ 最后，还要认真体会我们是如何解决“写进程饥饿”问题的。
|
||
+ 绝大多数的考研$PV$操作大题都可以用之前介绍的几种生产者消费者问题的思想来解决，如果遇到更复杂的问题，可以想想能否用读者写者问题的这几个思想来解决。
|
||
|
||
#### 资源抢占问题
|
||
|
||
一张圆桌上坐着$5$名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
|
||
|
||
系统中有$5$个哲学家进程，$5$位哲学家与左右邻居对其中间筷子的访问是互斥关系。
|
||
|
||
这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
|
||
|
||
信号量设置。定义互斥信号量数组`chopstick[5]={1,1,1,1,1}`用于实现对$5$个筷子的互斥访问。并对哲学家按$0\sim4$编号，哲学家$i$左边的筷子编号为$i$，右边的筷子编号为$(i+1)\%5$。
|
||
|
||
为了防止死锁：
|
||
|
||
1. 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
|
||
2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
|
||
3. 同时仅允许当一个哲学家左右两支筷子都可用时才允许他抓起筷子。（一个时刻只有一个哲学家才能尝试拿筷子）
|
||
|
||
使用第三种方法：
|
||
|
||
```cpp
|
||
semaphore chopstick[5]={1,1,1,1,1}; // 设置五根筷子的信号量
|
||
semaphore mutex = 1; // 互斥地取筷子
|
||
|
||
//i号哲学家的进程
|
||
Pi() {
|
||
while(1){
|
||
P(mutex); // 取筷子前获取互斥量
|
||
P(chopstick[i]); // 拿左
|
||
P(chopstick[(i+1)%5]); // 拿右
|
||
V(mutex); // 释放互斥量
|
||
吃饭...
|
||
V(chopstick[i]); // 放左
|
||
V(chopstick[(i+1)%5]); // 放右
|
||
思考...
|
||
}
|
||
}
|
||
```
|
||
|
||
+ 哲学家进餐问题的关键在于解决进程死锁。
|
||
+ 这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。
|
||
+ 如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。
|
||
|
||
#### 单生产者多消费者单指定资源问题
|
||
|
||
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。
|
||
|
||
桌子可以抽象为容量为$1$的缓冲区，要互斥访问。
|
||
|
||
组合一：纸+胶水；组合二：烟草+胶水；组合三：烟草+纸。
|
||
|
||
同步关系（从事件的角度来分析）：桌上有组合一→第一个抽烟者取走东西；桌上有组合二→第二个抽烟者取走东西；桌上有组合三→第三个抽烟者取走东西；发出完成信号→供应者将下一个组合放到桌上。
|
||
|
||
抽烟者抽烟与供应者准备烟互斥，同理由于缓冲区为$1$，所以互斥变量`mutex`可有可无，因为四个信号量同时只能有一个为$1$，天然互斥。
|
||
|
||
对于同步关系分别设置`offer1=0`、`offer2=0`、`offer3=0`、`finish=0`。
|
||
|
||
```cpp
|
||
semaphore offer1 = 0; // 桌上组合一的数量
|
||
semaphore offer2 = 0; // 桌上组合二的数量
|
||
semaphore offer3 = 0; // 桌上组合三的数量
|
||
semaphore finish = 0; // 抽烟是否完成
|
||
int i = 0; // 用于实现三个抽烟者轮流抽烟
|
||
|
||
provider() {
|
||
while(1){
|
||
// 根据i选择提供材料
|
||
if(i==0){
|
||
将组合一放桌上;
|
||
V(offer1);
|
||
}
|
||
else if(i==1){
|
||
将组合二放桌上;
|
||
V(offer2);
|
||
}
|
||
else if(i==2){
|
||
将组合三放桌上;
|
||
V(offer3);
|
||
}
|
||
// 向下一个抽烟者提供
|
||
i=(i+1)%3;
|
||
// 等待抽烟者反馈
|
||
P(finish);
|
||
}
|
||
}
|
||
|
||
smoker1() {
|
||
while(1){
|
||
P(offer1); // 占有组合
|
||
从桌上拿走组合一;
|
||
卷烟;
|
||
抽掉;
|
||
// 反馈抽烟完成
|
||
V(finish);
|
||
}
|
||
}
|
||
|
||
smoker2() {
|
||
while(1){
|
||
P(offer2); // 占有组合
|
||
从桌上拿走组合而;
|
||
卷烟;
|
||
抽掉;
|
||
// 反馈抽烟完成
|
||
V(finish);
|
||
}
|
||
}
|
||
|
||
smoker3() {
|
||
while(1){
|
||
P(offer3); // 占有组合
|
||
从桌上拿走组合三;
|
||
卷烟;
|
||
抽掉;
|
||
// 反馈抽烟完成
|
||
V(finish);
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
+ 吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。
|
||
+ 值得吸取的精华是“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”，注意体会我们是如何用一个整型变量$i$实现这个“轮流”过程的。
|
||
+ 若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个$V$操作应该放在各自对应的“事件”发生之后的位置。
|
||
|
||
### 管程
|
||
|
||
此前一般使用信号量机制来完成进程互斥同步，但是编写程序困难，易出错。
|
||
|
||
管程是进程同步工具，解决信号量机制大量同步操作分散的问题。
|
||
|
||
#### 管程的概念
|
||
|
||
管程是一种特殊的软件模块，有这些部分组成：
|
||
|
||
1. 局部于管程的共享数据结构（临界区）与其说明。
|
||
2. 对该数据结构进行操作的一组过程或函数。
|
||
3. 对局部于管程的共享数据设置初始值的语句。
|
||
4. 管程名字。
|
||
|
||
管程的基本特征：
|
||
|
||
1. 局部于管程的数据只能被局部于管程的过程所访问。
|
||
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据。（即管程中定义的共享数据结构只能被管程定义的函数所修改）
|
||
3. 每次仅允许一个进程在管程内执行某个内部过程。（在一个时刻内一个函数只能被一个进程使用）
|
||
4. 管程是被进程调用的，管程是语法范围，无法创建和撤销。
|
||
|
||
#### 条件变量
|
||
|
||
通过条件变量来实现阻塞进程。由于一个进程被阻塞的原因可能有多个，所以管程中设置多个条件变量，每个条件变量保存一个等待队列，用于记录因该条件变量而阻塞的所有进程。对条件变量只有两个操作：`wait`和`signal`。所以管程调用这两个操作时都**不用**判断条件，直接阻塞或唤醒。
|
||
|
||
+ `x.wait`：当`x`对应的条件不满足时，正在调用管程的进程调用`x.wait`将自己插入`x`条件的等待队列，并释放管程。此时其他进程可以使用该管程。
|
||
+ `x.signal`：`x`对应的条件发生了变化，则调用`x.signal`，唤醒一个因`x`条件而阻塞的进程。
|
||
|
||
```cpp
|
||
monitor Demo {
|
||
共享数据结构 S;
|
||
condition x; //定义一个条件变量×
|
||
init code(){}
|
||
take away(){
|
||
if(S<=0) x.wait();
|
||
// 资源不够,在条件变量×上阻塞等待
|
||
资源足够，分配资源，做一系列相应处理;
|
||
}
|
||
give_back(){
|
||
归还资源，做一系列相应处理;
|
||
if(有进程在等待) x.signal; //唤醒一个阻塞进程
|
||
}
|
||
}
|
||
```
|
||
|
||
条件变量与信号量：
|
||
|
||
+ 相似点：条件变量的$wait/signal$操作类似于信号量的$PV$操作，可以实现进程的阻塞/唤醒。
|
||
+ 不同点：条件变量是“没有值”的，仅实现了“排队等待”功能（所以一旦调用就不用判断，直接阻塞或释放）；而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。
|
||
|
||
#### 处理同步互斥问题
|
||
|
||
1. 需要在管程中定义共享数据（如生产者消费者问题的缓冲区）。
|
||
2. 需要在管程中定义用于访问这些共享数据的“入口”—―其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）。
|
||
3. 只有通过这些特定的“入口”才能访问共享数据。
|
||
4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的，程序员不用关心）。
|
||
5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）。可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
|
||
|
||
## 死锁
|
||
|
||
### 死锁的概念
|
||
|
||
#### 死锁的定义
|
||
|
||
在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。
|
||
|
||
#### 死锁、饥饿、死循环
|
||
|
||
都是进程无法顺利向前推进的现象（故意设计的死循环除外）。
|
||
|
||
|区别
|
||
:----:|:--:
|
||
死锁|死锁一定是“循环等待对方手里的资源”导致的，因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态
|
||
饥饿|可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态（如长期得不到需要的$I/O$设备），也可能是就绪态（长期得不到处理机）
|
||
死循环|可能只有一个进程发生死循环。死循环的进程可以上处理机运行（可以是运行态），只不过无法像期待的那样顺利推进。
|
||
|
||
死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。
|
||
|
||
死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题。
|
||
|
||
#### 死锁发生的条件
|
||
|
||
1. 系统资源的竞争。
|
||
2. 进程推进顺序非法。
|
||
|
||
产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生：
|
||
|
||
+ 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
|
||
+ 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
|
||
+ 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己己有的资源保持不放。
|
||
+ 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程己获得的资源同时被下一个进程所请求。
|
||
+ 发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）。
|
||
+ 如果同类资源数大于$1$，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。
|
||
|
||
#### 死锁发生的情况
|
||
|
||
1. 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（$CPU$）的竞争是不会引起死锁的。
|
||
2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程$P1$、$P2$分别申请并占有了资源$R1$、$R2$，之后进程$P1$又紧接着申请资源$R2$，而进程$P2$又申请资源$R1$，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
|
||
3. 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的$P$操作在实现同步的$Р$操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）
|
||
|
||
总之，对不可剥夺资源的不合理分配，可能导致死锁。
|
||
|
||
#### 死锁的处理策略
|
||
|
||
1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
|
||
2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）。
|
||
3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
|
||
|
||
|资源分配策略|各种可能模式|主要优点|主要缺点
|
||
:----:|:----------:|:----------:|:-------:|:-----:|
|
||
死锁预防|保守，宁可资源闲置|一次请求所有资源，资源剥夺，资源按序分配|适用于突发式处理的进程，不必进行剥夺|效率低，进程初始化时间延长；剥夺次数过多；不便灵活申请新资源
|
||
死锁避兔|是“预防”和“检测”的折中（在运行时判断是否可能死锁）|寻找可能的安全允许顺序|不必进行剥夺|必须知道将来的资源需求；进程不能被长时间阻塞
|
||
死锁检测|宽松，只要允许就分配资源|定期检查死锁是否已经发生|不延长进程初始化时间，允许对死锁进行现场处理|通过剥夺解除死锁，造成损失
|
||
|
||
### 预防死锁
|
||
|
||
预防死锁是不允许死锁发生的静态策略。
|
||
|
||
#### 破坏互斥条件
|
||
|
||
如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。
|
||
|
||
比如：$SPOOLing$技术。操作系统可以采用$SPOOLing$技术把独占设备在逻辑上改造成共享设备。比如，用$SPOOLing$技术将打印机改造为共享设备，将多个进程的请求合并为一个输出进程。
|
||
|
||
该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
|
||
|
||
#### 破坏不剥夺条件
|
||
|
||
1. 当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
|
||
2. 当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）。
|
||
|
||
该策略的缺点：
|
||
|
||
1. 实现起来比较复杂。
|
||
2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如$CPU$，而不能用于打印机。
|
||
3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
|
||
4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
|
||
|
||
#### 破坏请求和保持条件
|
||
|
||
可以采用**静态分配方法**，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
|
||
|
||
该策略实现起来简单，但也有明显的缺点：
|
||
|
||
1. 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。
|
||
2. 该策略也有可能导致某些进程饥饿。
|
||
|
||
#### 破坏循环等待条件
|
||
|
||
可采用**顺序资源分配法**。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
|
||
|
||
原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。
|
||
|
||
该策略的缺点：
|
||
|
||
1. 不方便增加新的设备，因为可能需要重新分配所有的编号。
|
||
2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费。
|
||
3. 必须按规定次序申请资源，用户编程麻烦。
|
||
|
||
### 避免死锁
|
||
|
||
预防死锁是不允许死锁发生的动态策略。
|
||
|
||
#### 安全序列与不安全状态
|
||
|
||
+ 所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
|
||
+ 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。
|
||
+ 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）。
|
||
|
||
#### 银行家算法
|
||
|
||
可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。
|
||
|
||
若每一轮检查都从最小编号开始会更快得到安全序列。
|
||
|
||
同时还有一个更快的方法得到安全序列：将剩余资源数与最多还需要对比，满足条件的进程全部加入安全序列（而非一个个），然后把归还的资源相加，进行下一轮的比较。
|
||
|
||
使用代码实现：
|
||
|
||
假设系统中有$n$个进程，$m$种资源。
|
||
|
||
用一个长度为$m$的一维数组 $Available$表示当前系统中还有多少可用资源。`Available[j]=K`表示系统中有$R_j$类资源$K$个。
|
||
|
||
每个进程在运行前先声明对各种资源的最大需求数，则可用一个$n\times m$的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵$Max$，`Max[i,j]=K`表示进程$P_i$最多需要$K$个资源$R_j$。
|
||
|
||
同理，系统可以用一个$n\times m$的分配矩阵$Allocation$表示对所有进程的资源分配情况。`Allocation[i,j]=K`表示进程$P_i$当前已经分片到$R_j$类资源的数目为$K$。
|
||
|
||
$Max-Allocation=Need[i,j]$矩阵，表示各进程最多还需要多少各类资源。
|
||
|
||
某进程$P_i$向系统申请资源，可用一个长度为$m$的一维数组$R_i$表示本次申请的各种资源量。
|
||
|
||
可用银行家算法预判本次分配是否会导致系统进入不安全状态：
|
||
|
||
1. 如果`Ri[j] <= Need[i,j]`（$0\leqslant j\leqslant m$）则转向步骤二，否则因为其需要的资源数已经大于最大值，认为出错。
|
||
2. 如果`Ri[j] <= Available[i]`（$0\leqslant j\leqslant m$），便转向步骤三看，否则表示尚无足够资源，$P_i$必须等待。
|
||
3. 系统试探着把资源分配给进程$P_i$，并修改相应的数据（并非真的分配，修改数值只是为了做预判）。
|
||
+ `Available = Available - Ri;`
|
||
+ `Allocation[i,j] = Allocation[i,j] + Ri[j];`
|
||
+ `Need[i,j] = Need[i,j] - Ri[j];`
|
||
4. 操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配，否则，恢复相应数据，让进程阻塞等待。
|
||
|
||
安全性算法，设置工作向量$Work$，有$m$个元素，表示系统中的剩余可用资源数目。在执行安全性算法开始时，`Work = Available`。
|
||
|
||
1. 初始时安全序列为空。
|
||
2. 从N$eed$矩阵中找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于$Work$向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤四。
|
||
3. 进程$P_i$进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，因此应执行
|
||
`Work = Work + Allocation[i]`，其中`Allocation[i]`表示进程$P_i$代表的在$Allocation$矩阵中对应的行，返回步骤二。
|
||
若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。
|
||
|
||
### 检测解除死锁
|
||
|
||
允许死锁的产生。
|
||
|
||
#### 检测死锁
|
||
|
||
为了能对系统是否已发生了死锁进行检测，必须：
|
||
|
||
1. 某种数据结构来保存资源的请求和分配信息。
|
||
2. 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。
|
||
|
||
检测数据结构就是**资源分配图**：
|
||
|
||
+ 两种结点：
|
||
+ 进程结点（圆圈）：对应一个进程。
|
||
+ 资源结点（方框）：对应一类资源，一类资源可能有多个。
|
||
+ 两种边：
|
||
+ 进程结点→资源结点（请求边）：表示进程想申请几个资源（每条边代表一个）。
|
||
+ 资源节点→进程结点（分配边）：表示已经为进程分配了几个资源（每条边代表一个）。
|
||
|
||
+ 如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。
|
||
+ 如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。
|
||
+ 相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程。
|
||
+ 如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）。
|
||
+ 如果最终不能消除所有边，那么此时就是发生了死锁。
|
||
+ 最终还连着边的那些进程就是处于死锁状态的进程。
|
||
|
||
总结上面的描述，所以检测死锁的算法：在资源分配图中，找出既不阻塞又不是孤点的进程$P_i$（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之称为孤立的结点。进程$P_i$所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。
|
||
|
||
1. 先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞（“不阻塞”即：系统有足够的空闲资源分配给它）的。
|
||
2. 把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来。
|
||
3. 看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。
|
||
4. 最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。
|
||
|
||
死锁定理：根据步骤一中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。若是不能完全简化，则系统死锁。
|
||
|
||
```txt
|
||
----------→ p1 -------
|
||
| ------→ |
|
||
| | ↓
|
||
--------- -------
|
||
| 0 0 0 | r1 | 0 0 | r2
|
||
--------- -------
|
||
↑ | |
|
||
| -------→ |
|
||
----------- p2 ←------
|
||
```
|
||
|
||
首先先看$R1$资源，它有三个箭头是向外的，因此它一共给进程分配了三个资源，此时，$R1$没有空闲的资源剩余。
|
||
|
||
再看$R2$资源，它有一个箭头是向外的，给进程分配了一个资源，此时，$R2$还剩余一个空闲的资源没分配。
|
||
|
||
看完资源，再来看进程，先看进程$P2$，它只申请一个$R1$资源，但此时$R1$资源已经用光了，所以，进程$P2$进入阻塞状态，因此，进程$P2$暂时不能化成孤立的点。
|
||
|
||
再看进程$P1$，它只申请一个$R2$资源，此时，系统还剩余一个$R2$资源没分配，因此，可以满足$P1$的申请。这样，进程$P1$便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于可以把$P1$的所有的边去掉，变成一个孤立的点：
|
||
|
||
```txt
|
||
p1
|
||
|
||
--------- -------
|
||
| 0 0 0 | r1 | 0 0 | r2
|
||
--------- -------
|
||
↑ | |
|
||
| -------→ |
|
||
----------- p2 ←------
|
||
```
|
||
|
||
进程$P1$运行完后，释放其所占有的资源（两个$R1$资源和一个$R2$资源），系统回收这些资源后，空闲的资源便变成两个$R1$资源和一个$R2$资源，由于进程$P2$一直在申请一个$R1$资源，所以此时，系统能满足它的申请。这样，进程$P2$便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于可以把$P2$的所有的边都去掉，化成一个孤立的点：
|
||
|
||
```txt
|
||
p1
|
||
|
||
--------- -------
|
||
| 0 0 0 | r1 | 0 0 | r2
|
||
--------- -------
|
||
|
||
p2
|
||
```
|
||
|
||
由于这个资源分配图可完全简化，因此，不会产生死锁。
|
||
|
||
#### 解除死锁
|
||
|
||
一旦检测出死锁的发生，就应该立即解除死锁。
|
||
|
||
并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。
|
||
|
||
解除死锁的主要方法有：
|
||
|
||
1. 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
|
||
2. 撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
|
||
3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
|
||
|
||
确定挂起或撤销的进程的指标：
|
||
|
||
1. 进程优先级。
|
||
2. 已执行多长时间。
|
||
3. 还要多久能完成。
|
||
4. 进程已经使用了多少资源
|
||
5. 进程是交互式的还是批处理式的。
|