Алгоритм Деккера

Алгоритм Деккера базується на використанні змінних key 1, key 2, queue. Змінні key 1, key2 використовуються як в попередньому алгоритмі з пункту 3. Значення змінної queue визначає чиячерга (процесу один чи процесу два) почати виконання критичної секції при умові, якщо двапроцеси бажають це зробити.

35 Задача синхронізації «парихмахера» та «філософів, які обідають».??????????

36 Використання семафорів для синхронізації та впорядкування паралельних процесів.

Семафор – це змінна спеціального типу, яка доступна паралельним процесам длявиконання двох операцій: зайнято (P - операція); відкрито (V – операція). Семафор відіграє рольдопоміжного критичного ресурсу і операції V та P є нероздільними. Крім того P і V виключаютьодна іншу.

Семафори працюють таки чином, що спочатку аналізують стан критичного ресурсу, якийідентифікується станом семафору, потім здійснюється допуск до критичного ресурсу або відмовавід нього. При відмові в доступі до критичного ресурсу використовується режим пасивногоочікування. В цьому випадку процес знаходиться в заблокованому стані. Він не перевіряє семафорбезперервно, як у стані активного очікування. В той час процес може виконувати необхідну дію.Допустимими значеннями семафору є тільки цілі числа. Семафори бувають двійкові (приймаютьзначення 0, 1), або n – значення (в іншому випадку).

Приклад:

var S: semaphore

begin

init Sem(S, 1)

parbegin

PR1: while true do

begin

P(S)

CS1

V(S)

end

and

PR2: while true do

begin

P(S)

CS2

V(S)

end

parend

Семафор S має початкове значення 1. Якщо процеси PR1, PR2 будуть намагатисявиконати операцію P(S), то це зробить успішно тільки один процес. Якщо це зробив процес PR2,тоді він закриває семафор S, після чого виконується його критичний інтервал. Процес PR1 в ційситуації буде заблокований на семафорі S. Після виконання операції V(S) процесу PR2 семафор Sвідкривається, показуючи можливість використання одного сумісного ресурсу. Цією операцією процес PR1 буде переведений із заблокованого стану в стан готовності

.

37 Монітороподібні засоби синхронізації паралельних процесів.

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

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

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

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

яким необхідний цей ресурс. А може існувати ситуація, коли є декілька процесів, які очікуютьзвільнення ресурсів. В цьому випадку монітор видає команду signal(), яка сповіщає, що один зочікуваних процесів може зайти і використати даний необхідний ресурс.Використання моніторів як основного засобу синхронізації дозволяє звільнити процеси віднеобхідності явного розподілення інформації між собою. Доступ до розділювальних змінних таобластей пам’яті контролюється власне тілом самого монітора. Так як монітори входять в складОС, то його змінні є завжди системними змінним. Це автоматично виключає критичні інтервали(секції) процесів тому, що в певний момент часу монітором може користуватися тільки один

процес. Одночасно два процеси не можуть отримати доступ до змінних монітору.

Основні переваги моніторів:

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

синхронізації;

 наявність всіх розділювальних змінних в тілі монітора, що дозволяє їх виключити з

вихідних модулів паралельних процесів;

 монітори дають змогу паралельним процесам сумісно використовувати програмні

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

38 Міжпроцесова взаємодія за допомогою поштових ящиків.

Взаємодія між паралельними процесами обумовлює не тільки синхронізацію (обмінтимчасовими сигналами), але й передачу і отримання довільних повідомлень. Крім того впаралельних процесах неможливо гарантувати відправку повідомлень одним процесом іотримання іншим процесом практично в один і той самий момент часу. Тому є необхідністьтимчасового зберігання повідомлення в спеціальному буфері обміну, який називаєтьсяпоштовий ящик. Наприклад, для того, щоб послати процес Р2, процес Р1 повинен запитати йогоу відповідний поштовий ящик, звідки Р2 може зчитати це повідомлення в будь – який моментчасу. Як правило, поштові ящики є системними об’єктами і для їх використання процесповинен запросити операційну систему відповідним запитом. Як правило, поштові ящикискладаються з головного елементу, в якому міститься інформація про параметри цьогопоштового ящика і декількох наступних елементів (комірок) в яких розміщуєтьсяповідомлення. Розмір комірки визначається при створенні поштового ящика.Найпростіший алгоритм роботи поштового ящика полягає в тому, що процес Р1 посилаєповідомлення в поштовий ящик до тих пір, поки є вільні комірки, а процес Р2 – зчитує ціповідомлення поки є заповнені комірки. В більш складних випадках використовуються двонаправлені поштові ящики які дозволяють підтверджувати прийом(зчитування)повідомлень. В цьому випадку в кожній комірці міститься або повідомлення від процесу Р1, або

підтвердження про зчитування (прийняття) повідомлення від процесу Р2.

Основними перевагами поштових ящиків є:

1) процесу нема необхідності знати про існування інших паралельних процесів до тогомоменту, поки він не отримає повідомлення від них;

2) два процеси можуть обмінюватись одним повідомленням більше ніж один раз;

