独占访问2 Exclusive Access 2
题意翻译
一个庞大的系统中运行着 $n$ 个守护进程。每个进程恰好用到两个资源。这些资源不支持并发访问,所以这些进程通过锁来保证互斥访问。 每个进程的主循环如下:
```
loop forever
DoSomeNonCriticalWork()
P.lock()
Q.lock()
WorkWithResourcesPandQ()
Q.unlock()
P.unlock()
end loop
```
注意 ,$P$ 和 $Q$ 的顺序至关重要。先获取 $P$ 和先获取 $Q$ 可能产生截然不同得到效果。
给定每个进程所需的两种资源,你的任务是确定每个进程获取所得顺序,使得进程永远不会死锁,且最坏情况下等待的最长链长度最小。
感谢 @We269 提供的翻译。感谢 @皎月半洒花 完善翻译 and 题面。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=447&page=show_problem&problem=4185
[PDF](https://uva.onlinejudge.org/external/14/p1439.pdf)
输入输出格式
输入格式
输出格式
输入输出样例
输入样例 #1
2
P Q
R S
6
P Q
Q R
R S
S T
T U
U P
4
P Q
P Q
P Q
P Q
3
P Q
Q R
R P
6
P Q
Q S
S R
R P
P S
R Q
输出样例 #1
0
P Q
R S
0
P Q
R Q
R S
T S
T U
P U
0
P Q
P Q
P Q
P Q
1
P Q
Q R
P R
2
P Q
Q S
R S
P R
P S
R Q