Номер стор.

таблиці

13 11

Зсув

Лінійна адреса

Figure: Сторiнкове перетворення адреси в i386

Сергiй Стасюк Системне програмне забезпечення

Page table structures, структури таблиць сторiнок

24 23

16 15 8 7 0

10 10 12

page table

32*

CR3

*) 32 bits aligned to a 4-KByte boundary

Figure: No PAE, 4 kB pages

Сергiй Стасюк Системне програмне забезпечення

Page table structures, структури таблиць сторiнок

Linear address: 31

24 23

16 15 8 7 0

10 page directory 22

32 bit PD entry

PS = 1

32*

CR3

*) 32 bits aligned to a 4-KByte boundy

Figure: No PAE, 4 MB pages

Сергiй Стасюк Системне програмне забезпечення

Page table structures, структури таблиць сторiнок

Linear address:

24 23

16 15 8 7 0

32*

page-directory- pointer table

Dir.Pointer entry

Dir.Pointer entry

Dir.Pointer entry

Dir.Pointer entry

9 9 12

page table

64 bit PD entry

64 bit PT entry

CR3

*) 32 bits aligned to a 32-Byte boundary

Figure: PAE with 4 kB pages

Сергiй Стасюк Системне програмне забезпечення

Page table structures, структури таблиць сторiнок

Linear address:

24 23

16 15 8 7 0

page-directory-

9 21

pointer table page directory

Dir.Pointer entry

Dir.Pointer entry

Dir.Pointer entry

Dir.Pointer entry

64 bit PD entry

32*

CR3

Figure: PAE with 2 MB pages

Сергiй Стасюк Системне програмне забезпечення

Питання?

Сергiй Стасюк Системне програмне забезпечення

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

Сергiй Стасюк

ЧДТУ

25 жовтня 2011 р.

Сергiй Стасюк Системне програмне забезпечення

Стратегiї керування вiртуальною пам’яттю

Розглядатимемо в термiнах сторiнкової органiзацiї. Види стратегiй:

Стратегiї заштовхування (пiдкачки) сторiнок; Стратегiї розмiщення;

Стратегiї виштовхування(замiщення).

Дисциплiни пiдкачки: Випереджаюча пiдкачка; Пiдкачка на вимогу.

Сергiй Стасюк Системне програмне забезпечення

У iдеальному випадку будь-яке звернення до сторiнки не повинне викликати переривання по вiдсутностi сторiнки в пам’ятi. Проте реалiзацiя пiдкачки на вимогу вимагає значно менших витрат.

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

Сергiй Стасюк Системне програмне забезпечення

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

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

Сергiй Стасюк Системне програмне забезпечення

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

Сергiй Стасюк Системне програмне забезпечення

Дисциплiни витiснення (вiдкачки, замiщення) сторiнок

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

Дисциплiна виштовхування випадкової сторiнки – проста, застосовується рiдко i має найменшу ефективнiсть.

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

Сергiй Стасюк Системне програмне забезпечення

Дисциплiни витiснення (вiдкачки, замiщення) сторiнок

Дисциплiна LRU (Least Recently Used) – витiсняється сторiнка, яка довше за iнших не використовувалася.

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

Дисциплiна LFU (Least Frequently Used) – виштовхується найменш часто використовувана сторiнка. Необхiдно контролювати iнтенсивнiсть використання сторiнок. Можливий випадок, коли найменш часто використовуваною виявляється сторiнка, тiльки що помiщена в ОЗП i вона знову пiддається свопiнгу.

Сергiй Стасюк Системне програмне забезпечення

Дисциплiни витiснення (вiдкачки, замiщення) сторiнок

Дисциплiна NUR (No Used Recently) – виштовхується сторiнка, що не використовувалася останнiм часом. Перевага при витiсненнi вiддається тим сторiнкам, якi не модифiкувалися, – їх не потрiбно фiзично переписувати на ЗЗП, а можна просто замiнити iншими сторiнками.

Для реалiзацiї цього алгоритму в дескрипторi будь-якої сторiнки передбачаються два бiти-ознаки:

1 Звернення = 0/1 (не було/було)

2 Модифiкацiя = 0/1 (не було/була).

