МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра систем автоматизованого проектування
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи
з дисципліни:
“ Системне програмування та операційні системи ”
На тему:
“ Розробка та реалiзацiя програми моделювання паралельних взаємодiючих процесiв ”
Допущено до захисту: Виконав: студент групи КН-24
Дата : Прийняв
Керівник :
Прийняв :
Оцінка :
Дата:
Львів 2010
Анотація
Курсова робота з курсу “Системного програмування та операційні системи”.
Розробка та реалiзацiя програми моделювання паралельних взаємодiючих процесiв. /Матляк І. Р., Львів: Національний університет “Львівська політехніка”, 2010. 27 - с.
Обсяг даної курсової роботи включно із кодом програм становить 27 сторінок. Курсова робота складається з 5-и розділів, у яких наведено основні теоретичні відомості про паралельні взаємодіючі процеси. Додаток істить текст програми і таблицю ASCII кодів.
Національний університет ” Львівська політехніка”
/назва вищого учбового закладу/
Кафедра ” Системи автоматизованого проектування ”
Дисципліна Сиситемне програмування і операційні системи
Спеціальність Комп’ютерні науки
Курс 2 Група КН-24 Семестр 4 .
Завдання
на курсовий проект студента
Матляк Ірина Романівна
/прізвище, ім’я, по – батькові/
1. Тема проекту / Розробка та реалiзацiя програми моделювання паралельних взаємодiючих процесiв
2. Термін здачі студентом закінченого проекту /роботи/ 10.06.2010 р.
3. Вхідні дані для проекту /роботи/
Теоретичні відомості про паралельні взаємодіючі процеси
4. Зміст розрахунково-пояснювальної записки /перелік питань, які підлягають розробці/
Вступна частина
Аналіз програми в загальному
Аналіз алгоритму програми
Реалізація програми
Висновки
5. Перелік графічного матеріалу / з точним зазначенням обов’язкових креслень/
Графічні схеми
6. Дата видачі завдання 11.03.2010 р.
№ п/п
Назва етапів курсового проекту ( роботи )
Термін виконання етапів проекту ( роботи )
Примітки
1.
Отримання завдання
11.03.2010 р.
2.
Уточнення завдання
7.04.2010 р.
4.
Пошук літератури
4 дні
5.
Складання алгоритму
8 дні
6.
Розробка програми
19.04.2010
11.
Тестування програм
12.05.2010
12.
Попередній перегляд проекту викладачем.
1.06.2010
13.
Здача роботи.
26.06.2010
Студент
Матляк Ірина Романівна
( підпис )
( прізвище, ім’я, по-батькові )
Керівник
Фармага Ігор Вірославович
( підпис )
( прізвище, ім’я, по-батькові )
____________________2010 р
Зміст
Вступ……………………………………………………………………..6
1. Загальна характеристика області………………………..6
1.1 Визначення процесу…………………………………6
1.2 Види процесів………………………………………...8
1.3.Види паралелізму……………………………………8
1.4.Проблема тупіків……………………………………9
2.Алгоритм розв’зку задачі…………………………….
12
3.Програмні реалізації алгоритму……………………..
13
3.1 Загальна характеристика програм ……………………
13
3.2 Призначення програм ……………………………….. .
13
3.3 Вхідна і вихідна інформація…………………………..
13
3.5 Середовище реалізації програм……………………… .
13
3.6 Технологія виконання та відлагодження програм… ..
13
4.Інструкція користувачеві програми………………….
14
5.Конрольні приклади та аналіз їх комп’ютерної реалізації…………………………………………………
15
Висновки………………………………………………...
16
Список літератури…………………………………….
17
Додатки………………………………………………….
18
Вступ
1.Загальна характеристика області
Перехід від однозадачних до мультизадачних ОС приніс не лише явний позитивний ефект,збільшення продуктивності роботи, але і ряд труднощів .
Методи і засоби вирішення проблем для однозадачних систем були неефективні у випадку багатозадачних сист. Відслідковування того що відбувається у операційній сист. де взаємодіє десяток процесів є майже неможливим, оскільки їх взаємодія носить випадковий характер .У випадку такого роду взаємодії усування помилок у системі, що виникає під час взаємодії деяких процесів відбувається майже «всліпу» і не може гарантувати того що надалі ця помилка не виникне знову. Також гостро постає проблема оптимального розділення ресурсів між процесами та, щоб вони максимально ефективно виконувались, без зайвих затримок .
Можуть виникати ситуації при яких процес перебуває в стані постійного очікування, тупіки, логічні помилки тощо.
З метою аналізу, виявлення і усунення критичних моментів які виникають під час взаємодії декількох паралельних процесів створюються типові моделі на яких механізми щодо відлагодження можна випробувати. Такий метод усунення критичних моментів дозволяє не лише покращувати існуючі методи усунення проблем , а і впроваджувати нові.
1.1 Визначення процесу
Термін процес вперше почали використовувати розробники системи MULTIX в 60-х роках. За час, що минув термін «процес» , використовувався в деяких випадках як синонім «задачі» і отримав багато різних визначень :
Програма в стадії виконання
Асинхронна робота
«жива душа» процедури
«концентрація засобів управління» для процедури що виконується
Щось, представлене у вигляді «блоку управління процесом» в операційній системі
Об’єкт, якому виділяються процесори
Зустрічаются і інші визначення :
« Коцепція процесу представляє собою природне узагальнення роботи рентерабельних програм у середовищі з віртуальною пам’яттю » за Шоу. Це узагальнене визначення випливає на основі розгляду термінів і понять що описують динамічно взаємодіючу систему.
Першим з таких понять є :
Активності . Характеристики продуктивності що прямо чи опосередковано пов’язані зі швидкістю з якою система виконує свою роботу. Робота відбувається шляхом виконання активностей. Сама активність , з нашої точки зору на систему, є найменшою одиницею роботи. Хоча активність може бути представлена сукупністю більш дрібних функцій і її виконання може тривати відносно довго, ми, тим не менше, розглядаємо її як єдиний дискретний крок.
Процеси. Логічно пов'язаний набір активностей утворює процес, котрий можна розглядати як об’єкт, що містить або ініціює ці активності. Деякі процеси можуть виступати в ролі активності чи субпроцеса в процесі більш високого рівня.
«Процесом називають сукупність одного або декількох потоків і захищеного адресного простору, у якому ці потоки виконуються » за Шеховцом і потік розуміється відповідно, як набір послідовно виконуваних команд процесора, який використовують загальний адресний простір процесу.
1.2 Види процесів
Процеси можна поділяти як за властивістю їх поведінки (взаємодіючі, незалежні) так і за порядком виконання (паралельні, квазіпаралельні, послідовні) .
Максимальна кількість процесів (захищених адресних просторів) і потоків, які в них виконуються, може варіювати в різних системах. В однозадачних системах є тільки один адресний простір, у якому у кожен момент часу може виконуватись один потік. Для них є властивими як взаємодіючі так і незалежні процеси. Але порядок виконання доступний лише послідовний, враховуючи специфіку системи(однозадачність). При такій взаємодії , перший процес передає дані наступному процесу.
Процеси називаються паралельними, якщо вони існують одночасно. Паралельні процеси можуть працювати абсолютно незалежно одне від одного або вони можуть бути асинхронними, що означає , що їм періодично потрібно синхронізуватись і взаємодіяти.
Квазіпаралельні процеси (лат. Quasi – майже) процеси котрі виконуються «порційно» . Кожен процес виконується частково і по черці. З першого погляду може здатись що квазіпаралельні процеси майже нічим не відрізняються від паралельно послідовних процесів, але на практиці із врахування особливостей роботи реального процесора, квазіпаралельне виконання процесів дозволяє виконати їх значно швидше.
3.Види паралелізму
Можна виділити такі основні види паралелізму :
Паралелізм багатопроцесорних систем
Паралелізм операцій введення-виведення
Паралелізм взаємодії з користувачем
Паралелізм розподілених сист.
Перший з них є справжнім паралелізмом, тому що у багатопроцесорних системах інструкції виконують декілька процесів одночасно.
Паралелізм операцій введення-виведення
Під час виконання операції введення-виведення (наприклад обміну даними із диском) низькорівневий код доступу до диска і код застосування не можуть виконуватись одночасно. У цьому разі застосуванню треба почекати завершення операції введення-виведення, звільнивши за цей час процесор. Природнім вважається зайняти на цей час процесор інструкціями іншої задачі.
Багатопотокове застосування може реалізувати цей вид паралелізму через створення нових птоків, які будуть виконуватись,коли поточній потік очікує операції введення-виведення. Так реалізується асинхронне введення-виведення, коли застосування продовжує своє виконання, не чекаючи завершення операцій введення-виведення.
4.Проблема тупіків.
При організації рівнобіжного виконання декількох процесів однією з функцій ОС є рішення складної задачі коректного розподілу ресурсів між процесами які виконуються. При рівнобіжному виконанні процесів можуть виникати ситуації, при яких два чи більше процесів весь час знаходитимуться в заблокованому стані. Кажуть, що в мультипрограмній системі процес знаходиться в стані тупіка, якщо він чекає подію, яка ніколи не виконається. Частіше тупіки виникають, із-за конкуренції незв’язаних, паралельних процесів за ресурси системи, але іноді до тупіків приводять помилки програмування.
При розгляді проблеми тупіків доцільно поняття ресурсів систем розділити на два класи — повторно використовувані (чи системні) ресурси (типу RR чи SR) і споживані (ті що витрачаються) ресурси (типу CR).
Повторно використовуваний ресурс (SR) є кінцева безліч ідентичних одиниць з наступними властивостями :
· число одиниць ресурсу постійно;
· кожна одиниця ресурсу, доступна чи розподілена одному і тільки одному процесу.
· процес може звільнити одиницю ресурсу (зробити її доступною), тільки якщо він раніше одержав цю одиницю, тобто ніякий процес не може впливати ні на один ресурс, якщо він йому не належить.
Дане визначення виділяє істотні для вивчення проблеми тупіків властивості звичайних системних ресурсів, до яких ми відносимо такі типи апаратури, як основна пам'ять, допоміжна (зовнішня) пам'ять, периферія і, можливо, процесори, а також програмне і інформаційне забезпечення, таке як файли даних, таблиці і „дозвіл ввійти у критичну секцію”.
Ресурс, що витрачається (CR) відрізняється від ресурсу типу SR у декількох відносинах :
- число доступних одиниць деякого ресурсу типу CR змінюється по мірі того, як здобуваються й звільняються (виробляються) окремі їхні елементи процесам що виконуються.
- процес „користувач” зменшує число одиниць ресурсу, спочатку запрошуючи, а потім здобуваючи (споживаючи) одну чи більше одиниць. Одиниці ресурсу, що придбані, у загальному випадку не повертаються ресурсу, а споживаються (витрачаються).
Методи боротьби з тупіками.
Проблема тупіків є надзвичайно серйозною та складною. У деяких випадках ціна, яку приходиться платити за те, щоб зробити систему вільною від тупіків, занадто висока. В інших випадках, наприклад у системах керування процесами реального часу, просто немає іншого вибору, оскільки виникнення тупіка може привести до катастрофічних наслідків.
Проблема боротьби з тупиками стає усе більш актуальною і складною по мірі розвитку і впровадження рівнобіжних обчислювальних систем.
Запобігання тупіків
Запобігання тупіків базується на ідеї про надзвичайно високу його вартість, тому краще витратити додаткові ресурси системи, щоб виключити імовірність виникнення тупіка при будь-яких обставинах. Цей підхід використовується в найбільш відповідальних системах, часто це системи реального часу.
Запобігання можна розглядати як заборону існуванню небезпечних станів.
Умову взаємного виключення можна придушити шляхом дозволу необмеженого поділу ресурсів. Умову чекання можна придушити, попередньо виділивши ресурси. При цьому процес може почати виконання, тільки одержавши всі необхідні ресурси. Необхідно також відзначити, що попереднє виділення переважно неможливе, тому що всі необхідні ресурси стають відомими процесу тільки після початку виконання.
Умову кругового очікування можна виключити, передбачаючи утворення ланцюгу запитів. Це можна забезпечити за допомогою принципу ієрархічного виділення ресурсів.
В цілому стратегія запобігання тупіків — це дуже дороге вирішення проблеми, і вона використовується нечасто.
командую повернення каретки. Система веде облік введених рядків, результат заноситься у глобальну змінн
2. Алгоритм розв’зку задачі
Програма цієї курсової роботи призначена для моделювання керування видачі пристроїв, що запобігає виникненню тупіків,
Спочатку ми виводимо повідомлення про введення чисел. Після цього поелементно в циклі вводимо числа. Потім переводимо числа в цифровий формат. Після виведення повідомлення ми чекаємо на натискання відповідних клавіші відповідно до натиснутої клавіші виконуємо певну арифметичну дію. Після ьцого знову переводимо результат в текстовий формат і виходимо з програми
3 Прогpамні реалізації алгоритму
3.1 Характеристика програм
Текст програми складається з 331 стрічки програмного коду і 31 використаної змінної(символа). Для створення виконавчого файлу використовується бібліотека fort.lib . Програма працює у текстовому режимі відображення інформації.
3.2 Призначення програм
Моделювання менеджера керування видачі пристроїв, що запобігає виникненню тупіків, або повідомляє про їх можливе виникнення.
3.3 Вхідна і вихідна інформація
Вхідні дані містяться в файлі data.txt і можуть бути змінені. Вихідна інформація поступає у вигляді таблиці даних, що циклічно оновлюється до вичерпання потреб усіх користувачів, або до моменту появи попередження про можливий тупік.
3.5 Середовище реалізації програм
Праграма працює на машинах типу IBM PC з процесорами сімейства x86 (16/32/64-розрядними). Найбільш оптимальним середовищем запуску є MS-DOS. Також може запускатись в середовищы Windows (Win98-WinXP) у командному рядку.
3.6 Технологія виконання та
відлагодження програм
Програмний код перетворюється у об’єктний файл за допомогою транслятора (masm.exe, wasm.exe, tasm.exe, або довільним іншим). Під час роботи з транслятором можна створити файл лістингу в якому будуть міститися дані про саму програму і вказані помилки, якщо такі допущені. Далі за допомогою лінкера LINK.exe встановлюются звязки ы створюэтся виконавчий файл.
У файлі лістингу можуть бути зазначені рядок що містить помилку і її опис. У разі не створення файлу лістингу слід переглянути уважно код на наявність критичних помилок і усунути їх в ручну, або видалити підозрілі секції.
4.Інструкція користувачеві
Перед початком роботи слід відкрити файл data.txt будь-яким текстовим редактором і задати початкові значення. Перший рядок містить число всього доступних пристроїв. Другий і наступні (залежно від к-ть користувачів) містять число уже взатих пристрої і після пробілу в загальному неоюхідних.
Зауваження : к-ть користувучав повинно бути однозначним, інакше программа або не зчитає дані або буде працювати не корректно.
Далі можна запустити саму программу і слідувати інструкціям.
5. Контрольні приклади та аналіз
результатів їх коп’ютерної реалізації
(Скріншоти програми)
Висновки
Результатом курсової роботи стала розробка менеджера керування видачі пристроїв, що запобігає виникненню тупіків, або повідомляє про їх можливе виникнення.
Методи і засоби вирішення проблем для однозадачних систем були неефективні у випадку багатозадачних сист. Відслідковування того що відбувається у операційній сист. де взаємодіє десяток процесів є майже неможливим, оскільки їх взаємодія носить випадковий характер .У випадку такого роду взаємодії усування помилок у системі, що виникає під час взаємодії деяких процесів відбувається майже «всліпу» і не може гарантувати того що надалі ця помилка не виникне знову. Також гостро постає проблема оптимального розділення ресурсів між процесами та, щоб вони максимально ефективно виконувались, без зайвих затримок .
Можуть виникати ситуації при яких процес перебуває в стані постійного очікування, тупіки, логічні помилки тощо
Список літератури
Шеховцов В. А. Операційні системи. — К.: Видавнича група BHV, 2005. — 576 с
Дейтел Г. Введение в операционные системы. - М.: Мир, 1987
Зубков С.В. Assembler для DOS, Windows и UNIX.: - M.: ДМК, 1999
Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных: Пер. с англ./Под ред. М. Брейера. — М.: Мир, 1979. — 464 с.
Операционные системы (Столлингс)
Таблиця ASCII кодів http://guap.ru/guap/kaf82/meth/ascii.pdf
Додаток 1
Текст програми
title New
sseg segment stack
db 256 dup(?)
sseg ends
dseg segment
mes db 'K-t korystuvachiv$'
A1 db 'Vudileni$'
A2 db 'prystroji$'
B1 db 'Maksymalno$'
B2 db 'neobhidni$'
mes1 db 'User$'
warn db 'Chyslo povynno buty odnoznachnym$'
path db 'D:\PRG\data.txt',0
dseg ends
cseg segment
assume cs:cseg,ds:dseg,ss:sseg
start: jmp main
main: push ds
mov ax,0
mov ax,dseg
mov ds,ax
;------------------------------------------------------------
mov ah,3dh
mov al,2
mov dx, offset path
int 21h
jc exit
;------------------К-ть користувачів-------------------------
crkl: Mov dx, offset mes
Mov ah, 09h
Int 21h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;---------------Зчитати символ------------------------------
Mov ah, 10h
Int 16h
;--------------Зберегти аscii код числа---------------------
cmp al,031h
je on
cmp al,032h
je tw
cmp al,033h
je tr
cmp al,034h
je fr
cmp al,035h
je fv
cmp al,036h
je sx
cmp al,037h
je sv
cmp al,038h
je eg
cmp al,039h
je nn
jmp cond
Mov ah, 06h
;-----------------Line1-------------------------------------
;-----------------Enter-------------------------------------
draw: Mov dl, 0Ah
Int 21h
Mov dl, 0Dh
Int 21h
;--------------Рамка----------------------------------------
Mov dl, 0C9h
Int 21h
mov cx,8
;-----------------------------------------------------------
a: Mov dl, 0Cdh
Int 21h
loop a
Mov dl, 0Cbh
Int 21h
mov cx,10
;-----------------------------------------------------------
b: Mov dl, 0Cdh
Int 21h
loop b
Mov dl, 0Cbh
Int 21h
mov cx,11
;-----------------------------------------------------------
c: Mov dl, 0Cdh
Int 21h
loop c
Mov dl, 0bbh
Int 21h
jmp brk
;-----------------------------------------------------------
;-----------------------------------------------------------
on: mov bl,1
jmp draw
tw: mov bl,2
jmp draw
tr: mov bl,3
jmp draw
fr: mov bl,4
jmp draw
fv: mov bl,5
jmp draw
sx: mov bl,6
jmp draw
sv: mov bl,7
jmp draw
eg: mov bl,8
jmp draw
nn: mov bl,9
jmp draw
cond: mov dx, offset warn
Mov ah, 09h
Int 21h
jmp crkl
;-----------------------------------------------------------
;-----------------Line2-------------------------------------
;-----------------Enter-------------------------------------
brk: Mov dl, 0Ah
Int 21h
Mov dl, 0Dh
Int 21h
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
mov cx,8
;-----------------------------------------------------------
d: Mov dl, 020h
Int 21h
loop d
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;-----------------------------------------------------------
Mov dx, offset A1
Mov ah, 09h
Int 21h
Mov ah, 06h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;-----------------------------------------------------------
Mov dx, offset B1
Mov ah, 09h
Int 21h
Mov ah, 06h
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
;-----------------Line3-------------------------------------
;-----------------Enter-------------------------------------
Mov dl, 0Ah
Int 21h
Mov dl, 0Dh
Int 21h
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
mov cx,8
;-----------------------------------------------------------
d1: Mov dl, 020h
Int 21h
loop d1
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;-----------------------------------------------------------
Mov dx, offset A2
Mov ah, 09h
Int 21h
Mov ah, 06h
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;-----------------------------------------------------------
Mov dx, offset B2
Mov ah, 09h
Int 21h
Mov ah, 06h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
;-----------------Line4-------------------------------------
;-----------------Enter-------------------------------------
Mov dl, 0Ah
Int 21h
Mov dl, 0Dh
Int 21h
;--------------Рамка----------------------------------------
Mov dl, 0CCh
Int 21h
mov cx,8
;-----------------------------------------------------------
e: Mov dl, 0Cdh
Int 21h
loop e
Mov dl, 0CEh
Int 21h
mov cx,10
;-----------------------------------------------------------
f: Mov dl, 0Cdh
Int 21h
loop f
Mov dl, 0CEh
Int 21h
mov cx,11
;-----------------------------------------------------------
g: Mov dl, 0Cdh
Int 21h
loop g
Mov dl, 0b9h
Int 21h
;-----------------------------------------------------------
;--------------User Masyv-----------------------------------
mov cx,bl
;-----------------Enter-------------------------------------
Us: Mov dl, 0Ah
Int 21h
Mov dl, 0Dh
Int 21h
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
;---------------Пробіл--------------------------------------
Mov dl, 020h
Mov ah, 06h
Int 21h
;-----------------------------------------------------------
Mov dx, offset mes1
Mov ah, 09h
Int 21h
push cx
mov cx,3
;---------------Пробіл--------------------------------------
h: Mov dl, 020h
Mov ah, 06h
Int 21h
loop h
pop cx
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
push cx
mov cx,10
;---------------Пробіл--------------------------------------
i: Mov dl, 020h
Mov ah, 06h
Int 21h
loop i
pop cx
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
push cx
mov cx,11
;-----------------------------------------------------------
j: Mov dl, 020h
Mov ah, 06h
Int 21h
loop j
pop cx
;-----------------------------------------------------------
Mov dl, 0bah
Int 21h
loop us
;-----------------------------------------------------------
;-----------------Enter-------------------------------------
Mov dl, 0Ah
Int 21h
Mov dl, 0Dh
Int 21h
;--------------Рамка----------------------------------------
Mov dl, 0C8h
Int 21h
mov cx,8
;-----------------------------------------------------------
k: Mov dl, 0Cdh
Int 21h
loop k
Mov dl, 0CAh
Int 21h
mov cx,10
;-----------------------------------------------------------
l: Mov dl, 0Cdh
Int 21h
loop l
Mov dl, 0CAh
Int 21h
mov cx,11
;-----------------------------------------------------------
m: Mov dl, 0Cdh
Int 21h
loop m
Mov dl, 0bch
Int 21h
;-----------------------------------------------------------
;-----------------------------------------------------------
mov ax,4c00h
int 21h
jmp crkl
cseg ends
end start
Додаток 2
Табдиця ASCII кодів 128—255
(додаткові символи)