Синхронизация N процессов с использованием семафора - условие гонки - PullRequest
Новая
       39

Синхронизация N процессов с использованием семафора - условие гонки

0 голосов
/ 24 ноября 2018

Я пытаюсь упорядочить N процессов, используя только семафоры (без мьютекса).

P1 -> P2 -> P3 -> ... -> Pn

Я занимаюсь этой проблемой:

, если вы звоните: 

s = 1;

P1 {
wait(s1)
...
signal(s1)
}

P2 {
wait(s1)
...
signal(s1)
}

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

Буду также признателен за любые предложения о том, как решить проблему такого рода (синхронизация N процессов) ТОЛЬКО с использованием семафоров, без использования N семафоров, я прочитал, что возможный минимум равен 3.

Спасибо.

1 Ответ

0 голосов
/ 25 ноября 2018

Вот несколько вариантов.Поскольку вы всегда вызываете signal, за которым сразу следует wait, опция рутины, вероятно, является лучшей.У вас нет распараллеливаемого кода, поэтому вы не сможете извлечь пользу из обычных потоковТакже будет полезно узнать, как избежать необходимости синхронизации.

  • Вы можете использовать более одного семафора.Там, где каждый поток явно передает управление следующему.

  • Вы можете иметь переменную Whose-turn-is-next.Получив блокировку, поток проверит, настала ли его очередь, если нет, то освободит блокировку.Это может привести к вращению, ничего не делая.Поэтому мы должны добавить еще одну блокировку.После проверки мы подождем, пока еще одна блокировка не завершится.Это будет освобождено после того, как поток проделал некоторую работу.Теперь темы не вращаются.Однако каждый раз, когда поток завершается, каждый другой поток проверяет, является ли он следующим.

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

Это не шаблон или анти-шаблон, просто примечание

  • В Unix поток в конечном итоге будет отложен, если он перегружает процессор и есть другие готовые к работе потоки.

Лучшие способы сделать это.

  • Избегайте необходимости синхронизации:
    (см. https://www.youtube.com/watch?v=2yXtZ8x7TXw) Если вы не используете изменяемые переменные, тогда параллелизм прост, и синхронизация не требуется.

  • Рассмотрим каналы и фильтры: в этом шаблоне потоки могут обмениваться данными через канал (fifo). Для этого вы можете использовать минимальный блокирующий циклический буфер (просто убедитесь, что вы помещаете в буфер только неизменяемые данные). | В Unixes(например, Gnu / Linux), вы можете использовать каналы и процессы. Вы можете сделать все это в одной программе, используя fork. Или вы можете соединить несколько программ вместе (bash - хороший инструмент для этого).

  • Рассмотрим микропотоки / подпрограммы / кооперативные потоки:
    Иногда полезно написать программу с несколькими независимыми потоками.Но если ваши потоки не тратят значительное количество времени на одновременную работу (например, потому что вы всегда вызываете signal; wait), тогда вам не нужны потоки.И потоки создают значительную сложность кода.Поэтому используйте сопрограммы (или как они там называются в вашей системе), они позволяют вам написать несколько подпрограмм для независимого планирования, но управление будет передано другой подпрограмме только при вызове yield (аналогичноВызов signal; wait, но механизм предпочтет передать следующую подпрограмму на ринге.

...