增强预检的改进银行家算法与可视化.pdf

2023年9月计算机应用文摘第39 卷第17 期增强预检的改进银行家算法与可视化汪汉（安康学院电子信息与工程学院,陕西安康7 2 50 0 0)摘要：针对传统银行家算法在安全状态检查过程中存在对明显不满足系统要求的执行序列进行额外检查、无法实时追踪并发过程中的系统资源情况和无法快速定位目标安全序列等缺点，提出一种增强预检的改进银行家算法和可视化方案。首先，梳理传统银行家算法定义的数据结构和算法流程，通过引入新的数据结构缓存检查阶段系统资源快照信息；其次，分别基于需求资源总量排序和加权总量排序2 种方式增强预检能力；最后，提出可视化方案并导入测试数据验证其可行性。关键词：银行家算法；安全状态；安全序列；可视化WANG Han中图法分类号：TP316Improved banker algorithm and visualization for enhanced pre-inspection(School of Electronic Information and Engineering,Ankang University,Ankang,Shaanxi 725000,China)Abstract:Aiming at the shortcomings of the traditional banker algorithm in the process of securitystatus inspection,it has additional checks on the execution sequence that obviously does not meet thesystem requirements,cannot track the system resources in the concurrent process in real time,andcannot quickly locate the target security sequence,etc.An improved banker algorithm andvisualization scheme that enhances pre-inspection are proposed.First,sort out the data structure andalgorithm process defined by the traditional banker algorithm,and cache the system resourcesnapshot information in the inspection stage by introducing a new data structure,secondly,based onthe total amount of required resources and the weighted total sorting method to enhance the pre-inspection ability,finally,propose a visualization scheme and import test data to verify its feasibility.Key words:banker algorithm,security status,security sequence,visualization目前，主流操作系统通过引入并发或并行的工作方式来提高计算机资源利用率和系统吞吐量 1。同时,这种工作方式也会导致新的问题，如死锁就是在系统可用资源不充足且并发进程调度顺序不合理的情况下产生的。计算机在执行过程中一旦发生死锁，会导致系统资源利用率降低,甚至系统全面崩溃 2 ，银行家算法是动态避免死锁的经典算法。1传统银行家算法1.1传统银行家算法定义的数据结构(1)当前系统可用资源数记为Available。以资源种类j为下标的一维数组,如Available表示当前系统中j类资源的可用数量总和。(2)当前系统中并发进程执行完成所需申请各类资源数记为Max。以进程i、资源种类j为下标的二维数组,如Maxij 表示当前系统中i进程执行完成文献标识码：A所需j类资源的数量总和。（3）当前系统已分配给各并发进程的各类资源数记为Allocation,以进程i、资源种类j为下标的二维数组,如Allocationij 表示当前系统已分配给i进程的j类资源的数量总和。（4)系统在某一时刻接收到并发进程的资源申请记为 Request,以进程i、资源种类j为下标的二维数组,如 Requestij表示当前系统接收到i进程申请j类资源的数量总和。(5)当前系统中并发进程执行完成还需申请各类资源数记为Need,以进程i资源种类j为下标的二维数组,如Needi表示当前系统中i进程执行完成还需j类资源的数量总和。1.2传统银行家算法流程如图1所示，传统银行家算法流程分为预检阶段和安全检查阶段两部分 388系统接收到进程的资源请求Request类资源是否都满足Requestmul=Needdin是类资源是否都满足Requestil-Availableln否预检阶段系统接收到进程的资源请求后，进人预检阶段，首先验证该请求的合法性 4,第一步判断该进程所请求的每类资源的数量是否小于其还需申请的各类资源的数量,第二步判断该进程所请求的每类资源数量是否小于系统中每类资源可用数量。若两步都满足，则预检成功，进入安全检查阶段，若其中有一步不满足,则判定该请求为无效请求 5进人安全状态检查时，假定系统满足该进程请求,并修改当前系统记录的所有初始值。（1）当前系统可用资源数记为Work，初始值为修改后的Available。以资源种类j为下标的一维数组，如Workj表示当前系统中j类资源的可用数量总和。(2)当前系统并发进程是否已执行记为Finish，初始值为false。以进程i为下标的一维数组，如Finishi表示当前系统中i进程是否已执行完成。2改进银行家算法改进银行家算法在传统银行家算法定义的数据结构基础上引人新的数据结构以缓存检查阶段进程动态执行次序和系统资源快照信息。(1)当前系统并发进程的完成次序记为List。存储已完成进程的一维数组,如List2表示当前系统中第3个执行结束的进程。(2）当前系统信息快照记为Flow。存储当前时刻系统信息快照的一维数组,如Flow2表示当前系统在第3个进程执行完成时系统信息，包括资源信息Work和进程完成次序List。(3）当前系统中所有并发进程记为ProcessNames的一维数组,如ProcessNames2表示下标序号为2的进程名。（4）当前系统中所有资源名记为ResourceNames的一维数组,如ResourceNames2表示下标序号为2的资源名。改进算法的安全状态检查流程如图2 所示。计算机应用文摘开始开始假设系统满足该请求，修改进程数据Needi0-Request0Allocationili+=Requestj0立Availablelil-Requestpl初始化Work,Finish文一是否处在安全状态否！一图1传统银行家算法流程2023年第17 期安全检查阶段统计BackStep预检是否合法是否存在进程Needp0jAvailableiResulti+=Needili)+SumdResulti+=Needii图3基于加权总量排序的增强预检开始上传excel文件模版读取数据信息映射源JSON数据替换标准头部填项是否光报错信息结束4.2可视化模块通过Flow动态跟踪进程执行次序和系统资源状态信息，进行上下步切换查看 8 。安全状态检查可视化如图5所示。Need矩阵总量排序Need矩阵R1R2R3PO237P133P20P32P4回退次数BackStep:3安全序列：P1P2POP3P4上一步下一步当前执行序列：P1系统中当前可用资源数：R1:6;R2:3:R3:6;当前系统所有安全序列 9 的枚举列表如图6 所示，全排序需要遍历所有情况，不受改进算法的影响，同时提供精确搜索功能，实现目标安全序列的快速定位。计算机应用文摘安全状态：安全共计6 6 条安全序列计算系统总资源数筛选目标安全序列Suml=Availablel+Allocationjil遍历ProcessNames改进银行家算法安全状态检测结束resourceNames:R,R2,R37.processNames:Po,P1,P2,P3,P4,available:2,3,3,5.5,10,max:I5.3.61.补全字段14.0.11.14.24allcation:I1.平台可解析的3,2.3,标准JSON格式(4.0.34,0,5,2.0,4,3,1,4sum:18,6,22图4模板文件规格化差值排序Need矩阵R1R2R3P41P322062089P1P2POP3P4P1P2POP4P3P1P2P3P4POP1P2P4POP3Result升序排序P1P3POP2P4P1P3P2P4PO得到SortDiffNeed得到SorDifftProcessNamesR1R2R31P4P322P26P11PO23回退次数BackStep1安全序列：P4P3P2P1PO上一步下一步当前执行序列：P4P3系统中当前可用资源数：R1:7;R2:4:R3:11:图5安全状态检查可视化P1P2P3POP4P1P2P4P3POP1P3POP4P2P1P3P2POP4P1P3P4POP2P1P3P4P2PO图6安全序列可视化5结束语在传统银行家算法的基础上，本文提出增强预检的改进银行家算法,引入新的数据结构追踪并发执行过程系统资源情况，基于需求资源总量排序和加权总量排序的增强预检阶段能够规避无效进程执行序列。本文侧重于系统可用资源，后续可以为进程增加优先级,，从而进一步提升系统利用率。参考文献：1 刘璇.基于银行家算法的资源调度研究与实现 J.智能计算机与应用,2 0 2 2,12(7)：2 0 6-2 0 9+2 15.2江立.基于银行家算法的进程安全序列改进算法 J.计算机产品与流通,2 0 19(5)：155-156.3宋丹,李亚东.银行家算法的改进与实现 J.计算机时代，2021(6):64-67.【4】陈紫菌.基于银行家算法的研究和应用分析 J.网络安全技术与应用,2 0 2 0,No.230(2)：44-48.5 CHANG L D,LI J G.Control Strategy of RGV OperationBlockage and Deadlock in Plane Mobile Stereo GarageJ.IOP Conference Series:Earth and Environmental1Science,2021,719(2):129-137.P133336刘畅,文家俊,贾海鹏，等.死锁避免之模拟银行家算法的P20PO2回退次数BackStep:1安全序列：P4P3P1P2PO上一步下一步当前执行序列：P4P3系统中当前可用资源数：R1:7:R2:4;R3:11;036编程实现 J.电子测试,2 0 2 1,46 4(11)：7 7-7 8.7 龚建华.JSON格式数据在Web开发中的应用 J.办公自动化,2 0 13,2 6 4(2 0):46-48.8赵国庆,黄荣怀,陆志坚.知识可视化的理论与方法 J.开放教育研究,2 0 0 5(1):2 3-2 7.9李坤芩,熊琰,王磊，等.基于银行家算法的安全序列分析J.电子技术与软件工程，2 0 2 1,196(2）：2 31-2 32.作者简介：汪汉（1994一），硕士，助教，研究方向；计算机科学与技术。