进程与线程

进程概述

是程序的一次执行过程，一个程序可以拥有多个进程。

操作系统会为被创建的进程分配唯一，不重复的PID与UID来区分彼此

• UID即进程所属用户ID

除外，操作系统还要记录分配的资源，运行情况，这些数据储存在PCB即进程控制块中。

• PCB，Process Control Block，是一种数据结构
• 它是进程存在的唯一标识，进程创建与结束对应着PCB的创建与回收

在程序运行之前，OS会在内存开辟对应的PCB，读入程序段，同时也会开辟数据段，包含运行过程中产生的各种数据。

一个进程实体(映像)由PCB、程序段、数据段组成

进程是动态的，而进程实体是静态的

特征

动态性、并发性、独立性、异步性、结构性

进程状态

分为创建态、就绪态、运行态、阻塞态、终止态

当进程申请处理器调度得不到满足时，处于就绪态。

在进程处于运行态时，一旦使用系统调用的方式申请某资源或等待某个事件发生，就进入阻塞态，此时CPU将处理其他进程。

在处于阻塞态时，一旦申请的资源被分配或等待的事情发生，进程将进入就绪态，等待CPU调度。

在处于运行态时，如果分配的时间片到期，或CPU被抢占，进程将进入就绪态

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

多核CPU，同一时刻可以有多个进程处于运行态。

进程控制

实现进程状态转换，而进程控制的实现基于“原语”

原语：一种特殊的程序，包含设备驱动和CPU切换等，其执行具有原子性，运行不能被中断。

• 所以，进程状态的转换是不会被中断的

原子性的实现是通过两个特权指令：关中断与开中断指令实现的。

在这两个指令之间的指令序列将完整的按序执行，不会处理外部中断信号。

进程终止

使用撤销原语终止

1. 从PCB集合找到终止进程PCB
2. 进程正在运行，立即剥夺CPU，CPU分配给其他进程
3. 终止其所有子进程（进程间关系是树形结构）
4. 将该进程拥有的所有资源归还给父进程或操作系统
5. 删除PCB

进程阻塞与唤醒

对应阻塞原语和唤醒原语，通常是成对出现的

进程切换

对应切换原语：

1. 将运行环境信息(进程上下文)存入PCB
2. PCB移入相应队列
3. 选择另一个进程执行，更新其PCB
4. 根据PCB恢复新进程所需运行环境

这将导致两个进程的状态切换！

进程间通信IPC

为了安全，一个进程无法直接访问另一个进程的地址空间。

共享存储方式

取而代之的是，OS允许进程开辟一块共享存储区，供多个进程使用，从而完成数据通信。

• 该共享存储区映射到进程的虚拟地址空间

• 各个进程对共享空间的访问应该是互斥的。

• 操作系统内核提供同步互斥工具(P、V操作)

• 数据的写入读出都是随机访问。

消息传递方式

进程间数据交换使用格式化的信息为单位，通过OS提供的“发/收消息”两个原语实现。

• 将消息封装为消息头和消息体部分。
• 分有直接、间接两种通信方式

直接通信方式将消息直接挂到接收进程的消息队列

间接通信方式将消息发到中间体(信箱)。

管道通信方式

数据是单向流动的，与共享存储方式不同的是：

• 其本质是一个内存缓冲区(特殊的文件)

• 数据遵循先进先出的规则，与循环队列类似

• 数据有序写入读出

• 只能实现半双工通信，若要全双工通信则需要设置两个管道

• 管道写满时，写进程阻塞，待读进程将管道数据取走，可唤醒写进程

• 管道读空时，读进程阻塞，待写进程向管道写入数据，即可唤醒读进程

管道数据一旦被读出，就彻底消失，解决方案：

• 一个管道允许多个写进程，一个读进程
• 允许多个写进程，多个读进程，但OS会让读进程轮流从管道读取数据。

只要管道没空，读进程就可以读

只要管道没满，写进程就可以写

线程概述

基本的CPU执行单元，也是程序执行流的最小单位，是一种轻量级的进程，一个进程可以包含多个线程

• 进程可以并发，线程同样可以，进一步提升系统并发度
• 可以让一个进程内也可以并发执行多个任务
• 进程只作为除CPU之外的系统资源的分配单元

线程实现方式

用户级线程ULT

线程的管理工作通过编程语言提供的线程库完成

• 线程库可以实现线程的创建、销毁、调度等功能
• 不需要CPU切换进程状态
• OS意识不到用户级线程的存在

