Файл: Оглавление Раздел I. Основные понятия.pdf

78 случае необходимости можно временно прервать процесс печати и предоставить принтер другому процессу.
При восстановлении через откат процесс периодически сохра- няет свое состояние, создавая контрольные точки. Это означает, что его состояние записывается в файл и впоследствии процесс может быть возобновлен из этого файла. Чтобы выйти из тупика процесс, занимающий необходимый ресурс, откатывает к тому моменту вре- мени, перед которым он получил данный ресурс. Освободившийся ресурс отдается другому процессу, попавшему в тупик.
Простейшим способом выхода из блокировки является уни- чтожение одного или нескольких процессов, находящихся в цикле взаимоблокировки. В некоторых случаях имеются процессы без по- бочных эффектов, которые можно перезапустить, не нарушая работу системы. Например, процедуру компиляции всегда можно повто- рить заново.
Рассмотрим простейший случай обнаружения тупика, когда каждый тип ресурсов системы представлен единственным ресурсом.
Например, такая система могла бы иметь один сканер, одно устрой- ство записи дисков, один принтер и так далее.
Обнаружение тупика в случае единственности ресурса каждо- го типа состоит из двух этапов: в текущем состоянии необходимо построить граф Холта, далее найти на нем цикл по какому-либо ал- горитму.
Рассмотрим пример системы из семи процессов, состояние ко- торых описывает таблица.
Процесс Захват ресурса Ждет ресурс
A
R
S
B
-
T
C
-
S
D
U
S, T
E
T
V
F
W
S
G
V
U

79
Рис. 9.3. Граф Холта, показывающий состояние тупика процессов D,V и G
Граф Холта, построенный по таблице, показан на рис.9.3. По визуальной модели состояния системы процессов видно, что про- цессы D, E, G (вместе с ними и процесс B) находятся в тупике. Про- цессы А, C и F могут завершить исполнение и высвободить занима- емые ресурсы, поскольку любому из них можно предоставить ре- сурс S.
Для анализа графа большей размерности может применяться следующий алгоритм. Используем список L для хранения посещен- ных узлов и пометки для пройденных ребер. Алгоритм применяется для каждого узла графа.
Шаг 1. Начальные условия: имеется текущий узел, список L пустой, ребра не маркированы.
Шаг 2. Текущий узел добавляем в конец списка L. Если теку- щий узел присутствует в списке два раза, то граф содержит цикл
(записанный в L). Алгоритм завершается.
Шаг 3. Если из текущего узла выходит немаркированное реб- ро, переходим к шагу 4, иначе переходим к шагу 5.
R
S
T
V
U
W
A
B
C
D
E
F
G

80
Шаг 4. Выбираем любое немаркированное ребро, маркиру- ем его, по нему переходим к новому текущему узлу. Переходим к шагу 2.
Шаг 5. Удаляем последний узел из списка. Предпоследний узел объявляем текущим. Возвращаемся к шагу 3. Если перед шагом
5 в списке был только начальный узел, то граф не содержит циклов.
Алгоритм завершается.
Теперь рассмотрим общий случай обнаружения тупика, если имеется один или несколько типов ресурсов представленных не од- ним, а сразу несколькими ресурсами.
В системе имеется m типов ресурсов. E = (e
1
, e
2
, …, e
m
) – век- тор существующих ресурсов, в котором e
j
- количество ресурсов типа
j (1

j

m). A = (a
1
, a
2
, …, a
m
) – вектор доступных ресурсов. В си- стеме имеется n процессов. Матрица текущего распределения ресур- сов С имеет вид:
C=












nm
n
m
m
c
c
c
c
c
c
c
1 2
21 1
12 11
, где
ij
c
– количество ресурсов типа
j, полученных процессом i.
Матрица запросов ресурсов R имеет вид:
R=












nm
n
m
m
r
r
r
r
r
r
r
1 2
21 1
12 11
, где r
ij
- количество ресурсов типа j, запрашиваемых процессом i.
С учетом условия взаимного исключения для ресурсов выпол- няется соотношение
j
n
i
j
ij
e
a
c




1

