- •Оглавление
- •7.1. Основные понятия 37
- •8.1. Основные понятия 47
- •14.1. Основные понятия 77
- •Введение
- •Раздел 1. Основные сведения об операционных системах Тема 1. Функции и классификация операционных систем
- •1.1. Функции ос
- •1.1. История ос
- •По назначению
- •По режиму обработки задач
- •1.3. Классификация ос
- •По способу взаимодействия с пользователем
- •По принципу построения
- •Вопросы для самоконтроля
- •Тема 2. Структура операционных систем. Системные вызовы
- •2.1. Структура ос
- •Монолитная структура (структура макроядра)
- •Иерархическая структура (многослойное ядро)
- •Структура микроядра
- •2.2. Выполнение системных вызовов
- •2.3. Понятие операционной и программной среды
- •Вопросы для самоконтроля
- •Раздел 2. Процессы и потоки Тема 3. Процессы
- •3.1. Основные сведения о процессах
- •Создание процессов
- •Завершение процессов
- •Иерархия процессов
- •3.2. Модели процесса Модель с двумя состояниями
- •Модель с пятью состояниями
- •3.3. Описание процессов
- •3.4. Управление процессами Создание процессов
- •Переключение процессов
- •3.5. Выполнение кода ос по отношению к процессам
- •Ядро вне процессов (автономное ядро)
- •Ядро в составе пользовательских процессов
- •Ос на основе процессов
- •Вопросы для самоконтроля
- •Тема 4. Системные вызовы управления процессами в ос unix
- •4.1. Создание процесса
- •4.2. Завершение процесса
- •4.3. Изменение образа памяти процесса
- •4.4. Синхронизация между родительским и дочерним процессами
- •4.5. Состояние "зомби"
- •Вопросы для самоконтроля
- •Тема 5. Сигналы в ос unix
- •5.1. Назначение сигналов
- •5.2. Обработка сигналов
- •5.3. Посылка сигнала процессу
- •Вопросы для самоконтроля
- •Тема 6. Потоки
- •6.1. Основные понятия
- •6.2. Основные операции с потоками
- •6.3. Способы реализации потоков в пространстве пользователя
- •В пространстве ядра
- •Смешанная реализация
- •Вопросы для самоконтроля
- •Тема 7. Взаимоблокировки
- •7.1. Основные понятия
- •Типы доступа к ресурсу
- •Условия возникновения взаимоблокировок
- •7.2. Моделирование взаимоблокировок
- •7.3. Обнаружение взаимоблокировок Обнаружение взаимоблокировок при наличии одного ресурса каждого типа
- •Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа
- •7.4. Избежание взаимоблокировок Безопасные и небезопасные состояния
- •Алгоритм банкира для одного вида ресурса
- •Алгоритм банкира для нескольких видов ресурсов
- •Вопросы для самоконтроля
- •Раздел 3. Взаимодействие процессов Тема 8. Проблема взаимного исключения и способы ее решения
- •8.1. Основные понятия
- •8.2. Аппаратные способы достижения взаимного исключения Запрещение прерываний
- •Специальные команды, выполняющиеся атомарно
- •8.3. Программные способы достижения взаимного исключения Переменные блокировки.
- •Алгоритм Деккера
- •Алгоритм Петерсона
- •Вопросы для самоконтроля
- •Тема 9. Примитивы синхронизации
- •9.1. Семафоры Определение семафора
- •Применение семафоров
- •9.2. Мьютексы
- •9.3. Мониторы
- •Структура монитора
- •Вопросы для самоконтроля
- •Тема 10. Классические проблемы межпроцессного взаимодействия
- •10.1. Проблема производителя и потребителя
- •10.2. Задача о читателях и писателях
- •10.3. Задача об обедающих философах
- •10.4. Задача о спящем парикмахере
- •10.5. Задача о железнодорожном перегоне
- •Вопросы для самоконтроля
- •Тема 11. Межпроцессное взаимодействие в ос unix
- •11.1. Неименованные каналы
- •Синхронизирующие свойства неименованного канала
- •Системные вызовы для работы с неименованными каналами
- •Шаги в установлении связи через неименованный канал
- •Ограничения неименованных каналов
- •11.2. Именованные каналы
- •Использование именованных каналов
- •Синхронизирующие свойства именованных каналов
- •Системные вызовы для работы с именованными каналами
- •11.3. Очереди сообщений
- •11.4. Разделяемая память
- •Вопросы для самоконтроля
- •Тема 12. Передача сообщений
- •12.1. Характеристика систем передачи сообщений
- •12.2. Модель клиент-сервер
- •Вопросы для самоконтроля
- •Тема 13. Api сокетов ос unix
- •13.1. Межпроцессное взаимодействие при помощи сокетов
- •13.2. Системные вызовы работы с сокетами в ос unix Структура адреса сокета
- •Получить дескриптор сокета (создать сокет)
- •Указать адрес локальной оконечной точки
- •Перевод сокета в пассивный режим
- •Принять соединение с сокетом
- •Установить соединение с сервером.
- •Чтение данных из сокета и запись данных в сокет
- •Операции клиента и сервера
- •14.2. Критерии краткосрочного планирования.
- •14.3. Стратегии краткосрочного планирования. Первым поступил – первым обслужен
- •Кратчайшая задача – первая
- •Наименьшее оставшееся время выполнения
- •Циклическое планирование
- •Приоритетное планирование
- •Вопросы для самоконтроля
- •Раздел 5. Управление памятью Тема 15. Технологии распределения памяти
- •15.1. Фиксированное распределение
- •15.2. Динамическое распределение
- •15.3. Система двойников
- •15.4. Простая страничная организация
- •15.5. Простая сегментная организация
- •Вопросы для самоконтроля
- •Тема 16. Виртуальная память
- •16.1. Предпосылки для организации виртуальной памяти
- •16.2. Страничная организация виртуальной памяти
- •Структура таблицы страниц
- •16.3. Сегментация
- •16.4. Комбинация сегментации и страничной организации
- •16.5. Алгоритмы управления виртуальной памятью
- •Стратегия выборки
- •Стратегия размещения.
- •Стратегия замещения
- •Вопросы для самоконтроля
- •Раздел 6. Ввод-вывод и файловая система Тема 17. Ввод-вывод
- •17.1. Принципы программного обеспечения ввода-вывода
- •Способы осуществления ввода-вывода
- •17.2. Программные уровни ввода-вывода
- •Обработчики прерываний
- •Драйверы устройств
- •Независимое от устройств программное обеспечение ввода-вывода
- •Программное обеспечение ввода-вывода пространства пользователя
- •Вопросы для самоконтроля
- •Тема 18. Физическая организация файловой системы
- •18.1. Цели и задачи файловой системы
- •18.2. Устройство диска
- •18.3. Физическая организация и адресация файла
- •Вопросы для самоконтроля
- •Тема 19. Логическая организация файловой системы
- •19.1. Типы файлов
- •19.2. Иерархическая структура файловой системы
- •Имена файлов
- •Монтирование
- •19.3. Атрибуты файлов
- •Вопросы для самоконтроля
- •Литература
- •Перечень сокращений
7.3. Обнаружение взаимоблокировок Обнаружение взаимоблокировок при наличии одного ресурса каждого типа
Необходимым и достаточным условием взаимоблокировки в такой ситуации является наличие цикла в графе ресурсов.
Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа
Пусть n – число процессов P1, P2, …, Pn; m – число классов ресурсов R1, R2, …, Rm; Ei – количество единиц ресурса класса i; E – вектор существующих ресурсов, содержащий общее количество имеющихся в системе единиц каждого ресурса; A – вектор доступных ресурсов, элемент этого вектора Ai – количество единиц ресурса Ri, доступных в данный момент; C – матрица текущего распределения, элемент этой матрицы Cij – количество единиц ресурса Rj, используемое процессом Ri; R – матрица запросов, элемент этой матрицы Rij – количество единиц ресурса Rj, которое запрашивает процесс Pi.
Эти четыре структуры показаны на рис. 7.3.
Будем считать, что для двух векторов A и B: AB тогда и только тогда, когда AiBi, 1im.
Алгоритм будет ставить на процессах отметку, служащую признаком того, что они могут закончить работу и, следовательно, не находятся в тупике. После завершения алгоритма любой немаркированный процесс находится в состоянии тупика. Алгоритм обнаружения тупиков состоит из следующих шагов.
Ищем немаркированный процесс Pi, для которого i-ая строка матрицы A.
Если такой процесс найден, прибавляем i-ую строку матрицы C к вектору A, маркируем процесс и возвращаемся к шагу 1.
Если таких процессов не существует, работа алгоритма заканчивается.
На первом шаге алгоритм ищет процесс, который может доработать до конца, т.е. все требуемые для него ресурсы должны быть доступны. Возвращаем занятые процессом ресурсы в общий фонд ресурсов. Процесс маркируем как завершенный. Если окажется, что все процессы могут работать, тогда ни один из них в данный момент не заблокирован.
Для иллюстрации работы алгоритма рассмотрим рис. 7.4. Здесь есть три процесса и четыре класса ресурсов, например, накопители на магнитной ленте (НМЛ), плоттеры, сканеры и устройство для чтения компакт-дисков. Процесс 1 использует один сканер. Процесс 2 занял два НМЛ и устройство для чтения компакт-дисков. Процесс 3 занимает плоттер и два сканера. Каждый процесс нуждается в дополнительном устройстве, как показывает матрица R.
Работая с алгоритмом обнаружения взаимоблокировок, мы ищем процесс, чей запрос ресурсов может быть удовлетворен. Требования первого процесса нельзя выполнить, потому что в системе нет доступного устройство для чтения компакт-дисков. Запросы второго процесса также нельзя удовлетворить, т.к. нет свободных сканеров. Но третий процесс может получить все желаемое, следовательно, он работает, завершается и возвращает все свои ресурсы, давая
A = (2 2 2 0 ).
С этого момента может выполняться процесс 2, по окончании возвращая свои ресурсы в систему. Мы получим:
A = (4 2 2 1 ).
Теперь может работать оставшийся процесс. В этой системе не возникает взаимоблокировки.
Теперь немного изменим вариант, изображенный на рис. 7.3. Пусть процесс 3, кроме двух НМЛ и плоттера, нуждается также и в устройстве для чтения компакт-дисков. Тогда ни один из запросов не может быть удовлетворен, значит, вся система находится в тупике.
