Составители:
Если же осутствует операция FA, но есть инструкция недели-
мого увеличения, то протокол входа может иметь вид
turn[i] = number; < number = number + 1; > .
В последнем случае недостаток состоит в том, что хотя переменная
number будет увеличиваться правильно, но процессы могут не полу-
чить уникальных номеров: например, каждый из процессов может
выполнять первое присваивание примерно в одно и то же время и,
таким образом, получить один номер. Таким образом, важно, что-
бы оба присваивания выпол нялис ь в одном неделимом действии.
Можно воспользоваться общим подходом создания критиче -
ской секции. Пусть CSenter — протокол входа, CSexit — прото-
кол выхода из критической секции, рассмотренные ранее. Тогда
инструкцию FA можно заменить последовательностью
CSenter; turn[i] = number; number = number + 1; CSexit;
Такой подход на практике уд овлетворите лен , если доступна ин-
струкция типа “проверить–установить”; однако, при этом процессы
получают номер а не всегда в том порядке, в котором они пытаются
это сделать, и теоретич еск и процесс может зациклиться навсегда.
Но с большой вероятностью каждый процесс получит свой номер,
и большинство процессов получит номера по порядку.
§8 Справедливое планирование без
использования специальных инструкций
Предыдущий алгоритм можно легко реализовать на машинах, име-
ющих неделимую операцию “извлечь и сложить”. Если такой опер а-
ции нет, то п риход ится использовать еще один протокол критиче-
ской се кци и, но это может нарушить справедливость алгоритма.
По алгоритму билета, посетитель получает уникальный номер
и ждет, пока подойдет его очередь. В отличие от упомянутого алго-
ритма, в котором посетители сверяют свои номера с общим счет-
чиком, здесь посетители сверяются друг с другом.
Предположим, что turn[1 : n] — массив целых чисел, инициа-
лизированный нулями. Для входа в критическую секцию процесс
56
Страницы
- « первая
- ‹ предыдущая
- …
- 53
- 54
- 55
- 56
- 57
- …
- следующая ›
- последняя »
