34. Механизмы синхронизации: post/wait
Структура данных.
ECB (блок управления событиями)
W P
0
1 31
флаги информационная часть
Функции POST и WAIT – работает с блоком.
Пример:
Точка входа
ATTACH EP=B ECB=адр1
Создание другого процесса
ATTACH EP=C ECB=адр2
…………….
ATTACH EP=D ECB=адр3
………………..
WAIT 3, ECBLIST=адр1
3 – общее число ожидаемых сообщений.
Зад B
0 0 адр RB зад
A
0 0 адр RB зад
A
0 0 адр RB зад
A
…….
POST
адр1, код завершения В
………….
адр2
адр3
зад С
0 1код зав.B
0 0 адр RB зад
A
0 0 адр RB зад
A
…….
POST
адр2, код завершения C
………….
0 1 код зав. B
1 0 адр RB зад
A
1 0 адр RB зад
A
2
адр RB зад A
2 – счетчик ожид. событий
Завершилось задание C. Счетчик ожид событий =1
0 1 код зав. B
0 1 код зав С
1 0 адр RBзадA
…….
POST
адр3, код завершения D
………….
0 1 код зав. B
0 1 код зав С
0 1 код зав D
Завершилось задание D. Счетчик ожид событий =0
Постановка А в очередь готовности
35. Синхронизация посредством обмена сообщениями.
Сообщение – один процесс производит а другие съедают.
QNX – упр ОС и обмен сообщениями
Есть процессы получатели и процессы потребители.
Сообщение.
заголовок информационная часть
send – отправить сообщение
send (di. Buf, Lbuf, rbuf, Lrbuf)
char *buf
di –идентификатор, Buf –буфер, Lbuf – длина буфера, rbuf – буфер для ответного сообщения, Lrbuf-его дилна
Нужно знать шв получателя. Его можно получить специальными средствами.
Receive – получить.
Receive (id, buf, Lbuf)
id – идентификатор процесса отправителя (0 – любой отправитель)
Запрос сообщения. Если его нет, то в ожидание.
36. Тупиковые ситуации в ос
Опр: Тупиковые ситуации – ситуации, когда 2 или более процессов перешли в состояние ожидания и никогда не могут из него выйти. Это возникает, когда процесс взаимодействует с ресурсом.
Пример 1: «смертельное объятие»
P1:
запрос на R1
…
запрос на R2_________блокируется
...
освобождение R2
освобождение R1
P2:
запрос на R2
...
запрос на R1_________блокируется
...
освобождение R1
освобождение R2
Если процессы выполняются последовательно, то все хорошо.
Действия процесса:
Запрос ресурса. Если ресурс свободен – процесс активен.
Запрос ресурса
Процесс владеет ресурсом
Освобождение ресурса
Рассмотрим:
1. P1 запросил R1
2. P1 владеет R1 (т. к. R1 свободен)
3. запрос в процессе P2: P2 владеет R2
4. Активен P1: P1 запросил R2 (R2 – занят)
5. выполняется P2: P2 запросил R1 (R1 – занят)
P1, P2 – в состоянии ожидания НАВЕЧНО.
Пример 2
P1, P2, ..., Pn – процессы.
Существует ресурс не единичной емкости R (m единиц). Например, память – выделяется блоками.
Процесс захватывает память по частям. Все процессы стали в состояние ожидания.
В UNIX процесс запрашивает память только 1 раз. С точки зрения системы память занята процессом.
Пример 3
P1 – вырабатывает сообщение s1
P2 – вырабатывает сообщение s2
P3 – вырабатывает сообщение s3
P1 ... ждать S3; послать S1
P2 ... ждать S1; послать S2
P3 ... ждать S2; послать S3
P1 – в ожидании, т. к. S3 нет. Не может послать S1.
P2 ждет S1 (его нет)
P3 ждет S2 (его нет)
Получили тупиковую ситуацию. Если поменять местами «послать» и «ждать» все хорошо работает.
Данную ситуацию нельзя обнаружить в отладчике, надо анализировать с помощью модели.
1. определить состояние системы – вектор, в который входят все состояния процессов ( активен – блокирован) и состояния ресурсов (свободен – занят)
2. Определить операции (запрос – освобождение)
Если рассматривать все возможные ситуации – получится ОЧЕНЬ много, невозможно нарисовать на одном листе. Поэтому используют модель Холта (рассматриваются отдельные ресурсы и процессы). Есть теорема : «Если в графе цикл, то тупик». Но обратное НЕВЕРНО, т.е. если нет циклов, еще не значит, что нет тупиков.
Задачи:
1. Распознавание тупика
2. Восстановление – как выйти
3. Предотвращение тупика (безопасная система). Опасная система допускает тупики, но работает быстрее.
Распознавание (используем модель Холта)
1. Выбираем активный процесс, стираем все стрелки. Например, P1
2. P1 вычеркнут, ресурс перейдет к P3
3. P3 активен – вычеркнули.
Активных процессов нет, граф содержит дуги -> существует тупик. Нет дуг – нет тупиков.
Восстановление
- единого способа выхода из тупика не существует. Можно отнять ресурс у процесса. Но надо каждый раз решать отдельно.
Предотвращение
-универсальные системы
1) Предварительное распределение ресурсов: перед запуском процесса ему предоставляются все нужные ресурсы. Но: надо знать эти ресурсы (существует предварительное описание)
Недостатки:
-медленная работа
-расточительно (если процесс мало использует ресурс, ресурс все равно занят)
Пример:
-применялось ограничено
2) Контроль за распределением ресурса
2.1. регулярное распределение - нужно знать все ресурсы, которые потребляет процесс. Перед запуском процесса строим модель Холта и сокращаем граф. Если тупика нет, запускаем. Если есть – не запускаем.
Недостаток – работает медленно. На практике не применяется.
2.2. Стандартная последовательность распределения.
Все ресурсы разделены на классы: К1, К2, …, Кi, Ki+1, ... Kn.
Запросы удовлетворяются в порядке возрастания классов, т. е. если процесс запросил ресурс из нескольких классов, то сначала используется класс с меньшим номером => тупика не будет.