安全序列

1安全序列假设系统有4个进程，分别为P1、P2、P3、P4，9个R1资源，3个R2资源，6个R3资源，下图为T0时刻的资源分配表：进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102P3314211103P4422002420Max表示：某个进程一共需要的资源个数。Allocation表示：进程已分配到的资源个数。Need表示：进程还需要的资源个数。Available表示：系统到最后还剩下的空闲资源个数。Max=Allocation+Need一共需要已分配未分配2另外，Available（1，1,2）表示：系统剩下1个R1资源，1个R2资源，2个R3资源空闲。2Need（1,0,2）表示：进程P2还需要1个R1资源，0个R2资源，2个R3资源)1,0,1(Re1quest表示：进程P1申请1个R1资源，0个R2资源，1个R3资源表示进程P2表示进程P13例如：进程MaxAllocationNeedR1R2R3R1R2R3R1R2R3P1322100222P1：3=1+2（一共需要3个R1资源，已分配1个R1资源，还需要2个R1资源）进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102P3314211103P4422002420上表所示：系统已经给P1分配了1个R1资源，给P2分配了5个R1资源，给P3分配了2个R1资源，给P1分配了0个R1资源，而系统原来一共有9个R1资源（题目已给出），所以，系统到最后一共还剩下9-（1+5+2+0）=1个R1资源同理：系统到最后一共还剩下3-（0+1+1+0）=1个R1资源系统到最后一共还剩下6-（0+1+1+2）=2个R1资源4如何求安全序列？进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102P3314211103P4422002420第一步：先看表中的Available这一列，系统一共还剩下1个R1资源，1个R2资源，2个R3资源。第二步：再看表中的Need这一列，只有进程P2申请的3个资源数分别小于系统剩余的3个资源数。所以先把剩余的系统资源分配给P1，让P2开始运行。（P1要申请2个R1和2个R2，但此时系统只剩下1个R1和1个R2，所以不能满足它的申请；P3要申请3个R3，但此时系统只剩下2个R3，所以也不能满足它的申请；P4要申请4个R1和2个R2，但系统只剩下1个R1和1个R2，所以也不能满足它的申请；）第三步：P2运行完后，释放它所占有的全部资源（6个R1，1个R2，3个R3），系统回收这些资源，因此系统此时一共剩下的资源增加为：6个R1，2个R2，3个R3（即：Allocation+Available）。得出下图结果：5进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222623P3314211103P4422002420第四步：再看表中的Need这一列，此时，进程P1、P3、P4申请的3个资源数都分别小于系统剩余的3个资源数。所以系统可以满足其中任意一个进程的申请。我们就先把系统资源分配给P1，让P1开始运行。第五步：P1运行完后，释放它所占有的全部资源（3个R1，2个R2，2个R3），系统回收这些资源，因此系统此时一共剩下的资源增加为：7个R1，2个R2，3个R3（即：Allocation+Available）。得出下图结果：进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P3314211103723P4422002420第六步：再看表中的Need这一列，此时，进程P3、P4申请的3个资源数都分别小于系统剩余的3个资源数。所以系统可以满足其中任意一个进程的申请。我们就先把系统资源分配给P3，让P3开始运行。6第七步：P3运行完后，释放它所占有的全部资源（3个R1，1个R2，4个R3），系统回收这些资源，因此系统此时一共剩下的资源增加为：9个R1，3个R2，4个R3（即：Allocation+Available）。得出下图结果：进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P4422002420934第八步：再看表中的Need这一列，此时，进程P4申请的3个资源数都分别小于系统剩余的3个资源数。所以系统可以满足它的申请。我们就把系统资源分配给P3，让P3开始运行。第九步：P3运行完后，释放它所占有的全部资源（4个R1，2个R2，2个R3），系统回收这些资源，因此系统此时一共剩下的资源增加为：9个R1，3个R2，6个R3（即：Allocation+Available）。得出下图结果：进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3936第十步：此时所有进程运行完毕，它们运行的时间先后顺序为：{P2,P1,P3,P4}我们把这个序列称为安全序列，因为按照这个先后顺序执行进程，系统不会出现死锁，所以是安全的。7注意：安全序列不是唯一的。（因为在“第四步”中，可以选择P1,P3,P4其中任意一个先执行，所以安全序列也可以是{P2,P3,P1,P4}、或{P2,P4,P3,P1}、或{P2,P4,P1,P3}等。8安全性检查安全性检查，实质是对前面那个{P2,P1,P3,P4,}安全序列进行检验，下图是T0时刻的安全性检查（对应最前面那个T0时刻资源分配表）进程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2112102511623trueP1623222100723trueP3723103211934trueP4934420002936trueWork表示：系统可提供给进程继续运行的各类资源的空闲资源的个数。（安全性检查开始时，Work=Available）Work与Available的区别：Available是第一个进程运行前，系统剩下的空闲资源。Work是每个进程运行前，系统剩下的空闲资源。（“Available”相当于第一个进程运行前的“Work”）Finish表示：系统是否有足够的进程分配给进程。开始时，Finish=false；当有足够资源分配给进程时，Finish=true。9进程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2112102511623trueP1623222100723trueP3723103211934trueP4934420002936true注意：这里与前面的资源分配表是不同的，是按之前的安全序列排列的，第一步：先看进程P2这一行，系统可提供的空闲资源“Work”大于进程P2所需要的资源“Need”，所以“Finish”为“true”。当进程P2运行完后，释放其所占有的全部资源，接着系统回收这些资源，此时，系统剩下的空闲资源为“Work+Allocation”，如下图所示：进程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2112102511623true第二步：再看进程P1这一行，先把P2运行完时，系统剩余的空闲资源“Work+Allocation”填入P2的“Work”这一列，接着，可以发现系统可提供的空闲资源“Work”大于进程P1所需要的资源“Need”，所以“Finish”为“true”。当进程P1运行完后，释放其所占有的全部资源，接着系统回收这些资源，此时，系统剩下的空闲资源为“Work+Allocation”，如下图所示：10进程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2112102511623trueP1623222100723true以此类推。复制到这里11例2假设有如下资源分配状态如下：进程AllocationNeedAvailableABCDABCDABCDP0201121001020P121001112P211103100P311010020P410002110解：可用资源为1020要先从这些个进程里面看谁的need小于等于它，这里只能选择p3（0020），p3完成后释放他的allocation(1101),此时可用资源变成2121，然后再从其余的里面找need小于等于2121的，这里我选的是p0，同样的p0执行完以后，释放出他的已有资源后，可用资源变成4132，同理依次可选择p4、p2、p1。由此可知此时系统是安全的，因为可以找到一个安全序列p3，p0，p4p2p1（注意安全序列不是唯一的）