Державний комітет Російської Федерації з вищої освіти
Казанський Державний Технічний Університет імені А.Н. Туполєва
------------------------------------------ ----------------------------------< br>---------------------------
Кафедра Електронно - обчислювальних машин
Пояснювальна записка до курсової роботи з дисципліни "Моделювання"
Виконав: студентгрупи 4301 Базу Ю.А.
Керівник:доцент кафедри ЕОМ Захаров В.М.
Оцінка: 5 (отл.)
Казань 1996
Зміст
1.Заданіе ............................................... ....................< br>............................. 3
2. Формалізація концептуальноїмоделі ................................................ 4
2.1. Побудова формальної схеми функціонування системи ........ 4
2.2. Визначення параметрів і зміннихмоделі ............................. 5
2.3. Визначення одиниці модельногочасу .................................... 6
2.4. Визначення закону функціонуваннясистеми ........................... 6
3. Алгоритмізація моделі і її машиннареалізація ............................. 7
3.1. Вибір програмних засобівмоделювання ................................. 7
3.2. Опис моделюючоїпрограми ............................................. 7
3.3. Перевірка достовірностіпрограми .............................................. 8
3.4. Моделювання випадковихвпливів ......................................... 9
3.4.1. Моделювання випадкових впливів, що мають рівномірнийрозподіл ................................................. ...... 9
3.4.1.1. Апаратнийспосіб ................................................. ............. 9
3.4.1.2. Програмнийспосіб ................................................. ......... 12
3.4.1.3. Вибір генератора
РРПСЧ ................................................. .. 13
3.4.2. Моделювання випадкових впливів, що мають нерівномірнийрозподіл ................................................. 14
3.5. Опис моделює програми для стохастичної
моделі ..................................... .................................< br>....................... 18
4. Отримання та інтерпретація результатів моделювання ................... 19
5. Література
.................................................. ..........................< br>................ 20
2. Формалізація концептуальної моделі
2.1. Побудова формальної схеми функціонування системи
Побудуємо формальну схему (Q-схему) заданої обчислювальної системи.
И1
Про
И2
К
і3
Рис. 1 Q - схема обчислювальної системи
Тут:
К - ЕОМ
О - Черга
И1 - і3 - Мережеві машини
2.2.Определеніе параметрів і змінних моделі
tp - інтервал між парафіями користувачівtgz1 - час підготовки завдання 1-им користувачемtgz2 - час підготовки завдання 2-им користувачемtgz3 - час підготовки завдання 3-ім користувачемtm - час виконання завдання на ЕОМk - кількість промоделювати на ЕОМ завданьnz - наявність заявки на вході системи: nz = 0 - немає заявок
___ nz = i - наявність заявки на i-ої мережевий машині (i = 1-3)pz1 - підготовка завдання мережевий машині 1 pz1 = 1 - йде підготовка завдання на мережевій машині 1 pz1 = 0 - мережна машина 1 не зайнятаpz2 - підготовка завдання мережевий машині 2 pz2 = 1 - йде підготовка завдання на мережевій машині 2 pz2 = 0 - мережна машина 2 не зайнятаpz3 - підготовка завдання мережевий машині 3 pz3 = 1 - йде підготовка завдання на мережевій машині 3 pz3 = 0 - мережна машина 3 не зайнятаznw - наявність заявки на виконання завдання znw = 0 - заявки відсутні ___ znw = i - наявність заявки від мережевої машини i (i = 1-3)wz - виконання завдання на ЕОМ wz = 0 - ЕОМ вільна wz = i - ЕОМ виконує заявку iocher [50] - черга в черзі зберігаються номери мережних машин з яких отримано
заявкиn - індекс вільного елемента в черзіw2 - кількість вип. завдань від 2-го користувача
На першому етапі імітаційного моделювання створимо детермінованумодель заданої обчислювальної системи, замінюючи стохастичні потоки їхматематичними очікуваннями:
- інтервал між парафіями користувачів 10 хв
- імовірність приходу кожного з користувачів 0.33
- час підготовки завдання 1-им користувачем 16 хв
- час підготовки завдання 2-им користувачем 17 хв
- час підготовки завдання 3-ім користувачем 18 хв
- час виконання завдання на ЕОМ 0.8 хв
2.3. Визначення одиниці модельного часу
За одиницю модельного часу (emb) приймається мінімальний інтервалреального часу, протягом якого система не змінює свого стану. Уданої задачі за emb доцільно прийняти час рівне
0.1 хв.
2.4. Визначення закону функціонування системи
Роботу даної обчислювальної системи відобразимо тимчасовими діаграмами.
користувач
emb
160
И1
170
И2
180
і3
ЕОМ
Рис 2 . Часові діаграми роботи системи
У машинний зал з інтервалом 100 emb приходить один з користувачів.
На початку приходить перше, і починає підготовку свого завдання на це йомубуде потрібно 160 emb. Через 100 emb приходить другий користувач і тежрозпочинає підготовку завдання на це йому відведено 170 emb. Невдовзі післяприходу 2-го користувача (через 60 emb) закінчує підготовку завданняперший користувач і виконує його на ЕОМ протягом 8 emb. Через 100 embпісля приходу другого користувача приходить третій користувач, при цьомудругий продовжує підготовку. Через 70 emb після приходу третьогокористувача закінчує підготовку другого і виконує своє завдання на ЕОМза 8 emb. Третій користувач закінчує підготовку через 180 emb післясвого приходу, в цей часзнову приходить першим користувач на цьому закінчується перший цикл роботисистеми і все повторюється знову.
Таким чином за кожен цикл з періодом Т = 300 emb виконується тризавдання від кожного користувача. Всі вони виконуються відразу ж післяпідготовки і не затримують один одного, тому що ЕОМ до моменту надходженняцих заявок вільна. Весь час роботи чергу залишається порожньою. За часциклу виконується одне завдання від 2-го користувача, отже відсотоквиконаних завдань, що надійшли від другого користувача дорівнює 33,3%.
Нам потрібно змоделювати виконання 500 завдань, отже загальначас роботи системи одно (500/3) * 300 = 50.000 emb. За цей час ЕОМпропрацювала 500 * 8 = 4000 emb, отже завантаження ЕОМ дорівнює 8%.
3. Алгоритмізація моделі і її машинна реалізація
3.1. Вибір програмних засобів моделювання
Для написання програми ми вибираємо мова програмування Borland C + +.
Ця мова добре зарекомендував себе ефективністю, лаконічністю,стрункістю програм. У багатьох випадках програми, написані на мові С + +порівняні по швидкості з програмами, написаними на мові Асемблера, прице вони більш наочні і прості у супроводі. У системне оточеннямови С + + входить багато бібліотек, в тому числі бібліотеки потрібних намстандартних функцій.
Програма для детермінованою моделі наведена у Додатку № 1.
3.2. Опис моделює програми для детермінованого варіанту моделі
Параметри та змінні даної програми описані в пункті 2.2.
Так як в обраною мовою програмування не можна створити паралельніпроцеси, то ми застосуємо принцип псевдораспараллеліванія.
У програмі організуємо чергу ocher [50] в комірках якої ми запам'ятовуємоадреса заявки (мережевий номер машини). Також вводимо ряд допоміжнихзмінних (ztgz1, ztgz2, ztgz3, ztm, zk) необхідних для зберіганнязначень вихідних параметрів системи.
Дана моделююча програма працює таким чином:
Спочатку програма запитує значення параметрів системи. Даліорганізується основний цикл, який виконується k разів. Першою дією вциклі є оператор додавання одиниці машинного часу t = t + emb.
Після перевіряємо не прийшов чи користувач, якщо прийшов то визначаємо який
(Конструкція switch (cikl)). Далі в програмі йде конструкція switch
(nz) встановлює відповідні прапорці підготовки завдання. Після йдегрупа умов виконує зменшення часу підготовки завдання. Якщозавдання підготовлене то подається запит на виконання. У цьому блоціпрограми визначається не порожня чи чергу, якщо не порожня то виконуємозавдання з черги інакше виконуємо заявку з мережевою машини. Передвиконанням заявки перевіряємо зайнята чи ЕОМ, якщо зайнята то ставимо заявку вчергу. Далі якщо на ЕОМ виконується завдання то зменшуємо час виконанняцього завдання. Після чого цикл повторюється. Після завершення циклу виробляємопідрахунок відсотка виконаних завдань, що надійшли від другого користувача.
3.3. Перевірка достовірності програми
Змоделюємо роботу системи з параметрами зазначеними в завданні.
Протокол роботи програми:
Введіть інтервал між парафіями користувачів 100
Введіть час підготовки завдання 1-им користувачем 160
Введіть час підготовки завдання 2-им користувачем 170
Введіть час підготовки завдання 3-им користувачем 180
Введіть час виконання завдання на ЕОМ 8
Введіть кількість промоделювати на ЕОМ завдань 500
Відсоток вип. завдань, поступ. від 2-го корис .= 33%
Висновок:
Результати роботи моделює програми співпадають з розрахованимитеоретично, отже програма написана і працює правильно.
Визначимо оптимальну структуру обчислювальної системи: оптимальнаструктура обчислювальної системи забезпечує мінімальний час простоюустаткування досягається при наступних параметрах: інтервал міжпарафіями користувачів 2 час підготовки завдання 1-им користувачем 1 час підготовки завдання 2-им користувачем 1 час підготовки завдання 3-им користувачем 1 час виконання завдання на ЕОМ
1
3.4. Моделювання випадкових впливів
3.4.1. Моделювання випадкових впливів мають рівномірний розподіл
3.4.1.1. Апаратний спосіб
При апаратній способі випадкові або псевдовипадкові числавиробляються спеціальної електронної приставкою - генератором, якийє зовнішнім пристроєм ЕОМ або входить до складу процесора.
Найбільше поширення на практиці знайшли генератори псевдовипадковихчисел (ГПСЧ), побудовані на основі регістра зсуву за реалізацією деякоїлогічної функції в колі зворотного зв'язку (ОС) (в нашому випадку це суматорпо модулі два).
Оскільки проведення натуральних дослідів з різними схемами ГПСЧтрудомістко, то ми будемо використовувати програмний засіб дозволяєбудувати і досліджувати різні ГПСЧ на програмних моделях. Для цих цілейпідходять автоматизована система підготовки та обробки статистичноїінформації (АСПОСІ), яка являє собою комплекс програмнихзасобів, що дозволяють будувати математичні моделі різних ГПСЧ ідосліджувати їх характеристики.
Для отримання ПСЧ будемо користуватися програмою gener.
Працюючи в діалоговому режимі з ПВМ ми визначаємо структуру генератора, т.тобто деяку вихідну інформацію: розрядність регістра зсуву ГПСЧ, вид ОС,кількість та номери підключених в ланцюг ОС розрядів регістра, кількістьгенеруються чисел і ін
Отримані числа записуються у файл і аналізуються (будуєтьсягістограма) за допомогою програми analize.
Для генерації чисел ми вибрали 3 різні структури ГПСЧ:
1) Файл vihod1.dat
Разрядность: 50
Зворотній зв'язок: 30
Кількість чисел: 1000
Розрядність числа: 25
Число зрушень: 2
2) Файл vihod2.dat
Разрядность: 50
Зворотній зв'язок: 30
Кількість чисел: 1000
Розрядність числа: 25
Число зрушень: 3
3) Файл vihod3.dat
Разрядность: 70
Зворотній зв'язок: 35
Кількість чисел: 1000
Розрядність числа: 25
Число зрушень: 6
Перевіримо якість чисел у файлах програмою analize.
Побудуємо гістограми:
vihod1.dat
vihod2.dat
vihod3.dat
Перевірка відповідності чисел у послідовності необхідномурозподілу дає наступні результати: теоретичні та статистичнідані у всіх 3-х файлах за критеріями Колмогорова і Х2 не узгоджуються.
Визначення числових характеристик
| № | Характеристика | vihod1.dat | vihod2.dat | vihod3.dat | < br>| 1 | найменше значення | 0.02 | 0.005 | 0.00059 |
| 2 | найбільше значення | 0.96 | 0.996 | 0.999 |
| 3 | Мат. очікування | 0.39 | 0.51 | 0.49 |
| 4 | Дисперсія | 0.078 | 0.086 | 0.085 |
| 5 | Среднеквадратіч.отклон. | 0.279 | 0.294 | 0.292 |
| 6 | Ексцес | -1.92 | -1.024 | -1.12 |
Визначення характеристик кореляції
? (?) ?(?)
1 1
0? 0
?
5
5
vihod1.datvihod2.dat
?(?)
1
0?
5
vihod3.dat
Висновок:
1) Зі збільшенням числа зрушень характеристики чисел поліпшуються.
2) З наведених 3-х файлів найякісніші числа знаходяться у файлі vihod3.dat, оскільки числа в послідовності достатньо незалежні. Але в той же час немає узгодженості по обом критеріям.
3.4.1.2. Програмний спосіб
При програмному способі псевдовипадкові числа нам необхідносформувати методом множення.
Суть методу: вибирається два n - розрядних числа X1 і X2. X1> 0 |
| |? > 0 | |
| Числові | m | 1 /? |
| m характеристики |? | 1 /? |
| D | | |
| Алгоритм отримання | ______ | 1 |
| випадкової величини | xi =? -2 ln z1 cos2? z2 | xi =- ---- ln zi |
| | Xi +1 =? -2 Ln z1 cos2? |? |
| | Z2 | |
| | (M = 0; D = 1) | |
| Область значень | | |
| випадкової величини | | |
Дослідження послідовності нормально розподілених ПСЧ.
(Програма в додатку № 3)
Визначення числових характеристик
| | | Теоретичне | Статистичне |
| № | Характеристика | | |
| | | Значення | значення |
| 1 | Мін.знач.совокупності | 11 | 12.31 |
| 2 | Макс.знач.совокуп-ти | 24 | 25.23 |
| 3 | Мат. очікування | 16 | 16.02 |
| 4 | Дисперсія | 2 | 2.07 |
| 5 | Сред.квадр.отклоненіе | 1 | 1.439 |
| 6 | Коефф.ассіметріі | 0 | 0.35 |
| 7 | Ексцес | 0 | 2.716 |
Апроксимація стат. розподілу теоретичної функцією.
Перевірка відповідності чисел послідовності необхідномурозподілу дає наступні результати:
Критерій Хі-Квадрат:
Х2 = 0.0000813
З довірчої ймовірністю 0.999 можна стверджувати про узгодженістьтеоретичних і статистичних даних.
Критерій Колмогорова:
Максимальна різниця max | F (x)-F * (x) | = 0.0823
З довірчої ймовірністю 0.999 можна стверджувати про узгодженістьтеоретичних і статистичних даних.
Визначення характеристик кореляції
?(?)
1
0?
5
Рис. 4. Графік зміни коефіцієнта кореляції.
Висновок:
Отримана послідовність ПСЧ, що має нормальний законрозподілу, задовольняє висунутим вимогам за якістю і можебути використана в задачах моделювання, оскільки
- Числові характеристики мають незначне відхилення від теоретичних значень,
- За критеріями згоди отримані задовільні значення довірчих ймовірностей,
- Числа послідовності достатньо незалежні, про що свідчить графік (Мал. 4.)
Послідовності ПСЧ для 2-го і 3-го користувачів генеруютьсяаналогічно, з тією лише різницею, що мат. очікування у них 17 і 18відповідно.
Дослідження послідовності експоненціально розподілених ПСЧ
(Програма в додатку № 3)
Визначення числових характеристик
| | | Теоретичне | Статистичне |
| № | Характеристика | | |
| | | Значення | значення |
| 1 | Мін.знач.совокупності | 0.5 | 0.8 |
| 2 | Макс.знач.совокуп-ти | 3.5 | 2.358 |
| 3 | Мат. очікування | 0.8 | 1.06 |
| 4 | Дисперсія | 0.08 | 0.066 |
| 5 | Сред.квадр.отклоненіе | 0.5 | 0.2575 |
| 6 | Коефф.ассіметріі | 0 | 1.682 |
| 7 | Ексцес | 0 | 1.097 |
Апроксимація стат. розподілу теоретичної функцією
Перевірка відповідності чисел послідовності необхідного законурозподілу дає наступні результати:
Критерій Хі-Квадрат:
Значення Х2 = 2310
З довірчої ймовірністю 0.999 можна стверджувати про узгодженістьтеоретичних і статистичних даних.
Критерій Колмогорова:
Максимальна різниця max | F (x)-F * (x) | = 0.023
З довірчої ймовірністю 0.91 можна стверджувати про узгодженістьтеоретичних і статистичних даних.
Визначення характеристик кореляції
?(?)
1
0?
5
Рис. 5. Графік зміни коефіцієнта кореляції.
Висновок:
Отримана послідовність ПСЧ, що мають експонентний законрозподілу, задовольняє висунутим вимогам за якістю і можебути використана в задачах моделювання, оскільки
- Числові характеристики мають незначне відхилення від теоретичних значень,
- За критеріями згоди отримані задовільні значення довірчих ймовірностей,
- Числа послідовності достатньо незалежні, про що свідчить графік (Рис. 5.)
3.5. Опис моделює програми для стохастичної моделі
Перетворимо раніше створену детерміновану модель обчислювальноїсистеми в стохастичну модель. Для цього потрібні наступні змінидетермінованою програми:
- Вставимо програмний генератор РРПСЧ - вбудовану функцію random () повертає РРПСЧ в інтервалі (0,1) - для визначення часу між парафіями користувачів.
- Файл norm-1.dat, що має нормальний закон розподілу з m = 16, D = 2 для визначення часу підготовки завдання на 1-ій мережевий машині.
- Файл norm-2.dat, що має нормальний закон розподілу з m = 17, D = 2 для визначення часу підготовки завдання на 2-ий мережевий машині.
- Файл norm-3.dat, що має нормальний закон розподілу з m = 18, D = 2 для визначення часу підго?? товки завдання на 3-ій мережевий машині.
- Файл expon.dat, що має експонентний закон розподілу з m = 0.8 для визначення часу виконання завдання на ЕОМ.
- Приберемо функції введення з клавіатури які використовувалися для введення параметрів системи.
Стохастична моделююча програма наведена в Додатку № 4.
4. Отримання та інтерпретація результатів моделювання
Значення вихідних характеристик, отримані при прогін моделі зрізними випадковими впливами.
| № |% виконаних завдань, |
| прогону | поступ. від 2-го |
| | Користувача |
| 1 | 9% |
| 2 | 9% |
| 3 | 9% |
| 4 | 9% |
| 5 | 9% |
| 6 | 9% |
| 7 | 9% |
| 8 | 9% |
| 9 | 9% |
| 10 | 9% |
| сред.зн | 9% |
|. | |
Висновок:
Усереднені значення вихідний характеристики підтверджують данідетермінованою моделі тому з введенням ймовірності приходу другукористувача рівною 0.1 в детерміновану модель теоретичне значеннявідсотка виконаних завдань надійшли від другого користувача стаєрівним 10%.
Література
1. Розробка САПР. № 9
В.М. Чорненький. Імітаційне моделювання.
2. Лекції з курсу "Моделювання".
3. Б. Страуструп. Мова програмування С ++.
4. Шрайбер Г.Д. Моделювання на GPSS.
5. Є.І. Козелл. від Сі до С ++.
Додаток № 1
// ЗАВДАННЯ 15. Детермінована модель системи.
# include
# include
const emb = 1;// одиниця машинного часу
main ()
(Int tp = 100;// інтервал між парафіями користувачів int tgz1 = 160;// час підготовки завдання 1-им користувачем int tgz2 = 170;// час підготовки завдання 2-им користувачем int tgz3 = 180;// час підготовки завдання 3-ім користувачем int tm = 8;// час виконання завдання на ЕОМ int k = 500;// кількість промоделювати на ЕОМ завдань int t = 0;// час
char nz = 0;// наявність заявки на вході системи char cikl = 0;// цикл приходу заявок char pz1 = 0;// підготовка завдання на мережевій машині 1 char pz2 = 0;// підготовка завдання на мережевій машині 1 char pz3 = 0;// підготовка завдання на мережевій машині 1 char znw = 0;// наявність заявки на виконання завдання char wz = 0;// виконання завдання на ЕОМ char ocher [50];// чергу char n = 0;// індекс вільного елемента в черзі int w2 = 0;// кількість вип. завдань від 2-го користувача
int ztgz1, ztgz2, ztgz3, ztm, zk;// перем.для запам'ятовування параметрів системи
printf ( "Введіть інтервал між парафіями користувачів");scanf ( "% d", & tp); printf ( "Введіть час підготовки завдання 1-им користувачем"); scanf ( "% d", & tgz1); ztgz1 = tgz1; printf ( "Введіть час підготовки завдання 2-им користувачем" ); scanf ( "% d", & tgz2); ztgz2 = tgz2; printf ( "Введіть час підготовки завдання 3-им користувачем"); scanf ( "% d", & tgz3); ztgz3 = tgz3; printf ( "Введіть час виконання завдання на ЕОМ "); scanf ("% d ", & tm);ztm = tm; printf ( "Введіть кількість промоделювати на ЕОМ завдань"); scanf ( "% d", & k); zk = k;
//----------- моделює цикл ----------------------------------- while (k! = 0)
(t = t + emb;
//поява користувача if (t% tp == 0) switch (cikl)
(case 0: nz = 1; cikl = 1; break; case 1: nz = 2; cikl = 2; break ; case 2: nz = 3; cikl = 3; break; case 3: nz = 1; cikl = 0;
)
// початок підготовки завдання switch (nz)
(case 1: pz1 = 1; nz = 0; break; case 2: pz2 = 1; nz = 0; break; case 3: pz3 = 1; nz = 0;
)
Додаток № 1 (продовження)
// підготовка завдання if (pz1 == 1) if (tgz1 == 0) (pz1 = 0; znw = 1; tgz1 = ztgz1;) else tgz1 = tgz1-emb; if (pz2 == 1) if (tgz2 == 0) (pz2 = 0; znw = 2; tgz2 = ztgz2;) else tgz2 = tgz2-emb; if (pz3 = = 1) if (tgz3 == 0) (pz3 = 0; znw = 3; tgz3 = ztgz3;) else tgz3 = tgz3-emb;
// запит на виконання if (n! = 0 & & wz == 0) (wz = ocher [n-1]; n -;)// якщо чергу не порожня а
ЕОМ свобода
// те що виконують. заявку зчерги if (znw! = 0)// якщо є заявка на виконання if (wz == 0) (wz = znw; znw = 0;)// якщо ЕОМ не зайнята else// якщо ЕОМ зайнята, то ставимо заявку в чергу
(if (n> = 50) (printf ( "nПереполненіе черги! n"); return 0;) else (ocher [n] = znw; znw = 0; n + +;)
)
//виконання завдання на ЕОМ switch (wz)
(case 1: if (tm == 0) (wz = 0; k -; tm = ztm;) else tm = tm-emb; break ; case 2: if (tm == 0) (wz = 0; k -; w2 + +; tm = ztm;) else tm = tm-emb;break; case 3: if (tm == 0) (wz = 0; k -; tm = ztm;) else tm = tm-emb;
)
) printf ( "nПроцент вип . завдань, поступ. від 2-го корис .=% d% ", 100 * w2/zk);
)
Додаток № 2
//Генерування рівномірно розподілених випадкових величин
# include
long x = 7533;// псевдовипадкове число
long Rnd (long x)// процедура формування чергового псевдовипадковогочисла
(Int l = 5169; long k = 65536; return (l * x)% k;
)
void main ()
(FILE * fout;// вихідний файл випадкових величин int i;// параметр циклу
fout = fopen ( "vi_gpsc1.dat", "w"); for (i = 1; i = 50) (printf ( "nПереполненіе черги! n"); return 0;) else (ocher [n] = znw; znw = 0; n + +;)
)
//виконання завдання на ЕОМ switch (wz)
(case 1: if (tm == 0) (wz = 0; k -; tm = expon ();) else tm = tm-emb ;break; case 2: if (tm == 0) (wz = 0; k -; w2 + +; tm = expon ();) else tm = tm -emb; break; case 3: if (tm == 0) (wz = 0; k -; tm = expon ();) else tm = tm-emb;
)
) printf ( "nПроцент вип. завдань, поступ. від 2-го корис .=% d%", 100 * w2/500); fclose (ravn); fclose (norm1); fclose (norm2); fclose (norm3); fclose ( exp);
)
