Основы операционных систем Лекция 3 - 28.02.081 Лекция 3. Планирование процессов Уровни планирования Критерии планирования и требования к алгоритмам Параметры. - презентация

1 Основы операционных систем Лекция Лекция 3. Планирование процессов Уровни планирования Критерии планирования и требования к алгоритмам Параметры планирования Вытесняющее и невытесняющее планирование Алгоритмы планирования

2 Основы операционных систем Лекция Введение Ограниченный набор ресурсов, несколько потребителей Требуется распределение ресурсов между потребителями, или планирование использования ресурсов Планирование должно иметь четко поставленные критерии и алгоритмы, соответствующие критериям и опирающиеся на параметры потребителей В этой лекции: планирование исполнения процессов в мультипрограммных вычислительных системах, или планирование процессов

3 Основы операционных систем Лекция Уровни планирования (1) В первой лекции упоминались два вида планирования в вычислительных системах: планирование заданий и планирование использования процессора Планирование заданий - процедура выбора очередного задания для загрузки в машину, т. е. для порождения соответствующего процесса Стало возможным после появления МД

4 Основы операционных систем Лекция Уровни планирования (2) Планирование использования процессора возникает в мультипрограммных вычислительных системах, где в состоянии готовность могут одновременно находиться несколько процессов Процедуры выбора одного готового процесса, который получит процессор в свое распоряжение, т.е. будет переведен в состояние исполнение Оба вида планирования будем рассматривать как различные уровни планирования процессов

5 Основы операционных систем Лекция Уровни планирования (3) Планирование заданий - долгосрочное планирование процессов Отвечает за порождение новых процессов в системе, определяя степень мультипрограммирования, число процессов, одновременно находящихся в системе Если степень мультипрограммирования системы постоянна, то новые процессы могут появляться только после завершения ранее загруженных

6 Основы операционных систем Лекция Уровни планирования (4) Решение о выборе процесса для запуска оказывает влияние на функционирование вычислительной системы на протяжении достаточно длительного интервала времени В некоторых операционных системах долгосрочное планирование сведено к минимуму В системах разделения времени порождение процесса происходит сразу после появления соответствующего запроса Поддержание разумной степени мультипрограммирования осуществляется за счет ограничения числа пользователей

7 Основы операционных систем Лекция Уровни планирования (5) Планирование использования процессора - краткосрочное планирование процессов Производится при обращении исполняющегося процесса к устройствам ввода-вывода или при завершении некоторого интервала времени Осуществляется весьма часто, как правило, не реже одного раза в 100 миллисекунд Оказывает влияние на функционирование системы до наступления очередного аналогичного события, т. е. в течение короткого промежутка времени

8 Основы операционных систем Лекция Уровни планирования (6) В некоторых ВС бывает выгодно временно удалить какой-либо частично выполнившийся процесс из оперативной памяти на диск, а позже вернуть его обратно для дальнейшего выполнения Swapping (перекачка), в профессиональной литературе используется транслитерация - свопинг Требуется дополнительный промежуточный уровень планирования процессов среднесрочный

9 Основы операционных систем Лекция Критерии планирования и требования к алгоритмам (1) Для каждого уровня планирования процессов можно предложить много различных алгоритмов Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которые желательно достичь, используя планирование

10 Основы операционных систем Лекция Критерии планирования и требования к алгоритмам (2): Цели 1. Справедливость: гарантировать каждому заданию или процессу некоторую часть времени использования процессора в компьютерной системе, не допуская ситуаций, когда процесс одного пользователя постоянно занимает процессор, а процесс другого пользователя фактически не выполняется 2. Эффективность: постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению (в реальных ВС загрузка процессора колеблется от 40 до 90 %)

11 Основы операционных систем Лекция Критерии планирования и требования к алгоритмам (3): Цели 3. Сокращение полного времени выполнения (turnaround time): обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением 4. Сокращение времени ожидания (waiting time): минимизировать время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки 5. Сокращение времени отклика (response time): минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя

