Главная страница
Навигация по странице:

  • Диаграмма последовательностей и кооперации

  • Архитектурное моделирование

  • Компонент Описание

  • Стереотип Условное обозначение

  • Диаграмма развертывания

  • ЛЕКЦИЯ №4. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

  • Описание систем массового обслуживания

  • Одноканальная модель процесса обслуживания

  • лекции по менеджменту. лекции. Курс лекций по дисциплине Моделирование систем предназначено для студентов, обучающихся по направлениям подготовки бакалавриата 09. 03. 01


    Скачать 1.74 Mb.
    НазваниеКурс лекций по дисциплине Моделирование систем предназначено для студентов, обучающихся по направлениям подготовки бакалавриата 09. 03. 01
    Анкорлекции по менеджменту
    Дата21.12.2020
    Размер1.74 Mb.
    Формат файлаpdf
    Имя файлалекции.pdf
    ТипКурс лекций
    #162568
    страница3 из 8
    1   2   3   4   5   6   7   8
    Моделирование поведения систем
    Поведение системы моделируется на базе трех диаграмм: прецедентов (Use Case Diagram); активности (Activity Diagram); взаимодействия (Sequence Diagram, Collaboration Diagram).
    Прецедент – множество последовательностей действий для по- лучения инициатором действий определенного результата. Инициа- тор действий это актер. Актер – связанное множество ролей, которые реализуются пользователями системы. Элементы диаграммы преце- дентов показаны в табл. 3.3.
    Таблица 3.3
    Элементы диаграммы использования
    Элемент
    Описание
    Прецедент
    Инициатор действия
    Между прецедентами устанавливается связь типа «зависи- мость» с указанием определенных стереотипов. В UML используется два стереотипа: include
    – включение одного прецедента в другой; extend
    – расширение прецедента.
    Стереотип Include означает автоматическое исполнение связан- ного с ним прецедента. Стереотип extend – возможные дополнитель-

    25 ные варианты работы пользователя с системой. Пример диаграммы прецедентов показан на рис. 3.15.
    Диаграммы активности
    Диаграммы активности моделируют динамический аспект пове- дения системы. Диаграмма документирует деятельность системы.
    Деятельность реализует определенную функцию системы, состоит из набора состояний: состояния действия; состояния деятельности.
    Рис. 3.15. Работа пользователя с системой
    Состояния действия считаются атомарными. Они выполняются за малый промежуток времени и не подлежат дальнейшей декомпо- зиции. Элементы диаграммы приводятся в табл. 3.4.
    Тблица 3.4
    Элементы диаграммы активности
    Элемент
    Описание
    Расходящаяся последовательность состояния
    Сходящаяся последовательность состояний
    Состояние деятельности
    Блок принятия решений
    Начало последовательности состояний
    Завершение последовательности состояний

    26
    Пример диаграммы активности показан на рис. 3.16.
    Рис. 3.16. Пересчет рублевой суммы в валюту
    Рис. 3.17. Диаграмма последовательностей:
    destroy
    – сигнал для уничтожения объекта;
    done
    – сигнал, означающий, что объект выполнил требуемые от него функции

    27
    Диаграмма последовательностей и кооперации
    Диаграмма последовательностей отображает процесс движения и возникновения сообщений в системе во времени. Условно по оси Х показываются объекты в порядке их появления в системе. По оси Y отображается пунктирная линия «жизни» объекта до момента его уничтожения. Период жизни на линии жизни показывается прямо- угольником.
    Диаграмма кооперации отражает структурную организацию объ- ектов порождающих и принимающих сообщения. Под сообщением по- нимается некоторая совокупность правил обмена данными между объ- ектами. Сообщение предполагает, что объект, получив некоторую ин- формацию, ответит на нее некоторой последовательностью действий.
    При указании ассоциативных связей они могут снабжаться сте- реотипами local (локальная связь) и global (глобальная связь).
    Рис. 3.18. Диаграмма кооперации
    Локальная связь позволяет обмениваться сообщениями объек- там, которые образуют пару источник – приемник. Глобальная связь определяет возможность передачи сообщения к любому объекту кооперации.
    Сообщения, возникающие в кооперации, должны быть пронуме- рованы. Нумерация выполняется в возрастающем порядке. Сообще- ние с большим номером появляется позже во времени, чем сообще- ние с меньшим номером.
    Архитектурное моделирование
    Архитектурное моделирование предполагает использование двух видов диаграмм: диаграмма компонентов (Component Diagram); диаграмма развертывания (Deployment Diagram).
    Данные диаграммы позволяют наглядно показать развертыва- ние программного кода модели системы на ЭВМ. Строятся такие диа- граммы с использованием трех элементов компонентов;

    28 узлов; интерфейсов.
    Условные обозначения приводятся в табл. 3.5.
    Таблица 3.5
    Элементы диаграммы компонентов
    Элемент
    Описание
    Компонент
    Узел вычислительной системы
    Интерфейс
    Диаграмма компонентов
    Компонент представляет собой физическую часть системы. В компьютерных информационных системах компонент это набор битов, который обрабатывается процессором. Компонент может представ- лять собой исполняемый программный код, либо электронный вари- ант документа. Описание компонентов приводятся в табл. 3.6.
    Таблица 3.6
    Описание компонентов
    Компонент
    Описание
    Компонент развертывания
    Представляет собой подключаемую динамическую библиотеку, либо исполняемую программу
    Рабочий продукт
    Файл с текстом программного кода, файл с исходными данными
    Компонент исполнения
    Результат работы системы.
    Например: новый объект, документ с результатами работы программы
    При показе компонентов могут быть использованы стереотипы
    UML: executable
    – исполняемый программный код; library
    – библиотека объектов; table
    – таблица базы данных; file
    – документ с текстом программы, данными; document
    – любой документ, полученный в результате работы программы.

    29
    Условные обозначения стереотипов приводятся в табл. 3.7.
    Таблица 3.7
    Пиктограммы стереотипов
    Стереотип
    Условное обозначение
    executable library table file document
    Компоненты обычно реализуют некоторый интерфейс. Интер- фейс это набор операций, которые описывают услуги, предоставляе- мые данным компонентом. На концептуальном уровне интерфейс реализуется определенным классом. После компилирования про- граммы реализация интерфейса выполняется программным кодом – компонентом. Пример диаграммы компонентов показан на рис. 3.19.
    Рис. 3.19. Диаграмма компонентов
    Компонент, предоставляющий интерфейс, связан с ним связью типа export, компонент использующий интерфейс связан с ним зависи- мостью типа import. Выделим следующие особенности компонентов: компонент представляет собой код; компонент может быть заменен другим, если он совместим с интерфейсом;

    30 компонент может экспортировать несколько интерфейсов; компонент это часть системы, взаимодействующая с осталь- ными через набор интерфейсов.
    Диаграмма развертывания
    Диаграммы этого типа служат для моделирования развертыва- ния программного обеспечения модели или моделируемой системы с учетом использования вычислительных ресурсов. Под вычислитель- ными ресурсами понимается процессор вычислительной системы.
    Процессоры могут быть разделены с помощью общей среды переда- чи данных и представляют собой узлы обработки данных.
    Рис. 3.20. Диаграмма развертывания
    На диаграмме узел – это аппаратный элемент системы, обла- дающей памятью, и процессором для обработки данных. Узел должен обладать уникальным идентификатором – именем, который реализует выполнение компоненты. На диаграммах компонента связана с узлом с помощью отношения зависимости (рис. 3.19).
    Контрольные вопросы
    1.
    Как показывают класс и его элементы?
    2.
    Перечислите и охарактеризуйте виды ассоциации?
    3.
    Что такое обобщение и зависимость между классами?
    4.
    Какие виды объектов можно выделить при моделировании предметной области модели?

    31 5.
    Для чего используются статические элементы классов?
    6.
    Для чего используются пакеты?
    7.
    Перечислите правила построения диаграмм прецедентов.
    8.
    Перечислите правила построения диаграмм активности.
    9.
    Перечислите правила построения диаграмм взаимодействия.
    10.
    Перечислите правила построения диаграмм развертывания и компонентов системы.
    ЛЕКЦИЯ №4. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
    Системы массового обслуживания (СМО) и Q схемы, Марковские цепи и
    процессы, определение параметров СМО.
    В данной лекции использованы положения теории массового об- служивания, в разработку которой большой вклад внесли такие уче- ные и исследователи как Колмогоров А.Н., Марков А.А., Гнеденко Б.И.,
    Советов Б.Я., Осипов Л.А. [1, 5, 11].
    Системы массового обслуживания относят к непрерывно-сто- хастическим системам (Q-схемам). Для таких систем характерно слу- чайное появление требований (заявок) на обслуживание. Завершение обслуживания происходит в случайные моменты времени. Основу системы массового обслуживания составляет канал обслуживания, показанный на рис. 4.1, где приняты условные обозначения:
    Н
    i
    – накопитель;
    u
    i
    – поток обслуживание;
    w
    i
    – поток заявок;
    K
    i
    – канал обслуживания заявки.
    Рис. 4.1. Канал обслуживания
    При моделировании реальных систем используют композиции из отдельных элементарных систем, которые называют Q-схемами. Если каналы отдельных приборов соединены параллельно, то имеет место многоканальное обслуживание. Если приборы и их параллельные композиции соединены последовательно, то имеет место многофаз- ное обслуживание. Различают разомкнутые и замкнутые Q-схемы.

    32
    В разомкнутых Q-схемах обратные связи отсутствуют. В замкну- тых Q-схемах есть обратные Q-связи, по которым заявки двигаются в направлении, обратном направлению «вход–выход».
    Правило обслуживания жестко определяет, в какой последова- тельности будут обслужены заявки системы. К ним относятся:
    FIFO (FCFS) First In, First Out (First Come, First Served).
    Обслу- живание выполняется в порядке поступления заявок;
    LIFO (LCFS) Last In, First Out (Last Come, First Served).
    Обслу- живание выполняется в обратном порядке прибытия заявок;
    SIRO Selection in Random Order.
    Очередная заявка для обслу- живания выбирается случайным образом;
    Non-preemptive priority
    . Относительный приоритет, некоторым заявкам отдается предпочтение по отношению к другим клиентам. Те- кущий процесс обслуживания не прерывается;
    Preemptive priority
    . Абсолютный приоритет. Если вновь прибы- вающая заявка обладает высшим приоритетом по сравнению с други- ми клиентами в системе, текущий процесс обслуживания прерывается и продолжается с новыми условиями. Прежние условия-требования отклоняются;
    RR (Round Robin).
    Каждая заявка может занять обслуживаю- щий процесс на определенный временной интервал. Клиенты, чье об- служивание требует больше времени, должны несколько раз ставить- ся в очередь на обслуживание.
    Поток событий – заявок
    Плотность вероятности потока событий, при среднем значении
    а, выражается формулой
    1
    ( )
    при
    0; ( ) 0 при
    0,
    x
    a
    f x
    e
    x
    f x
    x
    a
    (4.1) где a – коэффициент плотности потока событий.
    При моделировании СМО важную роль играет понятие простей- шего потока событий. К такому потоку событий предъявляются сле- дующие три требования: экспоненциальный закон распределения времени обслужива- ния и интервалов поступления заявок; стационарность (характеристики процесса не должен иметь существенных изменений во времени); ординарность (в один момент времени не должно быть более одного события); без последействия (будущий процесс зависит только от со- стояния системы в данный момент и не зависит от пути прихода в это состояние).
    По последнему требованию процесс определяют как Марковский
    (более точно его можно назвать процессом без предыстории). Поток

    33 событий, удовлетворяющий перечисленным выше условиям, называ- ется простейшим или Пуассоновским.
    Описание систем массового обслуживания
    Компактное описание СМО выполняют, используя нотацию Кен- дала: A/B/m/n.
    Указывается распределение времени поступления заявок в сис- тему; распределение времени, затрачиваемое на обслуживание заяв- ки в процессоре СМО. Кроме этого указывается число процессоров системы, число мест в очереди ожидания. При этом используют сле- дующие условные обозначения:
    A: закон распределения временных интервалов поступления заявок в систему;
    B: закон распределения временных интервалов в процессоре обслуживания;
    m: число процессоров в системе;
    n: число мест ожидания в очереди;
    M: экспоненциальное распределение;
    E
    k
    : распределение Эрланга с параметром k (k = 1, 2, …);
    D: детерминированное распределение, постоянные времен- ные интервалы;
    G: произвольное – неизвестное распределение.
    Рассмотрим пример условного обозначения канала обслужива- ния: M/D/3/5. Данный канал состоит из трех процессоров. В очереди может размещаться пять заявок. Временные интервалы поступления заявок распределены экспоненциально. Временные интервалы об- служивания постоянные.
    Построение формальной модели обслуживания может быть вы- полнено с помощью Марковских цепей и процессов.
    Марковская цепь
    Цепь Маркова описывает развитие системы во времени. При этом рассматривают состояния системы. Рассматривается текущее состояние системы для перехода в следующее состояние и при этом не учитываются предыдущие состояния системы.
    Марковская цепь это последовательность случайных перемен- ных в вероятностном пространстве:
    ( , ) :
    :
    n
    P
    X
    S
    (4.2)
    Множество S называется пространством состояния Марковской цепи. Это пространство может быть конечным набором состояний или бесконечным.
    {1, 2, ...,
    }
    S
    m или
    {1, 2, 3, ...}.
    S
    При этом справедливы следующие соотношения:
    1 1
    2 2
    0 0
    (
    |
    ,
    ,...,
    ).
    n
    n
    n
    n
    n
    n
    P X
    x
    X
    x
    X
    x
    X
    x
    (4.3)

    34
    Условная вероятность события будет иметь вид:
    1 1
    (
    |
    ).
    n
    n
    n
    n
    P X
    x
    X
    x
    (4.4)
    Это вероятность перехода из одного состояния в другое, она не зависит от вероятностей предыдущих событий. Вероятность перехода из состояния X
    n
    –1
    при временном интервале n–1 в состояние X
    n
    при временном интервале n не зависит от предыдущих состояний.
    Марковские цепи, в которых вероятность перехода из одного со- стояния в другое остается постоянной, называют гомогенными. В этом случае рассматривают только вероятность перехода из состояния X в состояние Y и не рассматривают временные интервалы.
    1
    (
    |
    ).
    xy
    n
    n
    p
    P X
    y X
    x
    (4.5)
    Вероятность смены состояния определяет матрица переходов.
    Матрицу переходов можно определить только для конечного про- странства состояния S Марковской цепи
    {1, 2, ...,
    }.
    S
    m
    В конечном пространстве состояний могут быть выделены m
    2
    вероятностей перехода p
    ij
    11 12 1
    21 22 2
    1 2
    (
    )
    при 1
    ,
    m
    m
    ij
    m
    m
    mm
    p
    p
    p
    p
    p
    p
    p
    i j
    m
    p
    p
    p
    (4.6)
    Если рассматриваемая система находится в состоянии i, то она переходит в произвольное состояние j. Сумма вероятностей строки переходной матрицы равна единице.
    1 1 для всех
    m
    ij
    j
    p
    i
    S
    (4.7)
    Если это справедливо для каждой строки матрицы, то матрицу называют стохастической.
    Рассмотрим систему с тремя состояниями. Смена состояний по- казана на рис. 4.2 в виде направленного графа. Этой системе соот- ветствует матрица переходов:
    0 1 0 0 0 1 .
    1 0 0
    Система переходит с вероятностью равной одному (гарантиро- ванный переход) из состояния 1 в состояние 2, потом из состояния 2 в состояние 3 и наконец, из состояния 3 назад в состояние 1. Переход из одного состояния в другое происходит циклически, каждый переход гарантированно исполняется.

    35
    Рассмотрим систему, состоящую из двух подсистем, граф со- стояния которой показан на рис. 4.3. Этому графу соответствует мат- рица переходов:
    1/ 2 0 1/ 2 0
    1 0 .
    2 / 3 0 1/ 3
    Рис. 4.2. Циклическая система
    В зависимости от выбора начального состояния, система остает- ся постоянно в состоянии 2 или циклически переходит из состояния 1 в состояние 3.
    Рис. 4.3. Система с двумя независимыми подсистемами
    На рисунке 4.4. приводится другой вариант системы. В системе есть переход из состояния 3 в состояние 2 с заданной вероятностью.
    Если система попала один раз в это состояние, она его больше не может покинуть. Такое состояние называются поглощающим.
    Переходная матрица такой системы имеет вид:
    1/ 2 0
    1/ 2 0
    1 0 .
    1/ 3 1/ 3 1/ 3

    36
    Марковский процесс
    В Марковских процессах учитываются временные интервалы, которые могут постоянными и/или переменными, в отличие от дис- кретных интервалов в Марковских цепях.
    Для каждого состояния вводится период пребывания системы в этом состоянии. Так же как и в Марковских цепях, система через оп- ределенный период времени переходит в новое состояние. Для СМО считают, что временные интервалы нахождения системы в опреде- ленном состоянии подчиняются экспоненциальному закону распре- деления.
    Рис. 4.4. Система с поглощающим состоянием 2
    Одноканальная модель процесса обслуживания
    В одноканальной СМО имеется один процессор обслуживания и одна очередь требований – заявок. Оценить эффективность работы такой СМО можно с помощью следующих параметров:
    M[L
    q
    ]
    – математическое ожидание числа заявок, ожидающих обслуживания в очереди;
    M[T
    q
    ]
    – математическое ожидание времени, которое заявка проводит в очереди, ожидая обслуживания;
    M[L]
    – математическое ожидание числа заявок в СМО ожи- дающих обслуживания;
    M[T]
    – математическое ожидание времени которое заявка проводит в СМО в ожидании обслуживания.
    Эти параметры могут быть определены для СМО типа: M/M/1/ .
    Предполагается, что очередь бесконечная. Все заявки – требо- вания подлежат обслуживанию.
    Для такой СМО Марковский процесс примет вид, показанный на рис. 4.5 где – интенсивность поступления заявок – требований в очередь, – интенсивность обслуживания заявок. Значения этих ве- личин принимаются постоянными.

    37
    Рис. 4.5. Одноканальная СМО с бесконечной очередью
    Работа СМО представляется последовательностью смены со- стояний с вероятностями p
    n
    , n = 0, 1, 2
    … для входа и выхода в со- стояние. В состоянии P
    0
    вход будет определен как P
    1
    , а выход P
    0
    (рис. 4.6).
    Рис. 4.6. Начальная фаза обслуживания
    В итоге получим уравнение:
    1 0
    p
    p
    (4.8)
    Для остальных состояний получим уравнения:
    0 2
    1 1
    1
    , для ;
    p
    p
    p
    p
    p
    (4.9)
    1 3
    2 2
    2
    , для .
    p
    p
    p
    p
    p
    (4.10)
    После преобразования получим:
    0 1
    0;
    p
    p
    0 1
    2
    (
    )
    0;
    p
    p
    p
    1 2
    3
    (
    )
    0;
    p
    p
    p

    1 1
    (
    )
    0;
    i
    i
    i
    p
    p
    p
    (4.11)
    0 1
    2 0
    0 0
    (
    )
    0 0
    0
    (
    )
    0 0
    0 0
    и т.д.
    p
    p
    p
    (4.12)

    38
    Вероятность перехода из одного состояния в другое вычисляет- ся согласно формуле:
    (1
    )
    ,
    n
    n
    p
    (4.13) где n – номер текущего состояния. Согласно формуле значение веро- ятности p
    0
    – отсутствие требований в системе будет равно:
    0
    (1
    ).
    p
    (4.14)
    В формулах 4.13 и 4.14 = / .
    Если в системе находится 0 или 1 заявка (n = 0, n = 1), заявка не будет ожидать обслуживания и сразу будет обработана, длина очере- ди будет равна 0. Если в СМО поступило две заявки, одна заявка бу- дет обслуживаться, а другая в очереди будет ожидать обслуживания.
    Длина очереди будет равной 1 заявке. При поступлении трех заявок, одна заявка обслуживается, а две заявки будут ожидать обслужива- ния и т.д. Следовательно, можно сделать вывод, что при n 1 всегда одна заявка будет обслужена, а n – 1 заявок будут ожидать обслужи- вания. Тогда число заявок в очереди будет равно
    2
    [
    ]
    (
    1).
    q
    n
    n
    M L
    p
    n
    (4.15)
    С другой стороны это значение может быть определено:
    2 2
    [
    ]
    (1
    )
    (1
    )
    (1
    )
    q
    M L
    (4.16)
    Остальные параметры могут быть рассчитаны по формулам. q
    [ ]
    [ ]
    ;
    M L
    M L
    (4.17)
    2
    [ ]
    ;
    1
    [ ]
    ;
    1
    M L
    M L
    (4.18) q
    [ ]
    ;
    (
    )
    M T
    (4.19) q
    1
    [ ]
    [ ]
    ;
    M T
    M T
    (4.20)
    1
    [ ]
    M T
    (4.21)
    В рассмотренной СМО имеют место соотношения: q
    q
    [ ]
    [ ];
    M L
    M T
    (4.22)
    [ ]
    [ ].
    M L
    M T
    (4.23)
    Эти зависимости отвечают закону Литтла.
    1   2   3   4   5   6   7   8


    написать администратору сайта