• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Бюджетне планування.
2. Бюджетне фінансове планування.
3. Етапи планування.
4. Етапи процесу планування.
5. Етапи процесу планування.
6. Етапи процесу планування.
7. Інформаційна база фінансового планування.
8. Кадрове планування.
9. Класифікація видів та методів податкового планування.
10. Макроекономічне індикативне планування.
11. Методи планування.

Переглядів: 1825