В ос windows реализовано вытесняющее планирование

Введение

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

Выбранный для выполнения поток работает в течение некоего периода, называемого квантом, по истечении которого поток вытесняется, то есть процессор передается другому потоку. Предполагается, что поток не знает, в какой момент он будет вытеснен. Поток также может быть вытеснен даже, если его квант еще не истек. Это происходит, когда к выполнению готов поток с более высоким приоритетом.

Процедура планирования обычно связана с весьма затратной процедурой диспетчеризации — переключением процессора на новый поток, поэтому планировщик должен заботиться об эффективном использовании процессора. Принадлежность потоков к процессу при планировании не учитывается, то есть единицей планирования в ОС Windows является именно поток. Запуск процедуры планирования удобно проиллюстрировать на упрощенной (по сравнению с диаграммой, изображенной на
рис.
5.3) диаграмме состояний потока, см.
рис.
6.1.

Картинка с сайта: intuit.ru

Рис.
6.1.
Упрощенная диаграмма состояний потоков в ОС Windows

Наиболее важным вопросом планирования является выбор момента для принятия решения. В ОС Windows запуск процедуры планирования вызывается одним из следующих событий.

Это, во-первых, события, связанные с освобождением процессора.

(1) Завершение потока

(2) Переход потока в состояние готовности в связи с тем, что его квант времени истек

(3) Переход потока в состояние ожидания

Во-вторых, это события, в результате которых пополняется или может пополниться очередь потоков в состоянии готовности.

(4) Поток вышел из состояния ожидания

(5) Поток только что создан

(6) Деятельность текущего потока может иметь следствием вывод другого потока из состояния ожидания.

В последнем случае выведенный из состояния ожидания поток может сразу же начать выполняться, если имеет высокий приоритет.

Наконец, процедура планирования может быть запущена, если изменяется приоритет потока в результате вызова системного сервиса или самой Windows, а также если изменяется привязка (affinity) потока к процессору, из-за чего поток не может больше выполняться на текущем процессоре.

Заметим, что переключение из пользовательского режима в режим ядра (и обратно) не влияет на планирование потока, так как контекст в этом случае не меняется.

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

Перевод потока из состояния ожидания в состояние готовности (вариант 4) может быть следствием прерывания, свидетельствующим об окончании операции ввода-вывода. В этом случае процедура планирования может быть отложена (deffered procedure call) до окончания выполнения высокоприоритетного системного кода.

Иногда подобный переход происходит в результате деятельности другого потока, который, например, выполнил операцию up на семафоре (пример 6-го варианта). Хотя этот другой поток и может продолжить работу, он должен запустить процедуру планирования, поскольку в очереди готовности могут оказаться потоки с более высоким приоритетом. По тем же причинам планирование осуществляется в случае запуска нового потока.

Алгоритмы планирования

Приоритеты

В ОС Windows реализовано вытесняющее приоритетное планирование, когда каждому потоку присваивается определенное числовое значение — приоритет, в соответствии с которым ему выделяется процессор. Потоки с одинаковыми приоритетами планируются согласно алгоритму Round Robin (карусель). Важным достоинством системы является возможность вытеснения потоков, работающих в режиме ядра — код исполнительной системы полностью реентерабелен. Не вытесняются лишь потоки, удерживающие спин-блокировку (см.
«Синхронизация потоков»
). Поэтому спин-блокировки используются с большой осторожностью и устанавливаются на минимальное время.

В системе предусмотрено 32 уровня приоритетов. Шестнадцать значений приоритетов (16-31) соответствуют группе приоритетов реального времени, пятнадцать значений (1-15) предназначены для обычных потоков, и значение 0 зарезервировано для системного потока обнуления страниц (см.
рис.
6.2).

Картинка с сайта: intuit.ru

Рис.
6.2.
Приоритеты потоков

Чтобы избавить пользователя от необходимости запоминать числовые значения приоритетов и иметь возможность модифицировать планировщик, разработчики ввели в систему слой абстрагирования приоритетов. Например, класс приоритета для всех потоков конкретного процесса можно задать с помощью набора констант-параметров функции SetPriorityClass, которые могут иметь следующие значения:

• реального времени ( REALTIME_PRIORITY_CLASS ),
• высокий ( HIGH_PRIORITY_CLASS ),
• выше нормы ( ABOVE_NORMAL_PRIORITY_CLASS ),
• нормальный ( NORMAL_PRIORITY_CLASS ),
• ниже нормы ( BELOW_NORMAL_PRIORITY_CLASS )
• и неработающий ( IDLE_PRIORITY_CLASS ).

Относительный приоритет потока устанавливается аналогичными параметрами функции SetThreadPriority:

Совокупность из шести классов приоритетов процессов и семи классов приоритетов потоков образует 42 возможные комбинации и позволяет сформировать так называемый базовый приоритет потока (см. таб. 6.1).

Базовый приоритет процесса и первичного потока по умолчанию равен значению из середины диапазонов приоритетов процессов (24, 13, 10, 8, 6 или 4). Смена приоритета процесса влечет за собой смену приоритетов всех его потоков, при этом их относительные приоритеты остаются без изменений.

Приоритеты с 16 по 31 в действительности приоритетами реального времени не являются, поскольку в рамках поддержки мягкого реального времени, которая реализована в ОС Windows, никаких гарантий относительно сроков выполнения потоков не дается. Это просто более высокие приоритеты, которые зарезервированы для системных потоков и тех потоков, которым такой приоритет дает пользователь с административными правами. Тем не менее, наличие приоритетов реального времени, а также вытесняемость кода ядра, локализация страниц памяти (см.
«Функционирование менеджера памяти»
) и ряд дополнительных возможностей — все это позволяет выполнять в среде ОС Windows приложения мягкого реального времени, например, мультимедийные. Системный поток с нулевым приоритетом занимается обнулением страниц памяти. Обычные пользовательские потоки могут иметь приоритеты от 1 до 15.

Лекция 5.

Планирование и диспетчеризация
потоков. Динамическое и статическое
планирование. Вытесняющие и невытесняющие
алгоритмы планирования. Алгоритмы
планирования, основанные на квантовании.
Алгоритмы планирования, основанные на
приоритетах. Планирование в ОС Windows.

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

Планирование потоков включает в себя
решение двух задач:

• Определение момента времени для смены
  текущего активного потока;

• Выбор для выполнения потока из очереди
  готовых потоков.

Существует множество различных алгоритмов
планирования потоков, преследующих
различные цели и обеспечивающих разное
качество мультипрограммирования. Именно
особенности этих алгоритмов определяют
специфику операционной системы, в
частности, является ли она системой
пакетной обработки, системой разделения
времени или системой реального времени.

Существуют два типа планирования –
динамическое и статическое. В большинстве
операционных систем универсального
назначения планирование осуществляется
динамически (on-line), то есть
решения принимаются во время работы
системы на основе анализа текущей
ситуации. ОС работают в условиях
неопределенности – потоки и процессы
появляются в случайные моменты времени
и также непредсказуемо завершаются.
Динамические планировщики могут гибко
приспосабливаться к изменяющейся
ситуации и не используя никаких априорных
предположений. Для того чтобы оперативно
найти в таких условиях оптимальный
порядок выполнения задач, операционная
система должна затрачивать значительные
усилия.

Другой тип планирования – статический
– может быть использован в специализированных
системах, в которых весь набор одновременно
выполняемых задач определен заранее
(например, в системах реального времени).
Планировщик называется статическим
(предварительным планировщиком), если
он принимает решения не во время работы
системы, а заранее (off-line). Для планирования
статическому планировщику нужны как
можно более полные предварительные
знания о характеристиках набора задач:
максимальном времени выполнения каждой
задачи, ограничениях предшествования,
ограничениях по предельным срокам
выполнения и т.п.