12 Основы операционных систем Лекция Критерии планирования и требования к алгоритмам (4): Желательные свойства 1. Предсказуемость: одно и то же задание должно выполняться приблизительно за одно и то же время 2. Минимальные накладные расходы 3. Равномерная загрузка ресурсов ВС с предпочтением процессов, которые будут занимать малоиспользуемые ресурсы 4. Масштабируемость: алгоритмы должны сохранять работоспособность при увеличении нагрузки

13 Основы операционных систем Лекция Критерии планирования и требования к алгоритмам (5) Многие приведенные цели и свойства являются противоречивыми Улучшение работы алгоритма с точки зрения одного критерия ухудшает ее с точки зрения другого критерия Приспособление алгоритма под один класс задач, приводит к дискриминации задач другого класса

14 Основы операционных систем Лекция Параметры планирования (1) Для достижения целей алгоритмы планирования должны опираться на характеристики процессов в системе, заданий в очереди на загрузку, состояния самой вычислительной системы, на параметры планирования Рассмотрим некоторые такие параметры

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

16 Основы операционных систем Лекция Параметры планирования (3) Статические параметры процессов Каким пользователем запущен процесс или сформировано задание? Насколько важной является поставленная задача, т. е. каков приоритет ее выполнения? Сколько процессорного времени запрошено пользователем для решения задачи? Каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода? Какие ресурсы ВС и в каком количестве необходимы заданию?

17 Основы операционных систем Лекция Параметры планирования (4) В алгоритмах долгосрочного планирования используются статические и динамические параметры ВС и статические параметры процессов (динамические параметры процессов на этапе загрузки заданий еще не известны) В алгоритмах краткосрочного и среднесрочного планирования дополнительно учитываются и динамические характеристики процессов

18 Основы операционных систем Лекция Параметры планирования (5) Для среднесрочного планирования в качестве таких характеристик может выступать следующая информация Сколько времени прошло со времени выгрузки процесса на диск или его загрузки в оперативную память? Сколько оперативной памяти занимает процесс? Сколько процессорного времени было уже предоставлено процессу?

19 Основы операционных систем Лекция Параметры планирования (6) Для краткосрочного планирования нужны ввести еще два динамических параметра Промежуток времени непрерывного использования процессора времени непрерывного ожидания называется название CPU burst, а промежуток ввода-вывода – I/O burst Важными динамическими параметрами процесса являются значения последних и очередных CPU burst и I/O burst

20 Основы операционных систем Лекция Вытесняющее и невытесняющее планирование (1) Процесс планирования осуществляется частью ОС, называемой планировщиком Планировщик может принимать решения о выборе для исполнения нового процесса в четырех случаях: 1. Процесс переводится из состояния исполнение в состояние завершение 2. Процесс переводится из состояния исполнение в состояние ожидание 3. Процесс переводится из состояния исполнение в состояние готовность 4. Процесс переводится из состояния ожидание в состояние готовность

21 Основы операционных систем Лекция Вытесняющее и невытесняющее планирование (2) В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и для выполнения всегда необходимо выбрать новый процесс В случаях 3 и 4 планирование может не проводиться; процесс, исполнявшийся до прерывания, может продолжать выполнение после обработки прерывания Если планирование осуществляется только в случаях 1 и 2, то имеет место невытесняющее (nonpreemptive) планирование В противном случае - вытесняющее (preemptive) планирование

22 Основы операционных систем Лекция Вытесняющее и невытесняющее планирование (3) Невытесняющее планирование использовалось, например, в MS Windows 3.1 и ОС Apple Macintosh Процесс занимает столько процессорного времени, сколько ему необходимо Переключение процессов возникает только при желании исполняющегося процесса Метод планирования относительно просто реализуем и достаточно эффективен (редкая смена контекста) Проблема возможности полного захвата процессора одним процессом (программа может зациклиться) Спасает только перезагрузка ВС