优点：线程管理的系统开销小，效率高

缺点：当一个用户级线程被阻塞时，整个进程都会被阻塞，并发度不高，多个线程不可在多核CPU上并行运行

内核级线程KLT

线程的管理工作由OS完成

• 线程切换需要OS从用户态切换为内核态
• 当一个线程被阻塞时，别的线程仍可继续执行，并发能力强
• 多线程可以在多核处理级上并行执行
• 一个用户进程会占用多个内核级线程，线程管理成本大，开销大

多线程模型

一对一模型：一个用户级线程映射到一个内核级线程

• 一个线程被阻塞后，别的线程可以继续执行
• 线程管理成本大，开销大

多对一模型：多个用户级线程映射到一个内核级线程

• 线程管理的系统开销小，效率高
• 当一个用户级线程被阻塞时，整个进程都会被阻塞，并发度不高

只有内核级线程才是处理机分配的单位

多对多模型：n个用户级线程映射到m个内核级线程($$n\geq m$$)

• 并发度高
• 由于内核级线程数量比用户及线程少，其系统开销比一对一模型更小

线程的组织与控制

通过线程控制块TCB这个数据结构组织单个线程的所有信息，包含：

• 线程标识符TID

• 程序计数器PC：指出线程目前执行到哪

• 其他寄存器：线程运行的中间结果

• 堆栈指针：保存函数调用信息，局部变量

• 线程运行状态:运行，就绪，阻塞

• 优先级：线程调度、资源分配的参考

其中，PC，寄存器，堆栈指针是线程切换时保存/恢复线程状态的依据

多个线程将组成一个线程表

处理机调度

高级(作业)调度

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

低级调度

又称进程调度/处理机调度，按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

• 最基本的的调度，一般的OS必须配置该调度
• 频率很高，几十毫秒一次

中级调度

又称内存调度

内存不足时，将某些进程的数据调出外存，等待内存空闲或者进程需要运行时再重新调入内存。

• 被调到外存的等待的进程，状态转为挂起态
• 被挂起的进程PCB会被组织成挂起队列

而中级调度就是按照某种策略决定将哪个处于挂起状态的进程重新调入内存。

发生频率比高级调度更高，比低级调度低。

挂起态

挂起态可细分为就绪挂起和阻塞挂起，分别来源于五状态模型的就绪态和阻塞态

形成原因是内存不足时，将处于这两种状态的进程调入外存。

当内存空闲，这两个挂起态将被激活，恢复原来的状态。

• 阻塞挂起等待某种事件发生后也可以进入就绪挂起

• 就绪挂起也可以来源于创建态和运行态。

挂起态与阻塞的区别：挂起态不在内存，阻塞态进程映像还在内存中。

进程调度的…

时机

需要切换的时机：当前运行的进程主动或被动地放弃处理机

不能切换地时机：

1. 处理中断的过程中
2. 进程在操作系统内核程序临界区
3. 原子操作过程。

方式

非剥夺调度方式：又称非抢占方式

• 只允许进程主动放弃处理机，运行过程中有更紧迫的任务到达也不会放弃处理机，直到进程终止或主动要求进入阻塞态
• 早期的批处理系统

剥夺调度方式：又称抢占式

• 进程在处理机执行时，有更紧迫的任务到达，将立即暂停正在执行的进程，处理机分配给更紧迫的进程。
• 可以实现各进程按时间片轮流执行功能。
• 适合于分时操作系统、实时操作系统

切换与过程

狭义的进程调度指的是从就绪队列选择一个要运行的进程

进程切换是指一个进程让出处理机，由另一个进程占用处理及的过程

广义的进程调度包含了选择一个进程和进程切换两个步骤。

过程主要完成了：

1. 对原来运行进程的各种数据的保存
2. 对新的进程各种数据的恢复

进程切换是有代价的，频繁的调度、切换将降低系统效率

调度器与闲逛进程

调度器/调度程序

调度器将决定：

• 让谁运行—-调度算法
• 运行多长时间—-时间片长度

在不支持内核级线程的OS,调度程序的处理对象是进程

在支持内核级线程的OS,调度程序的处理对象是内核线程

闲逛进程IDLE

当没有其他就绪进程时，调度程序将运行闲逛进程

• 优先级最低
• 可以是0地址指令，占一个完整的指令周期
• 能耗低

调度算法的评价指标

周转时间指从作业被提交给系统开始，到作业完成为止的时间间隔，包含：

1. 作业在外存后被队列等待高级调度的时间
2. 进程在就绪队列上等待低级调度的时间
3. 进程在CPU上执行的时间
4. 进程等待I/O操作完成的时间

进程等待时间：进程建立后等待被服务的时间之和，等待I/O完成的期间不进入等待时间

作业等待时间：作业在外存后备队列等待时间+建立进程后的等待时间。

响应时间：用户提交请求到首次产生响应所用的时间

批处理适用调度算法

先来先服务FCFS

根据到达的先后顺序调度。

周转时间=完成时间-到达时间

带权周转时间=周转时间/运行时间

等待时间=周转时间-运行时间

• 对长作业有利，对短作业不利(其带权周转时间很大)

• 不会导致饥饿

短作业优先SJF

每次调度时，选择当前已到达且运行时间最短的作业/进程

• SJF是非抢占式的算法
• 当所有进程都几乎同时到达时，SJF调度算法的平均等待时间、平均周转时间最少。
• 对短作业有利，长作业不利
• 有可能饥饿

最短剩余时间优先算法SRTN

基于SJF改进，又称抢占式的SJF算法

每当有进程加入就绪队列改变时就需要调度，新进程剩余时间比当前运行的进程剩余时间更短，则新进程抢占处理机，当前运行进程回到就绪队列，当一个进程完成时也需要调度。

高响应比优先HRRN

每次调度时计算各个作业的响应比，选择响应比最高的进行服务。 $$ 响应比 = \frac{等待时间+要求服务时间}{要求服务时间} $$

• 非抢占式算法，当进程完成或废弃再执行调度

• 综合了FCFS和SJF的优点

• 不会饥饿

上述三种算法适用于早期的批处理系统，交互性极其糟糕

交互式适用调度算法

时间片轮转调度算法RR

按到达就绪队列的顺序，轮流让各进程执行一个时间片，到期后：

• 若未完成，强制剥夺处理机

• 若完成，主动放弃处理机，执行调度

• 若就绪队列为空，继续执行当前进程

特性：

• 抢占式算法
• 被剥夺的进程将进入就绪队列队尾
• 适用于分时操作系统
• 系统开销大，不区分任务紧急程度
• 不会饥饿，适用于分时系统

注：

时间片的大小不能太大，当设置一个较大时间片，将退化为FCFS算法

而太小的时间片将导致频繁调度，系统开销增大。

优先级调度算法

根据优先级排列进程进行调度

• 非抢占式型，在进程主动放弃处理机时进行调度。

• 抢占式型，在进程主动放弃处理机时以及就绪队列发生改变时调度。

优先级分静态和动态两种。

• 系统进程高于用户进程
• 前台进程高于后台进程
• 更偏好于I/O繁忙型进程，非CPU繁忙型进程（计算型进程）

该算法有可能导致饥饿，适用于实时系统

多级反馈队列调度算法

对其他调度算法的折中平衡

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

新进程进入一级队列，若分配时间片用完且进程未结束，进入下一级队列**，按FCFS原则排队等待被分配时间片**，若进程已经在最下级队列，则重新放回最下级队列队尾。

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

• 若进程运行时，有更高级进程到达队列，则剥夺处理机，被剥夺的进程重新放回原队列队尾。

这是一个抢占式算法，有可能导致饥饿

多级队列调度算法

队列之间可以采用固定优先级或时间片划分调度。

各队列可采用不同的调度策略。

进程同步

并发必然导致进程异步，进程运行的先后顺序不可知，而进程同步就是用来解决这个问题。

临界资源与临界区

临界资源是一次仅允许一个进程使用的共享资源。

• 它是由各进程采取互斥的方式，实现共享的资源

临界区是每个进程用于访问临界资源的代码片

• 只要运行在临界区的线程还没有离开，其他所有进入此临界区的线程都会被挂起而进入等待状态

在临界区之上有段代码叫进入区：设置正在访问临界资源的标志，防止其他进程同时进入临界区。

在临界区之下有段代码叫退出区：负责解除正在访问临界资源的标志

进入区和退出区负责实现互斥

进程互斥

当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能访问该临界资源。

遵循以下原则：

1. 空闲让进
2. 忙则等待
3. 有限等待，对请求访问的进程，保证不会饥饿
4. 让权等待，进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥软件实现

单标志法

两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，每个进程进入临界区的权限只能被另一个进程赋予。

