Теорія операційних систем

Введення. Основні поняття і визначення.

Операційна система - це програма, яка виконує функціїпосередника між користувачем і комп'ютером.

ОС, виконуючи роль посередника, служить двом цілям:
1. ефективно використовувати комп'ютерні ресурси.
2. створювати умови для ефективної роботи користувача

Як ресурсів комп'ютера зазвичай розглядають:
1. час роботи процесора
2. адресний простір основної пам'яті

1. обладнання введення - виведення
2. файли, що зберігаються в зовнішній пам'яті

На малюнку наведені основні компоненти ОС як системи поділуресурсів.

Таким чином, основні компоненти ОС:
1. управління процесами (розподіляє ресурс - процесорний час);
2. управління пам'яттю (розподіляє ресурс - адресний простір основної пам'яті);
3. керування пристроями (розподіляє ресурси) - обладнання вводу - виводу;
4. управління даними (розподіляє ресурс - дані або файли).

Функціонування комп'ютера після вмикання живлення починається ззапуску програми первісного завантаження - Boot Track. Програма Boot
Track ініціалізує основні апаратні блоки комп'ютера й регістрипроцесора (CPU), накопичувач пам'яті, контролери периферійногообладнання. Потім завантажується ядро ОС, чи то пак Operating System Kernel.
Подальше функціонування ОС здійснюється як реакція на події,що відбуваються в комп'ютері. Наступ тієї чи іншої подіїсигналізується переривань - Interrupt. Джерелами переривань можуть бутияк апаратура (HardWare), так і програми (SoftWare).

Апаратура "повідомляє" про переривання асинхронно (в будь-який моментчасу) шляхом пересилання в CPU через загальну шину сигналів переривань.
Програма "повідомляє" про переривання шляхом виконання операції System Call.
Приклади подій, що викликають переривання:
1. спроба ділення на 0
2. запит на системне обслуговування
3. завершення операції введення - виведення
4. неправильне звернення до пам'яті

Кожне переривання обробляється відповідно обробникомпереривань (Interrupt handler), що входять до складу ОС.

Головні функції механізму переривань - це:
1. розпізнавання або класифікація переривань
2. передача управління відповідно до обробникові переривань
3. коректне повернення до перерваної програмі

Перехід від переривається програми до обробникові і назад повиненвиконуватися як можна швидше. Одним із швидких методів євикористання таблиці, що містить перелік усіх допустимих для комп'ютерапереривань і адреси відповідних обробників. Така таблиця називаєтьсявектором переривань (Interrupt vector) і зберігається на початку адресногопростору основної пам'яті (UNIX/MS DOS).

Для коректного повернення до перерваної програмі перед передачеюуправління обробникові переривань, вміст регістрів процесоразапам'ятовується або в пам'яті з прямим доступом або в системному стеку -
System Stack.

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

1. Управління процесами.

ПРОЦЕС - ЦЕ ПРОГРАМНИЙ МОДУЛЬ, які виконуються в CPU. ОПЕРАЦІЙНА
СИСТЕМА санітарного НАСТУПНУ Діяльність, пов'язана з ПРОЦЕСАМИ:
1. створення і видалення процесів
2. планування процесів
3. синхронізація процесів
4. комунікація процесів
5. дозвіл тупикових ситуацій

1.1 Поняття Процес. Стани процесу

НЕ БУДЕ змішувати поняття ПРОЦЕС І ПРОГРАМА. ПРОГРАМА - ЦЕ
ПЛАН ДІЙ, А ПРОЦЕС - ЦЕ САМО ДІЯ. ПОНЯТТЯ процес включає:
1. програмний код
2. дані
3. вміст стека
4. вміст адресного та інших регістрів CPU.

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

Розрізняють наступні стани процесу:
1. новий (new, процес тільки що створений)
2. що виконується (running, команди програми виконуються в CPU)
3. стані очікування (waiting, процес чекає завершення деякого події, найчастіше операції введення - виведення)
4. готовий (ready, процес чекає звільнення CPU)
5. завершений (terminated, процес завершив свою роботу)

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

Кожен процес представлений в операційній системі набором даних,званих process control block. У process control block процесописується набором значень, параметрів, що характеризують його поточнестан і використовуються операційною системою для управління проходженнямпроцесу через комп'ютер.

