Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання




НазваниеКонспект лекцій для студентів спеціальності ксм денної та заочної форми навчання
страница5/25
Дата25.11.2012
Размер1.39 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   ...   25

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


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
Розглянемо роботу дисципліни на прикладі, показаному на малюнку 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 - для другої).
1   2   3   4   5   6   7   8   9   ...   25

Похожие:

Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconКонспект лекцій для студентів IV курсу гуманітарного факультету спеціальності 030301 «Журналістика»
Конспект лекцій з дисципліни «Основи журналістикознавчих досліджень» для студентів IV курсу гуманітарного факультету спеціальності...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconКонспект лекцій для студентів спеціальностей 030508 І 030508 «Фінанси І кредит»
Менеджмент персоналу фінансових служб: Конспект лекцій для студентів спеціальностей 030508 І 030508 «Фінанси І кредит» денної та...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconНавчально-методичний комплекс для студентів денної та заочної форм навчання
Сторія міжнародних відносин. Навчально-методичний комплекс для студентів денної та заочної форми навчання / д.І. н проф. С. С. Троян....
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconВступ
Комп‘ютерні інформаційні технології в електроенергетиці (тексти лекцій для студентів 4 І 5 курсів денної І заочної форм навчання...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconКонспект лекцій з курсу «Економіка підприємств електротранспорту»
Економіка підприємств електротранспорту: Конспект лекцій для студентів 4-5 курсів денної І заочної форм навчання спеціальностей 092202...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconКонспект лекцій з курсу «психологія»
Конспект лекцій з курсу «Психологія» (для студентів 2 курсу денної форми навчання спец.: 092100 – «Промислове та цивільне будівництво»,...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання icon1. системный анализ под системным анализом понимают совокупность приёмов и методов для изучения сложных объектов, представляющих собой совокупность взаимодей-ствующих между собой элементов
Загальна теорія систем. Конспект лекцій Для студентів денної І заочної форм навчання спеціальності 080200 “Інформатика”/Укл.: Кац...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconКонспект лекцій з дисципліни «Економіка та управління знаннями»
Конспект лекцій з дисципліни «Економіка та управління знаннями» для студентів спеціальності 000014 «Управління інноваційною діяльністю»...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconПрограма навчальної дисципліни та робоча програма навчальної дисципліни «Планування та управління гіс проектами» (для студентів 5 курсу денної форми навчання спеціальності 070908 «Геоінфромаційні системи та технології»)
Програма навчальної дисципліни та робоча програма навчальної дисципліни «Основи землевпорядкування та кадастру» для студентів 5 курсу...
Конспект лекцій для студентів спеціальності ксм денної та заочної форми навчання iconКурсове проектування
Призначений для студентів молодших спеціалістів денної форми навчання спеціальності 05150103
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница