Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота №1
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Кафедра інформаційних технологій видавничої справи
Кафедра:
Кафедра інформаційних технологій видавничої справи
Інформація про роботу
Рік:
2020
Тип роботи:
Лабораторна робота
Предмет:
Системне програмування та операційні системи
Варіант:
7 19 7
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
кафедра інформаційних технологій видавничої справи
/
ЗВІТ ДО ЛАБОРАТОРНОЇ РОБОТИ № 1
з дисципліни: «Системне програмування»
на тему:
ПЛАНУВАННЯ ПРОЦЕСІВ
Львів - 2020
Мета роботи: дослідити та освоїти основні стратегії планування процесу, практично застосувати їх в коді.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Короткостроковий планувальник вибирає процеси з черги готових процесів і передає їх на виконання в CPU. Використовуються наступні критерії, що дозволяють порівнювати алгоритми короткострокових планувальників:
1. Утилізація CPU (CPU utilization) теоретично може знаходитися в межах від 0 до 100%. У реальних системах утилізація CPU 40% – 90% в залежності від завантаженості CPU.
2. Пропускна спроможність (CPU throughput) може вимірюватися кількістю процесів, які виконуються в одиницю часу.
3. Час обороту (turnaround time). Для деяких процесів важливим критерієм є повний час виконання, тобто інтервал від моменту появи процесу у вхідній черзі до моменту його завершення. Цей час і є часом обороту і включає час очікувань у вхідній черзі, в черзі готових процесів, в чергах до обладнання, час виконання в процесорі і час вводу - виводу.
4. Час очікування (waiting time). Під часом очікування розуміється сумарний час знаходження процесу в черзі готових процесів.
5. Час відгуку (response time). Для суто інтерактивних програм важливим показником є час відгуку або час від моменту попадання процесу у вхідну чергу до моменту першого звернення до терміналу.
1. Стратегія планування процесу FIFO
Перший прийшов – перший обслуговується (First come – first served FCFS).
FIFO є простою стратегією планування процесів і полягає в тому, що процесор передається другому процесу, який раніше його запитав. Коли процес попадає в чергу готових процесів, process control bloc приїднується до хвоста черги. Середній час очікування для стратегії FCFS великий і залежить від порядку надходження процесів у чергу готових процесів.
Стратегії FCFS властивий так званий «ефект конвою». У тому випадку, коли в комп’ютері є один великий процес і декілька малих, то всі процеси збираються на початку черги готових процесів, а потім в черзі до обладнання. Це приводить до зниження завантаженості як процесора, так і периферійного обладнання.
2. Стратегія найбільш короткої роботи – SJF.
SJF – Shortest Job First. Одним з методів боротьби з «ефектом конвою» є стратегія, що дозволяє процесу з черги виконуватися перший. SJF знижує час очікування черги. Найбільша складність в практичній реалізації полягає в неможливості заздалегідь визначити величину часу подальшого обслуговування. Тому стратегія SJF часто застосовується в довгострокових планувальниках, обслуговуючих пакетний режим. У цьому випадку замість величини часу подальшого обслуговування використовується допустимий максимальний час виконання завдання, який програміст повинен специфікувати перед відправкою завдання в пакет.
3. Стратегія пріоритетного планування.
Описані раніше стратегії можуть розглядатися як окремі випадки стратегії пріоритетного планування. Ця стратегія передбачає, що кожному процесу приписується пріоритет, що визначає черговість надання йому CPU.
Пріоритет – це ціле позитивне число, що знаходиться в деякому діапазоні, наприклад від 0 до 7, від 0 до 4095. Будемо вважати, що чим менше значення числа, тим вище пріоритет процесу. Пріоритети визначаються виходячи з сукупності внутрішніх і зовнішніх по відношенню до операційної системи чинників.
Внутрішні чинники:
вимоги до пам'яті;
кількість відкритих файлів;
відношення середнього часу вводу - виводу до середнього часу CPU.
Зовнішні чинники:
важливість процесу;
тип і величина файлів, що використовуються;
відділення, що виконує роботи і так далі.
Внутрішні чинники можуть використовуватися для автоматичного призначення пріоритетів самою операційною системою, а зовнішні для примусового, за допомогою оператора.
Головний недолік пріоритетного планування полягає в можливості блокування на невизначено довгий час низькопріоритетних процесів.
Для усунення зазначеного недоліку використовуються наступні методи: процеси, час очікування яких перевищує фіксовану величину, автоматично отримують одиничний приріст пріоритету.
4. “Карусельна” стратегія планування (Round Robin – RR).
Round Robin стратегія застосовується в системах розділення часу. Визначається невеликий відрізок часу, який називають квантом часу (10..100мс). Черга готових процесів розглядається як кільцева. Процеси циклічно переміщаються по черзі, отримуючи CPU на час, рівний одному кванту. Новий процес додається в хвіст черги. Якщо процес не завершився в межах виділеного йому кванта часу, його робота примусово уривається, і він переміщається в хвіст черги.
Властивості Round Robin стратегії сильно залежать від величини тимчасового кванта q. Чим більший часовий квант, тим довше за Round Robin стратегія наближається до FCFS.
При малих значеннях часового кванту RR - стратегію називають розділенням процесора – processor sharing. Це означає, що кожен з N процесів працює зі своїм власним процесором, продуктивність процесора дорівнює 1/N від продуктивності фізичного процесора.
5. Стратегія планування з використанням багаторівневої черги (multilevel queue scheduling).
Ця стратегія розроблена для ситуації, коли процеси можуть бути легко класифіковані на декілька груп, наприклад, часто процеси розділяють на дві групи: інтерактивні (процеси переднього плану) і пакетні (фонові). Інтерактивні і пакетні процеси мають різні вимоги до короткострокового планувальника, наприклад стосовно часу відгуку.
Стратегія багаторівневої черги розділяє чергу готових процесів на декілька черг, в кожній з яких знаходяться процеси з однаковими властивостями, і кожний з яких може плануватися своєю стратегією, наприклад RR для інтерактивних і FCFS для пакетних процесів.
Взаємодія черг здійснюється за наступними правилами: жоден процес з більш низьким пріоритетом не може бути запущений, поки не виконаються процеси у всіх чергах з більш високим пріоритетом. Робота процесу з черги з більш низьким пріоритетом може бути припинена, якщо в одній з черг з більш високим пріоритетом з'явився процес.
6. Стратегія планування з використанням багаторівневої черги з зворотними зв’язками (multilevel feedback queue sheduling).
Звичайна багаторівнева черга не допускає переміщення процесів між чергами. Багаторівнева черга із зворотними зв'язками передбачає, що процеси при певних умовах можуть переміщатися між чергами.
Процеси спочатку попадають в чергу 0, отримуючи кванти часу, рівні 8мс. Процеси, що не виконалися протягом цього часу, переходять в чергу 1,де вони починають оброблятися тільки тоді, коли черга 0 стає пуста. Процеси, які не виконалися в черзі 1 (q=16мс) переходять в чергу 2, де вони будуть оброблятися лише тоді, коли стають пусті черги 0 і 1.
Розглянута стратегія є найбільш універсальною і поєднує в собі властивості всіх розглянутих раніше стратегій.
РЕЗУЛЬТАТ ВИКОНАННЯ ЗАВДАННЯ
Код програми:
import time class Process: def __init__(self, nm, pr, tm, tp): self.name = nm self.priority = pr self.time = tm self.done = 0 self.type = tp P1 = Process('Process 1', 1, 12, 'SP') P2 = Process('Process 2', 4, 15, 'IPc') P3 = Process('Process 3', 3, 16, 'IPr') P4 = Process('Process 4', 2, 11, 'PP') P5 = Process('Process 5', 5, 13, 'StP') P6 = Process('Process 6', 6, 14, 'IPc') P7 = Process('Process 7', 7, 16, 'PP') P8 = Process('Process 8', 8, 11, 'SP') P9 = Process('Process 9', 9, 10, 'IPr') P10 = Process('Process 10', 10, 17, 'SP') array = [P1, P2, P3, P4, P5, P6, P7, P8, P9, P10]
def execute(proc, mode): if mode == 0: print('Executing ', proc.name, 'for', proc.time, 'seconds...') time.sleep(proc.time) print('Done') if mode == 1: print('Executing ', proc.name, 'for 1 seconds...') time.sleep(1) proc.done += 1 print('Done') def FIFO(arr): print('Process planning strategy FIFO')
n = 1 print('List: ') for i in arr: print('#', n, ':', i.name) n += 1 print('Execution:') for i in arr: execute(i, 0) def SJF(arr): print('Time planning strategy SJF') n = 1 print('List: ') for i in arr: print('#', n, ':', i.name) n += 1 arr.sort(key=lambda x: x.time, reverse=False) print('Execution:') for i in arr: execute(i, 0) def PPS(arr): print('Priority planning strategy') n = 1 print('List: ') for i in arr: print('#', n, ':', i.name) n += 1 arr.sort(key=lambda x: x.priority, reverse=False) print('Execution:') for i in arr: execute(i, 0) def RR(arr): print('Round Robin planning strategy') n = 1 print('List: ') for i in arr: print('#', n, ':', i.name) n += 1 arr.sort(key=lambda x: x.time, reverse=True) max = arr[0].time print('Execution:') for i in range(max): for j in arr: if j.done != j.time: execute(j, 1)
def MQS(arr): sp =[] ipc =[] ipr =[] pp =[] stp =[] for i in arr: if i.type is 'SP': sp.append(i) if i.type is 'IPc': ipc.append(i) if i.type is 'IPr': ipr.append(i)
if i.type is 'PP': pp.append(i) if i.type is 'StP': stp.append(i) print("Starting to process SystemProcesses with #1 priority with FIFO method") FIFO(sp) print("Starting to process InteractiveProcesses(Clean) with #2 priority with RR method") RR(ipc) print("Starting to process InteractiveProcesses(Edited) with #3 priority with PPS method") PPS(ipr) print("Starting to process PacketProcesses with #4 priority with SJF method") SJF(pp) print("Starting to process StudentProcesses with #5 priority with SJF method") SJF(stp) print("------DONE PROCESSING QUEUE------") while (True): print("----Menu----") print("1)FIFO") print("2)SJF") print("3)PPS") print("4)RR") print("5)MQS") print("6)") print("7)Exit") n = int(input()) if n == 1: FIFO(array) if n == 2: SJF(array) if n == 3: PPS(array) if n == 4: RR(array) if n == 5: MQS(array) if n == 7: break
Робота меню:
/
Стратегія FIFO:
/
/
/
Стратегія SJF:
/
/
Стратегія PPS
/
/
Стратегія RR:
/
/
Стратегія MQS:
/
/
/
Таблиця процесів:
Назва
Час
Пріорітетність
Група
Стратегія виконання процесів в групі
Process 1
2
1
System Processes
FIFO
Process 2
5
4
Interactive Processes (Clean)
RR
Process 3
6
3
Interactive Processes (Edited)
PPS
Process 4
1
2
Packet Processes
SJF
Process 5
3
5
Student Processes
SJF
Process 6
4
6
Interactive Processes (Clean)
RR
Process 7
6
7
Packet Processes
SJF
Process 8
1
8
System Processes
FIFO
Process 9
3
9
Interactive Processes (Edited)
PPS
Process 10
7
10
System Processes
FIFO
ВИСНОВКИ
На цій лабораторній роботі я дослідила та освоїла основні стратегії планування процесу, практично застосувала їх в коді, продемонструвавши принципи їх роботи.
06.06.2020 06:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора