Синхронизация
Для процессов, совместно выполняющих общую работу, недостаточно того, что они взаимно исключают друг друга при работе с разделяемыми переменными; им необходимо еще передавать друг другу информацию. Минимальной единицей передаваемой информации является простой временной сигнал. Основное требование в этом случае состоит в том, что процессу предоставляется возможность ждать, пока другой не сообщит ему о свершении определенного события. Первый процесс ждет свершение нужного события, выполнив ЖДАТЬ (событие); второй сигнализирует о свершении,, выполняя СВЕРШИТЬ (событие). Прежде чем обсуждать реализацию ЖДАТЬ и СВЕРШИТЬ, рассмотрим, как и можно использовать для синхронизации двух процессов.
В качестве первого примера возьмем пару процессов, производитель и потребитель. Первый производит записи по одной за один раз, а последний использует их по одной за один раз. Произведенная, но еще не востребованная запись помещается в буфер размером в одну запись. Поэтому процессы должны быть синхронизированы таким образом чтобы между любыми двумя последовательными записями в буфер выполнялось в точности одно чтение, и наоборот.
Рис.2.12. Программы Производитель - Потребитель с одним буфером а синхронизацией по событиям; (а) - исполнение процессов, (б) - определение процессов.
Для обеспечения такого чередования программа, приведенная на рис. 2.12, использует синхронизирующие примитивные операторы ЖДАТЬ и СВЕРШИТЬ. Производитель пишет первую запись и свершает событие начало, которое позволяет потребителю начать ее обработку. Аналогично потребитель читает i-ю запись и свершает событие конец, что позволяет производителю записать в буфер (i+1)-ю запись. Специально предусматривать взаимное исключение при доступе к буферу незачем, так как в данном случае оно обеспечивается синхронизацией.
Описанную синхронизацию можно реализовать, используя в качестве каждого события двоичный семафор, операцию P - вместо ЖДАТЬ и операцию V - вместо СВЕРШИТЬ. Соответствующие программы приведены на рис. 2.13. Другой вариант предложен на рис. 2.14. В этом примере производство записи явно отделено от ее записи в буфер, а ее потребление от чтения из буфера. Синхронизуются только запись и чтение. Заметим, что в этой версии переменная конец, должна иметь начальное значение 1, а не 0.
В следующем примере производитель и потребитель пользуются буфером большого размера, который представляет собой бесконечную очередь. Как только производитель подготовит запись, он добавляет ее в конец очереди. Как только потребитель готов использовать запись, он берет первую запись из начала очереди. Здесь синхронизация нужна для того, чтобы потребитель не пытался прочесть запись из пустой очереди. Очевидно, что для этого необходимо хранить информацию о числе записей в очереди. Первая попытка приведена на рис. 2.15, где число (первоначально равное 0) является текущим числом записей, находящихся в буфере.
Рис.2.13. Программы Производитель - Потребитель с одним буфером и двоичным семафором; (а) - исполнение процессов, (б) - определение процессов.
Используется только одно, а не два события, так как производитель может добавлять запись в бесконечную очередь в любой момент. К сожалению, эта программа неверна по двум причинам Очевидно, что разделяемая переменная число должна быть защищена от одновременного доступа. Другой ошибкой является отсутствие задержки процесса производителя, что позволяет обоим процессам обращаться к указателям очереди одновременно со всеми вытекающими отсюда последствиями. Необходимые взаимные исключения введены во второй вариант программы, представленный на рис. 2.16, где предполагается, что ЖДАТЬ и СВЕРШИТЬ являются критическими интервалами по отношению к числу. Все действия с событием число выполняются в этих критических интервалах.
Рис.2.14. Вариант программ Производитель - Потребитель с одним буфером; (а) - исполнение процессов, (б) - определение процессов.
Более сложные формы ЖДАТЬ и СВЕРШИТЬ можно реализовать, используя операции Р и V, обобщенные для работы с числовым, семафором, который может принимать любое неотрицательное целочисленное значение. Обобщенные P и V операции определяются следующим образом.
Рис.2.15. Первый вариант программ Потребитель - Производитель с буфером, организованным в виде очереди; (а) - исполнение процессов. (б) - определение процессов.
При числовых семафорах и операциях Р и V , определенных таким образом, первоначальное значение семафора определяет количество процессов, которые могут пройти семафор (при отсутствии операций V над ним) прежде, чем семафор станет равным 0 и заблокирует последующие процессы. Используя число как числовой семафор, можно написать программу (рис. 2.17), которая реализует пару потребитель-производитель и использует буфер, являющийся
Рис. 2.16. Программы Производитель - Потребитель с буфером, организованным в виде очереди, и с синхронизацией по событию; (а) - исполнение процессов, (б) - определение процессов.
очередью. Семафор взаимискл можно с одинаковым успехом считать как двоичным, так и числовым.
Рис.2.17. Программы Производитель - Потребитель с буфером, организованным в виде очереди, и с числовыми семафорами; (а) - исполнение процессов, (б) - определение процессов.
В третьем примере используется ограниченный буфер. Этот буфер независимо от того, как он реализован, в виде очереди или как-нибудь иначе, состоит из n записей. Возникает необходимость предотвратить не только чтение из
Рис.2.18. Программы Производитель - Потребитель с ограниченным буфером и числовыми семафорами; (a) - исполнение процессов, (б) - определение процессов.
пустого буфера, но и запись в полный буфер. Для этого используется два числовых семафора: пустой, который задает число пустых позиций в буфере, и полный, определяющий число занятых позиций. Соответствующая программа приведена на рис. 2.18. Рассмотрим еще одну пару определений операций Р и V
При таком определении числовые семафоры могут принимать отрицательные значения, которые можно интерпретировать следующим образом. Если s отрицательно, то – s - это число процессов, заблокированных по s. Можно показать, что такая интерпретация числовых семафоров полностью эквивалентна первой.
Важный и интересный вопрос синхронизации возникает в хорошо известной задаче читателей и писателей. Два класса процессов имеют доступ к некоторому ресурсу. Процессы первого класса должны иметь монопольный доступ к ресурсу. Процессы второго класса могут обращаться к данному ресурсу параллельно с любым числом процессов этого же
Рис.2.19. Читатели и писатели; (а) - исполнение процессов, (б) - определение процессов.
класса. Примером может служить система резервирования авиабилетов. Процессы первого класса при резервировании места пишут в запись рейс. Процессы второго класса читают из записи рейс, когда осуществляется поиск свободных мест, выдают список пассажиров или проверяют расписание. Решение задачи читателей и писателей, приведено на рис.2.19. Доступ к разделяемым ресурсам осуществляется через семафор w. Если ресурс не используется, то первый появившийся процесс при входе в критический интервал выполнит P(w) и закроет семафор. Если процесс является читателем, то переменная счетчикчитателей будет увеличена и последующие читатели будут обращаться к ресурсу, не проверяя w. Последний читатель, покидающий критический интервал, является единственным, кто должен выполнить V{w) и открыть семафор. Чтобы гарантировать, что в данный момент времени только один читатель или один писатель может войти в критический интервал, используется семафор взаимискл, который защищает и счетчикчитателей, и выполнение читателями Р(w) и V(w).
Если в критическом интервале находится писатель, то о w может быть заблокирован только один читатель, все остальные будут блокироваться по взаимискл. Другие писатели блокируются по w. Когда писатель выполняет V(w), не ясно, кто именно, читатель или писатель, ожидающий w, войдет в критический интервал. Чтобы гарантировать, что читатель получит самую свежую информацию, можно придать ожидающим писателям более высокий приоритет, чем ожидающим читателям. Это можно было бы выполнить с помощью соответствующей дисциплины управления списком ожидающих процессов. Так как дисциплина, которая подходит для одной задачи синхронизации, может не подойти для другой, то этот подход потребовал бы введения различных вариантов операций Р и V. В таком подходе есть два недостатка. Первый-это усложнение операционной системы. Второй-увеличение нагрузки на программиста, от которого потребовалось бы знание большого числа синхронизирующих примитивных операторов, выбор подходящих и проверка правильности их использования. Более предпочтительным является подход, при котором полнее используются примитивные операторы Р и V, например подход, требующий, чтобы процесс прошел один семафор, прежде чем ему позволят проверить второй. Фактически с использованием операций Р и V над числовыми семафорами могут быть решены произвольные задачи синхронизации.
Операции P(s) и V(s), имеющие доступ к одному и тому же семафору, сами должны быть реализованы в виде критических интервалов, чтобы операция V не происходила между проверкой семафора и блокированием процесса. Каждая должна выполняться неделимо, и в данный момент времени инициировать выполнение какой-нибудь из этих операций может только один параллельный процесс. Таким образом, любой критический интервал пользователей реализуется посредством пары более простых критических интервалов, обеспечиваемых системой. Оба члена этой пары присутствует только в одном экземпляре в ядре операционной системы, где они используют критические интервалы более низких уровней вплоть до неделимых операций над памятью.
Если, как предполагалось, имеется только один процессор, то операции Р и V реализуются как критический интервал с помощью простого запрета прерываний. Семафор s можно реализовать в виде записи с двумя полями. В одном поле хранится целое значение s , во втором - указатель на список процессов, заблокированных поs. На рис.2.20 показана реализация Р и V для числового семафора, который может принимать отрицательные значения.
Рис.2.20. Реализация операций Р и V на однопроцессорной ЭВМ.
Некоторые операционные системы обеспечивают монопольный доступ к ресурсам с. помощью операций запроса ресурса ENQ (enqueue - поставить в очередь) и его освобождения DEQ (dequeue -убрать из очереди). В наиболее простом варианте ENQ приводит к выделению ресурса, если он свободен; а в противном случае процесс, выдавший запрос, блокируется и ставится очередь к этому ресурсу. Операция DEQ приводит к тому, что ресурс выделяется первому процессу в списке, а если список пуст, то ресурс остается свободным. Другие варианты этих операций дают возможность одновременно запрашивать несколько ресурсов, требовать разделяемый доступ, отказываться от запроса, если ресурсов нет в наличии. Многие операционные системы предоставляют специальные средства управления совместным доступом к файлам.
