Алгоритм управління кількістю процесів в робочої суміші

СКЛАД АЛГОРИТМІВ ВНУТРІШНЬОГО ПЛАНУВАННЯ

Найважливішим фактором, що впливає на ефективність обчислювальних систем, є втрати часу на організа-

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

- Алгоритм управління кількістю процесів в робочій суміші;

- Алгоритм планування черговості вибору завдань для виконання їх на ЦП;

- Алгоритми вибору величини кванта часу, протягом якого процес, який отримав ЦП, може використовувати його.

Особливою функцією, покладеної на внутрішнє планування, є синхронізація паралельних процесів, проте-

кающих в системі.

АЛГОРИТМ УПРАВЛІННЯ КІЛЬКІСТЮ ПРОЦЕСІВ В РОБОЧОЇ СУМІШІ

Управління служить для підвищення продуктивності системи на основі раціонального використання апаратури

ЕОМ. Для режиму витісняючою мультизадачности кількість процесів, одночасно допускаються в систему, являє

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

дмуть позначення: qi - величина кванта процесорного часу, що відводиться i-м процесом; Ti - тривалість одного циклу

обробки для i-го процесу; Tз i, Tв i - тривалість переміщення i-го процесу з ОЗУ в ВЗП і назад при його витісненні і

відновленні; Tc i - витрати часу ОС на організацію роботи i-го процесу.

Тоді маємо: Т ц i = Т з i + T в i + qi + T c i,

Если T з i = T в i = T п; T c i = T c; qi = q, i = 1,..., N, то T = (2 T п + q + T c) N; N = T / (2 T п + q + T c)

Неважко розрахувати також ефективність завантаження центрального процесора на одному циклі для одного процесу: величина кванта час процесора - qi; непродуктивні витрати часу - Тн i = Тз i + Tп i + Tc i; показник завантаження процесора корисною роботою роботою

 

Збільшення кількості завдань, одночасно розв'язуваних системою, пов'язане зі збільшенням значення N

можна здійснити чотирма методами: 1)збільшенням загальної тривалості інтервалу циклу Т; 2)зменшенням витрат часу ОС на організацію мультипрограммирования Тс;3) зменшенням витрат часу на переміщення процесів з ОЗУ в ВЗП і назад при їх витіснення і відновленні Тз і Тв; 4)скороченням тривалості квантів часу, що відводяться для виконання процесів q.

Скорочення тривалості квантів часу qi, що відводяться для виконання процесів, автоматично викликає збіль-

чення тривалості перебування процесів у системі, через що цей спосіб має обмежене присування.

Найбільш продуктивними є методи, що призводять до скорочення витрат часу операційної системи Тс і, в

особливості, витрат часу на переміщення процесів з ОЗУ в ВЗП і назад при їх витіснення і відновленні.

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

 

АЛГОРИТМИ вибору чергової ОБРОБКИ

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

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

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

Рішення про порядок вибору процесів з черги здійснюється відповідно до реалізованими в ОС алгоритмами

планування черговості обробки. В даний час найбільш відомими є:

• алгоритм циклічної обробки;

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

• алгоритм вибору за характером використання попереднього кванта;

• алгоритм вибору з пріоритетом за характером блокування.

Практично всі алгоритми планування черговості обробки мають евристичний характер. Сигналом до початку

роботи цих алгоритмів служать зазначені вище події, що настали у системі:

• якщо попередній процес закінчився, то виконуються дії по його виведення з системи:

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

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

• якщо попередній процес вичерпав виділений йому квант часу, то він надходить в чергу готових процесів;

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

Логіка роботи всіх алгоритмів планування черговості обробки практично збігається. Розрізняються вони лише

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

Розглянемо алгоритми реалізації блоку "вибір чергового процесу".

Алгоритм циклічної обробки процесів не використовує жодної інформації про пріоритети оброблюваних

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

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

Алгоритм черг зі зворотним зв'язком організовує деяку кількість М черг, кожна з яких обслуговується в порядку надходження. Новий процес, що надійшов в систему, потрапляє в чергу № 1. Після закінчення використання чергового кванта часу процес переходить з черги з номером m в чергу з номером m + 1.