Накладные расходы ОС при статическом
планировании ниже, чем при динамическом,
так как решения принимаются не во время
работы операционной системы, а заранее.
Фактически ОС в этом случае затрачивает
время лишь на диспетчеризацию
потоков/процессов.

Диспетчеризация заключается в реализации
найденного в результате планирования
(динамического или статического) решения,
о есть в переключении процессора с
одного потока на другой. Диспетчеризация
сводится к следующему:

• сохранение контекста текущего потока,
  который требуется прервать;

• загрузка контекста нового потока,
  выбранного в результате планирования;

• запуск нового потока на выполнение.

Все множество алгоритмов планирования
можно разделить на два класса: вытесняющие
и невытесняющие алгоритмы.

Невытесняющие (non-preemptive) алгоритмы
планирования основаны на том, что
активному потоку позволяется выполняться,
пока он сам, по собственной инициативе,
не отдаст управление операционной
системе для того, чтобы та выбрала из
очереди другой готовый к выполнению
поток.

Вытесняющие (preemptive) алгоритмы – это
способы планирования, в которых решение
о переключении процессора с выполнения
одного потока на выполнение другого
потока принимается операционной
системой, а не активной задачей.

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

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

Такой подход может оказаться неудобным
как для пользователей операционной
системы, которые могут потерять контроль
над ОС в результате слишком долгой
работы приложения, так и для разработчиков
прикладных программ, вынужденных
возлагать на себя часть работы
планировщика, создавая приложения с
учетом одновременной работы нескольких
программ.

При определенных условиях невытесняющие
алгоритмы могут оказаться более
эффективными, поскольку:

• исключаются нерациональные прерывания
  программ в «неудобные» для них моменты
  времени;

• легко разрешаются проблемы совместного
  использования данных, так как задача
  Вов время выполнения может быть уверена,
  что в это время никто другой не изменит
  данные;

• повышается скорость переключения с
  потока на поток.

Практически во всех современных ОС
(UNIX, Linux, Windows)
реализованы вытесняющие алгоритмы
планирования потоков (процессов).
Примером эффективного использования
невытесняющего планирования являются
ОС NetWare 3.x и 4.x., ориентированных на высокую
скорость выполнения файловых операций.

В основе многих вытесняющих алгоритмов
планирования лежит концепция квантования.
В соответствии с этой концепцией каждому
потоку поочередно для выполнения
предоставляется непрерывный период
процессорного времени – квант.
Смена активного потока происходит,
если:

• поток завершился и покинул систему;

• произошла ошибка;

• поток перешел в состояние ожидания;

• исчерпан квант процессорного времени,
  отведенный данному потоку.

Поток, который исчерпал свой квант,
переводится в состояние готовности и
ожидает, когда ему будет предоставлен
новый квант процессорного времени, а
на выполнение в соответствии с определенным
правилом выбирается новый поток из
очереди готовых.

Кванты, выделяемые потокам, могут быть
одинаковыми для всех потоков или
различными. Также кванты, выделяемые
потоку, могут быть фиксированной длины
или меняться в разные периоды жизни
потока. От алгоритмов выделения квантов
зависит, будет ли операционная система
давать предпочтение коротким или длинным
задачам, предназначена ли ОС для
интерактивной работы одновременно
нескольких пользователей и т.д.

Предположим, что всем потокам
предоставляются кванты одинаковой
длины Q. Если в системе N потоков, то
время, которое поток проводит в ожидании
следующего кванта, можно грубо оценить
как Q(N-1). Чем больше потоков в системе,
тем больше время ожидания и тем меньше
возможности вести одновременную
интерактивную работу нескольким
пользователям. Для того, чтобы пользователь
не ощущал дискомфорта от присутствия
в системе других пользователей, необходимо
выбирать величину кванта очень небольшой.
Типичное значение кванта в системах
разделения времени составляет десятки
миллисекунд.

Чем больше квант, тем выше вероятность,
что потоки завершатся в результате
первого же цикла выполнения. Предположим,
что первоначально каждому потоку
назначается достаточно большой квант,
а величина каждого следующего кванта
уменьшается до некоторой заранее
заданной величины. В таком случае
преимущество получают более короткие
задачи, которые успевают выполниться
в течение первого кванта, а длительные
вычисления будут проводиться в фоновом
режиме.

Представим обратную ситуацию — каждый
следующий квант больше предыдущего.
Этот подход позволяет уменьшить накладные
расходы на переключение задач в случае,
когда сразу несколько задач выполняют
длительные вычисления. Понятно, что
затраты на переключение контекста есть
величина постоянная (для данной ОС и
данного компьютера) и не зависят от
кванта времени. Поэтому в общем случае,
чем больше квант, тем меньше суммарные
накладные расходы, связанные с
переключением потоков.

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

Такая ситуация продемонстрирована на
рис. 5.1. Поток A, выбранный для
выполнения ранее, полностью исчерпал
свой квант времени и переведен в другую
очередь. Планировщик выберет для
выполнения поток B, затем C.

Рис. 5.1. Квантование с предпочтением
потоков, интенсивно обращающихся к
вводу-выводу.

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

В различных ОС приоритет выражается
по-разному. Он может быть целым и дробным,
положительным и отрицательным. В
некоторых ОС приоритет потока тем выше,
чем больше число, в других – наоборот.

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

Во многих ОС предусматривается возможность
изменения приоритетов в течение жизни
потока. Изменение приоритета может
происходить по инициативе самого потока,
когда он обращается с соответствующим
системным вызовом к ОС, или по инициативе
пользователя, когда он выполняет
соответствующую команду. Кроме того,
ОС сама может изменить приоритеты
потоков в зависимости от ситуации,
складывающейся в системе. В последнем
случае приоритеты называются динамическими
в отличие от неизменных, фиксированных
приоритетов.

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

Существуют две разновидности приоритетного
планирования: обслуживание с относительными
приоритетами и обслуживание с абсолютными
приоритетами. В обоих случаях выбор
потока на выполнение осуществляется
одинаково: выбирается поток, имеющий
наивысший приоритет. На рисунке 5.2.
показана ситуация, когда из всех готовых
потоков на выполнение выбирается поток
B, который имеет высший среди всех готовых
потоков приоритет и стоит первым в
очереди.

Картинка с сайта: studfile.net

Рис. 5.2. Приоритетное планирование

Однако проблема определения момента
смены активного потока решается
по-разному. В системах с относительными
приоритетами активный поток выполняется
до тех пор, пока он сам не покинет
процессор, перейдя в состояние ожидания
(или произойдет ошибка, или поток
завершится). В системах с абсолютными
приоритетами выполнение активного
потока прерывается кроме указанных
причин, если в очереди готовых потоков
появился поток, приоритет которого выше
приоритета активного потока. В этом
случае прерванный поток переходит в
состояние готовности.

Системы с относительными приоритетами
позволяют минимизировать затраты на
переключение процессора с одного потока
на другой. Однако, здесь могут возникать
ситуации, когда один поток занимает
процессор долгое время. Ясно, что такой
вариант обслуживания не годится для
систем реального времени и систем
разделения времени, но может быть
использован в системах пакетной
обработки.

Во многих операционных системах алгоритмы
планирования построены с использованием
как концепции квантования, так и
приоритетов. Например, в основе
планирования лежит квантование, но
величина кванта и/или порядок выбора
потока из очереди готовых определяется
приоритетами потоков. Возможен вариант,
когда приоритет при этом будет меняться
в зависимости от того, использовал поток
квант времени полностью или нет.

