Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Дисципліни планування - вимоги, показники, класифікація

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

  • виконання процесу завершилося;
  • процес запитав виконання операції, що вимагає очікування якого-небудь іншого ресурсу;
  • виконання перерване системою.
Ріс.2.1. Представлення планування процесів у вигляді системи масового обслуговування

Перші два випадки з погляду системи масового обслуговування однакові: у будь-якому випадку процес виходить з даної системи. Якщо процес не завершився, то після отримання запитаного ресурсу процес знов поступить у вхідну чергу. У разі переривання процесу за ініціативою системи перерваний (витиснений) процес поступає у вхідну чергу відразу ж. Порядок обслуговування вхідної черги, черговість вибору з неї заявок на обслуговування і складає дисципліну або стратегію планування. Методи теорії масового обслуговування застосовуються для аналітичного моделювання процесу планування, хоча формальному аналізу піддаються тільки прості дисципліни (див., наприклад [12]).

Для оцінки ефективності функціонування даної системи масового обслуговування можуть бути застосовані кількісні показники. Позначимо через t - процесорний час, необхідне процесу для виконання. Ми його називатимемо тривалістю процесу. Позначимо через T - загальний час перебування процесу в системі. Цю величину - інтервал між моментом введення процесу в систему і моментом отримання результатів - також називають іноді часом реакції процесу. Разом з часом реакції, можуть бути корисні також і інші показники.

Втрачений час:

M = T - t;

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

Відношення реактивності:

R = t / T;

показує частку процесорного часу (часу виконання) в загальному часі реакції.

Штрафне відношення:

P = T / t;

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

Середні значення величин T, M, R, P і можуть служити кількісними показниками ефективності. Реальні системи, як правило, орієнтовані на конкретні характеристики процесів, зокрема, на певні діапазони значень t, тому вказані показники зручно розглядати як функції тривалості процесу: T(t), M(t), R(t), P(t).

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

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

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

Базові дисципліни планування

FCFS (first come - first serve - першим прийшов - першим обслуговується) - проста дисципліна, робота якої зрозуміла з її назви. Це дисципліна без витіснення, тобто, процес, вибраний для виконання на ЦП, не уривається, поки не завершиться (або не перейде в стан очікування за власною ініціативою). Як дисципліна без витіснення, FCFS забезпечує мінімум накладних витрат. Середній втрачений час при застосуванні цієї дисципліни не залежить від тривалості процесу, але штрафне відношення при рівному втраченому часі буде великим для коротких процесів. Тому дисципліна FCFS вважається кращою для довгих процесів. Істотною гідністю цієї дисципліни, разом з її простотою, є та обставина, що FCFS гарантує відсутність нескінченного відкладання процесів: будь-який процес, що поступив в систему, врешті-решт буде виконаний незалежно від ступеня завантаження системи.

На малюнку 2.2 показаний приклад планування по дисципліні FCFS для трьох процесів - A, B і C. На тимчасовій діаграмі кожен прямокутник представляє інтервал часу, протягом якого процес знаходиться в системі. Над верхнім лівим кутом такого прямокутника вказаний ідентифікатор процесу, а в дужках - його тривалість. Незатемнені ділянки відповідають активному стану процесу, затемнені - стану очікування. Процес A поступає у момент часу 0 і вимагає для виконання 6 одиниць процесорного часу. ЦП у цей момент вільний, і процес A відразу ж активізується. У момент часу 2 поступає процес B, що вимагає 11 одиниць. Оскільки ЦП зайнятий процесом A, процес B чекає в черзі готових процесів до моменту 6, коли процес A закінчиться і звільнить ЦП. Тільки після цього процес B починає виконуватися. Поки процес B виконується, поступають ще два процеси: C - у момент часу 8 і D - у момент 10, які чекають завершення процесу B. Коли процес B завершиться, ЦП буде відданий процесу C, що поступив раніше, а процес D залишається в очікуванні. У лінійці, розташованій під тимчасовою шкалою, вказані ідентифікатори процесів, активних в даний момент часу. Читач може сам визначити показники ефективності планування - для кожного процесу і усереднені. Слідує, проте, попередити, що до усереднених показників треба відноситися з обережністю, оскільки достовірними можуть вважатися тільки результати, отримані на статистично значущій вибірці.

