Алгоритм планирования реализованный в windows nt можно охарактеризовать как

Обновлено: 02.07.2024

Процесс (задача) – абстракция, описывающая выполняющуюся в рамках ОС программу. Для ОС процесс – единица работы, которая потребляет системные ресурсы.

Задачи, решаемые подсистемой управления процессами:

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

С понятием управления процессами в ОС связаны следующие технологии:

Содержание

Состояния процесса в ОС

Состояние процесса в ходе жизненного цикла в ОС

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

В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ - несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

Информация о процессе:

Режим работы процессора.
Информация об открытых файлах.
Регистры.
Состояние внешних устройств.
Операции ввода – вывода.

Информационные структуры описывающие процессы

Существует две информационные структуры по-разному описывающие процессы - контекст процесса и дескриптор процесса.

Контекст процесса

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

В состав контекста процесса входит:

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

Дескриптор процесса

Дескриптор процесса – это информационная структура, которая описывает внешнюю структуру (информацию) процессе (нужна планировщику для выполнения процесса, а так же нужна ядру в течение всего жизненного цикла процесса)

В состав дескриптора входят:

Идентификатор процесса;
Состояние процесса.
Информация о привилегированности процесса.
Информация о расположении кодового сегмента.

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

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

Задача планирования процессов состоит из трех действий:

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

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

Создание процесса

Создание процесса:

ОС создает контекст и дескриптор процесса.
Загрузка кодового сегмента в оперативную память.
Дескриптор помещается в очередь процессов, находящихся в готовности.

С этого момента можно считать, что процесс стартовал.

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

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

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

Алгоритмы, основанные на квантовании времени

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

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

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

Выбор новых процессов может быть построен по принципам:

Алгоритмы, основанные на приоритетах

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

Существует 2 разновидности таких алгоритмов:

Использующие относительные приоритеты.
Использующие абсолютные приоритеты.

Алгоритмы планирования с относительными приоритетами – активный процесс выполняется пока не завершится или не перейдет в состояние ожидания.

Алгоритмы планирования с абсолютными приоритетами – смена процесса происходит в тот момент, когда в системе появляется процесс, приоритет которого выше приоритета выполняемого процесса.

Реально используются смешанные схемы планирования.

Вытесняющий и невытесняющий алгоритмы планирования

Существует два основных типа процедур планирования процессов - вытесняющие (preemptive) и невытесняющие (non-preemptive).

Non-preemptive multitasking - невытесняющая многозадачность - это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.

Preemptive multitasking - вытесняющая многозадачность - это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей.

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

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

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

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

Поэтому разработчики приложений для non-preemptive операционной среды, возлагая на себя функции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить "дружественное" отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая им управление. Крайним проявлением "недружественности" приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет зависшую задачу с выполнения.

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

Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2), реализована вытесняющая многозадачность. Вытесняющую многозадачность часто называют истинной многозадачностью.

Синхронизация процессов в ОС

Проблема синхронизации процессов

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

За время своего существования в системе поток может многократно находиться в одном из трех состояний:

· выполнение – активное состояние, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

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

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

Возможные переходы между состояниями:

· Поток выбран на выполнение;

· Поток ожидает завершения ввода/вывода;

· Ввод/вывод завершен (событие произошло);

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

17. Планирование и диспетчеризация потоков, моменты перепланировки

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

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

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

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

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

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

Диспетчеризация сводится к следующему:

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

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

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

Ситуации, когда необходимо планирование:

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

2) Активная задача выполнила системный вызов, связанный с запросом на ввод/вывод или на доступ к ресурсу, который в настоящий момент занят. Планировщик переводит задачу в состояние ожидания и выполняет перепланирование.

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

4) Завершение периферийным устройством операции ввода/вывода переводит соответствующую задачу в очередь готовых, и выполняется планирование.

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

18. Алгоритм планирования, основанный на квантовании

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

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

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

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

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

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

