Министерство
информационных технологий и связи РФ
Сибирский
государственный университет телекоммуникаций и информатики
Факультет
информатики и вычислительной техники
Кафедра
вычислительных систем
Курсовая
работа
по курсу
Моделирование
Выполнили: Степанов Е.Е.
Гордеев С.А.
Гомзяков А.В.
студенты гр.ВМ-37
Проверил: Рудых Я.И.
Новосибирск
2005
Содержание
1. Постановка задачи
2. Описание модели в терминах PDEVS
формализма
3. Атомарные компоненты
4. Полученные результаты
5. Основные фрагменты кода
Вывод
1.
Постановка
задачи
Модель состоит из трех
обслуживающих серверов. Каждый сервер имеет очередь, в которой заявки могут
ожидать своей очереди. Также есть генератор сообщений. Первая очередь
бесконечная, остальные конечные. Обработки заявок всех серверов распределены
экспоненциально. В начальный момент времени очереди. Необходимо построить
модель в терминах PDEVS-формализма и
произвести эксперименты над моделью с помощью пакета DEJaView.
Необходимо ответить на
следующие вопросы:
1)
Выдать статистику
по всем очередям.
2)
Максимальную
длину первой очереди.
3) Сколько процентов сообщений прошло
через очередь без задержек - «сквозняки».
Рис. 1. Схематическое
изображение модели
2.
Описание
модели в терминах PDEVS формализма
В PDEVS-модели
существует 7 компонент:
Queue1, Queue2
и Queue3 – это три очереди.
Server1, Server2
и Server3 – это три прибора (сервера). Время
обслуживания распределено экспоненциально.
MessageGenerator - генератор сообщений.
Рассмотрим более подробно логику работы компонент.
1. Генератор подает сообщение в очередь Queue1.
2. В начальный момент времени все серверы находятся
в состоянии free (свободен). Cерверы Server1,
Server2 посылают сообщение на очереди Queue2 и Queue3 соответственно, это говорит о готовности серверов
принимать сообщения.
3.
Приняв сообщение
каждая очередь подаёт сообщение на выход toNext и он приходит на вход fromPrev соответствующего каждой очереди
сервера.
4.
Сервет меняет
своё состояние с free (свободен) на
busy (занят) и через некоторое время
подаёт сообщение на выход toNext
и после этого ждёт от следующей очереди подтверждения что в данной очереди ещё
есть хотя бы одно место.
5.
После того как
сервер отправил сообщение слёдующей очереди, он переходит в состояние free (свободен) и посылает предыдущей
очереди сообщение, которое говорит о готовности сервера принимать следующее
сообщение.
6.
Также существует
возможность перехода сообщения с Серверов в очередь Queue1 с вероятностями P1, P2, P3.
3.Атомарные компоненты
атомарной компоненты
класса атомарной компоненты
состояния компоненты
порты
порты
Busy
Busy
Busy
Full
Алгоритмы функционирования компонент:
Компоненты классов 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. Результаты работы модели
5.
Основные
фрагменты кода
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
serverIsFre
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();
}
else
/*
Если в очереди не было сообщений (требований), то теперь там будет одно */
if
(this.getPresentState().getName().equals("free")) {
numOfMessages++;
newState=findState("full");
}
}
else
if(serverIsFree){
/*проверить ещё надо*/
newState=findState("free");
}
}
else
newState = this.getPresentState();
return
newState;
}
/** Выходная функция
(создания списка выходных событий) */
protected LinkedList lambda()
{
LinkedList list = new LinkedList();
MessagePort mp1 = new MessagePort();
MessagePDEVS msg1 = new MessagePDEVS();
/* System.out.println("Очередь 1");*/
/* Реакция на
сообщения от клиента */
if (this.getCurrentPort().getType().equals("fromMessageGenerator"))
{
/* Если сообщение от клиента приходит
в тот момент, когда очередь была пуста, а сервер
* свободен,
тогда формируется и отправляется на обработку сообщение серверу */
if
((this.getPresentState().getName().equals("free")))
{
if(serverIsFree)
{
/*
Занимаем сервер */
serverIsFree
= false;
skvoz++;
/*
Установка метки времени */
msg1.setTimeStamp(this.getCurrentPort().getMessage().getTimeStamp());
/* Назначение выходного порта */
mp1.setPort("toNext");
/*
Текст для отладки и трассировки */
msg1.setData("from
Queue to Server");
/* Назначение сообщения на выходной
порт */
mp1.setMessage(msg1);
/*
Добавление в список выходных событий */
list.add(mp1);
return list;
}
}
}
else
/*
Реакция на сообщение от сервера. Очередь реагирует на сообщения от сервера о
том,
* что
сервер свободен, только тогда, когда очередь не пуста */
if(this.getCurrentPort().getType().equals("fromNext"))
{
if(this.getPresentState().getName().equals("full")
|| (numOfMessages==1)){
/* Занимаем сервер */
serverIsFree = false;
/*
Установка метки времени */
msg1.setTimeStamp(this.getCurrentPort().getMessage().getTimeStamp());
/* Назначение выходного порта */
mp1.setPort("toNext");
/*
Текст для отладки и трассировки */
msg1.setData("from
Queue to Server");
/* Назначение сообщения на выходной
порт */
mp1.setMessage(msg1);
/*
Добавление в список выходных событий */
list.add(mp1);
numOfMessages--;
return
list;
}
}
else
if(this.getCurrentPort().getType().equals("Vozvrat"))
{
vozvrat++;
/*
Если сообщение от клиента приходит в тот момент, когда очередь была пуста, а
сервер
*
свободен, тогда формируется и отправляется на обработку сообщение серверу */
if ((this.getPresentState().getName().equals("free"))
&& (serverIsFree)) {
/* Занимаем сервер */
serverIsFree = false;
skvoz++;
/* Установка метки времени */
msg1.setTimeStamp(this.getCurrentPort().getMessage().getTimeStamp());
/*
Назначение выходного порта */
mp1.setPort("toNext");
/*
Текст для отладки и трассировки */
msg1.setData("from
Queue to Server");
/*
Назначение сообщения на выходной порт */
mp1.setMessage(msg1);
/*
Добавление в список выходных событий */
list.add(mp1);
return list;
}
}
if(max<numOfMessages)
max=numOfMessages;
return list;
}
/** Конфликтная
функция транзакции (пуста) */
protected String
confluent() {
return
"external";
}
}
3.Server1.java.
package
DEJaView.modelLibs.a;
import
DEJaView.core.*;
import
java.util.*;
import java.util.Random;
/** Класс, реализующий
работу сервера, обрабатывающего сообщения (требования) */
public class
Server1 extends AtomicPDEVS {
/** Параметр распределения,
интенсивность потока */
private final static double sigma = 1.0;
private final static
double P = 0.95;
private
double V;
public
int vozvrat;
/** Вспомогательная переменная */
private double ta;
Random ra = new Random();
/** Создает объект
Server с заданным именем
* @param name имя создаваемого объекта ксласса Server */
protected Server1(String
name) {
super(name);
/* Объекты класса Server могут находиться в одном из двух
состояний, в зависимости
* от того, занят
сервер обработкой сообщения (требования) или нет */
addState("busy");
addState("free");
}
/** Инициализация компонента */
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() {
if
(this.getPresentState().getName().equals("busy")) {
ta =
Generator.genExp(sigma);
return
ta;
}
else
return
Double.POSITIVE_INFINITY;
}
protected
State delta_int() {
return
this.getPresentState();
}
protected
State delta_ext() {
State
newState = findState("busy");
return
newState;
}
protected
LinkedList lambda() {
LinkedList list = new LinkedList();
MessagePort mp1 = new MessagePort();
MessagePort mp2 = new MessagePort();
MessagePDEVS msg1 = new MessagePDEVS();
MessagePDEVS msg2 = new MessagePDEVS();
/*
System.out.println("Сервер 1");*/
if
(this.getCurrentPort().getType().equals("fromPrev")) {
V=ra.nextDouble();
if((V<P)||(V==P)){
msg1.setTimeStamp(this.getLastTime()
+ ta);
mp1.setPort("toNext");
msg1.setData("from
Server to Client: Message have being processing from" + this.getLastTime()
+ " till " + msg1.getTimeStamp());
mp1.setMessage(msg1);
list.add(mp1);
msg2.setTimeStamp(this.getLastTime()+
ta);
msg2.setPriority(1);
mp2.setPort("toPrev");
msg2.setData("from
Server to Queue: Server is free");
mp2.setMessage(msg2);
list.add(mp2);
}
else
if(V>P){
msg1.setTimeStamp(this.getLastTime()
+ ta);
mp1.setPort("Vozvrat");
vozvrat++;
/* System.out.println("Возврат с первого сервера" +V);*/
msg1.setData("from Server to Queue1");
mp1.setMessage(msg1);
list.add(mp1);
msg2.setTimeStamp(this.getLastTime()+ ta);
msg2.setPriority(1);
mp2.setPort("toPrev");
msg2.setData("from Server to Queue: Server is free");
mp2.setMessage(msg2);
list.add(mp2);
}
}
return
list;
}
protected
String confluent() {
return "external";
}
}
Вывод
В ходе проделанной работы были изучены основы
моделирования. Также мы получили практические навыки имитационного
моделирования.
Подробно был изучен PDEVS-формализм и пакет
моделирования систем с дискретными событиями DEJaView. Исследованы принципы функционирования простейших моделей
теории массового обслуживания. Разработан и реализован алгоритм
функционирования одной из моделей теории массового обслуживания, описанной в
терминах PDEVS под DEJaView.