Алгоритм вибору за характером використання попереднього кванта розрізняє два типи стану готовності процесів: низькопріоритетною і високопріоритетною готовністю.

Якщо процес повністю використав попередній виділений квант часу ЦП, то йому присвоюється стан

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

АЛГОРИТМИ ВИБОРУ ВЕЛИЧИНИ КВАНТА

Вибір величини кванта є принципово необхідним у режимі поділу часу. Процедура квантування

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

поширеними є:

- Алгоритм рівномірного квантування;

- Алгоритм квантування по пріоритету процесу;

- Алгоритм мінімізації кількості перемикань між процесами.

Алгоритм рівномірного квантування - найпростіший із згаданих вище алгоритмів. Відповідно до цього алго-

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

собою. Алгоритм квантування по пріоритету процесу здійснює регулювання тривалості кванта qi для i-го про-

цесу залежно від його поточного пріоритету pi. Функціональна залежність qi = qi (pi) може мати будь допустимий вид і повинна мати такі основні характеристики: монотонність, позитивна визначеність, обмеженість. Алгоритм квантування з мінімізацією кількості перемикань полягає в тому, що активізується процес займає не тільки свій квант, але і залишки квантів процесів, які перейшли до цього моменту часу в стан сподіваня.

Засоби управління ресурсами

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

Основними функціями управління ресурсами є:

- Облік наявності та стану ресурсів;

- Прийом і облік заявок на ресурси від завдань і процесів;

- Розподіл ресурсів між завданнями та процесами;

- Організація використання ресурсів, виділених кожній задачі чи процесу;

- Повернення ресурсу в систему по мірі його звільнення споживачем.

Для реалізації функцій управління ресурсами в ОС формуються інформаційні таблиці, в яких відображаються

такі основні дані:

• для ресурсів:

- Облікова інформація про ресурс (ідентифікатор, клас, кількість каналів тощо);

- Код стану ресурсу;

- Ідентифікатор процесу-власника і т.п.;

• для заявок на ресурси:

- Ідентифікатор процесу-заявника;

- Пріоритет процесу;

- Ідентифікатор і необхідний обсяг ресурсу тощо

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

вільних ресурсів, зв'язку між ресурсами і процесами.

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

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

Системна тупикова ситуація, або ситуація "зависання" системи - це ситуація, коли один або більше процесів

опиняються в стані безвиході.

В операційних системах тупики виникають в більшості випадків як результат конкуренції процесів за облада-

ня монопольно використовуваними ресурсами (рис. 3.1).

Сформульовані наступні чотири необхідних умови наявності тупика:

1) процеси вимагають надання їм монопольного права керування ресурсом, які їм виділяються (умова

взаимоисключения);

2) процеси утримують за собою ресурси, вже виділені їм, очікуючи в той же час виділення додаткових ре-

сурсов (умова очікування ресурсів);

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

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

потрібних наступного процесу ланцюга (умова кругового очікування).

У проблемі тупиків виділяють наступні чотири основних напрямки: запобігання тупиків, обхід тупиків, виявлення тупиків, відновлення після тупиків.

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

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

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

 

Семафор

Семафор - це захищена змінна, значення якої можна опитувати і змінювати тільки за допомогою операції

ініціалізація_семафора та двох спеціальних операцій P і V:

• операція P над семафором S записується як P (S) і виконується за правилами:

якщо S> 0 то S: = S-1 інакше (очікувати на S);

• операція V над семафором S записується як V (S) і виконується за правилами:

якщо (один або більше процесів очікують на S) то (дозволити одному з процесів продовжити роботу) інакше S: = S +1.

Розрізняють два види семафорів: двійкові семафори, у яких S може приймати значення 0 і 1, і вважають семафори, де S може приймати невід'ємні цілі значення.

Подібно операції проверіть_і_установіть, операції ініціалізація_семафора, P (S) і V (S) є неподільними.

Ділянки взаимоисключения по семафору S обрамляются операціями P (S) і V (S). Якщо одночасно декілька процесів спробують виконати операцію P (S), то тільки одному з них буде дозволено це зробити, а іншим доведеться чекати.

Семафори і операції над ними можуть бути реалізовані як програмно (рис. 3.5), так і апаратно. при програмноїреалізації вони розміщуються в тій частині ядра операційної системи, де здійснюється управління зміною станів процесів.
Узагальнююче засіб синхронізації процесів запропонував Дейкстра, який ввів два нових примітиву. В абстрактній формі ці примітиви, що позначаються P і V, оперують над цілими невід'ємними змінними, званими семафорами. Нехай S такий семафор. Операції визначаються наступним чином:
V (S): мінлива S збільшується на 1 одним неподільним дією; вибірка, інкремент та запам'ятовування не можуть бути перервані, і до S немає доступу іншим процесам під час виконання цієї операції.
P (S): зменшення S на 1, якщо це можливо. Якщо S = 0, то неможливо зменшити S і залишитися в області цілих невід'ємних значень, в цьому випадку процес, що викликає P-операцію, чекає, поки це зменшення стане можливим. Успішна перевірка і зменшення також є неподільною операцією.

Рис. 2.5. Реалізація критичної секції з використанням системних функцій WAIT (D) і POST (D)
В окремому випадку, коли семафор S може приймати тільки значення 0 і 1, він перетворюється на блокуючу змінну. Операція P містить в собі потенційну можливість переходу процесу, який її виконує, в стан очікування, в той час як V-операція може за деяких обставин активізувати інший процес, призупинений операцією P (порівняйте ці операції з системними функціями WAIT і POST).
Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один з яких пише дані в буферний пул, а інший зчитує їх з буферного пула. Нехай буферний пул складається з N буферів, кожний з яких може містити один запис. Процес "письменник" повинен припинятися, коли всі буфери опиняються зайнятими, і активізуватися при звільненні хоча б одного буфера. Навпаки, процес "читач" припиняється, коли всі буфери порожні, і активізується при появі хоч би одного запису.
Введемо два семафора: e - число порожніх буферів і f - число заповнених буферів. Припустимо, що запис у буфер і зчитування з буфера є критичними секціями (як у прикладі з принт-сервером на початку цього розділу). Введемо також двійковий семафор b, який використовується для забезпечення взаємного виключення. Тоді процеси можуть бути описані в такий спосіб:
/ / Глобальні змінні
# Define N 256
int e = N, f = 0, b = 1;
void Writer ()
while (1)
PrepareNextRecord (); / * підготовка нового запису * /
P (e) / * Зменшити число вільних буферів, якщо вони є * /
/ * У противному випадку - чекати, поки вони звільняться * /
P (b) / * Вхід в критичну секцію * /
AddToBuffer (); / * Додати новий запис у буфер * /
V (b) / * Вихід з критичної секції * /
V (f) / * Збільшити число зайнятих буферів * /
void Reader ()
while (1)
P (f) / * Зменшити число зайнятих буферів, якщо вони є * /
/ * У противному разі чекати, поки вони з'являться * /
P (b) / * Вхід в критичну секцію * /
GetFromBuffer (); / * Взяти запис з буфера * /
V (b) / * Вихід з критичної секції * /
V (e) / * Збільшити число вільних буферів * /
ProcessRecord (); / * Опрацювати запис * /
Тупики
Наведений вище приклад допоможе нам проілюструвати ще одну проблему синхронізації - взаємні блокування, звані також дедлок (deadlocks), клінчами (clinch) або тупиками. Якщо переставити місцями операції P (e) і P (b) у програмі "письменника", то при деякому збігу обставин ці два процеси можуть взаємно заблокувати один одного. Дійсно, нехай "письменник" першим увійде в критичну секцію та виявить відсутність вільних буферів; він почне чекати, коли "читач" візьме чергову запис з буфера, але "читач" не зможе цього зробити, тому що для цього необхідно увійти в критичну секцію, вхід до якої заблоковано процесом "письменником".
Розглянемо ще один приклад глухого кута. Нехай двох процесів, що виконується в режимі мультипрограмування, для виконання їхньої роботи потрібно два ресурси, наприклад, принтер і диск. На малюнку 2.6, а показані фрагменти відповідних програм. І нехай після того, як процес А зайняв принтер (встановив блокує змінну), він був перерваний. Управління отримав процес В, який спочатку зайняв диск, але при виконанні наступної команди був заблокований, так як принтер виявився вже зайнятим процесом А. Управління знову отримав процес А, який у відповідності зі своєю програмою зробив спробу зайняти диск і був заблокований: диск вже розподілено процесу В. У такому положенні процеси А і В можуть знаходитися як завгодно довго.
У залежності від співвідношення швидкостей процесів, вони можуть або цілком незалежно використовувати колективні ресурси (г), або утворювати черги до ресурсів (в), або взаємно блокувати один одного (б). Тупикові ситуації треба відрізняти від простих черг, хоча і ті й інші виникають при спільному використанні ресурсів і зовні виглядають схоже: процес призупиняється і чекає звільнення ресурсу. Однак чергу - це нормальне явище, невід'ємною ознакою високого коефіцієнта використання ресурсів при випадковому надходженні запитів. Вона виникає тоді, коли ресурс недоступний в даний момент, але через деякий час він звільняється, і процес продовжує своє виконання. Тупик ж, що видно з його назви, є до певної міри нерозв'язною ситуацією.
У розглянутих прикладах глухий кут був утворений двома процесами, але взаємно блокувати один одного можуть і більше число процесів.
Проблема тупиків включає в себе наступні завдання:
- Запобігання тупиків,
- Розпізнавання тупиків,
- Відновлення системи після тупиків.