19. Приоритетное планирование

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

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

Рисунок 2. Приоритеты потоков в Windows NT

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

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

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

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

20. Алгоритмы планирования ОС пакетной обработки: «первым пришел – первым обслужен», «кратчайшая задача – первая», «наименьшее оставшееся время выполнения»

В таких ОС критерием эффективности служит максимальная загрузка аппаратуры.

· FIFO. Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. Достоинства: простота реализации. Недостатки: если есть один процесс, ограниченный возможностями процессора, то они замедлят работу процесса.

· Кратчайшая задача - первая. Нужно знать время выполнения задачи! Критерий - минимальное среднее оборотное время. Оборотное время - время, прошедшее от начала выполнения до получения результата.

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

21. Алгоритмы планирования в интерактивных ОС: циклическое, приоритетное, гарантированное, лотерейное, справедливое планирование

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

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

· справедливость (как в очереди покупателей, каждому только по килограмму).

· слишком малый квант времени (по сравнению с временем переключения контекстов) приводит к частому переключению процессов и снижению производительности;

· слишком большой квант может привести к увеличению времени ответа на интерактивный запрос.

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

Гарантированное планирование. ОС гарантирует существующим потокам, что они получат гарантированную справедливую часть процессорного времени. n потоков, 1/n частей процессорного времени каждому. Стс должна вести учет времени, получаемого каждым потоком, в момент перепланировки вычисляется отношение фактически получаемого воремени к времени гарантированному. На выполнение выбирается тот поток, у которого это отношение наименьшее.

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

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

22. Алгоритм планирования Windows NT

Алгоритм планирования нитей в Windows NT объединяет в себе обе базовых концепции - квантование и приоритеты. Как и во всех других алгоритмах, основанных на квантовании, каждой нити назначается квант, в течение которого она может выполняться. Нить освобождает процессор, если:

блокируется, уходя в состояние ожидания;
завершается;
исчерпан квант;

· в очереди готовых появляется более приоритетная нить.

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

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

Планирование в ОС реального времени

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

Системы реального времени делятся на:

· жесткие - несоблюдение временных ограничений приводит к катастрофическим последствиям; в таких системах время завершения выполнения каждой из критических задач должно быть гарантировано для всех возможных сценариев работы системы;

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

Внешние события, на которые система должна реагировать, делятся:

· периодические – начиная с момента первоначального запроса все будущие моменты возникновения задачи можно определить заранее;

· спорадические - моменты возникновения запросов заранее неизвестны.

· Статический: до запуска системы составляется расписание. Все решения сделаны заранее, во время выполнения реализуется это расписание;

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

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

Алгоритм планирования - используемый алгоритм для планирования.

Ситуации, когда необходимо планирование:

Когда создается процесс

Когда процесс завершает работу

Когда процесс блокируется на операции ввода/вывода, семафоре, и т.д.

При прерывании ввода/вывода.

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

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

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

Основные три системы:

Системы пакетной обработки - могут использовать неприоритетный и приоритетный алгоритм (например: для расчетных программ).

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

Системы реального времени - могут использовать неприоритетный и приоритетный алгоритм (например: система управления автомобилем).

Задачи алгоритмов планирования:

Для всех систем
Справедливость - каждому процессу справедливую долю процессорного времени
Контроль над выполнением принятой политики
Баланс - поддержка занятости всех частей системы (например: чтобы были заняты процессор и устройства ввода/вывода)

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

Интерактивные системы
Время отклика - быстрая реакция на запросы
Соразмерность - выполнение ожиданий пользователя (например: пользователь не готов к долгой загрузке системы)

Системы реального времени
Окончание работы к сроку - предотвращение потери данных
Предсказуемость - предотвращение деградации качества в мультимедийных системах (например: потерь качества звука должно быть меньше чем видео)

4.2 Планирование в системах пакетной обработки

