Відмінності між версіями «Тема 12. Реалізація планування в Linux.»

Версія за 11:05, 24 квітня 2013

Планування процесів реального часу в ядрі.

Стосовно процесів реального часу, достатньо сказати, що:

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

Традиційний алгоритм планування.

Розглянемо алгоритм планування звичайних процесів. В основі алгоритму лежить розподіл процесорного часу на епохи (epochs). Упродовж епохи кожен процес має квант часу, довжину якого розраховують у момент початку епохи. Здебільшого різні процеси мають кванти різної довжини. Коли процес вичерпав свій квант, його витісняють і протягом поточної епохи він більше не виконувати­меться. Керування передають іншому процесові. Якщо ж процес був призупинений для виконання введення-виведення або внаслідок синхронізації, його квант не вважають вичерпаним і він може бути вибраний планувальником упродовж поточної епохи. Епоха закінчується, коли всі готові до виконання процеси вичер­пали свої кванти. У цьому разі алгоритм планування перераховує кванти для всіх процесів і розпочинає нову епоху.

Квант, який задають на початку епохи, називають базовим квантом часу проце­су. Його значення можуть динамічно змінюватися системними викликами PC і setpriorityO. Процес-нащадок завжди успадковує базовий квант свого предка. Пріоритет процесу буває двох видів:
• фіксований, для процесів реального часу, що задають тільки під час створення процесe;
• динамічний, для звичайних про­цесів, який залежить від базового пріоритету і часу, що залишився до вичерпання кванта.

Динамічний пріоритет будь-якого звичайного процесу завжди нижчий за будь-який пріоритет процесу реального часу.
Опишемо найважливіші поля структури даних процесу стосовно планування:
• policy — визначає, до якої групи відноситься процес (звичайні, реального часу з алгоритмом FIFO тощо);
• nice — задає величину, на якій ґрунтується базовий квант часу процесу (надалі для спрощення вважатимемо nice рівним базовому кванту, насправді це не зовсім так);
• counter — містить кількість переривань таймера, що залишилися до вичерпан­ня кванта часу процесу. На початку епохи counter надають значення базового кванта і зменшують його на одиницю в обробнику переривання таймера.

Умови виклику процедури планування
Розглянемо ситуації, коли відбувається виклик процедури планування (її назива­ють schedule()).
• Коли процес повинен бути заблокований через те, що потрібний йому ресурсу цей час недоступний. У цьому разі його керуючий блок спочатку додають у відповідну чергу очікування, а потім відбувається перепланування.
• За допомогою відкладеного запуску (lazy invocation). Відкладений запуск поля­гає в тому, що у певний момент часу спеціальному полю need_resched структури процесу надають значення 1. Це відбувається в таких випадках: коли поточний процес вичерпав свій квант; коли у стан готовності переходить процес, пріори­тет якого вищий, ніж у поточного; коли процес явно поступається своїм правом виконання через відповідний системний виклик. При цьому негайного перепла­нування не відбувається, але пізніше, коли цей процес повинен знову отримати керування після переривання, він перевіряє, чи не дорівнює поле needresched одиниці. Якщо рівність виконується, запускають процедуру планування.

Процедура планування
Ця процедура спочатку перевіряє, чи не переходить поточний процес у стан очі­кування, і якщо це так, вилучає його з черги готових процесів. Потім вибирається процес для виконання. Для цього проглядають чергу готових процесів, для кож­ного процесу оцінюють динамічний пріоритет і вибирають процес із максимальним його значенням. Алгоритм оцінки цього пріоритету описаний нижче. Для проце­су, що вичерпав свій квант часу, він дорівнюватиме нулю.
Якщо жоден процес не був вибраний, поточний процес продовжує виконува­тися. Коли ж вибір відбувся, контекст перемикають на новий процес.

Початок нової епохи
Особлива ситуація виникає тоді, коли для всіх процесів у черзі готових процесів значення динамічного пріоритету дорівнює нулю, тобто всі вони вичерпали свій квант і настав час починати нову епоху. Проте це не означає, що система взагалі не має процесів, для яких квант не вичерпаний, — вони можуть перебувати в чер­гах очікування (найчастіше це процеси, обмежені введенням-виведенням). Коли розпочинається нова епоха, відбувається перерахування квантів для всіх процесів системи (не тільки для процесів у стані готовності). При цьому довжину кванта для кожного процесу задають рівною сумі його базового пріоритету і по­ловини частини кванта, що залишилася в нього:
for_each_task (р)
p.counter = (p.counter / 2) + p.nice;
Оскільки до початку нової епохи ненульовий квант залишається тільки у про­цесів, які не перебувають у стані готовності, цей алгоритм надає певну перевагу процесам, обмеженим можливостями введення-виведення. При цьому значення кванта для процесу ніколи не зможе стати більшим, ніж подвоєне значення його базового пріоритету.

Розрахунок динамічного пріоритету
Тепер повернемося до обчислення динамічного пріоритету процесу. Для цього використовують функцію goodness О. Розглянемо можливі значення, які вона мо­же повернути.
• 0- у разі, коли процес вичерпав свій квант часу. Цей процес не буде вибра­ний для виконання, крім випадку, коли він стоїть у черзі готових процесів першим, а всі інші процеси черги також вичерпали свій квант.
• Від 0 до 1000 — у разі, коли процес не вичерпав свого кванту часу. Це значен­ня розраховують на основі значення базового кванта процесу й частини по­точного кванта, що залишилася в нього. Спрощено це можна зобразити так:
с = p.counter + p.пі се:
де р — покажчик на керуючий блок процесу.
Звідси випливає, що більше часу залишилося процесу для виконання і що довший його базовий квант, то вищий його пріоритет. Крім того, це значення до­датково збільшують на одиницю для процесів, які використовують ту саму па­м'ять, що й предки (наприклад, якщо процес відображає потік, створений за допо­могою функції cloneO).

Перерахування кванта під час створення нового процесу
Тепер розглянемо, що відбувається під час створення нового процесу. Найпрості­ше рішення (копіювати значення counter у структуру даних нащадка) може при­звести до того, що процеси будуть штучно подовжувати свій квант створенням нових нащадків, виконуючих той самий код. Для того щоб цьому перешкодити, після функції forkO значення counter розділяють навпіл: одна половина перехо­дить нащадкові, інша залишається предкові.
Перелічимо недоліки алгоритму.
• Вибір процесу для виконання відбувається внаслідок розрахунку динамічно­го пріоритету для всіх процесів у черзі готових процесів. Зі збільшенням кіль­кості готових процесів у системі переглядати цю чергу від початку до кінця під час кожного виклику процедури планування стає невигідно.
• Якщо кількість процесів буде дуже великою, перерахування всіх динамічних пріоритетів на початку нової епохи може виконуватися досить довго. З іншо­го боку, епохи змінюються рідше, що більше в системі процесів.
• Алгоритм розрахований на зменшення часу відгуку для процесів, обмежених можливостями введення-виведення, навіть якщо вони не є інтерактивними (наприклад, фоновий процес індексації пошукової системи) і не потребують малого часу відгуку.
• Зі збільшенням кількості процесорів підтримувати загальні черги, які не вра­ховують наявність різних процесорів, стає невигідно.