Сергiй Стасюк Системне програмне забезпечення

Дисциплiни витiснення (вiдкачки, замiщення) сторiнок

Перiодично бiти-ознаки скидаються в нуль. Виштовхування вiдбувається за наступним правилом: виштовхується перша сторiнка в списку з бiтами = 0 i = 0, якщо таких немає, то A = 1, M = 0 i т. д. вiдповiдно до наступної таблицi.

Сергiй Стасюк Системне програмне забезпечення

Дисциплiни витiснення (вiдкачки, замiщення) сторiнок

Дисциплiна FINUFO (First In and if Not Used First Out) – першим увiйшов i, якщо не використовується, – першим вийшов. З кожною сторiнкою зв’язується бiт використання, а уся таблиця сторiнок упорядковується в кругову чергу з посиланням на останню завантажену. Покажчик просувається вперед до першої сторiнки з нульовим бiтом використання i скидає на шляху бiти використання пройдених сторiнок.

Сергiй Стасюк Системне програмне забезпечення

Методи керування вiльною пам’яттю

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

Коли деяка дiлянка пам’ятi бiльше не потрiбна програмi, вiдомостi про це отримує планувальник пам’ятi. У його завдання входить облiк i перерозподiл пам’ятi, що явно звiльняється, а також звiльнення пам’ятi, яка не потрiбна для подальшого використання програмi, але явно не звiльнена – “збирання смiття”.

Сергiй Стасюк Системне програмне забезпечення

Методи керування вiльною пам’яттю

Зазвичай ОС зберiгає вiдомостi про вiльну пам’ять використовуючи саму цю пам’ять.

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

Зв’язування областей (дiлянок) вiльної пам’ятi в один список;

Маркування слiв вiльної пам’ятi;

Зв’язування вiльної пам’ятi в декiлька спискiв по методу близнюкiв.

Сергiй Стасюк Системне програмне забезпечення

Зв’язування вiльної пам’ятi в один список

Вiльнi блоки зв’язуються в список, де кожен блок мiстить вiдомостi про свiй розмiр i посилання на наступний блок (приклад – MS-DOS). Планувальнику пам’ятi вiдоме посилання на перший блок в цьому списку. Якщо список упорядковується по адресах блокiв, то можна зливати сумiжнi блоки в один. Iнодi блоки упорядковуються за збiльшенням (чи зменшенням) їх розмiру. Це ускладнює злиття сусiднiх блокiв, але прискорює пошук блокiв вiдповiдного розмiру при використаннi двонаправленого списку (в середньому переглядається чверть списку).

Сергiй Стасюк Системне програмне забезпечення

Маркування слiв вiльної пам’ятi

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

Сергiй Стасюк Системне програмне забезпечення

Система близнюкiв

Блоки пам’ятi мають розмiри, рiвнi ступеням двiйки; для кожного розмiру iснує свiй список вiльних блокiв. Тобто для кожного K = 0 ..N, де 2 N – розмiр усiєї пам’ятi, створюється свiй список вiльної пам’ятi розмiром 2 K.

Якщо потрiбно блок розмiром 2 K, а вiдповiдний список порожнiй, то переглядається список блокiв розмiру 2 K +1. Якщо такий блок знайдений, то вiн розбивається на два блоки розмiром 2 K, з яких один видiляється завданню, а iнший заноситься в список вiльних блокiв розмiром 2 K. Якщо блоку розмiром 2 K +1 немає, то шукається вiльний блок розмiром

2 K +2 i так далi.

Сергiй Стасюк Системне програмне забезпечення

Система близнюкiв

Якщо звiльняється блок розмiром 2 K, тодi шукається його близнюк, тобто вiльний сумiжний з ним блок того ж розмiру. Якщо близнюк є, то вони зливаються в один блок, який помiщається в список вiльних блокiв розмiром 2 K +1 з перевiркою на наявнiсть там близнюка, i так далi.

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

Сергiй Стасюк Системне програмне забезпечення

Збирання смiття

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

Збирання смiття може виконуватися в два етапи. Спочатку маркуються усi досяжнi в даний момент елементи динамiчних структур даних. Потiм видима дiлянка динамiчної пам’ятi i невiдмiченi елементи додаються до списку вiльної пам’ятi.

