Принцип забезпечення безпеки обчислень.

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

Забезпечення захисту інформації від несанкціонованого доступу є обов'язковою функцією мережевих операційних систем. В багатьох сучасних ОС гарантується ступінь безпеки даних, що відповідає рівню С2 в системі стандартів США. Основи стандартів в області безпеки були закладені в документі “Критерії оцінки надійності комп'ютерних систем”. Цей документ, виданий Національним центром комп'ютерної безпеки (NCSC-National Computer Security Center) в США в 1983р., часто називають Оранжевою книгою. У відповідності до вимог Оранжевої книги безпечною вважається система, яка “за допомогою спеціальних механізмів захисту контролює доступ до інформації таким чином, що лише особи, які мають відповідні повноваження або процеси, що виконуються від їх імені, можуть отримати доступ на читання, запис, створення або знищення інформації”.

Ієрархія рівнів безпеки, наведена в Оранжевій книзі, помічує найнижчий рівень безпеки, як D, а найвищий – як А.

В клас D попадають системи, оцінка яких виявила їх невідповідність вимогам всіх інших класів.

Основними властивостями, характерними для систем класу С, є наявність підсистеми обліку подій, зв'язаних з безпекою, і вибірковий контроль доступу. Клас (рівень) С ділиться на два підрівні: рівень С1 забезпечує захист даних від помилок користувачів, але не від дій зловмисників; і більш суворий рівень С2.

На рівні С2 мають бути присутні:

1. засоби секретного входу що забезпечує ідентифікацію користувачів шляхом вводу унікального імені і пароля перед тим, як їм буде дозволений доступ до системи;

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

3. засоби обліку і спостереження (auditing), що забезпечують можливість виявити і зафіксувати важливі події, пов'язані з безпекою, або будь-які спроби створити, отримати доступ або видалити системні ресурси ОС;

4. Захист пам'яті, який полягає в тому, що пам'ять ініціалізується перед тим, як повторно використовується.

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

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

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

Різні комерційні структури (наприклад, банки) особливо виділяють необхідність облікової служби, аналогічної тій, що рекомендують державні рекомендації С2. Будь-яка діяльність, що пов'язана з безпекою, може бути відслідкована і тим самим облікована. Це як раз те, що вимагає стандарт С2 і те, що потрібно банкам. Але комерційні користувачі не хочуть розплачуватися продуктивністю за підвищений рівень безпеки.

А – рівень безпеки займає своїми керуючими механізмами до 90% процесорного часу, що в більшості випадків неприйнятно. Більш безпечні системи не тільки знижають ефективність, а і суттєво обмежують число всіх доступних прикладних пакетів, які відповідним чином можуть виконуватися в подібній системі. Наприклад, для ОС Solaris(версія UNIX) є декілька тисяч додатків, а для її аналогу В–рівня – тільки близько 100.

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

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

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

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

Ріс.2.1. Представлення планування процесів у вигляді системи масового обслуговування

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

Для оцінки ефективності функціонування даної системи масового обслуговування можуть бути застосовані кількісні показники. Позначимо через 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*2ⁿ; оскільки в черзі з великими номерами потрапляють довші процеси, їх обслуговування з великим квантом дозволить заощадити витрати на перемикання;
• обслуговувати різні черги по різних дисциплінах (наприклад: RR - для першої черги, FCFS - для другої).