23 Основы операционных систем Лекция Вытесняющее и невытесняющее планирование (4) Вытесняющее планирование обычно используется в системах разделения времени Процесс может быть приостановлен в любой момент своего исполнения ОС устанавливает специальный таймер для генерации сигнала прерывания по истечении некоторого интервала времени кванта После прерывания процессор передается в распоряжение следующего процесса Квантование гарантирует приемлемые времена отклика и предотвращают зависание ВС из-за зацикливания какой-либо программы

24 Основы операционных систем Лекция Алгоритмы планирования (1) Существует большой набор алгоритмов планирования, которые предназначены для достижения различных целей и эффективны для разных классов задач Многие из них могут быть использованы на нескольких уровнях планирования Рассмотрим некоторые наиболее употребительные алгоритмы применительно к процессу кратковременного планирования

25 Основы операционных систем Лекция Алгоритмы планирования (2) First-Come, First-Served (FCFS) Простейший алгоритм - First Come, First Served (первым пришел, первым обслужен) Процессы, находящиеся в состоянии готовность, организованы в очередь Когда процесс переходит в состояние готовность, ссылка на его PCB, помещается в конец очереди Новый процесс для исполнения выбирается из начала очереди с удалением оттуда ссылки на его PCB Очередь FIFO - First In, First Out

26 Основы операционных систем Лекция Алгоритмы планирования (3) First-Come, First-Served (FCFS) Невытесняющее планирование Процесс, получивший в свое распоряжение процессор, занимает его до истечения своего текущего CPU burst После этого для выполнения выбирается новый процесс из начала очереди Преимуществом алгоритма FCFS является простота реализации Но у него имеется и много недостатков

27 Основы операционных систем Лекция Алгоритмы планирования (4) First-Come, First-Served (FCFS) Процесс p0p0 p1p1 p2p2 Продолжительность очередного CPU burst 1341 Пусть в состоянии готовность находятся три процесса p 0, p 1 и p 2, для которых известны времена их очередных CPU burst Эти времена приведены в таблице в некоторых условных единицах Будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало

28 Основы операционных систем Лекция Алгоритмы планирования (5) First-Come, First-Served (FCFS) исполнение готовность p0p0 p1p1 p2p2 Первым выбирается процесс p 0, получающий процессор на все время своего CPU burst (13 единиц времени) После его окончания в состояние исполнение переводится процесс p 1, занимая процессор на 4 единицы времени Наконец, возможность работать получает процесс p 2 Среднее время ожидания в этом случае ( )/3 = 10 единиц времени Среднее полное время выполнения ( )/3 = 16 единиц времени

29 Основы операционных систем Лекция Алгоритмы планирования (6) First-Come, First-Served (FCFS) исполнение готовность p0p0 p1p1 p2p2 Время ожидания для процесса p 0 равняется 5 единицам времени, для процесса p единице, для процесса p единиц Среднее время ожидания в этом случае ( )/3 = 2 единиц времени Полное время выполнения для процесса p единиц времени, для процесса p единиц, для процесса p единица Среднее полное время выполнения ( )/3 = 6 единиц времени

30 Основы операционных систем Лекция Алгоритмы планирования (7) First-Come, First-Served (FCFS) Среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди При наличии процесса с длительным CPU burst короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала своего выполнения Алгоритм FCFS практически неприменим для систем разделения времени

31 Основы операционных систем Лекция Алгоритмы планирования (8) Round Robin (RR) Вариант FCFS, реализованный в режиме вытесняющего планирования Готовые процессы организованы циклически - сидят на карусели Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно миллисекунд Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться

32 Основы операционных систем Лекция Алгоритмы планирования (9) Round Robin (RR) RR реализуется с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO Для очередного исполнения выбирается процесс, расположенный в начале очереди; устанавливается таймер для генерации прерывания по истечении кванта времени

33 Основы операционных систем Лекция Алгоритмы планирования (10) Round Robin (RR) При выполнении процесса возможны два варианта: 1. Время непрерывного использования процессора (остаток текущего CPU burst), требующееся процессу, меньше или равно кванта времени процесс освобождает процессор до истечения кванта времени, на исполнение выбирается новый процесс из начала очереди, и таймер начинает отсчет кванта заново 2. Продолжительность остатка текущего CPU burst процесса больше кванта времени по истечении кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале

