mirror of
https://github.com/cs341-illinois/coursebook.git
synced 2026-10-01 23:54:40 +08:00
Lawrence Angrave
76680db5f7
The chapter declared the resource allocation graph directed and then gave a cycle test whose entire rule was "if this node has been visited, report a cycle". That is only sound under assumptions the text never stated. It searches just the subgraph reachable from its start node, yet its API hands the caller a visited array to reuse across roots -- and doing so makes it report a cycle for the ordinary case of two processes waiting on one resource held by a third. The struct it was built on was not valid C either: it named the typedef Graph inside the typedef defining it. Replace it with the standard three-colour DFS, which distinguishes nodes that are finished from nodes on the current path, and explain the distinction with the false-positive case that motivates it. Add the O(V+E) cost, state the single instance assumption before the algorithm rather than leaving it implicit, and note that multiple instances leave a cycle necessary but not sufficient. Supersedes #195 by Cay Zhang, who diagnosed the problem and proposed the first fix; carrying over the AUTHORS entry from that PR.
260 B
260 B
Current
- [Name] [Change]
- [Lawrence Angrave, Cay Zhang] Deadlock: replace the resource allocation graph cycle detection snippet with a correct directed graph DFS, and explain why the "already seen" shortcut reports deadlocks that do not exist.