1.2. Планування процесів. Поняття черги.

Система управління процесами забезпечує проходження процесу через
КОМП'ЮТЕР. Залежно від стану ПРОЦЕСУ ЙОМУ ПОВИНЕН БУТИ НАДАТИ
ТОТ АБО ІНШІ РЕСУРС. НАПРИКЛАД, НОВИЙ ПРОЦЕС необхідно розмістити в
Основної пам'яті, отже, йому Необхідно виділити частина адресного
ПРОСТОРУ. ПРОЦЕСУ У СТАНІ ГОТОВИЙ повинні бути надані
Процесорний час. Виконується процес може зажадати ОБЛАДНАННЯ
ВВЕДЕННЯ - ВИВЕДЕННЯ і доступ до файлів.
| | | Заголово | | | | | | | |
| | | К | | | | | | | |
| Процеси | | першого | | PCB7 | | PCB8 | | | |
| у | | | | | | | | | |
| стані | | | | | | | | | |
| "Готовий" | | Последняя | | | | | | | |
| | | Й | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | |
| Черга до | | першого | | | | | | | |
| магнітною | | | | | | | | | |
| стрічці | | Последняя | | | | | | | |
| | | Й | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | |
| Черга | | першого | | PCB3 | | PCB14 | | PCB6 | |
| к | | | | | | | | | |
| диску № 1 | | Последняя | | | | | | | |
| | | Й | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | |
| Черга до | | першого | | PCB5 | | | | | |
| терміналу | | | | | | | | | |
| № 1 | | Последняя | | | | | | | |
| | | Й | | | | | | | |
| | | | | | | | | | |

Розподіл процесів між наявними ресурсами носить назвупланування процесів. Одним з методом планування процесів,орієнтованих на ефективну завантаження ресурсів, є метод чергресурсів. Нові процеси знаходяться у вхідній черзі, часто званоїчергою робіт - завдань (job queue).

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

Готові до виконання процеси розташовуються в основній пам'яті ізв'язані чергою готових процесів або ready queue. Процеси в цій черзіочікують звільнення ресурсу процесорний час.

Процес у стані очікування завершення операції введення - виведеннязнаходиться в одній з черг до устаткування введення - виведення, яка носитьназва devices queue.

При проходженні через комп'ютер процес мігрує між різнимичергами під керуванням програми, яка називається планувальник.
(scheduler) Операційна система, що забезпечує режиммультипрограмування, звичайно включає два планувальника - довгостроковий
(long term scheduler) і короткостроковий (short term scheduler/CPU scheduler).

Основна відмінність між довгостроковим і короткостроковим планувальникамиполягає в частоті запуску, наприклад: короткостроковий планувальник можезапускатися кожні 100 мс, довгостроковий - один раз за кілька хвилин.

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

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

Короткостроковий планувальник вирішує, який із процесів, що знаходяться вчерги готових процесів, повинен бути переданий на виконання в CPU. Удеяких операційних системах довгостроковий планувальник можевідсутнім. Наприклад, у системах поділу часу (time sharingsystem), кожен новий процес відразу ж міститься в основну пам'ять.

1.3. Взаємодія процесів. Користувацький рівень.

спільно виконувати ПРОЦЕСИ МОЖУТЬ БУТИ або незалежності
(INDEPENDED PROCESSES), якої взаємодії (COOPERATING PROCESSES).
ВЗАЄМОДІЯ ПРОЦЕСІВ часто розуміють У сенсі взаємного ОБМІНУ ДАНИМИчерез загальний буфера даних.

Взаємодія процесів зручно розглядати у схемі виробник --споживач (produces - consumer). Наприклад, програма виводу на друквиробляє послідовність символів, які споживаються драйверомпринтера або компілятор виробляє асемблерні текст, який потімспоживається асемблером.

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

Буфер має фіксовані розміри, і отже процеси можутьперебувати в стані очікування, коли:
. буфер заповнений; очікує процес - виробник
. буфер порожній; очікує процес - споживач

Буфер може надаватися і підтримуватися самої ОС, наприклад здопомогою засобів комунікації процесів (IPC - Inter Process Communication),або організувати прикладним програмістом. При цьому обидва процесивикористовують спільну ділянку пам'яті, наприклад процес - виробник і процес
- Споживач можуть використовувати наступні змінні:
Var n;type item =...;< br>Var buffer: array [0 .. n-1] of item;in, out: 0 .. n-1;, де n - кількість адресованих елементів буфера, Item - ім'ятипу елементів буфера, in, out - покажчики, що характеризують заповненнябуфера.

