Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010

“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010




Сторінка14/24
Дата конвертації10.03.2017
Розмір1.41 Mb.
1   ...   10   11   12   13   14   15   16   17   ...   24

4. 4 Алгоритми планування


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

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


4. 4. 1 Планування за принципом FIFO


Розглянемр найпрстіший (“наївний”) невитісняльний алгоритм, у якому потоки ставлять на виконання у порядку їхньої появи в системі й виконують до переходу в стан очікування, явної передачі або завершення. Чергу готових потоків при цьому організовують за принципом FIFO, тому алгоритм називають алгоритмом FIFO.

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

У такого алгоритму багато недоліків:


  • він за визначенням є невитісняльним;

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

  • він підлягає ефекту конвою (convoy effect).

Уфект конвою можна пояснити такою ситуацією. Припустимо, що в системі є один потік (назвемо його Tcpu), обмежений можливостями процесора, і багато потоків Tio, обмежених можливостями введення-виведення. Рано чи пізно потік Tcpu отримає процесор у своє розпорядження і виконуватиме інструкції з довгим інтервалом використання процесора.
Розпоря́дження: Розпорядження (також право розпоряджання, лат. ius abutendi) - одна з правомочностей власника (нарівні з володінням і користуванням). Можливість визначати фактичну і юридичну долю речі.
За цей час інші потоки Tio завершать введення-виведення, пермістяться в чергу готових потоків і там чекатимуть, при цьому пристрої введення-виведення простоюватимуть. Коли Tcpu нарешті заблокують і відбудеться передача керування, всі потоки Tio швидко виконають інструкції своїх інтервалів використання процесора (у них, як ми знаємо, такі інтервали короткі) і знову перейдуть до введення-виведення. Після цього Tcpu знову захопить процесор на тривалий час і т д.

4. 4. 2 Кругове планування


Найпростішим для розуміння і найсправедливішим витісняльним алгоритмом є алгоритм кругового планування (round-robin scheduling). У середні віки терміном “round robin” називали петиції, де підписи йдуть по колу, щоб не можна було дізнатися, хто підписався першим (ця назва свідчить, що для такого алгоритму всі потоки рівні).
Розумі́ння - психологічний стан, який виражає собою правильність ухваленого рішення і супроводжуваний відчуттям упевненості в точності сприйняття або інтерпретації якої-небудь події, явища, факту.
Середньові́ччя - період європейської історії від 5 століття (падіння Римської імперії і Велике переселення народів) до епохи Відродження та Реформації, кінець 15 століття - початок 16 століття. За усталеною періодизацією раннє середньовіччя швидше відбулося у Західній Європі, аніж у Східній (близько 9-11 ст.).

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

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

Черга готових потоків

t

Потік, що виконується

t q

t 2*q


Рисунок 4.3. Кругове планування

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

Завдання надто короткого кванта часу приводить до того, що відбувається дуже багато перемикань контексту, і значний відсоток процесорного часу витрачається не на корисну роботу, а на ці перемикання. З іншого боку, завдання надто довгого кванта хоча й заощаджує процесорний час, але спричиняє до зниження часу відгуку на інтерактивні запити, бо якщо десять користувачів одночасно натиснуть клавішу, то десять потоків потраплять у список готових, в наслідок чого останній з них очікуватиме десять довгих квантів часу. У випадку з квантом нескінченної довжини кругове планування зводиться до алгоритму FIFO (усі потоки встигають заблокуватися або закінчитися до вичерпання кванта). На практиці рекомендують встановлювати довжину кванта в 10 – 100 мс.

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


4. 4. 3 Планування із приоритетами


Планування за принципом кругового чергування припускає, що всі потоки однаково важливі. В іншому разі необхідно застосовувати планування із пріоритетами.
Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.
Пріоритет (рос. приоритет, англ. priority, нім. Priorität f) -

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

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

Рішення про вибір потоку для виконання приймають таким чином:



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

  • якщо в черзі немає жодного потоку, переходять до черги потоків з нижчим пріоритетом іт. д.

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

Розподіл пріоритетів є складним завданням, невдале його розв’язання може призвести до того, що потоки процесів із низьким пріоритетом чекатимуть дуже довго. Наприклад, у 1973 році в Масачусетському технологічному інституті була зупинена машина, на якій знайшли процес із низьким пріоритетом – він був поставлений у чергу на виконання в 1967 році і з того часу так і не зміг запуститися.

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

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

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