Например, операционная система Windows
использует квантование в сочетании с
динамическими абсолютными приоритетами.
Рассмотрим механизм планирования в
Windows подробнее.

В Windows предусмотрено 32 уровня приоритетов
– от 0 до 31. Эти значения группируются
следующим образом:

• шестнадцать уровней реального времени
  (16-31);

• пятнадцать динамических уровней (1-15);

• один системный уровень (0), зарезервированный
  для потока обнуления страниц (zero page
  thread).

Уровни приоритета потока назначаются
с учетом двух разных точек зрения:
Windows API и ядра Windows. Windows
API сначала упорядочивает
процессы по классам приоритета,
назначенным при их создании, а затем –
по относительному приоритету индивидуальных
потоков в рамках процессов. Существуют
6 классов процессов: Real-Time (реального
времени, базовое значение 24), High (высокий,
базовое значение 13), Above Normal (выше
нормального, базовое значение 10), Normal
(нормальный, базовое значение 8), Below
Normal (ниже нормального,
базовое значение 6), Idle
(простаивающий, базовое значение 4). В
Windows определены следующие относительные
приоритеты потоков: Time-critical
(критичный по времени), Highest (наивысший,
+2 к приоритету процесса), Above-normal (выше
нормального, +1 к приоритету процесса),
Normal (нормальный, как у
процесса), Below-normal
(ниже нормального, -1 от приоритета
процесса), Lowest (наименьший,
-2 от приоритета процесса) и Idle
(простаивающий). Базовый приоритет
каждого потока в Windows API устанавливается,
исходя из класса приоритета его процесса
и относительного приоритета самого
потока. Связь между приоритетами Windows
API и внутренними приоритетами ядра
Windows показана на рис. 5.3.

Если у процесса только одно значание
приоритета – базовое, то у каждого
потока их два – текущее и базовое. В
определенных обстоятельствах операционная
система может на короткое время повышать
приоритеты потоков в динамическом
диапазоне. Windows никогда
не меняет приоритеты потоков в диапазоне
реального времени, поэтому у таких
потоков базовый приоритет идентичен
текущему.

Начальный базовый приоритет потока
наследуется от базового приоритета
процесса, а тот наследует его от
родительского процесса. Обычно базовый
приоритет процесса по умолчанию равен
значению из середины диапазонов
приоритетов процессов (24,13,10,8,6 или 4).
Однако базовый приоритет некоторых
системных процессов несколько превышает
значение по умолчанию для класса Normal.
Это обеспечивает запуск потоков этих
процессов с приоритетом выше 8.

Картинка с сайта: studfile.net

Рис. 5.3. Взаимосвязь приоритетов в ядре
и Windows API.

Каждый поток в Windows выполняется в течение
отведенного ему кванта времени. По его
окончании Windows проверяет, ожидает ли
выполнения другой поток с таким же
уровнем приоритета. Если на момент
истечения кванта других потоков с тем
же уровнем приоритета нет, Windows выделяет
текущему потоку еще один квант.

По умолчанию в Windows 2000 и XP потоки
выполняются в течение 2 интервалов
таймера, а в системах Windows Server – 12. Это
сделано для того, чтобы в серверных
системах уменьшить расходы на переключение
контекста. Величина кванта для каждого
процесса хранится в блоке процесса ядра
и используется, когда потоку предоставляется
новый квант. Когда поток выполняется,
его квант уменьшается по истечении
каждого интервала таймера, и в конечном
счете срабатывает алгоритм обработки
завершения кванта – происходит момент
планирования потоков.

В процессе работы поток может неоднократно
переходить из состояния в состояния.
Посмотрим, каким образом будет происходить
выбор нового потока для выполнения.

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

выполняющийся поток может быть вытеснен
потоком с более высоким приоритетом.
Это может произойти, если:

• завершилось ожидание потока с более
  высоким приоритетом (т. е. произошло
  событие, которого он ждал);

• приоритет потока увеличился или
  уменьшился.

В случае вытеснения приоритет потока
не меняется, сам он переводится в
состояние готовности и помещается в
начало очереди готовых потоков с данным
приоритетом. После завершения вытеснившего
потока вытесненный сможет отработать
остаток своего кванта.

И, наконец, поток может полностью
израсходовать свой квант процессорного
времени. В этом случае Windows снижает
приоритет потока и выбирает на выполнение
поток из очереди готовых с приоритетом
выше нового приоритета текущего потока.
снизить приоритет можно только до
значения базового приоритета потока.

Приоритет потока может не только
понижаться, но и повышаться. Windows
может динамически повышать значение
текущего приоритета в следующих случаях:

• после завершения операции ввода-вывода;

• после окончания ожидания на событии
  или семафоре исполнительной системы;

• по окончании операции ожидания потоками
  активного процесса;

• при пробуждении GUI-потоков из-за операций
  с окнами;

• если поток, готовый к выполнению,
  задерживается из-за нехватки процессорного
  времени.

По завершении операций ввода-вывода
Windows повышает приоритет потока на
величину, зависящую от устройства
ввода-вывода. Например, после операций
ввода-вывода с диском или CD-ROM приоритет
увеличивается на 1, после сетевых операций
– на 2. Операции с мышью и клавиатурой
увеличивают приоритет на 6. Приоритет
потоков, владеющих окнами, повышается
на 2 уровня после их пробуждения из=за
активности подсистемы управления
окнами, например, при получении оконных
сообщений.

Приоритет всегда повышается относительно
базового, а не текущего уровня. Независимо
от приращения приоритет потока никогда
не будет больше 15. Иными словами, если
к потоку с базовым приоритетом 14 применить
динамическое повышение на 6 уровней,
его приоритет возрастет лишь до 15.

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

Соседние файлы в папке ОС архив

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Оцениваем алгоритмы планирования процессов в операционных системах

Картинка с сайта: habr.com

Планирование процессов в операционных системах — это как умение акробата балансировать на тонкой нити. Этот незаметный сложный механизм определяет, как ваш компьютер управляет своими ресурсами. На первый взгляд все кажется просто: переключайте задачи на процессоре как можно быстрее, чтобы минимизировать время простоя и максимизировать общую производительность. Но в реальности это глубокий исследовательский вопрос, который требует учета множества факторов: приоритетов задач, доступности ресурсов и оптимизации. Давайте разбираться вместе!

Используйте навигацию, если не хотите читать текст полностью:

→ Потоки и процессы
→ Описание алгоритмов планирования
→ FIFO
→ RR
→ SJF
→ Метрики оценки производительности
→ Описание прикладной задачи
→ Реализация и симуляция алгоритмов
→ Результаты симуляций и их анализ
→ Заключение

Потоки и процессы

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

Однако термины «планирование процессов» и «планирование потоков» часто используются как синонимы. Для простоты я буду использовать термин «планирование процессов» при упоминании общих концепций планирования, а «планирование потоков» — для обозначения идей, специфичных для потоков.

Картинка с сайта: habr.com

Описание алгоритмов планирования

Итак, ядро — базовая вычислительная единица ЦП, на которой выполняется процесс. То есть под «запуском на ЦП» обычно подразумевается выполнение процесса именно на ядре ЦП.

Источник.

В системе с одним ядром одновременно может выполняться только один процесс. Остальные в это время ждут, когда оно освободится. Если процессов в данный момент нет, ЦП простаивает.