Рис. 2.6. (A) фрагменти програм А і В, які поділяють принтер і диск; (б) взаємне блокування (клінч); (в) чергу до разделяемому диску; (г) незалежне використання ресурсів
Тупики можуть бути запобігти на стадії написання програм, тобто програми повинні бути написані таким чином, щоб глухий кут не міг виникнути ні при якому співвідношенні взаємних швидкостей процесів. Так, якщо б у попередньому прикладі процес А і процес У запитували ресурси в однаковій послідовності, то глухий кут був би в принципі неможливий. Другий підхід до запобігання тупиків називається динамічним і полягає у використанні певних правил при призначенні ресурсів процесам, наприклад, ресурси можуть виділятися в певній послідовності, загальною для всіх процесів.
У деяких випадках, коли тупикова ситуація утворена багатьма процесами, що використовують багато ресурсів, розпізнавання глухого кута є нетривіальним завданням. Існують формальні, програмно-реалізовані методи розпізнавання тупиків, засновані на веденні таблиць розподілу ресурсів і таблиць запитів до зайнятих ресурсів. Аналіз цих таблиць дозволяє виявити взаємні блокування.
Якщо ж тупикова ситуація виникла, то не обов'язково знімати з виконання всі заблоковані процеси. Можна зняти тільки частину з них, при цьому звільняються ресурси, очікувані іншими процесами, можна повернути деякі процеси в область свопінгу, можна зробити "відкат" деяких процесів до так званої контрольної точки, в якій запам'ятовується вся інформація, необхідна для відновлення виконання програми з даного місця. Контрольні точки розставляються в програмі в місцях, після яких можливе виникнення безвиході.
З усього вищесказаного ясно, що використовувати семафори потрібно дуже обережно, тому що одна незначна помилка може призвести до зупинки системи. Для того, щоб полегшити написання коректних програм, було запропоновано високорівневий засіб синхронізації, зване монітором. Монітор - це набір процедур, змінних і структур даних. Процеси можуть викликати процедури монітора, але не мають доступу до внутрішніх даних монітора. Монітори мають важливе властивість, яка робить їх корисними для досягнення взаємного виключення: тільки один процес може бути активним по відношенню до монітора. Компілятор обробляє виклики процедур монітора особливим чином. Зазвичай, коли процес викликає процедуру монітора, то перші кілька інструкцій цієї процедури перевіряють, не активний може який-небудь інший процес по відношенню до цього монітора. Якщо так, то зухвалий процес припиняється, поки інший процес не звільнить монітор. Таким чином, виключення входу декількох процесів в монітор реалізується не програмістом, а компілятором, що робить помилки менш імовірними.

МОНІТОРИ

Монітор - це механізм організації паралелізму, який містить як дані, так і процедури, необхідні для

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

