Способ обслуживания разноприоритетных запросов пользователей вычислительной системы

Способ обслуживания разноприоритетных запросов пользователей вычислительной системы

Иллюстрации

Показать все

Реферат

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

Заявленное техническое решение расширяет арсенал средств данного назначения.

Известны способы обслуживания запросов, реализованные, например, в устройстве по Авт. св. СССР №1441398 "Многоканальное устройство динамического приоритета", МПК G 06 F 9/46, опубликованное 30.11.88, где повышение приоритета запроса осуществляется линейно через определенные интервалы времени; и по Авт. св. СССР №1562912 "Многоканальное устройство с динамическим изменением приоритета", МПК G 06 F 9/46, опубликованное 07.05.90, где повышение приоритета запроса происходит после каждого обслуживания заявки по другим приоритетным направлениям.

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

Наиболее близким по своей технической сущности к заявленному является способ обслуживания запросов по патенту РФ №2140666 "Способ обслуживания запросов пользователей вычислительной системы и устройство, его реализующее (варианты)", МПК G 06 F 9/46, опубл. 27.10.99 (Вариант №1).

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

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

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

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

Поставленная цель достигается тем, что в известном способе обслуживания запросов разноприоритетных пользователей вычислительной системы, заключающемся в том, что предварительно задают параметры вычислительной системы, включающие М≥2 разноприоритетных пользователей, Z≥2 приоритетов пользователей, формируют запросы пользователей, принимают их, формируют очередь обслуживания запросов в соответствии с приоритетами пользователей, после чего обслуживают поступившие запросы. Для вычислительной системы, включающей Р≥2 серверов, каждый из которых обладает максимальным вычислительным ресурсом Q_mp, где р=1, 2,..., Р - номер сервера, и к каждому из которых закреплены М_р разноприоритетных пользователей, сформированные запросы пользователей принимают серверами, к которым они закреплены, а очередь на выполнение поступивших запросов формируют на каждом сервере. После этого на каждом сервере вычисляют необходимый вычислительный ресурс на обслуживание поступивших запросов Q_рн. Необходимый вычислительный ресурс р-го сервера Q_рн определяется суммой ресурсов, необходимых для реализации всех поступивших от пользователей запросов, которые в рассматриваемой заявке принимаются одинаковыми. Например, при поступлении на сервер 20 запросов, реализация каждого из которых требует вычислительного ресурса q, необходимый на их выполнение вычислительный ресурс Q_рн равен 20q (Q_рн=20q). Затем вычисляют разницу ΔQ_p=Q_mp-Q_рн между максимальным Q_mp и необходимым Q_рн вычислительными ресурсами р-го сервера. Запоминают полученные разницы ΔQ_p. На каждом сервере при ΔQ_p>0 обслуживают запросы, поступившие от закрепленных за ним пользователей. При ΔQ_p<0 обслуживают часть запросов пользователей, не превышающую максимальный вычислительный ресурс Q_mp сервера, а оставшийся в очереди избыточный объем запросов р-го сервера ΔQ_p сравнивают с положительными значениями ΔQ_n, где n=1, 2,..., Р и n≠р, других серверов. В случае нахождения ΔQ_n≥|ΔQ_p|, передают избыточный объем запросов ΔQ_p р-го сервера на n-й сервер, где обслуживают эти запросы. А при условии ΔQ_n<|ΔQ_p| на всех серверах, избыточные запросы р-го сервера разделяют на части ΔQ_p, где i=1, 2, 3, ... - порядковый номер части разделенного ресурса ΔQ_p, требующих обслуживания оставшихся запросов от одного пользователя р-го сервера. Затем последовательно сравнивают необходимый ресурс для обслуживания ΔQ_p1, ΔQ_p2,..., ΔQ_pi,... с положительными значениями ΔQ_n других серверов и по результатам сравнения передают для обслуживания одну или несколько частей ΔQ_pi разделенного ресурса ΔQ_p, совокупный ресурс на обслуживание которых не превышает ΔQ_n n-го сервера. Причем при ΔQ_pi≥ΔQ_n на всех серверах, на каждом из них в процессе обслуживания собственных запросов повторно вычисляют ΔQ_p, и при достижении избыточности ресурса р-го сервера, при котором выполняется условие ΔQ_p≥ΔQ_pi, на р-м сервере обслуживают запросы ΔQ_pi, а при достижении условия ΔQ_n≥ΔQ_pi на n-м сервере на него передают для обслуживания запросы ΔQ_pi. При этом действия по передаче на n-й сервер избыточных объемов запросов ΔQ_p или их частей ΔQ_pi повторяют до тех пор, пока запросы всех пользователей не будут приняты на обслуживание.

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

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

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

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