Ріс.2.2. Планування процесів по дисципліні FCFS

RR (round robin - карусель) - проста дисципліна з витісненням. Процес отримує в своє розпорядження ЦП на деякий квант часу Q (у простому випадку розмір кванта фіксований). Якщо за час Q процес не завершився, він витісняється з ЦП і прямує в кінець черги готових процесів, де чекає виділення йому наступного кванта, і так далі Показники ефективності RR істотно залежать від вибору величини кванта Q. RR забезпечує якнайкращі показники, якщо тривалість більшості процесів наближається до розміру кванта, але не перевершує його. Тоді більшість процесів укладаються в один квант і не стають в чергу повторно. При величині кванта, прагнучій до нескінченності, RR вироджується в FCFS. При Q, прагнучому до 0, накладні витрати на перемикання процесів зростають настільки, що поглинають весь ресурс ЦП. RR забезпечує якнайкращі показники справедливості: штрафне відношення P на великій ділянці тривалості процесів t залишається практично постійним. Тільки на ділянці t < Q штрафне відношення починає змінюватися і при зменшенні t від Q до 0 зростає експоненціально. Втрачений же час M істотно росте із збільшенням тривалості процесу.

На малюнку 2.3 показані приклади планування по дисципліні RR з різними величинами кванта Q=1 (рис.2.3.а) і Q=4 (рис.2.3.б). Розглянемо докладніше роботу на початковій тимчасовій ділянці рис.2.3.а. Процес A поступає у момент часу 0 і отримує квант часу ЦП. До моменту закінчення кванта в черзі вже є процес B. Процес A відправляється в чергу, а наступний квант отримує процес B. У момент часу 2 процес B прямує в чергу, а з черги вибирається процес A. У цей же момент поступає новий процес - C. Цей процес ставиться в кінець черги, а першим в черзі коштує процес A, тому наступний квант віддається процесу A і так далі Надаємо читачеві самостійно закінчити розгляд цього прикладу, а також прикладу, показаного на мал. 2.3.б.

Ріс.2.3. Планування процесів по дисципліні RR

SJN (shortest job next - найкоротша робота - наступна) - невитісняюча дисципліна, в якій найвищий пріоритет має найкоротший процес. Для того, щоб застосовувати цю дисципліну, повинна бути відома тривалість процесу - задаватися користувачем або обчислюватися методом екстраполяції. Для коротких процесів SJN забезпечує кращі показники, чим RR, як по втраченому часу, так і по штрафному відношенню. SJN забезпечує максимальну пропускну спроможність системи - виконання максимального числа процесів в одиницю часу, але показники для довгих процесів значно гірші, а при високому ступені завантаження системи активізація довгих процесів може відкладатися до безкінечності. Штрафне відношення слабо змінюється на основному інтервалі значень t, але значно зростає для найкоротших процесів: такий процес під час вступу до системи має найвищий пріоритет, але вимушений чекати, поки закінчиться поточний активний процес.

Приклад планування по цій дисципліні показаний на малюнку 2.4. Що поступив у момент часу 0 процес A захоплює ЦП. Процес B, що поступив у момент 1, вимушений чекати звільнення ЦП процесом A, хоча процес B і коротший. До моменту 6 - звільнення ЦП - з двох наявних в черзі процесів (B і C) вибирається коротший процес B. Процес C отримує ЦП тільки у момент часу 9, коли закінчується процес B. Коли у момент часу 16 процес C звільняє ЦП, з двох наявних в черзі процесів вибирається коротший процес E, хоча він поступив пізніше, ніж процес D.

Ріс.2.4. Планування процесів по дисципліні SPN

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