Это противоречит идее мультипрограммирования, в котором мы стараемся использовать все время работы ЦП продуктивно. Идея проста: процесс выполняется по кругу до завершения запроса ввода-вывода. То есть, если есть несколько процессов, они встают в очередь и выполняются друг за другом. Если процесс один, он крутится до тех пор, пока не появится новый. Когда это происходит, операционная система дожидается завершения процесса, забирает у него ЦП и передает новому.

В многоядерной системе концепция загрузки ЦП распространяется на все процессорные ядра системы. Такое планирование — фундаментальная функция операционной системы, которой уделяется наибольшее внимание.

Выполнение процесса начинается с загрузки процессора. За этим следует цепочка пакетов ввода-вывода и, наконец, последний всплеск частоты ЦП заканчивается системным запросом на прекращение выполнения. Речь не о повышении тактовой частоты процессора, а о периодах его активности при выполнении процессов. Длительность этого всплеска заметно различается от процесса к процессу и от компьютера к компьютеру. Но, как правило, график изменения частоты ЦП имеет вид, как на рисунке ниже.

Картинка с сайта: habr.com

Кривая обычно характеризуется как экспоненциальная или гиперэкспоненциальная, с большим количеством коротких и небольшим — длинных всплесков частоты ЦП.

Важно, что графики будут разными для программ, связанных с вводом-выводом, и программ, привязанным к ЦП. Первые обычно имеют много коротких всплесков частоты процессора. Вторые — несколько длительных. Такое распределение может быть важным при реализации алгоритма планирования.

Каждый раз, когда ЦП простаивает, операционная система должна выбрать один из процессов в очереди готовности для выполнения. За это отвечает планировщик: он выбирает из памяти процесс, готовый к выполнению, и выделяет ему ЦП. Концептуально можно сказать, что все процессы выстраиваются в очередь, чтобы запуститься на процессоре. Записи в очередях обычно представляют собой блоки управления процессами — PCB, или process control block.

Решения по планированию ЦП могут приниматься при следующих обстоятельствах.

• Процесс переключается из состояния выполнения в состояние ожидания (например, в результате запроса ввода-вывода или вызова wait() для завершения дочернего процесса).
• Процесс переходит из состояния выполнения в состояние готовности (например, при возникновении прерывания).
• Процесс переходит из состояния ожидания в состояние готовности (например, при завершении ввода-вывода).
• Процесс завершается.

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

Практически все современные операционные системы, включая Windows, macOS, Linux и UNIX, используют алгоритмы упреждающего планирования. К сожалению, оно может привести к состояниям гонки, когда данные распределяются между несколькими процессами.

Предлагаю рассмотреть случай двух процессов, которые совместно используют данные. Пока один обновляет их, он вытесняется, чтобы второй мог работать. Затем второй процесс пытается прочитать данные, которые находятся в противоречивом состоянии.

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

Что произойдет, если процесс будет вытеснен в середине этих изменений и ядру (или драйверу устройства) потребуется прочитать или изменить ту же структуру? Наступит хаос. Ядра операционной системы могут быть спроектированы как с вытесняющим, так и с невытесняющим режимом. Невытесняющее ядро будет ждать завершения системного вызова или блокировки процесса, ожидая завершения ввода-вывода, прежде чем выполнять переключение контекста.

Эта схема гарантирует простоту структуры ядра, поскольку оно не будет вытеснять процесс, пока структуры его данных находятся в несогласованном состоянии. К сожалению, эта модель плохо подходит для поддержки вычислений в реальном времени. Большинство современных операционных систем теперь полностью вытесняют работу в режиме ядра.

Хотя большинство современных архитектур ЦП имеют несколько процессорных ядер, я рассказываю о планировании в контексте только одного. То есть ниже я опишу ситуации, когда нам доступен один процессор с одним ядром. Следовательно, воображаемая система способна одновременно запускать только один процесс.

FIFO

FIFO (First In, First Out), также известный как FCFS (First Come, First Serve), является простейшим алгоритмом составления расписания. Он просто ставит процессы в очередь выполнения в том порядке, в котором они поступают.

Принцип работы

Когда процесс попадает в очередь готовности, его блок управления процессом привязывается к хвосту. Когда процессор освобождается, он выделяется процессу, а после завершения удаляет его из очереди.

Стоит сказать, что код планирования FIFO прост в написании и понимании. Вместе с тем, среднее время ожидания в соответствии с политикой этого алгоритма часто бывает довольно продолжительным. Сейчас разберем это подробнее.

Рассмотрим следующий набор процессов, пребывающих в момент времени 0, с продолжительностью загрузки ЦП, заданной в миллисекундах:

Если процессы поступают в последовательности P1, P2, P3 и обслуживаются в порядке FIFO, получаем результат, показанный на диаграмме Ганта. Это гистограмма, которая иллюстрирует конкретный график, включая время начала и окончания каждого из участвующих процессов:

Картинка с сайта: habr.com

Источник.

Мы видим, что время ожидания составляет 0 мс для процесса P1, 24 миллисекунды для P2 и 27 мс для P3. Таким образом, среднее время ожидания составляет (0 + 24 + 27)/3 = 17 мс. Однако если процессы поступают в порядке P2, P3, P1, результаты будут другими:

Картинка с сайта: habr.com

Источник.

Среднее время ожидания теперь составляет (6 + 0 + 3)/3 = 3 мс. Это существенное сокращение. Пример наглядно показывает, что среднее время ожидания в соответствии с политикой FIFO обычно не минимально и может существенно меняться, если время загрузки процессов на ЦП сильно различается.

Теперь рассмотрим производительность планирования FIFO в динамической ситуации. Предположим, у нас есть процесс, привязанный к процессору (назовем его P1), и множество процессов, связанных с вводом-выводом. Поскольку они протекают вокруг системы, может возникнуть следующий сценарий.

P1 получит и удержит ЦП. За это время все остальные процессы завершат ввод-вывод и перейдут в очередь готовности. Пока они ждут, операции ввода-вывода устройства простаивают. В конце концов, P1 завершит нагрузку на ЦП и перейдет к устройству ввода-вывода.

Все процессы, связанные с вводом-выводом, которые имеют короткие нагрузки на ЦП, выполняются быстро и возвращаются в очереди ввода-вывода. В этот момент процессор простаивает. P1 затем вернется в очередь готовности, и ему будет выделен ЦП. Опять же, все процессы ввода-вывода в конечном итоге ждут в очереди готовности, пока не завершится P1. Возникает эффект конвоя, поскольку все остальные процессы ждут, пока один большой процесс выйдет из ЦП. Этот эффект приводит к более низкой загрузке ЦП и устройств, чем это было бы возможно, если бы более коротким процессам разрешалось запускаться первыми.

Алгоритм FIFO не является вытесняющим. Забрав ЦП, процесс сохраняет его либо до своего завершения, либо до появления запроса ввода-вывода. То есть FIFO особенно неприятен для интерактивных систем, где важно, чтобы каждый процесс получал долю ресурсов ЦП через определенные промежутки времени. Было бы катастрофой позволить одному процессу удерживать процессор в течение длительного периода времени.

Преимущества и недостатки

Преимущества FIFO

• Простота реализации и понимания.
• Минимальные накладные расходы на планирование, так как переключение контекста происходит только при завершении процесса.
• Отсутствие стагнации (starvation) процессов, так как каждый процесс гарантированно получит возможность выполнения.
• Справедливость по отношению ко всем процессам, независимо от их длительности или приоритета.

Недостатки FIFO

