Планування процесора Algorithms in Operating Systems
Натаніель Брукс
⚡ Розумний підсумок
Планування процесора визначає, який готовий процес операційна система запустить наступним,ping завантаженість процесора та покращення продуктивності за допомогою таких алгоритмів, як «перший прийшов, перший обслуговується», «найкоротша робота спочатку», «пріоритет» та «круговий робімон».
Що таке планування ЦП?
Планування процесора — це процес визначення, який процес володітиме процесором для виконання, поки інший процес перебуває в режимі очікування. Головне завдання планування процесора полягає в тому, щоб щоразу, коли процесор залишається бездіяльним, ОС вибирала принаймні один з процесів, доступних у черзі готовності для виконання. Процес вибору виконується планувальником процесора, який вибирає один з процесів у пам'яті, готових до виконання.
Типи планування ЦП
Ось два види методів планування:
Випереджувальне планування
У випереджувальному плануванні завданням здебільшого призначаються їхні пріоритети. Іноді важливо виконати завдання з вищим пріоритетом перед іншим завданням з нижчим пріоритетом, навіть якщо завдання з нижчим пріоритетом все ще виконується. Завдання з нижчим пріоритетом затримується на деякий час і відновлюється, коли завдання з вищим пріоритетом завершить своє виконання.
Невипереджувальне планування
У цьому типі методу планування процесор виділяється певному процесу. Процес, який займає процесор, звільняє його шляхом перемикання контексту або завершення. Це єдиний метод, який можна використовувати на різних апаратних платформах, оскільки він не потребує спеціального обладнання (наприклад, таймера), як превентивне планування.
Коли планування є превентивним чи непревентивним?
Щоб визначити, чи є планування превентивним чи ні, враховуйте ці чотири параметри:
- Процес переходить із запущеного стану в стан очікування.
- Певний процес перемикається зі стану виконання у стан готовності.
- Певний процес переходить зі стану очікування у стан готовності.
- Процес завершує своє виконання та завершується.
Якщо застосовуються лише умови 1 та 4, планування називається невипереджувальним. Усі інші ситуації планування є випереджувальними.
Важлива термінологія планування процесора
- Час вибуху/час виконання: Час, необхідний процесу для завершення виконання. Його також називають часом виконання.
- Час прибуття: Момент, коли процес переходить у стан готовності.
- Час закінчення: Момент завершення процесу та його виходу з системи.
- Мультипрограмування: Декілька програм, які можуть бути присутніми в пам'яті одночасно.
- Вакансії: Тип програми, що не потребує жодної взаємодії з користувачем.
- Користувач: Різновид програми, яка передбачає взаємодію з користувачем.
- Процес: Посилання, яке використовується як для завдання, так і для користувача.
- Вибуховий цикл CPU/IO: Характеризує виконання процесу, яке чергується між активністю процесора та вводу/виводу. Час процесора зазвичай коротший, ніж час вводу/виводу.
Критерії планування ЦП
Алгоритм планування ЦП намагається максимізувати та мінімізувати наступне:
Максимізувати
Завантаження ЦП: Завантаження процесора – це головне завдання операційної системи, яке має забезпечити його максимальне завантаження. Воно може коливатися від 0 до 100 відсотків. Однак для RTOS воно може коливатися від 40 відсотків для низькорівневої системи до 90 відсотків для високорівневої системи.
Пропускна здатність: Кількість процесів, які завершують своє виконання за одиницю часу, називається пропускною здатністю. Отже, коли процесор зайнятий виконанням процесу, виконується робота, а робота, виконана за одиницю часу, називається пропускною здатністю.
Згорнути
Час очікування: Час очікування – це час, який певний процес повинен чекати в черзі готовності.
Час реакції: Це проміжок часу від моменту подання запиту до моменту отримання першої відповіді.
Час обороту: Час виконання – це час, необхідний для виконання певного процесу. Це загальний час, витрачений на очікування доступу до пам'яті, очікування в черзі та виконання на процесорі. Період між часом відправлення процесу та часом завершення називається часом виконання.
Таймер інтервалу
Переривання таймера - це метод, який тісно пов'язаний з випередженням. Коли певний процес отримує розподіл ЦП, таймер може бути встановлений на вказаний інтервал. І переривання таймера, і випередження змушують процес повертати ЦП до того, як завершиться його вибух ЦП.
Більшість багатопрограмних операційних систем використовують певний тип таймера, щоб запобігти назавждиму зависанню системи процесом.
Що таке диспетчер?
Диспетчер — це модуль, який забезпечує керування процесором для процесу. Диспетчер має бути швидким, щоб він міг запускатися при кожному перемиканні контексту. Затримка диспетчеризації — це час, необхідний планувальнику процесора для зупинки одного процесу та запуску іншого.
Функції, що виконуються диспетчером:
- Перемикання контексту.
- Перехід у режим користувача.
- Перехід до правильного розташування в щойно завантаженій програмі.
Типи планування ЦП Algorithms
В основному існує шість типів алгоритми планування процесів:
- Перший прийшов, перший подав (FCFS)
- Планування найкоротшої роботи спочатку (SJF).
- Найкоротший час, що залишився
- Пріоритетне планування
- Круговий розклад
- Багаторівневе планування черги
Планування Algorithms
Перший прийшов, перший обслужив
FCFS розшифровується як Перший прийшов, перший обслуживЦе найпростіший та найпростіший алгоритм планування процесора. У цьому типі алгоритму процес, який запитує процесор, першим отримує його розподіл. Цей метод планування можна керувати за допомогою черги FIFO.
Коли процес потрапляє до черги готовності, його плата керування процесом (PCB) пов'язується з хвостом черги. Тому, коли процесор звільняється, його слід призначити процесу на початку черги.
Характеристики методу FCFS
- Це алгоритм планування без випередження.
- Завдання завжди виконуються в порядку черги.
- Його легко реалізувати та використовувати.
- Однак цей метод має низьку ефективність, а загальний час очікування досить великий.
Найкоротший час, що залишився
Повна форма SRT – це найкоротший час, що залишився. Він також відомий як випереджальне планування SJF. У цьому методі процес буде виділено завданню, яке найближче до його завершення. Цей метод запобігає затримці завершення старішого процесу новим процесом у стані готовності.
Характеристики методу планування SRT
- Цей метод здебільшого застосовується в пакетних середовищах, де перевагу потрібно надавати коротким завданням.
- Це не ідеальний метод для реалізації в спільній системі, де необхідний процесорний час невідомий.
- Кожен процес пов'язаний з тривалістю наступного пакету обчислень процесора, тому операційна система використовує цю тривалість, щоб запланувати процес з найкоротшим можливим часом.
Планування на основі пріоритетів
Пріоритетне планування – це метод планування процесів на основі пріоритету. У цьому методі планувальник вибирає завдання для роботи відповідно до їхнього пріоритету.
Планування пріоритетів також допомагає ОС враховувати призначення пріоритетів. Процеси з вищим пріоритетом виконуються першими, тоді як завдання з рівними пріоритетами виконуються за циклічним принципом або за принципом FCFS. Пріоритет може бути визначений на основі вимог до пам'яті, вимог до часу та інших факторів.
Кругове планування
Круговий турнір є одним із найстаріших і найпростіших алгоритмів планування. Назва цього алгоритму походить від принципу циклічного розподілу, де кожна людина отримує рівну частку чогось по черзі. Він здебільшого використовується для планування в багатозадачних системах. Цей метод допомагає досягти виконання процесів без перевантаження.
Характеристики кругового планування
- Кругова система – це гібридна модель, яка керується годинником.
- Часовий інтервал, призначений для виконання конкретного завдання, має бути мінімальним. Однак він може відрізнятися для різних процесів.
- Він поводиться як система розподілу часу, яка реагує на кожен процес протягом певного часового ліміту.
Спочатку найкоротша робота
SJF (Shortest Job First - Найкоротша Завдання Перше) - це алгоритм планування, в якому процес з найкоротшим часом виконання вибирається для виконання наступним. Цей метод планування може бути випереджаючим або невипереджуючим. Він значно зменшує середній час очікування для інших процесів, що очікують на виконання.
Характеристики SJF Scheduling
- Кожне завдання пов'язане з одиницею часу, яку потрібно виконати.
- У цьому методі, коли процесор доступний, наступний процес або завдання з найкоротшим часом виконання виконується першим.
- Це реалізується з використанням політики непревентивного характеру.
- Цей алгоритм корисний для пакетної обробки, де очікування завершення завдань не є критичним.
- Це покращує продуктивність, виконуючи спочатку коротші завдання, які здебільшого мають коротший час виконання.
Багаторівневе планування черг
Цей алгоритм розділяє чергу готових процесів на кілька окремих черг. У цьому методі процеси призначаються до черги на основі певної властивості процесу, такої як пріоритет процесу, розмір пам'яті тощо.
Однак, це не незалежний алгоритм планування, оскільки для планування завдань йому потрібно використовувати інші типи алгоритмів.
Характеристики багаторівневого планування черг
- Для процесів зі спільними характеристиками слід підтримувати кілька черг.
- Кожна черга може мати свій власний окремий алгоритм планування.
- Кожній черзі призначаються пріоритети.
Мета алгоритму планування
Ось причини використання алгоритму планування:
- ЦП використовує планування для підвищення ефективності.
- Це допомагає розподілити ресурси між конкуруючими процесами.
- Максимального використання процесора можна досягти за допомогою мультипрограмування.
- Процеси, які мають бути виконані, зберігаються в черзі готовності.