Розглянемо приклад, представлений на малюнку 2.5. Процес A поступає в систему першим і встигає використовувати одиницю часу ЦП перш, ніж в систему приходить процес B. Процес B вимагає 3 одиниці процесорного часу, а процесу A залишилося використовувати ще 5 одиниць. Процес A витісняється, ЦП віддається процесу B. При звільненні ЦП в черзі вже є і процес C, але його тривалість більша, ніж залишок часу процесу A, тому процес C отримує ЦП тільки у момент часу 9, коли процес A завершиться. Процес C встигає використовувати тільки одну одиницю часу ЦП, коли приходить короткий процес E і витісняє процес C з ЦП. Виконання C знов відкладається до звільнення ЦП, яке відбувається у момент 14. У момент 17 приходить процес D. Його тривалість (6) менша, ніж повна тривалість процесу C (7), але до цього часу процес C вже використав 4 одиниці часу ЦП, і для завершення йому необхідно ще тільки 4 одиниці, тому процес D не витісняє процес C.

Ріс.2.5. Планування процесів по дисципліні PSPN

HPRN (highest penalty ratio next - з найбільшим штрафним відношенням - наступний) - дисципліна без витіснення, що забезпечує якнайкращі показники справедливості. Це досягається за рахунок динамічного перевизначення пріоритетів. Всякий раз при звільненні ЦП для всіх готових процесів обчислюється поточне штрафне відношення:

p[i]=(w[i]+t[i]) / t[i]

де i - номер процесу; w[i] - час, витрачений процесом на очікування; t[i] - тривалість процесу - передзадана або прогнозована. Для процесу p[i], що тільки що поступив=1. ЦП віддається процесу, що має найбільше значення p[i]. Для коротких процесів HPRN забезпечує приблизно ті ж показники справедливості, що і SJN, для довгих - ближчі до FCFS. На великому діапазоні середньої тривалості процесів показники, забезпечувані HPRN, представляють середнє між SJN і FCFS і слабо залежать від тривалості. Ще одна гідність HPRN - в тому, що в часі очікування може враховуватися (з деякими ваговими коефіцієнтами) і очікування в інших чергах і, таким чином, виконується більш комплексний облік завантаження системи. Істотним недоліком методу є необхідність перевычисления штрафного відношення для всіх процесів при кожному перемиканні, що погано узгоджується із загальною політикою мінімізації накладних витрат в дисциплінах без витіснення.

У прикладі, показаному на малюнку 2.6, під тимчасовою шкалою дані поточні значення штрафного відношення для процесів-претендентів в ті моменти часу, коли виконується перемикання. Так, у момент часу 6 два процеси - B і C - претендують на використання ЦП. Поточне штрафне відношення для процесу B складає:

p[B]=(5+3)/3=2.33

а для процесу C:

p[C]=(3+7)/7=1.43;

отже, ЦП віддається процесу B. Аналогічні обчислення проводяться в моменти часу 9 і 16.

Ріс.2.6. Планування процесів по дисципліні HPRN

SRR (selfish RR - егоїстичний RR) - метод з витісненням, що дає додаткові переваги виконуваним процесам, що дозволяє підвищити пропускну спроможність. Всі процеси розділяються на дві категорії - нові і вибрані. Новими вважаються ті процеси, які не отримали ще жодного кванта часу ЦП, решта всіх процесів - вибрані. Під час вступу до системи кожному процесу дається деякий пріоритет P0, однаковий для всіх процесів, який надалі зростає. В кінці кожного кванта часу перераховуються пріоритети всіх процесів, причому пріоритети нових процесів зростають на величину dA, а вибраних - на величину dB. ЦП віддається процесу з найвищим пріоритетом, а при рівності пріоритетів - тому, який раніше поставлений в чергу. Показники дисципліни істотно залежать від вибраного співвідношення між dA і dB. При dB/dA=1 дисципліна вироджується в звичайну RR, при dB >> dA - в FCFS. Власне дисципліна SRR забезпечується в діапазоні значень 0<dB/dA<1.

Розглянемо роботу дисципліни на прикладі, показаному на малюнку 2.7. Параметри дисципліни в даному прикладі:

P0=0; dA=2; dB=1; Q=1.

Ріс.2.7. Планування процесів по дисципліні SRR