然而，当一个进程允许进入临界区，而一直不访问临界区时，该算法违背了空闲让进原则。

双标志先检查法

设置一个布尔型数组，元素用于标识各进程想进入临界区的意愿

1. 先检查其他进程是否想进入临界区
2. 没有进程想进入临界区，将自己的意愿修改为true，进入临界区。
3. 使用完临界区，将自己的意愿改为false，退出

仍然会出现多个进程同时访问临界区的问题（在修改自己的意愿前，进程被切换到另一个）

违反忙则等待原则。

双标志后检查法

与先检查法类似，不同点在于后检查法先修改自己的意愿为true，再检查是否有其他进程想要使用。

解决了忙则等待问题，但仍违背了空闲让进以及有限等待原则，会出现饥饿现象。

Peterson算法

结合单、双标志法，设置布尔型数组表示各进程使用的意愿，维护一个turn变量用于表示优先交给哪个进程使用。

进入区:

1. 主动争取，表示自己想要使用
2. 主动谦让，将使用权让给对方
3. 检查对方是否想要使用且在最后是不是自己表示的谦让

然而未遵循让权等待的原则，会出现“忙等”

进程互斥硬件实现

开/关中断

利用“开/关中断指令”实现，即进程的执行将是原子化的，不会出现两个进程同时进入临界区的问题。

然而，不适用于多处理机以及仅适用于操作系统内核进程，不适用于用户进程

• 因为开/关中断指令只能运行在内核态

TS指令

全称TestAndSet或TestAndSetLock指令，或TSL指令

执行的过程不允许被中断，使用布尔型共享变量lock来表示当前临界区是否被加锁

该指令在执行时，不管临界区之前是否被上锁，都会加锁(lock=true)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

bool lock = false; //若刚开始为false，直接访问，为true，while循环继续。

bool TestAndSet(bool* lock){
	bool old;
    old = *lock;
    *lock = true; //直接加锁
    return old;
}
while(TestAndSet(&lock));
//临界区代码段
lock = false; //解锁，允许其他进程进入。
//剩余区代码段

• 相比软件实现，TSL指令将上锁和检查用硬件方式变为原子操作。

• 适用于多处理机环境

• 不满足“让权等待”

Swap指令

又称Exchange指令，即XCHG指令。

硬件实现，原子操作。

1
2
3
4
5
6
7
8

bool old = true; //若为true说明有其他进程上锁临界区
bool lock = true;
while(old == true){
    Swap(&lock,&old);
}
//临界区代码段
lock = false; //解锁，允许其他进程进入。
//剩余区代码段

• 先将上锁标记lock设为true，最后检查old。

• 若old为false说明没有其他进程对临界区上锁，准入临界区。

• 不满足让权等待，暂时无法进入临界区的进程会占用CPU循环执行Swap指令，导致“忙等”

互斥锁

通常使用硬件机制实现，会出现忙等待，需要连续循环忙等的互斥锁，称为自旋锁，

如TSL指令、swap指令、单标志法。

• 等待期间不用切换进程上下文，多处理器系统中，若上锁时间段，则等待代价很低。
• 常用于多处理器系统，一个核忙等，其它核照常工作并快速释放临界区
• 不太适用于单处理机，忙等过程不可能解锁。

信号量机制

用于表示系统中某种资源的数量，用户进程可以通过一对原语wait(s)和signal(s)，对信号量进行操作，实现进程互斥与同步

• 这对原语又称P、V操作。
• 该机制解决了先前算法所不能实现的让权等待问题

整型信号量

用整数型变量作为信号量，在PV操作内部维护该变量，

在PV操作内部，检查资源数以及上锁/解锁是原子化的，不会被中断，避免了多进程同时进入临界区的问题。

• 会出现忙等，不满足“让权等待”

记录型信号量

使用记录型数据结构表示的信号量

1
2
3
4

typedef struct{
	int value;			//剩余资源数	
    struct process* L    //等待队列 
}semaphore；

P操作：先将资源数-1，若此时资源数<0，则使用block原语让进程从运行态进入阻塞态，挂载到等待队列

V操作：将资源数+1，若此时资源数仍<=0，则说明有其他进程在等待使用，使用wakeup原语唤醒阻塞态进程使其进入就绪态，开始分配资源。

• 不会出现忙等

实现进程互斥

1. 分析并发进程的关键活动，划定临界区

2. 设置互斥信号量mutex，初值为1

3. 进入区P操作—申请资源