Буфер представлений у вигляді циклічно пов'язаного масиву адресуютьсяелементів з двома покажчиками - in, out. Покажчик in містить номерпершого вільного елемента буфера, а out - перший зайнятого елементабуфера.
| | | | | | | | | | | | | | | |
| | | 0 | 1 | 2 | 3 | 4 | 5 | | | | | n-| | |
| | | | | | | | | | | | | 1 | | |
| | | | | | | | | | | | | | | |

1. Порожній. in = out. Очевидно, що буфер порожній в тому випадку, якщо виконується ця умова.
2. Буфер буде повністю заповнений, якщо виконується умова
(in 1) mod n = out

Процес - виробник повинен виконувати процедуру записи в буфертипу
Repeat
...продукується черговий елемент у Next p
...while (in 1) mod n = out do no_op; buffer (in): = next p; in: = (in 1) mod n;until falseде Next p - локальна змінна процесу - виробника, у якійзберігається черговий продукується елементno_op - порожній оператор
Процес - споживач повинен виконувати процедуру читання з буфера типу
Repeatwhile in out do no_op; next p: = buffer (out); out: = (out +1) mod n;

... споживається черговий елемент з Next с

...until false

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

КОРОТКОСТРОКОВИЙ ПЛАНУВАЛЬНИК ОБИРАЄ ПРОЦЕСИ З черги ГОТОВИЙ
ПРОЦЕСІВ і передати їх на ВИКОНАННЯ В CPU. Існують різні АЛГОРИТМИ
АБО СТРАТЕГІЇ Рішення цього питання, відрізняється ставлення до критеріїв
Планування.

2.1. Критерії планування процесора.

вибирають за такими критеріями, який дозволяє порівняти АЛГОРИТМИ
КОРОТКОСТРОКОВИЙ ПЛАНУВАЛЬНИК:
1. утилізація CPU (використання) CPU utilization. утилізація CPU теоретично може знаходитися межах від 0 до 100%. У реальних системах утилізація CPU коливається в межах 40% для легко завантаженого CPU, 90% для важко завантаженого CPU.
2. пропускна здатність CPU throughput. Пропускна здатність CPU може вимірюватися кількістю процесів, які виконуються за одиницю часу.
3. час обороту (turnaround time) для деяких процесів важливим критерієм є повне час виконання, тобто інтервал від моменту появи процесу у вхідній черзі до моменту його завершення. Цей час названо часом обороту і включає час очікування у вхідній черзі, час очікування в черзі готових процесів, час очікування в чергах до обладнання, час виконання в процесорі і час введення - виведення.
4. час очікування (waiting time). під часом очікування розуміється сумарний час перебування процесу в черги готових процесів.
5. час відгуку (response time) для суто інтерактивних програм важливим показником є час відгуку або час, що минув від моменту потрапляння процесу до вхідної черги до моменту першого звернення до терміналу.

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

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

2.2. Стратегії планування процесора.

2.2.1.ПЕРВИЙ ПРИЙШОВ - ПЕРШИЙ Обслуговуюча FIFO. FIRST COME - FIRST SERVED

(FCFS).

FCFS є найбільш простим Стратегія планування ПРОЦЕСІВ І
Полягає в тому, що процесор передати тому ПРОЦЕСУ, ЩО РАНІШЕ
ВСІ ІНШІ його запити.

Коли процес потрапляє в чергу готових процесів, process controlblock приєднується до хвоста черги.

Середній час очікування для стратегії FCFS часто дуже велика ізалежить від порядку надходження процесів в чергу готових процесів.
Приклад № 1

Нехай три процеси потрапляють в чергу одночасно в момент 0 і маютьтакі значення часу подальшого обслуговування в CPU.варіант 1:
П1 (24 мс)
П2 (3 мс)
П3 (3 мс)варіант 2:
П2 (3 мс)
П3 (3 мс)
П1 (24 мс)

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

2.2.2. Стратегія найбільш коротка робота - вперед до перемоги комунізму!

SJF

