Содержание
1 Введение … 3
2 Алгоритм Round Robin … 5
3Перепланировка процессов … 8
4Дескриптор и контекст процесса … 10
5Спецификация на разработку программного комплекса «Планировщик и диспетчерпроцессов» … 15
5.1 Общееописание … 15
5.2Основные компоненты … 15
5.3Ответственность компонентов … 16
5.4 Правилакоммуникации … 16
5.5Основные структуры данных … 16
6 Системныевызовы «Создать процесс» и «Удалить
процесс» … 18
6.1Системный вызов «Создать процесс» … 18
6.2Системный вызов «Удалить процесс» … 20
7Заключение … 22
ПриложениеА. Графические материалы … 23
Библиографическийсписок … 26
1 Введение
1.1Когда компьютер работает в многозадачном режиме, на нем могут быть активными(находится в состоянии готовности) несколько процессов (от двух и более), пытающихсяодновременно получить доступ к одному процессору. Поэтому необходимо выбирать,какой процесс запустить следующим. Отвечающая за это часть Операционной системы(ОС) называется планировщиком, а используемый алгоритм – алгоритмом планирования.Помимо правильного выбора следующего процесса, планировщик также должензаботится об эффективном использовании процессора, поскольку переключение междупроцессами требует затрат.
1.2В многозадачном режиме процессы могут находиться в одном из трех основных состояний:исполнение, готовность или ожидание. Граф изменения состояний процессовпроиллюстрирован на рисунке 1.1. В состоянии исполнения может находиться толькоодин процесс. В состоянии готовности могут находиться несколько процессов. Дляоперативной выборки процессов на исполнение ОС всегда поддерживает двусвязныйсписок готовых процессов. В данном списке всегда находится хотя бы один элемент(процесс, запускаемый в случае «простаивания» системы). В состоянии ожиданиятакже могут находиться несколько процессов. Для организации ожидающих процессовтакже используются двусвязные списки. Но, в отличие от списка готовыхпроцессов, для ожидающих процессов используется один список для каждогоконкретного ресурса. Сколько разделяемых ресурсов, столько и списков заблокированныхпроцессов.
SHAPE * MERGEFORMAT
Ожидание
Исполнение
Готовность
1
2
3
4
Рисунок 1.1– Граф изменения состояния процессов
Нарисунке 1.1 номерами обозначены ситуации, когда происходит данный переход: 1 – планировщиквыбирает данный процесс из списка готовых процессов, 2 – квант данного процессаистек и планировщик выбирает другой процесс, 3 – процесс блокируется, ожидаявходных данных, 4 – поступили ожидаемые входные данные.
2Алгоритм RoundRobin
2.1Одним из наиболее старых, простых, справедливых и часто используемых алгоритмовпланирования является алгоритм циклического планирования или Round Robin (RR). Он работаетпо следующему принципу. Каждому процессу предоставляется некоторый интервалвремени процессора (квант времени). Если к концу кванта времени процесс все ещеработает, он прерывается, а управление передается другому процессу. Еслипроцесс блокируется или прекращает работу раньше отведенного ему квантавремени, то переход управления происходит в этот момент. Алгоритм работыпроиллюстрирован на рисунке 2.1. Так какиспользуется приоритетное планирование, то сначала из списка готовых процессоввыбирается процесс с наивысшим приоритетом. Если в списке остались толькопроцессы с одинаковым приоритетом, то выбирается самый первый. После того, какновый процесс попадает в очередь готовых процессов, он помещается в конецочереди. Когда процесс отработал свой квант или вышел из состояния блокировки,он также помещается в конец очереди.
SHAPE * MERGEFORMAT
А
Е
Б
В
Г
Д
2
2
3
1
Направление обхода списка процессов
Текущий
(работающий)
процесс
Приоритет
процесса
Г
А
Б
В
Д
Е
3
2
2
1
Направление обхода списка процессов
Текущий
(работающий)
процесс
Приоритет
процесса
Следующий
выбираемый
процесс
Следующий
выбираемый
процесс
t
Рисунок 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
Продолжение таблицы 4.1
Название
поля
Описание
Диапазон допустимых значений
Когда значение достигнет 0, процесс переносится в конец очереди готовых процессов.
Приоритет процесса
Условное значение, по которому планировщик определяет, какой процесс выбрать на обслуживание. От 0 до 4 – приоритеты, назначаемые ядром ОС для своих нужд. От 5 до 9 – приоритеты, назначаемые пользователем для своих нужд. 0 – самый высокий приоритет, 9 – самый низкий приоритет.
0 — 9
Базовый адрес контекста процесса
Содержимое регистра TR (содержит селектор дескриптора в GDT). Команда LTR загружает регистр TR. Кроме загрузки непосредственно селектора, процессор автоматически загружает базовый адрес, лимит и атрибуты из дескриптора, находящегося в GDT. Команда STR сохраняет содержимое регистра TR в РОН или ОЗУ.
0 — 216
Продолжениетаблицы 4.1
Название
поля
Описание
Диапазон допустимых значений
Информация о ресурсах
Список, содержащий информацию об открытых файлах, программных каналах, именованных каналах, общих областях ОП и т.д.
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
Продолжение таблицы 4.2
Название
поля
Описание
Диапазон
допустимых
значений
Регистр 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 с относительными приоритетами), список заблокированныхпроцессов (организован по принципу список списков, то есть внутри списказаблокированных процессов находятся списки процессов, ожидающих ответ от НЖМД,ожидающих ответ от НГМД, ожидающих определенный семафор, ожидающих определеннуюочередь сообщений, ожидающих определенного сигнала и т.д.).
5.5.2Указатель на начало списка готовых процессов, указатель на конец списка готовыхпроцессов.
5.5.3Указатель на структуру-описатель списка списков заблокированных процессов.Данная структура хранит в себе информацию о начале и конце каждой очереди. Вслучае появления нового устройства в системе необходимо только создать новуюочередь и добавить информацию об ее начале и конце в данную структуру.
6 Системныевызовы «Создать процесс» и «Удалить процесс»
6.1Системный вызов «Создать процесс»
Системныйвозов «Создать процесс» служит для создания почти полной копии родительскогопроцесса (процесса, в котором был инициирован системный вызов). Для созданияпочти полной копии вызывающего процесса ОС должна скопировать некоторые данныеиз процесса-родителя в процесс-потомок. Выполнение процессов разделяется последанного системного вызова. Имя системного вызова вызова: creat_proc. Входныеданные: отсутствуют. Выходные данные: идентификатор процесса. Сам системныйвызов реализован в ядре ОС, к которому обращается программа-заглушка всистемной библиотеке (через прерывание). Перечень действий, совершаемым ядромОС, представлен в таблице 6.1.
Таблица 6.1 – Системный вызов«Создать процесс»
№ этапа
Описание этапа
1
Проверить возможность создания нового процесса (кол-во процессов
2
Выделить память в области ОС для дескриптора процесса.
3
Создать дескриптор для нового процесса.
4
Назначить новому процессу идентификатор.
5
Записать в поле «Идентификатор родительского процесса» идентификатор процесса-родителя.
6
Скопировать содержимое полей (приоритет, информация о ресурсах и идентификатор пользователя, запустившего процесс) дескриптора процесса-родителя.
7
Выделить память в области пользователя для процесса.
8
Выделить память в области ОС для контекста процесса.
9
Настроить содержимое контекста нового процесса.
10
Полностью скопировать образ памяти из процесса-родителя.
11
Обновить информацию у процесса-родителя о потомках.
12
Добавить указатель о новом процессе список готовых процессов.
6.2Системный вызов «Удалить процесс»
Системныйвызов «Удалить процесс» служит для удаления уже существующего процесса. Причемудаление совершается самим ядром в принудительном порядке. Имя системноговызова: kill_proc. Входные данные: идентификатор процесса. Выходныеданные: отсутствуют. Сам системный вызов реализован в ядре ОС, к которомуобращается программа-заглушка в системной библиотеке (через прерывание). Такжепрограмма-заглушка проверяет допустимость входного параметра. То есть идентификаторпроцесса должен быть беззнаковым 2-байтным целым числом. Перечень действий,совершаемым ядром ОС, представлен в таблице 6.2.
Таблица 6.2– Системный вызов «Удалить процесс»
№ этапа
Описание этапа
1
Проверить существование данного идентификатора в таблице процессов.
2
Удалить информацию о текущем процессе из процесса-родителя.
Продолжение таблицы 6.2
№ этапа
Описание этапа
3
Удалить из всех очередей указатель на дескриптор текущего процесса.
4
Освободить память от дескриптора, контекста и ОП уровня пользователя текущего процесса.
5
Вызвать планировщик.
7Заключение
7.1В данном проекте была рассмотрена разработка программно-аппаратного комплекса«Планировщик и диспетчер процессов в системе разделения времени» с алгоритмомпланирования RR иотносительным приоритетом, а также некоторые системные вызовы. Проект показал,что программу планировщик надо разрабатывать очень тщательно, так как онаявляется основой любой многозадачной ОС. В итоге получилось, что для нормальнойработы планировщика и диспетчера процессов необходимо иметь в области ОП ОС какминимум дескриптор и контекст для каждого процесса, список готовых изаблокированных процессов. Также выяснилось, что переключение процессов – этодлительная операция, так как приходится переключаться из режима пользователя врежим ядра, запускать процесс планировки, потом диспетчеризации, а потом сновапереключаться обратно, на уровень пользователя. Системные вызовы создания иудаления процесса также требуют времени на обработку, так как им тоже нужноманипулировать данными в области ОЗУ ОС, для чего требуется также переключатьсяна уровень ядра.
Приложение А
Графические материалы
SHAPE * MERGEFORMAT
Начало
Конец
Выбрать первый элемент из списка в качестве максимального (по приоритету). Указатель на текущий элемент равен указателю на голову списка
Сдвинуть указатель текущего элемента на следующий элемент
Указатель на текущий элемент равен указателю на хвост списка
Нет
Да
Настроить указатель головы на максимальный элемент
Приоритет следующего элемента больше приоритета текущего элемента
Выбрать следующий элемент в качестве максимального элемента
Да
Нет
Рисунок А.1 – Блок-схемаалгоритма работы планировщика
с очередью готовых процессов
SHAPE * MERGEFORMAT
Начало
Конец
Выбрать из параметров вызова нужную очередь заблокированных процессов
Настроить указатель головы на первый элемент списка
Рисунок А.2 – Блок-схемаалгоритма работы планировщика
с очередью заблокированных процессов
SHAPE * MERGEFORMAT
Начало
Если планировщик вызван по прерыванию или системному вызову, связанному с разделяемым ресурсом, то запустить функцию работы с очередью заблокированных процессов
Если требуется планирование, то запустить функцию работы с очередью готовых процессов
Если требуется диспетчеризация процессов, то запустить диспетчер
Конец
Рисунок А.3– Блок-схема алгоритма работы планировщика
SHAPE * MERGEFORMAT
Начало
Конец
Сохранить контекст текущей задачи
Загрузить контекст новой
задачи
Рисунок А.4– Блок-схема алгоритма диспетчеризации