Базові алгоритми обслуговування черг (стр. 3 из 3)

6. Максимінна схема рівномірного розподілу ресурсів

З метою забезпечення рівномірного обслуговування використовується максимінна схема рівномірного розподілу ресурсів (max-min fair-share allocation scheme). Основними її правилами є такі:

• ресурси розподіляються в порядку підвищення вимог;

• користувач не може отримати обсяг ресурсів, який перевищує його потреби;

• ресурси розподіляються рівномірно між користувачами з незадоволеними вимогами.

Розглянемо приклад. Припустимо, що загальний обсяг доступного ресурсу дорівнює 14 одиницям. Вимоги до ресурсу користувачів А, В, С, D та Е складають 2, 2, 3, 5 і 6 одиниць, відповідно. Розподіл ресурсу починається з джерела з найменшими вимогами, який одержує обсяг ресурсу, що дорівнює відношенню всього запасу ресурсу до загальної кількості користувачів. Отже, у розглянутому нами випадку користувачам А і В буде надано 14/5=2,8 одиниць ресурсу (рис. 6). Однак вимоги користувачів А і В складають усього лише 2 одиниці ресурсу. У цьому випадку надлишковий ресурс обсягом 1,6 одиниць (по 0,8 одиниць з кожного користувача) рівномірно розподіляється між трьома іншими користувачами. Отже, користувачі С, D та Е одержують по 2,8 + (1,6/3) = 3,33 одиниць ресурсу (рис. 7). Наступним за обсягом висунутих вимог до ресурсів є користувач С. Вимоги користувача С на 0,33 одиниці менше обсягу ресурсів, що йому пропонується. Надлишковий ресурс обсягом 0,33 одиниці рівномірно розподіляється між користувачами D і Е, кожний з яких одержує по 3,33 + (0,33/2)=3,5 одиниці ресурсу (рис. 8).

Рисунок 6 – Розподіл ресурсів для користувачів А і В

Рисунок 7 – Розподіл ресурсів для користувача С

Рисунок 8 – Розподіл ресурсів для користувачів D та E

У загальному випадку обсяг ресурсів, наданий

-му користувачеві, розраховується за формулою:

,

де

– сумарний запас ресурсів; – обсяг уже розподілених ресурсів;

– кількість користувачів, яким ще потрібні ресурси.

Як видно з рис. 6 – 8, вимоги користувачів А та В задовольняються в повному обсязі, тому що вони не перевищують значення, отриманого в результаті рівномірного розподілу ресурсів між усіма користувачами. На кроці 2 цілком задовольняються вимоги користувача С. А запити користувачів D і Е залишаються незадоволеними.

Зверніть увагу, що всі користувачі з незадоволеними вимогами (тобто з вимогами, обсяг яких перевищує їх максимінну рівномірну частку), одержують рівні обсяги ресурсів. Максимінна схема рівномірного розподілу ресурсів одержала свою назву в зв'язку з тим, що користувач з незадоволеними вимогами одержує максимум з можливих мінімальних рівномірних часток. Максимінна схема рівномірного розподілу ресурсів, у якій кожному користувачеві призначається певна вага, одержала назву зваженої максимінної схеми рівномірного розподілу ресурсів (weighted max-min fair-share allocation scheme). У відповідності до зваженої максимінної схеми рівномірного розподілу ресурсів кожному користувачеві надається рівномірна частка ресурсів, пропорційна до його ваги. Принцип максимінного рівномірного розподілу ресурсів було покладено в основу узагальненої схеми поділу процесорного часу (Generalized Processor Sharing, GPS). У відповідності зі схемою GPS кожен потік трафіка вміщується у власну логічну чергу, після чого нескінченно малий обсяг даних з кожної непорожньої черги обслуговується за круговим принципом. Необхідність обробки нескінченно малого обсягу даних на кожному колі обумовлена вимогою рівномірного обслуговування всіх непорожніх черг на будь-якому кінцевому часовому інтервалі. Отже, схема GPS є справедливою в будь-який момент часу.Якщо ж усім потокам трафіка призначити вагу, то обсяг даних потоку, який оброблюється за одне коло, буде пропорційний його вазі. Подібне розширення схеми GPS фактично є зваженою максимінною схемою рівномірного обслуговування. Незважаючи на те, що GPS є ідеальним втіленням максимінної схеми рівномірного розподілу ресурсів, цю модель не можна реалізувати на практиці. Це пов'язано з припущенням про нескінченно малий обсяг даних, що обслуговуються, кожного кола.

7. Алгоритм рівномірного обслуговування черг (FQ)

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

Одним з основних понять алгоритму FQ є поняття лічильника циклів (Round Number, RN), значення якого відповідає кількості виконаних циклів побайтового планувальника кругового обслуговування в заданий момент часу. Лічильник циклів безпосередньо визначає значення порядкового номера пакета.

З метою ілюстрації способу моделювання схеми GPS за допомогою алгоритму FQ розглянемо три потоки трафіка – А, В і С, розміри пакетів яких складають 128, 64 і 32 байт, відповідно. Пакети надходять один за іншим на завантажений FQ-сервер у порядку Al, A2, A3, Bl, C1. Першим на FQ-сервер надходить пакет А1, потім –пакет А2 і т.д.

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

Припустимо, що системою FQ був отриманий пакет А1, який належить пасивному потокові. Повна обробка 128-байтового пакета побайтовим планувальником кругового обслуговування потребує 128 циклів. Якщо на момент одержання пакета А1 значення лічильника циклів дорівнювало 100, то після повної передачі пакета А1 це значення складе 100+128=228. По суті, порядковий номер пакета є номером циклу, в якому здійснюється передача останнього байта пакета. Оскільки в дійсності планувальник за один раз реалізує передачу всього пакета, а не його одного байта, він обслуговує весь пакет незалежно від того, чи зрівнявся лічильник циклів з порядковим номером пакета (рис.9).

Коли система FQ отримає пакет А2, він уже належатиме активному потокові трафіка завдяки наявності в черзі пакета А1 з порядковим номером 228. Порядковий номер пакета А2 дорівнюватиме 228+128=356, оскільки його слід передати після пакета А1. Аналогічно, пакетові A3 призначається порядковий номер 356+128=484. Оскільки пакети В1 і С1 належать пасивним потокам трафіка, їхні порядкові номери дорівнюють 164=(100+64) і 132=(100+32), відповідно (рис. 9). З урахуванням обчислених порядкових номерів пакети будуть обслуговані в такій послідовності: С1,В1, А1, А2, А3.

Отже, порядковий номер (Sequence Number)

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

(1)

де

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

Лічильник циклів

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

Рисунок 9 – Приклад моделювання побайтового GPS-планувальника кругового обслуговування за допомогою алгоритму FQ

Слід зазначити, що лічильник циклів оновлюється при передачі кожного чергового пакета, при цьому його нове значення дорівнює порядковому номерові пакета, що передається. Отже, якщо 32-байтовый пакет D1, що належить новому потоку, буде прийнятий у момент передачі пакета А1, значення лічильника циклів дорівнюватиме 228, а порядковий номер пакета D1 – 260=(228+32). Оскільки порядковий номер пакета D1 менше порядкових номерів пакетів А2 і A3, він буде переданий раніше за цих пакетів. Зміна в порядку обслуговування пакетів схематично зображена на рис. 10.

Рисунок 10 – Зміна в порядку обслуговування пакетів, яка викликана надходженням пакета D1 у момент передачі пакета А1