Вопрос 2: Способы реализации взаимного исключения. Вариант с жесткой синхронизацией, его недостатки.

Вопрос 2: Способы реализации взаимного исключения. Вариант с жесткой синхронизацией, его недостатки.

Способы реализации взаимного исключения

Будем предполагать, что система циклических потоков для проблемы критической секции имеет следующие программные формы:

Здесь управляющая конструкция parbegin... parend используется для указания на то, что часть программы, заключенная между этими операторами, должна выполняться параллельно. Через идентификатор CS с номером обозначены критические секции каждого потока, program_1, program_2, …, program_n представляют собой те части потоков, которые не обращаются к общим данным и могут работать параллельно без каких бы то ни было ограничений.

Вариант с жесткой синхронизацией, его недостатки.

Самый простой и самый неэффективный способ обеспечения взаимного исключения состоит в том, что ОС позволяет потоку запрещать любые прерывания на время его нахождения в критической секции. Но доверять управление системой пользовательскому потоку опасно – он может надолго занять процессор, а при крахе потока в критической секции крах потерпит вся система, т. к. прерывания никогда не будут разрешены.

Получить полный текст

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

· Поток, нормально работающий вне своей КС, не должен блокировать другой поток при вхождении последнего в свою КС.

· Два потока, готовые войти в свои КС, не должны откладывать неопределённо долго решение вопроса о том, который из них войдёт в свою КС первым.

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

1)Проблема решается легко, если потребовать, чтобы потоки входили в свои КС попеременно. Одна общая переменная может хранить указатель на то, чья очередь войти в КС. Рассмотрим программную реализацию этого варианта (назовем его вариант 1).

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

Возможные неприятности: если первый из потоков гораздо медленнее другого, такое решение будет неэффективным. Может возникнуть ситуация, когда поток 2, выполнив работу в своей КС, передаст очередь первому потоку, затем выполнит действия вне своей КС и снова начнёт на неё претендовать, а тот ещё даже не соберется заходить в КС. Тем самым он блокирует второй поток по первому типу, хотя программа и не может оказаться в состоянии полного тупика. Если же один из процессов завершится раньше другого, то второй вообще окажется не в состоянии продолжить выполнение. В рассмотренном примере мы имеем дело с жесткой синхронизацией.

2)Во второй версии программы делается попытка устранить указанные недостатки путём введения двух общих переменных CS1_in, CS2_in – флагов, которые будут указывать на то, находится ли каждый поток внутри своей критической секции. При такой организации более быстрый поток может несколько раз подряд войти в свой критический интервал, если другому потоку это пока не нужно. Рассмотрим текст программы.

В данном варианте process_1 остается в состоянии активного ожидания до тех пор, пока CS2_in имеет значение "истина". Когда process_2 выйдет из своего критического участка, он выполняет собственный код "выход взаимоисключения", устанавливая для переменной CS2_in значение "ложь". После этого process_1 устанавливает для переменной CS1_in значение "истина" и входит в свой критический участок. Недостатки предыдущего варианта здесь устранены, взаимное блокирование теперь невозможно, но зато оба процесса могут оба одновременно начать выполнять свои входные последовательности взаимоисключения.

Пусть первый процесс проверил переменную CS2_in и обнаружил, что она имеет значение "ложь", но изменить значение своей переменной CS1_in не успел, в то время как второй процесс проделал то же самое. Тогда в результате выполненных проверок они оба одновременно войдут в свои критические интервалы, так что программа данной версии не гарантирует взаимного исключения.

Существует ещё ряд вариантов взаимоисключения, но все они не свободны от недостатков.

3)Рассмотрим алгоритм реализации взаимоисключения, предложенный Деккером. Он не требует никаких специальных аппаратно-реализованных команд и позволяет избежать недостатков рассмотренных алгоритмов.

В этом алгоритме каждому из процессов соответствует логическая переменная, принимающая значение "истина", если этот процесс претендует на вход в критический интервал. Переменная turn принимает значения, соответствующие номеру выбранного на выполнение процесса.

Рассмотрим, как работает такой вариант. Первый процесс сообщает о своём желании войти в критическую секцию, устанавливая свой флаг (p1_wants_to_come:=true). Затем он переходит к циклу, в котором проверяет, не хочет ли и другой процесс войти в свою критическую секцию, т. е. каково значение переменной p2_wants_to_come. Если нет (переменная имеет значение "ложь"), то он пропускает тело цикла ожидания и успешно входит в свою критическую секцию. Если же первый процесс обнаруживает, что флаг второго процесса тоже установлен, то он входит в цикл ожидания. Здесь он проверяет, какой процесс выбран – анализирует значение переменной turn. Если turn=1, т. е. его очередь выполняться, он пропускает тело своего цикла и снова выполняет цикл проверки в ожидании того момента, когда второй процесс сбросит свой флаг. Если же выбран второй процесс (turn=2), то первый процесс сбрасывает свой флаг и блокируется в цикле ожидания, пока избранным остается второй процесс. Сбрасыванием своего флага он даёт возможность второму процессу войти в свой критический интервал.

Со временем второй процесс выйдет из критической секции и выполнит свой код "выход взаимоисключения" – отдаст приоритет первому процессу и сбросит свой флаг. Теперь у первого процесса появляется возможность выйти из внутреннего цикла ожидания и снова установить собственный флаг. Затем он выполняет внешний цикл проверки. Если флаг второго процесса по-прежнему сброшен, первый успешно входит в свою критическую секцию. Если же второй процесс успел снова выразить желание попасть в критическую секцию и поднял свой флаг, то первому придется войти в тело внешнего цикла проверки, убедиться в своем преимущественном праве на выполнение и подождать, пока второй процесс откажется от входа и сбросит флаг.

Предложенный алгоритм представляет собой программное решение проблемы взаимоисключения. В нём решены как проблема взаимодействия потоков с разными скоростями, так и проблемы бесконечного откладывания и взаимного выполнения. Существуют и способы аппаратного решения

Недостатком алгоритма Деккера является то, что во время нахождения одного из процессов в критической секции, другой впустую циклится и проверяет общие переменные, вызывая общее замедление системы и не выполняя при этом никакой полезной работы.

Вопрос 3: Пусть имеются три процесса X, Y, Z и три ресурса: P1 –устройство ввода, P2 – устройство печати, P3 – диск. Процесс X требует ресурсы P1 и P2, процесс Y – P2 и P3, процесс Z – P1 и P3. Скорости процессов различны. Процессы переходят из активного состояния в пассивное произвольным образом. Решить задачу синхронизации процессов с помощью семафоров.

Для каждого устройства (P1,P2,P3) создается отдельный семафор. В случае если процесс потребует устройство занятое другим процессом, он будет заблокирован до тех пор, пока устройство не освободится.

⇐ Предыдущая 1 2 34