34 Основы операционных систем Лекция Алгоритмы планирования (11) Round Robin (RR) время p0p0 ИИИИГГГГГИИИИИИИИИ p1p1 ГГГГИИИИ p2p2 ГГГГГГГГИ Предыдущий пример с порядком процессов p 0, p 1, p 2 и размером кванта – 4 Состояния процессов показаны на протяжении соответствующей единицы времени: столбец с номером 1 соответствует промежутку времени от 0 до 1 Среднее время ожидания - ( )/3 = 5,6(6) единицы времени Среднее полное время - ( )/3 = 11,6(6) единицам времени Средние времена ожидания и выполнения для обратного порядка процессов не отличаются от случая FCFS (2 и 6 единиц соответственно)

35 Основы операционных систем Лекция Алгоритмы планирования (12) Round Robin (RR) время p0p0 ИГГИГИГИГИИИИИИИИИ p1p1 ГИГГИГИГИ p2p2 ГГИ На производительность алгоритма RR сильно влияет величина кванта времени Тот же пример c порядком процессов p 0, p 1, p 2 для величины кванта времени равной 1 Среднее время ожидания - ( )/3 = 4 единицы времени Среднее полное время исполнения - ( )/3 = 10 единиц

36 Основы операционных систем Лекция Алгоритмы планирования (13) Round Robin (RR) При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS При очень малых величинах создается иллюзия того, что каждый из n процессов работает на своем собственном виртуальном процессоре с производительностью ~ 1/n от производительности реального процессора Накладные расходы на переключение резко снижают производительность системы

37 Основы операционных систем Лекция Алгоритмы планирования (13) Shortest-Job-First (SJF) Для алгоритмов FCFS и RR является существенным порядок расположения процессов в очереди процессов готовых к исполнению Если короткие задачи расположены в ближе к началу очереди, то общая производительность возрастает Если знать время следующих CPU burst для готовых процессов, то можно выбрать для исполнения процесс с минимальной длительностью CPU burst Если таких процессов несколько, то для выбора можно использовать FCFS (без квантования времени) Кратчайшая работа первой, или Shortest Job First (SJF).

38 Основы операционных систем Лекция Алгоритмы планирования (14) Shortest-Job-First (SJF) В качестве алгоритма краткосрочного планирования SJF может быть как вытесняющим, так и невытесняющим При невытесняющем планировании процессор предоставляется избранному процессу на все требующееся ему время, независимо от событий в ВС При вытесняющем SJF-планировании учитывается появление новых процессов в очереди готовых к исполнению во время работы выбранного процесса Если CPU burst нового процесса меньше, чем остаток CPU burst у исполняющегося, то исполняющийся процесс вытесняется новым

39 Основы операционных систем Лекция Алгоритмы планирования (15) Shortest-Job-First (SJF) Процессp0p0 p1p1 p2p2 p3p3 Продолжительность очередного CPU burst 5371 Пример работы невытесняющего алгоритма SJF В состоянии готовность находятся четыре процесса p 0, p 1, p 2 и p 3, для которых известны времена их очередных CPU burst Вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, процессы не совершают операций ввода-вывода, переключения контекста пренебрежимо мало

40 Основы операционных систем Лекция Алгоритмы планирования (16) Shortest-Job-First (SJF) время p0p0 ГГГГИИИИИ p1p1 ГИИИ p2p2 ГГГГГГГГГИИИИИИИ p3p3 И Среднее время ожидания SJF - ( )/4 = 3,5 единицы Для алгоритма FCFS при порядке процессов p 0, p 1, p 2, p 3 - ( )/4 = 7 Для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса всех невытесняющих алгоритмов

41 Основы операционных систем Лекция Алгоритмы планирования (17) Shortest-Job-First (SJF) ПроцессВремя появления в очередиПродолжительность очередного CPU burst p0p0 06 p1p1 22 p2p2 67 p3p3 05 Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов p 0, p 1, p 2 и p 3 с различными временами CPU burst и различными моментами их появления в очереди процессов готовых к исполнению

