Имитационное моделирование

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

Отчет об одном из таких исследований имеется в [FINK88]. Имитировалось поведение 50000 процессов со скоростью входа в систему λ = 0.8 и средним временем обслуживания T_s = 1. Таким образом, предполагается, что степень использования процессора равна p=λT_s .=.0.8. Обратите внимание — здесь исследуется только одна степень использования процессора.

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

На рис. 9.14 показано нормализованное время оборота, а на рис. 9.15 — среднее время ожидания. Взглянув на время оборота, мы можем увидеть, что производительность FCFS получается весьма непривлекательной —примерно у трети процессов время оборота более чем в 10 раз превышает время обслуживания; к тому же это самые короткие процессы. С другой стороны, время ожидания при этом одинаково для всех процессов, что обусловлено независимостью стратегии от времени обслуживания.

При применении стратегии RR используется квант, равный одной единице времени (см. рис. 9.14 и 9.15). За исключением очень коротких процессов, продолжительность которых менее одного кванта при этой стратегии нормализованное время оборота равняется примерно 5 квантам для всех процессов, тем самым обеспечивается беспристрастность. Производительность при использовании стратегии SPN выше, если не принимать во внимание короткие процессы. Стратегия SRT, представляющая собой версию SPN с вытеснением, превосходит SPN по производительности, за исключением 7% самых длинных процессов. Как видно по резуль­татам исследований, среди невытесняющих стратегий планирования FCFS отдает предпочтение длинным процессам, a SPN — коротким. Стратегия HRRN разрабатывалась как компромиссное решение, и именно такой, по результатам исследования, она и является. И, наконец, как и ожидалось, стратегия со снижением приоритета с одинаковыми квантами времени для всех очередей неплохо работает с короткими процессами.

Справедливое планирование

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

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

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

Был предложен ряд алгоритмов справедливого планирования [HERN84, KAY88, WOOD86]. В этом разделе мы рассмотрим описанную в [HENR84] схему планирования, реализованную в ряде систем UNIX. Эта схема известна как справедливый планировщик (fair-share scheduler — FSS). FSS при принятии решения рассматривает историю выполнения связанной группы процессов вместе с индивидуальными историями выполнения каждого процесса. Система разделяет пользовательское сообщество на множество групп со справедливым планированием и распределяет процессорное время между ними. Так, если у нас имеется четыре группы, каждая из них получит по 25% процессорного времени. В результате каждая группа обеспечивается виртуальной системой, работающей, соответственно, медленнее, чем система в целом.

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

где

CPU_j (i) – мера загруженности процессора процессом j на интервале i;
GCPU_k (i) — мера загруженности процессора группой h на интервале i;
Pj (i) - приоритет процесса j в начале интервала i (меньшее значение

соответствует большему приоритету);

Base_j — базовый приоритет процесса j;

W_k - вес, назначенный группе k (0<=W_k<=1 и åW_k =1).

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

В табл. 9.7 приведен пример, в котором процесс А находится в одной группе, а процессы В и С — в другой; вес каждой группы равен 0.5. Предположим, что все процессы ориентированы на вычисления и всегда готовы к выполнению. Базовый приоритет всех процессов – 60. Степень использования процессора определяется следующим образом: процессор прерывается 60 раз в секунду; при каждом прерывании увеличивается значение счетчика использования процессора текущего процесса, так же как и соответствующего счетчика группы. Один раз в секунду происходит перерасчет приоритетов.

В приведенной схеме первым запускается процесс А. Позже его вытесняет другой. Процессы В и С теперь имеют более высокий по сравнению с А приоритет, и на выполнение передается процесс В. По окончании второй единицы времени наивысший приоритет снова имеет процесс А, который и передается на выполнение. После этого ситуация повторяется с тем отличием, что теперь наи­высший приоритет имеет процесс С. Очередность выполнения процессов такова: А, В, А, С, А, В, А, С, .... В результате 50% времени процессор занят выполнением процесса А, и 50% — выполнением процессов В и С.

ТРАДИЦИОННОЕ ПЛАНИРОВАНИЕ UNIX

