进程管理

进程 & 线程

进程：操作系统进行资源分配和调度的基本单位_{每个进程都有自己独立的地址空间、代码、数据和系统资源}

线程：进程中的一个执行单元，一个进程可以包含多个线程_{有的进程要同时做很多事，传统进程只是串行执行，因此引入线程增加并发度；线程共享资源和地址}

进程

进程组成

进程由进程控制块 PCB、程序段、数据段组成

• 进程控制块 PCB：包含操作系统在管理进程时所需的所有信息_{进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息}，操作系统通过进程控制块来实现各种操作

  信息	含义
  进程描述信息	· 进程标识符：唯一标识进程 · 用户标识符：确保进程的权限和访问控制
  进程控制和管理信息	· 进程当前状态：描述进程状态，作为处理机调度一句 · 进程优先级：描述进程抢占处理机的优先级
  资源分配清单	说明有关内存地址和虚拟地址状况，所打开文件列表和 IO 设备信息
  处理机相关信息	也被称为 CPU 的上下文，即 CPU 中各寄存器的值 当进程被切换，CPU 状态保存于 PCB，以便重启时能断点重新执行

• 程序段：被进程调度到 CPU 执行的代码

• 数据段：程序使用和生成的数据

一个系统中有很多 PCB，应使用合适方式将其组织——按照进程状态将 PCB 分为多个队列，操作系统持有指向各个队列的指针

PCB 的索引是根据进程状态不同建立索引表，操作系统持有索引表的指针

进程状态

进程状态	含义
运行态	进程在处理机运行
就绪态	进程获得除 CPU 所有资源，一旦获得 CPU 即可运行多个就绪态进程会排成队列
阻塞态等待态	进程等待资源或某事件而暂停运行
创建态	进程正在被创建
终止态	进程消失

状态切换	含义
创建态 $\rightarrow$ 就绪态	进程正在被创建
就绪态 $\rightarrow$ 运行态	获得 CPU 资源后进程转化
运行态 $\rightarrow$ 就绪态	进程 CPU 时间片用完或更高优先级进程就绪
运行态 $\rightarrow$ 阻塞态	进程请求某资源或某事件，进程以系统调用请求操作系统内核服务
阻塞态 $\rightarrow$ 就绪态	进程等待的资源或事件到来
运行态 $\rightarrow$ 终止态	进程消失

原语

原语即对进程进行管理的措施，其具有原子性，不可中断不可分割

原语	操作
进程创建	1、为新进程分配唯一进程标识号；申请空白 PCB 2、分配所需资源从操作系统或父进程中获得 3、初始化 PCB，填写控制和管理进程信息 4、进程转入就绪态并插入就绪队列 父进程 & 子进程：进程可以创建进程，子进程可以继承父进程资源
进程终止	1、根据终止进程标识符，检索该进程 PCB，从中读取进程状态 2、若该进程有子孙进程，终止子孙进程 3、若该进程处于运行状态，终止执行 4、归还该进程所拥有全部资源 5、将该 PCB 从所在队列删除
进程阻塞和唤醒	1、在等待队列中找到对应进程 PCB 2、若该进程为运行态，则转为阻塞态，停止运行 3、将该 PCB 插入就绪队列，等待调度程序调度

进程通信

在多任务操作系统中，每个进程都有独立的内存空间。为了安全，进程之前不能直接访问对方内存，因此不能直接共享数据，而需要通过一定通信操作

进程通信	含义	图示
共享存储	通信的进程可以直接访问共享空间，对该空间进行读写实现进程之间信息交换 需要同步互斥工具
消息传递	使用操作系统提供的消息传递原语实现
管道通信	“管道 pipe”即用于连接读写的共享文件，即从内存中开辟大小固定的缓冲区 管道某一时间段只能单向传输，因此双向通信需要设置两个管道 各进程互斥访问管道，数据以字符流形式写入管道

线程

线程实现

线程实现方法	含义	图示
用户级线程 UTL	由应用程序通过线程库实现，所有线程管理工作均应用程序负责操作系统内核意识不到线程的存在 线程切换在用户态即可完成
内核级线程 KTL	由操作系统内核完成 线程切换必须在核心态下才能完成
两者组合多线程模型	将 $n$ 个用户及线程映射到 $m$ 个内核级线程（$n\ge m$） 操作系统只看得见内核级线程，只有内核级线程才是处理机分配单位

多线程模型：

