На современном этапе развития вычислительной техники получили развитие распределенные системы обработки информации в вычислительных сетях под управлением распределенных операционных систем. От качества программного обеспечения, решающего задачи оптимального планирования и диспетчеризации, в значительной мере зависит эффективность вычислительной системы в целом, так как решение дополнительных системных задач увеличивает дополнительные расходы машинного времени. Следствием неоптимального планирования процесса обслуживания множества запросов пользователей является уменьшение степени использования информационных ресурсов, а также снижение безопасности и живучести информационной системы [1, 2].
Анализ режимов функционирования сетевой базы данных (СБД) показал, что разработка и сопровождение информационных систем такого типа производится из расчета среднестатистической нагрузки, определяющейся соотношением 80/20, т.е. каждым 80 запросам соответствует 20 транзакций, но такое соотношение не дает реального представления о круглосуточном функционировании информационной системы. В частности, при таком подходе не учитывается почасовая нагрузка в течение суток, когда в периоды реорганизации число транзакций, как правило, превосходит число запросов [3–5].
В качестве примера рассмотрим гистограмму (рис. 1). Ее изучение показывает, что АИУС использующей СБД присущи два критических режима функционирования:
1. Область красного цвета – пиковая рабочая нагрузка, являющаяся суммой пользовательских запросов и запросов на корректировки (транзакций) и определяемая соотношением:
где 
– время реализации р-го запроса пользователя, а 
– время реализации р-го задания на корректировку.
Она характеризуется возрастанием числа запросов до 96 в минуту и числа транзакций до 18 в минуту. Длительность функционирования информационной системы в режиме пиковой нагрузки около 5 часов с 11.00 часов до 16.00 часов. Соотношение соответственно составляет 96/18.
2. Область зеленого цвета – режим реорганизации базы данных. Она характеризуется возрастанием числа транзакций до 45 в секунду и падением числа запросов до 5 в секунду. Продолжительность функционирования информационной системы в режиме реорганизации составляет около 3 часов соответственно с 00.00 до 03.00 часов. Соотношение составляет 5/45.
Рис. 1. Диаграмма соотношения запросы/транзакции в течение суток
Рис. 2. Диаграмма соотношения запросы/транзакции в течение суток с учетом параметра 80/20
Рис. 3. График соответствия правила 80/20 расчета динамической нагрузки транзакций реальной нагрузке
Рис. 4. График соответствия правила 80/20 расчета динамической нагрузки запросов реальной нагрузке
Рис. 5. График суммарной рабочей нагрузки по дням недели
Рис. 6. Схема управления базой данных
Таким образом, соответствие правила 80/20, используемого разработчиками и администраторами для СБД АИУС, справедливо для достаточно идеализированной системы и соответствует истинному только на некотором участке времени. Если предположить, что информационная система функционирует в режиме близком к идеальному все оставшееся время, то даже такое предположение ставит под сомнение правомочность использования данного правила поскольку 8 часов работы информационной системы при критической нагрузке составляет 1/3 суток, при условии, что 5 часов из 8 система функционирует в режиме обслуживания множества запросов пользователей (рис. 2).
Как противопоставление высказанному предположению об идеализированном состоянии информационной системы рассмотрим графики анализа рабочей нагрузки отдельно для транзакций и отдельно для запросов. Как видно из графика (рис. 3), рекомендуемое правило не учитывает возрастание пользовательской нагрузки в системе на указанном участке времени. Такое же состояние наблюдается и для реализации транзакций в системе, что и отображено на графике (рис. 4) соответственно. Исследование поведения рабочей нагрузки, возникающей в СБД для более длительных промежутков времени, показало, что в целом характер ее поведения не изменяется график (рис. 5), и наблюдается только некоторое снижение в конце недели с 56 до 47 запросов в мин., что не является достаточно существенным.
Также в классических моделях не учитываются такие важные ситуации, как возможность захвата некоторыми запросами одновременно пересекаемых областей данных. И наконец, это уровень требований к качеству обслуживания, предъявляемый различными классами запросов пользователей. Последнее обстоятельство снижает точность получаемых результатов и соответственно увеличивает число сбоев и конфликтов, возникающих в исследуемых системах.
Оценка и анализ процессов управления реализацией рабочей нагрузкой в сетевых информационных системах позволили выделить в отдельный класс запросы на корректировку на основе их семантики. Такое разделение рабочей нагрузки позволяет рассмотреть запросы и транзакции как две составляющих, исключив их влияние друг на друга. В классических же моделях указанное разграничение производится посредством применения различного рода блокировок, не семантических свойств языковых операторов.
Все это свидетельствует о необходимости повышения адекватности математических моделей процессов обслуживания запросов в структурно-сложных системах, разработке методов расчета и оптимизации этих систем и алгоритмов оптимального управления ими, обеспечивающих повышение их качества и оперативности [6].
Основной материал
База данных состоит из M таблиц Ті, 
содержащие информацию и системы управления базой данных. К базе данных имеют доступ K операторов Оj, 
, которые формируют запросы к базе данных. Каждый запрос Зp от любого оператора Oj имеет свой приоритет Сp, зависящий от уровня привилегий оператора. Момент времени, в который от оператора поступает запрос – величина случайная. Поэтому на входе системы управления при высокой интенсивности запросов образуются очереди запросов.
Схема управления распределенной базой данных показана на рис. 6.
При наличии ограничений на размер хранимой очереди в системе управления может возникнуть ситуация, при которой очередной запрос, поступивший на вход системы управления, не будет принят к обслуживанию, что приведет к его потере или к задержке в обслуживании. Таким образом, диссипативные структуры могут перейти из одного стационарного состояния в другое в результате неустойчивости предыдущего неупорядоченного состояния при критическом значении некоторого параметра, отвечающего точке бифуркации. В точке бифуркации невозможно предсказать, в каком направлении будет развиваться система: станет ли состояние хаотическим или система перейдет на новый, более высокий уровень упорядоченности [7, 8].
Следует отметить дополнительное требование к системе управления базой данных – система управления должна иметь одновременный доступ к любому количеству таблиц.
Определимся, что под разрешением очереди будем понимать процесс поэтапной выборки запросов из очереди запросов, которые необходимо и возможно выполнить на данном этапе. Запросы в очередь поступают в любой момент времени, но состояние очереди определяется только между этапами.
Для разрешения очереди запросов необходимо выбрать наиболее приемлемый способ выборки запросов и наилучший метод реализации выбранного способа.
Для оценки способа выборки запросов будем использовать коэффициент использования ресурсов KИР . Данный коэффициент показывает, какая часть таблиц из общего количества таблиц, к которым обращаются стоящие в очереди запросы, будет использована. Если KИР = 0, то ни одна таблица не будет использована, а если KИР = 1, то используются все таблицы, к которым существуют запросы на данный момент. Но не всегда возможно выбрать такие запросы, чтобы все таблицы были задействованы. Поэтому перед нами стоит задача выбора такого способа разрешения очереди запросов, при котором KИР стремилось к 1. В общем виде KИР определяется следующим образом:
, (1)
где NИ – количество таблиц, которые будут задействованы при реализации определенной выборки; NО – количество таблиц, к которым существуют запросы из очереди.
Но в данном виде KИР не учитывает приоритеты запросов, поэтому необходимо изменить коэффициент (1), для учета приоритета запросов. Но если учитывать приоритеты запросов, то представление коэффициента KИР зависит от выбранного способа выборки. От выборки будет зависеть только числитель, а знаменатель будет одинаковым. Определим его: пусть Yi – максимальная величина приоритета запроса из запросов очереди, обращающихся к таблице Ti, тогда знаменатель примет вид
. (2)
Наиболее перспективными вариантами способа обслуживания запросов являются:
– способ групповой выборки;
– способ групповой выборки с индивидуальным сегментированием.
Способ групповой выборки – это такой способ, при реализации которого из очереди запросов обслуживается несколько запросов одновременно. Выбираются запросы, которые требуют информацию из разных таблиц, и чтобы сумма их приоритетов была максимальной. В случае наличия равнозначных запросов выбирают более «старые».
Пусть 
– множество всех вариантов выборки запросов из очереди, 
– один из вариантов выборки запросов. Причем
, (3)
где 
, N – количество запросов в очереди, xp – булева переменная равная 1, если запрос Зp выбран в этом варианте, и 0, если нет. Сp – приоритет запроса Зp. Тогда числитель из (1) примет вид
. (4)
Получаем KИР следующего вида с учетом (4) и (2):
(5)
Для того чтобы KИР приняло единичное значение, необходимо, чтобы числитель (4) из (5) был бы равен знаменателю (2) из (5). Но это в лучшем случае, а в общем случае числитель должен стремиться к знаменателю. Так как знаменатель для конкретного момента времени это константа, то необходимо сделать такую выборку запросов 
из очереди, чтобы числитель принял максимальное значение, причем это значение никогда не превысит знаменатель.
Это означает, что необходимо выбрать из очереди как можно большее количество запросов, которые обращаются к разным таблицам, и сумма приоритетов выбранных запросов была бы максимальна. Причем стремление к максимуму суммы приоритетов выбранных запросов является главным критерием при выборе запросов из очереди.
Обозначим числитель (5) переменной F, которая стремится к максимальному значению. Получаем функционал:
. (6)
Пусть Аkg – булевая переменная равная 1, если Зk использует таблицу Тg, и 0, если нет. Bg – количество копий таблицы Тg. Тогда исходя из условия, что в любой момент времени любая таблица может быть использована для одного запроса получаем M ограничений вида
. (7)
Следовательно, нам необходимо найти такую выборку 
из множества 
, для которой функционал (6) примет максимальное значение, при выполнении всех ограничений (7). Мы получили задачу линейного программирования с булевыми переменными.
Способ групповой выборки с индивидуальной сегментацией – это такой способ, при реализации которого запросы, находящиеся в очереди, разбиваются на подзапросы. Из очереди полученных подзапросов выбираются подзапросы, требующие информацию из различных таблиц, и чтобы сумма их приоритетов была максимальной. В случае наличия равнозначных подзапросов выбирают более «старые».
Подзапрос – это часть запроса, которая запрашивает информацию из одной конкретной таблицы. Если запрос требует информацию из R таблиц, то он разбивается на R подзапросов.
В этом варианте нам надо выбрать из очереди как можно большее количество подзапросов, которые обращаются к разным таблицам, и сумма приоритетов выбранных подзапросов была бы максимальна. Причем стремление к максимуму суммы приоритетов выбранных подзапросов является главным критерием при выборе подзапросов из очереди.
Пусть Зkg – подзапрос запроса Зk, обращающийся к таблице Тg. Сkg – приоритет запроса Зkg. 
– множество всех вариантов выбора подзапросов из очереди, 
– один из вариантов выбора подзапросов. Причем 
, где 
, 
, p – количество запросов в очереди, M – количество таблиц, xkg – булевая переменная, равная 1, если соответствующий подзапрос Зkg выбран в этом варианте, и 0, если нет, тогда коэффициент (5) примет вид
, (8)
где 
– сумма всех возможных сочетаний произведений переменных содержащих в каждом произведении 
r различных переменных; 
;
– коэффициенты, стоящие в произведениях Sr, содержащих r переменных.
И, соответственно, исходя из (6), получаем функционал
. (9)
Таким образом, мы получаем задачу нелинейного программирования с булевыми переменными, с ограничениями вида (7).
В настоящее время наиболее эффективными методами решения рассматриваемых классов задач являются методы «рангового подхода» и «ветвей и границ». Данные методы обладают наименьшей вычислительной сложностью, при наименьшей погрешности приближенных решений. Основным недостатком в алгоритмах, основанных на методе «ветвей и границ», является их экспоненциальная сложность, а в алгоритмах, основанных на методе «рангового подхода» на данный момент не определено, каким образом реализовать принцип выделения «коридора» в задачах квадратичного программирования. При реализации обоих методов время получения решения фиксированно зависит от размерности решаемой задачи. Поэтому актуальным был вопрос разработки нового метода, лишенного указанных недостатков, причем была бы предусмотрена такая возможность, как задавать требуемое время решения задачи. Необходимо было также сохранить ряд достоинств указанных выше методов.
Предложенный метод основан на комбинированном использовании способа отсечения неперспективных вариантов решения, используя идеи метода «рангового подхода», и способа построения возможных вариантов решений, используя идеи метода «ветвей и границ» [9]. Суть разработанного метода заключается в том, что при формировании множества возможных решений на основе «рангового подхода» отсев неперспективных вариантов, внутри множеств, происходит на основе метода «ветвей и границ». При этом для определения верхней и нижней оценки, при реализации метода «ветвей и границ», были использованы разработанные для алгоритмов метода «рангового подхода» оптимистический (PО) и гарантированный прогнозы (PG) соответственно.
Оптимистический прогноз – это такая величина решения задачи, основанного на векторе (3), для которого определяется прогноз, которая обязательно не будет превышена.
Гарантированный прогноз – это такая величина решения задачи, основанного на векторе (3), для которого определяется прогноз, которая обязательно будет получена.
Для корректировки времени решения предложено использовать величину, названную степенью огрубления (εогр). Данная величина измеряется в процентах и показывает степень приближения верхней оценки к нижней оценке, путем принудительного уменьшения верхней.
При изменении εогр время решения задачи обратно пропорционально погрешности решения.
Для формализации метода были разработаны две процедуры П1 и П2. П1 применяется для построения цепочки векторов и, соответственно, для выбора из нее оптимального решения, а П2 применяется для построения прогнозов и отсечения неперспективных векторов. Необходимо отметить, что для каждого вектора из цепочки полученной с помощью процедуры П1 выполняется процедура П2.
Рассмотрим каждую процедуру подробней:
П1: При построении цепочки векторов есть необходимость хранить в памяти вычислительного средства все вектора из цепочки, которые не были отсечены с помощью процедуры П2. Поэтому необходимо выбрать такой вариант построения векторов, который бы требовал как можно меньше физической памяти для их хранения. Возможны два варианта построения цепочки: «в ширину» и «в глубину». Данные варианты различаются только способом формирования цепочки векторов и не влияют на вычислительную сложность алгоритмов, построенных на основе разработанного метода. Вариант «в ширину» имеет хорошую наглядность при построении, но требует значительные затраты физической памяти, а вариант «в глубину» менее нагляден, но менее требователен к объему физической памяти. К тому же данный вариант позволяет создавать алгоритмы на основе разработанного метода с использованием рекурсивных функций, что также упрощает программный код и увеличивает быстродействие разрабатываемых алгоритмов.
Работа процедуры П1 начинается с так называемого нулевого вектора. Нулевой вектор это такой вектор, который независимо от исходных данных задачи всегда удовлетворяет ограничениям.
П2: Данная процедура используется для построения прогнозов и отсечения неперспективных векторов. Причем корректировка времени решения, за счет которой время решения задачи не будет превышать требуемое время, происходит за счет ужесточения требований, при отсечении неперспективных векторов, используя величину εогр.
Для формализации процедуры введем понятие текущего максимума. Текущий максимум – это максимальная величина решения задачи, из всех решений, получаемых при подстановке в функционал (6) или (9) векторов уже побывавших в цепочке векторов.
На основе формализованного метода был заработан точный алгоритм решения задач линейного и квадратичного программирования. Разработка алгоритма включает в себя реализацию процедур П1 и П2. Для рационального использования памяти построение цепочки векторов производится в «глубину», в этом случае необходимо будет хранить не более N векторов в любой момент времени. Для дальнейшего уменьшения требуемого объема памяти, так как алгоритм является итерационным, реализован рекурсивный вызов функции П1. В теле которой выполняется функция П2. Входными параметрами для обеих процедур является текущий вектор (текущее решение) вида: 
. Причем вторым входным параметром функции П1 является число р. Данное число р сопровождает текущий вектор и говорит о том, что все 
определены и принимают значения 0 либо 1, а 
неопределенны. К тому же в очередном вызове процедуры П1 определяется значение именно х(р+1). Процедура П1 не зависит от степени нелинейности функционала. Решение задачи начинается с так называемого нулевого вектора. Нулевой вектор это – вектор (3), у которого все хi неопределенны. Обозначим 
, если хi неопределен, но при вычислении значений функционала и ограничений считать 
. Поэтому нулевой вектор примет вид
. (10)
Причем р нулевого вектора равен 1.
Обозначим: текущий вектор – 
; значение функционала при подстановке 
– 
; текущий максимум – 
; текущий оптимальный вектор – 
; некоторый вектор – 
.
Главная программа имеет вид:
Шаг 1. 
.
Шаг 2. Вызвать процедуру П1 (
, 1).
Шаг 3. Выдать 
и 
как решение задачи.
Шаг 1 необходим для инициализации переменной 
.
Шаг 2 процедура П1 запускается однократно с входными переменными равными нулевому вектору и его числу р. В дальнейшем данная процедура рекурсивно запускает сама себя.
Шаг 3 после перебора всех векторов на выходе процедуры будем иметь решение задачи.
Процедура П1 имеет вид
Заголовок П1(
)
Шаг 1. Определяем выполнимость всех ограничения при 
.
Шаг 2. Если хотя бы одно ограничение невыполнено, тогда выход из процедуры.
Шаг 3. Если 
, тогда 
, 
.
Шаг 4. Если 
, тогда выход из процедуры.
Шаг 5. Присвоить 
, у 
изменить хр на 0.
Шаг 6. Вызвать процедуру П1 (
, р + 1).
Шаг 7. Присвоить 
, у 
изменить хр на 1.
Шаг 8. Вызвать процедуру П1 (
, р + 1).
Шаг 9. Выход из процедуры.
Шаг 1 необходим для проверки является ли 
одним из решений задачи.
Шаг 3 необходим для обновления текущего оптимального решения.
Шаг 4 необходим для проверки глубины выборки.
Шаги 5, 6 и 7, 8 необходимы для формирования следующего текущего вектора и рекурсивного вызова функции.
Если ограничиться реализацией главного модуля и процедуры П1, то получим точный алгоритм. Но так как при большой размерности решаемой задачи время, за которое алгоритм выдаст точное решение, превысит допустимое время. Поэтому есть необходимость в разработке приближенного алгоритма. Для этого была разработана процедура П2.
Для описания процедуры П2 введем следующие переменные:
PG – гарантированный прогноз вектора 
;
PO – оптимистический прогноз вектора 
.
Процедура П2 интегрируется в процедуру П1 вместо Шага 3.
В этом случае процедура П1 с интегрированной процедурой П2 примет вид
Заголовок П1(
)
Шаг 1. Определяем выполнимость всех ограничения при 
.
Шаг 2. Если хотя бы одно ограничение не выполнено, тогда выход из процедуры.
Шаг 3. Если 
, тогда выход из процедуры.
Шаг 4. Если 
, тогда 
, 
.
Шаг 5. Присвоить PO + PO* εогр.
Шаг 6. Если 
, тогда выход из процедуры.
Шаг 7. Если 
, тогда выход из процедуры.
Шаг 8. Присвоить 
, у 
изменить хр на 0.
Шаг 9. Вызвать процедуру П1 (
, р + 1).
Шаг 10. Присвоить 
, у 
изменить хр на 1.
Шаг 11. Вызвать процедуру П1 (
, р + 1).
Шаг 12. Выход из процедуры.
Шаг 5 необходим для коррекции оптимистического прогноза с учетом εогр. Необходимо отметить, что если εогр = 1, тогда мы получаем точное решение, а при уменьшении εогр к 0 будут получены приближенные решения. Данный алгоритм позволяет, задавая значение εогр, получать решения с заданной погрешностью или за заданное время. Поэтому, корректно варьируя значением εогр возможно получать решение задачи любой размерности за заданное время.
Заключение
Необходимо ответить, что при использовании способа групповой выборки с индивидуальной сегментацией коэффициент КИР больше, чем при использовании способа групповой выборки без индивидуальной сегментации. Но время, необходимое для решения задачи определения оптимальной выборки при выборе различных способов выборки, различно. И помимо выбора способа выборки с максимальным значением коэффициента KИР, необходимо также учитывать то, что время, необходимое для определения оптимальной выборки, не должно превысить допустимое время ТД. А так как для одной и той же очереди запросов время, необходимое для определения оптимальной выборки у способа групповой выборки без индивидуальной сегментации меньше, чем у способа групповой выборки с индивидуальной сегментации, то возможны случаи, когда необходимо для нахождения оптимальной выборки выбирать способ групповой выборки без индивидуальной сегментации.
В различных системах на время обслуживания запросов из очереди накладывается временное ограничение, заключающееся в том, что оно не должно превышать некоторое значение Тд. Поэтому решение задачи обслуживания запросов, обеспечивающее максимальное значение коэффициента KИР , должно осуществляться с требуемой оперативностью, которую можно оценить вероятностью решения данной задачи за время, не превышающее Тд.