я
При реалізації пріоритетних дисциплін обслуговування окремим процесам і потокам надається переважне право перейти в стан виконання відповідно до встановлених для них пріоритетами. Пріоритети можуть бути фіксованими (постійними) і динамічними (змінними в ході обчислювального процесу), що, звичайно, вимагає додаткових ресурсів НД на обчислення пріоритетів і ускладнює ОС.
Розглянемо коротко деякі найбільш поширені алгоритми планування, тимчасові діаграми роботи яких необхідно побудувати в першому завданні курсової роботи.
Лінійні алгоритми планування реалізують виконання процесів і потоків в порядку черги, яка організовується згідно тим чи іншим угодам/7-9 /.
Найпростішою в реалізації є дисципліна обслуговування, при якій процеси і потоки виконуються в порядку їх появи в НД Цей алгоритм називається «першим прийшов - першим обслужений», або FCFS (Firstcome - FirstServed). Ті процеси і потоки, які були заблоковані в процесі виконання, після переходу в стан готовності знову ставляться в чергу готовності. При цьому можливі два варіанти.
У першому найпростішому варіанті розблокований процес або потік ставиться в кінець черги готових процесів і потоків.
У другому варіанті планувальник поміщає розблокований процес або потік перед тими процесами або потоками, які ще не виконувалися. Таким чином, утворюються дві черги: одна черга утворюється з нових процесів або потоків, а друга черга - з раніше виконувалися, але потрапили в стан очікування. Такий підхід дозволяє реалізувати стратегію обслуговування «закінчувати виконання процесів або потоків в порядку їх появи». Розглянутий алгоритм відноситься до невитисняючих.
До основних переваг цього алгоритму можна віднести його просту реалізацію, справедливість і малі витрати системних ресурсів на формування черги завдань.
Істотним недоліком алгоритму є зростання середнього часу очікування обслуговування при збільшенні завантаження НД, причому короткі процеси, які вимагають невеликих витрат машинного часу, змушені очікувати стільки ж, скільки і трудомісткі.
Уникнути зазначеного недоліку дозволяє невитисняючих алгоритм, при якому планувальник вибирає першим для виконання найкоротший процес (завдання). Цей алгоритм називається «найкоротший процес (задача) - перший», або SJN (ShortestJobNext)/2 /. Алгоритм дозволяє зменшити оборотне час - середній час від моменту надходження процесу (завдання) на виконання до завершення виконання.
Нехай є чотири процесу з часом виконання першого - a, другої - b, третьої - c і четвертого - d. Тоді перший процес виконається через час ta=a, другий - через час tb=a + b, третій через час tc=a + b + c, а четвертий через час td=a + b + c + d. Отже, середнє оборотне час to обчислення чотирьох процесів одно to=(ta + tb + tc + td)/4=(4a + 3b + 2c + d) 4. Очевидно, що внесок часу a в середнє більше, ніж всіх інших інтервалів часу, тому першим повинен виконуватися найкоротший процес, а останнім - найдовший, що вносить вклад рівний власного оборотного часу. Цей висновок справедливий для будь-якої кількості процесів і потоків.
Наступною версією попереднього алгоритму планування є алгоритм найменшого часу, що залишився виконання, або SRT (ShortestRemainingTime)/2,7-9 /. Відповідно до цього алгоритмом планувальник щоразу вибирає на виконання процес з найменшим залишилися часом виконання. Коли з'являється новий процес, його повне час виконання порівнюється з рештою часом виконання поточного процесу. Якщо час виконання нового процесу менше, поточний процес припиняється і керування передається новому процесу. Цей алгоритм дозволяє швидко обслуговувати короткі процеси.
У витісняючої алгоритмі планування, заснованому на квантуванні, кожному потоку по черзі для виконання надається обмежений безперервний період процесорного часу - квант (timeslice). Цей алгоритм отримав назву циклічного (карусельного), або RR (RoundRobin) .Смена активного потоку відбувається, якщо:
потік завершився і покинув систему
сталася помилка;
потік перейшов у стан очікування;
вичерпаний квант процесорного часу, відведений даному потоку.
Потік, який вичерпав свій квант, переводиться в стан готовності і очікує, коли йому буде надано новий квант процесорного часу, а на виконання відповідно до певним правилом вибирається новий потік з черги готових.
Кванти, виділювані процесам (потоками), можуть бути однаковими для всіх процесів або різними.
В основі витісняють алгоритмів планування, що використовують пріоритети процесів і потоків, лежить концепція пріоритетного обслуговування. Прі...