В этом разделе мы рассмотрим традиционное планирование UNIX, используемое как в SVR3, так и в 4.3 BSD UNIX. Эти системы в первую очередь предназначены для работы в интерактивной среде с разделением времени. Алгоритм планирования разработан таким образом, чтобы обеспечить приемлемое время отклика для интерактивных пользователей, в то же время гарантируя отсутствие голодания низкоприоритетных заданий. Хотя описываемый алгоритм и был заменен в более современных версиях UNIX, его изучение как представителя практически используемых алгоритмов с разделением времени не лишено основания. Схема планирования SRV4 соответствует требованиям реального времени, но этот вопрос мы обсудим в главе 10, "Многопроцессорное планирование и планирование реального времени".

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

где

CPU_j(i)— мера использования процессора процессом j на протяжении интервала i;

Р_j (i) — приоритет процесса j в начале интервала i (меньшее значение соответствует большему приоритету);

Base_j — базовый приоритет процесса j;

nice_j — указываемый пользователем коэффициент.

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

• программа свопинга;

• управление блочными устройствами ввода-вывода;

• управление файлами;

• управление символьными устройствами ввода-вывода;

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

Пример работы планировщика приведен в табл. 9.8. Процессы А, В и С создаются одновременно с одним и тем же базовым приоритетом 60 (мы игнорируем наличие значения параметра nice). Таймер прерывает выполнение процесса 60 раз в секунду и увеличивает значение счетчика текущего процесса. В примере предполагается, что ни один процесс не блокируется сам по себе и нет никаких других процессов, готовых к выполнению. Сравните эту таблицу с табл. 9.7.

РЕЗЮМЕ, КЛЮЧЕВЫЕ ТЕРМИНЫ И КОНТРОЛЬНЫЕ ВОПРОСЫ

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

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

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

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

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

• Выбор самого короткого процесса. Выбирается процесс с наименьшим ожидаемым временем работы; вытеснение процессов не применяется.

• Наименьшее остающееся время. Выбирается процесс с наименьшим ожидаемым временем оставшейся работы. Процесс может быть вытеснен другим готовым к выполнению процессом.

• Наивысшее отношение отклика.Принимаемое решение опирается на оценку нормализованного времени оборота.

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

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

Контрольные вопросы

9.1. Кратко опишите три типа планирования процессов.

9.2. Какое требование к производительности системы является критическим в случае использования интерактивной операционной системы?

9.3. В чем заключается отличие времени оборота от времени отклика?

9.4. Какой приоритет (высокий или низкий) представляет малое значение в случае планирования процессов?

9.5. В чем заключается отличие планирования с вытеснением от невытесняющего планирования?

9.6. Кратко опишите FCFS-планирование.

9.7. Кратко опишите круговое планирование.

9.8. Кратко опишите стратегию выбора самого короткого процесса.

9.9. Кратко опишите стратегию наименьшего остающегося времени.

9.10. Кратко опишите стратегию наивысшего отношения отклика.

9.11. Кратко опишите стратегию со снижением приоритета.

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

Планирование рассматривается почти в каждой книге, посвященной операционным системам. Строгий анализ различных стратегий планирования с использованием очередей представлен в [STUC85], [KLEI76] и [CONW67]. В [DOWD93] также содержится поучительный анализ производительности различных алгоритмов планирования.

CONW67 Conway R., Maxwell W., Miller L. Theory of Scheduling. — Reading, MA: Addison-Wesley, 1967.

DOWD93 Dowdy L., Lowery C. P.S. to Operating Systems. — Upper Saddle River, Ш: Prentice Hall, 1993. ,

KLEI76Kleinrock L. Queuing Systems. Volume II. Computer Applications. — New York: Wiley, 1976.¹

STUC85 Stuck В., Arthurs E. A Computer and Communications Network Performance Analysis Primer. — Englewood Cliffs, NJ: Prentice Hall, 1985.

¹ Имеется перевод данной книги: Клейнрок Л. Вычислительные системы с очередями. — М.: Мир, 1979. — Прим. ред.

ЗАДАЧИ

9.1. Рассмотрим следующий набор процессов:

Выполните для данного множества анализ, аналогичный анализу, представленному на рис. 9.5 и в табл. 9.5.

9.2. Выполните предыдущее задание для следующего набора процессов:

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

9.4. Предположим, что у нас имеется следующий набор значений времени разрыва: 13, 13, 13, а начальное приближение равно 10. Постройте график, аналогичный графику, приведенному на рис. 9.9.

9.5.Рассмотрим следующую альтернативу формуле (9.3):

S_n+l=aT_n+(1-aS_n)

X_n+1=min[U, max[L,(bS_n+1)]]

