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

OS-basic 09.   Управління віртуальною пам'яттю

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

Основні поняття модуля:

- Віртуальна пам'ять,
- Реальна пам'ять,
- Простір віртуальних адрес,
- Простір реальних адрес,
- Штучна суміжність,
- Дворівнева пам'ять,
- Поблокове відображення пам'яті,
- Таблиця відображення блоків,
- Регістр початкової адреси таблиці блоків,
- Сторінковий спосіб організації пам'яті,
- Віртуальний адреса в сторінковій системі,
- Файл підкачки (сторінковий файл, swap-файл),
- Сторінковий кадр,
- Таблиця сторінок,

- Біт присутності сторінки в ОП,
- Сегментна організація пам'яті, 

- Віртуальний адреса в сегментній системі,
- Таблиця сегментів, дескриптор сегмента
- Права доступу до сегмента: читання, запис, виконання, доповнення,
- Системи з комбінованою сторінково-сегментної організацією,
- Віртуальна адреса в системі зі сторінково-сегментною організацією,
- Стратегії заміщення сегментів (сторінок) в пам'яті: FIFO, LRU, LFU, випадковий вибір
- Пробуксовка,
- Робоча множина.

9.1 Віртуальна пам'ять. Поняття

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

                                                        Рис 9.1  Відображення пам’яті

Системне програмне забезпечення повинне зв'язувати кожне зазначене користувачем ім'я з фізичною коміркою пам'яті, тобто здійснити відображення простору імен на фізичну пам'ять комп'ютера. У загальному випадку це ототожнення здійснюється в два етапи (рис. 9.1): спочатку системою програмування, а потім операційною системою.

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

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

9.2 Віртуальна пам'ять. Основні концепції

Суть концепції віртуальної пам'яті полягає в тому, що адреси, до яких звертається виконується процес, відокремлюються від адрес, реально існуючих в первинній пам'яті.
Ті адреси, на які робить посилання виконується процес, називаються віртуальними адресами, а ті адреси, які існують в первинній пам'яті, називаються реальними (або фізичними) адресами (див. рис. 9.1). Діапазон віртуальних адрес, до яких може звертатися виконується процес, називається простором віртуальних адрес «V» цього процесу. Діапазон реальних адрес, що існують в конкретній обчислювальній машині, називається простором реальних адрес R цього комп'ютера.
Незважаючи на те, що процеси звертаються тільки до віртуальних адрес, насправді вони мають працювати з реальною пам'яттю. Таким чином, під час виконання процесу віртуальні

Рис. 9.2 Відображення елементів віртуального адресного простору

 на реальний адресний простір.

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

                            Рис. 9.3 Штучна суміжність. Елементи, які є суміжними в віртуальній

               пам'яті, відображаються не обов'язково на суміжні елементи реальної пам'яті.

Існують два найбільш загальноприйнятих способи реалізації віртуальної пам'яті - сторінкова і сегментна організації пам'яті. У деяких системах віртуальної пам'яті застосовується цей, або інший з цих способів, а в деяких – їх комбінація.

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

                            Рис 9.4 Дворівнева пам'ять

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

Рис. 9.5 Розміщення елементів віртуальної пам'яті різних

                                                         користувачів в реальній пам'яті

9.4 Поблочні відображення

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


Збільшення розміру блоків призводить до зменшення додаткових витрат пам'яті для механізму відображення. Однак великі блоки вимагають більшого часу на обмін між зовнішньою та первинної пам'яттю і з більшою ймовірністю обмежують кількість процесів, які можуть спільно використовувати первинну пам'ять.
При реалізації віртуальної пам'яті виникає питання про те, чи слід все блоки робити однакового або різних розмірів. Якщо блоки мають однаковий розмір, вони називаються сторінками, а відповідна організація віртуальної пам'яті називається сторінкової. Якщо блоки можуть бути різних розмірів, вони називаються сегментами, а відповідна організація віртуальної пам'яті називається сегментною. У деяких системах обидва ці підходи комбінуються, тобто сегменти реалізуються як об'єкти змінних розмірів, що формуються зі сторінок фіксованого розміру.
Адреси в системі поблочно відображення є двокомпонентними («двовимірними»). Щоб звернутися до конкретного елементу даних, програма вказує блок, в якому цей елемент розташовується, і зміщення цього елемента щодо початку блоку (рис 9.6). Віртуальний адресу v вказується за допомогою упорядкованої пари (b, d), де b - номер блоку, в якому розміщується відповідний елемент, ad - зміщення відносно початкової адреси цього блоку.

