Обмен сообщениями между процессами.

Этот обмен обеспечивается посредством т.н. почтового ящика. Главное требование – доставка соответствующему адресату (причем правильная доставка).

Протокол (требования):

1. прием/передача сообщений на пользовательском уровне должны выглядеть как вызовы процедур чтения/записи;

2. при обращении к процедуре чтения сообщения в случае его отсутствия процесс приостанавливается и ждет появления сообщения;

3. при обращении к процедуре записи сообщения и отсутствии процесса, ждущего это сообщение, последнее становится в очередь;

4. процесс, передающий сообщение, приостанавливается и ждет подтверждения.

По сути дела почтовый ящик – набор очередей.

Почтовый ящик – объект, который в качестве данных содержит:

• очер_сообщ, ожидающую процессы;

• очер_проц, ожидающую сообщения;

• очер_проц, ждущих подтверждения.

Методы: чтение/запись.

Уровни планирования ресурсов.

1)Простейший уровень; FIFO

2)Простейший уровень с защитой от тупиков (Deadlock);

3)2) + оптимальное использование ресурсов.

Тупики и борьба с ними.

4 причины (одновременно):

• метод ВИ (взаимных исключений);

• условие ожидания ресурса, при котором неработающие ресурсы не отпускаются;

• отсутствие “перетряхиваемой” системы;

• режим круговых ожиданий.

1 Ресурс

1 процесс

2 процесс

2 ресурс

Методы борьбы с тупиками:

1. алгоритм, не допускающий тупики;

а) априорной защиты (более жесткие);

б) обхода тупиков (более мягкие).

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

Алгоритмы априорного удаления тупиков.

Эти алгоритмы так или иначе связаны с разрушением какой-либо из причин возникновения тупиков.

1. метод устранения 2-ой причины возникновения тупиков;

Основная идея – предоставлять либо все ресурсы системы, либо ни одного.

Недостатки:

1. нарушаются принципы FIFO;

2. не оптимально тратятся ресурсы системы.

2. метод устранения 3-ей причины возникновения тупиков (метод перераспределяемости);

Заключается в том, что система “перетряхивается” (т.е. нерабочие ресурсы возвращаются).

Недостатки:

1. нарушаются принципы FIFO;

2. неоптимальное использование ресурсов.

3. метод устранения 4-ой причины возникновения тупиков (упорядоченные классы);

На самом деле – это режим кругового ожидания.

Ресурсы нумеруются – 1, 2, 3, …

1 Ресурс

2 Проц.

1 проц.

2 Ресурс

Ресурс более высокого класса выделяется в том случае, если уже взят ресурс более низкого класса (более высокий класс – условное разделение).

Алгоритм Дейкстры.

Идея заключается в том, что:

Вводится понятие надежного состояния (это состояние, находясь в котором система не зависнет даже при самых неблагоприятных прогнозах).

Переход осуществляется из одного надежного состояния в другое.

Исходные данные для планирования – матрица ресурсов, процессов и т.д.

Каждый раз, когда запрашивается ресурс, то анализируется ситуация при каждом запросе процесса ресурсов; если выделение этого ресурса приводит к другим НС, то ресурс выделяется, в противном случае – нет.

Пример:

проц	рес	Макс. число рес.
P1	3	6
P2	2	4
P3	1	5

Свободно 2 ресурса. Какому процессу их отдать? – второму, т.к. он поработает и отдаст их системе, т.е. здесь имеет место НС.

Достоинства:

+ гибкий алгоритм;

+ позволяет теоретически показать, что процессы сходятся (если хватает ресурсов); если число ресурсов равно хотя бы максимальному числу необходимых ресурсов какого-либо из процессов, то можно продолжить выполнение хотя бы последовательно (в отсутствии многозадачности).

Недостатки:

• алгоритм работает для конкретного числа процессов;

• если число процессов n, то число ресурсов = n!

Алгоритм Габермана.

Это – графический режим.

2 пр.

1 пр.

Вершины – процессы

Дуги - ресурсы

1 рес.

Суть метода заключается в предоставлении ресурса до тех пор, пока не образуется цикл в графе (из рисунка видно, что 3-ий ресурс не предоставляется первому процессу)

1 рес.

3 рес.

3 пр.

4 пр.

5 пр.

2 рес.

Достоинства:

1. нет ограничений на количество процессов;

2. сложность проверки на наличие цикла в графе.