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

40 40 Константин Коньков Основы организации операционных систем Microsoft Windows Академия Microsoft Академия Microsoft Обычно в состоянии "Готовности" имеется очередь готовых к выполнению (running) потоков. В данном случае это состояние распадается на три составляющих. Это, собственно, состояние "Готовности (Ready)"; состояние "Готов. Отложен (Deferred Ready)", что означает, что поток выбран для выполнения на конкретном процессоре, но пока не запланирован к выполнению; и, наконец, состояние "Простаивает (Standby)", в котором может находиться только один выбранный к выполнению поток для каждого процессора в системе. В состоянии "Ожидания (Waiting)" поток блокирован и ждет какого-либо события, например, завершения операции ввода-вывода. При наступлении этого события поток переходит в состояние "Готовности". Этот путь может проходить через промежуточное "Переходное (Transition)" состояние в том случае, если стек ядра потока выгружен из памяти. Код ядра выполняется в контексте текущего потока. Это означает, что при прерывании, системном вызове и т д., то есть когда процессор переходит в режим ядра и управление передается ОС, переключения на другой поток (например, системный) не происходит. Контекст потока при этом сохраняется, поскольку операционная система все же может принять решение о смене характера деятельности и переключении на другой поток. Вследствие этого в некоторых курсах по операционным системам состояние "Выполнение" разделяют на "Выполнение в режиме пользователя" и "Выполнение в режиме ядра". 2

3

4 Уровни планирования процессов Долгосрочное планирование – планирование заданий. Долгосрочное планирование – планирование заданий. Среднесрочное планирование – swapping. Среднесрочное планирование – swapping. Краткосрочное планирование – планирование использования процессора. Краткосрочное планирование – планирование использования процессора.

5 Цели планирования Справедливость Справедливость Эффективность Эффективность Сокращение полного времени выполнения (turnaround time) Сокращение полного времени выполнения (turnaround time) Сокращение времени ожидания (waiting time) Сокращение времени отклика (response time)

6 Желаемые свойства алгоритмов планирования Предсказуемость Предсказуемость Минимизация накладных расходов. Минимизация накладных расходов. Равномерность загрузки вычислительной системы. Равномерность загрузки вычислительной системы. Масштабируемость. Масштабируемость.

7 Параметры планирования Статические параметры вычислительной системы – например, предельные значения ее ресурсов. Статические параметры вычислительной системы – например, предельные значения ее ресурсов. Статические параметры процесса – кем запущен, степень важности, запрошенное процессорное время, какие требуются ресурсы и т.д. Статические параметры процесса – кем запущен, степень важности, запрошенное процессорное время, какие требуются ресурсы и т.д. Динамические параметры вычислительной системы – например, количество свободных ресурсов в данный момент. Динамические параметры вычислительной системы – например, количество свободных ресурсов в данный момент. Динамические параметры процесса – текущий приоритет, размер занимаемой оперативной памяти, использованное процессорное время и т.д. Динамические параметры процесса – текущий приоритет, размер занимаемой оперативной памяти, использованное процессорное время и т.д. статические динамические

8 CPU burst и I/O burst Важные динамические параметры процесса a=1 b=2 read c Ожидание окончания ввода a=a+c b print a Ожидание окончания вывода CPU burst I/O burst

9 Вытесняющее и невытесняющее планирование 1. Перевод процесса из состояния исполнение в состояние закончил исполнение 2. Перевод процесса из состояния исполнение в состояние ожидание Принятие только вынужденных решений – невытесняющее планирование 3. Перевод процесса из состояния исполнение в состояние готовность 4. Перевод процесса из состояния ожидание в состояние готовность Принятие вынужденных и невынужденных решений – вытесняющее планирование Вынужденное принятие решения Невынужденное принятие решения

Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 FCFS (First Come – First Served) t P0P0P0P0 P1P1P1P1 P2P2P2P2 исполнение готовность готовность исполнение исполнение Процессы P1P1P1P1 Продолжительность CPU burst

Алгоритмы планирования FCFS (First Come – First Served) t180 P0P0P0P0 P1P1P1P1 P2P2P2P2 исполнение готовность готовность 1 исполнение 5 исполнение 18 Процессы P2P2P2P2 P1P1P1P1 P0P0P0P0 Продолжительность CPU burst 1413

12 Алгоритмы планирования RR (Round Robin) Процесс 1 Процесс 2 Процесс 3 Процесс 4 готовность готовность исполнение Процессор Процесс 3 готовность готовность Процесс 2 исполнение Процесс 3

13 Алгоритмы планирования RR (Round Robin) Процесс 1 Процесс 3 готовность готовность исполнение Процессор готовность Процесс 4 готовность Процесс 3 Процесс 2 Процесс 1

14 Алгоритмы планирования Остаток времени CPU burst <= кванта времени: Остаток времени CPU burst <= кванта времени: –процесс освобождает процессор до истечения кванта; –на исполнение выбираем новый процесс из начала очереди готовых; Остаток времени CPU burst >= кванта времени: Остаток времени CPU burst >= кванта времени: –По окончании кванта процесс помещается в конец очереди готовых к исполнению процессов; –на исполнение выбираем новый процесс из начала очереди готовых. RR (Round Robin)

15 Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 RR (Round Robin) время P0P0P0P0 P1P1P1P1 P2P2P2P2 Величина кванта времени – 4 ИИИИ ГГ ГГ ГГГ Г P0P0P0P0 P1P1P1P1 P2P2P2P2 Очередь готовых исполнение P1P1P1P1 ИИИИ ГГГГ ГГГГ И ГИИИИИИИИИ

16 Алгоритмы планирования Процессы P0P0P0P0 P1P1P1P1 P2P2P2P2 Продолжительность CPU burst 1341 RR (Round Robin) время P0P0P0P0 P1P1P1P1 P2P2P2P2 Величина кванта времени – 1 И Г Г P0P0P0P0 P1P1P1P1 P2P2P2P2 Очередь готовых P0P0P0P0 исполнение P1P1P1P1 P2P2P2P2 P0P0P0P0 P2P2P2P2 P0P0P0P0 P0P0P0P0 P1P1P1P1 И Г Г P1P1P1P1 P2P2P2P2 P1P1P1P1 И Г Г P0P0P0P0 P1P1P1P1 И Г P1P1P1P1 И Г И Г И Г И ГИ ГИИИИ И И И ИИ

17 Алгоритмы планирования SJF (Shortest Job First) ПроцессыP0P0 P1P1 P2P2 P3P3 Продолжительность CPU burst 5371 невытесняющий время P0P0 P1P1 P2P2 P3P3 И Г Г Г ИИИ ГГГ ГГГИИИИИ ГГ Г ГГ И ИИИИИИ P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2

18 Алгоритмы планирования ПроцессыP0P0 P1P1 P2P2 P3P3 Продолжительность CPU burst6255 Момент появления в очереди 0260 SJF (Shortest Job First) вытесняющий И Г P0P0P0P0 P1P1P1P1 P2P2P2P2 готовность P3P3P3P3 исполнение P3P3P3P3 P1P1P1P1 P0P0P0P0 P2P2P2P2 время P0P0 P1P1 P2P2 P3P3 Г И И И ГГ ГГИИ ГГ И Г ГИИИИИ ГГГГГИИИИИИ