Планирование процессов. Критерии и параметры планирования

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

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

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

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

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

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

- справедливостью – гарантией каждому заданию или процессу определенной части времени использования процессора, стараясь не допустить возникновения ситуации, когда процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не начинал выполняться;

- эффективностью – максимальной занятостью процессора, не позволяющей ему простаивать в ожидании процессов, готовых к исполнению (в реальных вычислительных системах загрузка процессора колеблется от 40 до 90%);

- сокращением полного времени выполнения (turnaround time) – обеспечением минимального времени между стартом процесса (или его постановкой в очередь для загрузки) и его завершением;

- сокращением времени ожидания (waiting time) – времени, которое проводят процессы в состоянии готовность в очереди на исполнение;

- сокращением времени отклика (response time) – минимизированием времени, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

Независимо от целей планирования, алгоритмы планирования должны обладать следующими свойствами:

- быть предсказуемыми, то есть одно и то же задание должно выполняться приблизительно за одно и то же время;

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

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

- обладать масштабируемостью – не терять работоспособность при увеличении нагрузки.

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

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

- каким пользователем запущен процесс или сформировано задание;

- каков приоритет задачи, поставленной на выполнение;

- сколько процессорного времени запрошено для решения задачи;

- каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода;

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

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

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

- сколько времени прошло с момента выгрузки процесса на диск или его загрузки в оперативную память;

- сколько оперативной памяти занимает процесс;

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

Для краткосрочного планирования используются два динамических параметра:

- CPU burst – промежуток времени непрерывного использования процессора;

- I/O burst – промежуток времени непрерывного ожидания ввода-вывода.

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

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

- процесс переводится из состояния исполнение в состояние завершил исполнение;

- процесс переводится из состояния исполнение в состояние ожидание;

- процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера);

- процесс переводится из состояния ожидание в состояние готовность (завершилась операция ввода-вывода или произошло другое событие).

В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и для выполнения необходимо выбрать новый процесс. В случаях 3 и 4 планирование может не проводиться, процесс, который исполнялся до прерывания, может продолжать свое выполнение после обработки прерывания. Если планирование осуществляется только в случаях 1 и 2, то имеет место невытесняющее (nonpreemptiw) планирование. В противном случае – вытесняющее (preempts) планирование. Термин «вытесняющее планирование» возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом.

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

При невытесняющем режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. Переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания операции ввода-вывода или по окончании работы). Этот метод планирования просто реализуем и достаточно эффективен, так как позволяет выделить большую часть процессорного времени для работы самих процессов и до минимума сократить затраты на переключение контекста. Однако имеется возможность полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В этом случае требуется перезагрузка всей вычислительной системы. Невытесняющее планирование используется в Windows 3.1., Apple Macintosh и др.

Дата добавления: 2014-01-07