Пример монитора: кольцевой буфер

Производителю иногда требуется передать данные, в то время как потребитель еще не готов их принять, а потребитель иногда пытается принять данные, которые производитель еще не выдал.

В ОС часто предусматривается выделение некоторого фиксированного количества ячеек памяти для использования в качестве буфера передач между процессом-производителем и процессом-потребителем. Этот буфер можно представить в виде массива заданного размера. Процесс-производитель помещает передаваемые данные в последовательные элементы этого массива. Процесс-потребитель считывает данные в том порядке, в котором они помещались. Производитель может опережать потребителя на несколько шагов. Со временем процесс-производитель займет последний элемент массива. Когда он сформирует после этого очередные данные для передачи, он должен будет «возвратиться к исходной точке» и снова начать с записи данных в первый элемент массива (при этом естественно предполагается, что потребитель уже прочитал те данные, которые ранее сюда поместил производитель). Такой массив по сути работает как замкнутое кольцо.

Пример монитора: читатели и писатели

В вычислительных системах обычно имеются некоторые процессы, которые читают данные (и называются «читателями»), и другие процессы, которые записывают данные (и называются «писателями»).

Монитор под названием «читателииписатели»: в каждый конкретный момент времени работать может только один писатель; когда какой-либо писатель работает, логическая переменная «ктотопишет» имеет истинное значение. Ни один из читателей не может работать, во время работы какого-либо писателя. Переменная «читатели» указывает количество активных читателей. Когда число читателей оказывается равным нулю, ожидающий процесс-писатель получает возможность начать работу. Новый процесс-читатель не может продолжить свое выполнение, пока не появится истинное значение условия «читатьразрешается», а новый процесс-писатель — пока не появится истинное значение условия «писатьразрешается».

Сообщения. Это метод межпроцессорного взаимодействия, который использует два примитива: send и receive. Первый запрос посылает сообщение адресату, а второй получает сообщение от указанного источника. Если сообщения нет, второй запрос блокируется до получения сообщения.

Предпологается, что все сообщения имеют одинаковый размер и сообщения, которые посланы, но еще не получены, автоматически помещаются ОС в буфер. В этом решении используются N сообщений, по аналогии с N сегментами в буфере. Потребитель начинает с того, что посылает производителю N пустых сообщений. Как только у производителя оказывается элемент данных, который он может представить потребителю, он берет пустое сообщение и отсылает назад полное. Таким образом общее число сообщений в системе постоянно и их можно хранить в заранее заданном участке памяти.

Если производитель работает быстрее, чем потребитель, все сообщения будут ожидать потребителя в заполненном виде. При этом производитель блокируется в ожидании пустого сообщения. Если потребитель работает быстрее, ситуация инвертируется: все сообщения будут пустыми, а потребитель будет блокирован в ожидании полного сообщения.

передача сообщений в пределах одного компьютера происходит существенно медленнее, чем работа с семафорами и мониторами.

14. Тупики: условия возникновения, методы борьбы, стратегия Ханвендера; метод редукции графа - представление состояний системы в виде направленных графов; представление графа – матричное, с помощью связного списка; алгоритмы обнаружения тупиков - метод прямого обнаружения, алгоритм со счетчиком ожиданий; обход тупиков - алгоритм банкира; обнаружение и восстановление работоспособности системы.

Тупики

Одна из проблемм синхронизации - взаимные блокировки (тупики).

Пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.