Рис. 9.6 Формат віртуальної адреси в системі поблочного відображення.

Перетворення адреси віртуальної пам'яті v = (b, d) на адресу реальної пам'яті rздійснюється наступним чином (рис. 9.7). Кожен процес має власну таблицювідображення блоків, яку система веде в реальному пам'яті. Реальний адресу ацієї таблиці завантажується в спеціальний регістр центрального процесора,званий регістром початкової адреси таблиці блоків. Таблиця відображенняблоків містить по одному рядку для кожного блоку процесу, причому ці рядкийдуть в послідовному порядку, спочатку блок 0, потім блок 1 і т. д. Номер блокуb підсумовується з базовою адресою, а таблиці, утворюючи реальну адресу рядка таблиці для блоку b.

Рис. 9.7 Перетворення віртуальної адреси при поблочному відображенні.

Цей рядок містить реальну адресу b 'блоку b в реальному пам'яті. До цього початкового адресою b 'додається зсув d, так що утворюється потрібний реальний адресу r = b' + d.
Всі методи поблочно відображення, застосовувані в системах з сегментною, сторінкової та комбінованої сторінково-сегментної організацій, подібні схеми відображення, яка показана на рис. 9.7.
Важливо відзначити, що поблочно відображення здійснюється динамічно під час виконання процесу. Якщо механізм відображення реалізований недостатньо ефективно, то накладні витрати можуть привести до такого погіршення характеристик системи, що будуть практично зведені нанівець переваги, що досягаються завдяки використанню віртуальної пам'яті.

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

9.5.1. Основні концепції

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

Розглянь поблочно відображення в разі сторінкової організації пам'яті.Віртуальний адреса в сторінкової системі - це упорядкована пара (р, d), де р - номер сторінки у віртуальній пам'яті, ad - зміщення в рамках сторінки р, де розміщується адресованих елементів (рис. 9.8).

Рис. 9.8 Формат віртуальної адреси в системі з чисто сторінковою організацією.

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

Рис. 9.9 Поділ реальної пам'яті на сторінкові кадри

Динамічне перетворення адрес в системі з сторінкової організацією здійснюється наступним чином. Виконується процес звертається за адресоювіртуальної пам'яті v = (p, d). Механізм відображення сторінок, показаний на рис.9.10, шукає номер сторінки р в таблиці відображення сторінок і визначає, що цясторінка знаходиться в сторінковому кадрі р'. Адреса реальної пам'ятіформується потім шляхом конкатенації р'і d.

Рис. 9.10 Відповідність між віртуальною та реальною пам'яттю в системі з сторінковою організацією сторінкової організації

