Взаимодействие и планирование процессов ос кратко

Обновлено: 05.07.2024

Планирование процессов в ОС это процесс выбора – кто будет исполняться следующим и как долго это будет исполняться.

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

Переключения контекста это не есть операция планирования, это техническая операция.

Происходит прерывание;
Поток вызывает исключение или ловушку (trap);
После этого выбирается другой поток.

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

Классы планировщиков

Пакетный – ориентирован на длительные задачи, которые требуют больших вычислительных ресурсов, где не требуется частое прерывание. Т.е. подразумевают обработку больших задач большими пакетами, нет ограничения на время выполнения.
Интерактивный – ориентирован на снижение времени отклика, т.е. чтобы система казалась”отзывчивой”. Обычные абонентские системы на ПК – это интерактивные системы, когда в ответ на действие пользователя (например перемещение мыши) ОС что-то делает. И всегда пользователю хочется, чтобы этот ответ происходил как можно быстрее.
Главное чтобы на поступающий в систему запрос был получен максимально быстро ответ. Запрос – это любое взаимодействие с компьютером.
Реального времени – специализированные класс, ориентированный на дедлайн – предельный срок завершения какой-либо работы.Главное, чтобы определенное действие завершалось к определенному сроку, это понятие называется дедлайн .Поступающий запрос должен быть обработан не более, чем в определенный промежуток времени.Классический пример СРВ – управление ядерным реактором, в котором превышение времени отклика приведет к аварийной ситуации.

Уровни планирования

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

Основной задачей планирования процессов в ОС является обеспечение высокой производительности ОС.

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

Что концептуально требуется при проектировании планировщика ОС:

Максимизировать использование ЦП (чтобы он максимальноработал на задачах)
Максимизировать пропускную способность(числовыполненных запросов в единицу времени)
Минимизировать среднее время отклика (среднее время отподачи запроса до завершения обработки ответа)
Минимизировать среднее время ожидания (среднее времяот подачи запроса до начала его выполнения)
Минимизировать энергии (джоулей на инструкцию)

Метрики планирования

На следующем рисунке рассмотрим пример метрики планирования.

ta— время поступления процесса (когда процесс становится готовым к выполнению);

Tw – время ожидания (которое тратит процесс в очереди на выполнение);

Ts – время выполнения ЦП;

Tr – время оборота (общее время на ожидание и выполнение).

На схеме 5 и 6 процессы поступили в очередь готовых процессов.

5 задержался из-за 1-4 процесов. Для пятого процесса Tw – время ожидания Ts – время выполнения ЦП.

Время оборота это время от момента его поступления до момента, когда завершилось его выполнение Tr=Tw+Ts.

При планировании процессов главным остается вопрос: Как выбрать какой процесс будет работать дольше и дальше?

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

FIFO — классика – первым пришел, первым ушел
Кратчайшая работа следующей , т.е. следующей выбирается работа, которая требует наименьшего времени завершения
Round-robin
Многоуровневая очередь
Многоуровневая очередь с обратнойсвязью

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

FIFO

В данном случае мы будем его понимать как невытесняющую многозадачность

Процессы планируются по мере их поступления;
Время выполнения не учитывается (никак совсем);
Другие процесс с меньшим временем Tr вынуждены ждать (снижается отзывчивость системы);
Когда процесс переходит в состояние готовности он перемещается в конец очереди.

Пример FIFO

Допустим есть три процесса, которые пребывают в одно и тоже время t=0 в порядке P1,P2,P3.

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

Burst(Р1)=24 (усл.ед.времени)
Burst(Р2)=3
Burst(Р3)=3

Тогда Время ожидания

Среднее время ожидания = 17

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

Допустим процессы поступают в порядке Р2,Р3,Р1

Тогда время ожидания

Среднее время ожидания =3

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

За данным простым примером скрыта вся мощь и важность алгоритмов планирования процессов в ОС.

Обобщения по FIFO:

Он больше других подходит для длительных, требовательных к времени ЦП процессов;
Плохое использование ЦП и устройств ввода/вывода;
Среднее время ожидание сильно варьируется.

Кратчайшая работа следующей

Условимся, имеется в виду невытесняющая политика планирования – сколько квант времени запрашивает процесс, столько ему и выделяется.

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

Сложности:

Нужно оценивать требуемое время обработки для каждого процесса.

Для пакетных заданий на основе предыдущего опыта или вручную (нет гарантии, что повторится)
Для интерактивных заданий на основе затраченного времени

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

