Планування навантаження центрального процесора

Слід розрізняти механізми і політику планування. До механізмів планування належать засоби перемикання контексту, засоби синхронізації потоків тощо, до політики планування – засоби визначення моменту часу, коли необхідно перемкнути контекст. Ту частину системи, яка відповідає за політику планування, називають планувальником (англ. scheduler), а алгоритм, що використовують при цьому, - алгоритмом планування (англ. scheduling algorithm) .

Типи планувальників в операційних системах

Довготерміновий планувальник

Планувальник цього типу обирає роботу з підготовлених робіт, і завантажує її у пам’ять. Виконання переривається тільки тоді, коли процес залишає систему. Управління до певної міри мультипрограмне. У більшості сучасних систем розділення часу такий планувальник реально не існує.

Середньотермінове планування

У системах розділення часу, на відміну від довготермінового планування використовується для можливості  тимчасово видаляти процеси з пам’яті.

Короткотерміновий планувальник

Виконується швидко, біля сотні разів на секунду. Працює, коли:

• процес створюється або завершується;

• процес перемикається з виконання на блокування;  
• виникає переривання;
• процес обирається процес серед готових для виконання і виділяється CPU для цього процесу.

Цілі планування завантаження центрального процесора

Планувальник процесора мусить вирішувати, як довго процес має виконуватись та у якому порядку процеси будуть виконуватись.

Орієнтовані на користувача цілі політики планування:

• мінімізувати середній час реакції (час від отримання запиту до початку відповіді);
• мінімізувати час, коли максимальна кількість інтерактивних користувачів отримують адекватні відповіді;
• мінімізувати час обороту (час від старту процесу до завершення тобто час виконання плюс час чекання);
• мінімізувати варіацію середнього часу відповіді: прогнозованість є важливою;
• забезпечити, щоб процес завжди виконувався деяку кількість часу незалежно від завантаження системи.

Системно - орієнтовані цілі політики планування:

• максимізація пропускної здатності (кількості процесів, що закінчуються в одиницю часу);
• максимізація використання процесора (процент часу, протягом якого процесор зайнятий - CPU is busy);
• справедливість – у відсутності впливу користувача або ОС, процеси повинні оброблятись однаково, і ні один процес не повинен терпіти відмови від обслуговування (може бути зменшена справедливість у порядку мінімізації середнього часу відповіді!);
• баланс ресурсів – економія усіх ресурсів системи (CPU, memory, disk, I/O);
• сприяння процесам, що не завантажують напружених ресурсів.

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

Планувальник процесора обирає процес з черги готових і відсилає його на виконання у процесорі.  Для розробки алгоритмів роботи планувальника процесора прийняті наступні спрощуючі припущення про характер виконання процесів:

1. є тільки один процес на кожного користувача;
2. є тільки один потік управління на кожний процес;
3. процеси незалежні, і конкурують за ресурси (включаючи CPU);
4. процес виконується у пакетному циклі:
   • виконує деякий час обчислення у процесорі (CPU);
   • після цього виконує деякий ввід\вивід (I/O);
   • продовжує ці дві дії повторно.

Робиться також припущення, що є два типи процесів:

• стримувані процесором – великий об’єм обчислень і дуже малий ввід\вивід;
• стримувані вводом\виводом – великий ввід\вивід і дуже малі обчислення .

Алгоритм планування: Першим прийшов – першим обслуговується

Інші назви цього алгоритму планування: First-In-First-Out (FIFO), Run-UntilDone (виконується до закінчення) .

Політика: обирається процес з черги готових у порядку їх прибуття, і виконується цей процес non-preemptively (безперервно, без витіснення). Ранні FCFS планувальники були надмірно неперервними: процес не поступався процесором поки не закінчувався, навіть коли він виконував ввід\вивід. Зараз неперервність означає, що планувальник обирає інший процес тільки тоді, коли перший закінчується або блокується.

Дамо оцінку алгоритму FCFS. Цей алгоритм неперервний . Час відгуку – повільний, якщо є велика варіація у часі виконання процесів. Якщо один процес стоїть у черзі перед багатьма короткими процесами, він обирається для виконання, а короткі  процеси мають чекати довгий час. Завантаження CPU and I/O device низьке. Пропускній здатності – не надається значення. Не виконується принцип справедливості – у невигідному положенні короткі процеси та критичні до вводу\виводу процеси. Зависання – неможливе. Накладні витрати – мінімальні.

Алгоритм планування Round-Robin (карусель)

Політика:

1. встановлення фіксованого кванту часу;
2. обирання процесу з голови черги готових;  
3. виконання цього процесу протягом щонайбільше одного кванту часу, і якщо він не завершиться, додавання його у хвіст черги готових;  
4. якщо цей процес завершиться або заблокується до закінчення кванту часу, обрання іншого процесу з голови черги готових і виконання цього процесу протягом щонайбільше одного кванту часу .

Для впровадження алгоритму планування Round-Robin використовується апаратний таймер, що періодично видає переривання та FIFO черга готових;