多线程模型	含义	优点	缺点	图示
多对一模型	多个用户及线程映射到一个内核级线程 每个用户进程只对应一个内核级线程	用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高	当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高 多个线程不可在多核处理机上并行运行
一对一模型	一个用户及线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。	当一个线程被阻塞后，别的线程还可以继续执行，并发能力强 多线程可在多核处理机上并行执行。	一个用户进程会占用多个内核级线程,线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大
多对多模型	$n$ 用户级线程映射到 $m$ 内核级线程	克服多对一模型并发度不高的缺点 克服一对一模型开销太大模型

线程的组织与控制

线程控制块 TCB：记录控制和管理线程的信息_{通常包含线程标识符、一组寄存器、线程运行状态、优先级、存储区、堆栈指针}

线程创建：用户程序启动时，通常仅有初始化线程正在执行，其用于创建新线程；创建新线程要利用一个线程创建函数并提供 TCB 参数，函数执行完毕会返回线程标识符

线程终止：线程终止后不利己释放资源，只有进程中其他线程执行分离函数，资源才被释放

CPU 调度

[toc]

Q：你根据什么方法排列任务重要性的

A：根据一定规则

调度：根据一定规则分配 CPU

调度层次：作业从提交到完成，往往经历以下三级调度

调度层次	做法	位置	频率	对进程影响
高级调度 （作业调度）	因为内存有限，无法将全部作业放入内存 从后备队列中选择作业调入内存，并为其创建进程	外存 $\rightarrow$ 内存 面向作业	最低	无 $\rightarrow$ 创建态 $\rightarrow$ 就绪态
中级调度 （内存调度）	引入虚拟存储后，可将暂时不能运行的进程放至外存等待，可以提高利用率 从挂起队列选择合适进程数据调回内存	外存 $\rightarrow$ 内存 面向进程	中	挂起态 $\rightarrow$ 就绪态
低级调度 （进程调度）	从就绪队列选择进程分配处理机	内存 $\rightarrow$ CPU	最高	就绪态 $\rightarrow$ 运行态

挂起和阻塞都暂时不能获得 CPU；但挂起进程映像调到外存，阻塞进程还在内存

调度的实现

调度程序（调度器）：用于调度和分配 CPU 组件

• 排队器：将系统所有就绪态进程排成队列
• 分派器：将进程从就绪队列取出，将 CPU 分配给新进程
• 上下文切换器：在切换 CPU 时，会发生两对上下文切换操作
  1. 将当前进程上下文保存到 PCB，再装入分派程序上下文以便运行
  2. 移出分派程序上下文，将新选进程 CPU 现场信息装入相应寄存器

调度的时机：请求调度之后，会运行调度程序调度新的就绪进程，最后进行进程切换

• 当前运行进程主动放弃处理机
  • 进程正常终止
  • 运行过程发生异常终止
  • 进程主动请求阻塞_{如等待 IO}
• 当前运行进程被动放弃处理机
  • 分配给 CPU 时间片用完
  • 更紧急事需要处理
  • 有更高优先级进程进入就绪队列
• 有时候不能进行程序调度
  • 处理中断过程中，中断处理过程复杂，很难中断处理中进程切换
  • 进程在操作系统内核程序临界区中
  • 在原语操作过程中

调度方式：当优先权更高进程进入就绪队列时如何分配 CPU

• 非抢占方式：只允许进程主动放弃处理机_{实现简单但无法处理紧急任务}
• 抢占方式：暂停执行当前进程，将处理机分配给更重要的进程

调度评价指标

调度评价指标	含义
CPU 利用率	响应应该尽可能保持 CPU 别休息： $CPU 利用率 = \dfrac{CPU 有效工作时间}{CPU 有效工作时间 + CPU空闲等待时间}$
系统吞吐量	单位时间内 CPU 完成作业数量
周转时间	作业提交到作业完成经历的时间
等待时间	进程处于等待 CPU 时间之和
响应时间	用户提交请求到系统首次响应时间

典型调度算法

