Чередования, условия состязания и взаимоисключения

УПРАВЛЕНИЕ ПРОЦЕССАМИ. АЛГОРИТМЫ СИНХРОНИЗАЦИИ

Контрольные вопросы

1) Назовите причины кооперации процессов

2) Что такое кооперативные и независимые процессы

3) Опишите категории средств обмена информацией между процессами

4) Охарактеризуйте прямую и непрямую адресацию при обмене информацией между процессами

5) Охарактеризуйте прямую и непрямую связь между процессами

6) Опишите буферизацию и три варианта объемов буфера канала связи

7) Опишите потоковую модель передачи данных по каналам связи

8) Опишите модель сообщений передачи данных по каналам связи

9) Назовите условия обмена данными

10) Охарактеризуйте завершение связи между процессами

11) Опишите поток и состояния потока

12) Опишите планирование в операционных системах, поддерживающих потоки на уровне ядра и библиотек

На лекции рассматриваются следующие вопросы:

1) Чередования, условия состязания и взаимоисключения

2) Критическая секция

3) Алгоритмы взаимоисключений (требования, предъявляемые к алгоритмам; запрет прерываний; переменная-замок; строгое чередование; флаги готовности; алгоритм Петерсона; алгоритм булочной)

4) Аппаратная поддержка взаимоисключений (Команды Test-and-Set, Swap)

5) Недостатки алгоритмов взаимоисключений

6) Семафоры (концепция семафоров, решение проблемы производитель-потребитель с помощью семафоров)

7) Мониторы

8) Сообщения

9) Эквивалентность семафоров, мониторов и сообщений

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

При исполнении программ псевдопараллельно, в режиме разделения времени, они могут расслоиться на атомарные операции с различным их чередованием (interleaving).

Атомарные операции программ могут чередоваться всевозможными способами с сохранением своего порядка расположения внутри программ. Так как псевдопараллельное выполнение программ приводит к чередованию их неделимых операций, то результат псевдопараллельного выполнения может отличаться от результата последовательного выполнения.

Набор программ детерминирован, если всякий раз при псевдопараллельном исполнении для одного и того же набора входных данных он дает одинаковые выходные данные. В противном случае он недетерминирован. Детерминированный набор программ можно безбоязненно выполнять в режиме разделения времени. Для недетерминированного набора такое исполнение нежелательно.

Про недетерминированный набор программ говорят, что он имеет состязание (race condition) за ресурс.

Пример 1

Пусть есть две программы P и Q, состоящие из двух атомарных операций каждая:

P: x=2 Q: x=3

y=x-1 y=x+1

Возможны четыре разных набора значений для пары (x, y): (3, 4), (2, 1), (2, 3) и (3, 2).

Это пример недетерминированного набора программ. Процессы состязаются за вычисление значений переменных x и y.

Задачу упорядоченного доступа к разделяемым данным (устранение состязания), в том случае, если не важна его очередность, можно решить, если обеспечить каждому процессу эксклюзивное право доступа к этим данным. Каждый процесс, обращающийся к разделяемым ресурсам, исключает для всех других процессов возможность одновременного с ним общения с этими ресурсами, если это может привести к недетерминированному поведению набора процессов. Такой прием называется взаимоисключением (mutual exclusion). Если очередность доступа к разделяемым ресурсам важна для получения правильных результатов, то одними взаимоисключениями уже не обойтись.