Министерство информационных технологий и связи РФ
Сибирский государственный университет телекоммуникаций и информатики
Факультет информатики и вычислительной техники
Кафедра вычислительных систем
Курсовая работа
по курсу Моделирование
Выполнили: Степанов Е.Е.
Гордеев С.А.
Гомзяков А.В.
студенты гр.ВМ-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--PAGE_BREAK--
Так же выполняем действия необходимые для вычисления средней длины очереди
}
Иначе
Если (Очередь не ждёт освобождения сервера )
{
«Сквозняк»
Выполняем действия по вычислению доли сквозняков
}
Иначе
Если (пришло сообщение от сервера)
{
Флаг готовности сервера ставим в значение истина
}
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; продолжение
--PAGE_BREAK--
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(); продолжение
--PAGE_BREAK--
}
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;
/* Если сообщение пришло от сервера, то оно означает, что сервер готов обслуживать
* следующее сообщение (требование). В таком случае, если в очереди есть сообщения
* (требования), переходим в очереди новое состояние: уменьшаем количество сообщений продолжение
--PAGE_BREAK--
* (требований), ожидающих в обслуживания очереди на 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++;
/* Установкаметкивремени*/ продолжение
--PAGE_BREAK--
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
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(); продолжение
--PAGE_BREAK--
/** Создает объект 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
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.