4. 退出区V操作—资源释放

注：不同的临界资源要设置不同的互斥信号量，对每一个mutex做一遍PV操作，PV操作必须成对出现

实现进程同步

1. 分析需要实现同步的地方
2. 设置同步信号量S，初值为0
3. 对相对顺序滞后的代码执行前，使用P操作，由于初值为0，P操作-1资源数，此时代码进入阻塞态
4. 对相对顺序靠前的代码执行后，使用V操作，资源数+1，此时发现资源数<=0，则唤醒被阻塞的代码
5. 这样一来，代码将顺序执行。

实现前驱关系

1. 每一对前驱关系各设置一个同步信号量。

2. 按实现进程同步的方式，安排PV操作

解决互斥同步问题

生产者消费者问题

生产者和消费者共享一片缓冲区，

• 缓冲区没满，生产者将产品放入缓存区，否则等待
• 缓冲区非空，消费者才能取出产品，否则等待
• 缓冲区是临界资源，各进程必须互斥地访问

实现互斥是在同一进程进行一对PV操作

实现两进程同步是在其中一个进程执行P，另一个进程执行V

实现互斥的P操作必须在实现同步的P操作之后，否则两个互斥的进程有可能都被阻塞，出现死锁。

V操作不会导致进程阻塞，可以交换顺序。

多生产者-多消费者问题

多生产者与消费者共享大小为1，初值为0的缓冲区，生产者与消费者生产/消费的产品不同。

• 分析同步问题时，不能从单个进程行为的角度分析，从事件角度分析，要当成是两个事件的前后关系

注意：生产-消费者问题中若缓冲区大小大于1，则必须考虑多进程同时进入缓存区可能存在的数据覆盖问题，即必须对缓冲区设置互斥信号量mutex。

吸烟者问题

一个供应者与n个吸烟者，一根烟由n种材料组成，每个吸烟者拥有一个独属的材料，吸烟者轮流抽烟。

• 供应者持续提供n-1个不重复的材料，这对应着一个大小为1，初值为0的缓冲区
  • 将提供的多个材料认成一个组合，有多个不同的组合可能被提供。
• 某吸烟者发现提供的材料与自己的可以卷一根烟抽，给一个信号给供应者
• 供应者按序发送对应吸烟者需要的材料。

读者-写者问题

读者、写者进程并发运行，共享一个文件

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

互斥关系：写-写进程，写-读进程

设置针对文件本体的互斥信号量rw，整型信号量count记录当前有几个读进程访问文件，针对count的互斥信号量mutex

在写进程对rw进行PV操作

由第一个读文件的进程负责对文件的加锁，之后count++

读完文件，count–，由最后一个读进程负责读完解锁

对mutex的PV操作将保证各个读进程对count的访问是互斥的

核心在于对计数器count的应用，其记录正在访问文件的读进程数，可以用count的值判断当前进程是否是第一个/最后一个进程，从而进行不同的操作。

当count的赋值不能保证原子性时，应使用互斥信号量

哲学家进餐问题

每个进程都需要同时持有两个临界资源才能开始进餐，问题的核心点在于如何避免资源分配不当导致的死锁现象。

由于哲学家们坐在圆桌上，构成一个环，故可以设置一个针对筷子的互斥信号量数组

哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5.

防止死锁发生：

1. 只允许最多四个哲学家同时进餐，保证至少有一个哲学家可以拿到左右两只筷子

2. 或者要求奇数号哲学家先拿左再拿右，偶数号哲学家先拿右再拿左。

3. 或者保证每个哲学家拿筷子(无论哪根)都是互斥的，需要额外设置一个mutex，初值为1，互斥地取筷子

• 这样一来，只有第一个去取筷子的人才有可能获得两支筷子，开始进餐，后续的进程将在P(mutex)处或者拿左/右筷子处被阻塞

管程

信号量机制编写程序困难，易出错，而管程机制让程序员写程序时不需要关注复杂的PV操作，它是一种高级同步机制

管程是一种特殊的软件模块，包含：

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

管程的基本特征：

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

请将“过程”自动替换为“函数”

注：

• 管程有很多入口函数，但一次只开放一个，只能让一个进程或线程进入，该互斥特性由编译器负责实现

• 在管程可设置条件变量和等待/唤醒操作解决同步问题

死锁

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都被阻塞，都无法向前推进的现象，发生死锁的进程一定处于阻塞态