Дамо оцінку алгоритму Round-Robin. Він перервний. Час відгуку – хороший для коротких процесів. Довгі процеси можуть мати чекання n* q одиниць часу до іншого кванту  часу, де: n = кількість інших процесів; q = величина кванту часу . Пропускна здатність – залежить від кванту часу:

• дуже малий квант – дуже багато перемикань контексту;  
• дуже великий квант – наближається до FCFS.

Справедливість неповна – у невигідному положенні критичні до вводу\виводу процеси (може не використати повний квант часу). Зависання – неможливе. Накладні витрати – низькі.

Алгоритм планування  «Найкоротша робота – першою»

Інша назва: Найкоротший процес – наступним (Shortest-Process-Next).

Політика: Обирається для виконання процес, що має найменший наступний пакет операцій у процесорі. Shortest-Job-First є приоритетним плануванням, де пріоритет змінюється пропорційно довжині наступного CPU burst.

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

Політика: З кожним процесом асоціюється пріоритет, який може бути зовнішньо визначений, основаним на значимості, грошах, політиці і т. п., або внутрішньо визначеним, основаним на вимогах до пам’яті, файлів, співвідношенні у потребах процесору та вводу\виводу. Обирається процес, що має найвищий пріоритет і виконується у процесорі одним з двох способів: перервно, або неперервно .  

Оцінка:

• зависання – можливе для низько пріоритетних процесів;
• можна ухилитись від старіння процесів: збільшувати пріоритет якщо вони марно витрачають час у системі.

Багаторівневі черги планування

Політика: Використовується кілька черг готових, і з різними чергами асоціюються різні пріоритети. Обирається процес, що зайняв чергу, що має найвищий пріоритет, і виконується у процесорі одним з двох способів: перервно, або неперервно. Новий процес завжди призначається до однієї з особливих черг: Foreground, background, System, interactive, editing, computing. Кожна черга може мати свою політику планування.

Багаторівневі черги планування з зворотнім зв’язком

Політика: Використовується кілька черг готових, і з різними чергами асоціюються різні пріоритети. Обирається процес, що має найвищий пріоритет і виконується у процесорі одним з двох способів: перервно, або неперервно. Кожна черга може мати свою політику планування. Планувальник може переміщати процеси між чергами. Стартує завжди процес з найбільш пріоритетної черги. Коли він закінчить свій CPU burst, він переміщається у чергу з нижчим пріоритетом; запобігання старінню – переміщення старіших процесів до черги з вищим пріоритетом. Зворотній зв’язок = використання минулого для передбачення майбутнього – сприяння роботам, які не використовували процесора .

Планування в середовищі JAVA

Середовище JAVA підтримує досить простий алгоритм планування. Цей алгоритм базується на пріоритеті Thread-ів (підпроцесів, потоків) відносно інших потоків. Планування, або встановлення пріоритетів, реалізується в JAVA за допомогою методу setPriority(). Цій метод встановлює пріоритет підпроцесу, який задається цілим значенням параметра, що передається методу.  В класі Thread є декілька пріоритетів-констант: MIN_PRIORITY, NORM_PRIORITY і MAX_PRIORITY.  Вони відповідають значенням відповідно 1, 5, 10. більшість користувацьких програм повинно виконуватись на рівні NORM_PRIORITY плюс-мінус 1. Пріоритет фонових завдань, наприклад, мережевого вводу-виведення треба встановлювати в MIN_PRIORITY. Запуск підпроцесів на рівні MAX_PRIORITY потребує обережності. Якщо в підпроцесах з таким рівнем пріоритету відсутні виклики sleep чи yield, середовище може перестати реагувати на зовнішні виклики .      

Виклик методу yield приводить до того, що система перемикає виконання підпроцесу на наступний підпроцес.      

При виклику методу sleep(int n) система блокує підпроцес, що виконується, на n мілісекунд.  

Як приклад наведемо програму з двома підпроцесами різного пріоритету, що не ведуть себе однаково на різних платформах. Пріоритет одного з підпроцесів з допомогою виклику setPriority встановлюється на два рівня вище від Thread.NORM_PRIORITY, тобто, того, що за замовченням. У другого підпроцесу встановлюється пріоритет на два рівня нижче. Підпроцеси запускаються і працюють протягом 10 секунд. Кожний виконує цикл, в якому збільшує значення лічильника. Через 10 секунд після запуску основний підпроцес зупиняє їх роботу, присвоює умові завершення цикла while значення true і виводить значення лічильників, показуючи, скільки ітерацій встиг виконати кожен з підпроцесів.

