Удовлетворяет ли мое решение требованиям взаимного исключения?

Я нашел решение проблемы взаимного исключения в Интернете, которое имеет два процесса P0 и P1. (Предположим, что переменная turn инициализирована до 0)

volatile int turn;

Процесс P0:

/* Other code */
  while (turn != 0) { } /* Do nothing and wait. */
  Critical Section /* . . . */
  turn = 1;
  /* Other code */

Процесс P1:

/*Other code*/
  while (turn != 1) { } /* Do nothing and wait. */
  Critical Section /* . . . */
  turn = 0;
  /* Other code */

Как это решение решает проблему взаимного исключения? Я не понимаю этого полностью.


java mutex mutual-exclusion
person Tia    schedule 04.11.2015    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Предполагая, что нет другого кода, который может установить turn в значение, отличное от 0 или 1, и предполагая, что единственное, что связано с переменной turn, - это P0 и P1, тогда это решает свойство взаимного исключения. В частности, вы говорите, что turn инициализируется равным 0. Это означает, что P1 не может войти в критическую секцию: он занят в цикле while (turn != 1) и останется в этом цикле, пока что-то не установит turn == 1. Учитывая наше предположение, что только P0 и P1 вносят изменения в turn, это означает, что P1 не может войти в критическую секцию, пока P0 не установит turn в 1. Таким образом, P0 немедленно выйдет из цикла while (turn != 0) (поскольку turn изначально равно 0) и безопасно войдет в критическую секцию. . Он знает, что P1 не может войти в свою критическую секцию, пока turn не будет установлено в 1, и это произойдет только после того, как P0 покинет свою критическую секцию. Как только P0 установит turn в 1, P0 застрянет в цикле while (turn != 0) до тех пор, пока P1 не освободит его, так что теперь P1 находится в своей критической секции, а P0 не может быть в ней. И так далее.

Самый простой способ представить это — два человека и дубинка. Каждый из них соглашается ничего не делать (входить в свою критическую секцию), если не держит эстафету. Таким образом, у Человека 1 сначала есть дубинка, и он может делать что угодно, зная, что Человек 2 ничего не может сделать - у него нет дубинки. Как только Человек 1 закончил, он передает эстафету Человеку 2. Человек 2 теперь свободен делать все, что хочет, и он знает, что Человек 1 ничего не делает, а только ждет, пока ему вернут жезл.

person Oliver Dain    schedule 04.11.2015
comment
Спасибо за объяснение с такой ясностью! :D Ты гений Оливер. - person Tia; 04.11.2015

arrow_upward
0
arrow_downward

Как указывает @JustinSteele, это определенно не решает проблему взаимного исключения. Возможно, если бы вы изменили очередь на логическое значение, вы могли бы получить грязное исправление, поскольку логическое значение состоит только из двух значений. Если вам нужен более правильный способ обеспечения взаимного исключения, я бы посоветовал взглянуть на мьютексы, семафоры и условные переменные. Удачи!

person Pieter van der Heijden    schedule 04.11.2015
comment
Оливер сделал предположение, что ходы могут быть либо 0, либо 1. Но да, извините, я не совсем понял! - person Tia; 04.11.2015

arrow_upward
0
arrow_downward

Если и P0, и P1 выполняются, и каждый из них выполняется только один раз, верно, что P0 войдет в критическую секцию первым, исключительно, прежде чем P1.

С точки зрения модели памяти Java эта программа корректно синхронизируется, потому что все действия между потоками являются непостоянными операциями чтения и записи. Поэтому программа последовательно непротиворечива, легко анализируется.

Или, точнее, все операции чтения и записи энергозависимых данных выполняются в общем порядке (это соответствует порядку программирования); этот порядок гарантирует взаимную исключительность критических секций.

Однако здесь есть серьезная проблема. Если P1 прибывает первым, он должен ждать P0, независимо от того, как поздно прибудет P0. Это довольно несправедливо. И, если P0 не выполняется, P1 не может продвигаться вперед. И, если P0 выполняется, а P1 нет, P0 не может снова войти в критическую секцию (он должен ждать, пока P1 сбросит ход). Этот механизм блокировки допускает только строгую последовательность P0-P1-P0-P1-... (если только это не требуется)

Для решения этой проблемы существуют алгоритм Деккера, алгоритм Петерсона и т.д. См. этот пост - https://cs.stackexchange.com/a/12632

person ZhongYu    schedule 04.11.2015