Кратчайшая работа следующей вытесняющий вариант

Существует вытесняющий вариант метода кратчайшей работы следующего.

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

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

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

А те процессы, которым еще долго работать, оставить на потом и заняться ими “в плотную”. Логика в этом есть.

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

Планирование с приоритетами

Тот же алгоритм кратчайшей работы следующей можно представить, как планирование с приоритетом, где приоритет – наименьшее время работы.

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

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

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

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

Проявляется в алгоритме КРС. Низкоприоритетные запросы могут никогда не выполниться.

Решение проблемы:

Приоритет = Оценочное время выполнение на ЦП – время ожидания

Приоритеты – это инструмент с помощью которого необходимо сделать общий процесс планирования эффективным.

Round-robin

Данный алгоритм планирования обозначает циклический алгоритм с вытесняющим планированием.

Каждый процесс получает фиксированный квант процессорного времени (фиксированную единицу процессорного времени).
После истечения кванта времени процесс принудительно вытесняется и помещается в очередь готовых к выполнению.
Процесс всегда планируются в том же порядке и каждый процесс получает одинаковый квант времени
Не сложно подсчитать: если квант времени равен q и n-процессов в очереди, то каждый получит 1/n времени ЦП, кусками максимум по q
Никакой из процессов не ожидает больше, чем (n-1)*q единиц времени

Производительность Round-robin(RR)

Если q большое(стремиться к ∞), то RR перерождается в алгоритм FIFO;
Если q малое (но не стремится к 0, иначе ПК будет только переключать процессы и больше не выполнять вообще ничего), то все хорошо;
Нет старвации;
Появляется высокая отзывчивость системы;
Равное распределение времени;
Если q меньше, чем время, затрачиваемое на переключение контекста, тогда диспетчер будет неэффективным.

Недостаток Round-robin

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

Есть 2 процесса Р1 и Р2

Р2 в это время активно использует ЦП, например, считает.

Проблема RR в том, что не учитываются задержки, и полезное время работы Р1 составляет только 10%.

Многоуровневые очереди

Выделяется несколько разных очередей, например:

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

у интерактивных процессов RR;
у фоновых — FIFO.

1) Планирование с фиксированным приоритетом

Вначале обслужить все интерактивные процессы, потом все фоновые
Возможна старвация

2) Разделение времени

Каждой очереди выделяется часть времени ЦП, которую она может распланировать между своими процессами. Например 80% времени ЦП на интерактивные процессы через RR, 20% на фоновые через FIFO.

3) Многоуровневая очередь с обратной связью

Многоуровневая очередь с обратной связью

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

Многоуровневая очередь с обратной связью

Если он средний по времени выполнения, то в среднюю.

Если он требует много времени вычислительных ресурсов, то он помещается в последнюю очередь FIFO.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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мс

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

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

10/30+15/40+5/50=0.808 4.4.3 Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

За время своего существования процесс многократно изменяет свое состояние. Обычно различают следующие состояния процесса:

• новый (процесс только что создан);

• готовый (процесс ожидает освобождения CPU);

• выполняемый (команды программы выполняются в CPU);

• ожидающий (процесс ожидает завершения некоторого события, чаще всего операции ввода-вывода);

• завершенный (процесс завершил свою работу).

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

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

1) определение момента времени для смены выполняемого процесса;

2) выбор процесса на выполнение из очереди готовых процессов;

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

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

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

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

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

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

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

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

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

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

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

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

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

Значительным преимуществом невытесняющих систем является более высокая скорость переключения с задачи на задачу.

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

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

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

1. Установление факта прерывания (прием сигнала на прерывание) и идентификация прерывания (в операционных системах иногда осуществляется повторно на шаге 4).

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

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

4. Сохранение информации о прерванной программе, которую не удалось спасти на шаге 2 с помощью действий аппаратуры. В некоторых ВМ предусматривается запоминание довольно большого объема информации о состоянии прерванного процесса.

5. Обработка прерывания. Эта работа может быть выполнена той же подпрограммой, которой было передано управление на шаге 3, но в ОС чаще всего она реализуется путем последующего вызова соответствующей подпрограммы.

6. Восстановление информации, относящейся к прерванному процессу (этап, обратный шагу 4).

7. Возврат в прерванную программу.

Шаги 1–3 реализуются аппаратно, а шаги 4–7 – программно.

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

Итак, главные функции механизма прерываний:

– распознавание или классификация прерываний;

– передача управления соответственно обработчику прерываний;