Міністерство інформаційних технологій і зв'язку РФ
Сибірський державний університет телекомунікацій та інформатики
Факультет інформатики та обчислювальної техніки
Кафедра обчислювальних систем
Курсова робота
по курсу Моделювання
Виконали: Степанов Є.Є.
Гордєєв С.А.
Гомзяков А.В.
студенти гр.ВМ-37
Перевірив: Рудих Я.І.
Новосибірськ 2005
Зміст
Постановка завдання
Опис моделі в термінах PDEVS формалізму
Атомарні компоненти
Отримані результати
Основні фрагменти коду
Висновок
Постановка завдання
Модель складається з трьох обслуговуючих серверів. Кожен сервер має черга, в якій заявки можуть чекати своєї черги. Також є генератор повідомлень. Перша черга нескінченна, інші кінцеві. Обробки заявок всіх серверів розподілені експоненціально. У початковий момент часу черги. Необхідно побудувати модель в термінах PDEVS-формалізму і провести експерименти над моделлю за допомогою пакету DEJaView.
Необхідно відповісти на такі питання:
Видати статистику по всіх черг.
Максимальну довжину першої черги.
Скільки відсотків повідомлень пройшло через чергу без затримок - «протяги».
Рис. 1. Схематичне зображення моделі
Опис моделі в термінах PDEVS формалізму
У PDEVS-моделі існує 7 компонент:
Queue 1, Queue 2 і Queue 3 - це три черги.
Server 1, Server 2 і Server 3 - це три прилади (сервера). Час обслуговування розподілено експоненціально.
MessageGenerator - генератор повідомлень.
Розглянемо більш детально логіку роботи компонент.
1. Генератор подає повідомлення в чергу Queue 1.
2. У початковий момент часу всі сервери знаходяться в стані free (вільний). C ервери Server 1, Server 2 посилають повідомлення на черзі Queue 2 і Queue 3 відповідно, це говорить про готовність серверів приймати повідомлення.
Прийнявши повідомлення кожна чергу подає повідомлення на вихід toNext і він приходить на вхід fromPrev відповідного кожної черги сервера.
Сервет змінює свій стан з free (вільний) на busy (зайнятий) і через деякий час подає повідомлення на вихід toNext і після цього чекає від наступної черги підтвердження що в даній черзі ще є хоча б одне місце.
Після того як сервер відправив повідомлення наступної черги, він переходить у стан free (вільний) і посилає попередньої черги повідомлення, яке говорить про готовність сервера приймати таке повідомлення.
Також існує можливість переходу повідомлення з Серверів у чергу Queue 1 з ймовірностями P 1, P 2, P 3.
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 |
Алгоритми функціонування компонент:
Компоненти класів Server 1 і Server 2:
Delta _ int:
Залишаємося в поточному стані
Delta _ exp
Якщо (прийшов новий пакет від черги)
{
переходимо в стан "busy"
}
Lambd a
Якщо (Повідомлення від попередньої черги) {
Якщо пакет оброблений, то намагаємося відправити його наступної черги.
Випадково визначаємо куди піде повідомлення - або на початок ланцюга, або в наступну чергу.
Відсилаємо попередньої черги повідомлення про те що сервер звільнився.
}
Компоненти класу Queue 2, Queue 3:
Delta _ int:
залишаємося в поточному стані
Delta _ exp
Якщо (прийшов новий пакет)
{
Якщо (Прапор очікування, очікування звільнення сервера)
{
Збільшуємо лічильник надійшли пакетів на 1
Так само виконуємо дії необхідні для обчислення середньої довжини черги
}
Інакше
Якщо (Черга не чекає звільнення сервера)
{
«Сквозняк»
Виконуємо дії з вирахування частки протягів
}
Інакше
Якщо (прийшло повідомлення від сервера)
{
Прапор готовності сервера ставимо в значення істина
}
Lambda
Якщо (прийшов новий пакет)
{
Якщо (Сервер вільний)
{
Відсилаємо повідомлення серверу
«Сквозняк»
Виконуємо операції з вирахування частки протягів
}
Якщо (Очікуємо сервер)
{
Якщо чергу переповнилася надсилаємо повідомлення серверу
}
}
Якщо (прийшло повідомлення від сервера)
{
Якщо (Черга не порожня) {
Надсилаємо пакет на порт toNext черзі
Зменшуємо довжину черги на 1
}
}
Компоненти класів Server 3:
Delta _ int:
Залишаємося в поточному стані
Delta _ exp
Якщо (прийшов новий пакет від черги)
{
переходимо в стан "busy"
}
Lambd a
Якщо (повідомлення від попередньої черги) {
Якщо пакет оброблений, то намагаємося відправити його наступної черги.
Випадково визначаємо куди піде повідомлення - або на початок ланцюга, або на вихід з ланцюга.
Відсилаємо повідомлення попередньої черги про те, що сервер звільнився.
}
Компонент класу Queue 1:
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 ();
}
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 ());
/ * Призначення вихідного порту * /
mp 1. setPort ("toNext");
/ * Текст для налагодження та трасування * /
msg1.setData ("from Queue to Server");
/ * Призначення повідомлення на вихідний порт * /
mp 1. setMessage (msg 1);
/ * Додавання до списку вихідних подій * /
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 ());
/ * Призначення вихідного порту * /
mp 1. setPort ("toNext");
/ * Текст для налагодження та трасування * /
msg1.setData ("from Queue to Server");
/ * Призначення повідомлення на вихідний порт * /
mp 1. setMessage (msg 1);
/ * Додавання до списку вихідних подій * /
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 ());
/ * Призначення вихідного порту * /
mp 1. setPort ("toNext");
/ * Текст для налагодження та трасування * /
msg1.setData ("from Queue to Server");
/ * Призначення повідомлення на вихідний порт * /
mp 1. setMessage (msg 1);
/ * Додавання до списку вихідних подій * /
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.