СПОСОБ УПРАВЛЕНИЯ ОБСЛУЖИВАНИЕМ ЗАПРОСОВ ПОЛЬЗОВАТЕЛЕЙ В ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ Российский патент 1998 года по МПК G06F15/16 

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

Известны способы распределения запросов пользователей в вычислительных системах (см. , например, патент Японии N 2-30534, кл. G 06 F 15/16, и а.с. СССР N 1624473, кл. G 06 F 15/20, 1991), суть которых заключается в распределении заданий процессорам в многопроцессорной вычислительной системе при вертикальном распараллеливании программ. При освобождении любого процессора очередное задание распределяется сразу еще до окончания текущего задания.

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

Наиболее близким по технической сущности к заявленному способу распределения запросов пользователей в вычислительной системе является способ, реализованный в устройстве по а. с. СССР N 1730626 A1, кл. G 06 F 9/46, от 30.04.92.

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

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

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

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

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

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

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

Возможность реализации заявленного способа объясняется следующим образом. Способ предназначен для управления функционированием распределенной объектно-ориентированной системой обработки информации (РООСОИ), создаваемой на базе ассоциации локальных вычислительных сетей (ЛВС). Подобная система представляет собой вычислительную систему с территориально распределенными ресурсами, основными из которых являются серверы объектов (СО), выполняющие функции исполнительных узлов вычислительной системы. Серверы объектов создаются на базе файловых и (или) вычислительных серверов (ФС, ВС) ЛВС и представляют в распоряжение пользователей множество сервисов по обработке информации. Вариант такой системы представлен на фиг. 1.

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

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

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

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

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

Постановка запросов пользователей во входные очереди осуществляется процессорами ведения очередей в соответствии с приоритетами запросов пользователей. Критерии упорядочения очередей (Ki) задаются администраторами соответствующих ЛВС со своих рабочих мест (РМ АдЛВС), что позволяет организовать гибкую стратегию обслуживания запросов абонентов ЛВС, имеющих различные категории приоритетов обслуживания.

Исполнительные узлы вычислительной системы строятся на основе серверов объектов. Сервер объектов представляет собой коллективно используемый сервер, во внешней памяти которого в виде программ (объектов) обработки хранится фрагмент базы значений вычислительной системы. Отличительной чертой предлагаемой схемы является то, что СО, являясь основными исполнителями запросов пользователей, одновременно являются активными элементами децентрализованной системы управления. Последнее обеспечивается надстройкой над операционными системами серверов объектов процессора генерации кластеров требований (КТ) СО и процессора адаптивного выбора очередей запросов пользователей.

Формирование данных о свободных ресурсах РООСОИ осуществляют процессоры генерации кластеров требований СО, которые являются элементами сетевого ПО и в соответствии с частично модифицированными протоколами учета модели управления взаимодействием ВОС/МОС осуществляют контроль загрузки СО, и, по мере выполнения запросов пользователей, генерируют кластеры требований СО, являющиеся требованиями на получение СО запросов пользователей из входных очередей вычислительной системы. Поля, содержащиеся в КТ СО, представлены на фиг. 3.

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

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

После того, как КТ СО сформирован, он передается процессору адаптивного выбора очередей запросов пользователей (ПА-ВОЗ) для формирования адреса входной очереди, из которой будет осуществляться попытка получения исполнительным узлом запроса пользователя для его последующего выполнения.

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

Функционально ПАВОЗ является вероятностным автоматом с переменной структурой, функционирующим в случайной среде (Варшавский В.И. Коллективное поведение автоматов. М. : Наука, 1973. с. 18-42). Автоматическое обучение процессора осуществляется таким образом, чтобы выбор исходящих направлений для передачи КТ СО соотносился с величиной вероятности получения из соответствующих направлений запросов пользователей. Схема, иллюстрирующая его работу, представлена на фиг. 4.

Вышеназванный процессор может находиться в одном из c•k (c=[0,1,2,...C], k=[1,2,...K]) состояний. Величина C задает глубину памяти автомата и выбирается для каждой из опрашиваемых очередей в зависимости от коэффициента группирования запросов пользователей, поступающих из нее в СО. Коэффициент группирования рассчитывается как отношение количества взаимосвязанных запросов пользователей к их общему количеству, полученному СО из входной очереди. Взаимосвязанность запросов может заключаться в требовании преобразовать одни и те же данные или в принадлежности одному пользователю. Величина К является количеством входных очередей, включенных в схему опроса. Адресование определенной очереди осуществляется процессором в том случае, если он находится в любом из состояний c≠0. Алгоритм выбора адресуемых входных очередей запросов пользователей, реализуемый процессором, представлен на фиг. 5.

В исходном положении процессор находится в состоянии с=0 для всех очередей. После того как установлен факт готовности СО к обслуживанию запросов пользователей осуществляется генерация КТ СО и установка его полей. Далее КТ СО адресуется во входную очередь, стоящую в схеме S первой. Если из входной очереди получен запрос пользователя на обработку, то ПАВОЗ для адресуемой очереди переводится в состояние с=с+1, если c < С. Если с=С, то состояние процессора не изменится. Сервером объектов осуществляется обслуживание запроса пользователя и процессор вновь адресует ту же входную очередь (т.к. с≠0).

В том случае, когда запрос пользователя из адресуемой входной очереди не получен, то процессор переводится в состояние с=с-1, и после того, как выполняется условие с=0, он переключается на опрос следующей очереди в схеме S. Если запрос пользователя из опрашиваемой очереди не получен, то ПАВОЗ находится в состоянии с > 0, то попытка его получения повторяется вновь с задержкой z. Задержка z выбирается в зависимости от величины логического расстояния до адресуемой очереди. Значение z=бесконечность свидетельствует о том, что адресуемая очередь в вычислительной системе блокирована.

Совокупность процессоров адаптивного выбора очередей запросов пользователей может объединятся в коллектив вероятностных автоматов с переменной структурой, функционирующий в случайной среде (Варшавский В.И. Коллективное поведение автоматов. М.: Наука, 1973. с. 52-74). Подобное объединение реализуется с целью повышения оптимальности обслуживания запросов пользователей во всей вычислительной системе или на ее фрагменте.

Решение о направлении запросов пользователей на обслуживание в тот или иной СО, кластеры требований которых поступили во входную очередь (выделение свободных ресурсов РООСОИ для выполнения запросов), принимается процессорами обслуживания КТ СО, инициализируемыми на средствах вычислительной системы, в которых осуществляется ведение входных очередей. Процессор обслуживания содержит системный справочник объектов, который корректируется при поступлении КТ СО на основании содержимого поля "КорССО". Решение о выделении тому или иному СО запроса пользователя принимается процессором обслуживания на основе функции системной эффективности, агрегирующей индивидуальные эффективности СО и являющейся оценкой порядка системной эффективности вычислительной системы. Порядок системной эффективности в данном случае может быть определен по аналогии с определением порядка коллективного благосостояния в теории кооперативного принятия решений (Мулен Э. Кооперативное принятие решений: Аксиомы и модели.- М.: Мир, 1991, с. 55-62). Естественным требованием к свойствам порядков системной эффективности, которые могут использоваться в децентрализованной системе управления, является их сепарабельность. Поскольку сепарабельный порядок определяется на всех подмножествах множества управляющих процессоров системы управления, то это обеспечивает возможность на его основе принимать оптимальные управляющие решения располагая лишь локальной информацией об вычислительной системе и характеристиках протекающего в ней информационного процесса.

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

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

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

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