Заявленный способ поясняется чертежами, на которых показаны:

фиг.1 - структура вычислительной системы;

фиг.2 - пояснение распределения пользователей вычислительной системы между вычислительными серверами;

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

фиг.4 - схема проведения эксперимента;

фиг.5 - математические ожидания количества обработанных запросов.

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

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

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

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

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

Первоначально в вычислительной системе, содержащей Р≥2 серверов (Сервер №1, сервер №2, сервер №Р на фиг.1), каждый из которых обладает максимальным вычислительным ресурсом Q_mp, где р=1, 2,..., Р - номер сервера, и М≥2 разноприоритетных пользователей с общим числом приоритетов Z≥2, распределяют пользователей между серверами. Для этого за каждым р-м сервером закрепляют примерно равное количество М_р разноприоритетных пользователей (фиг.2).

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

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

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

После этого вычисляют необходимый вычислительный ресурс Q_рн на обслуживание поступивших запросов на каждом сервере (блок 5 на фиг.3). Вычисляют разницу ΔQ_p=Q_mp-Q_рн между максимальным Q_mp и необходимым Q_рн вычислительными ресурсами р-го сервера для оценки возможности вычислительного ресурса р-го сервера для обслуживания всех поступивших запросов. Запоминают полученные разницы ΔQ_p на каждом сервере (блоки 6 и 7 на фиг.3).

На каждом р-м вычислительном сервере в случае, когда ресурсов сервера достаточно для обслуживания всех поступивших запросов (при ΔQ_p≥0), обслуживают запросы, поступившие от закрепленных за ним пользователей (блок 15 на фиг.3). А в случае, когда ресурсов на одном или нескольких серверах недостаточно (при ΔQ_p<0) обслуживают часть запросов пользователей, не превышающую максимальный вычислительный ресурс Q_mp сервера. Это связано с тем, что при выполнении условия обслуживания запросов пользователя на одном сервере количество запросов обслуживаемых сервером может быть меньше, чем позволяет его максимальный вычислительный ресурс, а при попытке обслуживания запросов дополнительного пользователя максимальный вычислительный ресурс оказывается меньше ресурса, требуемого на обслуживание всех запросов. А оставшийся в очереди избыточный объем запросов р-го сервера ΔQ_p сравнивают с положительными значениями ΔQ_n, где n=1, 2,..., P и n≠р, других серверов (блок 9 на фиг.3). Причем обслуживание запросов выполняют в порядке очереди, начиная со старших приоритетов, чтобы в остатке оставались запросы младшего приоритета.

В случае нахождения сервера со свободным вычислительным ресурсом (ΔQ_n≥|ΔQ_p|), передают избыточный объем запросов ΔQ_p р-го сервера для обслуживания на n-й сервер (блок 16 на фиг.3).