SJF - SHORTEST JOB FIRST. ОДНИМ ІЗ МЕТОДІВ БОРОТЬБИ з "ефектом конвою"є стратегією, дозволяє процесу З чергу виконуються ПЕРШИМ.
Приклад № 2

Нехай чотири процесу одночасно потрапляють в чергу готовихпроцесів і мають такі значення часу подальшого обслуговування
П1 (6 мс)
П2 (8 мс)
П3 (7 мс)
П4 (3 мс)

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

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

2.2.3. Пріоритетне планування.

описаної раніше СТРАТЕГІЇ МОЖУТЬ розглядатися як окремий випадок
Стратегією пріоритетних планування. ЕТА стратегія припускає, що
КОЖНОМУ ПРОЦЕСУ приписується ПРІОРИТЕТ, визначати черговість
Надання йому CPU. Наприклад, стратегія FCFS припускає, що всі
ПРОЦЕСИ припускає, що всі ПРОЦЕСИ МАЮТЬ ОДНАКОВІ ПРІОРИТЕТИ, А
СТРАТЕГІЯ SJF Припускають, що ПРІОРИТЕТ Є величина, обернена ЧАСУ
Наступним обслуговуванням.

Пріоритет - це ціле позитивне число, що знаходиться в деякомудіапазоні, наприклад від 0 до 7, від 0 до 4095. Будемо вважати, що чим меншезначення числа, тим вищий пріоритет процесу.
| Приклад № 3. | пріоритет |
| П1 (10 мс) | 3 |
| П2 (1 мс) | 1 |
| П3 (2 мс) | 3 |
| П4 (1 мс) | 4 |
| П5 (5 мс) | 2 |

На малюнку наведена діаграма Гангу, що має процеси вчерги відповідно до стратегії пріоритетного планування
| П2 | П5 | П1 | П3 | П4 | |
| WT2 = 0 мс | WT5 = 1 мс | WT1 = 6 мс | WT3 = 16 мс | WT4 = 18 мс | |

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

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

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

Відомий випадок, коли в 1973 році в Массачусетському технологічномуінституті MIT при зупинці комп'ютера IBM 7094 у черги готових процесівбули виявлені процеси, представлені в 1967 і все ще не виконані.

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

2.2.4. "Карусельна" стратегія планування.

RR-ROUND ROBIN

Round Robin стратегія застосовується в системах поділу часу.
Визначається невеликий відрізок часу, названий квантом часу
(10 .. 100 мс). Черга готових процесів розглядається як кільцева.
Процеси циклічно переміщуються по черзі, отримуючи CPU на час, рівнеодного кванта. Новий процес додається у хвіст черги. Якщо процес незавершився в межах виділеного йому кванта часу, його роботапримусово переривається, і він переміщається в хвіст черги.
Приклад 4
П1 (24 мс)
П2 (3 мс)
П3 (3 мс)q = 4 мс.
Діаграма Гангу відповідно Round Robin стратегії для цього випадку маєвигляд:
| П1 | П2 | П3 | П1 | П1 | П1 | П1 | П1 |
| WT1 = 0 мс | 7 | 10 | 14 | 18 | 22 | 26 | 30 |

Властивості Round Robin стратегії сильно залежать від величини тимчасовогокванта q. Чим більше тимчасової квант, тим довше Round Robin стратегіянаближається до FCFS стратегії. (для розглянутого прикладу, якщо q> 24 мс,то -> FCFS.) При дуже малих значеннях тимчасового кванта Round Robinстратегія називають поділом процесора - processor sharing. Теоретичноце означає, що кожен з N процесів працює зі своїм власнимпроцесором, продуктивність процесора дорівнює 1/N від продуктивностіфізичного процесора.

2.2.5. ПЛАНУВАННЯ з використанням багаторівневої черги. (Multilevel queue scheduling)

ця стратегія Розроблений для СИТУАЦІЇ, КОЛИ ПРОЦЕСИ МОЖУТЬ БУТИ
Легко класифікувати на декілька груп, наприклад, часто ПРОЦЕСИ
Поділяють на дві групи: ІНТЕРАКТИВНІ (ПРОЦЕСИ передньому плані) і
Пакетні (фоновий).

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

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

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

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

2.2.6. Програмування з використанням багаторівневої черги з зворотними зв'язками (multilevel feedback queue sheduling)