3) ОС може гарантувати, що ніякий інший процес не буде вмішуватись у взаємодію

двох процесів;

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

Недоліком поштових ящиків є поява ще одного ресурсу (власне поштового ящика) яким

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

якому чітко визначено розмір і кількість комірок.

39 Міжпроцесова взаємодія за допомогою конвеєрів.

Термін конвеєр вперше був введений в склад операційної системи Unix для систем міні –машин. Конвеєр (pipe) – це ресурс операційної системи, за допомогою якого можна здійснюватиобмін повідомленнями між процесами. Розмір конвеєра для ОС міні - машин складав 64 Кб.Механізм роботи конвеєра аналогічний механізму роботи з файлами ОС Unix. Процес якийпередає інформацію функціонує так само як і при записі інформації у файл, а процес якомупризначене це повідомлення просто зчитує ці дані з файлу “pipe” аналогічно зв’язку. Функції ОС,за допомогою яких можна записати інформацію в канал і зчитати з каналу є тими самими, що і прироботі з файлами. Однак канал представляє собою не файл на диску, а буфер в оперативнійпам’яті.

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

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

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

40 Міжпроцесова взаємодія за допомогою черг повідомлень.

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

Механізм черг має наступні властивості:

 можна використовувати декілька дисциплін обробки повідомлень в черзі (наприклад,

FIFO, LIFO);

 якщо при читанні з конвеєра повідомлення повинно бути знищене з відповідноїкомірки, у випадку черг повідомлення не знищується і може бути прочитане декількаразів;

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

41 Умови виникнення взаємоблокувань.

Взаємні блокування (DeadLocks) з'являються, наприклад, тоді, коли всі процеси блоковані в черзі очікування семафора або умови

Передумови, за яких може з'явитись взаємоблокування:

1. Операційні засоби можуть використовуватися тільки на основі виключного права (ексклюзивно).

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

3. Операційні засоби не можуть забиратися у процесів в примусовому порядку.

4. Існує циркулярний ланцюг процесів, так що кожний процес використовує операційний ресурс, який замовляється наступним процесом цього ланцюга.

42 Стратегії уникненні взаємоблокувань.

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

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

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

Фізична пам’ять являє собою впорядковану множину комірок і всі вони пронумеровані,тобто до кожної із них можна звернутися вказавши її впорядкований номер (адрес). Кількістькомірок фізичної пам’яті є обмеженою і фіксованою. СПЗ повинно зв’язати кожне вказанекористувачем ім’я з фізичною коміркою пам’яті, тобто здійснити відображення простору імен нафізичну пам’ять комірки.

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

 спочатку системою програмування;

 потім ОС (з допомогою спеціальних програмних модулів керування пам’яттю івикористання спеціальних апаратних засобів).

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

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

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

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

43 Неперервний розподіл оперативної пам'яті

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

 область, яку займає операційна система;

 область, в якій розміщується програма яка виконується;

 незайнята область пам’яті.

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

44 Розподіл оперативної пам'яті з перекриттям.

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

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

Після того як поточний сегмент завершить своє виконання можливі два варіанти:

 або він сам звертається до ОС з вказанням в який сегмент має бути завантажений впам’ять наступним;

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

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

45Статичний розподіл оперативної пам'яті.

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

Як правило, статичний розподіл здійснюється на рівні довгострокового планування підчас розробки програми або ОС.

Приклад на мові Assembler:

buffer db 1024 dup(?)

46 Динамічний розподіл оперативної пам'яті.

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

4Ah, 48h, 49h – функції операційної системи, переривання 21h – на мові Assembler.

Команди malloc, realloc – на мові С.

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

47 Розділи оперативної пам'яті з фіксованими розмірами.

Розбиття пам’яті на розділи з фіксованими розмірами графічно можна так зобразити.

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

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

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

У випадку помилки адресації пам’яті виконувана програма може почати обробку з“чужого” сегменту пам’яті і даних, що може привести до непередбачених наслідків. Рішенням цієїпроблеми є використання регістрів захисту пам’яті, які містять граничні адреси області пам’ятіпоточної виконуваної задачі і при перевищені адреси управління передається на ОС.

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

Для зменшеннявтрат оперативної пам’яті використовують такі шляхи:

 виділяють розмір пам’яті який необхідний для поточної задачі;

 розміщають задачу не в одному неперервному розділі пам’яті, а в декількох розділахменшого розміру.

48 Розділи оперативної пам'яті із змінними розмірами

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

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

Виділення пам’яті під новий розділ може здійснюватись трьома способами:

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

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

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

49 Структура, основні поняття та принципи віртуалізації пам'яті.

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

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

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

Використання концепції віртуальна пам’ять дозволяє розділити фізичну пам’ять на блоки,

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

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

50 Сторінкова схема організації віртуальної пам'яті.

Використовується в ОС Linux, OS/2, Windows.

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

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

Розбиття всієї оперативної пам’яті на сторінки приводить до того, що замість фактичноодномірного адресного простору ми можемо користуватись двомірним. У цьому випадку першакоордината – це номер сторінки, друга – зміщення в середині сторінки.

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

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

