1. Отношения предшествования.
Для двух процессов существование такого отношения означает, что один процесс должен переходить в активное состояние всегда раньше второго процесса.
2. Отношения приоритетности.
Процесс с приоритетом Р может быть в активном состоянии только при выполнении двух условий: а) в состоянии готовности к рассматриваемому процессу нет процессов с большим приоритетом; б) процессор либо свободен, либо используется процессом с приоритетом меньше, чем Р.
3. Отношения взаимного исключения.
На рисунке: t1t2 – критическая область процесса А; t2t3 – критическая область процесса В. Пусть два процесса А и В используют общий ресурс R. Тогда совокупность действий над этим ресурсом в ходе выполнения каждого процесса называется критической областью или секцией, а совместный ресурс – критическим ресурсом. Критическая область А не должна выполняться над критическим ресурсом R в ходе выполнения другого процесса.
4. Отношение «производители-потребители».
Пусть процессы А и В информационно взаимодействуют друг с другом. Один процесс только вырабатывает сообщения (это «производитель»), а другой – воспринимает их (это «потребитель»). Процессы взаимодействуют через некоторую область, называемую буфером, которую в этом случае является критическим ресурсом. Синхронизация этих двух процессов требует следующих условий: а) обеспечить отношения взаимного исключения в отношении буферной памяти; б) учесть состояния буфера, определяющие возможность или невозможность посылки или принятия сообщения. Процесс-производитель должен быть переведен в состояние ожидания, если предыдущее сообщение не было забрано процессом-потребителем. Аналогично процесс-потребитель переводится в режим ожидания, если процесс-производитель не поместил в буфер очередное сообщение. В общем случае потребителей и производителей может быть больше. Чем по одному. А в буферной области может храниться более одного сообщения.
5. Отношения «читатели-писатели».
В отношении некоторой области памяти множество параллельных процессов, работающих с ней, разделяются на два этапа: 1) процессы-читатели; могут одновременн6о считывать информацию из области данных; 2) процессы-писатели: записывают информацию в область данных только исключая как друг друга, так и процессы-читатели.
6. Отношения «обедающие - философы».
Пусть имеется три параллельных процесса X, Y, Z и три ресурса: р1, р2, р3. Особенность развития процессов такова, что для прерывания процесса Х в активном состоянии ему требуется выделить одновременно р1, для Y – р2 и р3, для Z – р1 и р3.Преходы процессов в активное состояние происходят в непредсказуемые моменты времени.
Синхронизация процессов.
Процессам часто нужно взаимодействовать друг с другом, например, один процесс может передавать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла. Во всех этих случаях возникает проблема синхронизации процессов, которая может решаться приостановкой и активизацией процессов, организацией очередей, блокированием и освобождением ресурсов. Синхронизация – это установление определенной последовательности использования ресурсов множеством параллельных процессов.
Критическая секция Важным понятием синхронизации процессов является понятие "критическая секция" программы. Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Ситуации, когда два или более процессов обрабатывают разделяемые данные, и конечный результат зависит от соотношения скоростей процессов, называются гонками. Простейший способ обеспечить взаимное исключение - позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены. 
Рис. 2.4. Реализация критических секций с использованием блокирующих переменных
Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 2.4 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к разделяемому ресурсу D блокирующую переменную F(D). Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.
Если все процессы написаны с использованием вышеописанных соглашений, то взаимное исключение гарантируется. Операция проверки и установки блокирующей переменной должна быть неделимой. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом был нарушен принцип взаимного исключения, что потенциально может привести к нежелаемым последствиям. Во избежание таких ситуаций в системе команд машины желательно иметь единую команду "проверка-установка", или же реализовывать системными средствами соответствующие программные примитивы, которые бы запрещали прерывания на протяжении всей операции проверки и установки.
Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Для устранения таких ситуаций может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 2.5 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.
Обобщающее средство синхронизации процессов предложил Дейкстра в семафорном механизме.,.
Семафорный механизм Семафор – это переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух видов примитивных операций (закрытие и открытие), которая соответственно называются p и V операциями. Пусть имеется некоторый ресурс R. Поставим ему в соответствие целочисленную переменную – семафор S. Тогда операция P(S) уменьшает величину S на единицу, причем если S>0 или S=0, то процесс продолжает работу, а если S<0, то процесс блокируется (приостанавливается) пока V(S), выполненная другим процессом, не разблокирует его. Операция V(S) увеличивает величину S на единицу, причем если после этого S>0 или S=0, то ранее разработанный процесс разблокируется, а также процесс, выполнивший операцию V(S), может продолжаться далее. Процессы используют P и V в сочетании: Р – работа с критическим ресурсом V. В каждый момент времени только одна операция, P и V, может выполняться над данным семафором. Для синхронизации обобщенных отношений поставщиков и потребителей (количество сообщений в буфере больше одного) введем три общих семафора: S1 – число свободных мест в буфере; S2 – число сообщений в буфере; S3 – взаимоисключение процессов. В начальный момент: S1 – число свободных мест в буфере; S2=0; S3=1 (буфер не занят ни одним процессом и доступен любому). Чтобы послать сообщение в буфер, поставщик должен выполнить следующие операции:
1) Проверяется наличие места в буфере, и, если такого нет, то процесс блокируется. Если свободное место есть, то его количество меньше на единицу.
2) Проверяется доступность буфера, и, если он доступен, то процесс блокируется; в противном случае буфер занимается.
3) Записывается сообщение в буфер.
4) Увеличивается количество сообщений в буфере, и, если процесс В был заблокирован по отсутствию сообщений в буфере, то процесс В разблокируется.
5) Разблокируется доступ к буферу.
Потребитель В выполняет следующую последовательность операций:
|
|
1) Проверяет наличие сообщение в буфере, и, если таковых нет, то процесс блокируется; если сообщение есть, то их количество меньше на единицу.
2) Проверяется доступность буфера, и, если он недоступен, то процесс блокируется; в противном случае буфер занимается.
3) Забирается сообщение из буфера.
4) Увеличивается количество свободных мест в буфере, и, если процесс А был заблокирован по отсутствую свободных мест, то он разблокируется.
5) Разблокируется доступ к буферу. Операция с семафором реализуется аппаратными и программными средствами, входящими в состав ОС. В последнем случае операции P и V представляются специальными функциями ОС.
Монитор. Монитор – это набор процедур и структур данных, которые выполняют все работы по организации доступа к ресурсу или групп однотипных ресурсов. Монитор каждого ресурса находится вне процесса и любой процесс может им воспользоваться. При этом процессы полностью освобождаются от всех конструкций, необходимых для синхронизации. Сложность проблемы синхронизации состоит в нерегулярности возникающих ситуаций
Тупики.
Еще одна проблема синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками.
Пусть процесс А владеет ресурсом R1, и ему дополнительно требуется ресурс R2. В то же время процесс В обладает ресурсом R2 и ему дополнительно требуется ресурс R1. В этом случае говорят, что процессы зашли в тупик, т.е. они не могут развиваться, так как их запросы на ресурсы никогда не могут быть удовлетворены, если не предпринять чрезвычайных системных мер.
Проблема тупиков включает в себя следующие задачи:
· предотвращение тупиков,
· распознавание тупиков,
· восстановление системы после тупиков.
Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов.В некоторых случаях, когда тупиковая ситуация образована многими процессами, использующими много ресурсов, распознавание тупика является нетривиальной задачей. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.
Условия возникновения тупиков.
1. Процессы не разрешают отведенный им ресурс одновременно использовать другим процессом (взаимное исключение).
2. Требуя новые ресурсы, процессы не отдают полученные (условие ожидания).
3. Ресурсы не могут быть отняты у процессов (отсутствие предпочтения).
4. Существует замкнутая цепь ресурсов, в которой каждый процесс удерживает хотя бы один ресурс, требуемый далее в цепи (циклическое ожидание).
Способы предотвращения тупика.
Набор правил:
1) Каждый процесс должен запрашивать сразу все нужные ему ресурсы, и только получив их, может начинать свою работу.
2) Если процесс получает отказ на запрашиваемый ресурс, то он должен освободить занятые им ранее ресурсы.
3) Типы ресурсов упорядочиваются; если процесс получил некоторый ресурс, то он может требовать только следующий по порядку ресурс.
Этот подход приводил к неэффективному использованию ресурсов.
Алгоритм банкира. Имеется N единиц некоторого ресурса, а на обслуживание принимаются только те процессы, которым может потребоваться не более N единиц ресурса. Пусть частично запросы некоторых процессов удовлетворены и поэтому соответствующие части ресурса находятся у этих процессов, а некоторая часть – свободна. Пусть поступает новый запрос, если выполняются следующие условия:
1) Оставшийся после его удовлетворения ресурс должен быть достаточным для завершения хотя бы одного из процессов, ранее уже получивших часть ресурса.
2) Освобожденный этим процессом ресурс и не использованные ранее ресурсы вместе должны быть достаточны для завершения еще хотя бы одного процесса. И так проводятся аналогичные проверки до возможности завершения всех уже начатых процессов.
Обнаружение тупика.
Метод обнаружения заключается в том. Что выполняемые процессы периодически сбрасывают счетчик времени, а переполнение таких счетчиков является признаком наличия тупика (может поймать заждавшийся ресурса процесс).
Выход из тупика.
1. Прекращение процессов. Процессы в тупике полностью уничтожаются в некотором систематическом порядке до тех пор, пока не станет доступным достаточное количество ресурсов для устранения тупика. В худшем случае устраняются все процессы, находящиеся в тупике, кроме одного.
2. Перехват ресурсов. У процессов отнимается достаточное количество ресурсов и отдается процессам, находящимся в тупике, для ликвидации тупика. Процессы, у которых ресурсы были отняты, остаются с заявленными запросами на перехваченные у них ресурсы.
 |