81
Алгоритм обнаружения тупиков состоит из следующих шагов.
Все процессы не маркированы.
Шаг 1. В матрице R ищем строку, соответствующую немарки- рованному процессу, которая меньше либо равна А (r
j

a
j
).
Шаг 2. Если такая строка i найдена, то маркируем соответ- ствующий процесс, прибавляем строку номером i матрицы C к век- тору А, возвращаемся к шагу 1.
Шаг 3. Если немаркированных процессов нет, то алгоритм за- вершается.
Если после завершения алгоритма остаются немаркированные процессы, то они находятся в тупике.
Пример. Требуется определить, находится ли система процесс- ресурс в тупике.
E=(4, 2, 3, 1) A=(2, 1, 0, 0)











0120 2001 0010
C











2100 1010 2001
R
Убедимся в выполнении условия взаимного исключения для ресурсов: сложим строки матрицы C и вектор A, получим вектор E.
1 2
3 2 2 2 0 3 -
4 2 2 1 2 -
4 2 3 1 1-
A
( , , , )
маркируем
й процесс
A
( , , , )
маркируем
й процесс
A
( , , , )
маркируем
й процесс



Выполняя последовательность шагов алгоритма, маркируем все процессы. Следовательно нет процессов, находящихся в тупике.
Избегание взаимных блокировок. В первом примере показано, что, выбирая определенный порядок планирования среди несколь- ких возможных, планировщик избегает тупика. Стратегию поведе- ния планировщика в случае двух процессов и произвольного коли- чества ресурсов (в каждом типе имеется 1 ресурс) представляет диа- грамма траектории ресурсов (рис. 9.4).

82
Рис. 9.4. Диаграмма траектории ресурсов
Диаграмма представляет собой первый квадрант координат- ной плоскости. Оси являются временными, представляя события процесса А и процесса B. Для определенности свяжем отсчеты вре- мени процесса А со следующими событиями: 1 – захват принтера,
2 – захват плоттера, 3 – освобождение принтера, 4 – освобождение плоттера. На временной оси процесса B отмечаются следующие со- бытия: 1 – захват плоттера, 2 – захват принтера, 3 – освобождение плоттера, 4 – освобождение принтера.
С учетом введенных обозначений точка на диаграмме траек- тории ресурсов представляет состояние системы. Она может дви- гаться только вверх и вправо. В некоторых областях диаграммы си- стема не может находиться по правилу исключения для ресурса. Об- ласти называются, соответственно, области исключения ресурса
(рис. 9.4).
Если во время планирования точка, обозначающая состояние системы, попадет в область Х, то со временем в системе возникнет блокировка, так как точка не может двигаться вниз и влево. Любое состояние в области серого цвета является безопасным состоянием.
А
B
1 2
3 4
1 2
3 4
Области ис- ключения ре- сурсов
Тупик

83
В таком состоянии планировщик путем аккуратного планирования ресурсов может избежать возникновения тупика (рис. 9.4).
Алгоритм Банкира для одного типа ресурсов. Анализ диа- граммы траектории ресурсов показал, что цель алгоритма планиро- вания – проверить приводит ли удовлетворение запроса на ресурс к выходу из безопасного состояния системы.
Пусть имеется один ресурс некоторого типа. Воспользуемся аналогией работы планировщика с поведением банкира, кредитую- щего клиентов. Запишем состояние системы в виде таблицы распре- деления ресурсов, в которой A, B, C – имена клиентов банка (про- цессы); второй столбец – выданные клиенту кредиты (ресурсы); тре- тий столбец – число кредитов, необходимых клиентам. Внизу под- писано число свободных кредитов у банкира.
Вначале проверим, является ли текущее состояние безопас- ным. То есть сможем ли мы предложить стратегию обслуживания клиентов, удовлетворяющую все запросы на кредиты. Для этого бу- дем давать ссуду только тем клиентам, запросы которых в кредитах мы можем покрыть полностью при текущем количестве свободных кредитов у банка. Ниже показана такая стратегия обслуживания.
A
3 9
A
3 9
A
3 9
A
3 9
A
0
-
B
2 4
B
4 4
B
0
-
B
0
-
B
0
-
C
2 7
C
2 7
C
2 7
C
0
-
C
0
-
Свободно 3
Свободно 1
Свободно 5
Свободно 7
Свободно 10
Теперь допустим, что в рассмотренном безопасном состоянии клиент A выставил запрос на один кредит. Рассмотрим гипотетиче- ское состояние, возникающее при удовлетворении такого запроса.
A
3 9
+1
A
4 9
A
4 9
A
8 9
B
2 4
B
2 4
B
0
-
B
0
-
C
2 7
C
2 7
C
2 7
C
2 7
Свободно 3
Свободно 2
Свободно 4
Свободно 0
Небезопасно
Небезопасно
Небезопасно

