您如何从逻辑上阐述操作系统死锁的问题？

Question

Prolog中的编程任务是编写一个程序，该程序接受进程，资源等的输入，并打印出安全的执行顺序，或者如果没有安全的执行顺序，则简单地返回false。

我对序言很陌生，我只是无法让自己以要求我思考的方式思考（也就是说，以逻辑方式提出问题，让编译器找出如何进行操作），我被困在程序上的思考。您如何用谓词和诸如此类的逻辑来表达这样一个问题？

样本输入如下：进程列表，资源对列表以及该资源和事实的可用实例数allocated(x,y)，其中x是进程，y是分配给x和x的资源列表。最后requested(x,y)，使得x是一个进程，y是x请求的资源列表。

对于我的一生，除了C ++，我什么都想不到。我太困了。我什至不需要代码，只需要清楚。

编辑：这是示例输入。我真的只需要看我需要做什么。我完全一无所知。

进程（[p1，p2，p3，p4，p5]）。

available_resources（[[r1，2]，[r2，2]，[r3，2]，[r4，1]，[r5，2]]。

已分配（p1，[r1，r2]）。

已分配（p2，[r1，r3]）。

已分配（p3，[r2]）。

已分配（p4，[r3]）。

已分配（p5，[r4]）。

requested（p5，[r5]）。

Answer 1

您要做的是应用"state search"方法。

• 以初始状态S0开始。
• 根据允许的规则将变换应用于S0，得到S1。规则必须只允许创建一致的状态。例如，规则可能不允许生成新资源。检查新状态S1是否满足允许您宣告胜利的“最终状态”或“解决状态”的条件。
• 如果不是，则根据允许的规则对S1进行变换，得到S2。
• 等
• 应用转换可能会使您生成一个状态，从该状态不可能取得进展，但也不是“最终状态”。你被困住了。在这种情况下，转储一些最新的转换，移回较早的状态，然后尝试其他转换。

通过这种方式，当您探索不同的可能性以达到最终状态之一（或单个最终状态，具体取决于问题）时，您会在状态空间中得到一棵状态树。

我们需要的是：

状态描述；
• 一组允许的状态转换（有时称为“运算符”；]]
• 确定我们是否被封锁的标准；
• 决定我们是否已找到最终状态的标准；
• 也许可以试探性地决定下一个要尝试的状态。如果状态空间足够小，我们可以盲目尝试所有内容，否则类似A*的方法可能会有用。
• 探索算法本身。从初始状态开始，它将应用运算符，生成新状态，如果被阻止则回溯，并在达到最终状态时终止。
• 状态说明

通过以下相关信息描述状态（在任何时间t）：

多个过程
• 一些资源，几种相同的资源
• 有关哪些进程分配了哪些资源的信息
• 有关哪些进程请求了哪些资源的信息
• 与信息学中的任何其他事物一样，我们需要上述数据结构。

Prolog中的默认数据结构是

term，它是符号树。极其有用的列表只是特定树的另一种表示形式。必须具有一种表示形式，以便它可以与人类对话，并且仍然可以通过Prolog代码轻松地进行操作。那么像这样的术语呢：

[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)]

这表示以下事实：进程p1拥有两个资源r1和一个资源r2，并且接下来要r3。

然后，完整状态是一个列表列表，用于指定有关每个进程的信息，例如：

[[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)],
 [process(p2),owns(r3),wants(r1)],
 [process(p3),owns(r3)]]

操作员说明
Prolog不允许“可变状态”，因此运算符是从一种状态到另一种状态的转换，而不是修补状态以表示其他状态。 
状态未就地修改的事实当然非常重要，因为我们（可能）希望保留已访问的状态，以便在被阻止的情况下能够“追溯”到较早的状态。] >
我想可以使用以下运算符：

在状态StateIn中，进程P请求它需要但无法获得的资源R。

request(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn

在状态StateIn中，进程P获得空闲的资源R。
obtain(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn
在状态StateIn中，进程P释放拥有的资源R。
free(StateIn, StateOut, P, R) :- .... code that builds StateOut from StateIn
编写该代码，使得如果StateIn为
[[process(p1),owns(r1),owns(r1),owns(r2),wants(r3)],
 [process(p2),owns(r3),wants(r1)],
 [process(p3),owns(r3)]]
然后free(StateIn, StateOut, p1, r2)将构造一个StateOut
[[process(p1),owns(r1),owns(r1),wants(r3)],
 [process(p2),owns(r3),wants(r1)],
 [process(p3),owns(r3)]]
这将成为搜索循环中的新当前状态。等]
决定我们是否处于当前状态的标准
通常被“阻止”表示没有运算符适用于该状态，因为对于所有运算符而言，没有有效的先决条件成立。 
在这种情况下，标准似乎是“国家暗示僵局”。

因此需要写谓词check_deadlock(StateIn)。它必须测试状态描述中是否有任何死锁情况（实际上是进行自己的少量搜索）。

决定我们是否找到最终状态的标准

这是未指定的。此问题的最终状态是什么？

无论如何，如果check_final(StateIn)确实是最终状态，则必须有true谓词返回StateIn。

注意，最终标准也可能是从开始状态到当前状态的整个路径。在这种情况下：check_path([StartState,NextState,...,CurrentState])。

探索算法

在Prolog中，这可能相对较短，如果您不使用特定的启发式方法并使情况保持原始，则可以免费进行深度优先搜索和回溯。

你们都准备好了！