Учебный курс Операционные среды, системы и оболочки Лекция 6 Лекции читает доктор технических наук, профессор Назаров Станислав Викторович

Планирование заданий, процессов и потоков 1.Виды планирования Вид планированияВыполняемые функции Долгосрочное Решение о добавлении задания (процесса) в пул выполняемых в системе Среднесрочное Решение о добавлении процесса к числу процессов полностью или частично размещенных в основной памяти Краткосрочное Решение о том, какой из доступных процессов (потоков) будет выполняться процессором Планирование ввода-вывода Решение о том, какой из запросов процессов (потоков) на операцию ввода-вывода будет выполняться свободным устройством ввода- вывода

3 Схема планирования с учетом очередей заданий (процессов) Новый Готовый / Приостановлен- ный Готовый в ОП Выполняющийся в ОП Завершаю- щийся Долгосрочное планирование Вызов ОС Активация Приостановка Приостановка Активация Среднесрочное планирование Освобождение Ожидание события (прерывание ввода- вывода, сообщение) Диспетчеризация (краткосрочное планирование) Тайм-аут (таймер) Блокированный / Приостановленный Диск Диск Блокированный в ОП Наступление события С в о п и н г Наступление события

4 Долгосрочное планирование Тайм-аут Очередь готовых заданий Среднесрочное планирование Очередь готовых приостановленных заданий Очередь заблокированных приостановленных заданий Очередь заблокированных заданий Событие Интерактивные пользователи Пакетные задания Ожидание события ЦП Выход ОП Диск ОП

5 Типичный граф состояния потока ВЫПОЛНЕНИЕ ГОТОВНОСТЬ ОЖИДАНИЕ Поток завершен или ошибка Поток ожидает завершения ввода- вывода или другого события Ввод-вывод завершен (событие произошло) Поток вытеснен (исчерпал квант) Поток выбран на выполнение Вновь созданный поток

6 Алгоритмы планирования потоков 1.Невытесняющие (non-preemptive) планирование распределяется между ОС и прикладными программами; планирование распределяется между ОС и прикладными программами; необходимость частых передач управлений ОС, в противном случае возможна монополизация процессора приложением; необходимость частых передач управлений ОС, в противном случае возможна монополизация процессора приложением; зависания приложений могут привести к краху системы зависания приложений могут привести к краху системы 2. Вытесняющие (preemptive) функции планирования сосредоточены в ОС; функции планирования сосредоточены в ОС; планирование на основе квантования процессорного времени; планирование на основе квантования процессорного времени; планирование на основе приоритетов потоков: статических, динамических, абсолютных, относительных, смешанных; планирование на основе приоритетов потоков: статических, динамических, абсолютных, относительных, смешанных;

7 Простейший алгоритм планирования, реализующий состояния потока по кадру 27 Тайм - аут Процессор Ожидание события Очередь заблокированных потоков Ввод-вывод завершен Новый поток Очередь готовых потоков Выход

8 Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом Ожидание события Тайм - аут Процессор Новый поток Очередь 2 Очередь 1 1.Переключение контекстов потоков связано с потерями процессорного времени. 2.С увеличением времени кванта ухудшается обслуживание пользователей. 3.В алгоритмах, основанных на квантовании, ОС не имеет никаких сведений о характеристиках решаемых задач.

9 Граф состояния потока Выполнение Ожидание Очередь готовых потоков 1 Очередь готовых потоков 2 Вновь созданный поток t КВ Тайм-аут Завершение(ошибка) Событие (завершение ввода-вывода) Запрос ввода- вывода

10 Алгоритмы приоритетного планирования Процессор Назначение приоритета Тайм-аут Очередь высшего приоритета Очередь низшего приоритета Ожидание события Тайм-аут Завершение (ошибка) Новый поток Приоритетное переключение с квантованием

Системные приоритеты Пользоват. приоритеты Наивысший Повышенный Обычный Пониженный Наинизший Поток обнуления страниц Пустой поток Базовый приоритет Наивысший Наинизший Очереди системных потоков и потоков псевдореального времени Наивысший Наинизший ПРОЦЕССОРПРОЦЕССОРПРОЦЕССОРПРОЦЕССОР

12 Изменение базового приоритета потока Увеличение приоритета + 1 – завершение ввода-вывода по диску; + 2 – для последовательной линии; + 6 – клавиатура; + 8 – звуковая карта; + 2 – снимается блокировка по семафору (для потока переднего плана); снимается блокировка по семафору (для потока непереднего плана); приоритет 15 на 2 кванта процессора, если готовый к выполнению поток простаивает более некоторого директивного времени. Уменьшение приоритета - 1 – если полностью использован квант времени процессора (многократно, вплоть до базового приоритета).

13 Резервный (3) Выполняющийся (2) Готовый (1) Ожидание (5) Транзит (6) Завершенный (4) Переключение Вытеснение Блокировка / Приостановка Снятие блокировки / возобновление. Ресурсов достаточно Снятие блокировки. Ресурсов недостаточно Ресурсов достаточно Выбор для выполнения Завершение Работоспособные процессы (потоки) Неработоспособные процессы (потоки) 35 Инициализация (0)