调度算法	规则	可抢占	优点	缺点	导致饥饿
先来先服务 FCFS	按照作业到达先后顺序进行服务	非抢占	公平，实现简单	排在长作业后的短作业需要等待很长时间	×
短作业优先 SJF	追求最少平均等待时间 最短作业优先服务	非抢占	平均等待时间和平均周转时间最短	不公平，对长作业不利	√
高响应比优先 HRRN	响应比最高的优先服务 $响应比=\dfrac{t_{等待}+t_{要求服务}}{t_{要求服务}}$	非抢占	综合考虑作业等待时间和要求服务时间		×
时间片轮转	轮流为各个进程服务 按照就绪队列顺序，轮流让各个进程执行一个时间片，到时间就重新排队	抢占，由时钟中断通知时间	公平，响应快，适合分时操作系统	高频率进程切换有开销 不区分任务紧急程度	×
优先级调度算法	选择优先级最高的作业	均可	用优先级区分重要程度，适合实时操作系统	若高优先级源源不断，可能饥饿	√
多级反馈队列调度算法	我全都要 1、设置多级就绪队列，各级队列优先级从高到低，时间片从小到大 2、新进程到达时，进入第 1 级队列，按 FCFS 原则排队等待时间片 3、若用完时间片还没结束，则进程进入下一级队列队尾 4、只有第 k 级队列为空时，才会为 k+1 级队头进程分配时间片	抢占式	相对公平 每个新到达进程都可以很快响应 短进程只用较少时间即可完成 不必实现估计进程运行时间		√

一般来说，进程优先级可以参考以下原则

• 系统进程 $>$ 用户进程
• 交互型进程 $>$ 非交互型进程_{前台交互需要更快速响应}
• IO 进程 $>$ 计算进程_{IO 设备处理速度比 CPU 慢得多}

同步 & 互斥

同步：有的进程需要相互配合完成工作，需要遵循一定先后顺序

互斥：对临界资源访问需要互斥，即同一时间段只允许一个进程访问

临界区

临界区：访问临界资源的代码_{空闲让进，忙则等待，有限等待，让权等待}

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

• 进入区：检查是否可以进入临界区，若可进入，则应设置正在访问临界区标志
• 临界区：访问临界资源代码
• 退出区：将正在访问临界区的标志清除，和进入区共同实现互斥
• 剩余区：代码剩余部分

实现临界区软件方法

在进入区设置并检查标志，标明是否进程在临界区中；若已有进程在临界区，则在进入区循环检测并等待

单标志法

两个进程访问临界区后会把权限转给另一个进程

每个进程进入临界区权限只能另一个进程赋予

int turn = 0; // turn 表示当前允许进入临界区的进程号

/* P0 进程 */
while (turn != 0);  // 进入区
critical section;   // 临界区
turn = 1;           // 退出区
remainder section;  // 剩余区

/* P1 进程 */
while (turn != 1);  // 进入区
critical section;   // 临界区
turn = 0;           // 退出区
remainder section;  // 剩余区

对于临界区的访问，只能按 $P_0\rightarrow P_1\rightarrow P_0\rightarrow P_1\cdots$ 轮流访问。因此，违背空闲让进原则

双标志先检查

设置布尔型数组，标记进程 $i$ 是否想进入临界区

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$ 进入临界区但还没更改标志，则有可能造成多个进程同时访问临界区，即检查和上锁并非一气呵成，检查后上锁前可能发生进程切换

双标志后检查

和双标志先检查相反，先检查后上锁

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; // 剩余区

同样不是同时完成检查和上锁，所以有可能导致两个进程都进不去临界区

Peterson 算法

孔融：只有“让”，才能吃到梨

所以如果想着进入临界区，不如试试让对方先进临界区

bool flag[2];   // 表示进入临界区意愿数组
flag[0] = false;
flag[1] = false;
int turn = 0;  // turn 表示优先让哪个进程进入临界区

/* 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; // 剩余区

实现临界区硬件方法

计算机提供特殊硬件指令，允许对一个字检测或修正，或对两个字内容进行交换

中断屏蔽方法

使用“开/关中断”指令实现，即某进程开始访问临界区到结束访问不允许被中断

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

优点：简单高效
缺点：只适用单处理机和操作系统内核进程

TS 指令

借助 TestAndSet 指令实现互斥，该指令是原子操作，读出指定标志后将标志设置为真

• 若 lock 为 false，代表临界资源空闲，即可访问同时 lock=true
• 若 lock 为 true，代表资源正被使用，所以必须等待同时 lock=true

// 参数: 布尔型共享变量 lock, 表示当前临界区是否被枷锁
// 返回值: true 表示已加锁; false 表示未加锁
bool TestAndSet (bool *lock) {
    bool old;
    old = *lock;  // old 存储 lock 原本的值
    *lock = true; // 无论是否上锁，将 lock 设置 true
    return old;   // 返回 lock 原本的值
}

/* 使用 TSL 指令实现互斥算法逻辑 */
while (TestAndSet (&lock));  // 上锁并检查
critical section;            // 临界区代码
lock = false;                // 解锁
remainder section;           // 剩余区