Щоб забезпечити виділення потрібного йому ресурсу, процес повинен звернутися до конкретної процедури монітора.Необхідність входу в монітор в різні моменти часу може виникати у багатьох процесів. Однак вхід до монітору знаходиться під жорстким контролем: тут здійснюється взаємовиключає процесів, так що в кожен момент часу тільки одному процесу дозволяється увійти в монітор. Процесам, які хочуть увійти в монітор, коли він зайнятий,доводиться чекати, причому режимом очікування автоматично керує сам монітор.Якщо процес звертається до деякої процедурі монітора і виявляється, що відповідний ресурс вже зайнятий, то ця процедура монітора видає процесу команду WAIT (ЧЕКАТИ). Процес, який отримав таку команду, переводиться в режим очікування поза монітора.З часом процес, який займав потрібний ресурс, звільняє його, звертаючись для цього до монітора. Відповідна процедура монітора може просто прийняти повідомлення про повернення ресурсу, а потім чекати, поки не надійде запит від іншого процесу, якому буде потрібно цей ресурс. Однак може виявитися, що вже є процеси, які очікують звільнення даного ресурсу. У цьому випадку монітор виконує примітив оповіщення SIGNAL, щоб один з очікуючих процесів міг зайняти даний ресурс і покинути чергу до монітора. Якщо процес сигналізує про звільнення ресурсу і в цей час немає процесів, що очікують цей ресурс, то подібне сповіщення не викликає ніяких інших дій, крім того, що монітор знову вносить ресурс в список вільних.

 

Вступні зауваження

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

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

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

Існують також комбіновані способи формування запитів на ресурси з попереднім замовленням в пакеті

завдань або в програмі і виконавчим запитом під час виконання програми.

 

АЛГОРИТМИ ОБХОДУ Тупиків

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

алгоритм Хаберман, званий алгоритмом регульованого розподілу.

Алгоритм регульованого розподілу заснований на представленні розподілу ресурсів, запитів і процесів у вигляді орієнтованого графа (орграфа), званого графом розподілу ресурсів (ГРР).

Правило Хаберман: Якщо граф розподілу ресурсів має цикли, то такий розподіл ресурсів по процесах

може призвести до утворення тупикової ситуації.

Це правило дозволяє побудувати наступний алгоритм розподілу ресурсів:

• при вступі чергового запиту перевірити наявність вільного ресурсу;

• якщо вільний ресурс відсутній, то відмова, процес блокувати, інакше зробити попередній розподіл і

скорегувати ГРР;

• перевірити ГРР на наявність циклів;

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

 

Керування файлами

Організація файлів

Фізична організація файлів залежить від фізичних характеристик зовнішнього пристрою. Існують зовнішні устройства, які можна розглядати як послідовні файли, де обмін записами доступний тільки в лінійному порядку. До них відносяться накопичувачі на магнітних стрічках, стримери, принтери, модеми і т.п. У порівнянні з ними назбиратели на магнітних дисках допускають величезну гнучкість організації файлів. На поверхні дискової пластини розміщено серія концентричних кіл, які називаються доріжками або циліндрами диска. Кожна доріжка підрозділяється на сектори. Сектор - це мінімальний обсяг інформації, зазвичай передається в дискової системі.

Фізичні записи можуть розташовуватися в будь-якому місці диска. З міркувань ефективності при пошуку і передачі даних робляться всілякі спроби розташувати пов'язані фізичні записи в суміжних секторах або на сусідніх пластинах тієї ж доріжки диска.

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

Послідовна організація файлу передбачає створення на диску послідовного файлу.

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

У послідовних файлах розміщують набори даних з послідовною організацією. Зазвичай в послідовних файлах використовують один покажчик від одного блоку до іншого (рис. 5.8). Іноді для прискорення доступу застосовують подвійні посилання.

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

1) один фізичний блок під одну логічну запис;

2) кілька фізичних блоків під одну логічну запис;

3) один фізичний блок під декілька логічних записів.

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

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

Безперервна організація файлу передбачає створення на диску безперервного файлу.

Безперервний файл - файл на носії, що з низки фізичних блоків, які все розташовані в одній

суцільний області дискового простору.

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

Доступ до записів безперервного файлу досить простий. Якщо позначити через r - номер запису, l - довжину запису і L

- Довжину блоку, то номер b блоку, де знаходиться запис, обчислюється за формулою

b = l r / L.