Рис. 6.2. Сторінкова схема організації віртуальної пам’яті.

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

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

В більшості сучасних ОС, наприклад OS/2 використовується дисципліна LRU, в WindowsNT дисципліна заміщення FIFO. Так само як у випадку сегментного способу сторінковий механізмвимагає спеціальних апаратних засобів, наприклад кешування дескрипторів сторінок, що значнозбільшує продуктивність обчислювальної системи в цілому.

У сучасних мікропроцесорах (486 і інші) використовується механізм асоціативного кешу,який дозволяє кешувати 32 дескриптори сторінок, при чому розмір сторінки містить 4 Кб, розмірмаксимально швидкого звернення до пам’яті дорівнює відповідно 128 Кб.Основною перевагою сторінкової схеми організації віртуальної пам’яті є мінімальнафрагментація пам’яті, так як на кожну задачу може відводитись максимально одна незаповненасторінка в пам’яті.

Є два недоліки:

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

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

51 Сегментна схема організації віртуальної пам'яті.

Сегментна схема використовується в ОС OS/2.

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

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

Рис. 6.1. Сегментний спосіб організації віртуальної пам’яті.

РТДС – регістр таблиці дескрипторів сегментів;

ВА – віртуальна адреса;

S – сегмент;

D – зміщення в середині сегмента;

ТДПЗ – таблиця дескрипторів поточної задачі.

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

Кожен сегмент, який розміщується в пам’яті має відповідну інформаційну структуру – яканазивається дескриптором сегменту.

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

При розміщенні сегменту в ОЗП в цій таблиці встановлюється в 1 спеціальний біт, якийпоказує, що даний сегмент розміщується дійсно в ОЗП. В цьому випадку в поле адрес (в таблиці)записується адреса фізичної пам’яті з якої починається сегмент. В поле довжина (в таблиці)записується кількість комірок пам’яті, які розподілені в цьому сегменті.

Поле довжинавикористовується з двох причин:

 для того, щоб сегменти не перекривалися між собою;

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

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

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

Задачі заміщення сторінок фізичної пам’яті вирішуються за допомогою використання

таких дисциплін: FIFO (перший прийшов, перший вийшов); LRU (останній з недавновикористаних, який найдовше не використовувався); LFU (це той сегмент, який використовувавсярідше за всіх); ВВС (випадковий вибір сегментів).

Розглянемо наступні особливості сегментного способу організації віртуальної пам’яті:

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

завантажувати;

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

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

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

52 Сегментно-сторінкова схема організації віртуальної пам'яті.

Метою організації сегментно – сторінкового механізму організації віртуальної пам’яті єуникнення недоліків сторінкового способу за рахунок збільшення накладних витрат на реалізаціюсегментно – сторінкового способу.

Так само як і у випадку з сегментами вся програма розділяється на логічно завершенічастини сегментів і віртуальна адреса містить вказівник на номер відповідного сегменту. Іншаскладова віртуальної адреси складається з двох частин: віртуальної сторінки та індексу.

Рис. 6.3. Сегментно - сторінкова схема організації віртуальної пам’яті.

РТС – регістр таблиці сегментів;

S – сегмент;

Р – сторінка;

І – індекс;

ТС – таблиця сторінок.

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

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

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

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

паралельних комп’ютерах. Такий механізм закладений і в процесорах Intel 80x86, але через високускладність організації такої системи він практично не використовується в сучасних ОС.

53 Реальний та захищений режими роботи мікропроцесора Intel.

Широко відомо, що першим мікропроцесором, на базі якого була створена IBM РС, був Intel8088. Цей мікропроцесор відрізнявся від першого 16-розрядного мікропроцесора фірми Intel —8086 — насамперед тим, що в нього була 8-бітова шина даних, а не 16-бітова (як у 8086). Обидваці мікропроцесори призначалися для створення обчислювальних пристроїв, які б працювали воднозадачному режимі, тобто спеціальних апаратних засобів для підтримки надійних і ефективнихмультипрограмних ОС у них не було. Однак на той час, коли розробники усвідомили необхідністьвключення в мікропроцесор спеціальної апаратної підтримки для мультипрограмних обчислень,вже було створено дуже багато програмних продуктів. Тому для сумісності з першимикомп'ютерами в наступних версіях мікропроцесорів була реалізована можливість використовувати

їх у двох режимах — реальному (real mode — так назвали режим роботи перших 16-бітовихмікропроцесорів) і захищеному (protect mode – означає, що рівнобіжні обчислення можуть бутизахищені апаратно-програмними механізмами).

Докладно розглядати архітектуру перших 16-бітових мікропроцесорів i8086/i8088 ми небудемо, оскільки цей матеріал повинен вивчатися в попередніх дисциплінах навчального плану.Однак нагадаємо, що в цих мікропроцесорах (а виходить, і в інших мікропроцесорах сімействаі80х86 при їх роботі у реальному режимі) звертання до пам'яті з можливим адресним простором у1 Мбайт здійснюється за допомогою механізму сегментної адресації (рис. 7.1). Цей механізм буввикористаний для збільшення кількості розрядів, що беруть участь у вказівці адреси коміркипам'яті, з якою у даний момент здійснюється робота, з 16 до 20 і тим самим збільшення обсягупам'яті.