当 $N$ 个进程访问同一个临界资源，执行 TSL 指令判断进程占用；若占用则等待，若空闲则进入临界区执行代码，最后开锁

Swap 指令

交换两个字节的内容

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

/* 使用 Swap 指令实现互斥 */
bool old = true;
while (old == true)
    Swap (&lock, &old);
critical section;            // 临界区代码
lock = false;
remainder section;           // 剩余区

信号量

之前进程互斥解决方案都无法一口气检查上锁，因而导致两个进程可能同时进入临界区的问题，因此考虑通过使用操作系统一对原语进行操作

信号量：用于进程或线程同步的计数器机制，判断资源还有无剩余

整型信号量：用整数型变量作为信号量，用以表示系统中某资源数量_{仅有三种操作：初始化、P操作、V操作}

int S = 1;  // 初始化信号量，表示当前系统中资源数

void P (int S) {      // P 原语，相当于“进入区”
    while (S <= 0);   // 若资源不够，循环等待
    s--;              // 资源数够，就占用一个资源
}

void V (int S) {     // V 原语，相当于“退出区”
    S++;             // 释放资源
}

/* 进程 P_i */
... 
P(S);                // 进入区，申请资源
critical section;    // 临界区代码
V(S);                // 退出区，释放资源
...

但 while 循环时，CPU 一直运行没干正事，会“忙等”

记录型信号量：为解决“忙等”问题，以记录型数据结构表示的信号量

/* 记录型信号量定义 */
typedef struct {
    int value;          // 剩余资源数
    struct process *L;  // 等待队列，用于链接所有等待资源的议程
} semaphore;

/* 进程需要资源，通过 P 原语申请 */
void P (semphore S) {
    S.value--;
    if (S.value < 0) {  // 若资源不够，使用 block 原语使进程进入阻塞态，并挂到阻塞队列
        block (S.L);
    }
}

/* 进程用完资源，通过 V 原语申请 */
void V (semaphore S) {
    s.value++;
    if (S.value <= 0) {  // 释放资源后，若还有别的进程等待该资源，使用 wakeup 原语唤醒阻塞队列一个进程
        wakeup(S.L);
    }
}

信号量实现互斥 & 同步

利用信号量实现互斥：其实就是设置资源为 1

semphore mutex = 1;  // 初始化信号量

/* 进程 1 */
P1 () {
    P(mutex);            // 使用临界资源前加锁
    critical section;    // 临界区代码
    V(mutex);            // 使用临界资源后解锁
}

/* 进程 2 */
P2 () {
    P(mutex);            
    critical section;    
    V(mutex);            
}

利用信号量实现同步：可以理解为进程 2 是消费者，必须消费进程 1 生产出来的资源

semaphore S = 0;  //初始化信号量

/* 进程 1，生产资源 */
P1 () {
    critical section;    
    V(mutex);           
}

/* 进程 2，消费资源 */
P2 () {
    P(mutex);            
    critical section;   
}

互斥同步经典问题

生产者-消费者问题

系统中有一个生产者进程和一个消费者进程，生产者每次生产一个产品放入缓冲区，消费者每次从缓冲区取出一个产品

缓冲区满时，生产者必须等待；缓冲区空时，消费者必须等待

semaphore mutex = 1;      // 互斥信号量，实现对缓冲区互斥访问
semaphore empty = n;      // 同步信号量，表示空闲缓冲区数量
semaphore full = 0;           // 同步信号量，表示产品数量，即非空缓冲区数量

/* 生产者进程 */
producer () {
    while (1) {
        ...        // 生产一个产品
        P(mutex);  // 消费一个缓冲区空间
        P(empty);  // 实现互斥锁
        ...        // 把产品放入缓冲区
        V(mutex);  // 解开互斥锁
        V(full);   // 产品量 + 1，实现同步
    }
}

/* 消费者进程 */
cosumer () {
    while (1) {
        P(full);   // 消耗一个产品，实现同步
        P(mutex);  // 实现互斥锁 
        ...        // 从缓冲区取出一个产品
        V(mutex);  // 解开互斥锁
        V(empty);  // 增加一个空闲缓冲区
        ...        // 使用产品
    }
}

多生产者-多消费者问题

生产者 producer1 生产产品 a，生产者 producer2 生产产品 b

消费者 cosumer1 消费产品 a，消费者 cosumer2 消费产品 b