Значення b використовується потім для зчитування потрібного блоку в первинну пам'ять. Оскільки не потрібно проходити по вказівниками, як у першому випадку, то досягається суттєве скорочення витрат часу на доступ до даних.Оновлення запису r скоюється дуже просто - вона просто перекривається новими даними. При цьому відбувається звернення до потрібного кількістю фізичних блоків. Для безперервного файлу мають місце ті ж три випадки розміщення логічних записів у фізичних блоках, що і для послідовного файлу. Включення нового запису в безперервний файл дуже складно. Для цього системі, в середньому, необхідно перемістити половину записів довжиною l, перш ніж звільнити місце для нового запису. Включення нового запису в

безперервний файл може закінчитися невдачею, якщо при зсуві записів остання запис буде пересунуто за кордон файлу.

Сегментована організація файлу припускає створення сегментированного файлу.

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

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

Індекс будується як безліч блоків покажчиків сегментів (БУС) і може бути організований послідовним або безперервним способами. При безперервному підході максимальний розмір файлу вважається відомим (наприклад, один дисковий том) та відповідно з цим виділяється необхідна кількість індексних блоків. У разі послідовного підходу розмір файлу не обмежується. Проте пошук по послідовному індексом ставить ті ж проблеми, що і при пошуку в послідовному файлі. Кожен БУС в індексному файлі містить n елементів або покажчиків на блоки даних

і, можливо, покажчик на наступний індексний блок. Покажчик на дисковий блок повинен мати розмір, достатній для подання всього діапазону адрес на пристрої пам'яті.

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

СКЛАД АЛГОРИТМІВ ВНУТРІШНЬОГО ПЛАНУВАННЯ

Найважливішим фактором, що впливає на ефективність обчислювальних систем, є втрати часу на організа-

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

- Алгоритм управління кількістю процесів в робочій суміші;

- Алгоритм планування черговості вибору завдань для виконання їх на ЦП;

- Алгоритми вибору величини кванта часу, протягом якого процес, який отримав ЦП, може використовувати його.

Особливою функцією, покладеної на внутрішнє планування, є синхронізація паралельних процесів, проте-

кающих в системі.

АЛГОРИТМ УПРАВЛІННЯ КІЛЬКІСТЮ ПРОЦЕСІВ В РОБОЧОЇ СУМІШІ

Управління служить для підвищення продуктивності системи на основі раціонального використання апаратури

ЕОМ. Для режиму витісняючою мультизадачности кількість процесів, одночасно допускаються в систему, являє

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

дмуть позначення: qi - величина кванта процесорного часу, що відводиться i-м процесом; Ti - тривалість одного циклу

обробки для i-го процесу; Tз i, Tв i - тривалість переміщення i-го процесу з ОЗУ в ВЗП і назад при його витісненні і

відновленні; Tc i - витрати часу ОС на організацію роботи i-го процесу.

Тоді маємо: Т ц i = Т з i + T в i + qi + T c i,

Если T з i = T в i = T п; T c i = T c; qi = q, i = 1,..., N, то T = (2 T п + q + T c) N; N = T / (2 T п + q + T c)

Неважко розрахувати також ефективність завантаження центрального процесора на одному циклі для одного процесу: величина кванта час процесора - qi; непродуктивні витрати часу - Тн i = Тз i + Tп i + Tc i; показник завантаження процесора корисною роботою роботою

 

Збільшення кількості завдань, одночасно розв'язуваних системою, пов'язане зі збільшенням значення N

можна здійснити чотирма методами: 1)збільшенням загальної тривалості інтервалу циклу Т; 2)зменшенням витрат часу ОС на організацію мультипрограммирования Тс;3) зменшенням витрат часу на переміщення процесів з ОЗУ в ВЗП і назад при їх витіснення і відновленні Тз і Тв; 4)скороченням тривалості квантів часу, що відводяться для виконання процесів q.

Скорочення тривалості квантів часу qi, що відводяться для виконання процесів, автоматично викликає збіль-

чення тривалості перебування процесів у системі, через що цей спосіб має обмежене присування.

Найбільш продуктивними є методи, що призводять до скорочення витрат часу операційної системи Тс і, в

особливості, витрат часу на переміщення процесів з ОЗУ в ВЗП і назад при їх витіснення і відновленні.

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