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

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

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

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

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

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

for each_task(p)

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

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

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

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

• 0 – у разі, коли процес вичерпав свій квант часу. Цей процес не буде вибраний для виконання. Крім випадку, коли він стоїть у черзі готових процесів першим, а всі інші процеси черги також вичерпали свій квант.

• Від 0 до 1000 – у разі, коли процес не вичерпав свого кванту часу. Це значення розраховують на основі значення базового кванта процесу і частини поточного кванта, що залишилася в нього. Спрощено це можна зобразити так:

c=p.counter+p.nice;

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

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

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

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

Перелічимо недоліки алгоритму.

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

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

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

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