Синхронизация процессов и потоков
В многозадачной ОС синхронизация процессов и потоков необходима для исключения конфликтных ситуаций при обмене данными между ними, разделении данных, доступе к процессору и устройствам ввода-вывода. Во многих ОС эти средства называются средствами межпроцессного взаимодействия (InterProcess Communications – IPC).
Выполнение потока в многозадачной среде имеет асинхронный характер, поэтому сложно сказать, на каком этапе выполнения будет находиться поток в определенный момент времени. Задача синхронизации заключается в согласовании скоростей потоков путем их приостановки до наступления некоторого события и последующей активизации при наступлении этого события.
Пренебрежение вопросами синхронизации процессов, выполняющихся в многозадачной системе, может привести к неправильной их работе или даже к краху системы.
Рассмотрим в качестве примера программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл "заказов" другие программы. В данном случае это процессы-клиенты R и S, содержащие операции R1, R2, R3 и S1, S2, S3 (рис. 4.8). Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой предположим равно 4. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, вследствие исчерпания кванта). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в четвертую позицию имя своего файла и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию 4, поверх имени файла процесса S. Таким образом, файл процесса S не будет напечатан.
Рис. 4.8. Доступ процессов к разделяемым данным
Можно представить и другое развитие событий: были потеряны файлы нескольких процессов или, напротив, не был потерян ни один файл. В данном случае все определяется взаимными скоростями процессов и моментами их прерывания. Сложность проблемы синхронизации состоит в нерегулярности возникающих ситуаций.
Ситуация, когда два или более процессов обрабатывают разделяемые данные, и конечный результат зависит от соотношения скоростей процессов, называется состоянием состязания или гонками.
Критическая секция
Важным понятием синхронизации потоков является понятие «критическая секция».
Критическая секция – это часть программы, которая должна выполняться без прерываний со стороны других потоков. Критическая секция всегда определяется по отношению к определенным критическим данным,при несогласованном изменении которых результат выполнения программы может быть непредсказуем. Во всех потоках, работающих с критическими данными, должна быть определена критическая секция, которая в общем случае состоит из разных последовательностей команд. Критическая секция, например, используется для предоставления доступа к разделяемым ресурсам ВС.
Чтобы исключить эффект гонок по отношению к разделяемым данным, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этими данными, находился только один поток. Этот прием называют взаимным исключением. При этом неважно, находится этот поток в активном или в приостановленном состоянии.
Для реализации взаимных исключений используются различные способы: запрещение прерываний, блокирующие переменные, семафоры, синхронизирующие объекты ОС, рассмотренные ниже.
Запрещение прерываний
Поток при входе в критическую секцию, запрещает все прерывания, а при выходе из критической секции снова их разрешает. Это самый простой, но и самый неэффективный способ, так как опасно доверять управление системой пользовательскому потоку, который может надолго занять процессор, а при крахе потока в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.
Блокирующие переменные
Для синхронизации потоков одного процесса программист может использовать глобальные блокирующие переменные, к которым все потоки процесса имеют прямой доступ.
С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рис. 4.9 показан фрагмент алгоритма потока, использующего для реализации взаимного исключения доступа к разделяемому ресурсу D блокирующую переменную F(D). Перед входом в критическую секцию поток проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) устанавливается в 0, и поток входит в критическую секцию. После того, как поток выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.
Рис. 4.9. Реализация критической секции с использованием
блокирующих переменных
Если все потоки написаны с использованием вышеописанных соглашений, то взаимное исключение гарантируется. При этом они могут быть прерваны ОС в любой момент и в любом месте. Однако, одно ограничение на прерывания все же имеется – операция проверки и установки блокирующей переменной должна быть неделимой. Для этой цели необходимо использовать соответствующие команды проверки-установки (в процессоре Pentium это BTC, BTR, BTS) или специальные системные примитивы атомарных операций.
Поясним это. Пусть в результате проверки переменной поток определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой поток занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому потоку, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к нежелательным последствиям.
Данный способ реализации взаимного исключения имеет существенный недостаток: пока ресурс занят, поток, ожидающий его освобождения, будет непрерывно опрашивать блокирующую переменную, бесполезно тратя процессорное время, которое может быть использовано для выполнения какого-нибудь другого потока.
Для устранения этого недостатка в ОС Windows для работы с критическими секциями используются специальные системные вызовы: EnterCriticalSection() и LeaveCriticalSection().
При входе в критическую секцию (рис. 4.10) поток выполняет системный вызов EnterCriticalSection(), в рамках которого вначале выполняется проверка блокирующей переменной необходимого ресурса. Если ресурс занят, то циклический опрос далее не выполняется, а поток переводится в состояние ожидания освобождения ресурса D. Поток, который в это время использует ресурс D, после выхода из критической секции должен вызвать системную функцию LeaveCriticalSection(), в результате чего ресурс освобождается. ОС просматривает очередь ожидающих этот ресурс потоков и переводит поток, ожидающий событие D, в состояние «готовность».
Рис. 4.10. Реализация критической секции с использованием
системных функций
Семафоры
Семафор является средством управления доступом к разделяемому ресурсу со стороны выполняющихся параллельно потоков. Семафор – это специальная блокирующая переменная, которая может принимать только целые неотрицательные значения: 0; 1; 2; 3 и т. д. В частном случае, когда семафор может принимать только значения 0 и 1, он превращается в блокирующую переменную, называемую двоичным семафором.
Над семафором можно проводить только две операции, традиционно обозначаемые буквами V и Р:
V- операция (освобождение ресурса) – увеличение значения семафора на 1;
Р- операция (занятие ресурса) – уменьшение значения семафора на 1.
Пусть переменная S представляет собой семафор. Тогда операции V(S) и P(S) определяются следующим образом:
V(S) : переменная S увеличивается на 1 единым действием, если это возможно. Выборка, наращивание и запоминание S не могут быть прерваны. К переменной S нет доступа другим потокам во время выполнения этой операции.
P(S) : переменная S уменьшается на 1 единым действием, если это возможно. Если S=0 и ее невозможно уменьшить, оставаясь в области целых неотрицательных значений, поток, вызывающий операцию P, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение S также является неделимой операцией.
Во время выполнения примитивов V и P никакие прерывания недопустимы. Операция P заключает в себе потенциальную возможность перехода потока, который ее выполняет, в состояние ожидания. Операция V может при некоторых обстоятельствах активизировать другой поток, приостановленный операцией P. Операции V и Р выполняются операционной системой в ответ на запрос, выданный процессом и содержащий имя семафора в качестве параметра.
Рассмотрим использование семафоров на примере взаимодействия потоков, выполняющихся в многозадачном режиме. Одни потоки записывают данные в буферный пул, а другие считывают их из буферного пула. (Буферный пул – набор регистров, в которые записывается информация для временного хранения. Регистры освобождаются и занимаются потоками.)
Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись (рис. 4.11). Потоки-писатели должны приостанавливаться, когда все буферы оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, потоки-читатели должны приостанавливаться, когда все буферы пусты, и активизироваться при появлении хотя бы одной записи. Операции записи в буфер и считывания из буфера являются критическими секциями потоков-читателей и потоков-писателей.
Для решения задачи введем три семафора:
e – число пустых буферов;
f – число заполненных буферов;
b – блокирующая переменная – двоичный семафор, используемый для обеспечения взаимного исключения при работе с разделяемыми данными в критической секции.
Рис. 4.11. Использованиесемафоров для синхронизации потоков
Здесь операции Р и V имеют следующее содержание:
Р(е) – если есть свободные буферы, то уменьшить их количество на 1, если нет, то перейти в состояние «ожидание»;
P(b) – если критическая секция доступна, то установить признак «занято» (b=0), если нет, то перейти в состояние «ожидание»;
V(b) – освободить критическую секцию (установить b=1);
V(f) – нарастить число занятых буферов.
Следует учитывать, что уменьшение количества свободных и увеличение числа занятых буферов – разные операции.
Поток-писатель, прежде всего, проверяет, имеются ли в пуле пустые буферы, используя семафор P(e). Если свободных буферов нет (е=0), то поток переводится в состояние ожидания. Если свободные буферы есть (е>0), то поток-писатель уменьшает их число и входит в критическую секцию (если это возможно, т.е. если b=1) для записи данных в буфер. После выхода из критической секции поток-писатель наращивает число занятых буферов V(f).
Поток-читатель действует аналогично, с той разницей, что он начинает работу с проверки наличия заполненных буферов – P(f), а после чтения данных наращивает количество свободных буферов – V(e).
Синхронизирующие объекты ОС
ОС предоставляет процессам и потокам системные объекты синхронизации, которые могут использоваться для синхронизации потоков одного или разных процессов. Реализация объектов синхронизации зависит от конкретной ОС.
Например, в ОС Windows NT используются следующие объекты синхронизации:
· критические секции (для потоков одного процесса);
· семафоры;
· мьютексы (mutex – mutual exclusion) – двоичные семафоры для синхронизации потоков разных процессов;
· события (events) – используются с целью оповещения потоков о свершении какого-либо события;
· таймеры – используются для формирования временных интервалов или конкретного времени взаимодействия потоков.
Тупики
Тупики – это взаимные блокировки процессов, называемые также дедлоками (deadlocks) или клинчами (clinch).
В приведенном выше примере (см. рис. 4.11) если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Действительно, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов. Он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писателем".
Рассмотрим еще один пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, порт и диск (рис. 4.12, а). После того, как процесс А занял порт (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как порт оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.
Рис. 4.12. Возникновение взаимных блокировок при выполнении программы:
a – фрагменты программ А и В; б – взаимная блокировка;
в – очередь к диску; г – независимое использование ресурсов
В зависимости от соотношения скоростей потоков они могут взаимно блокировать друг друга (рис.4.12, б); образовывать очереди к разделяемым ресурсам (рис.4.12, в) независимо использовать разделяемые ресурсы (рис.4.12, г).
Тупиковые ситуации надо отличать от простых очередей, хотя и те и другие возникают при совместном использовании ресурсов и внешне выглядят похоже: процесс приостанавливается и ждет освобождения ресурса. Однако очередь – это нормальное явление при случайном поступлении запросов на раздельно используемые ресурсы. Тупик же является в некотором роде неразрешимой ситуацией.
В рассмотренных примерах тупик был образован двумя процессами, но взаимно блокировать друг друга могут и большее число процессов.
Проблема тупиков включает в себя решение следующих задач: предотвращение тупиков; распознавание тупиков; восстановление системы после тупиков.
Тупики могут быть предотвращены на стадии написания программ, т.е. программы должны быть написаны таким образом, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов. Так, если бы в предыдущем примере процесс А и процесс В запрашивали ресурсы в одинаковой последовательности, то тупик был бы в принципе невозможен. Другой более гибкий подход динамического предотвращения тупиков заключается в использовании определенных правил при назначении ресурсов процессам. Например, ресурсы могут выделяться в определенной последовательности, общей для всех процессов.
Если тупиковую ситуацию не удалось предотвратить, важно быстро и точно ее распознать, поскольку блокированные потоки не выполняют никакой полезной работы. Если тупиковая ситуация образована множеством потоков, занимающих массу ресурсов, распознавание тупика является нетривиальной задачей. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки.
Восстановление системы после тупиков реализуется следующими способами:
- снять с выполнения некоторые процессы для освобождения части ресурсов;
- вернуть некоторые процессы в область свопинга;
- совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.
Из всего вышесказанного ясно, что использовать семафоры нужно очень осторожно, так как одна незначительная ошибка может привести к останову системы. Для облегчения написания корректных программ, было предложено высокоуровневое средство синхронизации, называемое монитором.
Монитор – это набор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют важное свойство, которое делает их полезными для достижения взаимного исключения: только один процесс может быть активным по отношению к монитору.
В распределенных системах, состоящих из нескольких процессоров, каждый из которых имеет собственную оперативную память, семафоры и мониторы оказываются непригодными. В таких системах синхронизация может быть реализована только с помощью обмена сообщениями.
Управление памятью