Разработка модели теории массового обслуживания
Министерство информационных технологий и связи РФ
Сибирский государственный университет телекоммуникаций и информатики
Факультет информатики и вычислительной техники
Кафедра вычислительных систем
Курсовая работа
по курсу Моделирование
Выполнили: Степанов Е.Е.
Гордеев С.А.
Гомзяков А.В.
студенты гр.ВМ-37
Проверил: Рудых Я.И.
Новосибирск 2005
Содержание
Постановка задачи
Описание модели в терминах PDEVS формализма
Атомарные компоненты
Полученные результаты
Основные фрагменты кода
Вывод
Постановка задачиМодель состоит из трех обслуживающих серверов. Каждый сервер имеет очередь, в которой заявки могут ожидать своей очереди. Также есть генератор сообщений. Первая очередь бесконечная, остальные конечные. Обработки заявок всех серверов распределены экспоненциально. В начальный момент времени очереди. Необходимо построить модель в терминах PDEVS-формализма и произвести эксперименты над моделью с помощью пакета DEJaView.
Необходимо ответить на следующие вопросы:
Выдать статистику по всем очередям.
Максимальную длину первой очереди.
Сколько процентов сообщений прошло через очередь без задержек - «сквозняки».
Рис. 1. Схематическое изображение модели
Описание модели в терминах PDEVS формализма
В PDEVS-модели существует 7 компонент:
Queue1, Queue2 и Queue3 – это три очереди.
Server1, Server2 и Server3 – это три прибора (сервера). Время обслуживания распределено экспоненциально.
MessageGenerator - генератор сообщений.
Рассмотрим более подробно логику работы компонент.
1. Генератор подает сообщение в очередь Queue1.
2. В начальный момент времени все серверы находятся в состоянии free (свободен). Cерверы Server1, Server2 посылают сообщение на очереди Queue2 и Queue3 соответственно, это говорит о готовности серверов принимать сообщения.
Приняв сообщение каждая очередь подаёт сообщение на выход toNext и он приходит на вход fromPrev соответствующего каждой очереди сервера.
Сервет меняет своё состояние с free (свободен) на busy (занят) и через некоторое время подаёт сообщение на выход toNext и после этого ждёт от следующей очереди подтверждения что в данной очереди ещё есть хотя бы одно место.
После того как сервер отправил сообщение слёдующей очереди, он переходит в состояние free (свободен) и посылает предыдущей очереди сообщение, которое говорит о готовности сервера принимать следующее сообщение.
Также существует возможность перехода сообщения с Серверов в очередь Queue1 с вероятностями P1, P2, P3.
3.Атомарные компоненты
| Класс атомарной компоненты | Объекты класса атомарной компоненты | Возможные состояния компоненты | Входные порты | Выходные порты |
| Server1 | Server1 | Free, Busy | FromPrev,FromNext | ToPrev,toNext,Vozvrat |
| Server2 | Server2 | Free, Busy | FromPrev,FromNext | ToPrev,toNext,Vozvrat |
| Server3 | Server3 | Free, Busy | FromPrev,FromNext | ToPrev,Vozvrat |
| Queue1 | Queue1 | Free, Full | FromPrev,FromNext,Vozvrat | ToPrev,toNext |
| Queue2 | Queue2 | N=={1,2,3,4,5} | FromPrev,FromNext | ToPrev,toNext |
| Queue3 | Queue3 | N=={1,2,3,4,5} | FromPrev,FromNext | ToPrev,toNext |
Алгоритмы функционирования компонент:
Компоненты классов Server1 и Server2:
Delta_int:
Остаемся в текущем состоянии
Delta_exp
Если (пришел новый пакет от очереди)
{
переходим в состояние “busy”
}
Lambda
Если(Сообщение от предыдущей очереди){
Если пакет обработан, то пытаемся отправить его следующей очереди.
Случайно определяем куда пойдёт сообщение – или в начало цепи, или в следующую очередь.
Отсылаем предыдущей очереди уведомление о том что сервер освободился.
}
Компоненты класса Queue2,Queue3:
Delta_int:
остаемся в текущем состоянии
Delta_exp
Если (пришёл новый пакет)
{
Если (Флаг ожидания, ожидания освобождения сервера)
{
Увеличиваем счётчик поступивших пакетов на 1
Так же выполняем действия необходимые для вычисления средней длины очереди
}
Иначе
Если (Очередь не ждёт освобождения сервера )
{
«Сквозняк»
Выполняем действия по вычислению доли сквозняков
}
Иначе
Если (пришло сообщение от сервера)
{
Флаг готовности сервера ставим в значение истина
}
Lambda
Если (пришёл новый пакет)
{
Если (Сервер свободен)
{
Отсылаем сообщение серверу
«Сквозняк»
Выполняем операции по вычислению доли сквозняков
}
Если (Ожидаем сервер)
{
Если очередь переполнилась посылаем сообщение серверу
}
}
Если (пришло сообщение от сервера)
{
Если(Очередь не пуста){
Посылаем пакет на порт toNext очереди
Уменьшаем длину очереди на 1
}
}
Компоненты классов Server3:
Delta_int:
Остаемся в текущем состоянии
Delta_exp
Если (пришел новый пакет от очереди)
{
переходим в состояние “busy”
}
Lambda
Если (сообщение от предыдущей очереди){
Если пакет обработан, то пытаемся отправить его следующей очереди.
Случайно определяем куда пойдёт сообщение – или в начало цепи, или на выход из цепи.
Отсылаем уведомление предыдущей очереди о том, что сервер освободился.
}
Компонент класса Queue1:
Delta_int:
остаемся в текущем состоянии
Delta_exp
Если (пришёл новый пакет(или из цепи, или из генератора сообщений))
{
Если (Флаг ожидания, ожидания освобождения сервера)
{
Увеличиваем счётчик поступивших пакетов на 1
Выполняем действия по нахождению макс максимальной длины очереди
}
Иначе
Если (Сервер свободен )
{
«Сквозняк»
Выполняем действия по вычислению доли сквозняков
}
Иначе
Если (пришло сообщение от сервера)
{
Флаг готовности сервера ставим в значение истина
}
Lambda
Если( пришёл новый пакет(из генератора или из цепи) )
{
Если (Сервер свободен)
{
Отсылаем сообщение серверу
«Сквозняк»
Выполняем операции по вычислению доли сквозняков
}
Если (Ожидаем сервер)
{
}
}
Если (пришло сообщение от сервера)
{
Если(Очередь не пуста){
Посылаем пакет на порт toNext очереди
Уменьшаем длину очереди на 1
Выполняем действия по вычислению максимальной длины очереди
}
}
Компонент класса: MessageGenerator.
Если(пришло системное сообщение)
{
Отправляем сообщение первой очереди
Увеличиваем число сгенерированных сообщений на 1
}
4. Полученные результаты
Рис. 3. Результаты работы модели
Основные фрагменты кода
1.QueueModel.java
package DEJaView.modelLibs.a;
import DEJaView.modelLibs.a.MessageGenerator;
import DEJaView.modelLibs.a.Queue1;
import DEJaView.modelLibs.a.Server1;
import DEJaView.modelLibs.a.Queue2;
import DEJaView.modelLibs.a.Server2;
import DEJaView.modelLibs.a.Queue3;
import DEJaView.modelLibs.a.Server3;
import DEJaView.core.*;
import java.util.*;
public class QueueModel extends MULC {
public static void main(String args[]) {
MULC queuemodel = new MULC("queuemodel");
MessageGenerator MessageGenerator1 = new MessageGenerator("MessageGenerator1");
Queue1 Queue1 = new Queue1("Queue1");
Queue2 Queue2= new Queue2("Queue2");
Queue3 Queue3= new Queue3("Queue3");
Server1 Server1 = new Server1("Server1");
Server2 Server2=new Server2("Server2");
Server3 Server3=new Server3("Server3");
queuemodel.AddComponent(MessageGenerator1);
queuemodel.AddComponent(Queue1);
queuemodel.AddComponent(Queue2);
queuemodel.AddComponent(Queue3);
queuemodel.AddComponent(Server1);
queuemodel.AddComponent(Server2);
queuemodel.AddComponent(Server3);
MessageGenerator1.addOutPort("toQueue","toQueue");
Queue1.addInPort("fromMessageGenerator","fromMessageGenerator");
Queue1.addInPort("fromNext","fromNext");
Queue1.addInPort("Vozvrat","Vozvrat");
Queue1.addOutPort("toNext","toNext");
Queue2.addInPort("fromPrev","fromPrev");
Queue2.addInPort("fromNext","fromNext");
Queue2.addOutPort("toPrev","Prev");
Queue2.addOutPort("toNext","toNext");
Queue3.addInPort("fromPrev","fromPrev");
Queue3.addInPort("fromNext","fromNext");
Queue3.addOutPort("toPrev","toPrev");
Queue3.addOutPort("toNext","toNext");
Server1.addInPort("fromPrev","fromPrev");
Server1.addOutPort("toPrev","toPrev");
Server1.addOutPort("toNext","toNext");
Server1.addOutPort("Vozvrat","Vozvrat");
Server1.addInPort("fromNext","fromNext");
Server2.addInPort("fromPrev","fromPrev");
Server2.addOutPort("toPrev","toPrev");
Server2.addOutPort("toNext","toNext");
Server2.addOutPort("Vozvrat","Vozvrat");
Server2.addInPort("fromNext","fromNext");
Server3.addInPort("fromPrev","fromPrev");
Server3.addOutPort("toPrev","toPrev");
Server3.addOutPort("Vozvrat","Vozvrat");
queuemodel.getIC().addCouple("MessageGenerator1","toQueue","Queue1","fromMessageGenerator");
queuemodel.getIC().addCouple("Queue1","toNext","Server1","fromPrev");
queuemodel.getIC().addCouple("Server1","toNext","Queue2","fromPrev");
queuemodel.getIC().addCouple("Server1","Vozvrat","Queue1","Vozvrat");
queuemodel.getIC().addCouple("Server1","toPrev","Queue1","fromNext");
queuemodel.getIC().addCouple("Queue2","toPrev","Server1","fromNext");
queuemodel.getIC().addCouple("Queue2","toNext","Server2","fromPrev");
queuemodel.getIC().addCouple("Server2","toNext","Queue3","fromPrev");
queuemodel.getIC().addCouple("Server2","Vozvrat","Queue1","Vozvrat");
queuemodel.getIC().addCouple("Server2","toPrev","Queue2","fromNext");
queuemodel.getIC().addCouple("Queue3","toPrev","Server2","fromNext");
queuemodel.getIC().addCouple("Queue3","toNext","Server3","fromPrev");
queuemodel.getIC().addCouple("Server3","Vozvrat","Queue1","Vozvrat");
queuemodel.getIC().addCouple("Server3","toPrev","Queue3","fromNext");
queuemodel.init();
Date d1 = new Date();
double time =10000.0;
while ( !(queuemodel.getLocalTime()>time)) {
queuemodel.getProcessor().Simulate();
}
System.out.println("Пакетов отправлено: " +MessageGenerator1.num);
System.out.println("Число отказов во 2 ой очереди: " +Queue2.numOfRej);
System.out.println("Число отказов в 3 ей очереди: " +Queue3.numOfRej);
/*System.out.println("Осталось в первой очереди " +Queue1.numOfMessages);*/
System.out.println("Число возвратов с первого сервера " +Server1.vozvrat);
System.out.println("Число возвратов со второго сервера " +Server2.vozvrat);
System.out.println("Число возвратов с третьего сервера " +Server3.vozvrat);
System.out.println("Число возвратов в первую очередь " +Queue1.vozvrat);
System.out.println("Средняя длина 2 ой очереди " +(double)Queue2.Dlina/(double)Queue2.Chislo);
System.out.println("Средняя длина 3 ей очереди " +(double)Queue3.Dlina/(double)Queue3.Chislo);
System.out.println("Максимальная длина 1 ой очереди " +Queue1.max);
System.out.println("Процент сквозняков в первой очереди "+(double)Queue1.skvoz*100/(double)Queue1.num +"%");
System.out.println("Процент сквозняков во второй очереди "+(double)Queue2.skvoz*100/(double)Queue2.num +"%");
System.out.println("Процент сквозняков в третей очереди "+(double)Queue3.skvoz*100/(double)Queue3.num +"%");
Date d2=new Date();
long d = d2.getTime()-d1.getTime();
System.out.println("Время моделирования:" +d);
}
}
2.Queue1.java.
package DEJaView.modelLibs.a;
import DEJaView.core.*;
import java.util.*;
/** Класс, реализующий работу очереди сообщений (требований) */
public class Queue1 extends AtomicPDEVS {
/**Счётчик, подсчитывающий число пакетов в очереди*/
public int numOfMessages = 0;
/** Флаг, показывающий свободен ли сервер */
private boolean serverIsFree = true;
public int vozvrat;
public int skvoz=0;
public int num=0;
public int max=0;
/** Создает объект Queue с заданным именем
* @param name имя создаваемого объекта ксласса Client */
protected Queue1(String name) {
super(name);
/* Объекты класса Queue могут находится в одном из 5-тии
* состояний, в зависимости от количесва сообщений в очереди
*/
addState("free");
addState("full");
}
/** Инициализация компонента */
protected void init() {
/* Описание системного порта */
Port p;
/* Задание начального времени */
this.setLastTime(0);
/* Задание начального состояния */
this.setPresentState(findState("free"));
/* Далее генерируем начальное системное сообщение */
MessagePDEVS init_m = new MessagePDEVS("", Double.POSITIVE_INFINITY, this.getLastTime());
/* Далее передаем системное сообщение сообщение в очередь сообщений
* мультикомпонента, непосредственно содержащего данный компонент: */
/* 1. Назначение порта */
p = resolveOutPort("system");
/* 2. Назначение сообщения */
p.setMessage(init_m);
/* 3. Собственно передача сообщения */
this.getParentMULC().getProcessor().PassMessage(this.getName(), p.getName());
}
/** Функция продвижения времени */
protected double ta() {
return Double.POSITIVE_INFINITY;
}
/** Внутренняя функция транзакции */
protected State delta_int() {
return this.getPresentState();
}
/** Внешняя функция транзакции */
protected State delta_ext() {
State newState = null;
/* Если сообщение пришло от сервера, то оно означает, что сервер готов обслуживать
* следующее сообщение (требование). В таком случае, если в очереди есть сообщения
* (требования), переходим в очереди новое состояние: уменьшаем количество сообщений
* (требований), ожидающих в обслуживания очереди на 1. */
if (this.getCurrentPort().getName().equals("fromNext")) {
serverIsFree = true;
/* Если в очереди было одно сообщение (требование), то теперь там не будет ни одного */
if (this.getPresentState().getName().equals("full")) {
newState = this.getPresentState();
if(numOfMessages==1)
newState = findState("free");
}
else
/* Если в очереди было два сообщения (требования), то теперь там будет одно */
if (this.getPresentState().getName().equals("free")) {
newState = this.getPresentState();
}
}
else
/* Если сообщение (требование) пришло от клиента, то если очередь не заполнена,
* "вставляем" это сообщение (требование) в очередь, переходя в новое состояние */
if (this.getCurrentPort().getName().equals("fromMessageGenerator")){
num++;
if(!serverIsFree){
/* Если в очереди было пять сообщений (требований), то их там и останется пять */
if (this.getPresentState().getName().equals("full")){
numOfMessages++;
newState=this.getPresentState();
}
else
/* Если в очереди не было сообщений (требований), то теперь там будет одно */
if (this.getPresentState().getName().equals("free")) {
numOfMessages++;
newState=findState("full");
}
}
else
if(serverIsFree){
/*проверить ещё надо*/
newState=findState("free");
/* serverIsFree=false;*/
/*serverIsFree=false;*/
}
}
else
if(this.getCurrentPort().getName().equals("Vozvrat")){
num++;
if(!serverIsFree){
/* Если в очереди было пять сообщений (требований), то их там и останется пять */
if (this.getPresentState().getName().equals("full")){
numOfMessages++;
newState=this.getPresentState();