4.2.1 "Первый пришел - первым обслужен" (FIFO - First In Fist Out)

Процессы ставятся в очередь по мере поступления.

Справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди)

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

4.2.2 "Кратчайшая задача - первая"

Нижняя очередь выстроена с учетом этого алгоритма

Уменьшение оборотного времени

Справедливость (как в очереди покупателей, кто без сдачи проходит в перед)

Длинный процесс занявший процессор, не пустит более новые краткие процессы, которые пришли позже.

4.2.3 Наименьшее оставшееся время выполнение

Аналог предыдущего, но если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса.

4.3 Планирование в интерактивных системах

4.3.1 Циклическое планирование

Самый простой алгоритм планирования и часто используемый.

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

Пример циклического планирования

Справедливость (как в очереди покупателей, каждому только по килограмму)

Если частые переключения (квант - 4мс, а время переключения равно 1мс), то происходит уменьшение производительности.

Если редкие переключения (квант - 100мс, а время переключения равно 1мс), то происходит увеличение времени ответа на запрос.

4.3.2 Приоритетное планирование

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом.

Приоритет может быть динамический и статический.

Динамический приоритет может устанавливаться так:

П=1/Т, где Т- часть использованного в последний раз кванта

Если использовано 1/50 кванта, то приоритет 50.

Если использован весь квант, то приоритет 1.

Т.е. процессы, ограниченные вводом/вывода, будут иметь приоритет над процессами ограниченными процессором.

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

Приоритетное планирование 4-х групп

4.3.3 Методы разделения процессов на группы

Группы с разным квантом времени

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

Процесс либо заканчивает работу, либо переходит в другую группу

Этот метод напоминает алгоритм - "Кратчайшая задача - первая".

Группы с разным назначением процессов

Процесс, отвечающий на запрос, переходит в группу с наивысшим приоритетом.

Такой механизм позволяет повысить приоритет работы с клиентом.

Гарантированное планирование

В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.

Лотерейное планирование

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

Справедливое планирование

Процессорное время распределяется среди пользователей, а не процессов. Это справедливо если у одного пользователя несколько процессов, а у другого один.

4.4 Планирование в системах реального времени

Системы реального времени делятся на:

жесткие (жесткие сроки для каждой задачи) - управление движением

гибкие (нарушение временного графика не желательны, но допустимы) - управление видео и аудио

Внешние события, на которые система должна реагировать, делятся:

периодические - потоковое видео и аудио

непериодические (непредсказуемые) - сигнал о пожаре

Что бы систему реального времени можно было планировать, нужно чтобы выполнялось условие:

m - число периодических событий

i - номер события

P(i) - период поступления события

T(i) - время, которое уходит на обработку события

Т.е. перегруженная система реального времени является не планируемой.

4.4.1 Планирование однородных процессов

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

Т.к. все процессы важны, можно использовать циклическое планирование.

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

4.4.2 Общее планирование реального времени

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

Планировщик должен знать:

частоту, с которой должен работать каждый процесс

объем работ, который ему предстоит выполнить

ближайший срок выполнения очередной порции задания

Рассмотрим пример из трех процессов.

Процесс А запускается каждые 30мс, обработка кадра 10мс

Процесс В частота 25 кадров, т.е. каждые 40мс, обработка кадра 15мс

Процесс С частота 20 кадров, т.е. каждые 50мс, обработка кадра 5мс

Три периодических процесса

Проверяем, можно ли планировать эти процессы.

Условие выполняется, планировать можно.

Будем планировать эти процессы статическим (приоритет заранее назначается каждому процессу) и динамическим методами.

4.4.3 Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

Процессы должны удовлетворять условиям:

Процесс должен быть завершен за время его периода

Один процесс не должен зависеть от другого

Каждому процессу требуется одинаковое процессорное время на каждом интервале

У непериодических процессов нет жестких сроков

Прерывание процесса происходит мгновенно