42 Основы операционных систем Лекция Алгоритмы планирования (18) Shortest-Job-First (SJF) В начальный момент времени в состоянии готовность находятся p 0 и p 3 Меньшее время очередного CPU burst оказывается у процесса p 3, он и выбирается По прошествии 2-х единиц времени в систему поступает процесс p 1 Время его CPU burst меньше, чем остаток CPU burst у процесса p 3, и p 3 вытесняется По прошествии еще 2-х единиц времени процесс p 1 завершается, и вновь выбирается p 3 В момент t = 6 в очереди p 2, но нужно 7 единиц времени, а процессу p 3 осталось работать 2 единицы времени, остается p 3 После завершения p 3 в момент t = 7 в очереди p 0 и p 2, выбирается p 0 Последним получает возможность выполняться процесс p 2 Время p0p0 ГГГГГГГИИИИИИ p1p1 ИИ p2p2 ГГГГГГГИИИИИИИ p3p3 ИИГГИИИ

43 Основы операционных систем Лекция Алгоритмы планирования (19) Shortest-Job-First (SJF) Основная сложность при реализации SJF - невозможность точного знания очередного CPU burst для исполняющихся процессов В пакетных системах объем процессорного времени, требующееся заданию для выполнения, указывает пользователь Можно использовать для долгосрочного SJF- планирования Укажет больше времени, чем нужно - будет ждать получения результата дольше Если укажет меньшее время, задача может не досчитаться до конца

44 Основы операционных систем Лекция Алгоритмы планирования (20) Shortest-Job-First (SJF) При краткосрочном планировании можно только прогнозировать длительности следующего CPU burst, исходя из предыстории работы процесса Пусть (n) - величина n-го CPU burst, (n + 1) - предсказываемое значение для (n + 1)-го CPU burst, – некоторая величина в диапазоне от 0 до 1 Определим рекуррентное соотношение (n + 1) = (n) + (1- ) (n) (0) положим произвольной константой Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию

45 Основы операционных систем Лекция Алгоритмы планирования (21) Shortest-Job-First (SJF) При = 0 мы перестаем следить за последним поведением процесса, фактически полагая (n) = (n-1) = … = (0) Все CPU burst оцениваются одинаково, исходя из некоторого начального предположения Положив = 1, забываем о предыстории процесса Полагается, что время очередного CPU burst равно времени последнего CPU burst: (n+1) = (n) Обычно выбирают = ½ для равноценного учета последнего поведения и предыстории Tакой выбор удобен и для быстрой организации вычисления оценки (n + 1)

46 Основы операционных систем Лекция Алгоритмы планирования (22) Гарантированное планирование При интерактивной работе пользователей в ВС можно применить алгоритм планирования, гарантирующий, что каждый пользователь будет иметь в своем распоряжении часть процессорного времени Пронумеруем пользователей от до Для пользователя с номером i введем i - время нахождения пользователя в системе и i - суммарное процессорное время, уже выделенное всем его процессам в течение сеанса

47 Основы операционных систем Лекция Алгоритмы планирования (23) Гарантированное планирование Справедливым было бы получение i / процессорного времени Если i > i /, то система явно благоволит к пользователю с номером i Вычислим для каждого пользовательского процесса значение коэффициента справедливости i i и будем предоставлять очередной квант времени процессу с наименьшей величиной этого коэффициента

48 Основы операционных систем Лекция Алгоритмы планирования (24) Гарантированное планирование Алгоритм гарантированного планирования Недостаток - невозможность предугадать поведение пользователей Если некоторый пользователь отлучится, не прерывая сеанса работы, то по возвращении его процессы будут получать неоправданно много процессорного времени

49 Основы операционных систем Лекция Алгоритмы планирования (25) Приоритетное планирование Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования Каждому процессу присваивается некоторое числовое значение - приоритет, в соответствии с которым ему выделяется процессор Процессы с одинаковыми приоритетами планируются в порядке FCFS

