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

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

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

Рассмотрим типичную картину «разбора полетов» неким гипотетическим руководителем: его сотрудник жалуется на регулярную работу сверхурочно из-за неравномерности заданий, и при этом он часто не укладывается в требуемые от него сроки выполнения заданий.

Если руководителю известно, что средняя загрузка этого сотрудника составляет, скажем, 70%, то его воображение услужливо нарисует картинку, подобную той, которую мы изобразили на рис. 1.

Рис. 1. Загрузка сотрудника, идеальный вариант

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

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

Рассмотрим проблему в контексте трех основных российских вопросов: «кто виноват?», «что делать?» и «с чего начать?».

 

«Кто виноват»?

В современном мире мало что делается «с нуля» — его основой давно стали разделение труда и кооперация. Результаты выполнения одного задания тут же становятся основой другого. Однако так называемый «закон Хартри» гласит: «В какой бы стадии ни находилась работа, время, необходимое для ее завершения — величина постоянная». Иными словами, невозможно сказать что-либо определенное о моменте завершения обработки некоторого задания — в любой момент времени обработка может как завершиться… так и не завершиться. А раз нельзя ничего сказать о моменте завершения предыдущего задания, то невозможно говорить о моменте поступления нового. Тем не менее можно формализовать постановку задачи даже в столь непростых условиях.

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

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

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

Если обработка заданий выполняется по принципу «первый пришел — первый обработан», то средняя глубина очереди может быть рассчитана как U/ (1-U), где U есть средняя загрузка, измеряемая как отношение вероятности появления нового задания к вероятности завершения обработки задания (предполагаем, что она не превышает единицы). Соответственно среднее время завершения обработки задания может быть рассчитано как сумма времен ожидания (то есть обработки ранее прибывших заданий) и собственно времени обработки задания. Зная среднюю глубину очереди, можно рассчитать время обработки как T0/ (1-U), где T0 — среднее время обработки задания в отсутствие очереди. В таблице 1 приведены расчеты зависимости глубины очереди от значений загрузки.

Табл. 1. Зависимость показателей очереди от загрузки

Как следует из таблицы, даже при загрузке порядка 50% средняя глубина очереди равна единице, а это уже противоречит «здравым» рассуждениям гипотетического руководителя из примера в начале статьи: ведь при такой загрузке сотрудник половину времени вообще ничем не должен заниматься. Тщательный анализ приводит к еще более парадоксальным результатам: поскольку половину времени сотрудник действительно не занят, то средняя глубина очереди его «занятой» половины времени оказывается равной двум. Более того, поскольку некоторую часть «занятой» половины времени глубина очереди должна составлять единицу (в частности при выполнении последнего задания в очереди), то в отдельные моменты времени очередь теоретически может достигать трех. А при уровне загрузки 70% даже средняя глубина очереди превысит два. Также видно, что относительно небольшое изменение загрузки с 50% до 70% приводит к более чем пятикратному увеличению вероятности того, что в очереди окажется четыре и более заданий (включая обрабатываемое).

Основным свойством простейшего потока является ярко выраженная неоднородность поступления заданий. Можно сказать, что его поведение полностью согласуется с известным принципом «где густо, а где пусто». Пусть, например, на обработку сотруднику последовательно поступили задания А, В и С с разным временем обработки — задания А и С обрабатываются соответственно в четыре и два раза дольше, чем задание В (рис. 2). Пусть задания В и С пришли до завершения обработки задания А и были помещены в очередь. Тогда максимальная глубина очереди оказывается равной трем, причем задание В ожидало обработки в три раза дольше, чем собственно обрабатывалось. Фактически этот рисунок указывает на неопределенности моментов поступления и трудоемкости заданий как основных причин дополнительных задержек в обработке заданий сотрудником из примера в начале статьи — даже при фактически свободных 30% времени.

Рис. 2. Изменение глубины очереди

Таким образом, вызываемые очередями аномалии влияют на потребительские свойства системы подчас не меньше, чем собственные характеристики этой системы. Причины возникновения аномалий внутри системы связаны с полностью неопределенным характером ее взаимодействия с внешним миром в соответствии с «законом Хартри», вследствие чего описанные проблемы носят вполне объективный характер и потому должны решаться на основе научного подхода.

 

«Что делать?»

Для снижения дополнительных задержек при обработке поступающих заданий, рекомендуются следующие меры (об этом см. также: Д.Р. Кокс, У.Л. Смит. Теория очередей. М.: Мир, 1966).

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

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

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

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

 

Снижение вариации длительности обслуживания и повышение однородности

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

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

Благодаря этому теоретически обеспечивается использование 100% возможностей коммуникационных каналов и оборудования связи.

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

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

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

 

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

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

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

Рис. 3. Пример классификации трафика и распределения ресурсов

На рисунке 3 приведен пример классификации трафика и рекомендации по распределению пропускной способности канала (Enterprise QoS Solution Reference Network Design Guide. Copyright © 2005, Cisco Systems, Inc.). Для маркировки пакетов могут, например, использоваться поля QoS в заголовках канального уровня, а также поля Precedence/DSCP в IP-заголовках.

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

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

Например, порядок устранения инцидентов определяется с учетом количества затрагиваемых пользователей и устройств, а также повременной стоимости их простоя (Поддержка услуг. М.: ОАО «Первая образцовая типография», 2006). Если же известно примерное время устранения сбоя, то при определении приоритета удобно использовать частное от деления повременной стоимости простоя затронутых инцидентом пользователей и устройств на ожидаемое время устранения инцидента; чем выше значение частного, тем выше назначаемый приоритет.

 