class Clicker implements Runnable {  
    int click = 0; 
    private Thread t; 
    private boolean running = true; 
    public clicker(int p) { 
        t = new Thread(this); 
        t.setPriority(p); 
    }  
    public void run() { 
        while (running) {  
            click++;  
        } 
    } 
    public void stop() { 
        running = false; 
    } 
    public void start() { 
        t.start(); 
    } 
} 
class HiLoPri { 
    public static void main(String args[]) { 
        Thread.currentThread().setPriority(Thread.MAX_PRIORITY); 
        clicker hi = new clicker(Thread.NORM_PRIORITY + 2); 
        clicker lo = new clicker(Thread.NORM_PRIORITY - 2); 
        lo.start(); 
        hi.start(); 
        try Thread.sleep(-10000) { }  catch (Exception e) { } 
        lo.stop(); 
        hi.stop(); 
        System.out.println(lo.click + " vs. " + hi.click);  
    } 
}

Виконаємо програму і переконаймося, що на виконання менш пріоритетного процесу йде на 25 відсотків менше часу.  C:\>java HiLoPri

304300 vs. 406666

Планування для мультипроцесорів зі спільною пам’яттю

У мультипроцесорних системах зі спільною пам’яттю для кожного процесора може підтримуватись локальна черга виконання модулів управління призначеними йому периферійними пристроями. Крім того у системі, як правило, є одна або декілька глобальних черг. Згідно з однією з можливих стратегій планування, коли звільняється черговий процесор, система спочатку переглядає його локальну чергу, і якщо в ній немає готових процесів, обирає процес з глобальних черг. Причому для множини процесів, що є складовими однієї паралельної програми, указується інформація для планування - кількість процесів, що можуть одночасно виконуватись, а також їх відносні пріоритети.  

Якщо планувальник просто призначає перший у черзі процес процесору, що звільнився, то ігнорується можливість того, що процес міг недавно виконуватись на певному процесорі і у кеші. Так, у випадку переривання по «відмові сторінки» (описаному у розділі про віртуальну пам’ять) виконання процесу, безумовно краще продовжити на тому ж процесорі. Для цього можна дозволити процесору «чекати у стані зайнятості». При цьому процес, що викликав переривання по «відмові сторінки», залишається призначеним процесору – його блокування та перемикання контексту не відбувається. Такий процес звичайно виконує пустий цикл в очікуванні переривання, що сповіщає про завершення «підкачки» сторінки.  

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

Розподілене планування

При плануванні у централізованих системах ресурсом, що розподіляється, є CPU, а споживачем ресурсу – процес. Метою планування є - приписати кожен процес до якогось періоду часу CPU. При плануванні у розподілених системах ресурсом є процесор / робоча станція а споживачем - обчислювальна задача . Мета планування - приписати кожну обчислювальну задачу певному процесору, розподілити задачі по множині процесорів, та таким чином оптимізувати деякі витрати. Розподіл навантаження це прийняття рішення, які процеси переміщати від одного процесора до іншого та коли це робити.

Перерозподіл навантаження може надати такі переваги:

• зменшення часу відгуку для процесів шляхом переміщення процесів до легко навантажених вузлів;
• прискорення індивідуальних робіт завдяки переходу процесів до більш швидких вузлів або розділення процесів;
• збільшення пропускної здатності за рахунок досягнення балансу системного навантаження, тобто змішування процесів, пов’язаних інтенсивним використанням CPU, та процесів з великим вводом/ виводом;
• підвищення ефективності  використання ресурсів, шляхом переміщення процесів до вузла, де зберігаються ресурси;
• зменшення трафіку у мережі за рахунок створення кластерів пов’язаних процесів на одному вузлі.

Джерела

1. Планування процесів і потоків [Електронний ресурс] – Режим доступу до ресурсу: http://studopedia.su/6_13666_obrobka-pererivan.html.

2. Планування систем [Електронний ресурс]. – 2016. – Режим доступу до ресурсу: http://www.studfiles.ru/preview/5485156/page:22/.

3. Дорошенко А. Ю. Архітектура і операційні середовища комп’ютерних систем / А. Ю. Дорошенко, В. М. Кислоокий, О. Л. Синявський. – Київ, 2005. – 220 с.

4. Дорошенко А.Е. Математические модели и методы организации высоко-производительных параллельных вычислений. - К.,"Наукова думка", 2000.- 177 с.

5. Дж.Вебер, Технология Java в подлиннике, BHV,СПб, 2000, 1104 с.

6. Системы параллельной обработки / под ред. Д. Ивенса // М.: Мир, 1985.- 415с.

7. В. Корнеев, Параллельные вычислительные системы.−М. Ноулидж. − 1999.

8. Дорошенко А. Ю. МЕТОДИЧНІ РЕКОМЕНДАЦІЇ до лабораторних занять з курсу «Системне програмування та операційні системи» / А. Ю. Дорошенко, В. М. Волохов. – Київ, 2009. – 42 с.

9.  Х.М. Дейтел, П.Дж. Дейтел, Д.Р. Чофнес. Операционные системы. Основы и принципы: Третье издание. Пер. с англ. – М.: ООО «Бином-Пресс», 2006 г. – 1024 с.:ил.

10. Немнюгин С.А. Стесик  О.Л. Параллельноге программирование для многопроцессорных вычислительных систем.–СПб:БХВПетербург, 2002.–400 с.