Отношения между процессами

Между процессами в мультипрограммной ВС могут возникать различно-

го типа отношения. Рассмотрим основные из них:

Отношение предшествования. Для двух процессов существование тако-

го отношения означает, что один процесс должен переходить в активное

состояние всегда раньше второго процесса.

Отношение приоритетности. Процесс с приоритетом P может быть в

активное состояние только при выполнении двух условий:

- в состоянии готовности к рассматриваемому процессору НЕТ про-

цессов с большим приоритетом;

- процессор либо свободен, либо используется процессом с приори-

тетом меньшим Р.

Отношение взаимного исключения.

1.0

Ожидание

Процесс A│ ┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐ ┌┬┬ ...┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐

├──┴┴┴┴┴┴┴┴^┴┴┴┴┴┴┴┼─────┴┴┼────┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴──

│ ├┬┬┬┬┬┬┬┤ │ ├┬┬┬┬┬┬┬┬┬┐

Ресурс R ├──────────┼┴┴%┴┴┴┴┼┬┬┬┬┬┬┬^┬┬┬┬┼┴┴┴┴┴┴┴┴┴┴──────

│ │ │ ├┴┴┴┴┴┴┴┼┴┴┴┴┤

│ ┌┬┬┬┬┬┼ ...├┬┬┬┬┬┬┬┬┬┬┬┬┐

Процесс B├───────┴┴┴┴┴┴┼────┼┴┴┴┴┴┴┴┴┴┴┴┴┴────────────────

│ │ │ │ │ │

│ │ │ │ │ │

└──────────┼──┼────┼───────┼────┼────────────────

t1│ t2 t3│ t4 │t5

│5──┬──6┼5───┬──────6┤

Критическая область│ │ Критическая область

процесса A │ │ процесса B

───────┘ └────

0

Пусть два процесса A и B используют при своем развитии некоторый

общий ресурс R. Тогда совокупность действий над этим ресурсом в ходе

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

но используемый ресурс называется критическим ресурсом.

Критическая область не должна выполнятся процессом одновременно

с критической областью над этим же ресурсом в ходе другого процесса. В

общем случае количество параллельных процессов, использующих общий

ресурс, и следовательно имеющих соответствующую критическую секцию,

может быть более двух.

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

Установление определенной последовательности (очередности) ис-

пользования ресурсов множеством параллельных процессов называется

синхронизацией(приведение двух или более процессов к согласованному

по времени выполнению)

Множественность отношений между процессами порождает множество ме-

ханизмов синхронизации, реализуемых средствами ОС. Рассмотрим основ-

ные из них.

Семафорный механизм. Предложен в 1965г Э.Дейкстра.

Семафор- переменная специального типа, которая доступна парал-

лельным процессам для проведения над ней только двух видов примитивных

операций (простейших) "закрытия" и "открытия", называемых соответс-

твенно P- и V-операциями.

ТУПИКИ

Пусть процесс А владеет ресурсом R1 и ему дополнительно требуется

ресурс R2, в то же время процесс В владеет ресурсом R2 и ему дополни-

тельно требуется ресурс R1. В этом случае говорят, что эти процессы

зашли в тупик.

То есть, эти два процесса не могут развиваться, так как их запро-

сы на ресурсы никогда не могут быть удовлетворены, если не будут при-

няты черезвычайные системные меры:

- принудительное изъятие ресурсов или;

- ликвидация процессов.

┌─────────┐ ┌──────────┐ ┌─────────┐ ┌──────────┐

│ ┌─┴──────^┐ │ │ ┌─┴──────^┐ │

╔═══^═══╗ │Ресурс R1│ ╔═════╧═╗ ╔═══^═══╗ │ Ручка │ ╔═════╧═╗

║процесс║ └─────────┘ ║процесс║ ║Студент║ └─────────┘ ║Студент║

║ А ║ ┌─────────┐ ║ В ║ ║ ПЕТЯ ║ ┌─────────┐ ║ ВАСЯ ║