Приоритет в этом алгоритме пропорционален частоте.

Процессу А он равен 33 (частота кадров)

Процессу В он равен 25

Процессу С он равен 20

Процессы выполняются по приоритету.

Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

4.4.4 Динамический алгоритм планирования EDF (Earliest Deadline First)

Наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения.

При больших загрузках системы EDF имеет преимущества.

Рассмотрим пример, когда процессу А требуется для обработки кадра - 15мс.

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

1-прерывание таймера(конец кванта)-планировщик переводит задачу или поток в состояние канта что бы получить след. Квант

2-активная задача выполнила сис. вызов –запрос на вод-вывод, который в настоящий момент занят, переводит в состояние ожидания и выполняет перепланировку

3-активная задача выполнила сис.вызов связанный с освобождением ресурсов-планировщик получает ресурс и переводит в состояние готовности.

4-внешнее аппаратное прерывание, сигнализирующая о завершении УВМ операций в.-в.,в этом случае планировщик переводит задачу в очередь готовых и производит перепланировку

5-внутриние прерывание сигнала-планировщик снимает задачу и производит перепланировку.

21) Опишите моменты перепланировки в среде ос рв.

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

22)Как осуществляются диспетчеризация и учёт приоритетов прерываний в ос?

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

23) Как работает диспетчер прерываний?

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

Не так давно пытался найти здесь какую-нибудь информацию о планировщике Windows и к своему удивлению не нашёл ничего конкретного о планировщиках вообще, поэтому решил запостить вот этот пример планировщика, надеюсь кому-то он окажется полезен. Код написан на Turbo Pascal со вставками ассемблера 8086.

Что собственно планирует планировщик?

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

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

FIFO
Самые короткие — вперёд!
Самые выполнившиеся вперёд!

Циклическая
С приоритетом по времени
С приоритетом по назначению

Критические секции

Взаимная блокировка

Допустим у нас есть неразделяемые ресурсы А и Б и потоки Х, Y, которые хотят задействовать эти ресурсы. Если некий ~~криворукий~~ недостаточно компетентный программист расставит критические скобки вот так:
…
Поток X
Занять Ресурс(А)
Занять Ресурс(Б)
…
Отдать Ресурс(А)
Отдать Ресурс(Б)
Поток Y
Занять Ресурс(Б)
Занять Ресурс(А)
…
Отдать Ресурс(Б)
Отдать Ресурс(А)

через некоторое время возникнет вот такая ситуация:

Сладенькое

Ну и собственно то ради чего это всё писалось. Как уже было сказано код нашего планировщика будет выполнен на языке Turbo Pascal.
Механизм критических секций реализован в процедурах EnterCritical(), LeaveCritical(). Вспомним ещё раз: чтобы войти в критическую секцию — нужно проверить не занята ли она, и по результату — либо занять её и разрешить потоку ей пользоваться, либо поставить поток в очередь и передать управление кому-то другому.

C LeaveCritical() вроде бы и так всё ясно:

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

Сама процедура скомпилирована с директивой interrupt, то есть является обработчиком прерывания. Которое может быть спровоцировано как аппаратно, так и программно вызовом int 08h, вот так:

Так же необходимо описать сами процедуры регистрации, включения и остановки потоков. Если кому-то интересно — можно посмотреть в исходниках процедуры RegistrThread, RunThread, StopThread.
Вот и всё! Наш планировщик готов.
Исходники вместе примером многопоточной программы написаной под этот планировщих и досовским турбиком можно скачать здесь. Можно поиграться и посмотреть как по разному будут выполняться потоки при вытесняющей и невытесняющей многозадачности (процедура ExecuteRegisterThreads(true/false)), смоделировать ситуацию взаимной блокировки и убедиться в том, что она не всегда диагностируема (я однажды минуту ждал пока возникнет дедлок).
Запускать в системах новее Win98 советую из под DOSbox.

Читайте также: