69775

Реалізація планування в Linux

Лекция

Информатика, кибернетика и программирование

Ядро Linux при плануванні не розрізняє процеси і потоки тому для визначеності ми надалі говоритимемо про планування процесів. Планування процесів реального часу в ядрі Стосовно процесів реального часу достатньо сказати що: вони завжди матимуть під час планування пріоритет...

Украинкский

2014-10-10

55 KB

4 чел.

Тема 5. Реалізація планування в Linux.

У цьому розділі розглянемо два варіанти реалізації планування в Linux — традиційну (належить до ядер версій до 2.4 включно) і нову, включену в ядро версії 2.6.

Ядро Linux при плануванні не розрізняє процеси і потоки, тому для визначеності ми надалі говоритимемо про планування процесів.

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

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

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

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

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

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

Квант, який задають на початку епохи, називають базовим квантом часу процесу. Його значення можуть динамічно змінюватися системними викликами nісе() і setpriority(). Процес-нащадок завжди успадковує базовий квант свого предка.

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

Опишемо найважливіші поля структури даних процесу стосовно планування:

♦ роliсу — визначає, до якої групи відноситься процес (звичайні, реального часу з алгоритмом FIFO тощо);

  •  nice — задає величину, на якій ґрунтується базовий квант часу процесу (надалі для спрощення вважатимемо nice рівним базовому кванту, насправді це не зовсім так);

counter — містить кількість переривань таймера, що залишилися до вичерпання кванта часу процесу. На початку епохи counter надають значення базового кванта і зменшують його на одиницю в обробнику переривання таймера.

Умови виклику процедури планування

Розглянемо ситуації, коли відбувається виклик процедури планування (її називають schedule().

♦ Коли процес повинен бути заблокований через те, що потрібний йому ресурс у цей час недоступний. У цьому разі його керуючий блок спочатку додають у відповідну чергу очікування, а потім відбувається перепланування.

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

Процедура планування

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

Якщо жоден процес не був вибраний, поточний процес продовжує виконуватися. Коли ж вибір відбувся, контекст перемикають на новий процес.

Початок нової епохи

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

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

for_each_task (p)

p.counter = (p.counter / 2) + p.nice;

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

Розрахунок динамічного пріоритету

Тепер повернемося до обчислення динамічного пріоритету процесу. Для цього використовують функцію goodness О. Розглянемо можливі значення, які вона може повернути.

  •  0 — у разі, коли процес вичерпав свій квант часу. Цей процес не буде вибраний для виконання, крім випадку, коли він стоїть у черзі готових процесів першим, а всі інші процеси черги також вичерпали свій квант.
  •  Від 0 до 1000 — у разі, коли процес не вичерпав свого кванту часу. Це значення розраховують на основі значення базового кванта процесу й частини поточного кванта, що залишилася в нього. Спрощено це можна зобразити так: с - p.counter + p.nice;

де р — покажчик на керуючий блок процесу.

Звідси випливає, що більше часу залишилося процесу для виконання і що довший його базовий квант, то вищий його пріоритет. Крім того, це значення додатково збільшують на одиницю для процесів, які використовують ту саму пам'ять, що й предки (наприклад, якщо процес відображає потік, створений за допомогою функції clone()).

Перерахування кванта під час створення нового процесу

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

Вибір процесу для виконання відбувається внаслідок розрахунку динамічного пріоритету для всіх процесів у черзі готових процесів. Зі збільшенням кількості готових процесів у системі переглядати цю чергу від початку до кінця під час кожного виклику процедури планування стає невигідно.

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

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

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

5.3. Сучасні підходи до реалізації планування

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

Проте робота над виправленням недоліків тривала. Як наслідок, у ядро версії 2.6 була інтегрована нова реалізація алгоритму планування [97]. Розглянемо коротко, як вона допомагає розв'язувати названі раніше проблеми.

Насамперед, цей алгоритм підтримує окремі черги готових процесів для кожного процесора, забезпечуючи ефективну роботу за умов багатопроцесорності.

Ще одна проблема, яку має розв'язати новий алгоритм, пов'язана з необхідністю розраховувати у старому алгоритмі динамічний пріоритет для всіх готових процесів під час кожного виклику процедури планування. Рішення приймають таке: кожна черга готових процесів — це масив черг готових процесів, де елементи упорядковані за динамічним пріоритетом. У результаті під час вибору процесу для виконання достатньо продивитись чергу з найвищим пріоритетом до першого процесу, який можна запустити. Ця процедура не залежить від загальної кількості готових процесів у системі.

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

5.4. Програмний інтерфейс планування

У цьому розділі розглянемо системні виклики Linux, за допомогою яких можна працювати із базовим пріоритетом процесів (величиною nice) і цим впливати на їхнє планування.

Для зміни базового пріоритету процесу використовують виклик setpriority():

finclude <sys/resource.h>

int setpriority(int which, int who, int priority);

Зокрема, параметр which може набувати значення PRI0_PR0CESS або PRIOJJSER, відповідно показуючи, що параметр who буде інтерпретований як ідентифікатор процесу чи ідентифікатор користувача. У першому випадку задають пріоритет для конкретного процесу (або для поточного процесу, якщо who дорівнює нулю), у другому - для всіх процесів цього користувача.

Параметр priority задає новий пріоритет. Пріоритет може варіюватися в межах від -20 до 20, менші значення свідчать про вищий пріоритет. Значенням за замовчуванням є 0. Негативні значення priority можуть задавати лише користувачі з правами адміністратора.

Для отримання інформації про поточний базовий пріоритет використовують виклик getpriority():

int getprioritytint which,  int who);

Цей виклик повертає значення пріоритету, параметри which і who для нього мають той самий зміст, що й для функції setpriority(). Розглянемо приклад використання цих викликів:

// задати пріоритет для поточного процесу

setpriority(PRI0_PR0CESS. 0.  10);

.// довідатися про поточне значення пріоритету

printf ("поточний пріоритет; %d/п", getpriority(PRI0_PR0CESS,  0));

Для відносної зміни базового пріоритету поточного процесу можна також використати системний виклик пісе():

#include <unistd.h>

int nice(int inc);     // змінює пріоритет поточного процесу на іпс

Контрольні питання:

1. Реалізація планування в Linux.

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

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

4. Умови виклику процедури планування.

5. Процедура планування.

6. Сучасні підходи до реалізації планування.

7. Програмний інтерфейс планування.


 

А также другие работы, которые могут Вас заинтересовать

42174. ИССЛЕДОВАНИЕ ТЕХНОЛОГИИ ФОРМАТИРОВАНИЯ СЛОЖНЫХ ПО ФОРМАТУ ДОКУМЕНТОВ 654.5 KB
  Рукописные работы дипломные работы курсовые работы рефераты отчёты и пр. Основная часть рукописной работы Раздел 2 следует за титульным листом начинается со страницы № 2 обычно имеет оглавление. Заголовок 1 для глав работы Заголовок 2 для параграфов. Например для форматирования реквизитов Название организации Исполнитель Руководитель работ Название специальности Тема дипломной работы и пр.
42175. ИССЛЕДОВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПАРАЛЛЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО И ЕМКОСТНОГО СОПРОТИВЛЕНИЙ 203 KB
  Общие теоретические сведения В схеме рис.1 Векторная диаграмма этой схемы представлена на рис. Рис. Диаграмма представленная на рис.Ток совпадает по фазе с напряжением . Из точки О1 откладываем отрезок О1К = I2k /mI , по направлению вектора . Отрезок О1К является хордой круговой диаграммы . В масштабе mz откладываем по направлению отрезка О1К отрезок О1А = R2 /mz и из точки А под углом 900 к линии О1К проводим линию изменяющегося параметра AN’. Перпендикуляр, к линии изменяющегося параметра, опущенный из точки О1 совпадает по направлению с хордой.