ЗВИЧАЙНА Багаторівнева Черги не допускати переміщення ПРОЦЕСІВ
Між чергами. Багаторівнева ЧЕРГА зі зворотним зв'язком Припускають,що процес За певних умов можуть переміщатися між чергами.

Процеси спочатку потрапляють в чергу 0, де кожному з нихнадається квант часу, що дорівнює 8 мс. Ті процеси, які не встигливиконатися протягом цього часу, що переміщуються у чергу 1. Процеси зчерзі 1 починають оброблятися тільки тоді, коли черга 0 ставатипорожній. Ті процеси, які не виконали у черзі 1 (q = 16 мс)переміщуються в чергу 2. Процеси з черги 2 будуть оброблятися тількив тому випадку, якщо стають порожніми черзі 0 і 1.

Розглянута стратегія є найбільш універсальною і поєднує всобі властивості всіх розглянутих раніше стратегій.
1. FCFS
2. SJF
3. пріоритетна
4. Round Robin
5. багаторівнева чергу

3. Управління невіртуальному пам'яттю.

3.1. СВОППІНГ. (SWAPPING)

СВОППІНГОМ званий метод управління пам'яттю, заснований на тому,що всі процеси, які беруть участь у мультипрограмному ОБРОБКИ, зберігаються у
Зовнішньої пам'яті.

Процес, якому виділений CPU, тимчасово переміщається в основнупам'ять (swap in/roll in).

У разі переривання роботи процесу він переміщається назад узовнішню пам'ять (swap out/roll out).
Зауваження: при своппінге з основної пам'яті в зовнішню (і назад)переміщається вся програма, а не окрема її частина.

Своппінг іноді використовують при пріоритетному плануванні CPU. У цьомувипадку з метою звільнення пам'яті для високопріоритетних процесів,низькопріоритетним процеси переміщуються у зовнішню пам'ять.

Основне застосування своппінг знаходить у системах поділу часу,де він використовується одночасно з Round Robin стратегією планування CPU.

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

Метод своппінга впливає на величину тимчасового кванта Round Robinстратегії.
Приклад.
1. нехай черговий завантаження в пам'ять процес має розмір 100 Кб.
2. диск дозволяє читати дані зі швидкістю 1 Мб в секунду
3. отже, 100 Кб можуть бути завантажені через 100 мс.
4. будемо вважати, що для початкового підвода головки читання - записи потрібно 8 мс
5. таким чином, операція своппінг займе 108 мс, а загальний час своппінга
- 216 мс.

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

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

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

3.2. Суміжне розміщення процесів.

метод розміщення ПРОЦЕСІВ в основній пам'яті ЦЯ
Розташування ділянки пам'яті, виділену для однієї і тієї ж ПРОГРАМИ ділять
НА ДВА КЛАСУ. ПЕРШИЙ - МЕТОД СУМІЖНІ розміщення, а ДРУГИЙ - МЕТОД
Несуміжних розміщення.

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

3.2.1. Однопрограмних режим.

малюнок ілюструє СУМІЖНІ РОЗМІЩЕННЯ (CONTIGUOUS ALLOCATION) ОДНІЄЇ
ПРОГРАМИ в основній пам'яті.

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

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

оверлейной структуру програми і послідовність завантаженняоверлейной сегментів планує сам програміст.

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

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

3.2.2 мультипрограмному режим з фіксованою межами.

мультипрограмування з фіксованою Розділ (MULTIPROGRAMMING
WITH A FIXED NUMBER OF TASKS) припускає поділ АДРЕСНО
ПРОСТОРУ НА ряд розділів ФІКСОВАНОГО РОЗДІЛУ. В КОЖНОМУ РОЗДІЛІ
ПУБЛІКУЙТЕ ОДИН ПРОЦЕС.

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

У цьому випадку, якщо відповідний розділ зайнятий, то процес залишаєтьсяв черзі у зовнішній пам'яті навіть у тому випадку, коли інші розділивільні.

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

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

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

Перш ніж програма у роздiлi N почне виконуватися, її граничніадреси завантажуються у відповідні регістри. У процесі роботи програмивсе що формуються нею адреси контролюються на задоволення нерівності а <Адр. <Б

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

