СодержаниеВведение
1. Ресурсы
1.1. Выгружаемые и невыгружаемые ресурсы
1.2. Получение ресурса
2. Введение во взаимоблокировки
2.1.Условия взаимоблокировки
2.2. Моделирование взаимоблокировок
3. Страусовый алгоритм
4. Обнаружение и устранение взаимоблокировок
4.1. Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
4.2. Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа
4.3. Выход из взаимоблокировки
5. Избежание взаимоблокировок
5.1. Траектории ресурсов
5.2. Безопасные и небезопасные состояния
5.3. Алгоритм банкира для одного вида ресурсов
5.4. Алгоритм банкира для нескольких видов ресурсов
6. Предотвращение взаимоблокировок
6.1. Атака условия взаимного исключения
6.2. Атака условия удержания и ожидания
6.3. Атака условия отсутствия принудительной выгрузки ресурса
6.4. Атака условия циклического ожидания
7. Сопутствующие вопросы
7.1. Двухфазовое блокирование
7.2. Тупики без ресурсов
7.3. Голодание
8. Исследования в области взаимоблокировок
ВыводВведениеВ компьютерных системах существует большое количество ресурсов, каждый из которых в конкретный момент времени может использоваться только одним процессом. В качестве таких примеров можно привести принтеры, накопители на магнитной ленте и элементы внутренних таблиц системы. Появление двух процессов, одновременно передающих данные на принтер, приведет к печати бессмысленного набора символов. Наличие двух процессов, использующих один и тот же элемент таблицы файловой системы, обязательно станет причиной разрушения файловой системы. Поэтому все операционные системы обладают способностью предоставлять процессу эксклюзивный доступ (по крайней мере, временный) к определенным ресурсам.
Часто для выполнения прикладных задач процесс нуждается в исключительном доступе не к одному, а к нескольким ресурсам. Предположим, например, что каждый из двух процессов хочет записать отсканированный документ на компакт-диск. Процесс А запрашивает разрешение на использование сканера и получает его. Процесс В запрограммирован по-другому, поэтому сначала запрашивает устройство для записи компакт-дисков и также получает его. Затем процесс А обращается к устройству для записи компакт-дисков, но запрос отклоняется до тех пор, пока это устройство занято процессом В. К сожалению, вместо того чтобы освободить устройство для записи компакт-дисков, В запрашивает сканер. В этот момент процессы заблокированы и будут вечно оставаться в этом состоянии. Такая ситуация называется тупиком, тупиковой ситуацией или взаимоблокировкой.
Взаимоблокировки могут возникать между различными машинами. Во многих офисах есть локальная сеть, включающая в себя множество компьютеров. Часто такие устройства, как сканеры, устройства для записи компакт-дисков, принтеры и накопители на магнитной ленте, присоединены к сети как ресурсы совместного доступа, то есть доступны любому пользователю на любой машине. Если эти ресурсы позволяется резервировать удаленно (то есть с домашней машины пользователя), может возникнуть аналогичный описанному выше вид тупиковых ситуаций. Более сложные ситуации могут стать причиной тупиков, вовлекающих три, четыре и более устройств и пользователей.
Взаимоблокировки могут произойти во множестве других ситуаций помимо запросов выделенных устройств ввода-вывода. В системах баз данных программа может оказаться вынужденной заблокировать несколько записей, чтобы избежать состояния конкуренции. Если процесс A блокирует запись R1, процесс В блокирует запись R2, а затем каждый процесс попытается заблокировать чужую запись, мы также окажемся в тупике. Таким образом, взаимоблокировки появляются при работе как с аппаратными, так и с программными ресурсами.Литература1. Ахо В., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы М.: Вильямс, 2001
2. Беляков М.И., Рабовер Ю.И., Фридман А.Л. Мобильная операционная система М.:, Радио и связь, 1991
3. Блэк У. Интернет: протоколы безопасности. Учебный курс Спб.: Издательский дом Питер, 2001
4. Брамм П., Брамм Д. Микропроцессор 80386 и его применение М., Мир, 1990
5. Вахалия Ю. UNIX изнутри Спб.: Издательский дом Питер, 2003
6. Дейтел Г. Введение в операционные системы М.: Мир, 1987
7. Дунаев С. Unix. System V. Release 4.2 М.: Диалог МИФИ, 1996
8. Казаринов Ю.М., Номоконов В.М., Подклетнов Г.С., Филиппов Ф.М. Микропроцессорный комплекс К1810 М.: Высшая школа, 1990
9. Кастер Хелен Основы Windows NT и NTFS М.: Русская ред. 1996
10. Керниган Б. В, Пайк Р. UNIX - универсальная среда программирования М.: Финансы и статистика. 1992
11. Коффрон Дж. Технические средства микропроцессорных систем М.: Мир, 1983
12. Олифер В.Г., Олифер Н.А. Новые технологии и оборудование IP-сетей Спб.: BHV, 2000
13. Олифер В.Г., Олифер Н.А. Сетевые операционные системы Спб.: Издательский дом Питер, 2001
14. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы Спб.: Издательский дом Питер, 2002
15. Снейдер Й. Эффективное программирование TCP/IP Издательский дом Питер, 2001
16. Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000 СПб: Издательский дом Питер, М.: Русская редакция, 2001
17. Стивенс У. UNIX: Взаимодействие процессов СПб: Издательский дом Питер, 2002
18. Стивенс У. UNIX: разработка сетевых приложений СПб: Издательский дом Питер, 2003
19. Столлингс В. Операционные системы М.: Вильямс, 2001
20. Таненбаум Э. Современные операционные системы СПб.: Издательский дом Питер, 2002
21. Таненбаум Э. Компьютерные сети СПб.: Издательский дом Питер, 2003
22. Таненбаум Э., Ван Стеен М. Распределенные системы. Принципы и парадигмы СПб.: Издательский дом Питер, 2003
23. Робачевский А. Операционная система UNIX Спб.: BHV, 1999
24. Цикритис Д., Бернстайн Ф. Операционные системы М.: Мир. 1977
|
|
