Планування ресурсу Оперативна память

РЕФЕРАТ

На тему:

Планування ресурсу „Оперативна пам’ять”


1. Оперативна пам’ять  

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

Отже, ОС виконує такі функції, зв'язані з управлінням задачами:

• Створення та знищення задач;

• Формування процесів і диспетчеризація задач;

• Синхронізація задач.

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

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

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

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

        Функції ОС по управлінню пам’яттю 

	Відстежування вільної і зайнятої пам’яті.

		Виділення пам’яті процесам і звільнення пам’яті після завершення процесу. 

	Виштовхування кодів і даних процесів із ОП на диск, коли розміри ОП недостатні для розміщення в ній всіх процесів і повернення процесів в ОП, коли в ній достатньо місця. Ї

		Наладка адрес програми на конкретну область фізичної пам’яті. 

	Дефрагментація пам’яті. 

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

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

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

На виконання операцій перезарядження іде визначений час, через що швидкість роботи динамічної пам'яті знижується. Крім того, час збереження заряду конденсатора обмежено, тому щоб збережена інформація не спотворювався, необхідно її періодичне перевстановлення. Воно виконується в спеціальних циклах регенерації (Refresh cycle). Час доступу до динамічної пам'яті приблизно в 3-4 рази менше такту роботи ЦП.

Існує пам'ять статичного типу, у якій інформація зберігається на статичних тригерах. Для статичної пам'яті не потрібні цикли регенерації й операції перезарядження. Час доступу до статичної пам'яті істотно менше, ніж до динамічної пам'яті. Швидкодія використовуваної ОП багато в чому визначає швидкість роботи процесора і впливає на продуктивність усієї системи. Однак для реалізації одного запам'ятовуючого елемента динамічної пам'яті потрібно 1-2 транзистора, для статичної - 4-6 транзисторів. Відповідно вартість статичної пам'яті істотно вище вартості динамічної пам'яті, а виконання ОЗП на елементах статичної пам'яті приводить до значного подорожчання ПК.

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

Конструктивно ОП виконується в даний час у виді SIMM-корпусів з однорядним розташуванням контактів (Single In line Memory Module). Для підключення до системної плати на них мається спеціальне друковане рознімання. Останнім часом з'явилися нові корпуси пам'яті DIММ (Dual In line Memory Module) з дуже малим часом звертання.

Існують різні типи модулів пам'яті: FРМ DRАМ - зі швидким посторінковим доступом, ЕDО DRАМ - зі значно меншим часом завантаження даних у порівнянні з FРМ DRАМ, SD RАМ (Synchronous Dynamic RAM) - новий тип пам'яті, що приходить на зміну FРМ DRАМ і EDO DRАМ, він дозволяє працювати зі швидкістю системной шини. Для різних системних плат передбачена можливість використання модулів пам'яті того чи іншого типу.

У сучасних ПК мається, як правило, постійний запам'ятовуючий пристрій (ПЗП), чи ROM (Read Only Memory). Найважливішою функцією цієї пам'яті є збереження ВIOS (Basic Input Output System) - базова система в/в). ВIOS забезпечує інваріантість програмних засобів до архітектури системної плати і містить необхідний набір програм в/в, що забезпечують роботу периферійних пристроїв.

Крім програм в/в в ПЗП містяться програма тестування Р0SТ (Power On Self Test) і програма початкового завантажника, що виконує функцію завантаження ОС з диска.

Звичайно ВIOS зберігається в мікросхемах так званого масочного ПЗП: інформація в них записується один раз при виготовленні мікросхем. 

Крім того, у ПК є пам'ять з незалежним живленням (від батарейки), названа СМ0S RАМ (Complementary Metal Oxide Semiconductor), обсягом 256 байт. Ця пам'ять не відображається в адресному просторі мікропроцесора, а служить для збереження даних про поточні параметри (параметри твердих дисків, ОП, мікропроцесора показання годин і т.д.). При необхідності вміст СМ0S RАМ можна скорегувати.

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