84
Мы видим, что возникает состояние, в котором не хватает одного кредита для удовлетворения запроса как клиента А (показа- но выше), так и клиента C (определяется аналогично). Оказавшись в таком состоянии, банкир признает банкротство, так как вынуж- ден отказать всем не обслуженным клиентам. То есть система ока- зывается в тупике, следовательно запрос процессом A одного ре- сурса приводит к выходу из безопасного состояния и должен быть отклонен.
Предотвращение при помощи устранения одного из условий
возникновения тупика. Если удастся предложить стратегию работы с ресурсами, в которой исключено хотя бы одно из условий Хоффма- на, тупик не возникнет.
1. Атака взаимного исключения. Пример использования оче- реди печати показывает, что можно избежать захвата принтера.
2. Атака условия удержания и ожидания. Если все ресурсы за- прашиваются одновременно, то тупиков не возникнет. Например, можно использовать функцию WaitForMultipleObjects.
3. Атака условия отсутствия принудительной выгрузки. Реали- зуется при обработке транзакций. Каждый процесс готов освободить захваченные ресурсы по запросу менеджера транзакций.
4. Атака условия циклического ожидания. Если все ресурсы пронумерованы и каждый процесс имеет право захватывать ресурс только с большим порядковым номером, чем номера уже захвачен- ных ресурсов, то тупика не возникнет.
Экзаменационные вопросы по разделу III
1. Абстракция процесса, управление процессами в многозадачной операционной системе. Определение процесса. Диаграмма со- стояния, контекст, дескриптор процесса. Квантование и приори- тетное планирование. Нити (потоки исполнения).
2. Функциональные возможности многозадачности в ОС Windows.
Способы использования многозадачности в приложениях.
3. Планировщик ОС Windows. Класс и уровень приоритета. Пере- ключение контекста. Потоки, не являющиеся готовыми. Дина- мический приоритет.

85 4. Эффект инверсии приоритетов. Пример возникновения инвер- сии. Способы преодоления.
5. Мультипроцессорная обработка в ОС Windows. Термины, вызо- вы API, их назначение.
6. Состояние состязания. Пример возникновения и способ преодо- ления.
7. Средства синхронизации в режиме пользователя в ОС Windows.
Функции, реализующие атомарные операции, объект «критиче- ская секция».
8. Задача о критической секции. Алгоритм Питерсона для двух процессов. Условия задачи. Объяснение принципа работы алго- ритма.
9. Предотвращение агрессивной оптимизации кода с использова- нием модификатора volatile. Эффект голодания, пример возник- новения.
10. Эффект ложного разделения переменных. Пример влияния кэш- линий на скорость исполнения многопоточных программ.
11. Управление объектами ядра в ОС Windows. Описатель объекта.
Таблица описателей объектов процесса. Создание, наследование, именование, дублирование описателей.
12. Средства синхронизации в режиме ядра в ОС Windows. Собы- тия, семафоры, мьютексы.
13. Эффект взаимоблокировки или возникновения тупика. Опреде- ление, условия возникновения, моделирование графами Холта.
14. Стратегия «обнаружение-устранение» для борьбы с взаимобло- кировками. Применение графов Холта и матриц распределения ресурсов.
15. Стратегия избегания блокировок. Диаграмма траектории ресур- сов. Алгоритм банкира для одного вида ресурсов.
16. Предотвращение блокировок путем исключения условий их воз- никновения.

86