Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задание. Планирование процессов
|
|
Планирование процессов
Для реализации процессов операционные системы используют таблицу, называемую таблицей процессов, в которой каждая запись соответствует одному из процессов. Эти записи содержат данные по каждому из процессов, такие как: приоритет, внутренний счетчик команд, состояние процесса, указатель стека, распределение памяти, состояние открытых им файлов и всю остальную информацию, относящуюся к процессу, для возможности быстрого переключения процесса в различные состояния.
+------------------------------------------------------------+
| алгоритм schedule_process |
| входная информация: отсутствует |
| выходная информация: отсутствует |
| { |
| выполнять пока (для запуска не будет выбран один из про-|
| цессов) |
| { |
| для (каждого процесса в очереди готовых к выполнению)|
| выбрать процесс с наивысшим приоритетом из загру-|
| женных в память; |
| если (ни один из процессов не может быть избран для |
| выполнения) |
| приостановить машину; |
| /* машина выходит из состояния простоя по преры- |
| /* ванию |
| */ |
| } |
| удалить выбранный процесс из очереди готовых к выполне- |
| нию; |
| переключиться на контекст выбранного процесса, возобно- |
| вить его выполнение; |
| } |
+------------------------------------------------------------+
Рисунок 8.1. Алгоритм планирования выполнения процессов
задание
Разработать и реализовать программу (эмулятор планировщика), реализующую модель обслуживания процессов с приоритетами обслуживания и заданным квантом времени.
Алгоритм работы планировщика следующий:
выбираются задачи, требующие по времени исполнения
все найденные задачи последовательно выполняются,
после исполнения всех задач планировщик ещё раз делает выборку задач, которые нуждаются выполнения и делает так по циклу
На рисунке 1.1 номерами обозначены ситуации, когда происходит данный переход: 1 – планировщик выбирает данный процесс из списка готовых процессов, 2 – квант данного процесса истек и планировщик выбирает другой процесс, 3 – процесс блокируется, ожидая входных данных, 4 – поступили ожидаемые входные данные.
Таблица – Моменты перепланировки
| № п/п | Момент перепланировки |
| Завершение процессом своей работы (системные вызовы exit(), cancel() и др.). | |
| Блокирование процесса на системном вызове (операции ВВ, семафоре, в ожидании сигнала и т.д.). | |
| Добровольное блокирование процесса (системный вызов wait(), sleep() и др.). | |
| Истечение кванта времени, отведенного процессу. |
Этапы переключения между процессами представлены в таблице 3.2.
Таблица 3.2 – Этапы переключения между процессами
| № этапа | Описание этапа |
| Переключиться из режима пользователя в режим ядра (через прерывание). | |
| Сохранить контекст текущего процесса. | |
| Сохранить карту памяти (биты-признаки обращения к страницам памяти) текущего процесса. | |
| Запустить планировщик для выбора нового процесса. | |
| Загрузить контекст нового процесса. | |
| Загрузить карту памяти нового процесса в блок управления памятью. | |
| Запустить новый процесс. |
Для обеспечения многозадачности в ОС используется таблица процессов (список), в которой находятся указатели на дескрипторы процессов. Дескрипторы содержат статическую информацию о процессе. Кроме этого в ОС также используется динамическая информация о текущем (работающем) процессе. Совокупность этой информации называется контекстом процесса. Примеры дескриптора и контекста процесса представлены в таблицах 1 и 2, соответственно.
Таблица 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 |
Таблица 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 |
Основные структуры данных
- Дескриптор (представлен в таблице 1), контекст (представлен в таблице 2), список готовых процессов (организован по принципу алгоритма RR с относительными приоритетами), список заблокированных процессов (организован по принципу список списков, то есть внутри списка заблокированных процессов находятся списки процессов, ожидающих ответ от НЖМД, ожидающих ответ от НГМД, ожидающих определенный семафор, ожидающих определенную очередь сообщений, ожидающих определенного сигнала и т.д.).
- Указатель на начало списка готовых процессов, указатель на конец списка готовых процессов.
- Указатель на структуру-описатель списка списков заблокированных процессов. Данная структура хранит в себе информацию о начале и конце каждой очереди. В случае появления нового устройства в системе необходимо только создать новую очередь и добавить информацию об ее начале и конце в данную структуру.
Схематично алгоритм работы планировщика можно представить следующим образом:
Цикл планирования
{
J = Ø; /* J – множество нераспределенных заданий */
/* Выбор заданий */
По всем j Є (множеству заданий)
{
Если j не распределено
J += j;
}
Сортировать J по приоритетам;
1. Исходные данные:
· поток заявок на выполнение процессов (имя заявки, время поступления, приоритет, время исполнения).
2. Результаты работы модели, отображаемые на дисплее, должны для каждого момента времени, когда состояние системы изменяется, включать номер обслуживаемого процесса или фиксировать режим ожидания, а так же список процессов, составляющих очередь. Кроме этого возможна графическая интерпретация результатов работы программы, например в виде диаграммы выполнения процессов.