使用多线程算法进行交通路口模拟

Question

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

问题

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

1. 交叉点分为四个象限[以黄色显示]。
2. 汽车从四个方向[0,1,2,3]随机进入交叉路口，
3. 在交叉路口每辆车可以单次移动。三种可能的行动是
   1. 向左走
   2. 直走
   3. 向右走

例如：

如果汽车从方向 2 驶入并想要左转。它应该通过 象限 2、象限 1 以及最后的象限 0

半完整解决方案

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

1. 获得它将通过的象限列表，
2. 锁定从最后一个象限开始的每个象限
3. 在上面的示例中，来自方向 2 的汽车将锁定象限 0、象限 1，然后锁定象限 2 >.
4. 通过交叉路口
5. 释放获得的锁。
6. 锁以相同的顺序释放。 象限 0、象限 1 和象限 2

但是，上述解决方案并不是最优的，因为它会导致死锁。 em>

我的问题是

1. 还有什么其他/更好的方法可以实现这一点？
2. 我可以使用 C 中的信号量来实现吗？
3. 如果不是，我应该考虑什么同步方法？

更新

1. 我想要一个解决方案，允许多辆车进入交叉路口，并且仍然避免死锁和碰撞。在整个交叉路口上有一个锁将不够优化。

Answer 1

您的解决方案（如步骤 2 中建议的那样）无法避免死锁。

考虑一下当来自四条街道的车辆想要向左转时的情况。然后所有的汽车开始锁定不同的方向：

从方向 0 开始，它锁定方向 2。
从方向 1 开始，它锁定象限 3。
从方向 2 开始，它锁定象限 0。
从方向 3 开始，它锁定象限 1。
-- 死锁 --

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

Answer 2

我假设您的“最后象限”锁定顺序是它在穿过交叉点时看到的最后一个？

我认为您可以更改算法以始终按数字顺序锁定象限 - 如果有任何已锁定，则解锁并重试。汽车必须先锁定其完整路径，然后才能驶过十字路口并解锁。例如，如果一辆汽车想要从路径 1 行驶到 2，它将首先锁定象限 0，然后锁定象限 3。如果它想从路径 3 行驶到 1，那么它将首先锁定象限 2，然后锁定象限 3。

我认为这解决了死锁问题，因为每个线程都以相同的顺序锁定。当某人锁定 3 0 1 和某人锁定 1 2 3 时，就会发生死锁。

因此，完整的任务列表将是：

1. 它尝试按象限数字顺序 (0, 1, 2, 3) 锁定其路径。如果这是 C，那么我会使用 `pthread_mutex_trylock() 为每个象限加一个锁。
2. 如果它发现一个象限被锁定，它会解锁它锁定的象限，休眠一段随机时间，然后重新开始。
3. 如果它锁定了完整的路径，那么它就可以遍历该路径。
4. 一旦它穿过一个象限，它就可以安全地解锁它。它不必等到走出另一边才解锁。

正如您所提到的，它不能做的是锁定其第一个象限，进入该象限，然后尝试锁定路径中的下一个象限。在这种情况下，这会导致僵局或僵局。

Answer 3

我能够使用以下逻辑在 C 中实现解决方案（实际实现对每个象限使用信号量）。

我在问题中提到的解决方案部分正确，但是由于锁定的问题，我遇到了死锁。
我能够通过为锁分配优先级来解决这个问题。
通过首先锁定最高优先级的锁来获得锁。
以下是每辆车使用的伪代码算法：

假设：

1. 每个象限都有一个与其关联的锁。
2. 每个锁都有一个关联的优先级。优先顺序如下

优先级(Lock_0) <优先级(Lock_1) <优先级(Lock_2) <优先级(Lock_3)
*其中 Lock_x 是象限 x 的锁

*其中Lock_x是象限x 算法

1. 每辆车都会获得它将经过的象限列表

2. 从优先级最高的象限开始锁定每个象限。

   例如：在上面的示例中，来自方向 2 的车辆左转将锁定象限 2、象限 0，然后锁定象限 1 .

3. 穿过十字路口

4. 释放获取的锁。

   例如：在上面的示例中，锁以相同的顺序释放。 象限 2、象限 1 和象限 0

Answer 4

您实际上可能不需要信号量来实现解决方案。
问题并不是真正的资源控制（不需要锁定象限）
是关于资源调度的。

让我们假设运动/时间以离散的步骤发生

，以知道何时开始移动您的汽车，您必须预测象限是否会在您将来需要时使用。为此，当每辆车进入十字路口时，它应该描述它的意图..使用步骤队列..示例：

让我们有一个队列，每个象限有 1 行，

 T 1 2 3 4 5 6 7 8 9 
 0|
 1|
 2|
 3|

当汽车 1 来自底部时（2）他将使用（象限：2 1 0) 所以他保留 如果 2号

 T 1 2 3 4 5 6 7 8 9 
 0|    1
 1|  1 
 2|1
 3|

车在刻度 2 上从右侧出现并想要前进（Q：1 0），

 T 1 2 3 4 5 6 7 8 9 
 0|   2*1
 1| 2*1 
 2|1
 3|

我们就会发生碰撞，因此每辆车只有在它需要的所有象限都为空时才尝试标记其意图。如果没有，它会将意图滑动 1 帧并重试。在这种情况下，

 T 1 2 3 4 5 6 7 8 9 
 0|    1 2
 1|  1 2
 2|1
 3|

如果没有发生冲突，如果汽车 3 在时间帧 2 从顶部到达，则汽车 2 的时间表将是，可以尽快安排运动(0) 并且想要走到底部（Q：0 3）他可以立即开始。因为当他需要使用它时，它作为意图使用的象限不会被占用，

 T 1 2 3 4 5 6 7 8 9 
 0|  3 1 2
 1|  1 2
 2|1
 3|    3

这是一般方法..具体实施时会有变化..
如果您有线程（每辆车一个），您可能需要同步它们对队列的访问。但这只是同步数据访问而不是交叉路口逻辑

，并且如果运动步骤不是离散的单位，队列帧必须代表 X 秒的动画。