Разработка имитационной модели работы распределенной вычислительной системы

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

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

       
 

     1.2. Понятие системы массового обслуживания 

     Имитационная  модель предназначена для имитации процесса функционирования реальных систем массового обслуживания. Системы массового обслуживания (СМО) представляют собой системы специального вида, реализующие многократное выполнение однотипных задач. Это прежде  всего процессы  в технических системах  – телефонные  сети,  радиосвязь и телекоммуникации, вычислительные машины, системы и вычислительные сети. При их анализе наиболее важно определить скорость передачи или обработки информации, оценить пропускную способность, загрузку оборудования и т. д.  Особое значение приобрели такие системы при изучении процессов в информатике. Это, прежде всего, компьютерные системы сети передачи информации, ОС, базы и банки данных. Системы обслуживания играют значительную роль в повседневной жизни. Опыт моделирования разных типов дискретных событийных систем свидетельствует о том, что приблизительно 80% этих моделей основаны на CMO.[4, c. 52]

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

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

     Каждая  СМО предназначена для обслуживания (выполнения) некоторого потока заявок (требований), поступающих на вход системы большей частью не регулярно, а случайные моменты времени. Обслуживание заявок, в этом случае, также длится не постоянное, заранее известное время, а случайное время, которое зависит от многиx случайных, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО: в иное время на входе СМО могут скапливаться необслуженные заявки, что приводит к перегрузке СМО, а иногда при свободных каналах на входе СМО заявки не будет, что приводит к недогрузке СМО, т.е. к простаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо «становятся» в очередь, либо по причине невозможности дальнейшего пребывания в очереди покидают СМО необслуженными. [10, c. 34]

     Поступление заявки в СМО называется событием. Последовательность событий, заключающихся  в поступлении заявок в СМО, называется входящим потоком заявок. Последовательность событий, заключающихся в выполнении заявок в СМО, называется выходящим потоком заявок.

     Поток заявок называется простейшим, если он удовлетворяет следующим условиям:

     1) отсутствие последействия, т.е. заявки поступают независимо друг от друга;

     2) стационарность, т.е. вероятность поступления данного числа заявок на любом временном отрезке [t₁; t₂] зависит лишь от величины этого отрезка и не зависит от значения t₁, что позволяет говорить о среднем числе заявок за единицу времени, λ, называемом интенсивностью потока заявок;

     3) ординарность, т.е. в любой момент времени в СМО поступает лишь одна заявка, а поступление одновременно двух и более заявок пренебрежимо мало.

     Каналом обслуживания называется устройство в  СМО, обслуживающее заявку. СМО, содержащее один канал обслуживания, называется одноканальной, а содержащее более одного канала обслуживания – многоканальной.

     Если  заявка, поступающая в СМО, может  получить отказ в обслуживании (в силу занятости всех каналов обслуживания) и в случае отказа вынуждена покинуть СМО, то такая СМО называется СМО с отказами.

     Если  в случае отказа в обслуживании заявки могут вставать в очередь, то такие СМО называются СМО с очередью (или с ожиданием). При этом различают СМО с ограниченной и неограниченной очередью. Очередь может быть ограничена как по количеству мест, так и по времени ожидания. Различают СМО открытого и замкнутого типа. В СМО открытого типа поток заявок не зависит от СМО. В СМО замкнутого типа обслуживается ограниченный круг клиентов, а число заявок может существенно зависеть от состояния СМО .[8, c. 21]

     СМО могут также различаться по дисциплине обслуживания.

     Если  в СМО нет приоритета, то заявки отбираются из очереди в канал  по различным правилам.