Розглянемо тепер цей процес більш докладно. Зокрема, оскільки зазвичай невсі сторінки процесу знаходяться в первинній пам'яті одночасно, таблицявідображення сторінок повинна вказувати, чи є адресуемая сторінка в первинній пам'яті, і якщо є, то де саме, а якщо ні, то в якому місці зовнішньої пам'яті її можна знайти . На рис. 9.11 показана типова рядок таблиці відображення сторінок. Біт-ознака присутності сторінки r встановлюється в 0,якщо даної сторінки в первинній пам'яті немає, і в 1, якщо ця сторінка є в первинній пам'яті. Якщо сторінки немає, то s - її адресу у зовнішній пам'яті. Якщо сторінка є в первинній пам'яті, то р '- номер її сторінкового кадру. Зазначимо, щор '- це не дійсний адресу первинної пам'яті. Адреса первинної пам'яті а, з якого починається сторінковий кадр р '(якщо розмір сторінки дорівнює р), визначається наступним твором (якщо сторінкові кадри мають номери 0, 1, 2 і т.д.): а = (р) (р')

Рис. 9.11 Рядок таблиці сторінок.

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

Рис. 9.12 Відображення віртуального адресного простору на фізичну пам'ятьпри сторінкової організації

9.6. сегментна організація
9.6.1. Основні концепції

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

Рис. 9.13 Розподіл пам'яті несуміжними блоками.

У системах з сегментною організацією (сегментацією) це обмеження знімається, і програма (і її дані) може займати багато окремих блоків первинної пам'яті (рис. 9.13). Самі блоки, не обов'язково однакового розміру, все ж повинні складатися із суміжних клітинок, проте окремі блоки можутьрозміщуватися і не поруч один з одним.
Віртуальний адреса в сегментної системі - це упорядкована пара  = (s, d), де s- номер сегмента віртуальної пам'яті, ad - зміщення в рамках цього сегмента, дезнаходиться адресованих елементів (рис. 9.14). Процес може виконуватисятільки у випадку, якщо його поточний сегмент (як мінімум) розміщується в первинній пам'яті. Сегменти передаються з зовнішньої пам'яті в первиннуцілком. Всі осередки, пов'язані з сегменту, займають суміжні адреси первинноїпам'яті. Вступник із зовнішньої пам'яті сегмент може

Рис. 9.14 Формат віртуальної адреси в чисто сегментної системі.

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

Рис. 9.15 Перетворення віртуальної адреси в чисто сегментної системі.

Динамічне перетворення адрес здійснюється наступним чином (рис. 9.15). Виконується процес видає адресу віртуальної пам'яті  = (s, d). Механізм відображення сегментів шукає сегмент s в таблиці сегментів і визначає, що цейсегмент знаходиться в реальній пам'яті, починаючи з клітинки s '. Адресареальної  пам'яті, відповідний віртуального адресою  = (s, d), формуєтьсяпотім шляхом додавання s 'до d.
Перетворення імені сегмента в його порядковий номер здійснить системапрограмування, а операційна система буде розміщувати сегменти в пам'ять ідля кожного сегмента отримає інформацію про його початок. Таким чином, віртуальний адреса для цього способу буде складатися з двох полів - номерсегмента і зміщення відносно початку сегмента.  Відповідна ілюстрація приведена на рис. 9.16. На цьому малюнку зображено випадок звернення до осередку, віртуальний адреса якої дорівнює сегменту з номером 11 ізміщенням від початку цього сегмента, рівним 612. Як ми бачимо, операційнасистема розмістила даний сегмент в пам'яті, починаючи з комірки з номером 19700.

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

Кожен сегмент, що розміщується в пам'яті, має відповідну інформаційну структуру, часто звану дескриптором сегмента. Саме операційна система будує для кожного виконуваного процесу відповідну таблицю дескрипторів сегментів і при розміщенні кожного з сегментів в оперативній або зовнішньої пам'яті в дескрипторі відзначає його поточне місце розташування. Якщо сегмент завдання в даний момент знаходиться в оперативній пам'яті, то про це робиться позначка в дескрипторі. Як правило, для цього використовується «біт присутності» (present). В цьому випадку в поле «адреса» диспетчер пам'яті записує адресу фізичної пам'яті, з якого сегмент починається, а в полі «довжина сегмента» (limit) вказується кількість адресованих комірок пам'яті.Це поле використовується не тільки для того, щоб розміщувати сегменти без накладення один на інший, але і для того, щоб проконтролювати, не звертається Чи код виконується завдання за межі поточного сегмента. У разі перевищення довжини сегмента внаслідок помилок програмування ми можемо говорити про на ¬ рушення адресації і за допомогою введення спеціальних апаратних засобів генерувати сигнали переривання, які дозволять фіксувати (виявляти) такого роду помилки.
Якщо біт present в дескрипторі вказує, що зараз цей сегмент знаходиться не в оперативній, а в зовнішній пам'яті (наприклад, на вінчестері), то названі поля адреси і довжини використовуються для вказівки адреси сегмента в координатах зовнішньої пам'яті. Крім інформації про місцезнаходження сегмента, в дескрипторі сегмента, як правило, містяться дані про його типі (сегмент коду або сегмент даних), права доступу до цього сегменту (можна або не можна його модифікувати, надавати іншої задачі), відмітка про звернення до даного сегменту ( інформація про те, як часто або як давно / недавно цей сегмент використовується або не використовується, на підставі якої можна прийняти рішення про те, щоб надати місце, займане поточним сегментом, іншому сегменту).
При передачі управління наступній задачі ОС повинна занести до відповідного регістр адресу таблиці дескрипторів сегментів цього завдання. Сама таблиця дескрипторів сегментів, в свою чергу, також являє собою сегмент даних, який обробляється диспетчером пам'яті операційної системи.
При такому підході з'являється можливість розміщувати в оперативній пам'яті не всі сегменти завдання, а тільки ті, з якими в даний момент відбувається робота. З одного боку, стає можливим, щоб загальний обсяг віртуального адресного простору завдання перевершував об'єм фізичної пам'яті комп'ютера, на якому це завдання буде виконуватися. З іншого боку, навіть якщо потреби в пам'яті не перевершують наявну фізичну пам'ять, з'являється можливість розміщувати в пам'яті як можна більше завдань.


9.6.2. Управління доступом в системах з сегментною організацією

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

Рис. 9.21 Види управління доступом.

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


9.7 Системи з комбінованою сторінково-сегментної організацією

9.7.1. Основні концепції

І сегментна, і сторінкова організації мають важливі переваги як способи побудови віртуальної пам'яті. Починаючи з систем середини 60-х років, зокрема з інформаційно-обчислювальної системи з поділом часу Multics і системи поділу часу TSS корпорації IBM, у багатьох обчислювальних машинах застосовується комбінована сторінково-сегментна організація пам'яті. Ці системи володіють достоїнствами обох способів реалізації віртуальної пам'яті.Сегменти зазвичай містять ціле число сторінок, причому не обов'язково, щоб всі сторінки сегмента перебували у первинної пам'яті одночасно, а суміжні сторінки віртуальної пам'яті не обов'язково повинні надаватися суміжними в реальному пам'яті. В системі зі сторінково-сегментної організацією застосовується трикомпонентна (тривимірна) адресація, тобто адресу віртуальної пам'яті v визначається як впорядкована трійка v = (s, p, d), де s - номер сегмента, р - номер сторінки, а d - зміщення в рамках сторінки, по якому знаходиться потрібний елемент (рис. 9.18).

Рис. 9.18 Формат віртуальної адреси в сторінковому-сегментної системі


9.7.2. Динамічне перетворення адрес в системах зі сторінково-сегментної організацією

Розглянемо тепер динамічне перетворення віртуальних адрес у реальні в сторінковому-сегментної системі із застосуванням комбінованого асоціативно-прямого відображення, як показано на рис. 9.19.
Виконується процес робить посилання по віртуальному адресою  = (s, р, d).Найостанніші за часом звернення сторінки мають відповідні рядки в асоціативної таблиці. Система виробляє асоціативний пошук, намагаючись знайти рядок з параметрами (s, р) в асоціативної таблиці. Якщо такий рядок тут виявляється, то адресу сторінкового кадру р ', за яким ця сторінка розміщується в первинній пам'яті, з'єднується зі зміщенням d, утворюючи реальну адресу r, відповідний віртуального адресою v, - і на цьому перетворення адреси завершується.
У звичайному випадку більшість запитів на перетворення адрес вдається задовольнити подібним асоціативним пошуком. Якщо ж необхідного адреси в асоціативної пам'яті немає, то перетворення здійснюється способом повного прямого відображення. Це робиться так: базова адреса b таблиці сегментів додається до номера сегмента s, так що утворюється адресу b + s рядка для сегмента s у таблиці сегментів по первинній пам'яті. У цьому рядку вказується базовий адреса s 'таблиці сторінок для сегмента s. Номер сторінки р додається до s ', так що утворюється адреса p + s' рядка в таблиці сторінок для сторінки р сегмента s. Ця таблиця дозволяє встановити, що віртуальної сторінці р відповідає номер кадру р '. Цей номер кадру з'єднується зі зміщенням d, так що утворюється реальна адреса r, відповідний віртуального адресою v = (s, р, d).
Ця процедура перетворення адрес описана, звичайно, в припущенні, що кожен необхідний елемент інформації знаходиться саме там, де йому належить бути.Проте в процесі перетворення адрес існує багато моментів, коли обставини можуть складатися не настільки сприятливо. Перегляд таблиці сегментів може показати, що сегмента s у первинній пам'яті немає; при цьому виникає переривання по відсутності сегмента, операційна система знайде потрібний сегмент у зовнішній пам'яті, сформує для нього таблицю сторінок і завантажить відповідну сторінку в первинну пам'ять, бути може, замість деякої існуючоїсторінки цього або будь-якого іншого процесу. Коли сегмент знаходиться в первинній пам'яті, звернення до таблиці сторінок може показати, що потрібної сторінки в первинній пам'яті все ж немає. При цьому відбудеться переривання по відсутності сторінки, операційна система візьме керування на себе, знайде дану сторінку у зовнішній пам'яті і завантажить її в первинну пам'ять (може, знову-таки з заміщенням іншої сторінки). Як і при чисто сегментної системі, адреса віртуальної пам'яті може вийти за рамки сегмента і відбудеться переривання по виходу за межі сегмента. Або контроль за бітам-ознаками захисту може виявити, що операція, виконання якої запитується за вказаною віртуального адресою, не дозволена, внаслідок чого відбудеться переривання по захисту сегмента. Операційна система повинна передбачати обробку всіх цих ситуацій.
Асоціативна пам'ять (або аналогічно високошвидкісна кеш-пам'ять) грає вирішальну роль в забезпеченні ефективної роботи механізму динамічного перетворення адрес. Якщо перетворення адрес проводити за допомогою чисто прямого відображення з веденням в первинній пам'яті повного набору таблиць відповідності віртуальних і реальних адрес, типове звернення до віртуальної пам'яті вимагало б циклу пам'яті для доступу до таблиці сегментів, другого циклу пам'яті для доступу до таблиці сторінок і третього для доступу до потрібного елементу в реальному пам'яті. Таким чином, кожне звернення до адресуемому елементу займало б три цикли пам'яті, тобто реальне швидкодію обчислювальної системи склало б лише приблизно третину від номінального значення, а дві третини витрачалися б на перетворення адрес! Цікаво, що при всього лише восьми або шістнадцяти асоціативних регістрах розробники домагаються для багатьох систем показників швидкодії, що становлять 90 і більше відсотків повних швидкісних можливостей їх керуючих (центральних) процесорів.