Конкретизуємо задачу й обмежимося розглядом визначення адреси команди. Для адресаціїоперандів використовується аналогічний механізм, тільки беруть участь у цьому випадку іншісегментні регістри. Нагадаємо, що для визначення фізичної адреси команди вміст сегментногорегістра СS (code segment) перемножується на 16 за рахунок додавання cправа (до молодших бітів)чотирьох нулів, після чого до отриманого значення додається вміст покажчика команд (регістр ІР,instruction pointer). Виходить двадцатибітівое значення, що і дозволяє вказати будь-який байт із 220.Насправді, оскільки відбувається саме додавання і кожен з доданків може мати значення вінтервалі від нуля до 216-1 = 65535 – 64К, ми можемо вказати адресу початку сегмента, рівнийFFFFFFFF00Н, і до нього додати зсув FFFFFFFFН. У цьому випадку ми одержимо переповненнярозрядної сітки, але для сучасних 32-бітових процесорів (і для вже забутого i80286) маєтьсяможливість вказати перші 64Кбайт вище першого мегабайта.

Рис. 7.1 Схема визначення фізичної адреси для процесора 8086.

У захищеному режимі роботи визначення фізичної адреси здійснюється зовсім інакшеНасамперед використовується сегментний механізм для організації віртуальної пам'яті. При цьомуадреси задаються 32-бітовими значеннями. Крім цього, можлива сторінкова трансляція адрес,також з 32-бітовими значеннями. Нарешті, при роботі в захищеному режимі, що за замовчуваннямприпускає 32-бітовий код, можливе виконання подвійних програм, створених для роботимікропроцесора в 16-бітовому режимі. Для цього введений режим віртуальної 16-бітової машини і20-бітові адреси реального режиму транслюються за допомогою сторінкового механізму в 32-бітові значення захищеного режиму. Нарешті, є ще один режим — 16-бітовий захищений, щодозволяє 32-бітовим мікропроцесорам виконувати захищений 16-бітовий код, що був характернийдля мікропроцесора 80286. Правда, слід зазначити, що цей останній режим практично невикористовується, оскільки програм, створених для нього, не так вже і багато.Для вивчення цих можливостей розглянемо спочатку нові архітектурні можливостімікропроцесорів i80х86.

54 Нові системні регістри мікропроцесора Intel.

Основні регістри мікропроцесора і80x86, знання яких необхідно для розуміння захищеногорежиму роботи, приведені на рис. 7.2. Варто звернути увагу на наступне:

 покажчик команди ЕIP — 32 бітовий регістр, молодших 16 розрядів цього регістра єрегістр IP;

 регістр флагів EFLAGS — 32 біта, молодших 16 розрядів представляють регістрFLAGS;

 регістри загального призначення ЕАХ, ЕВХ, ЕСХ, EDX, а також ESP, EBP, ESI, EDI— 32-бітові, однак їх молодші 16 розрядів являють собою відомі регістри АХ, ВХ,СХ, DX, SP, BP, SI, DI;

 сегментні регістри CS, SS, DS, ES, FS, GS — 16-бітові. При кожному з регістрів CS,SS, DS, ES, FS, GS зображені пунктиром сховані від програмістів (недоступнінікому, крім власне мікропроцесора) 64-бітові регістри, у які завантажуютьсядескриптори відповідних сегментів;

 регістр-покажчик на локальну таблицю сегментів поточної задачі- - LDTR (16 бітів).При цьому регістрі також є «тіньовий» (схований від програміста) 64-бітовийрегістр, у який мікропроцесор заносить дескриптор, що вказує на таблицюдескрипторів сегментів задачі, що описують її локальний віртуальний адреснийпростір;

 регістр-покажчик задачі TR (task register, 16 бітів). Вказує на дескриптор углобальній таблиці дескрипторів, що дозволяє одержати доступ до дескрипторазадачі TSS2 — інформаційній структурі, що підтримує мікропроцесор для керуваннязадачами;

 регістр CDTR1 (48 бітів) глобальної таблиці GDT, що містить як дескрипторизагальних сегментів, так і спеціальні системні дескриптори. Зокрема, у GDTRзнаходяться дескриптори, з допомогу яких можна одержати доступ до сегментівTSS;

 регістр IDTR (48 бітів) таблиці дескрипторів переривань. Містить інформацію,необхідну для доступу до ”таблиці переривань” IDT;

 керуючі регістри CR0 - CR3 (32-бітові) і деякі інші регістри.