где U и L редставляют собой заранее определенные верхнюю и нижнюю границы значения Т. Значение Х_n+1 используется в алгоритме SPN вместо S_n+l. Какие функции выполняют параметры aи b, и какое влияние высокие и низкие значения данных параметров?

9.6. В невытесняющей однопроцессорной системе очередь готовых процессов содержит три задания в некоторый момент t (непосредственно после завершения то задания), поступивших в систему в моменты времени t_1; t₂ и t₃, ожидаемое время выполнения которых r₁, r₂и r₃, соответственно. На рис. 9.16 показано линейное увеличение отношения отклика этих процессов со временем. Используйте данный пример для поиска стратегии планирования, известной как планирование минимакса отношения отклика, которая минимизирует максимальное отношение отклика для данного пакета заданий, игнорируя другие возможные поступления заданий. Указание: сначала примите решение о том, какое задание будет выполняться последним.

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

9.8. Определим время пребывания Т_r как среднее общее время, затрачиваемое процессом на ожидание и обслуживание. Покажите, что в случае обслуживания "первым вошел — первым вышел" со средним временем обслуживания T_r и степенью загруженности процессора р справедливо соотношение T_r = T_s/(l-r).

9.9. Процессор переключается между готовыми к выполнению процессами с бесконечной скоростью без накладных расходов (это идеализированная модель кругового планирования с использованием квантов времени, которые гораздо меньше времени обслуживания). Покажите, что при распределенных в соответствии с законом Пуассона процессах с экспоненциальным временем обслуживания, входящих из бесконечного источника, среднее время отклика R_x процесса со временем обслуживания х задается соотношением R_х =х/(1-ρ). Указание: обратитесь к основным уравнениям теории очередей, которые можно найти по адресу: http://WilliamStallings.com/StudentSupport.html. Затем примите количество ожидающих процессов в системе перед поступлением данного равным w.

9.10. Большинство круговых планировщиков используют кванты времени фиксированного размера. Приведите аргументы в пользу квантов малого размера, а затем — в пользу большого размера квантов времени. Сравните типы систем и заданий, для которых применимы те или иные аргументы. Есть ли среди них такие, для которых применимы и те, и другие аргументы?

9.11. В системе с очередями новое задание должно ожидать своей очереди на обслуживание. В то время, когда задание находится в состоянии ожидания, его приоритет линейно возрастает со временем со скоростью αот нулевого значения. Задание находится в состоянии ожидания до тех пор, пока его приоритет не сравняется с приоритетом обслуживаемых заданий, после чего оно будет обслуживаться наравне с другими процессами с использованием кругового планирования (при этом его приоритет возрастает со скоростью β, меньшей, чем а). Этот алгоритм известен как круговой эгоистичный, поскольку задания пытаются (понапрасну) монополизировать процессор путем постоянного повышения приоритета. Воспользуйтесь рис. 9.17, чтобы показать, что среднее вре­мя отклика R_x задания со временем обслуживания х задается формулой

где

в предположении, что время поступления и обслуживания распределено экспоненциально, со средними значениями 1/λ и s соответственно. Указание: рассмотрите систему в целом и две подсистемы в отдельности.

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

9.13. Какой тип процессов в целом получает преимущества при многоуровневом возврате — ориентированные на вычисления или ориентированные на операции ввода-вывода? Вкратце поясните свой ответ.

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

9.15. Пять пакетных заданий, от А до Е, поступают в вычислительный центр одновременно. Их ожидаемое время работы — 15, 9, 3, 6 и 12 минут соответственно. Их приоритеты, определенные при передаче заданий, равны соответственно 6, 3, 7, 9 и 4, причем меньшее значение означает более высокий приоритет. Для каждого из перечисленных ниже алгоритмов определите время оборота каждого процесса и среднее время оборота всех процессов. Накладные расходы, связанные с переключением процессов, не учитываются. Поясните, как вы пришли к данному ответу. В трех последних случаях предполагается, что в определенный момент времени работает только один процесс, вытеснения не происходит и все задания ориентированы на вычисления.

а. Круговое планирование с размером кванта, равным 1 мин.

б. Планирование с учетом приоритетов.

в. FCFS при запуске процессов в следующем порядке: 15, 9, 3, 6 и 12.

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

ПРИЛОЖЕНИЕ А. ВРЕМЯ ОТКЛИКА

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

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

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

Таблица 9.9. Диапазоны времени отклика

Более 15 секунд

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

Более 4 секунд

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

От 2 до 4 секунд

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

Менее 2 секунд

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

Менее секунды

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