Завдання алгоритму планування

Щоб створити алгоритм планування, потрібно мати якесь уявлення про те, з чим повинен впоратися тлумачний алгоритм. Деякі завдання залежать від середовища оточення (пакетна, інтерактивна або реального часу), але є й такі завдання, які бажано виконати в будь-якому випадку. Ось деякі завдання алгоритму планування, яких слід дотримуватися при різних обставини, і які нам незабаром доведеться розглянути:

- Всі системи

Рівнодоступного ______________________________________________________________________

______________________________________________________________________________________________

Примушування до певної політиці —_________________________________________________________

______________________________________________________________________________________________

Баланс — ________________________________________________________________________________

Продуктивність — _________________________________________________________________________

Зворотній час-_____________________________________________________________________________

Використання центрального процесора — ___________________________________________________

- Интерактивні системы

Час відгуку — _________________________________________________________________________

Пропорційність — ____________________________________________________________________

- Системи реального часу

Дотримання граничних строків — __________________________________________________________

Передбачуваність — _______________________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________________

Найпростішим з усіх алгоритмів планування буде непріорітетним алгоритм, наступний принципом: «першим прийшов - першим обслужений». При використанні цього алгоритму центральний процесор виділяється процесам в порядку надходження їх запитів.

Сильною стороною цього алгоритму є простота його розуміння і така ж простота його програмування. Його справедливість схоже справедливості розподілу дефіцитних квитків на спортивні або концертні видовища тим людям, які зайняли чергу з другої години ночі. При використанні цього алгоритму відстеження готових процесів здійснюється за допомогою єдиного пов'язаного списку. Вибір наступного виконуваного процесу зводиться до ви ¬ потягу одного процесу з початку черги. Додавання нового завдання або розблокованого процесу зводиться до приєднання його до кінця черги. Що може бути простіше для сприйняття і реалізації?

На жаль, принцип «першим прийшов - першим обслужений» страждає також і суттєвими недоліками. Припустимо, що використовується один процес, обмежений швидкістю обчислень, який щоразу запускається на 1 с, і безліч процесів, обмежених швидкістю роботи пристроїв введення-виведення, незначно використовують час центрального процесора, але кожен повинен здійснити 1000 зчитувань з диску, перш ніж завершити свою роботу. Процес, обмежений швидкістю обчислень, працює протягом 1 с, а потім переходить до читання блоку даних з диска. Тепер запускаються всі процеси введення-виведення і приступають до читання даних з диска. Коли процес, обмежений швидкістю обчислень, отримує свій блок даних з диска, він запускається ще на 1 с, а за ним безперервною низкою слідують всі процеси, обмежені швидкістю роботи пристроїв введення-виведення.

В остаточному підсумку кожен процес,_______________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

Лекція№12

Планування в інтерактивних системах

Циклічне планування

Одним із самих старих, простих, справедливих і найбільш використовуваних залишається алгоритм циклічного планування. _____________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

 

Зрозуміло, якщо процес переходить в блокований стан або завершує свою роботу до закінчення кванта часу, то перемикання центрального процесора на інший процес відбувається саме в цей момент. Алгоритм циклічної планування не представляє складності в реалізації. На рис. 2.21, а показано, що від планувальника потрібно всього лише вести список процесів, готових до виконання. Коли процес вичерпає свій квант часу, він, як показано на рис. 2.21, б, поміщається в кінець списку.

 

 

Пріоритетне планування

Основна ідея: ___________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

Навіть якщо у персонального комп'ютера один власник, на ньому можуть виконуватися кілька процесів з різним ступенем важливості.

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

______________________________________________________________________________________________

На рис. 2.22 показана система з чотирма класами пріоритетності. Алгоритм планування виглядає наступним чином: якщо є готові до запуску процеси з класом пріоритетності 4, слід запустити кожен з них на один квант часу, за принципом планування, при цьому зовсім не турбуючись про класи з більш низьким пріоритетом. Коли клас з рівнем пріоритету 4 спорожніє, в циклічному режимі запускаються процеси з класом пріоритетності 3. Якщо спорожніють обидва класи, і 4 і 3, в циклічному режимі запускаються процеси з класом пріоритетності 2, і т. д.