У цьому підручнику ми збираємося вивчити важливу концепцію алгоритмів планування процесів ЦП. Важлива назва концепції – «першим прийшов, першим обслужено». Це основний алгоритм, який повинен вивчити кожен студент, щоб зрозуміти всі основи алгоритмів планування процесів центрального процесора.
First Come First Serve прокладає шлях до розуміння інших алгоритмів. Цей алгоритм може мати багато недоліків. Але ці недоліки створили дуже нові та ефективні алгоритми. Отже, наш обов’язок — дізнатися про алгоритми планування процесів ЦП «першим прийшов, першим обслужено».
Важливі скорочення
- ЦП - - - > Центральний процесор
- FCFS - - - > Перший прийшов, перший подав
- AT - - - > Час прибуття
- BT - - - > Час вибуху
- WT - - - > Час очікування
- TAT - - - > Turn Around Time
- CT - - - > Час завершення
- FIFO - - - > Першим прийшов, першим вийшов
Перший прийшов перший обслужений
Алгоритм планування ЦП «першим прийшов, першим обслужено», коротко відомий як FCFS, є першим алгоритмом алгоритму планування процесів ЦП. В алгоритмі «перший прийшов, перший обслужений» ми дозволяємо процесу виконуватися лінійно.
Це означає, що будь-який процес, який першим увійшов до черги готовності, виконується першим. Це показує, що алгоритм «першим прийшов, першим обслужено» дотримується принципу «першим прийшов, першим вийшов» (FIFO).
Алгоритм «перший прийшов, перший обслужений» може бути виконаний у попередній спосіб і без попереднього вилучення. Перш ніж перейти до прикладів, давайте зрозуміємо, що таке попередній і не попередній підхід у плануванні процесів ЦП.
Попередній підхід
У цьому випадку попереднього планування процесу ОС виділяє ресурси для процесу на заздалегідь визначений період часу. Під час розподілу ресурсів процес переходить із стану роботи в стан готовності або зі стану очікування в стан готовності. Це перемикання відбувається тому, що ЦП може призначити іншим процесам пріоритет і замінити поточний активний процес процесом з вищим пріоритетом.
Невиключний підхід
У цьому випадку Non Emptive Process Scheduling ресурс не можна вилучити з процесу до завершення роботи процесу. Коли запущений процес завершується і переходить у стан очікування, ресурси перемикаються.
Ефект конвою в режимі «Хто прийшов, перший подав» (FCFS)
Ефект конвоювання — це явище, яке виникає в алгоритмі планування під назвою «першим прийшов, першим обслужено» (FCFS). Алгоритм планування за принципом «перший прийшов, перший обслужений» виконується без випередження.
карта reactjs
Спосіб без випередження означає, що якщо процес або завдання розпочато, операційна система повинна завершити цей процес або завдання. Поки процес або завдання не дорівнює нулю, новий або наступний процес або завдання не розпочне своє виконання. Визначення невипереджувального планування з точки зору операційної системи означає, що центральний процесор (ЦП) буде повністю виділений до кінця процесу або завдання, розпочатого першим, а новий процес або завдання виконується лише після завершення старішого процесу або робота.
Може бути кілька випадків, які можуть призвести до того, що центральний процесор (ЦП) виділяє занадто багато часу. Це пов’язано з тим, що в алгоритмі планування без випередження за принципом «перший прийшов, перший обслужений» процеси або завдання вибираються в послідовному порядку. Через це більш короткі завдання або процеси, що стоять за великими процесами або завданнями, займають надто багато часу для завершення їх виконання. Через це час очікування, час виконання та час завершення дуже високі.
Отже, оскільки перший процес великий або час завершення занадто великий, тоді виникає цей ефект конвойу в алгоритмі «перший прийшов, перший обслужив».
Припустімо, що довготривала робота потребує нескінченного часу. Тоді інші процеси повинні чекати такий же нескінченний час. Завдяки цьому ефекту конвою, створеному довгостроковою роботою, голодування процесів очікування зростає дуже швидко. Це найбільший недолік FCFS CPU Process Scheduling.
Характеристики планування процесів ЦП FCFS
Характеристики планування процесів центрального процесора FCFS:
- Реалізація проста.
- Не викликає жодних наслідків під час використання
- Він приймає непревентивну стратегію, а попереджувальну стратегію.
- Він виконує кожну процедуру в порядку їх отримання.
- Час прибуття використовується як критерій відбору процедур.
Переваги FCFS CPU Process Scheduling
Переваги FCFS CPU Process Scheduling:
- Щоб розподілити процеси, він використовує чергу «Першим прийшов, першим вийшов».
- Процес планування процесора FCFS простий і простий у реалізації.
- У ситуації FCFS із попереджувальним плануванням немає ймовірності зупинки процесу.
- Оскільки пріоритет процесу не враховується, це справедливий алгоритм.
Недоліки FCFS CPU Process Scheduling
Недоліки FCFS CPU Process Scheduling:
- Алгоритм планування ЦП FCFS має тривалий час очікування
- Планування ЦП FCFS надає перевагу ЦП над операціями введення або виведення
- У FCFS існує ймовірність появи ефекту конвою
- Оскільки FCFS настільки відвертий, він часто не дуже ефективний. Разом із цим тривалі періоди очікування. Усі інші замовлення залишаються неактивними, якщо центральний процесор зайнятий обробкою одного замовлення, що потребує багато часу.
Проблеми в алгоритмі планування процесора «першим прийшов, першим обслужено».
приклад
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Невиключний підхід
А тепер давайте розв’яжемо цю проблему за допомогою алгоритму планування під назвою «Перший прийшов, перший обслужений» у невипереджувальному підході.
Діаграма Ганта для прикладу 1 вище:
Час обробки = час завершення - час прибуття
Час очікування = час обороту - час вибуху
Рішення вищевказаного питання Приклад 1
| Так ні | ID процесу | Час прибуття | Час вибуху | Час завершення | Час обороту | Час очікування | |
|---|---|---|---|---|---|---|---|
| 1 | П 1 | А | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | Б | 1 | 3 | 12 | одинадцять | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | одинадцять |
| 4 | P 4 | Д | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | І | 2 | 3 | двадцять один | 19 | 16 |
| 6 | С. 6 | Ф | 3 | 2 | 23 | двадцять | 18 |
Середній час завершення:
Середній КТ = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Середній КТ = 97 / 6
Середній КТ = 16,16667
Середній час очікування:
Середня WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Середній WT = 66 / 6
Середній WT = 11
java print
Середній час обороту:
Середній TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
Середній TAT = 89 / 6
Середній TAT = 14,83334
Ось як FCFS вирішується в Non Emptive Approach.
Тепер давайте зрозуміємо, як їх можна вирішити за допомогою попереднього підходу
Попередній підхід
Тепер давайте розв’яжемо цю проблему за допомогою алгоритму планування під назвою First Come First Serve у попередньому підході.
У Pre Emptive Approach ми шукаємо найкращий доступний процес
типи циклу for
Діаграма Ганта для прикладу 1 вище:
| Так ні | ID процесу | Час прибуття | Час вибуху | Час завершення | Час обороту | Час очікування | |
|---|---|---|---|---|---|---|---|
| 1 | П 1 | А | 0 | 9 | 23 | 23 | 14 |
| 2 | P 2 | Б | 1 | 3 | 8 | 7 | 4 |
| 3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | Д | 1 | 4 | п'ятнадцять | 14 | 10 |
| 5 | P 5 | І | 2 | 3 | одинадцять | 9 | 7 |
| 6 | С. 6 | Ф | 3 | 2 | 5 | 2 | 0 |
| далі → ← поперед Щоб позбутися проблеми марнування сигналів пробудження, Дейкстра запропонував підхід, який передбачає збереження всіх дзвінків пробудження. Дейкстра стверджує, що замість того, щоб надавати дзвінки пробудження безпосередньо споживачеві, виробник може зберегти дзвінок пробудження в змінній. Кожен із споживачів може прочитати його, коли йому це потрібно. Семафор — це змінні, які зберігають усі виклики пробудження, які передаються від виробника до споживача. Це змінна, читання, зміна та оновлення якої відбувається автоматично в режимі ядра. Семафор не можна реалізувати в режимі користувача, оскільки завжди може виникнути конкуренція, коли два або більше процесів намагаються отримати доступ до змінної одночасно. Для впровадження завжди потрібна підтримка операційної системи. Відповідно до вимог ситуації Semaphore можна розділити на дві категорії.
Ми детально обговоримо кожен з них. |