╚═══╤═══╝ │Ресурс R2│ ╚═════%═╝ ╚═══╤═══╝ │ Бумага2│ ╚═════%═╝

│ └─%─────┬─┘ │ │ └─%─────┬─┘ │

└─────────┘ └───────────┘ └─────────┘ └───────────┘

Совокупность условий необходимых и достаточных для возникновения

тупиков:

1)процессы не разрешают отведенный им ресурс одновременно исполь-

зовать другим процессам(взаимное исключение);

2)требуя новые ресурсы, процессы не отдают полученные ранее(усло-

вие ожидания);

3)ресурсы не могут быть отняты у процессов(отсутствие предпочте-

ния);

4)существует замкнутая цепь ресурсов, в которой каждый процесс

удерживает хотя бы один ресурс, требуемый далее в цепи.(циклическое

ожидание).

Тупики можно предотвращать, обнаруживать и устранять.

Способы предотвращения тупика.

ПЕРВЫЙ ПОДХОД

1)каждый процесс должен запрашивать сразу все необходимые ему ре-

сурсы, и только получив их может начинать свою работу(устраняется ус-

ловие ожидания);

2)если процесс получает отказ на запрашиваемый ресурс, то он дол-

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

3)типы ресурсов упорядочиваются. Если процесс получил некоторый

ресурс, то он может требовать только следующий по порядку ресурс(уст-

раняется циклическое ожидание)

Такой подход приводит к неэффективному использованию ресурсов,

однако легко реализуется.

ВТОРОЙ ПОДХОД (Алгоритм банкира)

Имеется N единиц некоторого ресурса R и на обслуживание принима-

ются только те процессы, которым может потребоваться не более N единиц

ресурса.

Пусть частично запросы некоторых процессов удовлетворены и поэто-

му соответствующие части ресурса находятся у этих процессов, а некото-

рая часть ресурса R - свободна.

Поступает новый запрос. Он может быть принят на обслуживание если:

- оставшийся после его удовлетворения ресурс - должен быть доста-

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

ших часть ресурса;

- освобожденный этим процессом ресурс и неиспользованный ранее

ресурс вместе должны быть достаточны для завершения еще хотя бы одного

процесса;

- и так далее, до завершения всех начатых процессов.

Обнаружение тупика(распознование). Незаблокированный процесс

приобретает любые ресурсы, в которых он нуждается, выполняет необходи-

мые действия, а затем освобождает ВСЕ свои ресурсы и засыпает. Осво-

бождение ресурсов может освободить некоторые ранее заблокированные

процессы. Такая работа ВС продолжается до тех пор, пока не останется

незаблокированных процессов.

Если существу ют некоторые заблокированные процессы при заверше-

нии описанной последовательности действий, то оставшиеся процессы на-

ходятся в состоянии тупика, в противном случае нет процессов в состоя-

нии тупика.

Один из практически используемых методов обнаружения тупиков зак-

лючается в том, что выполняемые процессы периодически сбрасывают счет-

чики времени, а переполнение таких счетчиков служит признаком наличия

тупика.

Выход из тупика: Существует два общих подхода:

1)прекращение процессов.Процессы в тупике последовательно прекра-

щаются(уничтожаются) в некотором систематическом порядке до тех пор,

пока не станет доступным достаточное количество ресурсов для устране-

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

находившиеся в тупике, кроме одного (Почему?)

Наиболее простым и практичным порядком уничтожения является стра-

тегия, при которой первыми уничтожаются процессы с наименьшей ценой

прекращения. Такой ценой может быть:

а)приоритет процесса;

б)затраты времени на повторный запуск процесса и его выполнение

до точки прекращения;

в)внешняя цена, определяемая пользователем породившим этот про-

цесс (студент, администрация, системный программист, производство)

2)перехват ресурсов. У процессов отнимается достаточное количест-

во ресурсов и отдается процессам, находящимся в тупике, чтобы ликвиди-

ровать тупик. Процессы, у которых ресурсы были отняты, остаются с выс-

тавленными запросами на перехваченные у них ресурсы.