• Низкая пропускная способность системы, особенно если длительные процессы блокируют короткие (эффект конвоя).
• Высокое среднее время ожидания и время отклика, особенно для коротких процессов, если они находятся в конце очереди.
• Отсутствие приоритизации процессов, что может привести к проблемам с выполнением срочных задач.
• Неэффективное использование ресурсов процессора, особенно в системах с процессами различной длительности.
• Сложности с соблюдением дедлайнов процессов из-за отсутствия механизма приоритетов.

RR

RR (Round Robin Scheduling) — это алгоритм циклического планирования с вытеснением, при котором процессор выдает процессы по очереди на фиксированный квант времени. Если процесс не успевает завершиться за отведенное ему время, он прерывается и помещается в конец очереди готовности.

Принцип работы

Начинается все, как в FIFO: процессы встают в очередь в том порядке, в котором приходят. Затем определяется небольшая единица времени, называемая квантом или интервалом. Обычно до 100 мс. Планировщик ЦП обходит очередь готовности и выделяет каждому процессу ЦП на интервал до одного кванта времени.

Планировщик ЦП выбирает первый процесс из очереди готовности, устанавливает таймер на прерывание через один квант времени и направляет процесс. Затем происходит одно из двух.

• Если процесс успевает выполниться за один квант времени, он добровольно освобождает процессор. Затем планировщик переходит к следующему процессу в очереди готовности.
• Если не успевает, срабатывает таймер, который вызывает прерывание для операционной системы. Оно не является критическим или аварийным, а лишь сигнализирует операционной системе, что нужно переключить процесс, чтобы поддерживать работу алгоритма. Соответственно, будет выполнено переключение контекста, а процесс будет помещен в конец очереди готовности.

В любом сценарии планировщик ЦП выберет следующий процесс в очереди готовности. Среднее время ожидания в соответствии с политикой RR часто бывает большим. Рассмотрим следующий набор процессов, которые прибывают в момент времени 0, с продолжительностью загрузки ЦП, заданной в миллисекундах:

Мы используем временной квант в 4 мс, и процесс P1 получит его полностью. Однако по условию для выполнения ему нужно еще 20 мс. Следовательно, он вытесняется по истечении первого кванта времени, а ЦП передается следующему процессу в очереди, P2. Ему нужно всего 3 мс, поэтому он завершается до истечения своего кванта времени. Затем процессор передается следующему процессу, P3. С ним повторяется предыдущий сценарий. Затем ЦП возвращается процессу P1, который будет удерживать его циклами по 4 мс, пока не завершится. В результате график RR выглядит следующим образом:

Картинка с сайта: habr.com

Источник.

Давайте посчитаем среднее время ожидания для этого расписания. P1 ждет 6 мс (суммарное время выполнения процессов P2 и P3). P2 ждет 4 мс, пока выполняется P1. P3 ждет 7 мс, пока выполняются P1 и P2. Таким образом, среднее время ожидания составляет 17/3 = 5,66 мс. В алгоритме планирования RR ЦП не выделяется ни одному процессу более чем на один квант времени подряд (если только это не единственный работающий процесс).

Если загрузка ЦП процесса превышает один квант времени, этот процесс вытесняется и помещается обратно в очередь готовности. Таким образом, алгоритм планирования RR является упреждающим. Если в очереди готовности находится n процессов и квант времени равен q, то каждый процесс получает 1/n процессорного времени порциями максимум по q единиц времени.

Каждый процесс должен ждать не более (n — 1) * q единиц времени до своего следующего кванта. Например, есть пять процессов и временной квант 20 мс. Значит, каждый процесс будет получать ЦП в свое распоряжение через каждые 100 мс.

Производительность алгоритма RR сильно зависит от размера временного кванта. С одной стороны, если он чрезвычайно велик, политика RR будет схожа с политикой FIFO. С другой, если он чрезвычайно мал (скажем, одна миллисекунда), подход RR может привести к большому количеству переключений контекста.

Картинка с сайта: habr.com

Источник.

Предположим, у нас есть только один процесс продолжительностью 10 мс и квант времени, равный 12 мс. В этом случае процесс завершится менее чем за один квант без каких-либо дополнительных затрат. Однако если квант равен шести миллисекундам, то процессу потребуется два кванта, что приведет к переключению контекста. Если квант времени равен одной миллисекунде, произойдет девять переключений контекста, что замедлит выполнение процесса (рис. выше).

Таким образом, мы хотим, чтобы квант времени был большим по сравнению со временем переключения контекста. Если последнее составляет примерно 10% кванта времени, то на переключение контекста будет потрачено около 10% времени процессора. На практике большинство современных ОС имеют кванты от 10 до 100 миллисекунд. Время, необходимое для переключения контекста, обычно составляет менее 10 микросекунд (0,01 мс). Таким образом, время переключения контекста составляет небольшую часть кванта времени.

Выбор кванта времени

Время выполнения также зависит от размера кванта времени.

Картинка с сайта: habr.com

Источник.

Как мы можем видеть на рисунке выше, среднее время выполнения набора процессов не обязательно улучшается по мере увеличения размера кванта времени. В общем, среднее время обработки можно улучшить, если большинство процессов завершат следующий цикл загрузки ЦП за один квант времени. Например, для трех процессов по 10 мс каждый и при кванте времени в 1 мс среднее время выполнения равно 29 мс. Однако если квант времени равен 10, то среднее время выполнения падает до 20. Если добавить время переключения контекста, в среднем время выполнения увеличивается еще больше. И это при меньшем временном интервале, поскольку нужно больше переключений контекста.

Временной интервал должен быть большим по сравнению со временем переключения контекста, но в то же время не превышать его слишком сильно. Как указано выше, если квант времени слишком велик, планирование RR перерождается в политику FIFO. Эмпирическое правило заключается в том, что 80% пакетов процессорного времени должны быть короче кванта времени.

Преимущества и недостатки

Преимущества RR

• Справедливое распределение процессорного времени.
• Отсутствие блокировки системы одним процессом.
• Низкое время отклика для интерактивных процессов.

Недостатки

• Необходимость выбора оптимального кванта времени.
• Накладные расходы на переключение контекста.
• Неэффективность для процессов с очень короткими или очень длинными временами выполнения.

SJF

SJF (Shortest Job First) — это алгоритм, который выбирает в первую очередь процесс с минимальным ожидаемым временем выполнения. Он может работать как с вытеснением (тогда это будет SRTF — Shortest Remaining Time First), так и без него.

Принцип работы

Алгоритм сортирует процессы в очереди по ожидаемому времени выполнения от меньшего к большему. После назначает ЦП сначала процессам с коротким временем выполнения, а затем все более и более длинным.

Если следующие пакеты ЦП двух процессов одинаковы, для разрыва связи используется планирование FIFO. Обратите внимание, что более подходящим термином для этого метода планирования был бы алгоритм «самый короткий следующий пакет ЦП».Это потому, что планирование зависит от длины следующего пакета ЦП процесса, а не от его общей длины.

Я использую термин термин SJF, потому что большинство людей применяют его, и он часто встречается в учебниках для обозначения этого типа планирования. В качестве примера планирования SJF рассмотрим следующий набор процессов с продолжительностью загрузки ЦП, заданной в миллисекундах:

Используя планирование SJF, запланировали бы эти процессы в соответствии со следующей диаграммой Ганта:

Картинка с сайта: habr.com

Время ожидания — 3 миллисекунды для процесса P1,16 — для P2, 9 — для P3 и 0 — для P4. Таким образом, среднее время ожидания будет (3 + 16 + 9 + 0)/4 = 7 миллисекунд. Для сравнения: если бы использовали схему планирования FIFO, среднее время ожидания составило бы 10,25 миллисекунды.

