基于深度优先搜索算法的操作系统死锁检测
OS Deadlock Detection Based on Depth-first Search Algorithm
丁红霞1
作者信息
摘要
操作系统在现代生活中扮演着至关重要的角色,它被嵌入各种物联网和各种规模的计算机中.操作系统提供的服务之一是为进程分配资源,在分配过程中,可能会出现死锁.因此,操作系统必须提供一个能够检查系统状态以确定是否发生了死锁的算法.对于单一实例的资源类型,可以用等待图模型来检测死锁.但是教材中一般没有算法描述,只说时间复杂度是O(n2).文章将深度优先搜索算法应用于等待图模型检测死锁,其时间复杂度是O(n+m).
Abstract
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).
关键词
深度优先搜索/死锁检测/操作系统/等待图模型Key words
depth-first search/deadlock detection/operating system/wait-for graph model引用本文复制引用
出版年
2024
NETL
NSTL
万方数据