开发者

How do I prove whether or not a dining philosophers suffers from deadlock or starvation possibilities? Where to start?

I have a homework task to prove whether or not a particular variation on the dining philosophers problem suffers from deadlock or starvation. I suspect that the situation does not suffer at all from either but I'm finding this tricky to prove and I 开发者_开发百科don't really know where to start. Is there a general strategy for attacking this sort of problem?


You can read about Wait-for graphs (more details here) which are DAGs (Directed Acyclic Graphs) and are used to detect deadlocks.

cheers


For a start, I would be very surprised to hear there is a general strategy to solve the problem which is not so abstract as to be useless.

Now, showing the variation is safe is much, much easier than proving it: your task is to prove the variation is safe? If so, you might minimize the number of parts (reduce the number of philosophers to two or maybe three) and try ta apply one or more formal verification methods.

In practice, formal verification is so rare that I might illustrate it best with an example: I've talked with people working on software used in nuclear facilities (haven't gone into the details) and when I asked if they use formal verification, I got "well, yes, we should [be using it]..."

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