死锁实验三玲语2

专业班级 计科 1602S 学号 2016190432105 姓名 lsimplehappy 实验三实验三 死锁的避免死锁的避免 一 实验目的一 实验目的 当系统的总资源数 m 小于或等于所有进程对资源的最大需求 时 就可能产 生死锁 死锁会引起计算机系统的瘫痪 银行家算法是在实现资源分配时避免死 锁的一个著名 算法 该算法是在能确保系统处于安全状态时才把资源分配给申请 者 通过本实验使学生能 进一步理解死锁的概念 并能选择一个算法来避免死锁 采用银行家算法来预防死锁是可靠的 但也是非常保守的 因为它限制了进 程对资源的 存取 从而降低了进程的并发运行程度 死锁检测并不限制进程对资 源的申请 只要有 就分配 但这也可能造成死锁 但由于死锁并不是经常发生 的 故大大提高了系统运行的效率 通过本实验 可使学生进一步加深理解和掌 握死锁的检测算法 二 实验环境二 实验环境 C C C Cfree Microsoft Visual Studio 6 0 Microsoft Visual Studio NET2005 三 实验的重点和难点三 实验的重点和难点 1 避免死锁的实质在于如何防止系统进入不安全状态 2 在银行家算法中用到了可利用资源向量 Available 最大需求矩阵 Max 分配矩阵 Allocation 需求矩阵 Need 等数据结构 而在安全性检查算法中则 还要用到工作向量 Work 和完成向量 Finish 等数据结构 1 3 安全性检查算法的目的是寻找一个安全序列 四 实验内容四 实验内容 系统中有 m 个同类资源被 n 个进程共享 每个进程对资源的最大需求数分 别为 S1 S2 Sn 且 Max Si m i 1 2 n 进程可以动态地申请资源和释放 资源 编写一个程序 实现银行家算法 当系统将资源分配给某一进程而不会死 锁时 就分配之 否则 推迟分配 并显示适当的信息 数据结构和操作说明 参照教材上有关银行家算法的资源分配表 设计适当的 数据结构 进程要分配的资源数 可由随机数决定或命令行输入 但要注意数据的 有效范围 分别使用检测 进程 资源循环等待链 的方法来检测进程的死锁状 态 对 于相同的进程资源分配 占用次序 比较两个算法的结果 数据结构 死锁检测算法的数据结构参考书教材资源占用矩阵 进程等待 资 源矩阵 Q 资源总数向量和可用资源向量 W 检测 进程 资源循环等待链 的 算法可对所有的资源和进程进行编号 并设置一张资源分配表和一张进程等待表 五 实验要求 五 实验要求 画出实现银行家算法的程序框图 说明数据结构 在每当进程要分配资源时 以及释放资 源后 打印输出资源分配或释放后的分配情况表 如可能产生死锁 显示适当信息 如不会 产生死锁 更新系统的资源分配状态表 画出所实现算法的框图 说明所采用的数据结构 进程和所申请的资源可用 命令行或随机数 决定 进行一次分配就检测死锁 输出所涉及的表格数据 2 3 六 实验代码及实验结果 六 实验代码及实验结果 include include typedef struct int A int B int C RES define false 0 define true 1 系统中所有进程数量 define PNUMBER 3 最大需求矩阵 RES Max PNUMBER 已分配资源数矩阵 RES Allocation PNUMBER 需求矩阵 RES Need PNUMBER 可用资源向量 RES Available 0 0 0 安全序列 int safe PNUMBER void setConfig int i 0 j 0 4 printf 开始手动配置资源 n 可分配资源 printf 输入可分配资源 n scanf d d d 最大需求矩阵 MAX printf 输入最大需求矩阵 dx d n PNUMBER PNUMBER for i 0 i PNUMBER i scanf d d d 已分配矩阵 Alloc printf 输入已分配矩阵 dx d n PNUMBER PNUMBER for i 0 i PNUMBER i scanf d d d 需求矩阵 printf 输入需求矩阵 dx d n PNUMBER PNUMBER for i 0 i PNUMBER i scanf d d d printf 结束配置资源 n void loadConfig FILE fp1 if fp1 fopen config txt r NULL 5 printf 没有发现配置文件 请手动输入 n setConfig else int i 0 printf 发现配置文件 开始导入 n 可分配资源 fscanf fp1 d d d 最大需求矩阵 MAX for i 0 i PNUMBER i fscanf fp1 d d d 已分配矩阵 Alloc for i 0 i PNUMBER i fscanf fp1 d d d 需求矩阵 for i 0 iA Available B res B Available C res C Allocation process A res A Allocation process B res B Allocation process C res C Need process A res A Need process B res B Need process C res C 若试探分配后进入不安全状态 将分配回滚 void RollBack int process RES res Available A res A Available B res B Available C res C Allocation process A res A Allocation process B res B Allocation process C res C Need process A res A Need process B res B Need process C res C 安全性检查 bool SafeCheck 7 RES Work Work A Available A Work B Available B Work C Available C bool Finish PNUMBER false false false int i int j 0 for i 0 i PNUMBER i 是否已检查过 if Finish i false 是否有足够的资源分配给该进程 if Need i A Work A Work B Allocation i B Work C Allocation i C Finish i true safe j i i 1 重新进行遍历 如果所有进程的 Finish 向量都为 true 则处于安全状态 否则为不安 全状态 for i 0 i A B C A B C Available C 试探分配 ProbeAlloc process res 如果安全检查成立 则请求成功 否则将分配回滚并返回失 败 if SafeCheck return true else printf 安全性检查失败 原因 系统将进入不安全状态 有可能引起死锁 n printf 正在回滚 n RollBack process res else 9 printf 安全性检查失败 原因 请求大于可利用资源 n else printf 安全性检查失败 原因 请求大于需求 n return false 输出资源分配表 void PrintTable printf 资源分配表 n printf Process Max Allocation Need Available n printf A B C A B C A B C A B C n printf P0 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d n Max 0 A Max 0 B Max 0 C Allocation 0 A Allocation 0 B Alloc ation 0 C Need 0 A Need 0 B Need 0 C Available A Available B Availa ble C printf P1 2d 2d 2d 2d 2d 2d 2d 2d 2d n Max 1 A Max 1 B Max 1 C Allocation 1 A Allocation 1 B Alloc ation 1 C Need 1 A Need 1 B Need 1 C printf P2 2d 2d 2d 2d 2d 2d 2d 2d 2d n Max 2 A Max 2 B Max 2 C Allocation 2 A Allocation 2 B Alloc ation 2 C Need 2 A Need 2 B Need 2 C printf n 10 银行家算法分配 void banker char ch 判断输入的是否是安全状态 PrintTable printf 先检查初始状态是否安全 n if SafeCheck printf 系统处于安全状态 n printf 安全序列是 P d P d P d n safe 0 safe 1 safe 2 else printf 系统处于不安全状态 程序将退出 n printf 执行完毕 n getchar return 开始分配 do int process RES res printf 请依次输入请求分配的进程和对三类资源的请求数量 进程 编号 0 1 2 n scanf d d d d if process 0 if request process 11 PrintTable printf 安全序列是 P d P d P d n safe 0 safe 1 safe 2 else printf 分配失败 n printf 是否继续分配 Y N getchar ch getchar else printf 输入的进程号 0 2 n ch y while ch Y ch y printf 执行完毕 n 随机分配算法执行 bool RandRequest int process RES res request 向量需小于 Available 向量 if res A B C Available C 试探分配 ProbeAlloc process res 判断进程是否执行完 执行完释放资源 if Max process A Allocation process A 有则使其执行完成 并将已分配给该进程的资源全部回 收 Available A Allocation process A Available B Allocation process B Available C Allocation process C Allocation process A 0 Allocation process B 0 Allocation process C 0 Need process A Max process A Need process B Max process B Need process C Max process C return true else printf 分配失败 原因 请求大于可利用资源 n return false 随机分配 void randPatch char ch 13 判断输入的是否是安全状态 PrintTable printf 先检查初始状态是否安全 n if SafeCheck printf 系统处于安全状态 n printf 安全序列是 P d P d P d n safe 0 safe 1 safe 2 else printf 系统处于不安全状态 程序将退出 n printf 执行完毕 n getchar return 开始分配 do int process RES res printf 请依次输入请求分配的进程和对三类资源的请求数量 进程 编号 0 1 2 n scanf d d d d if RandRequest process PrintTable if SafeCheck printf 系统发生死锁 getchar getchar break 14 else printf 分配失败 n printf 是否继续分配 Y N getchar ch getchar while ch Y ch y printf 执行完毕 n int main int x while 1 printf n printf t t t 共享资源分配与银行家算法 n printf n printf t t t 按 2 银行家算法 n printf t t t 按 3 随机分配算法 n printf t t t 按 0 退出系统 n printf n printf 您输入的是 scanf d fflush stdin 15 system cls printf n printf t t t 共享资源分配与银行家算法 if x 2 printf t 银行家算法 n else if x 3 printf t 随机分配算法 n printf n switch x case 1 加载配置文件 loadConfig 打印资源分配表 PrintTable printf 信息导入完成 n getchar break case 2 banker break case 3 randPatch break case 0 printf 退出系统 n n return 0 break default printf 请输入 0 1 之间的数字 n return 0 16 结果截图 结果截图 17 七 实验过程遇到的问题及其解决 七 实验过程遇到的问题及其解决 银行家分配算法原则是 当进程申请资源时 如果系统中现存资源数能满 足进程的当前资源申请量以及申请的资源数要小于需要的资源数 request j need i j request j available j 并且还 要验证是否有安全 只有在安全情况下才能将资源分配给它 也即银行家算法能避 免死锁的发生 操作系统按照银行家制定的规则为进程分配资源 当进程首次申请资源时 要测试该进