Віртуальна память. Архітектурні засоби підтримки віртуальної памяті. Лекція 9 Віртуальна пам’ять. Архітектурні засоби підтримки вірту. Лекція 9 Віртуальна память. Архітектурні засоби підтримки віртуальної' памяті
 Скачать 166.83 Kb.
|
|
Лекція 9 Віртуальна пам’ять. Архітектурні засоби підтримки віртуальної' пам’яті. Розглянуто апаратні особливості підтримки віртуальної пам’яті. Розбивка адресного простору процесу на частині й динамічній трансляції адреси дозволили виконувати процес навіть під час відсутності деяких його компонентів в оперативній пам’яті. Наслідком такої стратегії є можливість виконання більших програм, розмір яких може перевищувати розмір оперативної пам’яті. У цій і наступній лекціях мова йтиме про найпоширенішій у цей час схемі керування пам’яттю, відомої як віртуальна пам’ять, у рамках якої здійснюється складний зв’язок між апаратним і програмним забезпеченням. На початку будуть розглянуті апаратні аспекти віртуальної пам’яті, а потім питання, щр виникають при її програмній реалізації. Поняття віртуальної' пам’яті Розроблювачам програмного забезпечення часто доводиться вирішувати проблему розміщення в пам’яті більших програм, розмір яких перевищує обсяг доступної оперативної пам’яті. Один з варіантів рішення даної проблеми - організація структур з перекриттям - розглянутий у попередній лекції. При цьому передбачалася активна участь програміста в процесі формування частин, що перекриваються, програми. Розвиток архітектури комп’ютерів і розширення можливостей операційної системи по керуванню пам’яттю дозволило перекласти рішення цього завдання на комп’ютер. Одним з головних досягнень стала поява віртуальної пам’яті (virtual memory). Уперше вона була реалізована в 1959 р. на комп’ютері "Атлас", розробленому в Манчестерському університеті. Суть концепції віртуальної пам’яті полягає в наступному. Інформація, з якої працює активний процес, повинна розташовуватися в оперативній пам’яті. У схемах віртуальної пам’яті в процесу створюється ілюзія того, що вся необхідна йому інформація є в основній пам’яті. Для цього, по-перше, займана процесом пам’ять розбивається на кілька частин, наприклад сторінок. По-друге, логічна адреса (логічна сторінка), до якого звертається процес, динамічно транслюється у фізичну адресу (фізичну сторінку). І, нарешті, у тих випадках, коли сторінка, до якої звертається процес, не перебуває у фізичній пам’яті, потрібно організувати її підкачування з диска. Для контролю наявності сторінки в пам’яті вводиться спеціальний біт присутності, що входить до складу атрибутів сторінки в таблиці сторінок. Таким чином, у наявності всіх компонентів процесу в основній пам’яті необхідності немає. Важливим наслідком такої організації є те, що розмір пам’яті, займаної процесом, може бути більше, ніж розмір оперативної пам’яті. Принцип локальності забезпечує цій схемі потрібну ефективність. Можливість виконання програми, що перебуває в пам’яті лише частково, має ряд цілком очевидних переваг. Програма не обмежена обсягом фізичної пам’яті. Спрощується розробка програм, оскільки можна задіяти більші віртуальні простори, не піклуюнись про розмір використовуваної пам’яті. Оскільки з’являється можливість часткового приміщення програми (процесу) на згадку й гнучкий перерозподіл пам’яті між програмами, можна розмістити в пам’яті більше програм, що збільшує завантаження процесора й пропускну здатність системи. Обсяг виводу-вводу-висновку для вивантаження частини програми на диск може бути менше, ніж у варіанті класичного свопінга, у підсумку кожна програма буде працювати швидше- Таким чином, можливість забезпечення (за підтримкою операційної системи) для програми "видимості" практично необмеженої (характерний розмір для розрядн-32-розрядних архітектор 232 = 4 Гбайт) адресованій користувальницької пам’яті (логічний адресний простір) при наявності основної пам’яті істотно менших розмірів (фізичний адресний простір) - дуже важливий аспект. Але введення віртуальної пам’яті дозволяє вирішувати іншу, не менш важливе завдання - забезпечення контролю доступу до окремих сегментів пам’яті й, зокрема, захист користувальницьких програм друг від друга й захист ОС від користувальницьких програм. Кожен процес працює зі своїми віртуальними адресами, трансляцію яких у фізичні виконує апаратури комп’ютера. Таким чином, користувальницький процес не має змоги прямо звернутися до сторінок основної пам’яті, зайнятим інформацією, що ставиться до інших процесів. Наприклад, розрядн-16-розрядний комп’ютер PDP-11/70 з 64 Кбайт логічної пам’яті міг мати до 2 Мбайт оперативної пам’яті. Операційна система цього комп’ютера проте підтримувала віртуальну пам’ять, щр забезпечувала захист і перерозподіл основної пам’яті міжкористувальницькими процесами. Нагадаємо, що в системах з віртуальною пам’яттю ті адреси, які генерує програма (логічні адреси), називаються віртуальними, і вони формують віртуальний адресний простір. Термін "віртуальна пам’ять" означає, що програміст має справу з пам’яттю, відмінної від реальної, розмір якої потенційно більше, ніж розмір оперативної пам’яті. Хоча відомі й чисто програмні реалізації віртуальної пам’яті, цей напрямок одержало найбільш широкий розвиток після відповідної апаратної підтримки. Слід зазначити, що встаткування комп’ютера бере участь у трансляції адреси практично у всіх схемах керування пам’яттю. Але у випадку віртуальної пам’яті це стає більше складним внаслідок розриву відображення й багатомірності логічного адресного простору. Може бути, найбільш істотним внеском обладанння у реалізацію описуваної схеми є автоматична генерація виняткових ситуацій при відсутності в пам’яті потрібних сторінок (page fault). Кожна із трьох раніше розглянутих схем керування пам’яттю - сторінкової, сегментної й сегментно-сторінкова - придатна для організації віртуальної пам’яті. Найчастіше використається сигментно-сторінкова модель, що є синтезом сторінкової моделі й ідеї сегментації. Гричому для тих архітектур, у яких сегменти не підтримуються апаратно, їхня реалізація - завдання архітектурно-незалежного компонента менеджера пам’яті. Сегментна організація в чистому виді зустрічається рідко. Архітектурні засоби підтримки віртуальної' пам’яті Очевидно, що неможливо створити повністю машинно-незалежний компонент керування віртуальною пам’яттю. З іншого боку, є істотні частини програмного забезпечення, пов’язаного з керуванням віртуальною пам’яттю, для яких деталі апаратної реалізації зовсім не важливі. Одним з досягнень сучасних ОС є грамотний й ефективний поділ засобів керування віртуальною пам’яттю на апаратно-незалежну й апаратно-залежною частини. Коротко розглянемо, що і яким образом входить в апаратно-залежну частину підсистеми керування віртуальною пам’яттю! Компоненти апаратно- незалежної підсистеми будуть розглянуті в наступній лекції. У найпоширенішому випадку необхідно відобразити великий віртуальний адресний простір у фізичний адресний простір істотно меншого розміру. Користувальницький процес або ОС повинні мати можливість здійснити запис по віртуальній адресі, а завдання ОС - зробити так, щоб записана інформація виявилася у фізичній пам’яті (згодом при недостачі оперативної пам’яті вона може бути витиснута в зовнішню пам’ять). У випадку віртуальної пам’яті система відображення адресних просторів крім трансляції адрес повинна передбачати ведення таблиць, що показують, які області віртуальної пам’яті в цей момент перебувають у фізичній пам’яті й де саме розміщаються. Сторінкова віртуальна пам’ять Як й у випадку простої сторінкової організації, сторінкова віртуальна пам’ять і фізична пам’ять представляються, що складаються з наборів блоків або сторінок однакового розміру. Віртуальні адреси діляться на сторінки (page), що відповідають одиниці у фізичній пам’яті утворять сторінкові кадри (page frames), а в цілому система підтримки сторінкової віртуальної пам’яті називається пейджингом (paging). Передача інформації між пам’яттю й диском завжди здійснюється цілими сторінками. Пспя розбивки менеджером пам’яті віртуального адресного простору на сторінки віртуальна адреса перетвориться в упорядковану пару (p,d), де p - номер сторінки у віртуальній пам’яті, а d - зсув у рамках сторінки p, усередині якої розміщається адресований елемент. Процес може виконуватися, якщо його поточна сторінка перебуває в оперативній пам’яті. Якщо поточної сторінки в головній пам’яті ні, вона повинна бути переписана (підкачана) із зовнішньої пам’яті. сторінку, Що Надійшла, можна помістити в будь-який вільний сторінковий кадр. Оскільки число віртуальних сторінок велика, таблиця сторінок приймає специфічний вид (див. розділ "Структура таблиці сторінок"), структура записів стає більше складної, серед атрибутів сторінки з’являються біти присутності, модифікації й інші керуючі біти. Гри відсутності сторінки в пам’яті в процесі виконання команди виникає виняткова ситуація, називана сторінкове порушення (page fault) або сторінкова відмова. Обробка сторінкового порушення полягає в тім, щр виконання команди переривається, викликана сторінка підкачується з конкретного місця вторинної пам’яті у вільний сторінковий кадр фізичної пам’яті й спроба виконання команди повторюється. Гри відсутності вільних сторінкових кадрів на диск вивантажується рідко використовувана сторінка. Гроблеми заміщення сторінок й обробки сторінкових порушень розглядаються в наступній лекції. Для керування фізичною пам’яттю ОС підтримує структуру таблиці кадрів. Вона має один запис на кожен фізичний кадр, що показує його стан. У більшості сучасних комп’ютерів зі сторінковою організацією в основній пам’яті зберігається лише частина таблиці сторінок, а швидкість доступу до елементів таблиці поточної віртуальної пам’яті досягається, як буде показано нижче, за рахунок використання надшвидкісною пам’яті, розміщеної в кеші процесора. Сегментно-сторінкова організації віртуальної' пам’яті Як й у випадку простої сегментації, у схемах віртуальної пам’яті сегмент - це лінійна послідовність адрес, що починається з 0. Гри організації віртуальної пам’яті розмір сегмента може бути великий, наприклад, може перевищувати розмір оперативної пам’яті. Повторюючи усе раніше наведені міркування про розміщення в пам’яті більших програм, приходимо до розбивки сегментів на сторінки й необхідності підтримки своєї таблиці сторінок для кожного сегмента. На практиці, однак, появи в системі великої кількості таблиць сторінок намагаються уникнути, організувати сегменти, що не перекриваються, в одному віртуальному просторі, для опису якого вистачає однієї таблиці сторінок. Таким чином, одна таблиця сторінок приділяється для всього процесу. Наприклад, у популярних ОС Linux й Windows 2000 всі сегменти процесу, а також область пам’яті ядра обмежені віртуальним адресним простором обсягом 4 Гбайт. Гри цьому ядро ОС розташовується по фіксованих віртуальних адресах поза залежністю від виконуваного процесу. Структура таблиці сторінок Організація таблиці сторінок - один із ключових елементів відображення адрес у сторінковій і сегментно- сторінкових схемах. Розглянемо структуру таблиці сторінок для випадку сторінкової організації більш докладно. Отже, віртуальна адреса складається з віртуального номера сторінки й зсуву. Номер запису в таблиці сторінок відповідає номеру віртуальної сторінки. Розмір запису коливається від системи до системи, але найчастіше він становить 32 біта. Із цього запису в таблиці сторінок перебуває номер кадру для даної віртуальної сторінки, потім додається зсув і формується фізична адреса. Крім цього запис у таблиці сторінок містить інформацію про атрибути сторінки. Це біти присутності й захисту (наприклад, 0 - read/Wite, 1 - read only...). Також можуть бути зазначені: біт модифікації, що встановлюється, якщо вміст сторінки модифікований, і дозволяє контролювати необхідність перезапису сторінки на диск; біт посилання, що допомагає виділити мало використовувані сторінки; біт, що дозволяє кешування, і інші керуючі біти. Помітимо, що адреси сторінок на диску не є частиною таблиці сторінок. Основну проблему для ефективної реалізації таблиці сторінок створюють більші розміри віртуальних адресних просторів сучасних комп’ютерів, які звичайно визначаються розрядністю архітектури процесора. Найпоширенішими на сьогодні є 32-розрядні процесори, що дозволяють створювати віртуальні адресні простори розміром 4 Гбайт (для 64- розрядних комп’ютерів ця величина дорівнює 264 байт). Крім того, існує проблема швидкості відображення, що вирішується за рахунок використання так називаної асоціативної пам’яті (див. наступний розділ). Гідрахуємо зразковий розмір таблиці сторінок. В 32-бітному адресному просторі при розмірі сторінки 4 Кбайт (Intel) одержуємо 232/212=220, тобто приблизно мільйон сторінок, а в 64-бітному й того більше. Таким чином, таблиця повинна мати приблизно мільйон рядків (entry), причому запис у рядку складається з декількох байтів. Помітимо, що кожен процес має потребу у своїй таблиці сторінок (а у випадку сегментно-сторінкової схеми бажано мати по одній таблиці сторінок на кожен сегмент). Зрозуміло, що кількість пам’яті, що відводить таблицям сторінок, не може бути такою великою! Для того шрб уникнути розміщення в пам’яті величезної таблиці, неї розбивають на ряд фрагментів. В оперативній пам’яті зберігають лише деякі, необхідні для конкретного моменту виконання фрагменти таблиці сторінок. У силу властивості локальності число таких фрагментів відносно невелике. Виконати розбивка таблиці сторінок на частині можна по-різному. Найпоширеніший спосіб розбивки - організація так називаної багаторівневої таблиці сторінок. Для приклада розглянемо дворівневу таблицю з розміром сторінок 4 Кбайт, реалізовану в 32-розрядній архітектурі Intel. Таблиця, ЩР складається з 220 рядків, розбивається на 210 таблиць другого рівня по 210 рядків. Ці таблиці другого рівня об'єднані в загальну структуру за допомогою однієї таблиці першого рівня, що складає з 210 рядків. 32- розрядна адреса ділиться на 10-розрядне поле pi, 10-розрядне поле р2 й 12-розрядний зсув d. Поле pi указує на потрібний рядок у таблиці першого рівня, поле р2 - другого, а поле d локалізує потрібний байт усередині зазначеного сторінкового кадру (див. рис. 9.1).  Рис. 9.1. Гриклад дворівневої таблиці сторінок За допомогою всього лише однієї таблиці другого рівня можна охопити 4 Мбайт (4 Кбайт x 1024) оперативної пам’яті. Таким чином, для розміщання процесу з більшим обсягом займаної пам’яті досить мати в оперативній пам’яті одну таблицю першого рівня й кілька таблиць другого рівня. Очевидно, щр сумарна кількість рядків у цих таблицях багато менше 220. Такий підхід природно узагальнюється на три й більше рівні таблиці. Наявність декількох рівнів, природно, знижує продуктивність менеджера пам’яті. Незважаючи на те що розміри таблиць на кожному рівні підібрані так, щр>б таблиця містилася цілком усередині однієї сторінки, звертання до кожного рівня - це окреме звертання до пам’яті. Таким чином, трансляція адреси може зажадати декількох звертань до пам’яті. Кількість рівнів у таблиці сторінок залежить від конкретних особливостей архітектури. Можна привести приклади реалізації однорівневого (DEC PDP-11), дворівневого (Intel, DEC VAX), трьохрівневого (Sun SPARC, DEC Alpha) пейджингу, а також пейджингу із заданою кількістю рівнів (Motorola). Функціонування RISC-процесора MIIPS R2000 здійснюється взагалі без таблиці сторінок. Тут пошук потрібної сторінки, якщо ця сторінка відсутня в асоціативній пам’яті, повинна взяти на себе ОС (так званий zero level paging). Асоціативна пам’ять Пошук номера кадру, щ> відповідає потрібній сторінці, у багаторівневій таблиці сторінок вимагає декількох звертань до основної пам’яті, тому займає багато часу. У деяких випадках така затримка неприпустима. Гроблема прискорення пошуку зважується на рівні архітектури комп’ютера. У відповідності із властивістю локальності більшість програм протягом деякого проміжку часу звертаються до невеликої кількості сторінок, тому активно використається тільки невелика частина таблиці сторінок. Гриродне рішення проблеми прискорення - постачити комп’ютер апаратним пристроєм для відображення віртуальних сторінок у фізичні без звертання до таблиці сторінок, тобто мати невелику, швидку кеш-пам’ять, щр зберігає необхідну на даний момент частина таблиці сторінок. Цей пристрій називається асоціативною пам’яттю, іноді також уживають термін буфер пошуку трансляції (translation lookaside buffer - TLB). Один запис таблиці в асоціативній пам’яті (один вхід) містить інформацію про одну віртуальну сторінку: її атрибути й кадр, у якому вона перебуває. Ці поля в точності відповідають полям у таблиці сторінок. Тому що асоціативна пам’ять містить тільки деякі із записів таблиці сторінок, кожен запис в TLB повинна включати поле з номером віртуальної сторінки. Пам’ять називається асоціативної, тому що в ній відбувається одночасне порівняння номера відображуваної віртуальної сторінки з відповідним полем у всіх рядках цієї невеликої таблиці. Тому даний вид пам’яті досить дорого коштує. У рядку, полі віртуальної сторінки якої збіглося із шуканим значенням, перебуває номер сторінкового кадру. Звичайне число записів в TLB від 8 до 4096. Ріст кількості записів в асоціативній пам’яті повинен здійснюватися з урахуванням таких факторів, як розмір кешу основної пам’яті й кількості звертань до пам’яті при виконанні однієї команди. Розглянемо функціонування менеджера пам’яті при наявності асоціативної пам’яті. На початку інформація про відображення віртуальної сторінки у фізичну відшукується в асоціативній пам’яті. Якщо потрібний запис знайдений - все нормально, за винятком випадків порушення привілеїв, коли запит на звертання до пам’яті відхиляється. Якщо потрібний запис в асоціативній пам’яті відсутній, відображення здійснюється через таблицю сторінок. Відбувається заміна однієї із записів в асоціативній пам’яті знайденим записом з таблиці сторінок. Тут ми зіштовхуємося із традиційної для будь-якого кешу проблемою заміщення (а саме яку із записів у кеші необхідно змінити). Конструкція асоціативної пам’яті повинна організовувати запису таким чином, щоб можна було ухвалити рішення щодо того, яка зі старих записів повинна бути вилучена при внесенні нових. число вдалих пошуків номера сторінки в асоціативній пам’яті стосовно загального числа пошуків називається hit (збіг) ratio (пропорція, відношення). Іноді також використається термін "відсоток влучень у кеші'. Таким чином, hit ratio - частина посилань, що може бути зроблена з використанням асоціативної пам’яті. Звертання до тим самим сторінок підвищує hit ratio, чим більше hit ratio, тим менше середній час доступу до даних, що перебуває в оперативній пам’яті. Гриіпустимо, наприклад, що для визначення адреси у випадку кеш-промаху через таблицю сторінок необхідно 100 нс, а для визначення адреси у випадку кеш-попадання через асоціативну пам’ять - 20 нс. З 90% hit ratio середній час визначення адреси - 0,9x20+0,1x100 = 28 нс. Цілком прийнятна продуктивність сучасних ОС доводить ефективність використання асоціативної пам’яті. Високе значення ймовірності знаходження даних в асоціативній пам’яті пов’язане з наявністю в даних об’єктивних властивостей: просторової й тимчасової локальності. Необхідно звернути увагу на наступний факт. Гри перемиканні контексту процесів потрібно домогтися того, щоб новий процес "не бачив" в асоціативній пам’яті інформацію, що ставиться до попереднього процесу, наприклад очищати її. Таким чином, використання асоціативної пам’яті збільшує час перемикання контексту. Розглянута дворівнева (асоціативна пам’ять + таблиця сторінок) схема перетворення адреси являє яскравий приклад ієрархії пам’яті, заснованої на використанні принципу локальності, про що говорилося у введенні до попередньої лекції. Інвертована таблиця сторінок Незважаючи на багаторівневу організацію, зберігання декількох таблиць сторінок великого розміру як і раніше являють собою проблему. Її значення особливо актуально для 64-розрядних архітектур, де число віртуальних сторінок 75 дуже велике. Варіантом рішення є застосування інвертованої таблиці сторінок (inverted page table). Цей підхід застосовується на машинах PowerPC, деяких робочих станціях Hewlett-Packard, IBM RT, IBM AS/400 і ряді інших. У цій таблиці втримується по одному записі на кожен сторінковий кадр фізичної пам’яті. Істотно, щр досить однієї таблиці для всіх процесів. Таким чином, для зберігання функції відображення потрібна фіксована частина основної пам’яті, незалежно від розрядності архітектури, розміру й кількості процесів. Наприклад, для комп’ютера Pentium c 256 Мбайт оперативної пам’яті потрібна таблиця розміром 64 Кбайт рядків. Незважаючи на економію оперативної пам’яті, застосування інвертованої таблиці має істотний мінус - запису в ній (як й в асоціативній пам’яті) не відсортовані по зростанню номерів віртуальних сторінок, що ускладнює трансляцію адреси. Один зі способів рішення даної проблеми - використання хеш-таблиці віртуальних адрес. Гри цьому частина віртуальної адреси, що представляє собою номер сторінки, відображається в хеш-таблицю з використанням функції хешиваня. Кожній сторінці фізичної пам’яті тут відповідає один запис у хеш-таблиці й інвертованій таблиці сторінок. Віртуальні адреси, що мають одне значення хеш-функції, зчіплюються один з одним. Звичайно довжина ланцюжка не перевищує двох записів. Розмір сторінки Розроблювачі ОС для існуючих машин рідко мають можливість впливати на розмір сторінки. Однак для знову створюваних комп’ютерів рішення щодо оптимального розміру сторінки є актуальним. Як і слід було сподіватися, немає одного найкращого розміру. Скоріше є набір факторів, що впливають на розмір. Звичайно розмір сторінки - це ступінь двійки від 2s до 214 байт. чим більше розмір сторінки, тим менше буде розмір структур даних, що обслуговують перетворення адрес, але тем більше будуть втрати, пов’язані з тим, що пам’ять можна виділяти тільки посторінково. Як варто вибирати розмір сторінки? Го-перше, потрібно враховувати розмір таблиці сторінок, тут бажаний великий розмір сторінки (сторінок менше, відповідно й таблиця сторінок менше). З іншого боку, пам’ять кращр утилізується з маленьким розміром сторінки. У середньому половина останньої сторінки процесу пропадає. Необхідно також ураховувати обсяг вводу-висновку для взаємодії із зовнішньою пам’яттю й інші фактори. Гроблема не має ідеального рішення. Історична тенденція складається в збільшенні розміру сторінки. Як правило, розмір сторінок задається апаратно, наприклад в DEC PDP-11 - 8 Кбайт, в DEC VAX - 512 байт, в інших архітектурах, таких як Motorola 68030, розмір сторінок може бути заданий програмно. З огляду на всі обставини, у ряді архітектур виникають множинні розміри сторінок, наприклад в Pentium розмір сторінки коливається від 4 Кбайт до 8 Кбайт. Гроте більшість комерційних ОС через складність переходу на множинний розмір сторінок підтримують тільки один розмір сторінок. Висновок У дійсній лекції розглянуті апаратні особливості підтримки віртуальної пам’яті. Розбивка адресного простору процесу на частині й динамічній трансляції адреси дозволили виконувати процес навіть під час відсутності деяких його компонентів в оперативній пам’яті. Підкачування відсутніх компонентів з диска здійснюються операційною системою в той момент, коли в них виникає необхідність. Наслідком такої стратегії є можливість виконання більших програм, розмір яких може перевищувати розмір оперативної пам’яті. Щр>б забезпечити даній схемі потрібну продуктивність, відображення адрес здійснюється апаратно за допомогою багаторівневої таблиці сторінок й асоціативної пам’яті. |