Управление глубиной очередей

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

Управление глубиной очереди наиболее актуально при передаче данных и для телекоммуникаций, поскольку информационные буферы телекоммуникационного оборудования размещаются только в оперативной памяти и ограничиваются ее объемом. При заполнении буферов до некоторого порогового значения устройство может начать «отбрасывать» приходящие пакеты в соответствии с явным на то указанием (например, согласно значению бита Discard Eligible в заголовке пакетов Frame Relay), либо руководствуясь значениями полей Precedence/DSCP в IP-заголовках.

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

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

 

Изменение производительности

Снижение дополнительных задержек за счет изменения производительности подразумевает: увеличение общего количества «обработчиков заданий» (использование технологии EtherChannel, нескольких серверов, увеличение численности исполнителей), дополнительное повышение доступности «обработчиков заданий» путем изменения порядка распределения заданий (применение технологии multilink PPP, мониторов транзакций и координирование работы исполнителей), а также использование более производительного «обработчика заданий» (канал с повышенной пропускной способностью, более мощный процессор или сотрудник более высокой квалификации).

Также можно попробовать найти оптимальное соотношение между загрузкой обработчика и временем обработки задания, что особенно важно при планировании загрузки персонала. Сюда же можно отнести обоснование степени загрузки персонала, поскольку оплата труда обычно является основной статьей расходов современных предприятий. Если некоторый специалист является уникальным в своей области, то его эффективность будет описываться кривой «А» на рисунке 4, то есть до определенного порога заметные увеличения нагрузки U не приводят к существенному росту времени T обработки задания. Однако после достижения этого порога даже незначительное увеличение нагрузки U приводит к заметному приросту времени Т. Поэтому на практике важно определить этот порог исходя из максимума отношения нагрузки U ко времени обработки задания T. Можно показать, что он будет достигаться при уровне загрузки порядка 50%. Аналогичным образом можно найти оптимальную нагрузку для различного количества «обработчиков». При этом можно использовать другие критерии оптимизации, например, с учетом стоимости затрат на обработку заданий, а также финансовых потерь от дополнительных задержек из-за перегрузки «обработчика».

Примечание: полученная расчетная величина 50% идет вразрез с общепринятым рекомендуемым уровнем загрузки персонала 120%. Но для достижения такого уровня загрузки необходима высочайшая квалификация менеджера, поскольку задания должны поступать как минимум заблаговременно и должна существовать непротиворечивая система приоритетов их выполнения. Превышение же теоретического максимума загрузки в 100% означает либо отбрасывание части наименее приоритетных заданий, либо примерно 10-часовой рабочий день, либо сознательное снижение качества работ.

Рис. 4. Влияние методов повышения производительности на время отклика

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

Кривая «А» соответствует одному устройству базовой производительности и в дальнейшем будет использоваться для сопоставительного анализа. Обратим внимание на то, что относительное время обработки 2 достигается при загрузке 50%.

Кривая «В» описывает функционирование двух устройств базовой производительности, задания которым назначаются последовательно из общего простейшего потока заданий. По сравнению с кривой «А», здесь относительное время обработки 2 сохраняется вплоть до уровня загрузки 100%, то есть по 50% на каждый обработчик.

Кривая «С» описывает функционирование двух устройств базовой производительности с возможностью перераспределения заданий между ними; иными словами, устройства обрабатывают общий простейший поток заданий. Расчет был выполнен в соответствии с рекомендациями, изложенными в AS/400 HTTP Server Performance and Capacity Planning. © IBM 2000. Как видно из рисунка 4, для кривой «С» относительное время обработки 2 сохраняется вплоть до уровня загрузки 140%, или по 70% на каждый обработчик — т. е. примерно на 40% большей, чем для кривых «А» и «В». Фактически кривая «С» объясняет выгоды консолидации ресурсов — от информационных до людских.

Кривая «D» описывает функционирование одного устройства двукратной производительности. Здесь относительное время обработки, равное 2, сохраняется вплоть до уровня загрузки в 150% (реально 75% с учетом удвоенной производительности обработчика — то есть примерно в 1,5 раза больше, чем для кривых «А» и «В»).

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

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

 

«С чего начать?»

Теперь, когда причины явления и способы борьбы с ним известны, дело за малым — «уговорить Ротшильда». Ведь любые изменения потребуют затрат, больших или малых, но без них даже самые лучшие идеи останутся только на бумаге.

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

С одной стороны, у каждой группы рекомендаций есть своя «ниша», в которой их применение дает максимальный эффект. С стороны, необходимо помнить, что если ожидаемая нагрузка превышает 100%, то без изменения пропускной способности системы не обойтись.

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

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

Табл. 2. Допустимая загрузка устройств различной производительности.
* — относительно базового устройства, в скобках приведена реальная загрузка

В области высоких загрузок разница между линиями «C» и «D» на рисунке 4 минимальна. В этом случае допустима экстенсивная модернизация за счет увеличения количества недорогих средств обработки информации. Хорошим дополнением будет управление глубиной очереди и назначение приоритетов заданиям.

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

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

Игорь Щетинин — руководитель отдела технического проектирования компании «Ай-Теко», shchetinin@i-teco.ru