Взаимодействие и синхронизация процессов и потоков Проблемы взаимодействия и синхронизации Степень осведомленности ВзаимосвязьВлияние одного процесса на другой Потенциальные проблемы Процессы не осведо- млены друг о друге Конкуренция Результат работы одного процес- са не зависит от действий других. Возможно влияние одного про цесса на время работы другого. Взаимоисключения Взаимоблокировки Голодание Процессы косвенно осведомлены о наличии друг друга Сотрудничеств о с использо- ванием разде- ления Результат работы одного процесса может зависеть от информации, полученной от других. Возможно влияние одного процесса на время работы другого. Взаимоисключения Взаимоблокировки Голодание Синхронизация Процессы непосредст венно осведомлены о наличии друг друга Сотрудничеств о с исполь- зованием связи Результат работы одного процесса зависит от информации, полученной от других процессов. Возможно влияние одного процесса на время работы другого. Взаимоблокировки (расходуемые ресурсы) Голодание

Конкуренция процессов в борьбе за ресурсы – ситуация, когда два или более процессов требуют доступ к одному и тому же ресурсу (принтеру, файлу и т.п.), называемому. Часть программы, использующая критический ресурс, называется Конкуренция – ситуация, когда два или более процессов требуют доступ к одному и тому же ресурсу (принтеру, файлу и т.п.), называемому критическим. Часть программы, использующая критический ресурс, называется критической секцией. Процесс А Процесс В Процесс А попадает в критическую область TT1TT1 TT2TT2 TT3TT3 TT4TT4 Процесс А покидает критическую область Процесс В пытается попасть в критическую область Процесс В блокирован Процесс В попадает в критическую область Процесс В покидает критическую область T T 1.Процессы не должны одновременно находиться в критических областях. 2.В программе не должно быть предположений о скорости или количестве процессов. 3.Процесс, находящийся вне критической области, не может блокировать другие процессы. 4.Невозможна ситуация, в которой процесс вечно ждет попадания в критическую область. Необходимость взаимоисключений:

16 Взаимоблокировки (тупики, deadlock) Группа процессов находится в, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из этой же группы Группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из этой же группы Процесс Ресурс R1 P2 R2 P1 Исходное распределение ресурсов R1 P2 R2 P1 P2 P1 R1R2 Тупиковая ситуация

17 Проблема голодание R R RR PP1PP1 PP2PP2 PP3PP3 PP1PP1 PP2PP2 PP3PP3 PP1PP1 PP2PP2 PP3PP3 PP1PP1 PP2PP2 PP3PP3 Активный Блокированные БлокированныеАктивный Активный Блокированные Блокированные Активный

Сотрудничество с использованием разделения Процессы, взаимодействующие с другими процессами без наличия явной информации о друг друге, обращаются к разделяемым переменным, к совместно используемым файлам или базам данных. Дополнительно: синхронизация процессов для обеспечения согласованности данных Проблемы: взаимоисключение, взаимоблокировка, голодание. Дополнительно: синхронизация процессов для обеспечения согласованности данных Пример: пусть должно выполняться a = b при начальном значении a = b = 1 Пример: пусть должно выполняться a = b при начальном значении a = b = 1 1-й вариант: процессы выполняются последовательно 1-й вариант: процессы выполняются последовательно P1: a = a + 1; b = b + 1; P2: b = 2 * b; a = 2 * a; P1: a = a + 1; b = b + 1; P2: b = 2 * b; a = 2 * a; 2-й вариант: процессы прерывают друг друга 2-й вариант: процессы прерывают друг друга P1: a = a + 1; прерывание; P2: b = 2 * b; прерывание; P1: a = a + 1; прерывание; P2: b = 2 * b; прерывание; P1: b = b + 1; прерывание; P2: a = 2 * a; P1: b = b + 1; прерывание; P2: a = 2 * a; Согласование нарушено: a = 4, b = 3 Согласование нарушено: a = 4, b = 3 Ситуации, в которых два или более процессов обрабатывают разделяемые данные (файлы) и конечный результат зависит от скоростей процессов (потоков), называются гонками.

Методы взаимоисключений 1.Запрещение прерываний при входе в критическую область и разрешение прерываний после выхода из критической области. Достоинства: простота реализации. Недостатки: монополизация процессора, возможный крах ОС при сбое процесса, невозможность использования в многопроцессорных системах. 2.Блокирующие переменные (программный подход) F(D)=1? Да, свободен Нет, занят Попытка доступа к разделяемому ресурсу D Занять ресурс F(D)=0 Критическая секция (работа с ресурсом D) Освободить ресурс F(D)=1 Неделимая операцияпроверка-установка Команды TC, BTR, BTS процессора Pentium (анализ и присвоение значения логической переменной) Недостатки: необходимость постоянного опроса другими потоками, требующими тот же ресурс, блокирующей переменной; дополнительные затраты процессорного времени.