·  программа обработки завершения процесса;

·  программа управления ресурсами (перегрузка или недогрузка ресурсов).

Графическая интерпретация планирования и диспетчеризации представлена на рис. 9.

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

Рис. 9. Временная диаграмма взаимодействия "Диспетчера" и задач

4. Средства синхронизации и взаимодействия процессов

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

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

Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипрограммирования, может привести к их неправильной работе или даже к краху системы. Рассмотрим, например (рис. 10), программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл "заказов" другие программы. Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой для определенности предположим равным 4.

Рис. 10. Пример необходимости синхронизации

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

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

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

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

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

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

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

На рис. 12 приведена временная диаграмма исполнения команды "Проверить и установить".

POST(D)

Рис. 12. Временная диаграмма исполнения команды "Проверить и установить"

4.3. Синхронизация процессов на основе семафорных операций

Для устранения активного ожидания процесса CPU может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x – идентификатор некоторого события. На рис. 13 показан фрагмент алгоритма процесса, использующего эти функции.

Рис. 13. Реализация критических секций с использованием
системных функций WAIT(D) и POST(D)

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

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

Рассмотрим использование семафоров для взаимоисключения процессов.

4.3.1. Двоичный семафор

С каждым семафором связывается список процессов, ожидающих разрешения пройти семафор.

ОС может выполнить три действия над процессами:

1)  может назначить для исполнения готовый процесс;

2)  может заблокировать исполняющийся процесс и поместить его в список, связанный с конкретным семафором;

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

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

Замечание. Все CS должны быть одинаковы по длительности, поэтому чтобы упростить временные диаграммы здесь и далее применено сокращение
( ).

Рис.14. Временная диаграмма для двоичного семафора

Рис. 15. Временная диаграмма для двоичных семафоров (семафоры - S1 и S2).
Б – блокировано, СS1 и CS2 – критические участки 1 и 2,
идентифицированные семафорами S1 и S2.

Описание диаграммы двоичного семафора

До момента t 1 ресурс был не занят. В момент t 1 процесс Pr1, выполняет операцию P(S) и входит в критический участок (CS). В момент t2 процесс Pr2 выполняет операцию P(S) – занять ресурс, это приводит к изменению: S = –1 – означает, что Pr2 в состоянии блокирования.

В момент t 3 – конец критического участка для процесса Pr1. Выполняется операция V(S) – освободить, это приводит к увеличению значения S на единицу (т. е. S=0). Для процесса блокированного (Pr2) это сигнал на разблокировку и предоставления ему ресурса.

В момент t 4 процесс Pr2 освобождает ресурс, выполняется операция V(S), которая изменяет значение S на 1 (т. е. S=1).

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

4.3.2. Универсальный семафор (считающий семафор)

Универсальный семафор – это пара операций – примитив и аргумент-семафор, имеющий диапазон целых чисел.

Числовые семафоры могут принимать отрицательные значения: если S отрицательно, то |S| - это число процессов, заблокированных по S.

Алгоритмы исполнения операций P(S) и V(S)

На рис. 16 приведена диаграмма считающего семафора для пяти процессов, требующих один ресурс.

Рис. 16. Пример диаграммы считающего семафора
(1 ресурс, семафор - S, 5 процессов – Рг1¸Рг5)

4.4. Семафоры как счетчики ресурсов и синхронизаторы

Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. Процесс "писатель" должен приостанавливаться, когда все буфера оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, процесс "читатель" приостанавливается, когда все буферы пусты, и активизируется при появлении хотя бы одной записи. Введем два семафора: e – число пустых буферов и f – число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:

// Глобальные переменные

#define N 256

int e = N, f = 0, b = 1;

void Writer ()

{

while(1)

{

PrepareNextRecord(); /* подготовка новой записи */

P(e); /*Уменьшить число свободных буферов, если они есть, в противном случае - ждать, пока они
освободятся */

P(b); /* Вход в критическую секцию */

AddToBuffer(); /* Добавить новую запись в буфер */

V(b); /* Выход из критической секции */

V(f); /* Увеличить число занятых буферов */

}

}

void Reader ()

{

while(1)

{

P(f); /* Уменьшить число занятых буферов, если они
есть, в противном случае ждать, пока они
появятся */

P(b); /* Вход в критическую секцию */

GetFromBuffer(); /* Взять запись из буфера */

V(b); /* Выход из критической секции */

V(e); /* Увеличить число свободных буферов */

ProcessRecord(); /* Обработать запись */

}

}

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

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

В качестве примера возьмем пару процессов:

Pr1 – производитель;

Pr2 – потребитель.

Пусть Pr1 создает записи по одной за Dt, а Pr2 использует их по одной за Dt.

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

