9.5. Рекомендуемая литература

Планирование рассматривается почти в каждой книге, посвященной операционным системам. Строгий анализ различных стратегий планирования с использованием очередей представлен в [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. ,

KLEI76 Kleinrock 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.6. Задачи

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

Имя процесса	Время поступления	Время обработки
А В C D E	0 1 3 9 12	3 5 2 5 5

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

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

Имя процесса	Время поступления	Время обработки
А	0	1
В	1	9
С	2	1
D	3	9

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

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

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

S_n+l=T_n+(1-S_n)

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

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

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

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

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

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

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

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

где

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

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

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

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

13. Пять пакетных заданий, от А до Е, поступают в вычислительный центр одновременно. Их ожидаемое время работы — 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 секунды представляют собой верхний предел допустимого времени отклика

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

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

Десятые доли секунды

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

Зависимость производительности работы пользователя в интерактивных приложениях от времени отклика изучалась в ряде работ (см., например, [SHNE84, THAD81, GUYN88]). Эти исследования показали, что когда темп работы таков, что ни пользователь, ни компьютер не ожидают друг друга, производительность резко возрастает при том же, если не более высоком, качестве работы. Достаточно широко применимо в интерактивных приложениях время отклика до 2 секунд, поскольку обычно человеку требуется небольшое время для раздумий над следующей задачей. Тем не менее общая тенденция такова, что с возрастанием скорости отклика растет и производительность работы.

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

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

Время отклика системы. Интервал времени между моментом ввода очередной команды пользователем и моментом завершения вывода ответа на нее на терминал.

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

Еще одна область, где время отклика является критическим, — World Wide Web, независимо от доступа — через Internet или в пределах корпоративной сети. Время получения страницы из Web существенно варьируется, и столь же сильно варьируется степень вовлечения пользователя в работу. Системы с малым временем отклика обычно больше привлекают пользователя и сильнее удерживают его внимание. Как показано на рис. 9.19, наиболее высокий уровень пользовательского внимания у систем, время отклика которых меньше 3 секунд. При времени отклика от 3 до 10 секунд внимание пользователя рассеивается, а время, больше 10 секунд, зачастую приводит к потере пользователя, который попросту завершает работу с данным узлом.

ПРИЛОЖЕНИЕ Б. ОЧЕРЕДИ

В этой главе, как и в ряде последующих глав, используются результаты, полученные в теории очередей. В этом приложении мы представим краткое оп­ределение систем очередей и основную терминологию этой области. Для читателей, незнакомых с анализом очередей, будет полезно получить информацию, ка­сающуюся его основ, по адресу: http://WilliamStallings.com/StudentSupport.html.

Очередь с одним сервером

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

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

В табл. 9.10 приведены основные параметры, связанные с очередями. Элементы поступают в систему с некоторой скоростью λ. В любой момент времени в очереди ожидает обслуживания некоторое количество элементов (может быть нулевым); среднее количество элементов в очереди — w, а среднее время ожидания обслуживания — Т_s. Эта величина усредняется по всем входящим в систему элементам, в том числе обслуживаемым немедленно, без ожидания. Сервер обслуживает элементы со средним временем обслуживания T_s, которое представляет собой интервал между диспетчеризацией элемента и его выходом из системы. Загруженность, ρ, представляет собой отношение времени, в течение которого сервер занят, к общему времени. И, наконец, два параметра описывают систему в целом. Это — среднее количество элементов r, находящихся в системе, включая обслуживающиеся и ожидающие (если таковые имеются), и Т_r — среднее время, затраченное ими на прохождение системы (мы будем говорить о нем как о времени нахождения в системе).³

Таблица 9.10. Параметры системы с очередью

λ — скорость поступления; среднее количество элементов, поступающих в систему за одну секунду. Тs —- среднее время обслуживания каждого поступившего элемента; количество времени, затраченное на обслуживание одного поступившего элемента (без учета времени ожидания в очереди). ρ — загруженность; доля времени, в течение которого сервер находится в состоянии занятости. w — среднее количество элементов, ожидающих обслуживания. Tw — среднее время ожидания (включая как элементы, ожидающие обслуживания, так и элементы, обслуженные немедленно при поступлении в систему (со временем ожидания, равным нулю)). r — среднее количество элементов, находящихся в системе (ожидающих и обслуживаемых). Тr — среднее время нахождения в системе (затраченное на ожидание и обслуживание)

Если предположить, что емкость очереди не ограничена, то системой не будет потерян ни один элемент; будет только отложено обслуживание элементов. При таком условии скорость поступления элементов в систему будет равна скорости их выхода из системы. При увеличении потока элементов в системе возрастает загруженность сервера, и при ρ = 1 достигается насыщение. Таким образом, теоретическая максимальная скорость поступления равна

Однако при приближении к насыщению очередь становится очень большой (и растет неограниченно при ρ = 1). Практические требования, такие, как требования ко времени отклика или ограничения на размер буферов, обычно ограничивают скорость поступления в систему с одним сервером 70-90% от теоретиче­ского максимума.

³ В ряде литературных источников этот термин применяется к среднему време­ни ожидания в очереди до момента обслуживания.

Обычно делаются следующие предположения.

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

• Размер очереди. Обычно предполагается, что очередь не ограничена, т.е. линия ожидания может неограниченно увеличиваться. Если очередь конечна, в системе могут наблюдаться потери элементов. На практике очередь конечна, но в большинстве случаев это не приводит к существенным отличиям в анализе.

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

Очередь со многими серверами

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

Все параметры системы, показанные на рис. 9.20, без изменений переносятся на многосерверную систему, за исключением загруженности сервера. Если у нас имеется N идентичных серверов и ρ — загруженность каждого сервера, то под загруженностью системы мы можем понимать величину Nρ; иногда для этой величины используется термин интенсивность трафика (traffic intensity). Таким образом, максимальная теоретическая загруженность равна N*l00%, а теоретическая максимальная скорость поступления

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

На рис. 9.21,6 показан еще один вариант системы с несколькими серверами, в котором каждому серверу соответствует единственная очередь.