Простой пример - 7


Для процесса 2 можно сделать аналогичное замечание.

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

Во второй части доказательства необходимо показать, что в случае сомнения, какому из двух процессов первым войти в критический интервал, выяснение этого вопроса не может откладываться до бесконечности. Теперь мы обратим внимание на целочисленную переменную "очередь": замечаем, что присваивание значения этой переменной происходит только при окончании критических интервалов (или по окончании некоторых их частей), поэтому можно считать переменную "очередь" константой во время принятия решения о том, кому войти в критический интервал. Предположим, что "очередь = 1". Тогда процесс 1 может только циклиться через метку L1 (при этом "с1 = 0") и только до тех пор, пока он находит, что "с2 = 0". Но если "очередь = 1", то процесс 2 может циклиться только через В2, а это состояние процесса 2 означает, что "с2 = 1", поэтому процесс 1 не может циклиться и непременно попадает в свой критический интервал. Для случая "очередь = 2" применяется симметричное (относительно процессов и переменных) рассуждение.

В третьей и заключительной части доказательства мы отмечаем, что остановка, скажем процесса 1 в "остатке цикла 1", не препятствует продвижению процесса 2: тогда справедливо соотношение "с1 = 1", и процесс 2 может входить в свой критический интервал совершенно независимо от текущего значения переменной "очередь". Этим завершается доказательство корректности решения Деккера. Тех читателей, которые не оценили изобретательности этого решения, я прошу учесть, что для них уже была подготовлена почва из тщательно подобранных мною и затем отвергнутых, как непригодные, решений.




Начало  Назад  Вперед