Під тимчасовою шкалою тут показані поточні значення пріоритетів процесів. Процес A під час вступу отримує пріоритет 0. Оскільки на цей момент інших процесів немає, процес A починає виконуватися. Отримавши ЦП, процес A потрапляє в категорію вибраних, тому при закінченні кванта у момент 1 пріоритет процесу A зростає на 1. У момент 1 поступає процес B, йому привласнюється початковий пріоритет 0, на даний момент це нижче, ніж пріоритет A, тому ЦП залишається у процесу A. Після ще одного кванта, до моменту часи 2 пріоритет процесу A збільшується ще на 1 і стає рівним 2, але пріоритет процесу B, як нового, збільшується на 2 і стає рівним пріоритету A. За принципом RR ЦП віддається процесу B, як довше чекаючому. Процес B тепер також стає вибраним і надалі його пріоритет росте повільніше. Новий процес C, що поступає пізніше, має нульовий початковий пріоритет і вимушений чекати 3 кванти, поки їх пріоритет не порівняється з пріоритетами вибраних процесів. Аналогічним чином відбувається обслуговування і решти процесів, що поступають.

FB (foreground-background - передний-задний плани) - черга готових процесів розщеплюється на дві підчерги - черга переднього плану і черга заднього плану. Черги обслуговуються по дисципліні RR, але чергу переднього плану має абсолютний пріоритет: поки в ній є процеси, черга заднього плану не обслуговується. Новий процес прямує в чергу переднього плану. Якщо процес використовував встановлене число N квантів в черзі переднього плану, але не завершився, він переводиться в чергу заднього плану.

Узагальнення дисципліни FB на n черг з номерами 0, 1..., n-1 і з абсолютними пріоритетами, що убувають при зростанні номера черги, носить назву MLFB (multiply level feed back - багаторівневі черги із зворотним зв'язком). Розщеплювання черги готових процесів на дві і більш за підчергу забезпечує селекцію процесів по тривалості - довші процеси потрапляють в черзі з великими номерами і, відповідно, з меншими пріоритетами. Дисципліна MLFB дуже ефективна для систем, що працюють в інтерактивному режимі.

На малюнку 2.8 показані приклади роботи MLFB для N=1. Під тимчасовою шкалою показані стани процесів в кожен момент часу: "а" - для активного процесу і номер черги - для неактивного. Процес A поступає в чергу 0 і, оскільки ЦП вільний, відразу ж вибирається з неї на виконання. Після використання одного кванта часу ЦП процес A переводиться в чергу 1. У цей момент (момент 1) в чергу 0 поступає процес B. Оскільки черга 0 має вищий пріоритет, ніж черга 1, на виконання вибирається процес B. Процес B після використання кванта (момент 2) потрапляє також в чергу 1. Оскільки у момент часу 2 черга 0 порожня, обслуговується черга 1, з неї вибирається процес A, який був поставлений в цю чергу раніше, ніж процес B. Після цього кванта (момент 3) процес A переходить в чергу 2, а в черзі 0 з'являється новий процес C, якому і буде відданий наступний квант. Після цього кванта (момент 4) процес C буде направлений в чергу 1. На цей момент часу ми маємо 3 процеси: процес A в черзі 2, процес B в черзі 1 і процес C в черзі 1. Обслуговується черга 1, процес B потрапив в цю чергу раніше, він отримує наступний квант і так далі

Ріс.2.8. Планування процесів по дисципліні MLFB

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

  • разом з переважним обслуговуванням високопріоритетної черги надавати (але з меншою частотою) кванти часу і чергам з низькими пріоритетами;
  • виконувати зворотне переміщення процесу в чергу з меншим номером після того, як процес прочекав встановлений інтервал часу в низькопріоритетній черзі;
  • встановити розмір кванта залежним від номера черги, наприклад: Q[n]=q*n або Q[n]=q*2n; оскільки в черзі з великими номерами потрапляють довші процеси, їх обслуговування з великим квантом дозволить заощадити витрати на перемикання;
  • обслуговувати різні черги по різних дисциплінах (наприклад: RR - для першої черги, FCFS - для другої).



Поделиться с друзьями:


Дата добавления: 2014-12-23; Просмотров: 1672; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.031 сек.