У сучасних системах програмування (C, Pascal, C++) програмiст може i повинен явно звiльняти непотрiбну динамiчну пам’ять.

У системах програмування бiльш високого рiвня (C++ з бiблiотеками, Java, Python) програмiст може залишити вивiльнення об’єктiв пам’ятi системi або взагалi не може явно вивiльняти об’єкти.

Сергiй Стасюк Системне програмне забезпечення

Керування пам’яттю в ОС Windows 95 (Windows NT)

Системнi обмеження Windows 95:

Реалiзованi не всi функцiї Win 32, деякi є тiльки заглушками;

Окремi функцiї API залишилися 16-розряднми;

Windows 95 допускає до 16364 вiкон i стiльки же незалежних меню – це менше, нiж у Windows NT, але значно бiльше, нiж в Windows 3.1;

Максимальна кiлькiсть областей пам’ятi – 16 Кб; Гранична дата для файлової системи FAT – 31.12.2099.

Адресний простiр кожного процесу (4Гб, 32 бiт) дiлиться на двi частини: молодшi 2 Гб (0x0-0x7FFFFFFF) доступнi користувачевi, а старшi 2 Гб (0x80000000-0xFFFFFFF) зарезервованi для використання ядром. Для кожного процесу ядро пiдтримує сторiнкову карту (page map).

Сергiй Стасюк Системне програмне забезпечення

Керування пам’яттю в ОС Windows 95 (Windows NT)

Сторiнковий механiзм Windows 95 використовує сторiнки розмiром 4КiБ i алгоритм LRU для витiснення сторiнок. Сторiнки вiртуального адресного простору процесу можуть знаходитися в одному з трьох станiв:

1 Вiльна – не використовується в даний момент, але може бути зарезервована або пов’язана з фiзичною пам’яттю.

2 Зарезервована – не пов’язана з фiзичною пам’яттю i недоступна для розподiлу.

3 Зайнята – сторiнка вiдображена на фiзичний адресний простiр (у пам’ятi або на диску).

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

Сергiй Стасюк Системне програмне забезпечення

Керування пам’яттю в ОС Windows 95 (Windows NT)

Для сумiсностi з Windows 3.1 залишилося поняття “Movable memory” або “Discardable memory”. У Windows 3.1 блоки такої пам’ятi могли перемiщатися системою в цiлях ущiльнення, в Windows 95 вони можуть бути звiльненi.

Рекомендується використовувати в програмах для керування пам’яттю тiльки стандартнi функцiї C (malloc, free i так далi). Проте iснує можливiсть управляти сторiнками вiртуального адресного простору iз застосунку:

VirtualAlloc - приєднує, резервує i звiльняє сторiнки.

VirtualLock, VirtualUnlock - блокує/розблоковує сторiнки (заблокована не пiддається свопiнгу).

VirtualProtect - мiняє атрибути захисту пам’ятi.

Сергiй Стасюк Системне програмне забезпечення

Керування пам’яттю в ОС Windows 95 (Windows NT)

Функцiї для роботи з купами (Heaps) рекомендується використовувати для початкового видiлення (перевiрки доступностi) пам’ятi процесу.

Спiльна пам’ять Win 32 реалiзована за допомогою механiзму вiдображення файлiв. Вмiст вказаного файлу вiдображається на спiльну пам’ять. Якщо файл, що вiдображається, – swapfile Windows, то данi з нього не завантажуються в ОЗП при створеннi дiлянки спiльної пам’ятi.

Механiзм вiдображення файлiв можна використати для запуску програм EXE i DLL; сторiнковi таблицi процесу налаштовуються так, щоб вони вказували на виконуваний файл на диску. Потiм управлiння передається на точку входу в програму i сторiнки завантажуються в ОЗП по мiру необхiдностi. Якщо процес спробує зробити запис в одну з таких сторiнок, вона буде призначена на файл пiдкачки.

Сергiй Стасюк Системне програмне забезпечення

Розподiл адресних просторiв пiдсистем Windows та застосункiв

Системна ВМ

Віртуальні машини DOS