• Первым пришел – первым обслужен (FCFS – First Came – First Served)
• Последним пришел – первым обслужен (LCFS – Last Came – First Served)
• Первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE)
• Первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT)
• Первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT)
• Первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT)

     Приоритеты  бывают двух типов – абсолютный и относительный.

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

     СМО описываются некоторыми параметрами, которые характеризуют эффективность  работы системы.

       – число каналов в СМО;

       – интенсивность поступления в СМО заявок;

       – интенсивность обслуживания заявок;

       – коэффициент загрузки СМО;

       – число мест в очереди;

       – вероятность отказа в обслуживании поступившей в СМО заявки;

       – вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО);

     Рассмотрим  конкретный тип СМО. 

     1.3. Имитационное моделирование в распределенных вычислительных системах 

     1.3.1. Понятие распределенных  вычислительных систем 

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

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

     Виды  вычислительных систем

     • однопроцессорные компьютеры

     • параллельные системы

     • системы реального времени

     • распределенные системы

     • кластеры и сети (локальные, глобальные)

     Альтернативный  вариант организации — распределенная система, где общая память вообще отсутствует, а каждый процессор обладает собственной локальной памятью (рис. 1). Часто такие системы объединяют отдельные ВМ. Обмен информацией между составляющими системы обеспечивается с помощью коммуникационной сети посредством обмена сообщениями. [9, c .11]

     

     Рис 1.Структура распределенной вычислительной системы. 

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

     Распределённые вычисления — способ решения трудоёмких вычислительных задач с использованием нескольких компьютеров, объединённых в параллельную вычислительную систему.

     Распределённые  вычисления являются частным случаем  параллельных вычислений, то есть одновременного решения различных частей одной  вычислительной задачи несколькими процессорами (или ядрами одного процессора) одного или нескольких компьютеров. Поэтому необходимо, чтобы решаемая задача была сегментирована, то есть разделена на подзадачи, которые могут вычисляться параллельно. При этом для распределённых вычислений приходится также учитывать возможное различие в вычислительных ресурсах, которые будут доступны для расчёта различных подзадач. Более того, не всякую задачу можно разделить на подзадачи, которые можно решать параллельно.[9, c 14]

     Распределенная система обработки данных (РСОД) - любая система, позволяющая организовать взаимодействие независимых, но связанных между собой ЭВМ. Эти системы предназначены для автоматизации таких объектов, которые характеризуются территориальной распределенностью пунктов возникновения и потребления информации. Концептуально распределенная обработка подразумевает тот или иной вид организации сети связи и децентрализацию трех категорий ресурсов:

     · аппаратных вычислительных средств  и собственно вычислительной мощности;

     · баз данных;

     · управление системой.[9, c. 23]

     В распределенных системах обработки  данных в той или иной степени  осуществляется реализация следующих  основных функций:

               · доступ к ресурсам (вычислительным мощностям, программам, данным и т. п.) с терминалов и из пользовательских программ в режиме «файл-сервер»;

              · выполнение заданий и интерактивное общение пользователей с запущенными по их требованию программами в режиме «клиент-сервер»;

     · сбор статистики о функционировании системы;

              · обеспечение надежности и живучести системы в целом.

     В настоящее время применяют различные  подходы к классификации распределенных систем обработки данных по разным критериям. По степени однородности различают:

     · полностью неоднородные РСОД;

     · частично неоднородные РСОД;

     · однородные РСОД.

     Полностью неоднородные РСОД характеризуются  тем, что в них объединены ЭВМ, построенные на основе различных архитектур и функционирующие под управлением разных операционных систем (ОС).

     Однородные  распределенные системы строятся на однотипных вычислительных средствах, оснащенных одинаковыми операционными системами. По архитектурным особенностям выделяют:

     · РСОД на основе систем телеобработки;

     · РСОД на основе сетевой технологии.

     Под сетевой технологией понимается такая форма взаимодействия ЭВМ, при которой любой из процессов одной из машин по своей инициативе может установить логическую связь с любым процессом в любой другой ЭВМ. В отличие от таких систем РСОД на основе систем телеобработки не обеспечивают полного, симметричного и независимого взаимодействия процессов. По степени распределенности с позиций пользователя РСОД делятся на 2 группы: региональные и локальные. К региональным РСОД будем относить распределенные конфигурации, характеризующиеся следующими основными параметрами: неограниченной географической распределенностью; наличием тех или иных механизмов маршрутизации; каждые два узла связаны собственным каналом, и отсутствует проблема его разделения; широким диапазоном скоростей передачи - 10\.. 10^ бит/с; произвольной топологией. В них можно выделить несколько способов организации взаимодействия между ЭВМ: