Лотерейне планування.

Багаторівневі черги зі зворотним зв'язком

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

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

Відмінності між двома алгоритмами полягають у тому, що:

♦ потокам дозволено переходити з рівня на рівень (із черги в чергу);

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

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

Лотерейне планування (lottery scheduling) - це останній алгоритм, який ми розглянемо. Він простий для розуміння і легкий у реалізації, разом з тим має великі можливості.

Ідея лотерейного планування полягає у тому, що:

♦ потік отримує деяку кількість лотерейних квитків, кожен з яких дає право користуватися процесором упродовж часу Т;

♦ планувальник через проміжок часу Т вибирає випадково один лотерейний квиток;

♦ потік, «що виграв», дістає керування до наступного розіграшу.

Лотерейне планування дає змогу:

♦ емулювати кругове планування, видавши кожному потокові однакову кількість квитків;

♦ емулювати планування із пріоритетами, розподіляючи квитки відповідно до пріоритетів потоків;

♦ емулювати SRTCF - давати коротким потокам більше квитків, ніж довгим (якщо потік отримав хоча б один квиток, він не голодуватиме);

♦ забезпечити розподіл процесорного часу між потоками - дати кожному потокові кількість квитків, пропорційну до частки процесорного часу, який потрібно йому виділити (наприклад, якщо є три потоки, і треба, щоб потік А займав 50 % процесора, а потоки В і С — по 25 %, можна дати потоку А два квитки, а потокам В і С — по одному);

♦ динамічно міняти пріоритети, відбираючи і додаючи квитки по ходу.

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Подальшого виконання	\|	Умови виклику процедури планування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.