Средства синхронизации процессов

Проблема синхронизации

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

Проблему синхронизации иллюстрирует пример, взаимодействия процессов с печатающим устройством. (см. рис. 4.3). На печатающее устройство в порядке очереди выводятся файлы, имена которых занесены в специальный файл, представляющий собой очередь печати. Переменная NEXT, доступная всем процессам, содержит номер первой свободной позиции очереди печати. Процессы, желающие произвести печать, читают эту переменную, записывают в соответствующую позицию очереди печати имя необходимого файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT (например, равное пяти). Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, в следствие исчерпания кванта времени). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в пятую позицию имя своего файла и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию пять, поверх имени файла процесса S (указанную последовательность действий можно записать в виде стадий: R1-S1-S2-S3-R2-R3).

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

Критическая секция

Важным понятием синхронизации процессов является понятие «критическая секция» программы. Критическая секция – это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением.

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

Другим способом является использование блокирующих переменных. В этом случае с каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен, и значение 0, если ресурс занят. На рис. 4.4 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к разделяемому ресурсу D блокирующую переменную F(D). Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.

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

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

В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно можно назвать WAIT(x) и POST(x), где x – идентификатор некоторого события. В этом случае, если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ. В этом случае блокирующая переменная является частным случаем семафоров (в общем случае семафор может принимать не только значения 0 или 1).

Достоинство синхронизации на основе аппарата событий – отсутствие активного ожидания представления ресурса.

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

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

Управление памятью

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

Типы адресов

Для идентификации переменных и команд используются символьные имена (метки), виртуальные адреса и физические адреса (см. рис. 4.5).

Символьные имена присваивает пользователь при написании программы на алгоритмическом языке или ассемблере.

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

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

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