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

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

Запровадження. Основні поняття і определения.

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

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

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

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 sharing system), кожен новий процес відразу ж потрапляє міститься у основну память.

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

РАЗОМ ВЫПОЛНяЕМЫЕ ПРОЦЕСИ МОЖУТЬ БУТИ АБО НЕЗАЛЕЖНИМИ (INDEPENDED PROCESSES), АБО ВЗАЄМОДІЮЧИМИ (COOPERATING PROCESSES). ВЗАЄМОДІЯ ПРОЦЕСІВ чАСТО ПОНИМАЕТСя У СЕНСІ ВЗАЄМНОГО ОБМЕНА ДАНИМИ чЕРЕЗ ОБЩИЙ БУФЕР ДАННЫХ.

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

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

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

Буфер може надаватися і самої ОС, приміром, із допомогою коштів комунікації процесів (IPC — Inter Process Communication), або організувати прикладним програмістом. У цьому обидва процесу використовують загальний ділянку пам’яті, наприклад процес — виробник та інформаційний процес — споживач може використати такі перемінні: Var n; type item=…; 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 — порожній оператор Процес — споживач має виконувати процедуру читання з буфера типу Repeat while 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 control block приєднується до хвосту очереди.

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

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

На рисунку наведені діаграми Гангу черги готових процесів варіант1: |П1 |П2 |П3 |WT=17 мс | |WT1=0 мс |WT2=24 мс |WT3=27 мс | |.

варіант 2: |П2 |П3 |П1 |WT=3 мс | |WT2=0 мс |WT3=3 мс |WT1=6 мс | |.

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

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

SJF.

SJF — SHORTEST JOB FIRST. ОДНИМ ІЗ МЕТОДІВ БОРОТЬБИ З «ЕФЕКТОМ КОНВОя» яВЛяЕТСя СТРАТЕГИя, ПОЗВОЛяЮЩАя ПРОЦЕСУ ІЗ ОчЕРЕДИ ВЫПОЛНяТЬСя ПЕРШИМ. Приклад № 2.

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

На малюнку приведено діаграма Гангу, побудована відповідності зі стратегією SJF. |П4 |П1 |П3 |П2 |WT=7 мс | |WT4=0 мс |WT1=3 мс |WT3=9 мс |WT2=16 мс | |.

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

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

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

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

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

Перш ніж програма розділ 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). Номер сторінки придатна як індекс для таблиці сторінок (page table).

Таблиця сторінок містить початкові адреси 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 байт.

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

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

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

ПЕРЕТВОРЕННЯ ЛОГИчЕСКОГО АДРЕСИ У ФИЗИчЕСКИЕ ОСУЩЕСТВЛяЕТСя ДЛя КОЖНОГО АДРЕСИ, ГЕНЕРОВАНОГО ПРОЦЕСОРОМ, ТОМУ чАСТО ДЛя УСКОРЕНИя ЦЬОГО ПРОЦЕСУ ПРИМЕНяЮТСя АПАРАТНІ МЕТОДИ. НА МАЛЮНКУ ПРИВЕДЕНО СХЕМА, ИЛЛЮСТРИРУЮЩАя МЕТОД, ВИКОРИСТОВУЄ АСОЦІАТИВНІ РЕГІСТРИ (ASSOCIATIVE REGISTERS).

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

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

Захист страничной пам’яті полягає в контролі рівня доступу до кожної сторінці, можливі такі рівні доступу: 1. лише читання 2. і читання і запис 3. лише выполнение.

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

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

СТРАНИчНАя ОРГАНИЗАЦИя ПАМяТИ ПЕРЕДБАЧАЄ, щО ПОДІЛ ПРОГРАМИ НА СТОРІНКИ ОСУЩЕСТВЛяЕТ ОПЕРАЦИОННАя СИСТЕМА І ЦЕ НЕВИДИМЕ ДЛя ПРИКЛАДНОГО ПРОГРАМІСТА. БІЛЬШІСТЬ ТЕХНОЛОГІЙ ПРОГРАММИРОВАНИя ТАКОЖ ПЕРЕДБАЧАЄ ПОДІЛ ПРОГРАМИ НА БЕЗЛІЧ ЛОГИчЕСКИХ чАСТИН — ПІДПРОГРАМИ, ПРОЦЕДУРИ, МОДУЛІ І ТАК ДАЛЕЕ.

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

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

ОБЫчНО СЕГМЕНТИ ФОРМИРУЮТСя КОМПИЛяТОРОМ, А НА ЕТАПІ ЗАВАНТАЖЕННЯ ЇМ ПРИСВАИВАЮТСя ІДЕНТИФІКУЮТЬ НОМЕРИ. ТАКИМ ЧИНОМ, ЛОГИчЕСКИЙ АДРЕС ПРИ СЕГМЕНТНОЙ ОРГАНІЗАЦІЇ ПАМяТИ ПОЛЯГАЄ ІЗ ДВОХ чАСТИН: P. S І D, ДЕ P. S — НОМЕР СЕГМЕНТА, А D — УСУНЕННЯ У МЕЖАХ СЕГМЕНТА.

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

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

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