Pr1 – пишет i-ую (первую запись) в буфер и совершает событие – НАЧАЛО – это событие позволяет потребителю начать обработку записи.

Pr2 – читает i-ую запись из буфера и совершает событие – КОНЕЦ – это позволяет производителю (Pr1) записать в буфер i+1 запись.

Специально предусматривать взаимное исключение при доступе к буферу нет необходимости, т. к. в данном случае оно обеспечивается синхронизацией. Итак – семафор может быть синхронизатором, координирующим производство и потребление ресурсов. Процесс, потребляя ресурс, выполняет P-операцию над связанным с ресурсом семафором (т. е. Р(S)), что означает изменение значения S в меньшую сторону. Процесс производит ресурс, выполняя V(S)-операцию над тем же семафором.

4.4.1. Алгоритм "Производитель-Потребитель" с буфером на одну запись

Введем переменные (семафоры):

ПУСТО = 1 – сигнал для производителя "поместить в буфер запись"

ПОЛНО = 1 – сигнал для потребителя "читать запись"

Описание (определение) процессов "Производитель-Потребитель" с буфером на одну запись

Исполнение процессов "Производитель-Потребитель" с буфером на одну запись

GLB буфер (глобальная переменная)

Semaphore ПОЛНО, ПУСТО

ПОЛНО = 0

ПУСТО = 1

CO BEGIN (COrporation Begin)

CO{

Вызвать "Производитель";

Вызвать "Потребитель"

СО}

COEND

На рис. 17 представлена диаграмма алгоритма с буфером на одну запись.

Рис. 17. Временная диаграмма синхронизации процессов "Производитель-Потребитель"
с буфером на одну запись

4.4.2. Алгоритм "Производитель-Потребитель" с буфером
большого размера (бесконечным)

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

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

Исполнение процессов "Производитель-Потребитель" с буфером большого размера

GLB buffer

GLB namber(N)

N=0

CO{

Вызвать "Производитель"

Вызвать "Потребитель"

СО}

Описание процессов "Производитель-Потребитель" (MAKER-USER) с буфером большого размера

Свершить (doit(N)) и Ждать (wait(N)) – синхронизирующие примитивные операторы ядра ОС.

Этот алгоритм некорректен по 2 причинам:

·  разделяемая переменная (число (N)) должна быть защищена от одновременного доступа;

·  отсутствует задержка процесса-производителя, что позволяет обоим процессам обращаться к указателям очереди одновременно.

Второй вариант этого алгоритма.

Введем необходимые взаимные исключения. Предположим, что "ждать" и "свершить" являются CS по отношению к числу (N), тогда все действия, связанные с событием "число (N)", выполняются в этих критических участках.

Исполнение процессов "Производитель-Потребитель" с буфером большого размера (2-ой вариант)

GLB buffer <буфер>

GLB namber(N) <число>

SEMAPHORE (interexeption) <взаимоисключить>

N=0

CO{

Вызвать MAKER <производитель>

Вызвать USER <потребитель>

СО}

Возникает необходимость предотвратить не только чтение из пустого буфера, но и запись в полный буфер. Для этого используется 2 числовых семафора "НЕПОЛНО" и "НЕПУСТО", которые задают число пустых позиций в буфере и число занятых позиций.

Алгоритм исполнения процессов «Производитель-Потребитель» с буфером из фиксированного числа записей

N := 0;

«НЕПОЛНО» := 1;

«НЕПУСТО» := 0; начальные значения параметров

взаимоисключить := 1;

MAX

Описание процессов "Производитель-Потребитель" с буфером из фиксированного числа записей

4.5. Тупики

Приведенный пример в начале п. 4.4. может проиллюстрировать еще одну проблему синхронизации – взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками. Если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Действительно, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писателем".

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

Рис. 19. a) фрагменты программ А и В, разделяющих принтер и диск;
б) взаимная блокировка (клинч); в) очередь к разделяемому диску;
г) независимое использование ресурсов

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

Необходимые условия возникновения тупиковых ситуаций.

1.  Процессы требуют предоставления им права монопольного управления ресурсами, которые им предоставляются (условие взаимоисключения).

2.  Процессы удерживают за собой ресурсы, выделенные им, в то же время ожидают выделения дополнительных ресурсов (условие ожидания ресурсов).

3.  Ресурсы нельзя отобрать у процесса, удерживающего их, пока эти ресурсы не будут использованы для завершения работы (условия неперераспределенности).

Проблема тупиков включает в себя следующие задачи:

·  предотвращение тупиков;

·  распознавание тупиков;

·  восстановление системы после тупиков.

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

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4