Розробка операційних систем

Інформатика, програмування

Дагестанский державний університет.

Математичний факультет.

Кафедра інформатики та обчислювальної техніки.

Дипломна робота

на тему

«Розробка операційних систем».

Керівник:

Ханікалов Х.Б.

Виконав: студент 5 к. 4 гр.

Атаян А.П.

Махачкала 2000

План роботи:
Введення.

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

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

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

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

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

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

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

2.2.1.Первий прийшов - першим обслуговується FIFO. First come - first served (FCFS).

2.2.2. Стратегія - найбільш коротка робота! SJF.

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

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

2.2.5. Планування з використанням багаторівневої черги. (Multilevel queue scheduling).

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

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

3.1. Своппінг. (swapping).

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

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

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

3.2.3. Мультипрограмування зі змінними розділами.

(multiprogramming with a variable number of tasks (MVT).

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

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

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

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

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

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

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

3.4.2. Поділ сегменту між декількома процесами .

3.4.3. Фрагментація.

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

4.1. Странічірованіе за запитом (demand paging).

4.2. Заміщення сторінок.

4.2.1. FIFO.

4.2.2. Оптимальний алгоритм.

4.2.3. LRU - алгоритм (least recently used).

5. Загальні відомості.

5.1. Управління пам'яттю.

5.2. Файлова система.

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

5.4. Взаємодія між процесами.

5.5. Графічний інтерфейс користувача.

5.6. Об'єктно-орієнтоване орієнтування та операційні системи.

Висновок.

ВСТУП.

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

На сьогоднішній день на ринку програмного забезпечення для IBM PC -сумісних комп'ютерів співіснують декілька сімейств операційнихсистем. Однозадачние однокористувацький ОС MS-DOS і PC-DOS єнайпоширенішими з огляду на свою простоту і 'невибагливості', більшуроль тут грає і те, що переважна більшість програм працюєсаме під їх управлінням. MS-DOS і PC-DOS характеризуються мінімальнимкористувальницьким і програмним інтерфейсами, в той же час, працюючи звсілякими програмними оболонками, інтегрованими середовищами (такими як
Microsoft Windows або DESQview), створюють комфортабельну середовище длякористувача і програми.

ОС Microsoft Windows NT, орієнтована на роботу в різноріднихмережах, високонадійні, однак, це досягнуто за рахунок часткової втратисумісності з MS-DOS.

Операційна система OS/2 стоїть осібно: будучи повноправноюбагатозадачного операційною системою зі своїм оригінальним графічнимкористувальницьким і програмним інтерфейсами, вона зберігає сумісність з
MS-DOS і PC-DOS (починаючи з версії WARP 3.0 і з Microsoft Windows).

ОС UNIX - одна з найстаріших і найбільш простих операційних систем,спочатку була розрахована на розробку програм (для неї самої і нетільки) на міні-ЕОМ і дозволяла без великих затрат праці програмістапереносити програму з однієї системи ЕОМ на іншу. Не дивно, щозараз продається багато різних варіантів мобільної операційної системи
UNIX, таких як XENIX, UNIXWARE, SUN-OS, LINUX, BSD.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На малюнку схематично показано, яким чином операційна системавикористовує process control block для перемикання процесора з одногопроцесу на іншій.

| | | Заголово | | | | | | |
| | | К | | | | | | |
| Процеси | | першого | | PCB7 | | PCB8 | | |
| у | | | | | | | | |
| стані | | | | | | | | |
| "Готовий" | | Последняя | | | | | | |
| | | Й | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| Черга до | | першого | | | | | | |
| магнітною | | | | | | | | |
| стрічці | | Последняя | | | | | | |
| | | Й | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| Черга | | першого | | PCB3 | | PCB14 | | PCB6 |
| к | | | | | | | | |
| диску № 1 | | Последняя | | | | | | |
| | | Й | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| Черга до | | першого | | PCB5 | | | | |
| терміналу | | | | | | | | |
| № 1 | | Последняя | | | | | | |
| | | Й | | | | | | |

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

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

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

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

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

1. буфер заповнений; очікує процес - виробник

2. буфер порожній; очікує процес - споживач

Буфер може надаватися і підтримуватися самої ОС, наприклад здопомогою засобів комунікації процесів (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. Очевидно, що буфер порожній в тому випадку, якщо виконується ця умова.
1. Буфер буде повністю заповнений, якщо виконується умова
(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.
1. пропускна здатність CPU throughput. Пропускна здатність CPU може вимірюватися кількістю процесів, які виконуються за одиницю часу.
1. час обороту (turnaround time) для деяких процесів важливим критерієм є повне час виконання, тобто інтервал від моменту появи процесу у вхідній черзі до моменту його завершення. Цей час названо часом обороту і включає час очікування у вхідній черзі, час очікування в черзі готових процесів, час очікування в чергах до обладнання, час виконання в процесорі і час введення - виведення.
1. час очікування (waiting time). Під часом очікування розуміється сумарний час перебування процесу в черги готових процесів.
1. час відгуку (response time) для суто інтерактивних програм важливим показником є час відгуку або час, що минув від моменту потрапляння процесу до вхідної черги до моменту першого звернення до терміналу.

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

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

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

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

FIRST SERVED (FCFS).

На рисунку Схематично показати, яким образів операційної системи
ВИКОРИСТОВУЄ PROCESS CONTROL BLOCK для перемикання Процесор з ОДНОГО
ПРОЦЕСУ НА ІНШИЙ.

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

На малюнку наведена діаграма Гангу, побудована відповідно достратегією SJF.

Легко порахувати, що при використанні 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. вимоги до пам'яті
1. кількість відкритих файлів
1. ставлення середнього часу введення - виведення до середнього часу CPU і так далі
Зовнішні фактори:
1. важливість процесу
1. тип і розмір файлів, що використовуються для оплати
1. відділення, що виконує роботи і так далі

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

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

Відомий випадок, коли в 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
1. SJF
1. пріоритетна
1. Round Robin
1. багаторівнева чергу

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

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

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

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

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

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

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

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

Метод своппінга впливає на величину тимчасового кванта Round Robinстратегії.
Приклад.
1. нехай черговий завантаження в пам'ять процес має розмір 100 Кб.
1. диск дозволяє читати дані зі швидкістю 1 Мб в секунду
1. отже, 100 Кб можуть бути завантажені через 100 мс.
1. будемо вважати, що для початкового підвода головки читання - записи потрібно 8 мс
1. таким чином, операція своппінг займе 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. в тих випадках, коли мультипрограмному суміш неоднорідна по відношенню до розмірів програм, виникає необхідність у частому ущільненні, що витрачає ресурс процесорний час і компенсує економію ресурсу пам'яті.
1. під час ущільнення всі прикладні програми переводяться в стан
"очікування", що призводить до неможливості виконання програм у реальному масштабі часу.

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

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

У тому випадку, коли звільняється черговий розділ, операційнасистема повинна вибрати один з процесів для розміщення його в пам'яті.
Алгоритм вибору може використовувати одну з наступних трьох стратегій:
1. стратегія найбільш відповідного (best fit strategy) вибирає процес, якому у звільненому розділі найбільш тісно (виграш в пам'яті).
1. стратегія перший підходящого (first fit strategy) вибирає перший процес, який може розмістити у звільненому розділі.
1. стратегія найменш придатного (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 - мінімальний адресованих елементів основної пам'яті.

Для вус