50 Основы операционных систем Лекция Алгоритмы планирования (26) Приоритетное планирование Для SJF в качестве приоритета выступает оценка следующего CPU burst Чем меньше значение этой оценки, тем выше приоритет процесса Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости Чем он меньше, тем больше приоритет у процесса

51 Основы операционных систем Лекция Алгоритмы планирования (27) Приоритетное планирование Принципы назначения приоритетов могут опираться как на внутренние критерии ВС, так и на внешние Внутренние - различные количественные и качественные характеристики процесса Ограничения на время использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних I/O burst к CPU burst и т. д. Внешние критерии - важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и другие политические факторы

52 Основы операционных систем Лекция Алгоритмы планирования (28) Приоритетное планирование Приоритетное планирование может быть как вытесняющим, так и невытесняющим При вытесняющем планировании процесс с более высоким приоритетом, появившийся в очереди готовых процессов, вытесняет исполняющийся процесс с более низким приоритетом В случае невытесняющего планирования он просто становится в начало очереди готовых процессов Примеры

53 Основы операционных систем Лекция Алгоритмы планирования (29) Приоритетное планирование Пусть в очередь готовых процессов поступают те же процессы, что и в примере для алгоритма SJF, но им присвоены приоритеты Большее значение соответствует меньшему приоритету, т.е. наиболее приоритетным является процесс p 3, а наименее приоритетным - процесс p 0 ПроцессВремя появления в очереди Продолжительность очередного CPU Burst Приоритет p0p0 064 p1p1 223 p2p2 672 p3p3 051

54 Основы операционных систем Лекция Алгоритмы планирования (30) Приоритетное планирование Первым для выполнения в момент времени t = 0 выбирается процесс p 3 После его завершения в момент времени t = 5 в очереди готовых p 0 и p 1. Больший приоритет из них у процесса p 1, он и начнет выполняться. Затем в момент времени t = 8 для исполнения будет избран процесс p 2, и лишь потом p 0. Невытесняющий вариант: Врем я p0p0 ГГГГГГГГГГГГГГИИИИИИ p1p1 ГГГИИ p2p2 ГИИИИИИИ p3p3 ИИИИИ

55 Основы операционных систем Лекция Алгоритмы планирования (31) Приоритетное планирование Первым, как и в предыдущем случае, исполняться начнет процесс p 3, а по его окончании процесс p 1 Но в момент времени t = 6 он будет вытеснен процессом p 2 и продолжит свое выполнение только в момент времени t = 13 Последним, как и раньше будет исполнен процесс p 0. В случае вытесняющего приоритетного планирования: Врем я p0p0 ГГГГГГГГГГГГГГИИИИИИ p1p1 ГГГИГГГГГГГИ p2p2 ИИИИИИИ p3p3 ИИИИИ

56 Основы операционных систем Лекция Алгоритмы планирования (32) Приоритетное планирование В примерах приоритеты процессов не изменялись со временем – статические Легко реализовать, небольшие издержки на выбор наиболее приоритетного процесса Однако статические приоритеты не реагируют на изменения ситуации в ВС Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов

57 Основы операционных систем Лекция Алгоритмы планирования (33) Приоритетное планирование Начальное значение динамического приоритета, присвоенное процессу, действует в течение короткого времени После этого назначается новое, более подходящее значение приоритета Единственная операция над процессами, которую мы не обсуждали Изменение приоритета процессов проводится согласованно с совершением других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении кванта времени или по завершении процесса

58 Основы операционных систем Лекция Алгоритмы планирования (34) Приоритетное планирование Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования Схемы с динамическими приоритетами гораздо сложнее в реализации и связаны с большими издержками по сравнению со статическими схемами Однако их использование предполагает, что эти издержки оправдываются улучшением поведения системы

59 Основы операционных систем Лекция Алгоритмы планирования (35) Приоритетное планирование Проблема приоритетного планирования: при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут быть не запущены неопределенно долгое время Случается одно из двух: 1. Дожидаются своей очереди на исполнение 2. Вычислительную систему приходится выключать, и они теряются