semaphore a = 0;  // 缓冲区有几个产品 a
semaphore b = 0;  // 缓冲区有几个产品 b
semaphore mutex = 2;  // 缓冲区还可以放多少产品

producer1 () {
    while (1) {
        ...  // 准备产品 a
        P(mutex);
        ...  // 产品 a 放入缓冲区
        V(a);
    }
}

producer2 () {
    while (1) {
        ...  // 准备产品 b
        P(mutex);
        ...  // 产品 b 放入缓冲区
        V(b);
    }
}

cosumer1 () {
    while (1) {
        P(a);
        ...  // 从缓冲区取出 a
        V(mutex);  
        ...  // 消费 a
    }
}

cosumer2 () {
    while (1) {
        P(b);
        ...  // 从缓冲区取出 b
        V(mutex);  
        ...  // 消费 b
    }
}

读者-写者问题

有两组读者写者并发进程共享一个文件，允许多个读者同时读文件，但只允许一个写者写信息，任一写者完成操作前不允许其他读写者工作且写者操作前应让已有读写者全部退出

semaphore rw = 1;     // 实现对文件互斥访问
int count = 0;        // 记录当前几个读者在读文件
semaphore mutex = 1;  // 对 count 变量互斥访问
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);
        V(w);
        ...             // 读文件
        P(mutex);       //读进程互斥访问 count
        count--;        // 访问文件读进程数 - 1
        if(count == 0)  // 最后一个读进程解锁
            V(rw);
        V(mutex);
    }
}

吸烟者问题

三个吸烟者进程分别需要烟草、纸、胶水，一个供应者进程需要提供三种材料才能使其抽烟

semaphore offer1 = 0;  // 桌上组合一数量
semaphore offer2 = 0;  // 桌上组合二数量
semaphore offer3 = 0;  // 桌上组合三数量
semaphore finish = 0;  // 抽烟是否完成
int i = 0;             // 用于实现三者轮流抽烟

provider () {
    while (1) {
        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);
    }
}

哲学家进餐问题

$n$ 个哲学家，每个哲学家之前摆放一个筷子，只有同时拿到左右筷子才能进餐

semaphore chopstick[5] = {1, 1, 1, 1, 1};  // 初始化信号量
semaphore mutex = 1;                       // 设置筷子信号量

P_i ()                                     // 哲学家 i 的进程
    while (1) {
        P(mutex);                          // 获取筷子前获得互斥量
        P(chopstick[i]);                   // 取左边筷子
        P(chopstick[(i + 1) % 5]);         // 取右边筷子
        V(mutex);                          // 释放筷子信号量
        ...                                // 进餐
        V(chopstick[i]);                   // 放回左边筷子
        V(chopstick[(i + 1) % 5]);         // 放回右边筷子
        ...                                // 思考
    }

管程

信号量机制中，手操 PV 过于扯淡，太容易写成死锁了。

管程：封装共享资源和同步

monitor Demo {  // 定义管程名称
    // 定义数据结构
    共享数据结构 S;
    //对共享数据结构初始化语句
    init_code () {
        S = 5;  // 初始化资源数
    }
    // 申请资源
    take_away () {
        S--;  // 可用资源数 - 1
        ...
    }
    //归还资源
    give_back () {
        S++;  // 可用资源数 + 1
        ...
    }
}

Java 中使用 synchronized 关键字描述一个函数，则该函数同一时间段只能被一个线程调用

死锁

死锁：各进程互相等待对方手里资源

死锁产生必要条件：

• 互斥条件：进程要求所分配资源进行排他性使用
• 不可剥夺条件：进程所获得资源在未使用完之前，不能被其他进程强行夺走
• 请求并保持条件：进程已经保持至少一个资源，但又提出新的资源要求
• 循环等待条件：存在进程资源循环等待链

死锁处理

死锁处理策略	资源分配策略	优点	缺点
死锁预防	设置限制条件，破坏必要条件之一	适用突发式处理进程 不必进行剥夺	效率低，初始化时间延长 剥夺次数过多 不便灵活申请新资源
死锁避免	资源动态分配过程，避免系统进入不安全状态	不必进行剥夺	必须知道将来新资源需求 进程不能被长时间阻塞
死锁检测	定期检查死锁是否已经发生	不延长进程初始化时间 允许对死锁进行现场处理	通过剥夺解除死锁，造成损失

死锁预防

