2-1.死锁-经典同步问题
三、经典同步问题
1.生产者-消费者问题
计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池联系起来，环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品。
下面给出基于环形缓冲区的生产者与消费者关系的形式描述，设：
（1）公用信号量mutex：初值为1，用于实现临界区互斥。
（1）生产者私用信号量empty：初值为n，指示空缓冲块数目。
（2）消费者私用信号量full：初值为0，指示满缓冲块数目。
（3）整型量in和out初值均为0，in指示首空缓冲块序号，out指示首满缓冲块序号。
semaphore empty=n, full=0;
item buffer［0, …, n-1］；//buffer[n]
integer in=0, out=0;
parbegin
producer:begin
repeat
data= produce_item();
wait(empty);
buffer(in) = data;
in = (in+1) mod n;
signal(full);
until false;
end
consumer:begin
repeat
wait(full);
data = buffer(out);
out =(out+1) mod n;
signal(empty);
consumer the data;
until false;
end
parend2.读者-写者问题
读者-写者1.png
（1）特点
（1） 任意多个读进程可以同时读这个文件； （2） 一次只有一个写进程可以往文件中写； （3） 如果一个写进程正在进行操作，禁止任何 读进程读文件。
读者-写者.png
3.哲学家问题（集合信号量）
四、死锁：(重点)
0.死锁概念
多个进行相互等待对方资源，在得到所有资源继续运行之前，都不会释放自己已有的资源，这样造成了循环等待的现象。
1.产生的原因：
semaphore SR1=1，SR2=1；
Parbegin
P1: Begin
Repeate
Wait（SR1）； ……………………..a
Wait（SR2）； ……………………..b
P1进程的临界区；
Signal（SR2）；
Signal（SR1）；
Until false；
End
P2: Begin
Repeate
Wait（SR2）； …………………….c
Wait（SR1）； …………………….d
P2进程的临界区；
Signal（SR1）；
Signal（SR2）；
Until false；
End
Parend.
# 这就是一个死锁，P1、P2都申请了R1、R2资源，但哪一个都没有完成，也无法请求，互相等待。（1）竞争资源(资源不够)：
资源的数量不是足够多，不能同时满足所有进程提出的资源申请，这就造成了资源的竞争，而且资源的使用不允许剥夺。
注意：
①系统不发生死锁的资源最少数：
为每个进程均只差一个资源的情况，只要再加一个资源就不可能发生死锁了。
（2）进程间推进顺序非法:
进程的推进次序影响系统对资源的使用。 比如，上述的P1、P2进程，如果让P1进程申请R1资源，再申请R2资源，然后P2申请R2，可能这时P2暂时因得不到资源而阻塞，但P1进程需要的资源都已满足，P1进程会使用资源结束，释放资源并唤醒P2进程。这样的推进方式就不会死锁了。
进程间推进顺序非法.png
2.死锁产生必要条件：
1）互斥条件(资源不共享)。 2）请求和保持条件。 3）资源不剥夺条件。 4）环路等待条件。
3.预防死锁的算法：
（1）安全状态
是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统能找到这样一个安全序列，则称系统处于安全状态。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
注意：安全序列可能不唯一。
我的理解：
当已求出剩余可用资源矩阵时，将剩余可用资源矩阵的各项 与 剩余需求矩阵对应各项进行逐个比较，若剩余需求 < 剩余可用资源（记住：一定是小于，等于不行）时则优先满足该进程，进程完成后，释放占用资源 到 剩余可用资源；再依次比较。
（2）银行家算法： 期末10分大题。
0.概念
银行家的做法就是判断系统的安全性，动态地决定资源的分配。 银行家算法是一种代表性的避免死锁的算法。它允许进程动态地申请资源，系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则不分配。
1．银行家算法中的数据结构：
(m个进程n类资源)
(1) 可利用资源向量: 系统中每类资源的最大数量。
这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而 动态地改变。 如果Available[j]=K，则表示系统中现有Rj类资源K个。
(2) 最大需求矩阵Max : 也就是完成该进程所需各类资源总数。
这是一个m×n的矩阵，它定义了系统中 m个进程中的每一个进程对n类资源的最大需求。 如果Max[i,j]=K，则表示 进程 i 需要 Rj 类资源的最大数目为K。
(3) 分配矩阵Allocation : 也就是为该进程每类资源分配的数量。
这也是一个m×n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。 如果Allocation[i,j]=K，则表示 进程 i当前已分得R j类资源的数目为K。
(4) 剩余需求矩阵Need : 系统分配一次资源后，完成该进程还需每类资源多少。
这也是一个m×n的矩阵，用以表示每一个进程尚需的各类资源数。 如果Need[i,j]=K，则表示 进程 i 还需要 R j 类资源K个，方能完成其任务。
上述三个矩阵间存在下述关系：
Need[i, j]=Max[i, j]-Allocation[i, j] #尚需要的资源量=最大资源需求量-已分配资源量
(5) 剩余可用资源矩阵Available: 剩余资源 = 总的 - 已分配的。
例1：
银行家算法例1.png
银行家算法例1.1.png
银行家算法例1.2.png
银行家算法例1.3.png
银行家算法例1.4.png
4.死锁的检测和解除：
（1）死锁检测：
1）资源分配图:
资源分配图.png
一组进程结点P={p1,p2, …,pn}和一组资源结点R={r1,r2, …,rn}，N是节点的集合，N=PUR。即： N= {p1,p2, …,pn} U{r1,r2, …,rn}。 E是有向边的集合，e∈E，e连接着P中的一个结点和R中的一个结点，e={pi, rj}是资源请求边，由进程pi指向资源rj，表示进程pi请求一个单位的rj资源。e={rj, pi}是资源分配边，由资源rj指向进程pi, 它表示把一个单位的资源rj分配给进程pi。
2）资源分配图化简:
方法步骤:
- 第一步：先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞（“不阻塞”即：系统有足够的空闲资源分配给它）的
- 第二步：把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来
- 第三步：看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。
- 第四步：最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。
例：
资源分配图例1.png
解析：
R1有两个资源，一个分配给了P1,,一个分配给了P3，此时P2申请R1的资源，因为R1此时没有可用资源，P2堵塞。
R2有三个资源，已经给P1,P2,P3，各自分配了一个资源，而P1此时又再次申请资源R2,P1堵塞
R3有两个资源，已经分配给P2一个，P2申请一个资源，分配给它，所以P3是非阻塞结点
化简的话，看从没有阻塞的结点开始，删去P3周围所有的bian边，使其成为一个孤立的点，然后看剩下的资源按上述步骤再次进行分配，若到最后只剩下一群孤立的点，则说明该资源图是可以化简的。3)死锁定理：
如果资源分配图是可完全化简的，则系统是安全的，如果资源分配图是不可化简的，则系统处于不安全状态，会发生死锁。
（2）死锁解除：
1）剥夺法恢复
将某些资源从其它进程强占过来分配给另一些进程。要求强占不影响原进程恢复后的执行。与资源的属性有关，难实现。
2）撤销进程
这是常用的解除死锁的方法，从系统中撤消某些进程，释放资源以解除死锁。要求保证系统的数据等的一致性，难于判断。
3）回退法恢复
系统执行过程中设置若干断点，并保存现场。采用回滚方式释放资源以解除死锁。要求保护的现场不能频繁覆盖。
五、管程
1.管程的定义
管程：是代表共享资源的数据结构，以及对该数据结构实施操作的一组过程所组成的管理程序，共同构成操作系统的资源管理模块，称为管程。是进程同步的工具。
2.管程由四部分组成：
局部于管程的共享变量说明； 对该数据结构进行操作的一组过程； 对局部于管程的数据设置初始值的语句。 管程名字。