Керуючий регістр CR0 містить цілий ряд флагів, що визначають режими роботимікропроцесора. Самий молодший біт (РЕ, protect enable) цього регістра визначає режим роботипроцесора. При РЕ=0 процесор функціонує в реальному режимі роботи, а при одиничномузначенні мікропроцесор переключається в захищений режим. Самий старший біт регістра CR0 (бітPG, paging) визначає, включений (PG=1) чи немає (PG=0) режим сторінкового перетворення адрес.Регістр CR2 призначений для розміщення в ньому адреси підпрограми обробки сторінковоговиключення, тобто у випадку використання сторінкового механізму відображення пам'ятізвертання до відсутньої сторінки буде викликати перехід на відповідну підпрограму диспетчерапам'яті, і для визначення цієї підпрограми буде задіяний регістр CR2. Регістр CR3 містить номер

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

55 Підтримка сегментної схеми організації віртуальної пам'яті мікропроцесора Intel.

Як ми вже знаємо, для організації ефективної і надійної роботи обчислювальної системи в

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

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

 щоб існував загальний (розподілений) адресний простір.

Тому в мікропроцесорах і80x86 реалізований сегментний спосіб організації розподілу пам'яті.Крім цього, в цих мікропроцесорах може бути задіяна і сторінкова трансляція. Оскільки длякожного сегмента потрібний дескриптор, пристрій керування пам'яттю підтримує відповіднуінформаційну структуру. Полядескриптора (базова адреса, поле межі) розміщені в дескрипторі не безупинно, а в розбивку, по-перше, через те, що розробники постаралися мінімізувати кількість перехресних з'єднань внапівпровідниковій структурі мікропроцесора, а по-друге – внаслідок необхідності забезпечитиповну сумісність мікропроцесорів (попередній мікропроцесор і80286 працював з 16-бітовимкодом і теж підтримував сегментний механізм реалізації віртуальної пам'яті). Необхіднопомітити, що формат дескриптора сегмента, зображений на рис. 7.3, справедливий тільки длявипадку перебування відповідного сегмента в оперативній пам'яті. Якщо ж біт присутності вполі прав доступу рівний нулю(сегмент відсутній в памяті), то всі біти за виключенням поляправ доступу, вважаються невизначеними і можуть використовуватися системнимипрограмістами (для вказівки адреси сегмента в зовнішній пам'яті) довільним чином.

Локальний адресний простір задачі визначається через таблицю LDT (local descriptor table).У кожної задачі може бути свій локальний адресний простір. Загальний чи глобальний адреснийпростір визначається через таблицю GDT (global descriptor table). Само собою, що роботу з цимитаблицями (їхнє заповнення і наступну модифікацію) повинна здійснювати операційна система.Доступ до таблиць LDT і GDT з боку прикладних задач повинен бути неможливий.При переключенні мікропроцесора в захищений режим він починає працювати зовсім іншимчином, ніж у реальному режимі, обчислювати фізичні адреси команд і операндів. Насамперед,вміст сегментних регістрів інтерпретується інакше: вважається, що там міститься не адресапочатку сегмента, а номер відповідного сегмента. Для того щоб підкреслити цей факт, сегментнірегістри CS, SS, DS, ES, FS, GS у такому випадку навіть називаються інакше — селекторами

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

 поле індексу (index) — старші 13 бітів (3-15). Визначає власне номер сегмента (йогоіндекс у відповідній таблиці дескрипторів);

 поле індикатора таблиці сегментів (table index, TI) — біт з номером 2. Визначаєчастину віртуального адресного простору (загальне чи приналежне тільки данійзадачі). Якщо TI=1, то Index вказує на елемент у глобальній таблиці дескрипторівGDT, тобто йде звертання до загальної пам'яті. Якщо TI=1, то йде звертання долокальної області пам'яті поточної задачі; цей простір описується локальноютаблицею дескрипторів LDT;

 поле рівня привілеїв – біти 0 і 1. Вказує запитуваний рівень привілеїв (RPL, requested

privilege level).

Операційна система в процесі свого запуску ініціалізує багато регістрів і, насамперед, GDTR.Цей регістр містить початковий адрес глобальної таблиці дескрипторів (GDT) і її розмір. Як мивже знаємо, у GDT знаходяться дескриптори глобальних сегментів і системні дескриптори.Для маніпулювання задачами ОС має інформаційну структуру, що ми уже визначили якдескриптор задачі. Мікропроцесор підтримує роботу з найбільш важливою частиною дескрипторазадачі, що найменше залежить від операційної системи. Ця інваріантна частина дескриптора, зяким і працює мікропроцесор, названа сегментом стану задачі (task state segment, TSS). Перелікполів TSS зображений на рис. 7.5. Видно, що в основному цей сегмент містить контекст задачі.Процесор одержує доступ до цієї структури за допомогою регістра задачі (task register, TR).Регістр TR містить індекс (селектор) елемента в GDT. Цей елемент являє собою дескрипторсегмента TSS. Дескриптор заноситься в тіньову частину регістра (див. рис. 7.2). До розгляду TSSми ще повернемося, а зараз помітимо, що в одному з полів TSS міститься покажчик (селектор) налокальну таблицю дескрипторів даної задачі. При переході процесора з однієї задачі на іншу вмістполя LDTR заноситься мікропроцесором в однойменний регістр. Ініціалізувати регістр TR можна іявно.

