基于深度优先搜索算法的操作系统死锁检测  

OS Deadlock Detection Based on Depth-first Search Algorithm

作　　者：丁红霞 DING Hong-xia(Taizhou University,Taizhou 225300,China)

机构地区：[1]泰州学院,江苏泰州225300

出　　处：《电脑与信息技术》2024年第3期17-19,54,共4页Computer and Information Technology

摘　　要：操作系统在现代生活中扮演着至关重要的角色,它被嵌入各种物联网和各种规模的计算机中。操作系统提供的服务之一是为进程分配资源,在分配过程中,可能会出现死锁。因此,操作系统必须提供一个能够检查系统状态以确定是否发生了死锁的算法。对于单一实例的资源类型,可以用等待图模型来检测死锁。但是教材中一般没有算法描述,只说时间复杂度是O(n~2)。文章将深度优先搜索算法应用于等待图模型检测死锁,其时间复杂度是O(n+m)。Operating systems play a crucial role in modern life,being embedded in all kinds of iot and computers of all sizes One of the services provided by operating systems is the allocation of resources to processes,during which deadlocks may occur.Therefore the operating system must provide an algorithm to check the system state to determine if a deadlock has occurred.For single-instance resource type,the wait-for graph model can be used to detect deadlocks.However,the algorithm is not generally described in textbooks,except that the time complexity is O(n2).The article applies the depth-first search algorithm to the wait-for graph model to detect deadlocks,and its time complexity is O(n+m).

关 键 词：深度优先搜索 死锁检测 操作系统 等待图模型 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]