При отсутствии на всех серверах свободного вычислительного ресурса ΔQ_n, превышающего избыточный объем запросов р-го сервера ΔQ_p, избыточные запросы разделяют (блок 11 на фиг.3) на части ΔQ_pi, где i=1, 2, 3,... - порядковый номер части разделенного ресурса ΔQ_p, требующих обслуживания оставшихся запросов от одного пользователя р-го сервера. Т.е. в состав каждой отдельной части ΔQ_pi входят запросы только одного пользователя. Затем последовательно сравнивают необходимый ресурс для обслуживания ΔQ_p1, ΔQ_p2,..., ΔQ_pi, ... с положительными значениями ΔQ_n других серверов и по результатам сравнения передают (блок 16 на фиг.3) для обслуживания одну или несколько частей ΔQ_pi разделенного ресурса ΔQ_p, совокупный ресурс на обслуживание которых не превышает ΔQ_n n-го сервера. Например, при наличии на n-м сервере свободного ресурса ΔQ_n и требующих обслуживания запросов, разделенных на части ΔQ_p1≤ΔQ_p2≤ΔQ_p3, при выполнении условий (ΔQ_p1+ΔQ_p2)≤ΔQ_n, ΔQ_p2≤ΔQ_n и ΔQ_p3≤ΔQ_n, но одновременно и выполнения условий (ΔQ_p1+ΔQ_p3)≥ΔQ_n, (ΔQ_p2+ΔQ_p3)≥ΔQ_n, на n-й сервер могут быть переданы для обслуживания ΔQ_p1, или ΔQ_p2, или ΔQ_p3, или (ΔQ_p1+ΔQ_p3). При этом на n-й сервер передают максимально возможный объем запросов от р-го сервера. В приведенном примере передают объем (ΔQ_p1+ΔQ_p2). Оставшиеся части разделенного избыточного ресурса ΔQ_p передают на другие серверы.

В случае, когда отдельные части избыточного объема запросов превышают свободный вычислительный ресурс на всех серверах (при ΔQ_pi≥ΔQ_n), то на всех серверах в процессе обслуживания собственных запросов повторно вычисляют ΔQ_p, и при достижении необходимого уровня свободного ресурса на р-м сервере, превышающего необходимое значение хотя бы одной из частей ΔQ_pi, т.е. при ΔQ_p≥ΔQ_pi, обслуживают избыточные запросы ΔQ_pi (блок 15 на фиг.3). А при достижении необходимого уровня свободного ресурса на n-м сервере (при достижении условия ΔQ_n≥ΔQ_pi), передают избыточные запросы ΔQ_pi для обслуживания на n-й сервер (блок 16 на фиг.3). Действия по передаче на n-й сервер и/или приему на обслуживание на р-м сервере избыточных объемов запросов ΔQ_p или их частей ΔQ_pi повторяют до тех пор, пока запросы всех пользователей не будут приняты на обслуживание.

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

Обобщенная схема проведения эксперимента представлена на фиг.4.

Модель вычислительной системы включала три сервера с заданными максимальными вычислительными мощностями Q_mp=50, 60 и 70 соответственно. За каждым из серверов были закреплены 10 разноприоритетных пользователей. Причем за каждым сервером было закреплено одинаковое количество равноприоритетных пользователей 1-го, 2-го и 3-го приоритетов, как это показано на фиг.2, и объединенных в три сегмента вычислительной системы.

В модели было предусмотрено параллельное выполнение трех независимых друг от друга процессов:

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

процесса, моделирующего загрузку сервера запросами на обслуживание;

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

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

интенсивность поступления запросов - λ, изменяющаяся во времени;

закон распределения времени поступления запросов f(Δt), принят экспоненциальным т.к. создает наиболее тяжелый режим при обслуживании запросов, а при большом числе источников запросов, что соответствует реальной вычислительной системе, суммарный поток стремится к простейшему, имеющему экспоненциальное распределение, независимо от законов распределения отдельных источников (см. Иванов Е.В. Имитационное моделирование средств и комплексов связи и автоматизации. - СПб.: ВАС, 1992. - 206 с.).