SJF является доказуемо оптимальным, поскольку обеспечивает минимальное среднее время ожидания для данного набора процессов. Постановка короткого процесса перед длинным уменьшает среднее время ожидания.

Несмотря на это, SJF нельзя реализовать на уровне планирования ЦП, поскольку нет способа узнать длину следующего пакета. Один из подходов к этой проблеме — попытаться аппроксимировать планирование SJF. Мы можем не знать продолжительность следующего пакета процессора, но можем предсказать его значение. Ожидаемо, что следующий пакет будет аналогичен по длине предыдущим. Вычислив приблизительную длину следующего пакета ЦП, можем выбрать процесс с самым коротким прогнозируемым пакетом ЦП.

Следующий пакет ЦП обычно прогнозируется как экспоненциальное среднее измеренных длин предыдущих пакетов. Можем определить это значение с помощью следующей формулы:

Здесь tn — длина n-го пакета ЦП, а 𝛕n + 1 — наше прогнозируемое значение для следующего пакета ЦП. Переменная α находится в диапазоне от 0 до 1.

Значение tn содержит нашу самую свежую информацию, а 𝛕n хранит прошлую историю. Параметр α контролирует относительный вес недавней и прошлой истории в нашем прогнозе. Если α = 0, то 𝛕n+1 = 𝛕n и недавняя история не оказывает влияния (текущие условия считаются переходными).

Если α = 1, то 𝛕n+1 = tn и имеет значение только самый последний пакет процессора (предполагается, что история устарела и не имеет значения). Чаще всего α = 1/2, поэтому недавняя и прошлая история имеют одинаковый вес. Начальное значение 𝛕0 может быть определено как константа или среднее значение всей системы. На рисунке показано экспоненциальное среднее при α = 1/2 и 𝛕0 = 10.

Картинка с сайта: habr.com

Источник.

Чтобы понять поведение экспоненциального среднего, мы можем расширить формулу для 𝛕n + 1, заменив 𝛕n и найдя:

Картинка с сайта: habr.com

Обычно α < 1. В результате (1 — α) также меньше 1, и каждый последующий термин имеет меньший вес, чем его предшественник.

Алгоритм SJF может быть вытесняющим и невытесняющим. Выбор возникает, когда новый процесс поступает в очередь готовности, в то время как предыдущий все еще выполняется. Следующий пакет ЦП вновь прибывшего процесса может быть короче, чем то, что осталось от текущего. SJF с вытеснением, соответственно, вытесняет выполняющийся в данный момент процесс, тогда как SJF без вытеснения позволяет ему завершить пакетную нагрузку ЦП. Вытесняющее планирование SJF иногда называют планированием с наименьшим оставшимся временем. В качестве примера рассмотрим следующие четыре процесса с продолжительностью загрузки ЦП, заданной в миллисекундах:

Картинка с сайта: habr.com

Вот как в таких условиях будет выглядеть результирующий график упреждающего SJF:

Картинка с сайта: habr.com

Источник.

P1 запускается в момент времени 0, поскольку это единственный процесс в очереди. P2 прибывает в момент 1. Оставшееся время для процесса P1 (7 миллисекунд) больше, чем время, необходимое для P2 (4 миллисекунды), поэтому P1 вытесняется, а P2 планируется. Среднее время ожидания для этого примера составляет [(10 – 1) + (1 – 1) + (17 – 2) + (5 – 3)]/4 = 26/4 = 6,5 миллисекунд. Невытесняющее планирование SJF приведет к тому, что среднее время ожидания составит 7,75 миллисекунды.

Преимущества и недостатки

Преимущества SJF

• Минимизация среднего времени ожидания процессов.
• Эффективное использование процессора.

Недостатки

• Необходимость знать или прогнозировать время выполнения процессов.
• Возможность голодания длинных процессов.
• Сложность реализации алгоритма прогнозирования времен выполнения.

Метрики оценки производительности

Среднее время ожидания

Среднее время ожидания (Average Waiting Time, AWT) определяется как среднее время, которое процессы проводят в очереди готовности перед их выполнением на процессоре. Оно рассчитывается как сумма всех времен ожидания процессов, поделенная на количество процессов:

Здесь W_i​ — время ожидания i-го процесса, n — общее количество процессов.

Среднее время выполнения

Среднее время выполнения (Average Turnaround Time, ATT) определяется как время от момента поступления процесса в систему до его завершения. Оно включает время ожидания и время выполнения на процессоре:

Здесь T_i​ — время выполнения i-го процесса, n — общее количество процессов.

Среднее время отклика

Среднее время отклика (Average Response Time, ART) — это время от поступления запроса до начала его обработки процессором. Время отклика не включает время, необходимое для выполнения процесса, только время ожидания до первого выполнения:

Здесь R_i​ — время отклика i-го процесса, n — общее количество процессов.

Описание прикладной задачи

Определение наборов процессов для тестирования

Для тестирования производительности алгоритмов планирования я выбрал несколько наборов процессов, которые характеризуются различным временем выполнения и поступления.

• Набор 1. Процессы с равномерным распределением времени выполнения.
• Набор 2. Процессы с переменным временем выполнения, имитирующие рабочую нагрузку на сервере.
• Набор 3. Процессы с коротким временем выполнения, чередующиеся с длительными процессами, чтобы проверить алгоритмы на предмет устойчивости к эффекту конвоя.

Каждый набор был разработан таким образом, чтобы обеспечить разнообразие сценариев для тщательного тестирования алгоритмов FIFO, Round Robin и SJF.

Реализация и симуляция алгоритмов

Краткое описание реализации алгоритмов

Подходы, которые я использовал для реализации алгоритмов планирования процессов:

• FIFO (First-In First-Out) — процессы обрабатываются в порядке их поступления;
• Round Robin — процессы получают процессорное время по очереди с фиксированным квантом времени;
• SJF (Shortest Job First) — процессы обрабатываются в порядке возрастания их ожидаемого времени выполнения.

Проведение симуляции для каждого алгоритма

Для проведения симуляций написан скрипт на Python, который моделирует выполнение процессов в операционной системе Linux:

# Определение процессов для симуляции
processes = [
   {'id': 1, 'burst_time': 10},
   {'id': 2, 'burst_time': 5},
   {'id': 3, 'burst_time': 8}
]
time_quantum = 4

Симуляция FIFO:

# FIFO Scheduling
def fifo_scheduling(processes):
   waiting_time = 0
   total_waiting_time = 0
   total_turnaround_time = 0
   response_time = 0
   total_response_time = 0
   for i, process in enumerate(processes):
       if i == 0:
           response_time = 0
       else:
           response_time = waiting_time
       total_response_time += response_time
       total_waiting_time += waiting_time
       waiting_time += process['burst_time']
       total_turnaround_time += waiting_time
   avg_waiting_time = total_waiting_time / len(processes)
   avg_turnaround_time = total_turnaround_time / len(processes)
   avg_response_time = total_response_time / len(processes)
   return avg_waiting_time, avg_turnaround_time, avg_response_time

Симуляция Round Robin:

# Round Robin Scheduling
def round_robin_scheduling(processes, time_quantum):
   from collections import deque
   q = deque(processes)
   current_time = 0
   waiting_time = {process['id']: 0 for process in processes}
   remaining_time = {process['id']: process['burst_time'] for process in processes}
   response_time = {process['id']: -1 for process in processes}
   completed_processes = 0
   total_waiting_time = 0
   total_turnaround_time = 0
   total_response_time = 0
   while completed_processes < len(processes):
       process = q.popleft()
       if response_time[process['id']] == -1:
           response_time[process['id']] = current_time
       if remaining_time[process['id']] > time_quantum:
           current_time += time_quantum
           remaining_time[process['id']] -= time_quantum
           q.append(process)
       else:
           current_time += remaining_time[process['id']]
           waiting_time[process['id']] = current_time - process['burst_time']
           total_turnaround_time += current_time
           total_waiting_time += waiting_time[process['id']]
           total_response_time += response_time[process['id']]
           remaining_time[process['id']] = 0
           completed_processes += 1
   avg_waiting_time = total_waiting_time / len(processes)
   avg_turnaround_time = total_turnaround_time / len(processes)
   avg_response_time = total_response_time / len(processes)
   return avg_waiting_time, avg_turnaround_time, avg_response_time

Симуляция SJF:

# SJF Scheduling
def sjf_scheduling(processes):
   sorted_processes = sorted(processes, key=lambda x: x['burst_time'])
   waiting_time = 0
   total_waiting_time = 0
   total_turnaround_time = 0
   response_time = 0
   total_response_time = 0
   for i, process in enumerate(sorted_processes):
       if i == 0:
           response_time = 0
       else:
           response_time = waiting_time
       total_response_time += response_time
       total_waiting_time += waiting_time
       waiting_time += process['burst_time']
       total_turnaround_time += waiting_time
   avg_waiting_time = total_waiting_time / len(processes)
   avg_turnaround_time = total_turnaround_time / len(processes)
   avg_response_time = total_response_time / len(processes)
   return avg_waiting_time, avg_turnaround_time, avg_response_time

Выполнение симуляций:

# Выполнение симуляций
fifo_results = fifo_scheduling(processes)
rr_results = round_robin_scheduling(processes, time_quantum)
sjf_results = sjf_scheduling(processes)
print("FIFO Results: ", fifo_results)
print("Round Robin Results: ", rr_results)
print("SJF Results: ", sjf_results)

Результаты симуляций и их анализ

Выводы

Для систем с равномерной нагрузкой лучше использовать алгоритм FIFO, так как он проще в реализации и предполагает минимальные управленческие расходы. Это затраты системы на выполнение задач, связанных с управлением процессами. В контексте планирования процессов в операционных системах, такие расходы включают время процессора, память, код и данные ОС.
Для интерактивных систем и систем реального времени, где важна справедливость и быстрота отклика, лучше всего подходит алгоритм Round Robin. Он гарантирует равномерное распределение процессорного времени и быструю реакцию системы на запросы пользователей.
Для вычислительных задач, требующих минимизации общего времени выполнения, наиболее эффективным является алгоритм SJF. Однако следует учитывать риск голодания для длительных процессов, поэтому можно рассмотреть использование модифицированных версий алгоритма.

Заключение

Анализ и симуляции показали, что у каждого алгоритма планирования есть сильные и слабые стороны. FIFO подходит для простых систем с однородной нагрузкой. Round Robin справедливо распределяет процессорное время, но требует точной настройки. SJF обеспечивает наименьшее среднее время ожидания и выполнения, однако может вызвать голодание долгих процессов и требует точной оценки времени выполнения.

Выбор подходящего алгоритма зависит от специфики задач и требований системы и оптимальный выбор может варьироваться в зависимости от контекста использования.

Материал из РУВИКИ — свободной энциклопедии

Вытесняющая многозадачность (приоритетная многозадачность, англ. preemptive multitasking, дословно упреждающая многозадачность) — это вид многозадачности, при которой операционная система принимает решение о переключении между задачами по истечении некоего кванта времени^[1].

Решение принимается в соответствии с приоритетами задач. В отличие от кооперативной многозадачности, управление операционной системе передаётся вне зависимости от состояния работающих приложений, благодаря чему, в частности, зависшие (к примеру — зациклившиеся) приложения, как правило, не «подвешивают» операционную систему. За счёт регулярного переключения задач также улучшается системы, оперативность освобождения ресурсов системы, которые больше не используются задачей^[1][2].

В реализации вытесняющая многозадачность отличается от кооперативной, в частности, тем, что требует обработки системного прерывания от аппаратного таймера^[3]. По истечении кванта времени, отведённого процессу, происходит прерывание и вызывается планировщик процессов. Частота вызова планировщика критична: слишком частый его вызов будет расходовать процессорное время впустую.

Вытесняющая многозадачность используется в большинстве современных операционных систем общего назначения^[4], к примеру: Windows 9x и NT^[5], Linux (и другие UNIX)^[6] и OS/2^[7],^[8] Mac OS^[9][10] и BeOS^[11], MenuetOS и KolibriOS^[12]. Примером системы с вытесняющей многозадачностью более ранней, чем UNIX, может служить VMS^[13]. Она также используется во многих встраиваемых операционных системах реального времени, таких как FreeRTOS^[14].

• Многозадачность:
  • Кооперативная
  • Мультипрограммирование
• Многопоточность

• Эрик Реймонд. Искусство программирования для Unix. — Издательский дом Вильямс, 2005. — 544 с. — ISBN 978-5-8459-0791-2.
• Max Hailperin. 2.5. Preemptive multitasking // Operating Systems and Middleware: Supporting Controlled Interaction. — Max Hailperin, 2007. — С. 33-34. — 496 с. — ISBN 978-0-534-42369-8. Архивная копия от 15 сентября 2016 на Wayback Machine
• Christopher Kormanyos. 11.7 Preemptive Multitasking // Real-Time C++: Efficient Object-Oriented and Template Microcontroller Programming. — Springer, 2015. — 389 с. — ISBN 978-3-662-47810-3.

1. ПЛАНИРОВАНИЕ ПРОЦЕССОВ

На
протяжении
существования
процесса
выполнение его потоков может быть многократно
прервано и продолжено. Переход от выполнения
одного потока к другому осуществляется в
результате планирования и диспетчеризации.
Работа по определению того, в какой момент
необходимо прервать выполнение текущего
активного потока и какому потоку предоставить
возможность
выполняться,
называется
планированием.
Планирование
потоков
осуществляется
на
основе
информации,
хранящейся в описателях процессов и потоков.

2.

При планировании могут приниматься во
внимание приоритет потоков, время их
ожидания в очереди, накопленное время
выполнения, интенсивность обращений к
вводу-выводу и другие факторы.
Планирование потоков включает в себя решение
двух задач:
− определение момента смены текущего
активного потока;
− выбор для выполнения потока из очереди
готовых потоков.

3.

Существует множество различных алгоритмов
планирования потоков, решающих приведенные
задачи.
Особенности реализации планирования потоков в
наибольшей степени определяют
специфику
операционной системы, в частности, является ли
она системой пакетной обработки, системой
разделения времени или системой реального
времени.
В
большинстве
операционных
систем
универсального
назначения
планирование
осуществляется динамически, то есть решения
принимаются во время работы системы на основе
анализа текущей ситуации.

4.

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

5.

Диспетчеризация заключается в реализации
найденного
в
результате
планирования
(динамического или статистического) решения, то
есть в переключении процессора с одного потока
на другой. Прежде чем прервать выполнение
потока, ОС запоминает его контекст, для того,
чтобы
впоследствии
использовать
эту
информацию для возобновления выполнения
данного потока.
Диспетчеризация обычно сводится к:
− сохранению контекста текущего потока, который
требуется сменить;
− загрузке контекста нового потока;

6.

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

7.