Отже, регістр LDTR містить селектор, що вказує на один з дескрипторів глобальної таблиціGDT. Цей дескриптор заноситься мікропроцесором у тіньову частину регістра LDTR і описуєтаблицю LDT для поточної задачі. Тепер, коли в нас визначені як глобальна, так і локальнатаблиця дескрипторів, можна розглянути процес визначення лінійної адреси. Для прикладурозглянемо процес одержання адреси команди. Адреси операндів визначаються за аналогією, алезадіяні будуть інші регістри.

Мікропроцесор аналізує біт TI селектора коду й у залежності від його значення, витягає зтаблиці GDT чи LDT дескриптор сегмента коду з номером (індексом), що рівний полю index(біти 3-15 селектора, див. рис. 7.4). Цей дескриптор заноситься в тіньову (сховану) частинурегістра CS. Далі мікропроцесор порівнює значення регістра EIP (extended instruction pointer —покажчик інструкції команди) з полем розміру сегмента, що міститься у взятому дескрипторі, іякщо зсув відносно початку сегмента не перевищує розміру межі, то значення EIP додається дозначення поля початку сегмента і ми одержуємо шукану лінійну адресу команди. Лінійна адреса- це одна з форм віртуальної адреси. Вихідна двійкова віртуальна адреса, що обчислюєтьсявідповідно до використовуваної адресації, перетвориться в лінійну. В свою чергу, лінійна адресабуде дорівнювати або фізичному (якщо сторінкове перетворення відключене), або за допомогоюсторінкової трансляції перетвориться у фізичну адресу. Якщо ж зсув з регістра EIP перевищуєрозмір сегмента коду, то ця аварійна ситуація викликає переривання і керування повиннепередаватися супервізору ОС.

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

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

56 Підтримка сторінкової схеми організації віртуальної пам'яті мікропроцесора Intel.

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

створювати ці таблиці максимально можливого розміру. Розробники пішли по шляху, при якомурозмір сторінки все-таки невеликий (він обраний рівним 212 = 4096 = 4К), а поле номера сторінкизавбільшки 20 бітів, у свою чергу, розбивається на два поля і здійснюється двохетапна(двохкрокова) сторінкова трансляція.

Для опису кожної сторінки створюється відповідний дескриптор. Довжина дескриптораобрана рівною 32 бітам: 20 бітів лінійної адреси визначають номер сторінки (власне кажучи —її адресу, оскільки додавання до нього (приписування як молодші розряди) 12 нулів приводитьдо визначення початкової адреси сторінки), а інші біти розбиті на наступні поля, що зображеніна рис. 7.7. Як видно, три біти дескриптора зарезервовані для використання системнимипрограмістами при розробці підсистеми організації віртуальної пам'яті. З цими бітамимікропроцесор сам не працює.

Насамперед, мікропроцесор аналізує самий молодший біт дескриптора — біт присутності,тому що якщо поле present дорівнює нулю, то це означає відсутність даної сторінки в оперативнійпам'яті, і така ситуація призводить до переривання в роботі процесора з передачею керуваннявідповідній програмі, що повинна буде завантажити викликану сторінку. Біт dirty — «брудний» —призначений для оцінки, що дану сторінку модифікували і при заміщенні цього сторінковогокадру наступним її необхідно зберегти в зовнішній пам'яті. Біт звертання (access) свідчить про те,що до даної таблиці чи сторінки здійснювався доступ. Він використовується для визначеннясторінок), що буде брати участь у заміщенні при використанні дисциплін LRU чи LFU. Нарешті,перший і другий біти використовуються для захисту пам'яті.

Старші 10 бітів лінійної адреси визначають номер таблиці сторінок (раgе table entry, РТЕ), зякої за допомогою других 10 бітів лінійної адреси вибирається відповідний дескрипторвіртуальної сторінки. І вже з цього дескриптора вибирається номер фізичної сторінки, якщо данавіртуальна сторінка відображена зараз на оперативну пам'ять. Ця схема визначення фізичноїадреси по лінійному

Чорна таблиця, що ми індексуємо першими (старшими) 10 бітами лінійної адреси, названатаблицею каталогів таблиць сторінок (раge directory entry PDE). Її адреса в оперативній пам'ятівизначається старшими 20 бітами керуючого регістра CR3.