3.2.3. Мультипрограмування зі змінними розділами. (multiprogramming with a variable number of tasks (MVT).

МЕТОД MULTIPROGRAMMING WITH A VARIABLE NUMBER OF TASKS ПЕРЕДБАЧУВАНА
РОЗДІЛЕННЯ Пам'яті на РОЗДІЛИ І вставлено завантажувальний МОДУЛІВ У
Переміщати АДРЕСИ, ОДНАК, КОРДОНУ РОЗДІЛІВ не фіксується.
| | | | | | 0 | ОС |
| 90 Кб | | | | | а | Розділ 1 |
| П5 | П4 | П3 | П2 | П1 | | Розділ 2 |
| | | | | | | Розділ 3 |
| | | | | | | Розділ 4 |
| | | | | | | 80 Кб |

Як випливає з малюнка, у початковій фазі відсутній фрагментація,пов'язана з тим, що розмір чергового процесу менше розміру, займаногоцим процесом розділу. На цій фазі причиною фрагментації єневідповідність розміру чергового процесу та вільного ділянки пам'яті. Заміру завершення роботи програми звільняються окремі розділи. У томувипадку, коли звільняються суміжні розділи, межі між ними видаляються тарозділи об'єднуються.
| | | | 0 | ОС |
| | | 90 Кб | а | Розділ 1 |
| П7 | П6 | П5 | | 100 Кб |
| | | | | |
| | | | | Розділ 4 |
| | | | | |

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

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

3.2.4. Мультипрограмування зі змінними розділами і ущільненням пам'яті.

ясно, що МЕТОД MULTIPROGRAMMING WITH A VARIABLE NUMBER OF TASKS
Породжує в ПАМ'ЯТІ Багато малих ФРАГМЕНТ, КОЖЕН З ЯКИХ МОЖЕ БУТИ
Недостатній для Розміщення чергового ПРОЦЕСУ, ОДНАК Сумарний розмір
ФРАГМЕНТ ПЕРЕВИЩУЄ РОЗМІР ЦЬОГО ПРОЦЕСУ.

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

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

3.2.5. Основні стратегії заповнення вільного розділу.

розглянуті методи мультипрограмування припускає наявність
Вхідної черги/Черг до РОЗДІЛАХ основної пам'яті.

У тому випадку, коли звільняється черговий розділ, операційнасистема повинна вибрати один з процесів для розміщення його в пам'яті.
Алгоритм вибору може використовувати одну з наступних трьох стратегій:
1. стратегія найбільш відповідного (best fit strategy) вибирає процес, якому у звільненому розділі найбільш тісно (виграш в пам'яті).
2. стратегія перший підходящого (first fit strategy) вибирає перший процес, який може розмістити у звільненому розділі.
3. стратегія найменш придатного (last fit strategy) вибирає процес, якому у звільненому розділі найбільш вільно (у цьому випадку залишається фрагмент часто достатній для розміщення ще одного процесу)

3.3. Сторінкова організація пам'яті.

сторінкова організація пам'яті (PAGING) відноситься до методу несуміжних
РОЗМІЩЕННЯ ПРОЦЕСІВ в основній пам'яті.

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

3.3.1. Базовий метод.

Адресний простір ОСНОВНИЙ і зовнішньої пам'яті розбивається на блоки
ФІКСОВАНОГО РОЗМІРУ, називається Сторінкова РАМКИ (FRAMES). ЛОГІЧНОГО
Адресний простір ПРОГРАМИ ТАКОЖ розбивається на блоки ФІКСОВАНОГО
РОЗМІРУ, називається сторінкою (PAGES). РОЗМІРИ Сторінкова рамок і СТОРІНОК
Збігаються. ПРОЦЕС завантажуються в пам'ять посторінково, причому кожна СТОРІНКА
Поміщається в будь-яку вільну Сторінкова рамки Основного ПАМ'ЯТІ.

Кожен адреса, що генерується процесором, складається з двох частин: П --номер сторінки (page number) і Д - зміщення в межах сторінки (off set).
Номер сторінки може використовуватися як індекс для таблиці сторінок (pagetable).

Таблиця сторінок містять початкові адреси f всіх сторінкових рамок, уяких розміщено програму. Фізична адреса визначається шляхом додаванняпочаткового адреси сторінкової рамки f і зміщення Д.
| | | Вторинна | | Таблиця | | Основна |
| | | Пам'ять | | сторінок | | пам'ять |
| | | | | Програми | | |
| | | | | А | | |
| | | Стр. 0 | | 1 | | стр. 0 |
| | Програма | стр. 1 | | 3 | | |
| | А | стр. 2 | | 4 | | стр. 1 |
| | | Стр. 3 | | | 7 | | стр. 2 |
| | | | | | | |
| | | | | | | |
| | | | | | | Стр. 3 | |

Малюнок показує, що сторінкова організація пам'яті повністювиключає зовнішню фрагментацію. Внутрішня фрагментація не перевищуєвеличини page_size-Q_Elem, де page_size - розмір сторінкової рамки, а
Q_Elem - мінімальний адресованих елементів основної пам'яті.

Для прискорення обчислення фізичної адреси операцію підсумовуваннязамінюють операцією конкатенації.
| старші розряди | молодші розряди | |
| | 2n + | 2n | | f |
| | 1 | | | |
| | | |
| | 2n-| | 2n | Д |
| | 1 | | | |

На малюнку заштриховані незаповнені нульові розряди. Для того,щоб операція конкатенації була можлива, необхідно, щоб базові адресисторінкових рамок розташовувалися тільки в старших розрядах (2n +1), анаступні - лише молодших розрядів (20, 21, 22).

Наприклад, при n = 9 базові адреси сторінкових рамок - це наступнийряд: 512, 1024, 1536. Отже, розмір сторінкової рамки дорівнює 512байт.

У сучасних операційних системах типовий розмір сторінкистановить 2 Кб або 4 Кб.

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

3.3.2. Апаратна підтримка сторінкової організації пам'яті.

Перетворення логічних адрес У фізичному здійснюється для
КОЖНОГО АДРЕСИ, що генеруються процесори, тому ЧАСТИНИ ДЛЯ ПРИСКОРЕННЯ
ЦЬОГО ПРОЦЕСУ застосовується апаратний МЕТОДИ. На малюнку приведений СХЕМА,
Ілюструється метод, що використовує Асоціативний РЕГІСТРИ (ASSOCIATIVE
REGISTERS).

Кожен асоціативний регістр крім операцій читання - записи можеобробляти операцію порівняння коду, що надходить на його вхід з част?? юкоду, що зберігається в регістрі. Матриця асоціативних регістрів зберігає частинутаблиці сторінок. Номер сторінки П подається одночасно на входи всіхасоціативних регістрів, які паралельно виконують операцію порівняння.
На виході матриці асоціативних регістрів утворюється початкова адресасторінкової рамки f того регістра, в якому відбулося збіг коду.

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

Захист сторінкової пам'яті заснована на контролі рівня доступу до кожноїсторінці, можливі наступні рівні доступу:
1. тільки читання
2. і читання і запис
3. тільки виконання

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

3.4. Сегментна організація пам'яті.

сторінкова організація пам'яті Припускають, що РОЗДІЛЕННЯ ПРОГРАМИ
НА СТОРІНКИ здійснює операційна СИСТЕМА І ЦЕ невидимо для
Прикладних програмістів. БІЛЬШІСТЬ ТЕХНОЛОГІЙ програмування також
Припускає поділ ПРОГРАМИ На безлічі логічні частини -
Підпрограм, ПРОЦЕДУРИ, МОДУЛІ І ТАК ДАЛІ.

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

3.4.1. Базовий метод сегментної організації пам'яті.

ЗВИЧАЙНО СЕГМЕНТА ФОРМУЄТЬСЯ компілятори, А НА ЕТАПІ ЗАВАНТАЖЕННЯ ІМ
Привласнюється ідентифікують номер. ТАКИМ ЧИНОМ, логічних адрес ПРИ
Сегментна ОРГАНІЗАЦІЇ пам'яті складається з двох частин: S І D, ДЕ S - НОМЕР
СЕГМЕНТА, А D - Зсув В МЕЖАХ СЕГМЕНТА.

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

Кількість рядків таблиці сегментів дорівнює кількості сегментівпрограми: S, limit, base. Limit - розмір сегмента, base - початкова адресасегмента в пам'яті.

Номер сегмента S використовується в якості індексу для таблицісегментів. За допомогою таблиці сегментів визначається його початкова адресаbase в основній пам'яті. Значення limit використовується для захисту пам'яті.
Зсув d повинна задовольняти нерівності 0