60 Основы операционных систем Лекция Алгоритмы планирования (36) Приоритетное планирование Решение: увеличение со временем значения приоритета процесса, находящегося в состоянии готовность Пусть изначально процессам присваиваются приоритеты от 128 до 255 Каждый раз, по истечении некоторого промежутка времени, значения приоритетов готовых процессов уменьшаются на 1 Процессу, побывавшему в состоянии исполнение, восстанавливается первоначальное значение приоритета

61 Основы операционных систем Лекция Алгоритмы планирования (37) Многоуровневые очереди (Multilevel Queue) Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность Очередям приписываются фиксированные приоритеты Внутри очередей для планирования могут применяться разные алгоритмы Для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR Подход многоуровневых очередей повышает гибкость планирования: для процессов с различными характеристиками применяется наиболее подходящий им алгоритм

62 Основы операционных систем Лекция Алгоритмы планирования (38) Многоуровневые очереди с обратной связью Развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи Процесс не постоянно приписан к определенной очереди Может мигрировать из очереди в очередь, в зависимости от своего поведения

63 Основы операционных систем Лекция Алгоритмы планирования (39) Многоуровневые очереди с обратной связью Родившийся процесс поступает в очередь 0 При выборе на исполнение получает квант времени размером 8 единиц Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0 Иначе переходит в очередь 1 Для процессов из очереди 1 квант равен 16 Если укладывается - остается в очереди 1 Иначе переходит в очередь 2 - квант 32 Если не укладывается, - в очередь 3 без квантования времени

64 Основы операционных систем Лекция Алгоритмы планирования (40) Многоуровневые очереди с обратной связью Миграция процессов в обратном направлении может осуществляться по различным принципам После завершения ожидания ввода с клавиатуры процессы из очередей 1, 2 и 3 могут помещаться в очередь 0 После завершения дисковых операций ввода-вывода процессы из очередей 2 и 3 могут помещаться в очередь 1 После завершения ожидания всех других событий - из очереди 3 в очередь 2

65 Основы операционных систем Лекция Алгоритмы планирования (41) Многоуровневые очереди с обратной связью Многоуровневые очереди с обратной связью - наиболее общий подход к планированию процессов из числа рассмотренных Наиболее трудоемки в реализации, но в то же время они обладают наибольшей гибкостью Для полного описания их конкретного воплощения необходимо указать: Количество очередей для процессов, находящихся в состоянии готовность Алгоритм планирования, действующий между очередями Алгоритмы планирования, действующие внутри очередей Правила помещения родившегося процесса в одну из очередей Правила перевода процессов из одной очереди в другую

66 Основы операционных систем Лекция Заключение (1) Для распределения процессорного времени между процессами в ВС применяется процедура планирования процессов Различают краткосрочное, среднесрочное и долгосрочное планирование процессов Конкретные алгоритмы планирования процессов зависят от поставленных целей, класса решаемых задач и опираются на статические и динамические параметры процессов и компьютерных систем Различают вытесняющий и невытесняющий режимы планирования

67 Основы операционных систем Лекция Заключение (2) Простейшим алгоритмом планирования является невытесняющий алгоритм FCFS, который, однако, может существенно задерживать короткие процессы, не вовремя перешедшие в состояние готовность В системах разделения времени широкое распространение получила вытесняющая версия этого алгоритма RR Среди невытесняющих алгоритмов оптимальным с точки зрения среднего времени ожидания процессов является алгоритм SJF В интерактивных системах часто используется алгоритм гарантированного планирования

68 Основы операционных систем Лекция Заключение (3) Алгоритм SJF и алгоритм гарантированного планирования являются частными случаями планирования с использованием приоритетов В более общих методах приоритетного планирования применяются многоуровневые очереди процессов и многоуровневые очереди с обратной связью Будучи наиболее сложными в реализации, эти способы планирования обеспечивают гибкое поведение вычислительных систем и их адаптивность к решению задач разных классов