Планировщик и диспетчер процессов в системе разделения времени (стр. 1 из 2)
Планировщик и диспетчер процессов в системе разделения времени
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 Сначала происходит поиск решения, а потом его реализация, то есть сначала вызывается планировщик, а потом уже диспетчер. Также может вызываться только планировщик, а диспетчер – нет (например, когда требуется просто перенести процесс из очереди заблокированных процессов в очередь готовых, если он получил данные от ВУ). Алгоритмы работы планировщика и диспетчера процессов представлены в приложении А.