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

Аналитическое моделирования
системы массового обслуживания
на языках программирования высокого уровня общего назначения – Objective-C и Kotlin

Задача аналитического моделирования систем массового обслуживания является достаточно важной и имеет большую практическую значимость. Поэтому в настоящей работе рассматривается разработка программ аналитического моделирования системы массового обслуживания на языках программирования высокого уровня общего назначения – Objective-C и Kotlin. Приводятся полные исходные тексты программ и результаты работы. Программы станут полезны системным администраторам и всем, изучающим современные языки программирования

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

Известной СМО является СМО типа M/M/K/N. В этой СМО имеется входной поток заявок с интенсивностью λ, буфер заявок емкости N, K каналов обработки заявок с производительностью μ. Ранее в журнале «Системный администратор» было рассмотрено аналитическое моделирование СМО типа M/M/K/N на языках 1С [6], школьном алгоритмическом языке [7], PowerShell [8], Python [9], PHP [10], Ada и Common Lisp [11], Fortran 95 и Rust [12], JavaScript и Prolog [13], Swift и Go [14], Haskell и C# [15], F# и C++ [16], OCaml и Perl [17], D и R [18], Tcl и Lua [19], Vala и Dart [20], Ruby и Pascal [21], Java и AWK [22], Scala и Octave [23].

Ключевые слова: аналитическое моделирование, система массового обслуживания, Objective-C, Kotlin

Полную версию статьи читайте в журнале
Подпишитесь на журнал
Купите в Интернет-магазине

Источник

Squeak: Моделирование систем массового обслуживания

На Хабре крайне мало информации о таком языке программирования как Squeak. Я попытаюсь рассказать о нем в контексте моделирования систем массового обслуживания. Покажу как написать простой класс, расскажу его структуру и использую его в программе, которая будет обслуживать заявки посредством нескольких каналов.

Пару слов о Squeak

Squeak это открытая, кросс-платформенная реализация языка программирования Smalltalk-80 c динамической типизацией и сборщиком мусора. Интерфейс довольно специфический, но вполне удобный для отладки и анализа. Squeak полностью отвечает концепции ООП. Все состоит из объектов, даже конструкции if-then-else, for, while реализованы с их помощью. Весь синтаксис сводится к посылке объекту сообщения в виде:

Любой метод всегда возвращает объект и ему можно направить новое сообщение.
Squeak часто используется для моделирования процессов, но может использоваться и как средство для создания мультимедийных приложений и разнообразных образовательных платформ.

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

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

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

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

Немного математики

Для пуассоновского потока число событий X, попадающих в интервал длины τ (тау), примыкающий к точке t, распределено по закону Пуассона:

где a_{(t, τ)} — среднее число событий, наступающих на интервале времени τ.
Среднее число событий, наступающих в единицу времени, равно λ(t). Следовательно, среднее число событий на интервале времени τ, примыкающему к моменту времени t, будет равно:

Время T между двумя событиями при λ(t) = const = λ распределено по закону:

Плотность распределения случайной величины T имеет вид:

Для получения псевдослучайных пуассоновских последовательностей интервалов времени t_i решают уравнение:

где r_i — равномерно распределенное на интервале [0, 1] случайное число.
В нашем случае это дает выражение:

По генерации случайных чисел можно писать целые тома. Здесь же, для генерации равномерно распределенных на интервале [0, 1] целых чисел используем следующий алгоритм:

где R_i — очередное случайное целое число;
Р — некоторое большое простое число (например 2311);
Q — целое число — верхняя граница интервала, например, 2 21 = 2097152;
rem — операция получения остатка от деления целых чисел.

Начальное значение R₀ обычно задают произвольно, например, используя показания таймера:

Класс Rand

Для получения равномерно распределенных на интервале [0, 1] случайных чисел создаем класс — генератор вещественных чисел:

Float variableWordSubclass: #Rand "имя класса" instanceVariableNames: '' "переменные экземпляра" classVariableNames: 'R' "переменные класса" poolDictionaries: '' "общие словари" category: 'Sample' "имя категории"

"Инициализация" init R := Time totalSeconds.next "Следующее псевдослучайное число" next R := (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat

Для установки начального состояния датчика посылаем сообщение Rand init.
Для получения очередного случайного числа посылаем Rand next.

Программа обработки заявок

Итак, в качестве простенького примера сделаем следующее. Пусть нам необходимо промоделировать обслуживание регулярного потока заявок от одного источника со случайным интервалом времени между заявками. Имеется два канала различной производительности, позволяющих обслуживать заявки за 2 и 7 единиц времени соответственно. Необходимо зарегистрировать число заявок, обслуженных каждым каналом на интервале 100 единиц времени.

 "Объявление временных переменных" | proc1 proc2 t1 t2 s1 s2 sysPriority queue continue r | "Начальные установки переменных" Rand init. SysTime := 0. s1 := 0. s2 := 0. t1 := -1. t2 := -1. continue := true. sysPriority := Processor activeProcess priority. "Текущий приоритет" queue := Semaphore new. "Модель очереди заявок" "Создание процесса - модели канала 1" (Process forContext: [ proc1 := Processor activeProcess. [continue] whileTrue: "Цикл обслуживания" [ queue wait. "Ждать заявку" t1 := SysTime + 2. "Следующее время активизации" s1 := s1 + 1. proc1 suspend. "Приостановить процесс в ожидании окончания обслуживания" ]. proc1 := nil. "Удалить ссылку на процесс 1" ] priority: (sysPriority + 1)) resume. "Новый приоритет больше фонового" "Создание процесса - модели канала 2" (Process forContext: [ proc2 := Processor activeProcess.. [continue] whileTrue: [ queue wait. t2 := SysTime + 7. s2 := s2 + 1. proc2 suspend. ]. proc2 := nil. ] priority: (sysPriority + 1)) resume. "Продолжение описания главного процесса и модели источника" [SysTime < 100] whileTrue: [ r := (Rand next * 10) rounded. (r = 0) ifTrue: [r := 1]. ((SysTime rem: r) = 0) ifTrue: [queue signal]. "Послать заявку" "Коммутатор процессов обслуживания" (t1 = SysTime) ifTrue: [proc1 resume]. (t2 = SysTime) ifTrue: [proc2 resume]. SysTime := SysTime + 1. "Тикает модельное время" ]. "Показать состояние счетчика заявок" PopUpMenu inform: 'proc1: ',(s1 printString),', proc2: ',(s2 printString). continue := false. 

При запуске видим, что процесс 1 успел обработать 31 заявку, а процесс 2 только 11:

Источник