4. 4. 4 планування на підставі характеристик подальшого виконання


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

Насамперед слід відзначити алгоритм “перший – із найкоротшим часом виконання” (Shortest Time to Completition First, STCF), коли з кожним потоком пов’язують тривалість наступного інтервалу використання ним процесора і для виконання щоразу вибирають той потік, у якого цей інтервал найкоротший. У результаті потоки, що захоплюють процесор на коротший час, отримують під час планування перевагу і швидше виходять із системи.

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

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

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

tn 1=aTn (1-a)tn, 0<a<1, t0=T0,

где tn 1 – оцінка довжини інтервалу;

tn – оцінка довжини попереднього інтервалу;

Tn – справжня довжина попереднього інтервалу.

Найчастіше використовують значення a=0,5, у цьому разі перерахування оцінки достатньо обчислити середнє між попередньою оцінкою і реальним значенням інтервалу.

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

Витісняльним аналогом STCF є алгоритм “перший – із найкоротшим часом виконання, що залишився” (Shortest Remainig time to completition first, SRTCF). Його відмінність від STCF полягає в тому, що, коли в чергу готових потоків додають новий , у якого наступний інтервал використання процесор коротший, ніж час, що залишився до завершення виконання поточного потоку, поточний потік переривається, і на його місце стає новий потік.


4. 4. 5 Багаторівневі черги зі зворотним зв’язком


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

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

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


  • потокам дозволено перехолити з рівня на рівень;

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

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

Потік не вичерпав кванта

Потік вичерпав квант

Потік давно не одержував керування

Черга алгоритму FIFO

Пріоритет

Рисунок 4. 4 Багаторівневі черги зі зворотним зв’язком

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


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

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



  • потік отримує жеяку кількість лотерейних квитків, кожен з яких дає право користуватися процесором упродовж часу T;
    Користува́ння - добування з речей їхніх корисних властивостей (наприклад, збирати врожай, вживати продукти харчування, носити одяг і взуття). Одна з трьох класичних правомочностей власника (нарівні з володінням і розпорядженням).


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

  • потік, що “виграв№, дістає керування до наступного розіграшу.

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

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

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

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

  • забезпечити розподіл процесоного часу між потоками – дати кожному потокові кількість квитків, пропорційну до частки процесорного часу, який потрібно йому виділити (наприклад, якщо є три потоки, і треба, щоб потік A займав 50% процесора, а потоки B і C – по 25%, можна дати потоку A два квитки, а потокам B і C – по одному);

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

Хоча більшість цих задач може бути розв’язана лотерейним плануванням лише приблизно, з деякою ймовірністю, на практиці отримують цілком задовільні результати. При цьому що довше працює система, то ближчими будуть результати до теоретичних значеь (за законом великих чисел). Насправді лотерейне планування використовує той факт, що вся ідеологія планування значною мірою є евристичною, оскільки не можна точно передбачити характер поведінки потоків у системі.
Більшість - велика частина чого-небудь, або кількісне переважання прихильників якоїсь ідеї чи рішення над їхніми противниками. Вважається найпершою засадою демократичного способу прийняття спільних рішень, головною й необхідною умовою обрання кандидата на виборну посаду.
Ймові́рність (лат. probabilitas, англ. probability) - числова характеристика можливості того, що випадкова подія відбудеться в умовах, які можуть бути відтворені необмежену кількість разів. Імовірність є основним поняттям розділу математики, що називається теорія імовірностей.
Планування - це заздалегідь намічений порядок дій, необхідних для досягнення поставленої цілі. Планування - оптимальний розподіл ресурсів для досягнення поставленої мети.
Ідеоло́гія (грец. ιδεολογία, від Ιδεα - прообраз, ідея, і λογος - слово, розум, вчення, буквально вчення про ідеї) - організована сукупність ідей у формі політичних міфів, настанов, гасел, програмних документів партій, філософських концепцій тощо.
Поведі́нка - родовий термін, який охоплює різні реакції живого організму чи групи організмів.

1   ...   10   11   12   13   14   15   16   17   ...   24



  • 4. 4. 1 Планування за принципом FIFO
  • 4. 4. 2 Кругове планування
  • 4. 4. 3 Планування із приоритетами
  • 4. 4. 4 планування на підставі характеристик подальшого виконання
  • 4. 4. 5 Багаторівневі черги зі зворотним зв’язком
  • 4. 4. 6 Лотерейне планування