Планировщик и диспетчер процессов в системе разделения времени

1 Введение

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

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

Рисунок 1.1 – Граф изменения состояния процессов

На рисунке 1.1 номерами обозначены ситуации, когда происходит данный переход: 1 – планировщик выбирает данный процесс из списка готовых процессов, 2 – квант данного процесса истек и планировщик выбирает другой процесс, 3 – процесс блокируется, ожидая входных данных, 4 – поступили ожидаемые входные данные.

2 Алгоритм Round Robin

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

Рисунок 2.1 – Схема работы алгоритма RR

Самым важным атрибутом данного алгоритма является длина кванта времени, отводимого процессу. Слишком малый квант времени приведет к частому переключению процессов и небольшой эффективности. Слишком большой квант времени может привести к медленному реагированию на короткие интерактивные запросы. «Значение кванта времени около 20-50 мс часто является разумным компромиссом [1].»

3 Перепланировка процессов

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

Таблица 3.1 – Моменты перепланировки

№ п/п	Момент перепланировки
1	Завершение процессом своей работы (системные вызовы exit(), cancel() и др.).
2	Блокирование процесса на системном вызове (операции ВВ, семафоре, в ожидании сигнала и т.д.).
3	Добровольное блокирование процесса (системный вызов wait(), sleep() и др.).
4	Истечение кванта времени, отведенного процессу.

Этапы переключения между процессами представлены в таблице 3.2.

Таблица 3.2 – Этапы переключения между процессами

№ этапа	Описание этапа
1	Переключиться из режима пользователя в режим ядра (через прерывание).
2	Сохранить контекст текущего процесса.
3	Сохранить карту памяти (биты-признаки обращения к страницам памяти) текущего процесса.
4	Запустить планировщик для выбора нового процесса.
5	Загрузить контекст нового процесса.
6	Загрузить карту памяти нового процесса в блок управления памятью.
7	Запустить новый процесс.

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

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

Таблица 4.1 – Дескриптор процесса

Название поля	Описание	Диапазон допустимых значений
Идентификатор процесса	Число, однозначно идентифицирующее процесс в ОС. В системе не должно быть процессов с одинаковыми идентификаторами.	0 - 216
Оставшийся квант времени	Назначается ОС при создании процесса. С каждым прерыванием от таймера данное значение уменьшается на едини цу (у активного процесса).	0 - 255
Название поля	Описание	Диапазон допустимых значений
	Когда значение достигнет 0, процесс переносится в конец очереди готовых процессов.
Приоритет процесса	Условное значение, по которому планировщик определяет, какой процесс выбрать на обслуживание. От 0 до 4 – приоритеты, назначаемые ядром ОС для своих нужд. От 5 до 9 – приоритеты, назначаемые пользователем для своих нужд. 0 – самый высокий приоритет, 9 – самый низкий приоритет.	0 - 9
Базовый адрес контекста процесса	Содержимое регистра TR (содержит селектор дескриптора в GDT). Команда LTR загружает регистр TR. Кроме загрузки непосредственно селектора, процессор автоматически загружает базовый адрес, лимит и атрибуты из дескриптора, находящегося в GDT. Команда STR сохраняет содержимое регистра TR в РОН или ОЗУ.	0 - 216
	Название поля	Описание	Диапазон допустимых значений
	Информация о ресурсах	Список, содержащий информацию об открытых файлах, программных каналах, именованных каналах, общих областях ОП и т.д.	0 - 216
	Идентификатор родительского процесса	Для ускоренной работы системного вызова getppid().	0 - 216
	Список идентификаторов процессов-потомков	Для ускоренной работы системного вызова wait().	0 - 216
	Идентификатор пользователя	Для обеспечения многопользовательского режима.	0 - 216

Таблица 4.2 – Контекст процесса

Название поля	Описание	Диапазон допустимых значений
РОН	Содержимое всех регистры общего назначения. EAX, EBX, ECX, EDX. Данное поле должно интерпретироваться как 4 подряд сохраненных 4-байтных значений.	4 * (0 – 232)
Селекторы	Селектор кодового сегмента (CS), селектор сегмента данных (DS), селектор сегмента стека (SS) и селекторы ES, FS, GS дескрипторов в LDT. Данное поле должно интерпретироваться как 6 подряд идущих 2-байтных значений.	6 * (0 – 216)
Регистры смещений	Содержимое всех регистров смещений. EIP, ESP, EBP, ESI и EDI. 5 подряд идущих 4-байтных значений.	5 * (0 – 232)
Регистр флагов	Содержимое регистра EFLAGS.	0 - 232
Название поля	Описание	Диапазон допустимых значений
Регистр LDTR	Селектор дескриптора LDT в GDT.	0 - 247
Регистр CR3	Содержимое регистра, содержащего базовый адрес каталога страниц.	0 - 232
Базовый адрес битового массива разрешенных операций ввода/вывода	Используется для ограничения доступа процесса к определенным портам ВВ. 0 – доступ к порту запрещен, 1 – доступ к порту разрешен.	0 - 255

5 Спецификация на разработку программного компонента «Планировщик и диспетчер процессов (ПИДП)»

5.1 Общее описание

5.1.1 ПИДП – это программный комплекс, который вызывается, когда требуется любое действие, связанное с администрированием процессов в системе (создание/удаление процесса, перенос процесса из очереди заблокированных в очередь готовых и т.д.). Данная программа должна максимально быстро выполнять свои действия, так как она вызывается достаточно часто.

5.2 Основные компоненты

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

5.2.2 Диспетчер – это часть программного комплекса ПИДП, предназначенная для реализации решения, выбранного планировщиком.

5.3 Ответственность компонентов

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

5.4 Правила коммуникации

5.4.1 Функции, обеспечивающие планировку процессов, обмениваются указателями на дескрипторы процессов. Функция, обеспечивающая переключение контекста, работает с указателями на контексты процессов.

5.5 Основные структуры данных

5.5.1 Дескриптор (представлен в таблице 4.1), контекст (представлен в таблице 4.2), список готовых процессов (организован по принципу алгоритма RR с относительными приоритетами), список заблокированных процессов (организован по принципу список списков, то есть внутри списка заблокированных процессов находятся списки процессов, ожидающих ответ от НЖМД, ожидающих ответ от НГМД, ожидающих определенный семафор, ожидающих определенную очередь сообщений, ожидающих определенного сигнала и т.д.).