Mathematical model of the system for processing the results of physical experiments with feedback.pdf Введение Проведение экспериментальных исследований связано со сложными и трудоемкими процедурами сбора и обработки данных, с анализом полученной информации и построением моделей процессов и полей различной природы. При обработке данных, полученных в результате физических экспериментов, нередко возникают ситуации, когда анализ полученных данных включает в себя первичную и повторную обработку, причем повторная обработка требует отличных от первичной обработки временных затрат. Так, например, при анализе вещества методом масс-спектрометрии регистрируется поток вещества, истекающий из эффузионного отверстия. Первоначально проводится оценка зависимости интенсивности от массы и поиска так называемых пиков - максимального отклонения интенсивности от нулевого значения при постоянной температуре. Выбирается и фиксируется значение массы. Затем происходит анализ зависимости интенсивности от температуры при выбранном значении массы. На основе этих зависимостей и формируется вывод о качественном и количественном составе вещества [1]. Для такого рода анализа данных физических экспериментов [2, 3] с использованием вычислительной техники требуется исследование потока данных, потребовавших повторной обработки. При этом преследуется цель получения как можно лучших значений таких показателей, как производительность, загруженность ресурсов, малое время простоя, высокая пропускная способность. Системы массового обслуживания (СМО) являются математическими моделями систем обработки данных [4], они позволяют получать вероятностные характеристики функционирования программно-аппаратных комплексов, производящих обработку информации. В качестве заявок входящего потока системы массового обслуживания в таком случае выступают отдельные пакеты данных (задания), предназначенные для обработки. Обслуживающими приборами являются программные модули, занимающие некоторые аппаратные ресурсы (процессор, память). Анализ моделей таких систем в виде СМО позволяет оценить необходимые вычислительные мощности, которые требуется задействовать для получения требуемого результата в отведенное время. В работе [5] рассмотрена модель процесса обработки данных физических экспериментов в виде СМО с неограниченным числом приборов, которая учитывает только занятость вычислителя. В настоящей работе предлагается модель процесса обработки данных, которая учитывает число заданий, поступивших для повторной обработки в вычислительную систему за определенный интервал времени. В качестве такой модели предлагается рассмотреть так называемую неоднородную СМО типа M|M|∞ c повторными обращениями. Требуется выполнить анализ потока повторных обращений в такой системе. Подобные задачи были решены ранее в работах [6-9], где исследование проводилось при условии функционирования системы в стационарном режиме. Однако для анализа реальных систем обработки данных важными являются не только стационарные, но и переходные характеристики функционирования. В настоящей работе в качестве метода исследования предлагается метод марковского суммирования [10], который позволяет выполнить исследование потока повторных обращений в нестационарном режиме работы системы. Кроме того, этот метод дает возможность исследования потока повторных обращений в системах с немарковскими входящими потоками данных, а также произвольным распределением времени обработки. 1. Математическая модель Рассмотрим систему массового обслуживания с неограниченным числом приборов и возможностью повторного обращения (рис. 1). На вход системы поступает простейший поток заявок с интенсивностью λ. Каждая поступающая заявка мгновенно занимает свободный прибор на первой фазе обработки, где обслуживается в течение случайного времени, которое имеет экспоненциальное распределение с параметром μ1. Каждая заявка, завершив обслуживание на первой фазе системы, с вероятностью r1 может перейти на вторую фазу (это обращение будем считать повторным), или с вероятностью (1 - r1) может покинуть систему (завершить свою обработку). Время обслуживания заявки на второй фазе системы является случайной величиной, имеющей экспоненциальное распределение с параметром μ2. Завершив обслуживание на второй фазе системы, каждая заявка с вероятностью r2 может вернуться на вторую фазу системы для следующего повторного обслуживания или с вероятностью (1 - r2) может покинуть систему. Рис. 1. Неоднородная СМО с неограниченным числом приборов и повторными обращениями В работе ставится задача исследования так называемого r-потока - потока повторных обращений в системе с момента начала ее функционирования, то есть нахождения распределения вероятностей числа событий r-потока, наступивших за определенный интервал времени, начиная с t0 = 0. Каждая заявка входящего потока, поступившая в систему в момент времени t, будет формировать события r-потока, которые наступят после момента времени t. Будем полагать, что в момент времени t0 = 0 система свободна и в ней нет обслуживаемых заявок. Зафиксируем некоторый момент времени t = T. Обозначим n(t) - число событий r-потока, то есть число обращений ко второй фазе системы, наступивших на интервале [0, T], сформированных заявками входящего потока, поступившими в систему на интервале [0, t], t ≤ T. Также будем использовать обозначение . (1) Очевидно, что P(n) = P(n, T) есть распределение вероятностей числа событий r-потока, наступивших за время T на интервале [0, T]. 2. Метод марковского суммирования Суммарное число n(t) событий r-потока, сформированных заявками входящего потока, поступившими в систему на интервале [0, t], есть сумма случайного числа независимых случайных величин. Распределение вероятностей каждой суммируемой случайной величины - это распределение вероятностей числа событий, сформированных одной поступившей в систему заявкой. Эти распределения различаются между собой и зависят от моментов поступления в систему заявок входящего потока. Число слагаемых, определяющих значения n(t), равно числу заявок входящего потока, поступивших в систему на интервале [0, t]. Введем в рассмотрение следующие компоненты: • ξ(t) - число событий в r-потоке, сформированных одной заявкой, пришедшей в момент времени t за интервал (T - t); • g(i, t) = {ξ(t) = i} - вероятность того, что заявка, поступившая в систему в момент времени t, к моменту времени T сформирует в r-потоке i событий. Случайный процесс ξ(t) будем называть локальным r-потоком. По формуле полной вероятности можно записать следующее равенство: . При получим дифференциальное уравнение Колмогорова для распределения вероятностей P(n, t) (2) с начальными условиями (3) Переходя к характеристическим функциям вида , , запишем дифференциальное уравнение для характеристической функции исследуемого процесса n(t) (4) с начальными условиями . (5) Для решения задачи (4), (5) найдем вид характеристической функции G(u, t) процесса ξ(t). 3. Исследование локального r-потока Рассмотрим временную ось и момент времени τ ≥ t, где момент t - момент поступления в систему заявки входящего потока. Пусть η(t, τ) - число событий локального r-потока, то есть число повторных обращений, сформированных заявкой, поступившей в систему в момент времени t, за интервал [t, T - t]. Тогда ξ(t) = η(t, T - t). Введем в рассмотрение дополнительную переменную ν(t, τ), описывающую состояние заявки, поступившей в систему в момент времени t, в момент времени t + τ следующим образом: если в момент времени t + τ заявка покинула систему, то ν(t, τ) = 0; если в момент времени τ заявка находится на первой фазе системы, то ν(t, τ) = 1; если в момент времени τ заявка находится на второй фазе системы, то ν(t, τ) = 2. Случайный процесс {η(t, τ), ν(t, τ)} является марковским. Обозначим: • вероятность того, что заявка, поступившая в систему в момент времени t, к моменту времени t + τ покинула систему и сделала i повторных обращений g0(i, t, τ) = {η(t,τ) = i, ν(t, τ) = 0}; • вероятность того, что заявка, поступившая в систему в момент времени t, к моменту времени t + τ находится на первой фазе (в этом случае она не сделала ни одного повторного обращения) g1(i, t, τ) = {η(t, τ) = i, ν(t, τ) = 1}, если i = 0, и g1(i, t, τ) = 0, если i > 0; • вероятность того, что заявка, поступившая в систему в момент времени t, к моменту времени t + τ находится на второй фазе и сделала i повторных обращений g2(i, t, τ) = = {η(t,τ) = i, ν(t, τ) = 2}, i = 1, 2, 3, ... Для распределения вероятностей двумерного марковского процесса {η(t, τ), ν((t, τ)} составим систему дифференциальных уравнений Колмогорова: (6) i = 0; (7) , i = 1, 2, 3, ... (8) Начальные условия для системы (6) - (8) имеют следующий вид: (9) Заметим, что вид выражений для , не будет зависеть от t, поэтому систему (6) - (8) можно переписать так: (10) i = 0; (11) , i = 1, 2, 3, ...; (12) (13) Введем частичные характеристические функции вида , , и, подставив их в систему (10) - (12), получим систему дифференциальных уравнений (14) с начальными условиями (15) Решая систему дифференциальных уравнений (14) с начальными условиями (15), находим (16) (17) (18) Тогда характеристическая функция G(u, t) процесса ξ(t) будет определяться выражением . Подставив сюда выражения (16) - (18) и выполнив элементарные преобразования, получим . (19) 4. Характеристическая функция r-потока Переходим к решению уравнения (4) с начальными условиями (5). Подставим в уравнение (4) выражение (19) для характеристической функции локального r- потока. Получим дифференциальное уравнение для характеристической функции исследуемого процесса n(t) . (20) с начальными условиями (5). Проинтегрировав уравнение (20) и подставив начальные условия (5), получим . (21) Используя выражение для характеристической функции H(u, T) распределения вероятностей , обратным преобразованием Фурье определим это распределение вероятностей: . Используя свойства характеристической функции H(u, T) распределения вероятностей , можно также вычислить основные вероятностные характеристики - математическое ожидание M{n(T)} и дисперсию D{n(T)}: (22) . (23) Заключение В работе проведено исследование вероятностных характеристик потока данных, требующих повторной обработки. Показано, что поток повторных обращений в систему не является простейшим. Математическое ожидание и дисперсия числа повторных обслуживаний при нестационарном режиме работы системы получены методом марковского суммирования. Данный метод позволяет исследовать поток повторных обращений в системах с немарковскими входящими потоками и произвольным временем обработки. Результаты работы могут быть использованы при проектировании вычислительных систем для обработки данных физических экспериментов, а именно - для оптимизации привлекаемых вычислительных ресурсов.

Скачать электронную версию публикации