multithreading - 使用多线程算法的交通路口仿真

这是一个采访问题，被问到并希望找到有效的解决方案。

问题

如图所示，考虑四个道路的交叉点。定义每条道路都有一个方向。您将如何解决该问题，以便改善交通状况和避免死锁。

相交被分为四个象限[以黄色显示]。

汽车从四个方向[0,1,2,3]随机进入路口

在交叉路口，每辆车都可以移动。三种可能的 Action 是

向左走

直接进入

右移

例如:



半完整的解决方案

黄色标记的每个象限都有一个与之关联的信号量。
我想象的是一个两阶段协议(protocol)，其中每辆车都会

获取将通过

传递的象限列表

从最后一个象限开始锁定每个象限

在上面的示例中，从方向2 出发的汽车将锁定象限0 ，象限1 和象限2 。

穿过十字路口

释放获得的锁。

锁以相同顺序释放。 象限0 ，象限1 和象限2

但是，上述解决方案不是最佳解决方案，因为它会导致死锁。

我的问题是

还有什么/更好的方法可以实现？

我可以在C语言中使用信号量来实现吗？

如果没有，我应该看哪种同步方法？

更新

我想要一个允许多辆车进入交叉路口并仍然避免死锁和碰撞的解决方案。整个交叉路口只有一个锁会比优化还差。

最佳答案

您的解决方案(如步骤2中所建议)无法避免死锁。

考虑一下这样的情况:在四条街道上有汽车要向左转。然后所有的汽车开始锁定不同的助剂:

从方向0开始，它锁定游丝2。
从方向1开始，它会锁定助熔剂3。
从方向2开始，它会锁定游丝0。
从方向3，它会锁定游丝1。
-死锁-

您可以通过四个方向共享一个互斥锁来避免死锁。

关于multithreading - 使用多线程算法的交通路口仿真，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9404484/