Планирование процессов включает в себя
решение следующих задач:
– определение момента времени для смены
выполняемого процесса;
– выбор процесса на выполнение из очереди
готовых процессов;
– переключение
контекстов
«старого»
и
«нового» процессов.
Первые две задачи решаются программными
средствами, а последняя в значительной
степени аппаратно.

8.

Все множество алгоритмов планирования можно
разделить на два принципиально различных
класса: вытесняющие и невытесняющие.
− Невытесняющие (non-preemptive) алгоритмы
основаны на том, что активному потоку
позволяется выполняться до тех пор, пока он
сам, по собственной инициативе, не отдаст
управление операционной системе для того,
чтобы та выбрала из очереди другой готовый к
выполнению поток.
− Вытесняющие (preemptive) алгоритмы – это
такие способы планирования потоков, в
которых решение о переключении процессора
с выполнения одного потока на выполнение
другого потока принимается операционной
системой, а не активной задачей.

9.

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

10.

Прикладная программа, получив управление от
операционной
системы,
сама
передает
управление ОС с помощью какого-либо
системного вызова, когда посчитает это
необходимым.
Такой механизм создает проблемы, как для
пользователей, так и для разработчиков
приложений.
Если
приложение
тратит
слишком много времени на выполнение какойлибо работы, например на форматирование
диска, пользователь не может переключиться с
этой задачи на другую задачу.

11.

Почти во всех современных операционных
системах,
ориентированных
на
высокопроизводительное
выполнение
приложений (UNIX, Windows NT/2000),
реализованы
вытесняющие
алгоритмы
планирования потоков (процессов).
Среди вытесняющих алгоритмов рассмотрим
подробнее две группы наиболее часто
встречающихся алгоритмов: алгоритмы,
основанные на квантовании, и алгоритмы,
основанные на приоритетах.

12.

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

13.

В соответствии с алгоритмами, основанными на
квантовании,
смена
активного
процесса
происходит, если,
процесс завершился и покинул систему;
произошла ошибка;
процесс перешел в состояние ОЖИДАНИЕ;
исчерпан
квант
процессорного
времени,
отведенный данному процессу.
Процесс, который исчерпал свой квант, переводится
в состояние ГОТОВНОСТЬ и ожидает, когда ему
будет предоставлен новый квант процессорного
времени, а на выполнение в соответствии с
определенным правилом выбирается новый
процесс из очереди готовых.

14.

Таким образом, ни один процесс не занимает процессор
надолго, поэтому квантование широко используется в
системах разделения времени.

15.

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

16.

17.

Другая группа алгоритмов использует понятие
«приоритет» процесса.
Приоритет − это число, характеризующее
степень привилегированности процесса при
использовании ресурсов вычислительной
машины, в частности, процессорного времени:
чем
выше
приоритет,
тем
выше
привилегии.
Чем выше привилегии процесса, тем меньше
времени он будет проводить в очередях.
Существует две разновидности приоритетных
алгоритмов:
алгоритмы,
использующие
относительные приоритеты, и алгоритмы,
использующие абсолютные приоритеты.

18.

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

19.

20.

В
системах с абсолютными приоритетами
выполнение активного процесса прерывается еще
при одном условии: если в очереди готовых
процессов появился процесс, приоритет которого
выше приоритета активного процесса. В этом
случае прерванный процесс переходит в
состояние готовности.
Во многих операционных системах алгоритмы
планирования построены с использованием как
квантования, так и приоритетов. Например, в
основе планирования лежит квантование, но
величина кванта и/или порядок выбора процесса
из очереди готовых определяется приоритетами
процессов.

21.

22.

В
качестве примера рассмотрим схему
назначения приоритетов потокам, принятую в
операционной системе Windows .
В системе определено 32 уровня приоритетов и
два класса потоков – потоки реального
времени
и
потоки
с
переменными
приоритетами.
Диапазон от 1 до 15 включительно отведен для
потоков с переменными приоритетами, а от 16
до 31– для более критичных ко времени
потоков реального времени (приоритет 0
зарезервирован для системных целей).
При создании процесса он в зависимости от класса
получает по умолчанию базовый приоритет в
верхней или нижней части диапазона.

23.

Базовый приоритет процесса в дальнейшем может
быть повышен или понижен операционной
системой.
Пусть, например, значение базового приоритета
некоторого процесса равно К. Тогда все потоки
данного процесса получат базовые приоритеты из
диапазона [К-2, К+2]. Отсюда видно, что, изменяя
базовый приоритет процесса, ОС может влиять на
базовые приоритеты его потоков.
ОС может повышать приоритет потока (который в
этом случае называется динамическим) в тех
случаях, когда поток не полностью использовал
отведенный ему квант, или понижать приоритет,
если квант был использован полностью.

24.

25.

Приоритеты от 16 до 31
используются
для
выполнения
основных
функций ОС и обычно не
применяются
для
приложений; а приоритеты
от 0 до 15 — определяют
процессорный приоритет
приложения.

26.

В Windows реализован смешанный алгоритм
планирования – вытесняющий, на основе
квантования и приоритетов.
В
Windows отсутствует единый модуль,
отвечающий за планирование потоков.
Алгоритм
планирования
реализуется
несколькими процедурами ядра, совокупность
которых называется диспетчером ядра
(kernel’s dispatcher).

27.

1. Выбор потока на выполнение.
Просматривается очередь готовых к выполнению потоков и
выбирается первый поток в очереди с наибольшим
приоритетом, которому для выполнения предоставляется
квант времени.

28.

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

29.

3. Вытеснение потоком с большим приоритетом.
Во время выполнения поток может быть вытеснен при
появлении потока с большим приоритетом. Такая ситуация
может возникнуть по следующим причинам:
поток с большим приоритетом завершил ожидание;
приоритет потока в очереди готовности динамически увеличился;
в системе создан поток с большим приоритетом.
В
любом
случае
выполняющийся поток
вытесняется,
помещается в начало
очереди готовности с
соответствующим
приоритетом; при этом
неистраченная
часть
кванта остается за
потоком.

30.

4. Завершение кванта времени
Когда квант времени, предоставленный потоку, истекает,
операционная система проверяет, есть ли в очереди
готовности поток с таким же приоритетом или выше. Если
есть, то поток помещается в конец соответствующей очереди
готовности и новый поток выбирается на выполнение. Если
такие потоки отсутствуют, выполняющемуся потоку может
быть предоставлен новый квант времени.

31.

Динамическое повышение приоритета
Если бы операционная система осуществляла планирование
потоков только на основе выше рассмотренных ситуаций,
большинство потоков с низким приоритетом вообще никогда
не выполнялись бы – диспетчер ядра все время выбирал бы
потоки с наивысшим приоритетом.
Чтобы дать всем потокам шанс на выполнение ОС применяет
механизм динамического повышения приоритета (Priority
Boosts), который работает в следующих случаях:
• возникает событие диспетчера ядра;
• завершается операции ввода/вывода;
• происходит событие пользовательского интерфейса;
• поток слишком долго ожидает ресурс;
• поток слишком долго ожидает своей очереди на выполнение.
Никогда не повышаются приоритеты потоков реального
времени (16–31).

32.

Вопросы к лекции
3.3.1 Дайте определение процесса и потока.
3.3.2 Как происходит создание и завершение
процессов и потоков?
3.3.3 В каких состояниях может находиться поток?
3.3.4 Как осуществляется планирование процессов?
3.3.5 Чем отличаются алгоритмы планирования,
основанные на квантовании, и алгоритмы,
основанные на приоритетах?
3.3.6
Чем
отличаются
вытесняющие
и
невытесняющие алгоритмы планирования?
3.3.7
Опишите
механизм
планирования,
реализованный в Windows.