Дисциплины планирования - требования, показатели, классификация

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

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

Рис.2.1. Представление планирования процессов в виде системы массового обслуживания

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

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

Потерянное время:

M = T - t;

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

Отношение реактивности:

R = t / T;

показывает долю процессорного времени (времени выполнения) в общем времени реакции.

Штрафное отношение:

P = T / t;

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

Средние значения величин T, M, R, P и могут служить количественными показателями эффективности. Реальные системы, как правило, ориентированы на конкретные характеристики процессов, в частности, на определенные диапазоны значений t, поэтому указанные показатели удобно рассматривать как функции длительности процесcа: T(t), M(t), R(t), P(t).

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

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

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

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

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

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

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

Различают приоритеты:

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

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

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

E' = W1 * E + W2 * S

где E - прогноз, сделанный на предыдущем интервале для текущего интервала, W1 и W2 - весовые коэффициенты, подбираемые так, что:

W1 + W2 = 1

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

Содержание раздела