饥饿：可能只有一个进程发生饥饿，既可能是阻塞态(长期得不到I/O)，也可能是就绪态(长期上不了处理机)

死循环：进程可以是运行态，但无法按预期向前推进，属于被管理者的问题，而死锁和饥饿属于管理者(操作系统)的问题

产生的必要条件

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

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

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

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

发生死锁时一定有循环等待，但发生循环等待时未必死锁。

但系统中同类资源都只有1个时，循环等待是死锁的充分必要条件

总之，对不可剥夺资源的不合理分配，可能导致死锁。

预防死锁

核心在于破坏四个必要条件其中之一。

破坏互斥

将必须互斥使用的资源改造成允许共享使用的资源，比如SPOOLing技术

然而很多时候无法这么做

破坏不剥夺条件

1. 某进程请求新的资源得不到满足时，主动释放自己持有的所有资源，不管其使用完毕与否
2. 由操作系统协助，将想要的资源强行剥夺，比如剥夺调度方式

缺点：

• 实现复杂

• 释放已获得得资源可能造成前一阶段工作的失效，一般只适用于易保存和易恢复得资源，如CPU

• 反复地申请释放资源将增加系统开销，降低系统吞吐量

• 第一条将有可能重复发生放弃申请资源导致进程饥饿

破坏请求和保持条件

使用静态分配法：在进程运行之前，将他所需的资源全部申请完，有一个未满足，则不运行。

• 有些资源可能只需要使用很短的时间，将导致资源利用率极低，可能会导致其他进程饥饿

破坏循环等待条件

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

• 规避了资源环路，整个资源的申请将是线性的

• 进程实际使用的资源的顺序可能和编号递增顺序不一致，导致资源的浪费

• 编程难度提高

• 不方便增设新的设备，可能需要重新分配所有编号

避免死锁–银行家算法

安全序列：如果系统按这种序列分配资源，则每个进程都能顺利完成，只要能找出一个安全序列，系统就是安全状态，这个序列不唯一，一定不发生死锁

不安全状态：分配资源后，系统找不到任何一个安全序列，如果有进程提前归还资源，则系统有可能重新回到安全状态，有可能发生死锁

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

安全性算法：

1. 将资源总数-初始分配数，得到剩余可用资源
2. 维护一张表，包含进程最大需求，已分配，最多还需要的资源数
3. 逐个比对最多还需要项与剩余可用资源的大小，若小于：
   • 说明该进程一定可以顺利执行，结束即可归还资源
   • 将剩余可用资源+该进程已分配的资源，更新剩余可用资源的值
   • 将该进程添加到安全序列
4. 继续从头到尾比对

银行家算法数据结构：

• 假设系统中有n个进程，m种资源，则可用一个n*m的矩阵表示所有进程对各种资源的最大需求矩阵Max，Max[i,j] = K表示进程Pi最多需要K个资源Rj，

• 同样存在一个n*m的分配矩阵Allocation表示资源的分配情况

• Max-Allocation=Need矩阵，表示各进程最多还需要多少各类资源

• 需要维护一个长度为m的一维数组Available表示本次申请的各种资源量

如果：

• Request_i[j]<=Need[i,j]，则继续，否则认为出错
• 如果Request_i[j]<=Available[j]，则继续，否则表示无足够剩余资源，Pi阻塞
• 系统假分配资源(仅作预判使用)给Pi，并修改相应数值
• 更新Available，Allocation，Need矩阵
• 操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，正式分配，否则恢复相应数据，进程阻塞

银行家算法计算的是某一个进程对资源的需求问题

安全性算法是计算所有的进程在各自的银行家算法执行下是否处于安全状态

死锁检测与解除

检测算法：

1. 在资源分配图中，找出既不阻塞又不是孤点的进程Pi，消去其所有请求边与分配边，使之成为孤立的节点
2. 进程Pi所释放的资源，可以唤醒某些因等待这些资源被阻塞的进程，原来的阻塞进程可以顺利执行，同样可以消去边。
3. 若最后图中所有边被消去，则没有死锁

解除死锁：

1. 资源剥夺：挂起某些死锁进程，抢占其资源，分配给其他死锁进程，
   • 同时应防止被挂起的进程长时间得不到资源而饥饿
2. 撤销进程法：强制撤销部分、或全部进程，并剥夺这些进程的资源
   • 付出的代价可能会很大，某些快要完成的进程将重新开始
3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的状态，需要OS记录进程的历史信息设置还原点