1. 2. Типи адрес

Для ідентифікації змінних і команд використовуються символьні імена (мітки), ВА і фізичні адреси (малюнок 16). 

Символьні імена надає користувач при написанні програми  алгоритмічною мовою чи на асемблері. 

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









Символьні імена  Ідентифікатори перемінних в 

програмі на алгоритмічній мові										

Транслятор					





Віртуальні адреса	Віртуальні адреса які виробляються 

транслятором





Фізичні адреса1) Завантажувач що переміщається 

статистичне перетворення 			

2) Динамічне перетворення 

апаратними засобами 



Номер комірок фізичної пам’яті  	



Рис. 16. Типи адрес

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

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

1.3. Пам'ять і відображення

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

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

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








Логічне (символьне) ім’я																		Простір імен програми







Віртуальний адрес

Комірка оперативної пам’яті

(фізичний адрес)

Операційна система

Система програмуванняВіртуальний адресний простір																																																																																																						

							          			Фізична пам’ять комп’ютера 













Рис. 17. Пам'ять і відображення

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

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

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

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

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

- обсяг ВАП програми Vv менше обсягу фізичної пам'яті Vp;

- Vv = Vp; 

-Vv > Vp.

Перша ситуація, при якій Vv < Vp, нині практично не зустрічається, але проте це реальне співвідношення. Скажемо, не дуже давно 16-розрядні міні-ЕОМ мали систему команд, у яких користувачі-програмісти могли адресувати до 216°(64) До адрес (звичайно в якості адресованій одиниці виступала комірка пам'яті розміром з байт). А фізично старші моделі цих міні-ЕОМ могли мати обсяг ОП в трохи мегабайт. Звертання до пам'яті настільки великого обсягу здійснювалося за допомогою спеціальних регістрів, вміст яких складався з адреси операнда (чи команди), що витягається і/чи обумовленим з поля чи операнда (чи з покажчика команди). Відповідні значення в ці спеціальні регістри, що виступають як базовий зсув у пам'яті, заносила ОС. Для однієї задачі в регістр заносилося одне значення, а для другої третьої, четвертої і т.д. задачі, розташовуваної одночасно з першої, але в іншій області пам'яті, заносилося, відповідно, інше значення. Уся фізична пам'ять, таким чином, розбивалася на розділи обсягом по 64 Кбайт, і на кожен такий розділ здійснювалося відображення свого ВАП.

Ситуація, коли Vv = Vp зустрічалася досить часто, особливо характерна вона була для недорогих обчислювальних комплексів. Для цього випадку мається велика кількість методів розподілу ОП.

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



1.4. Свопінг

Свопінг – алгоритм реалізації віртуальної пам'яті. Його можна розбити на три  частини:  керування простором на пристрої вивантаження, вивантаження процесів з основної пам'яті і підкачування процесів в основну пам'ять. Як пристрій вивантаження використовують розділ на пристрої типу твердого (swap-partition) чи дисковий файл (swap-file) на такому пристрої.

Свопінг є різновидом ВП. 

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







Рис. 18. Залежність завантаження процесора від числа задач і інтенсивності в/в.

З рисунка видно, що для завантаження процесора на 90% досить всього трьох рахункових задач. Однак для того, щоб забезпечити таке ж завантаження інтерактивними задачами, що виконують інтенсивне в/в, будуть потрібні десятки таких задач. Необхідною умовою для виконання задачі є завантаження її в ОП, обсяг якої обмежений. У цих умовах був запропонований метод організації обчислювального процесу, названий свопінгом. Відповідно до  цього методу деякі процеси (звичайно знаходяться в стані чекання) тимчасово вивантажуються на диск. Планувальник ОС не виключає їх зі свого розгляду, і при настанні умов активізації деякого процесу, що знаходиться в області свопінга на диску, цей процес переміщається в ОП. Якщо вільного місця в ОП не вистачає, то вивантажується інший процес. 

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

2. Оверлейні структури програм

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

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

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

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

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

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







Сегментно-сторі-нковий розподіл

З використанням зовнішньої пам’яті

Сегментний розподіл

Сторінковий розподіл 

Динамічними розділами

Без використання зовнішньої пам’яті

Фіксованими розділами

Переміщуваними розділами

Способи розподілу пам’яті



























Рис. 19. Класифікація методів розподілу пам'яті

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

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



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



а - із загальною чергою; б - з окремими чергами

Підсистема керування пам'яттю в цьому випадку виконує наступні задачі: 

· порівнюючи розмір програми, що надійшла на виконання, і вільних розділів, вибирає придатний розділ, 

· здійснює завантаження програми і настроювання адрес. 

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

3. 2. Розподіл пам'яті розділами змінної величини

У цьому випадку пам'ять машини не поділяється заздалегідь на розділи. Спочатку вся пам'ять вільна. Кожній знову поступаючій задачі виділяється необхідна їй пам'ять. Якщо достатній обсяг пам'яті відсутній, то задача не приймається на виконання і стоїть в черзі. Після завершення задачі пам'ять звільняється, і на це місце може бути завантажена інша задача. Таким чином, у довільний момент часу ОП являє собою випадкову послідовність зайнятих і вільних ділянок (розділів) довільного розміру. На рис.21 показаний стан пам'яті в різні моменти часу при використанні динамічного розподілу. Так в момент t0 у пам'яті знаходиться тільки ОС, а до моменту t1 пам'ять розподілена між 5 задачами, причому задача П4, завершуючись, залишає пам'ять. На звільнене після задачі П4 місце завантажується задача П6, що надійшла в момент t3. 





Рис.21. Розподіл пам'яті динамічними розділами



Задачами ОС при реалізації даного методу керування пам'яттю є: 

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

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

· завантаження задачі у виділений їй розділ і коректування таблиць вільних і зайнятих областей; 

· після завершення задачі коректування таблиць вільних і зайнятих областей. 

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

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

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

3. 3. Розподіл пам'яті переміщуваними розділами

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



Рис. 22. Розподіл пам'яті переміщуваними розділами



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

4. Методи розподілу пам'яті з використанням дискового простору.

4.1. Поняття віртуальної пам'яті.

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

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

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

 Для цього ВП вирішує наступні задачі: 

-  розміщує дані в ЗП різного типу, наприклад, частина програми в ОП, а частина на диску; 

- переміщує по мірі необхідності дані між ЗП різного типу, наприклад, завантажує потрібну частину програми з диска в ОП; 

   - перетворює ВА у фізичні. 

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

Найбільш розповсюдженими реалізаціями ВП є сторінковий, сегментний і сторінково-сегментний розподіл пам'яті, а також свопінг. 

4.2. Сторінковий розподіл

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

Вся ОП машини також поділяється на частині такого ж розміру, називані фізичними сторінками (чи блоками). 

Розмір сторінки звичайно вибирається рівним ступеня двійки: 512, 1024 і т.д., це дозволяє спростити механізм перетворення адрес. 

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

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

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

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

· довше всього не використовувалася сторінка, 

· перша  сторінка, що зустрілася, 

· сторінка, до якої останнім часом  було найменше  звертань. 

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

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

Розглянемо механізм перетворення ВА у фізичний при сторінковій організації пам'яті (рис. 23). 

ВА при сторінковому розподілі може бути представлений у виді пари (p, s), де p - номер віртуальної сторінки процесу (номерація сторінок починається з 0), а s - зсув у межах віртуальної сторінки. З огляду на те, що розмір сторінки дорівнює 2 у ступені до, зсув s може бути отримано простим відділенням k молодших розрядів у двійеовому записі ВА.  Старші розряди, що залишилися, являють собою двійковий запис номера сторінки p. 




Віртуальний адрес 		   k двійкових розділів  



Номер віртуальної сторінки - р

Зміщення у віртуальній сторінці - S











№ віртуальної сторінки

№ фізичної сторінки









 p

n









       

 	   Розмір сторінки 2k

















Номер фізичної сторінки - n

Зміщення у фізичній

 сторінці - S







 	

Фізичний адрес	 	    k двійкових розрядів

 

Рис. 23. Механізм перетворення віртуальної адреси у фізичний

при сторінковій організації пам'яті

При кожному звертанні до ОП апаратними засобами виконуються наступні дії: 

1. на підставі початкової адреси таблиці сторінок (вміст регістра адреси таблиці сторінок), номера віртуальної сторінки (старші розряди ВА) і довжини запису в таблиці сторінок (системна константа) визначається адресу потрібного запису в таблиці; 

2. з цього запису витягається номер фізичної сторінки; 

3. до номера фізичної сторінки приєднується зсув (молодші розряди віртуальної адреси). 

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

На продуктивність системи зі сторінковою організацією пам'яті впливають тимчасові витрати, зв'язані з обробкою сторінкових переривань і перетворенням ВА у фізичну. При часто виникаючих сторінкових перериваннях система може витрачати велику частину часу, на свопінг сторінок. Щоб зменшити частоту сторінкових переривань, варто було б збільшувати розмір сторінки. Крім того, збільшення розміру сторінки зменшує розмір таблиці сторінок, а значить зменшує витрати пам'яті. З іншого боку, якщо сторінка велика, значить велика і фіктивна область в останній віртуальній сторінці кожної програми. У середньому на кожній програмі губиться половина обсягу сторінки, що в сумі при великій сторінці може скласти істотну величину. Час перетворення ВА у фізичну у значній мірі визначається часом доступу до таблиці сторінок. У зв'язку з цим таблицю сторінок прагнуть розміщати в "швидких" ЗП. Це може бути, наприклад, набір спеціальних регістрів чи регістрів пам'ять, що використовує для зменшення часу доступу асоціативний пошук і кешування даних. 

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

4.3. Сегментний розподіл

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

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

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






ОСВіртуальний адресний          



Сегмент 0

процесу Апростір процесу А                 	Таблиця сегментів 



Сегмент 0        процесу А 

0



1



2

3

Вивантажений

Вивантажений



Сегмент 1





Сегмент 2





Сегмент 3





Сегмент 1 процесу А і

сегмент 2 процесу В



                               Розділений 

   сегмент 



Віртуальний адресний 

простір процесу В		Таблиця сегментів



Сегмент 2

Сегмент 1

Сегмент 0        процесу В

0



1

Вивантажений

2







Сегмент 0

процесу В











Рис. 24. Розподіл пам'яті сегментами

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

ВА при сегментній організації пам'яті може бути представлений парою (g, s), де g - номер сегмента, а s - зсув у сегменті. Фізична адреса виходить шляхом додавання початкової фізичної адреси сегмента, знайденого в таблиці сегментів по номері g, і зсуву s. 

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

4.4. Сторінково-сегментний розподіл

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

Віртуальний адрес (g , p , S)



№ віртуальної сторінки - р

Зміщення - S

№ сегмента -  g





				

				

	   Таблиці сегментів



	



g	

												     

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

							сегменту g

						  



n

р











Зміщення - S

№ фізичної сторінки - n





Фізичний адрес

Рис. 25. Схема перетворення віртуальної адреси у фізичну для

сегментно-сторінкової організації пам'яті



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

5.1. Організація ВП

ВП відрізняється від звичайної ОП тим, що якісь її рідко використовувані фрагменти можуть знаходитися на диску і довантажуватися в реальну ОП у міру необхідності. Така організація пам'яті дозволяє зняти обмеження, що накладається обсягом фізичної пам'яті, установленої на ЕОМ. Для реалізації ВП використовують, наприклад, динамічну переадресацію. Сегментом у термінах ВП називається область пам'яті з 2L сторінок. Спочатку по номеру в таблиці сегментів відшукується сегмент. Таблиця сегментів містить початкову адресу таблиці сторінок. Друга частина адресу використовується для звертання в цю таблицю, і по ній знаходиться фізичний адрес даної сторінки. Результати пошуку по таблицях запам'ятовуються у швидкодіючому асоціативному ЗП, названому TLB. Найбільш часто вживані адреси відкладаються в TLB і тому 98-99% звертань до пам'яті йдуть без перегляду таблиць.

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

Кожен сегмент має зв'язок з дисковим простором, на якому зберігаються дані, відображувані в даний сегмент ВАП. Це може бути чи файл частина файлу на диску, чи ж це може бути область свопінгу, що файлом не є. Сегмент чи сегмент коду ініціалізованих даних звичайно зв'язаний з файлом, у якому зберігається програма, що виконується. Під зв'язком з файлом розуміється відображення віртуального сегмента і його сторінок на визначену область диска, з якої завантажуються дані віртуальних сторінок сегмента при їхньому переміщенні в ОП, а також куди містяться дані при витисненні віртуальних сторінок на диск. Віртуальні сторінки, що були споконвічно узяті з визначеного файлу, називаються vnode-сторінками, а сторінки, що з'явилися тільки при розгортанні процесу (а це звичайно сторінки чи стека неініціалізованих сегментів даних) - анонімними сторінками. Однак анонімні сторінки також мають зв'язок з файлом, у який вони виштовхуються при їхньому витисненні з фізичної пам'яті (так званий свопінг-прилад). На свопінг-прилад також указує vnode, тому в цій якості може виступати будь-як файл, а переміщення сторінок зі свопінг-прилад в пам'ять здійснюється тими ж функціями, що використовуються для vnode-сторінок. 

	 	Віртуальний адресний простір. Теоретично будь-який ВАП може бути розрідженим, так що здатність використовувати велику кількість розкиданих секцій не є в дійсності властивістю архітектури ВП. Іншими словами, будь-яка 32-х бітна машина повинна дозволяти процесу мати 50 000 секцій даних, розділених проміжками по 100 Мбайт, у межах від 0 до 4 Гбайт. Однак, у багатьох реалізаціях лінійна сторінкова таблиця від 0 до самої старшої використовуваної сторінки зберігається в пам'яті ядра. На машині з розміром сторінки в 1 Kб. ця конфігурація вимагає 4 мільйони елементів таблиці сторінок, роблячи таку схему дуже дорогою. Навіть при багаторівневій організації сторінкової таблиці така розрідженість у кращому випадку неприйнятна. Наприклад у ядрі Mach ОC UNIX при його розробці споконвічно ставилася задача повної підтримки розріджених адресних просторів. 







Мал. 26. Адресний простір із призначеними областями, 
відображеними об'єктами і не використовуваними адресами



Ключовим поняттям, зв'язаним з використанням ВАП, є об'єкт пам'яті (memory object). Об'єкт пам'яті може бути сторінкою чи набором сторінок, а також може бути файлом чи більш спеціальною структурою даних, наприклад, записом БД. Об'єкт пам'яті може бути відображений у не використовувану частину ВАП, формуючи нову область, як це показано на рис.26. Коли файл відображений у ВАП, то його можна читати в нього чи можна писати за допомогою звичайних машинних команд. Відображені (mapped) файли посторінково витісняються з пам'яті звичайним чином. Коли процес завершується, то його відображені в пам'ять файли автоматично повертаються у ФС разом із усіма змінами, що відбулися з їхнім змістом у той час, коли вони були відображені в пам'ять. Також можливо скасувати відображення файлу іншого об'єкта пам'яті, звільняючи його адресний простір і роблячи його доступним для послідовного його розподілу відображення. 

Звичайно, відображення файлів у пам'ять не єдиний спосіб доступу до них. Їхній вміст можна читати і звичайним способом. Однак і в цьому випадку бібліотечні функції можуть відображати файли в пам'ять крім бажання користувача, а не використовувати систему в/в. Такий спосіб дозволяє сторінкам файлів використовувати систему ВП, а не спеціально виділені буфери де-небудь у системі. 


Таблиця 
Примітиви для керування віртуальним адресним простором 

Виклик 

Опис 

Allocate 

Робить область віртуального адресного простору використовуваною

Deallocate 

Звільняє область віртуального адресного простору 

Map 

Відображає об'єкт пам'яті у віртуальний простір 

Copy 

Копіює область в інший діапазон віртуальних адрес 

Inherit 

Встановляє атрибут спадкування для області 

Read 

Читає дані з адресного простору іншого процесу 

Write 

Записує дані в адресний простір іншого процесу 



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

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

Виклик Inherit впливає на спосіб спадкування областю властивостей при створенні нового процесу. Адресний простір може бути сконфігурованим так, що деякі області будуть успадковувати властивості, а деяких немає. Виклики Read і Write дозволяють одержати доступ до віртуальної пам'яті, що відноситься до іншого процесу. 

5.2. Стратегії: переміщення ардес по вимозі, заміщення сторінок та 

звільнення зайнятих сторінок

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

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

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

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

		програма може виконуватися CPU, коли частина сторінок знаходиться в основній пам’яті, а частина – в зовнішній;     

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

     Для врахування розподілу сторінок між зовнішньою і основною пам’яттю кожен рядок таблиці сторінок доповнюється бітом місцезнаходження сторінки (valid/invalid bit). 

     В тому випадку, коли процесор намагається використати сторінку, яка помічена значенням invalid , виникає подія, яка називається сторінкова недостатність (paging fault). 

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

     Основні етапи обробки сторінкової недостатності: 

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

		Якщо значення біта invalid, то процес переривається і керування передається ОС і для обробки події сторінкової недостатньості. 

		Відшуковується необхідна сторінка у другорядній пам’яті і вільна сторінкова рамка в основній. 

		Потрібна сторінка загружається в вибрану сторінкову рамку. 

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

		Керування передається перерваному процесу. 

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

     Другорядна пам’ять, яка використовується при обміні сторінок по вимозі,- це високошвидкісний дисковий пристрій, яке часто називають обладнанням свопінгу (swap device), а частину використовуваного дискового простору – простором свопінгу (swap space). 

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

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

     Обробка сторінкової недостатньості з врахуванням заміщення проводиться по наступному алгоритму: 

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

якщо значення біту invalid, то йде пошук вільної сторінкової рамки; 

якщо є вільна сторінкова рамка, то вона використовується; 

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

сторінка-жертва переміщається в простір свопінгу і таблиця сторінок редагується; 

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

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

сторінка-жертва переміщується в простір свопінга; 

потрібна сторінка переміщається в сторінкову рамку, яка звільнилась. 

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

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

     Для практичного використання методу обміну сторінок по вимозі необхідні два алгоритми: 

алгоритм розподілу сторінкових рамок (frame allocation algorithm); 

алгоритм заміщення сторінок (page replacement algorithm). 





5.3. Алгоритми розподілу сторінкових рамок

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

     FIFO (first-in-first-out). Найбільш простим алгоритмом заміщення сторінок є алгоритм FIFO. Цей алгоритм асоціює з кожною сторінкою час, коли ця сторінка була поміщена в пам’ять. Для заміщення вибирається найбільш стара сторінка. 

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

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

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

     Алгоритм LRU (least recently used). Алгоритм вибирає для заміщення ту сторінку, на яку не було посилання на протязі найдовшого періоду часу. Він асоціює з кожною сторінкою час останнього використання цієї сторінки. Для заміщення вибирається та сторінка, яка не використовувалась довше за інші. Зазвичай застосовуються два підходи при використанні цього алгоритму: 

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

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

     Алгоритм LFU (least freqently used). Цей алгоритм заміняє ту сторінку, яка використовується найменш частіше. Спосіб упорядкування схожий на LRU.

     Також можливий випадковий вибір сторінки. Такий алгоритм називається random – замінюється сторінка, яка вибирається випадково.          

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

6. Ієрархія запам'ятовуючих пристроїв. Принцип кешування даних

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

На наступному рівні розташовується більш швидкодіюча (час доступу1 дорівнює приблизно 10-20 наносекундам) і менш об'ємна (від десятків мегабайт до декількох гігабайт) ОП, реалізована на відносно повільній динамічній пам'яті DRAM.

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

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



Оперативна пам’ять

 (на основі DRAM)

Регістри процесора	Об’єм

 								       Вартість 

	Десятки байт			    2-3 нс	Час	      зберігання 



Швидкодіюча пам’ять

(на основі SRAM)доступу  	біта



Десятки-сотні

Кілобайт			           5-8 нс





	 Десятки



Зовнішня пам’ять	 Мегабайт				 10-20 нс 

  

  Десятки					       

      Десятки

	          Гігабайт						мс



Рис.27 Ієрархія запам’ятовуючих пристроїв

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



6.1. Кеш-пам’ять 

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

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

Розглянемо окремий випадок використання кеш-пам'яті для зменшення середнього часу доступу до даних, що зберігається в ОП. Для цього між процесором і ОП міститься швидкий ЗП, названий просто кеш-пам'яттю (мал. 28). У якості такого може бути використана, наприклад, асоціативна пам'ять. Уміст кеш-пам'яті являє собою сукупність записів про всіх завантажених у неї елементах даних. Кожен запис про елемент даних містить у собі адреса, що цей елемент даних має в ОП, і керуючу інформацію: ознака модифікації й ознака звертання до даних за деякий останній період часу. 





Оперативна

пам’ять“Повільна” відповідь



ЦП









КЕШзапит













Структура кеш-пам’яті



Адрес даних в ОП	Дані		         Управління інформацією															біт модифікації	        біт повороту		

						

					















Рис. 28. Кеш-пам'ять



6.2. Принцип кешування пам’яті 

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

У системах, оснащених кеш-пам'яттю, кожен запит до ОП виконується у відповідності з наступним алгоритмом: 

1. Проглядається вміст кеш-пам'яті з метою визначення,   чи не знаходяться потрібні дані в кеш-пам'яті; кеш-пам'ять не є адресованою, тому пошук потрібних даних здійснюється по вмісту - значенню поля чи "адресу в ОП", взятому з запиту. 

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

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

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

Покажемо, як середній час доступу до даних залежить від імовірності влучення в кеш. Нехай мається основні ЗП із середнім часом доступу до даних t1 і кеш-пам'ять, що має час доступу t2, мабуть, що t2<t1. Позначимо через t середній час доступу до даних у системі з кеш-пам'яттю, а через p -імовірність влучення в кэш. По формулі повної імовірності маємо: 

t = t1((1 - p) + t2(p

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

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

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

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

Усі попередні міркування справедливі і для інших пар ЗП, наприклад, для ОП і зовнішньої пам'яті. У цьому випадку зменшується середній час доступу до даних, розташованим на диску, і роль кеш-пам'яті виконує буфер в ОП. 

6.3. Узгодження швидкостей обміну і кешування даних.

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

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

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

7. Розподіл ОП в ОС для MS-DOS

 Перше питання, що хочеться задати — це які ОС варто відносити до сучасних, а які — ні?  Чи варто в наш час вивчати таку «несучасну» ОС, як MS-DOS? На наш погляд, насамперед до сучасних ОС варто віднести ті, що використовують апаратні можливості мікропроцесорів, спеціально закладені для організації високопродуктивних і надійних обчислень. Однак ці ОС, як правило, дуже складні і громісткі. Вони займають великий дисковий простір, вимагають і великого обсягу ОП. Тому для рішення деякого класу задач цілком підходять і системи, що використовують мікропроцесори в так називаному реальному режимі роботи.

Як відомо, MS-DOS — це однопрограмна ОС. У ній, звичайно, можна організувати запуск резидентних або TSR-задач, але в цілому вона призначена для виконання тільки одного обчислювального процесу. 

 У IBM PC використовувався 16-розрядний мікропроцесор 18088, що за рахунок введення сегментного способу адресації дозволяв адресуватися до пам'яті обсягом до 1 Мбайт. У наступних ПК (IBM PC AT, AT386 і ін.) було прийняте рішення підтримувати сумісність з першими, тому при роботі з DOS насамперед розглядають перший Мбайт. Уся ця пам'ять розділялася на кілька областей, що проілюстровано на мал. 2.10. На цьому малюнку зображено, що пам'яті може бути і більше, ніж 1 Мбайт

Якщо не вдаватися в деталі, можна сказати, що до складу MS-DOS входять наступні основні компоненти:

Базова підсистема в/в - BIOS (base input-output system), що включає в себе крім програми тестування ПК (POST2) оброблювачі переривань (драйвери), розташовані в ПЗП. В остаточному підсумку, майже всі інші модулі MS-DOS звертаються до BIOS. Якщо і не прямо, то через модулі більш високого рівня ієрархії.

 Модуль розширення BIOS — файл IO.SYS (в інших DOS-системах він може називатися інакше, наприклад, IBMIO.COM).

Основний, базовий модуль обробки переривань DOS — файл MSDOS.SYS. Саме цей модуль в основному реалізує роботу з ФС. (У PC-DOS аналогічний за значенням файл називається IBMDOS.COM).

Командний процесор (інтерпретатор команд) — файл COMMAND.COM.



Розподіл ОП Windows 9.х

З точки зору базової архітектури ОС Windows 95/98 вони обидві є 32-розрядими, багатопоковими ОС з витісняючою багатозадачністю ОС. Основний коритсувацький інтерфейс цих ОС – графічний.

Для своєї загрузки вони використовують ОС MS-DOS 7.х. 

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

У   Windows 95/98 кожна 32-розрядна ПП виконується у своєму відповідному адресному просторі, але всі вони  використовують сумісно один і той же 32-розрядний системний код. Іншими словами, ВАП не використовує всіх апаратних засобів захисту, закладених у мікропроцесорах.

Системний код Windows95/98 розміщується вище границі 2 Гбайти. У 32-бітних мікропроцесорах і80х86 є чотири рівня захисту, які називаються кільцями з номерами від 0 до 3. Кільце з номером 0 є найбільш привілегійованим, тобто максимально захищеними. Компоненти  системи Windows 95, відносяться до кільця 0, відображаються на ВАП між 3 і 4 Гбайти. До цих компонентів відносяться ядро Windows,підсистема управління ВМ, модулі ФС і віртуальні драйвери. 

Розподіл ОП Windows NT

В ОС Windows NT також використовується плоска модель пам’яті. Схема розподілу можливого ВАП в системах Windows NT дуже відрізняється від моделі пам’яті  Windows95/98. Передусім, на відміну від Windows95/98 дуже великі степені використовується ряд серйозних апаратних засобів захисту, які є в мікропроцесорах, а також використаний інший логічний розподіл адресного простору. 

По-перше, всі системні програмні модулі знаходяться в своїх особистих ВАП, і доступ лддо них зі сторони ПП неможливий. Ядро системи і декілька драйверів працюють у нульовому кільці в окремому адресному просторі.

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

ПП виділя.ться 2 Гбайти локального лінійного простору від границі 64 кб до 2 Гбайт. 

Для 16-розрядних прикладних Windows програм  ОС Windows NT  реалізує сеанси Windows on Windows. На відміну від Windows95/98  Windows NT дає можливість виконувати 16-розрядні Windows індивідуально в особистих просторах пам’яті або сумісно в розподіленому адресному просторі. 

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

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

Вся ВП у WindowsNT розділяється на класи: зарезервовану, виділену і доступну.

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

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

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