Кожна з таблиць PDE і РТЕ складається з 1024 елементів (210=1024). У свою чергу, коженелемент (дескриптор сторінки) має довжину 4 байти (32 біта), тому розмір цих таблиць самевідповідає розміру сторінки. Оцінимо тепер цю двохкрокову схему трансляції з позицій витратипам'яті. Кожен дескриптор описує сторінку розміром 4 Кбайт. Отже, одна таблиця сторінок, щомістить 1024 дескриптора, описує простір пам'яті в 4 Мбайт. Якщо наша задача користуєтьсявіртуальним адресним простором, наприклад, у 50 Мбайт (припустимо, що мова йде про деякийграфічний редактор, що обробляє зображення, що складається з великої кількості пікселів), тодля опису цієї пам'яті необхідно мати 14 сторінок, що містять таблиці РТЕ. Крім цього, нам будепотрібно для цієї задачі ще одна таблиця PDE (теж розміром в одну сторінку), у якій 14дескрипторів будуть вказувати на місцезнаходження згаданих таблиць РТЕ. Інші дескрипториPDE можуть бути не задіяні. Разом, для опису 50 Мбайт адресного простору задачі будепотрібно всього 15 сторінок, тобто 60 Кбайт пам'яті, що можна вважати прийнятним.Якби не був використаний такий двохкроковий механізм трансляції, то втрати пам'яті наопис адресного простору могли б скласти 4(Кбайт) * 210 = 4 (Мбайт)! Очевидно, що це вженеприйнятне рішення.

Отже, мікропроцесор для кожної задачі, для якої в нього є TSS, дозволяє мати таблицюPDE і деяку кількість РТЕ. Оскільки це дає можливість адресуватися до будь-якого байта з 232, ашина адреси саме і дозволяє використовувати фізичну пам'ять з таким обсягом, то можна як бивідмовитися від сегментного способу адресації. Іншими словами, якщо вважати, що завданняполягає з одного єдиного сегмента, що, у свою чергу, розбитий на сторінки, то фактично миодержуємо тільки один сторінковий механізм роботи з віртуальною пам'яттю. Цей підхід одержавназву «плоскої пам'яті». При використанні плоскої моделі пам'яті спрощується створення іопераційних системи, і систем програмування. Крім цього, зменшуються витрати пам'яті дляпідтримки системних інформаційних структур. Тому в абсолютній більшості сучасних 32-розрядних ОС, створюваних для мікропроцесорів i80x86, використовується плоска модель пам'яті

57 Режим віртуальної машини мікропроцесора Intel.

Розробники розглянутого сімейства мікропроцесорів у своєму прагненні забезпечитимаксимально можливу сумісність архітектури пішли не тільки на те, щоб забезпечити можливістьпрограмам, створеним для перших 16-розрядних ПК, без проблем виконуватися на комп'ютерах збільш пізніми моделями мікропроцесорів за рахунок введення реального режиму роботи. Вонитакож забезпечили можливість виконання 16-розрядних додатків реального режиму за умови, щосам процесор при цьому функціонує в захищеному режимі роботи й операційна система,використовуючи відповідні апаратні засоби мікропроцесора, організує мультипрограмний(мультизадачний) режим. Іншими словами, мікропроцесори i80x86 підтримують можливістьстворення операційних середовищ реального режиму при роботі мікропроцесора в захищеномурежимі. Якщо умовно назвати 16-розрядні додатки DOS-додатками (оскільки в абсолютнійбільшості випадків це саме так), то можна сказати, що введено підтримку для організаціївіртуальних DOS-машин, що працюють разом зі звичайними 32-бітовими додатками захищеногорежиму. Це навіть знайшло відображення в назві режиму роботи мікропроцесорів і80x86 —режим віртуального процесора i8086, іноді (для стислості) його називають режимом V86 чи просто віртуальним режимом, — при якому у захищеному режимі роботи може виконуватися код DOS-додатка. Мультизадачність при виконанні декількох програм реального режиму буде підтриманаапаратними засобами захищеного режиму.

Перехід у віртуальний режим здійснюється за допомогою зміни біта VM (virtual mode) урегістрі EFLAGS. Коли процесор знаходиться у віртуальному режимі, для адресації пам'ятівикористовується схема реального режиму роботи - (сегмент: зсув) з розміром сегментів до 64Кбайт, що можуть розташовуватися в адресному просторі розміром у 1 Мбайт, однак отриманіадреси вважаються не фізичними, а лінійними. У результаті застосування сторінкової трансляціїздійснюється відображення віртуального адресного простору 16-бітового додатка на фізичнийадресний простір. Це дозволяє організувати рівнобіжне виконання декількох задач, розробленихдля реального режиму, так ще і разом зі звичайними 32-бітовими додатками потребуючих

захищеного режиму роботи.

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

Питання, зв'язане з операціями введення/виведення, які недоступні для звичайнихдодатків, зважується аналогічно. При спробі виконати неприпустимі командивведення/виведення виникають переривання, і необхідні операції виконуються операційноюсистемою, хоча задача про цьому і «не підозрює». При виконанні команд IN, OUT, INS, OUTS,CLI, STI процесор, що знаходиться у віртуальному режимі і виконує код на рівні привілеївтретього (самого нижнього) кільця захисту, за рахунок виникаючих внаслідок цього перериваньпереводиться на виконання високо привілейованого коду операційної системи.Таким чином, ОС можуть цілком віртуалізувати ресурси комп'ютера: і апаратні, іпрограмні, створюючи інше повноцінне операційне середовище; при існуванні так званихнативних додатків, створюваних по власних специфікаціях даної ОС. Дуже важливим моментомдля організації повноцінної віртуальної машини є реалізація віртуалізації не тількипрограмних, але й апаратних ресурсів. Так, наприклад, в ОС Windows NT ця задача виконанаявно невдало, тоді як у OS/2 є повноцінна віртуальна машина як для DOS-додатків, так і длядодатків, що працюють у середовищі специфікацій Win16. Правда, останнім часом це вжеперестало бути актуальним, оскільки з'явилася велика кількість додатків, що працюють поспецифікаціях Win32 API.