死锁预防	含义	缺点
破坏互斥条件	将临界资源改为可共享使用资源	可行性不高，很多时候无法破坏
破坏不可剥夺条件	方案一：申请资源得不到满足时，立即释放拥有的所有资源 方案二：申请资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）	实现复杂 导致部分工作失效 反复申请和释放导致开销大 可能导致饥饿
破坏请求和保持条件	运行前分配好所有需要的资源，之后一直保持	资源利用率低 可能导致饥饿
破坏循环等待条件	给资源编号，必须按照编号从小到大顺序申请资源	不方便新增设备 会导致资源麻烦 用户编程麻烦

死锁避免

安全状态：系统按某种序列为每个进程分配所需资源，使得每个进程顺利完成

不安全状态：系统存在不安全序列_{死锁是非安全状态子集}

银行家算法

将操作系统视作银行家，管理的资源视作银行家管理的资金，进程请求资源视作用户向银行家贷款

数据结构描述：假设系统中有 $n$ 个进程，$m$ 类资源

• 可利用资源向量 Available：含有 $m$ 个元素的数组，每个元素代表一类可用的资源数目
  Available[j] = K 表示此时系统中有 $K$ 个 $R_j$ 类资源可用

• 最大需求矩阵 Max：$n\times m$ 矩阵，定义系统中 $n$ 个进程中的每个进程对 $m$ 类资源的最大需求
  Max[i, j] = K 表示进程 $P_i$ 需要 $R_j$ 类资源的最大数目为 $K$

• 分配矩阵 Allocation：$n\times m$ 矩阵，定义系统中每类资源当前已分配给每个进程的资源数
  Allocation[i, j] = K 表示进程 $P_i$ 当前已分得 $R_j$ 类资源数目为 $K$

• 需求居中 Need：$n\times m$ 矩阵，表示进程接下来最多还要多少资源
  Need[i, j] = K 表示进程 $P_i$ 还需要 $R_j$ 类资源数目为 $K$

$$
\text{Need}=\text{Max}-\text{Allocation}
$$

银行家算法：设 $\text{Request}_i$ 是进程 $P_i$ 请求向量，Request[i, j] = K 表示进程 $P_i$ 需要 $j$ 类资源 $K$ 个

1. 若 $\text{Request}_i\left[j\right]\le \text{Need}\left[i,j\right]$，转步骤 2
   否则认为出错，因为所需资源数超过宣布最大值

2. 若 $\text{Request}_i\left[j\right]\le \text{Available}\left[j\right]$，转步骤 3
   否则表示尚无足够资源，$P_i$ 必须等待

3. 系统试探将资源分配给进程 $P_i$，并修改数据结构数值
   $\text{Available}=\text{Available}-\text{Request}_i$
   $\text{Allocation}\left[i,j\right] = \text{Allocation}\left[i,j\right] + \text{Request}_i\left[j\right]$
   $\text{Need}\left[i,j\right]=\text{Need}\left[i,j\right]-\text{Request}_i\left[j\right]$

4. 系统执行安全性算法，检测此次资源分配后系统是否安全
   安全则将资源分配给 $P_i$
   否则将本次试探作废，让进程 $P_i$ 继续等待

安全性算法：设置工作向量 $\text{Work}$，表示系统中剩余可用资源数目，有 $m$ 个元素

1. 初始化 $\text{Work}=\text{Available}$
   初始时安全序列为空

2. 从 $\text{Need}$ 矩阵中找到符合下面条件的行：该行对应进程不在安全序列且改行小于等于 $\text{Work}$ 向量
   找到后将对应进程加入安全序列
   找不到执行步骤 4

3. 进程 $P_i$ 进入安全序列后，可顺利执行直至完成，并释放所分配资源，返回步骤2
   $\text{Work}=\text{Work}+\text{Allocation}\left[i\right]$

4. 若此时安全序列中已有所有进程，则系统处于安全状态
   否则系统处于不安全状态

死锁检测

可用资源分配图这一数据结构

• 请求边：进程到资源有向边
• 分配边：资源到进程

简化资源分配图：找到一条有向边与其相连，且该有向边对应资源申请数量小于等于系统中已有空闲资源数量，消去请求边和分配边，重复操作

能够完全简化的资源分配图即可以避免死锁

死锁解除

死锁解除	具体方法
资源剥夺法	挂起某些死锁进程并抢占资源
撤销进程法	强制撤销部分、甚至全部死锁进程并剥夺资源 根据进程优先级，已执行时间、还要执行多久等考虑
进程回退法	让一个或多个死锁进程回退到足以回避死锁的底部