Моделирование пересечения трафика с использованием многопоточного алгоритма

Question

Это вопрос интервью, который был задан и хотел найти эффективное решение.

Проблема

Рассмотрим пересечение четырех дорог, как показано на схеме. У каждой дороги определено направление. Как бы вы решили проблему, чтобы улучшить состояние трафика и , чтобы избежать взаимных блокировок .

1. пересечение разделено на четыре квадранта [показано желтым цветом].
2. Автомобили беспрепятственно въезжают на перекресток с четырех направлений [0,1,2,3]
3. На перекрестке каждая машина может сделать один ход. три возможных хода
   1. Идите налево
   2. Идите прямо
   3. Идите направо

Например:

, если автомобиль въезжает с направления 2 и хочет повернуть налево. это должно пройти через Quandrant 2 , Quandrant 1 и, наконец, Quandrant 0

Полукомплектное решение

Каждый квадрант , отмеченный желтым, имеет связанный с ним семафор. Я представлял себе двухфазный протокол, в котором каждая машина будет

1. получить список квадрантов, через которые он пройдет
2. блокировка каждого из квадрантов, начиная с последнего квадранта
   3. В приведенном выше примере автомобиль с направления 2 заблокирует квадрант 0 , квадрант 1 и затем квадрант 2 .
3. Перемещение через перекресток
4. Освободить приобретенные замки.
   3. Замки открываются в том же порядке. квадрант 0 , квадрант 1 и квадрант 2

Однако приведенное выше решение не является оптимальным, поскольку приводит к тупику.

Мой вопрос

1. Каким другим / лучшим способом это может быть достигнуто?
2. Могу ли я реализовать это, используя семафор в C?
   2. Если нет, то на какой метод синхронизации я должен смотреть?

Обновление

1. Мне нужно решение, позволяющее нескольким вагонам въезжать на перекресток и по-прежнему избегать взаимоблокировок и столкновений. Наличие единой блокировки на всем перекрестке будет меньше, чем оптимизировано.

Answer 1

Ваше решение (как предложено в шаге 2) не избегает тупика.

Рассмотрим случай, когда с четырех улиц появляются машины, желающие повернуть налево. Затем все машины начинают блокировать разные cuadrants:

с направления 0, блокирует кубрант 2. со стороны 1 он блокирует кубрант 3. со стороны 2 блокирует cuadrant 0. со стороны 3 он блокирует cuadrant 1. - тупик -

Вы можете избежать тупика, если мьютекс будет разделен на четыре направления.

Answer 2

Мне удалось реализовать решение в C, используя следующую логику (Реальная реализация использовала семафоры для каждого квадранта).

Решение, о котором я упоминал в вопросе, было частично правильным, однако у меня возникла тупиковая ситуацияиз-за того, в чем были сделаны замки.Я смог решить эту проблему, назначив приоритет замкам.Блокировки получаются блокировкой блокировки с наивысшим приоритетом.Ниже приведен алгоритм псевдокода, используемый каждым автомобилем:

Допущения:

1. С каждым квадрантом связана блокировка.
2. Каждый замок имеет связанный приоритет.Приоритеты следующие:

Приоритет (Lock_0) <Приоритет (Lock_1) <Приоритет (Lock_2) <Приоритет (Lock_3) </strong>
*, где Lock_x - этоБлокировка для квадранта x

Алгоритм

1. Каждая машина получает список квадрантов, через которые она будет проходить

2. Блокировка каждогоиз квадрантов, начиная с квадранта с наивысшим приоритетом.

   Например: в приведенном выше примере автомобиль с направления 2, поворачивающий влево, заблокирует квадрант 2 , квадрант 0 а затем квадрант 1 .

3. Пройдите через перекресток

4. Снимите полученные блокировки.

   Например: в приведенном выше примере блокировки открываются в том же порядке. сектор 2 , сектор 1 и сектор 0

Answer 3

Возможно, вам не нужны семафоры для реализации решения. Проблема не в контроле ресурсов (не нужно блокировать квадранты), а в планировании ресурсов.

Давайте предположим, что движение / время происходит вдискретные шаги

, чтобы узнать, когда начать движение вашего автомобиля, вы должны предсказать, будет ли использоваться квадрант, когда он понадобится вам в будущем ... для этого, поскольку каждый автомобиль попадает на перекрестокдолжен описать свое намерение .. используя очередь шагов .. пример:

позволяет иметь очередь с 1 строкой для каждого квадранта

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

, когда автомобиль 1 идет снизу (2)он будет использовать (Quadrants: 2 1 0), поэтому он резервирует квадранты

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

, если автомобиль № 2 идет справа на тике 2 и хочет двигаться вперед (Q: 1)

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

у нас происходит авария, поэтому каждая машина будет пытаться пометить намерение только в том случае, если все квадранты, в которых она нуждается, пустые ... если нет, то она сдвинет намерение на 1 кадр и попытается снова ... в этом случаерасписаниеДля автомобиля 2 будет

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

, если не возникнет конфликта, движение может быть запланировано как можно скорее, если автомобиль 3 выйдет во временном интервале 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 секунд анимации.

Answer 4

Я предполагаю, что ваш порядок блокировки "последнего квадранта" является последним, который он видит при движении по пересечению?

Я думаю, вы можете изменить свой алгоритм, чтобы всегда блокировать квадранты в числовом порядке - разблокировка, если естьуже заблокирован и повторите попытку.Автомобиль должен был заблокировать свой полный путь, прежде чем проехать через перекресток и отпереть.Например, если автомобиль хочет перейти с пути 1 на 2, он заблокирует первый квадрант 0, а затем 3. Если он хочет перейти с пути 3 на 1, он заблокирует сначала 2, а затем 3.

Я думаю, что это решает проблему взаимоблокировки, потому что каждый поток блокируется в том же порядке.Использование вашего тупика происходит, когда кто-то блокирует 3 0 1, а кто-то, когда кто-то блокирует 1 2 3.

Таким образом, полный список задач будет выглядеть так:

1. Он пытается заблокировать свой путь вчисловой порядок квадрантов (0, 1, 2, 3).Если это C, то я бы использовал `pthread_mutex_trylock() с блокировкой для каждого квадранта.
2. Если он обнаружит, что квадрант заблокирован, он разблокирует заблокированные, спит случайное количество времени и запускаетсяover.
3. Если он блокирует свой полный путь, он может пройти по нему.
4. После прохождения через квадрант он может безопасно разблокировать его.Не нужно ждать, чтобы выйти на другую сторону, прежде чем он разблокируется.

Как вы упоминаете, он не может заблокировать свой первый квадрант, ввести этот квадрант и затем попытаться заблокироватьследующий в пути.В этом случае это может привести к тупику или тупику.