58 Рівні привілеїв мікропроцесора Intel.

Для того щоб заборонити користувацьким задачам модифікувати області пам'яті, щоналежать самій ОС, необхідно мати спеціальні засоби. Одного розмежування адресних просторівчерез механізм сегментів мало, тому що можна вказувати різні значення адреси початку сегмента ітим самим одержувати доступ до чужих сегментів. Іншими словами, необхідно в явному видірозмежовувати системні сегменти даних і коду від сегментів, що належать користувацькимпрограмам. Тому були введені два основних режими роботи процесора: користувача і супервізора.Більшість сучасних процесорів мають принаймні два цих режими. Так, у режимі супервізора програма може виконувати всі дії і мати доступ до будь-яких адресів, тоді як у режимікористувача повинні бути обмеження, для того щоб виявляти і припиняти заборонені дії,перехоплюючи їхній і передаючи керування супервізору ОС. Часто і режиму користувачазабороняється виконання команд введення/виведення і деяких інших, щоб гарантувати, що тільки

ОС виконує ці операції. Можна сказати, що ці два режими мають різні рівні привілеїв.У мікропроцесорах i80x86 маються не два, а чотири рівні привілеїв. Часто рівні привілеївназивають кільцями захисту, оскільки це іноді допомагає пояснити принцип дії самого механізму;тому говорять, що деякий програмний модуль «виконується в кільці захисту з таким-то номером».Для вказівки рівня привілеїв використовуються два біти, тому код 00 позначає самий вищийрівень, а код 11 (=3) — самий нижчий. Найвищий рівень привілеїв призначений для операційноїсистеми (насамперед, для ядра ОС), найнижчий — для прикладних задач користувача. Проміжнірівні привілеїв введені для більшої свободи системних програмістів в організації надійних обчисленьпри створенні ОС і іншого системного ПЗ. Передбачалося, що рівень з номером (кодом) 1 може бутивикористаний, наприклад, для системного сервісу — програм обслуговування апаратури, драйверів,що працюють з портами введення/виведення. Рівень привілеїв з кодом 2 може бути використаний длястворення користувацьких інтерфейсів, систем керування базами даних і т.п., тобто для реалізаціїспеціальних системних функцій, що стосовно супервізора ОС поводяться як звичайні додатки. Так,наприклад, система OS/2 використовує три рівні привілеїв: з нульовим рівнем привілеїв виконуєтьсякод самої ОС, на другому рівні виповнюються системні процедури підсистеми введення/виведення, натретьому рівні виповнюються прикладні задачі користувачів. Однак найчастіше на практицівикористовуються тільки два рівні — нульової і третій. Таким чином, згаданий режим супервізора для

мікропроцесорів і80x86 відповідає виконанню коду з рівнем привілеїв 0 (його позначають так: PL0 –privilege level). Підводячи підсумок, можна констатувати, що саме рівень привілеїв задач визначає,які команди в них можна використовувати і яка підмножина сегментів і/чи сторінок у їхньомуадресному просторі вони можуть обробляти.

Основними системними об'єктами, якими маніпулює процесор при роботі в захищеномурежимі, є дескриптори. Дескриптори сегментів містять інформацію про рівень привілеювідповідного сегмента чи коду даних. Рівень привілею задачі, що виконується, визначаєтьсязначенням поля привілею, що знаходиться в дескрипторі її поточного кодового сегмента. Нагадаємо,що в кожному дескрипторі сегмента (див. рис.7.3) є поле DPL у байті прав доступу, що і визначаєрівень привілею зв'язаного з ним сегмента. Таким чином, поле DPL поточного сегмента коду стаєполем CPL. При звертанні до якого-небудь сегмента і відповідному селекторі вказується запитуванийрівень привілеїв RPL (див. рис. 7.4).

У межах однієї задачі використовуються сегменти з різним рівнем привілею й у визначенімоменти часу виконуються чи обробляються сегменти з відповідними їм рівнями привілею.Механізм перевірки привілеїв працює в ситуаціях, які можна назвати міжсегментними переходами(звертаннями). Це доступ до сегмента даних чи стековому сегменту, міжсегментні передачікерування у випадку переривань (і особливих ситуацій), при використанні команд CALL, JMP, INT,IRET, RET. У таких міжсегментних звертаннях беруть участь два сегменти: цільовий сегмент (до якогоми звертаємося) і поточний сегмент коду, з якого йде звертання.Процесор порівнює згадані значення CPL, RPL, DPL і на основі поняття ефективного рівняпривілеїв (EPL = max (RPL, DPL)) обмежує можливості доступу до сегментів за наступнимиправилами, у залежності від того, чи йде мова про звертання до коду чи до даних.