Процесс, моделирующий функционирование сервера имитирован работой обслуживающего прибора - устройства или совокупности устройств, выполняющих операции по обслуживанию и диспетчеризации запросов. Таким образом, обслуживающий прибор представляет собой совокупность каналов обслуживания, причем один канал обслуживания соответствует одному серверу. Обслуживающий прибор характеризуется числом каналов обслуживания; интенсивностью обслуживания (μ пакетов/с); законом распределения времени обслуживания F(t₀).

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

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

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

Результаты моделирования приведены в табличном виде на фиг.5а и в виде диаграммы на фиг.5б, из которых видно, что суммарный поток запросов, обслуженных с применением разработанного технического решения (выделен жирным в табличном представлении и обведен рамкой на диаграмме), превышает наилучшие результаты, полученные в других вариантах обработки, на 20% при максимальной загрузке, на 14, 16% при средней и на 1,98% при минимальной загрузке сервера.

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

1. Способ обслуживания запросов разноприоритетных пользователей вычислительной системы, заключающийся в том, что предварительно задают параметры вычислительной системы, включающие М≥2 разноприоритетных пользователей, Z≥2 приоритетов пользователей, формируют запросы пользователей, принимают их, формируют очередь обслуживания запросов в соответствии с приоритетами пользователей, после чего обслуживают поступившие запросы, отличающийся тем, что для вычислительной системы, включающей Р≥2 серверов, каждый из которых обладает максимальным вычислительным ресурсом Q_mp, где р=1, 2,..., Р - номер сервера, и к каждому из которых закреплены М_р разноприоритетных пользователей, сформированные запросы пользователей принимают серверами, к которым они закреплены, а очередь на выполнение поступивших запросов формируют на каждом сервере, после чего на каждом сервере вычисляют необходимый вычислительный ресурс на обслуживание поступивших запросов Q_pn и разницу ΔQ_p=Q_mp-Q_рн между максимальным Q_mp и необходимым О_рн вычислительными ресурсами р-го сервера и запоминают полученные разницы ΔQ_p, на каждом сервере при ΔQ_p≥0 обслуживают запросы, поступившие от закрепленных за ним пользователей, а при ΔQ_p<0 обслуживают часть запросов пользователей, не превышающую максимальный вычислительный ресурс Q_mp сервера, а оставшийся в очереди избыточный объем запросов р-го сервера ΔQ_p сравнивают с положительными значениями ΔQ_n других серверов и в случае нахождения ΔQ_n≥|ΔQ_p|, где n=1, 2,..., Р и n≠р, передают избыточный объем запросов ΔQ_p р-го сервера на n-й сервер, где обслуживают эти запросы, а при условии ΔQ_n<|ΔQ_p| на всех серверах избыточные запросы р-го сервера разделяют на части ΔQ_pi, где i=1, 2, 3,... - порядковый номер части разделенного ресурса ΔQ_p, требующих обслуживания оставшихся запросов от одного пользователя р-го сервера, затем последовательно сравнивают необходимый ресурс для обслуживания ΔQ_p1, ΔQ_p2,..., ΔQ_pi,... с положительными значениями ΔQ_n других серверов и по результатам сравнения передают для обслуживания одну или несколько частей ΔQ_pi, разделенного ресурса ΔQ_p, совокупный ресурс на обслуживание которых не превышает ΔQ_n n-го сервера, причем при ΔQ_pi≥ΔQ_n на всех серверах на каждом из них в процессе обслуживания собственных запросов повторно вычисляют ΔQ_p, и при достижении избыточности ресурса р-го сервера, при котором выполняется условие ΔQ_p≥ΔQ_pi, на р-м сервере обслуживают запросы ΔQ_pi, а при достижении условия ΔQ_n≥ΔQ_pi на n-м сервере на него передают для обслуживания запросы ΔQ_pi, причем действия по передаче на n-й сервер избыточных объемов запросов ΔQ_p или их частей ΔQ_pi повторяют до тех пор, пока запросы всех пользователей не будут приняты на обслуживание.

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

3. Способ по п.1, отличающийся тем, что равноприоритетные запросы одного пользователя обслуживают на одном сервере.