exam12 3 - stankin/design-part-1 GitHub Wiki
Основные способы реализации алгоритмов имитационного моделирования для очередей.
Реферат к лекции 12. Понятия исполнительного устройства и очереди в системе массового обслуживания.
Выполнил: Маслова Яна
Проверил: Дмитренко Сергей Сергеевич, ИДБ-18-07
Имитационное моделирование
Имитационное моделирование (симуляция) – это распространенная разновидность аналогового моделирования, реализуемого с помощью набора математических средств, специальных компьютерных программ-симуляторов и особых IT, позволяющих создавать в памяти компьютера процессы-аналоги, с помощью которых можно провести целенаправленное исследование структуры и функций реальной системы в режиме ее «имитации», осуществить оптимизацию некоторых ее параметров.
> Что отражает модель?
Имитационная модель должна отражать логику и закономерности поведения моделируемого объекта во времени (временная динамика) и пространстве (пространственная динамика). Имитационная модель создается:
- для управления сложными бизнес-процессами, чтобы определить их характерные особенности;
- при проведении экспериментов над объектами в экстренных ситуациях, связанных с рисками, в случаях, когда натуральное моделирование нежелательно или невозможно.
Имитационное моделирование возникло для поддержки решения и исследования задач массового обслуживания (задачи об очередях).
> Цель исследования очередей – оптимизация издержек:
- Что выгоднее, принять на работу несколько сотрудников, чтобы уменьшить время ожидания клиентов в очереди, либо сэкономить на заработной плате сотрудников, уменьшив их количество.
Система массового обслуживания
В системе массового обслуживания каждая заявка проходит несколько этапов:
- появление заявки на входе в систему;
- ожидание в очереди;
- процесс обслуживания, после которого заявка покидает систему.
Первый и третий этап характеризуются случайными величинами.
При моделировании очереди нужно учесть:
- Длину очереди;
- Правило обслуживания (например, FIFO, или очередь с приоритетами);
- В более сложных случаях, можно моделировать извлечение заявки из очереди без обслуживания, когда время ожидания превысило определенный уровень.
Конфигурация системы обслуживания:
- Одноканальная или многоканальная система обслуживания;
- Однофазное или многофазная система обслуживания;
- Случайное или детерминированное время обслуживания.
Очереди и алгоритмы их обслуживания — основа QoS
Механизмы очередей используются в любом сетевом устройстве, где применяется коммутация пакетов — маршрутизаторе, коммутаторе локальной или глобальной сети, конечном узле.
Необходимость в очереди возникает в периоды временных перегрузок, когда сетевое устройство не успевает передавать поступающие пакеты на выходной интерфейс. Если причиной перегрузки является процессорный блок сетевого устройства, то необработанные пакеты временно помещаются во входную очередь, т. е. в очередь на входном интерфейсе.
Стратегия FlFO
Принцип алгоритма FIFO состоит в следующем. В случае перегрузки пакеты помещаются в очередь, а если перегрузка устраняется или уменьшается, пакеты передаются на выход в том порядке, в котором поступили («первым пришел — первым ушел», First In — First Out).
Этот алгоритм обработки очередей по умолчанию применяется во всех устройствах с коммутацией пакетов. Он отличается простотой реализации и отсутствием потребности в конфигурировании, однако имеет принципиальный недостаток — дифференцированная обработка пакетов различных потоков невозможна. Очереди FIFO необходимы для нормальной работы сетевых устройств, но они не справляются с поддержкой дифференцированного качества обслуживания.
Такая схема приемлема, если исходящий канал имеет достаточно большую свободную полосу пропускания.
Приоритетное обслуживание очередей
В сетевом устройстве имеется несколько очередей, в соответствии с количеством классов. Поступивший в период перегрузки пакет помещается в очередь согласно его приоритету. На рисунке приведен пример использования трёх приоритетных очередей: с высоким, средним и низким приоритетом. Приоритеты очередей имеют абсолютный характер предпочтения при обработке: пока из более приоритетной очереди не будут выбраны все пакеты, устройство не переходит к обработке следующей, менее приоритетной. Поэтому пакеты со средним приоритетом всегда обрабатываются только тогда, когда очередь пакетов с высоким приоритетом пуста, а пакеты с низким приоритетом — только, когда пусты все вышестоящие очереди.
Конечный размер буферной памяти сетевого устройства предполагает некоторую предельную длину каждой очереди. Пакет, поступивший в то время, когда буфер заполнен, просто отбрасывается.
Приоритетное обслуживание очередей обеспечивает высокое качество сервиса для пакетов из самой приоритетной очереди. Что же касается остальных классов приоритетов, то качество их обслуживания ниже, чем у пакетов с наивысшим приоритетом, причем предсказать уровень снижения затруднительно. Оно может быть довольно существенным, если высокоприоритетные данные передаются с большой интенсивностью.
Взвешенные настраиваемые очереди
Алгоритм взвешенных очередей (Weighted Queuing) разработан для того, чтобы для всех классов трафика можно было предоставить определенный минимум пропускной способности или удовлетворить требования к задержкам. Под весом какого-либо класса понимается доля выделяемой данному виду трафика пропускной способности выходного интерфейса. Алгоритм, в котором вес классов трафика может назначаться администратором, называется «настраиваемой очередью». Трафик делится на несколько классов, и для каждого вводится отдельная очередь пакетов. С каждой очередью связывается доля пропускной способности выходного интерфейса, гарантируемая данному классу трафика при перегрузках этого интерфейса. В примере, приведенном на рисунке, устройство поддерживает пять очередей для пяти классов трафика. Этим очередям соответствует 10, 10, 30, 20 и 30% пропускной способности выходного интерфейса при перегрузках.
Поставленная цель достигается благодаря тому, что очереди обслуживаются последовательно и циклически, и в каждом цикле из каждой очереди забирается такое число байт, которое соответствует весу очереди. Например, если цикл просмотра очередей в рассматриваемом примере равен 1 сек, а скорость выходного интерфейса составляет 100 Мбит/с, то при перегрузках в каждом цикле из первой очереди забирается 10 Мбит данных, из второй тоже 10 Мбит, из третьей — 30 Мбит, из четвертой — 20 Мбит, из пятой — 30 Мбит. В результате каждому классу трафика достается гарантированный минимум пропускной способности, что во многих случаях является более желательным результатом, чем подавление низкоприоритетных классов высокоприоритетным.
Точные значения параметров QoS для алгоритма взвешенного обслуживания предсказать трудно. Они существенным образом зависят от динамически изменяющихся параметров нагрузки сетевого устройства — интенсивности пакетов всех классов и вариаций промежутков времени между прибытием пакетов. В общем случае взвешенное обслуживание приводит к большим задержкам и их отклонениям, чем первоочередное обслуживание для самого приоритетного класса, даже при значительном превышении выделенной пропускной способности над интенсивностью входного потока данного класса. Но для более низких приоритетных классов взвешенное справедливое обслуживание часто оказывается более приемлемым с точки зрения создания благоприятных условий обслуживания всех классов трафика.
❌ Ну так и какие есть способы реализации алгоритмов? Без генераторов случайных чисел можно как-то обойтись?