• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

Детальніше про алгоритм Деккера – самостійно!

5. Команда “перевірка” та “встановлення”.

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

Розглянемо гіпотетичну команду TS (test and set), дія якого полягає в тому, що першій змінні key 1 присвоюється значення key 2 (з прикладу питання 3), після чого другій змінні key 2 присвоюється 1. Команда TS є неподільною командою, тобто між початком виконання цієї команди і її завершенням не можуть виконуватися ніякі інші команди. Введемо змінну common, яка буде загальною змінною для двох (всіх) процесів, які використовують деякі критичні ресурси. Common=1, якщо будь – який із взаємодіючих процесів знаходиться у своїй критичній секції. Також з кожним процесом зв’яжемо локальну змінну local 1, local 2. Вони будуть дорівнювати 1, якщо певний процес бажає ввійти у свою критичну секцію.

Приклад.

var local1, local2, common: integer

begin

common:=0

par begin

PR1:

begin local1:=1

while local1=1 do TS(local1, common)

CS1:

common:=0

end

and

PR2:

begin local2:=1

while local2=1 do TS(local2,common)

CS2:

common:=0

end

par end

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

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

Вирішення задачі “виробник – споживач” за допомогою семафорів.

Для вирішення цієї задачі розподілювальними змінними є лічильники вільних та зайнятих буферів пам’яті, які повинні бути захищені зі сторони обох процесів. Тобто дії по відправленні і отриманні повідомлень повинні бути синхронізовані. Семафори S – free, S – fil – в даному випадку є числовими, семафор S – exp – двійковим.

Приклад.

var S-free, S-fil, S-exp: semaphore;

begin

InitSem (s-free, N);

InitSem (s-fil, 0);

InitSem (s-exp, 1);

parbegin

PROCEDURE: while true do

begin

{підготовка повідомлень}

P(S-free);

P(S-fil);

{послати повідомлення}

V(S-fil);

V(f-exp);

end;

and

CONSUMER: while true do

P(S-fil);

P(S-exp);

{отримати повідомлення}

V(S-free);

V(S-exp);

{обробка повідомлень}

parend

end

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

Операція P(S – free) зменшує значення S - free на одиницю. Операція V(S – free) збільшує значення лічильника S - free на одиницю.

Перед відправою повідомлення процес виробник зменшує значення S – fil на одиницю, а після відправки повідомлення збільшує значення S – fil на одиницю. Так само перед отриманням повідомленням процес споживач зменшує значення S – fil на одиницю шляхом виконання операції P(S – fil), а після отримання повідомлення збільшує значення семафору S – free в результаті виконання операції V(S – free).

Вирішення задачі читачів – письменників за допомогою семафорів – самостійно!

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

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

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

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

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

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

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

· наявність всіх розділювальних змінних в тілі монітора, що дозволяє їх виключити з вихідних модулів паралельних процесів;

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

8. Поштові ящики.

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

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

Технічна реалізація поштових ящиків в ОС Windows – самостійно!

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

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

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

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

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

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

9. Конвеєри.

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

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

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

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

10. Черги повідомлень.

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

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

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

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

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

Тема 5. Керування реальною пам’яттю

1. Підходи до керування реальною пам’яттю.

2. Неперервний розподіл оперативної пам’яті.

3. Розподіл з перекриттям.

4. Статичний розподіл пам’яті.

5. Динамічний розподіл пам’яті.

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

7. Розділи пам’яті зі змінними розмірами.

1. Підходи до керування реальною пам’яттю.

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

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

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

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

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

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

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

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

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

2. Неперервний розподіл оперативної пам’яті.

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

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

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

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

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

3. Розподіл з перекриттям.

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

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

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

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

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

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

4. Статичний розподіл пам’яті.

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

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

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

buffer db 1024 dup(?)

5. Динамічний розподіл пам’яті.

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

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

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

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

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

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

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

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

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

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

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

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

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

7. Розділи пам’яті зі змінними розмірами.

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

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

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

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

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

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

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

Тема 6. Керування віртуальною пам’яттю

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S – сегмент;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S – сегмент;

Р – сторінка;

І – індекс;

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

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

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

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

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

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

Тема 7. Архітектурні особливості мікропроцесорів Intel 80x86.

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

2. Нові системні регістри мікропроцесорів і80x86.

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

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

5. Режим віртуальних машин для виконання додатків реального режиму.

Читайте також:

1. Rete-алгоритм
2. Алгоритм
3. Алгоритм
4. Алгоритм 1.
5. Алгоритм RLE
6. Алгоритм безпосередньої заміни
7. Алгоритм Берлекемпа-Мессі
8. Алгоритм відшукання оптимального плану.
9. Алгоритм Дейкстри.
10. Алгоритм Деккера.
11. Алгоритм діагностики при травмах живота.

Переглядів: 2005