基于多线程算法的交通交叉口仿真

Question

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

问题

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

1. 将交叉口划分为四个象限，显示为黄色，
2. 汽车从交叉口的四个方向随机进入交叉口，1，2，3
3. 在交叉口，每辆汽车都可以进行一次移动。这三种可能的移动方式是
   1. Go左侧
   2. 直行
   3. Go Go

​

例如：

如果一辆车从方向进入2并想左转。它应该通过quandrant 2，quandrant 1，最后是quandrant 0。

​

​

半完全解

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

从上一个象限开始，从最后一个象限开始，从上面的示例中，从

1. 得到的象限列表中的每个象限都会锁定象限0<代码>E 242，<代码>E 143象限1<代码>E 244然后e 145象限>象限>。

​

锁所获得的intersection

• Release通过

1. 。
   1. 锁按相同的顺序释放。象限0，quandrant 1和quandrant

​

然而，上面的解决方案并不是最优的，因为它会导致死锁。

我的问题是

achieved?

• Can --我用C？

1. 中的信号量来实现它，如果不是，我应该看at?

的同步方法。

​

更新

1. I需要一种解决方案，允许多辆汽车进入交叉口，同时仍然可以避免死锁，以及collision.Having，整个交叉口上的单一锁都没有经过优化。

Answer 1

我能够使用以下逻辑在C中实现一个解决方案(实际实现使用了每个象限的信号量)。

我在问题中提到的解决方案是部分正确的，但是由于锁的创建问题，我正处于死锁状态。我能够通过分配锁的优先级来解决这个问题。锁是通过先锁定最高优先级的锁来获得的。以下是每个car使用的伪码算法：

假设：

1. 每个象限都有一个与它相关的锁，
2. 每个象限都有一个相关的优先级。优先级如下：

优先级(Lock_0)<优先级(Lock_1)<优先级(Lock_2)<优先级(Lock_3)

*其中Lock_x是象限x的锁

算法

1. 每辆车都会得到通过

的象限列表

1. 锁，每个象限从象限开始，具有最高优先级。

在上面的例子中，从2方向左转的汽车会锁定象限2，象限0，然后象限。

在intersection中移动

1. 释放获得的锁。

在上面的例子中，锁是按相同的顺序释放的。象限2，quandrant 1和quandrant

Answer 2

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

考虑一下，当从四条街有汽车想要向左拐的时候。然后，所有的汽车开始锁定不同的夸夸其谈：

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

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

Answer 3

我假设你的“最后一象限”锁定顺序是它在交叉路口移动时看到的最后一次锁定顺序？

我认为你可以改变你的算法，把象限按数字顺序锁定--解锁(如果有的话)已经锁定，然后重试。在驶过十字路口和解锁之前，这辆车必须锁上完整的路径。例如，如果一辆汽车想从路径1到2，它会锁定第一个象限0，然后是3，如果它想从路径3到1，那么它将首先锁定2，然后锁定3。

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

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

1. 试图以象限数字顺序锁定路径(0，1，2，3)。如果这是C，那么我会使用`pthread_mutex_trylock()对每个象限设置一个锁。
2. 如果发现一个象限被锁定了，就会解锁它锁定的象限，随机睡眠一段时间，然后重新开始。
3. ，如果它锁定了它的完整路径，那么它就可以遍历这条路径。
4. ，一旦它穿过象限，就可以安全地解锁。在打开锁之前，它不必等待从另一边出去。

正如你提到的，它不能做的是锁定它的第一个象限，进入那个象限，然后试图锁定下一个象限。在这种情况下，这将导致死锁或僵局。