某系统的进程可能占有和等待一些资源,现给出在某一时刻dump的这些进程占有和等待的资源信息。
请按照如下简化规则分析哪些进程发生了死锁;
请升序返回所有死锁的进程ID列表,或空列表[]。
简化规则如下:
如果某个进程P的任意等待资源被占有,则该进程必须等待,等待期间该进程不会是犯法所占用的资源;
如果进程P所等待的资源全部都未被其他进程占有,则该进程必将释放所占有的资源。
基于上,如果某个进程因为所等待的资源一直被占有而无限等待下去,则认为该进程发生了死锁。
输入:
第一行为一个整数num,表示进程个数;
接下来的的num行,依次表示每个进程占有和等待的资源情况,格式为:进程ID (占有资源列表) (等待资源列表);
输入保证:每个资源最多只会被一个进程占有。
输出:
升序返回所有死锁的进程ID列表,或空列表[]。
测试用例
(1)
5
100 () (20)
1 (40 20) (10)
2 (10) (30 100)
3 (100 300) (40 0)
0 () (30)
[1 2 3 100]
解释:
进程1等待被进程2占有的资源10;
进程2等待被进程3占有的资源100;
进程3等待被进程1占有的资源40;
这三个进程都因为锁等待的资源一直被占有而无线等待下去,所以这三个进程都发生了死锁。
因为进程1死锁,资源20一直被占有,导致进程100也死锁;
进程0等待的资源30未被占有,因此进程0不死锁。
(2)
4
2 () (40 30)
1 (20) (30 40)
3 () ()
9 (40) (30)
[]
(3)
6
1 (10) (20 50)
2 (20) (30 60)
3 (30) (40)
5 (50) ()
6 (101) (202)
7 (202) (101)
[6 7]