42176. ИССЛЕДОВАНИЕ ЭЛЕКТРИЧЕСКОЙ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПАРАЛЛЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО, ИНДУКТИВНОГО И ЕМКОСТНОГО СОПРОТИВЛЕНИЙ. РЕЗОНАНС ТОКОВ 182.5 KB
  Общие теоретические сведения В схеме рис.1 Векторные диаграммы этой схемы при различных значениях емкости С представлена на рис.9 Рис. Если емкость C конденсатора подобрать так чтобы ток полностью компенсировал реактивную составляющую то общий ток будет совпадать по направлению с напряжением рис.
42177. Прилади і методи контролю метеорологічних умов на робочих місцях 99 KB
  Теоретичний вступ До показників які характеризують метеорологічні умови мікроклімат належать: температура відносна вологість швидкість руху повітря теплове випромінювання. Дійсну температуру повітря в робочій зоні визначають за формулою 1: де tч і t0 показники чорного та посрібленого термометрів 0С. Вимірювання температури повітря в приміщенні можна також проводити з допомогою сухого термометра аспіраційного психометра Ассмана. Вимірювання вологості повітря.
42178. Амбулаторно-поликлиническая помощь сельскому населению. Обзор. Состояние, проблемы и перспективы развития в Республике Беларусь 258 KB
  При этом в настоящее время существуют различны, иногда противоположные, мнения относительно действующей организационной модели сельского здравоохранения. Рядом автором она признается несовершеннолетней: недостаточная мощность организаций здравоохранения села рассматривается
42180. ИСПОЛЬЗОВАНИЕ ТЕХНОЛОГИИ «ПРИНЯТИЕ РЕШЕНИЙ» ПРИ РЕШЕНИИ ЗАДАЧ СРЕДСТВАМИ ТАБЛИЧНОГО ПРОЦЕССОРА 293 KB
  Найдите решения уравнения fx=0 с точность до 001 на отрезке [;b] используя опцию Подбор параметра. № варианта Функция fx Отрезок [;b] Шаг h fx = 3x52x4x36x2x4 [2;5] 05 fx = 3x5x36x2x4 [2;5] 05 fx = 2x56x4x3x2x4 [2;5] 05 fx = x39x224x15 [10;10] 05 fx = x23 x 2 [5;5] 05 fx = x36x29x6 [2;5] 05 fx = x36x29x2 [2;5] 05 fx = x39x224x2 [2;5] 05 fx = x33x26 [10;10] 05 fx = x312x245x51 [2;5] 05 fx= x26x8 [2;8] 05 fx =...
42181. ИССЛЕДОВАНИЕ ЭЛЕКТРИЧЕСКИХ ЦЕПЕЙ С ВЗАИМНОЙ ИНДУКТИВНОСТЬЮ 410 KB
  Исследовать свойства электрических цепей переменного тока с последовательным и параллельным соединением индуктивно связанных катушек. Коэффициент пропорциональности M21= называют взаимной индуктивностью катушек 2 и 1. Итак индуктивная связь катушек это связь их через магнитное поле когда магнитный поток одной катушки пронизывает не только витки собственной катушки но и витки другой находящейся поблизости катушки. Взаимная индуктивная связь катушек обусловливает...
42182. ИССЛЕДОВАНИЕ НЕСИММЕТРИЧНОГО ПАССИВНОГО ЧЕТЫРЕХПОЛЮСНИКА 222.5 KB
  Исследование линейного пассивного четырехполюсника при переменной нагрузке определение на основании опытных данных постоянных четырехполюсника А В С D и построение круговой диаграммы. Активные четырехполюсники в своих ветвях содержат источники энергии в пассивных четырехполюсниках источников энергии нет. Для любого пассивного четырехполюсника напряжение и ток на входе и выходе связаны между собой уравнениями:...