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²¹ = 2097152;
rem — операция получения остатка от деления целых чисел.

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

Time totalSeconds

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

r := (R / Q) asFloat

Класс 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:

Автор: C1eriC

Источник