Рис. 9.19 Перетворення віртуальної адреси шляхом комбінованого асоціативно прямого відображення в сторінковому-сегментної системі.


9.8. Стратегії заміщення сегментів (сторінок) в пам'яті

Отже, якщо необхідного сегмента в оперативній пам'яті немає, то виникає переривання і керування передається через диспетчер пам'яті програмі завантаження сегмента. Поки відбувається пошук сегмента у зовнішній пам'яті і завантаження його в оперативну, диспетчер пам'яті визначає відповідне для сегмента місце. Можливо, що вільного місця немає, і тоді приймається рішення про вивантаження якогось сегмента і його переміщення в зовнішню пам'ять.Якщо при цьому ще залишається час, то процесор передається іншій готової до виконання завдання. Після завантаження необхідного сегмента процесор знову передається завданню, що викликала переривання через відсутність сегмента. Всякий раз при зчитуванні сегмента в оперативну пам'ять в таблиці дескрипторів сегментів необхідно встановити адресу початку сегменту і ознака присутності сегмента.
При пошуку вільного місця використовується одна з перерахованих вище дисциплін роботи диспетчера пам'яті (застосовуються правила «першої відповідного» і «самого невідповідного» фрагментів). Якщо вільного фрагмента пам'яті достатнього об'єму зараз немає, але тим не менш сума цих вільних фраг ¬ ментів перевищує вимоги по пам'яті для нового сегмента, то в принципі може бути застосовано «ущільнення пам'яті», про який ми вже говорили в підрозділі «Розділи з фіксованими кордонами »при розгляді динамічного способу розбиття пам'яті на розділи.
В ідеальному випадку розмір сегмента повинен бути досить малим, щоб його можна було розмістити в випадково вивільнюваних фрагментах оперативної пам'яті, але достатньо великим, щоб утримувати логічно закінчену частину програми з тим, щоб мінімізувати міжсегментні звернення.
Для вирішення проблеми заміщення (визначення того сегмента, який повинен бути або переміщений в зовнішню пам'ять, або просто заміщений новим) викорис ¬ зуются наступні дисципліни:
• правило FIFO (first in - first out, що означає: «перший прийшов першим і вибуває»);
• правило LRU (least recently used, що означає «останній з недавно використаних" або, інакше кажучи, «найдовше невикористовуваний»);
• правило LFU (least frequently used, що означає: «використовуваний рідше всіх інших»);
• випадковий (random) вибір сегмента.

Перша і остання дисципліни є найпростішими в реалізації, але вони не враховують, наскільки часто використовується той чи інший сегмент і, отже, диспетчер пам'яті може вивантажити або розформувати той сегмент, до якого в самому найближчому майбутньому буде звернення. Безумовно, достовірної інформації про те, який із сегментів потрібно в найближчому майбутньому, в загальному випадку мати не можна, але ймовірність помилки для цих дисциплін багаторазово вище, ніж у другої і третьої дисципліни, які враховують інформацію про використання сегментів.
Алгоритм FIFO асоціює з кожним сегментом час, коли він був поміщений в нам'яти. Для заміщення вибирається найбільш старий сегмент. Облік часу необов'язковий, коли всі сегменти в пам'яті зв'язані в FIFO-чергу і кожен поміщається в пам'ять сегмент додається у хвіст цієї черги. Алгоритм враховує тільки час знаходження сегмента в пам'яті, але не враховує фактичне використання сегментів. Наприклад, перші завантажені сегменти програми можуть містити змінні, використовувані протягом роботи всієї програми. Це призводить до негайного повернення до щойно заміщеними сегменту.
Для реалізації дисциплін LRU і LFU необхідно, щоб процесор мав додаткові апаратні засоби. Мінімальні вимоги - достатньо, щоб при зверненні до дескриптора сегмента для отримання фізичної адреси, з якого сегмент починає розташовуватися в пам'яті, відповідний біт звернення міняв своє значення (скажімо, з нульового, яке встановила ОС, в одиничне). Тоді диспетчер пам'яті може час від часу переглядати таблиці дескрипторів виконуються завдань і збирати для відповідної обробки статистичну інформацію про звернення до сегментів. В результаті можна скласти список, впорядкований або за тривалістю не використання (для дисципліни LRU), або за частотою використання (для дисципліни LFU).
Якщо обсяг фізичної пам'яті невеликий і навіть часто необхідні сторінки не вдається розмістити в оперативній пам'яті, то виникає так звана «пробуксовка». Іншими словами, пробуксовка - це ситуація, при якій завантаження потрібної нам сторінки викликає переміщення в зовнішню пам'ять тієї сторінки, з якою ми теж активно працюємо. Очевидно, що це дуже погане явище. Щоб його не допускати, бажано збільшити обсяг оперативної пам'яті (зараз це стало найпростішим рішенням), зменшити кількість паралельно виконуваних завдань або спробувати використовувати більш ефективні дисципліни заміщення.
В абсолютній більшості сучасних ОС використовується дисципліна заміщення сторінок LRU як найефективніша.
У ряді ОС з пакетним режимом роботи для боротьби з пробуксовкою використовується метод «робочого безлічі». Робоче безліч - це безліч «активних» сторінок завдання за певний інтервал. Тобто тих сторінок, до яких було звернення за цей інтервал часу. Реально кількість активних сторінок завдання (за інтервал Т) весь час змінюється, і це природно, але тим не менш для кожного завдання можна визначити середню кількість її активних сторінок.Це середня кількість активних сторінок і є робоче безліч завдання.Спостереження за виконанням безлічі різних програм показали, що навіть якщо Т одно часу виконання всієї роботи, то розмір робочого безлічі часто істотно менше, ніж загальне число сторінок програми. Таким чином, якщо ОС може визначити робочі безлічі виконуються завдань, то для запобігання пробуксовки досить планувати на виконання тільки таку кількість завдань, щоб сума їх робочих множин не перевищувала можливості системи.


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

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

9.9.2. Сторінковий спосіб

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