Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010

“Інформаційні управляючі системи та технології” 080402 “Інформаційні технології проектування” Одеса 2010




Сторінка20/24
Дата конвертації10.03.2017
Розмір1.41 Mb.
1   ...   16   17   18   19   20   21   22   23   24

7. 3 Сторінкова організація пам’яті


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

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


7.3.1. Базові принципи сторінкової організації пам’яті


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

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

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

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

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






Рис. 7.7 Перетворення адреси у разі сторінкової організації пам‘ті

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






Рис. 7.8 Логічний і фізичний адресний простір у разі сторінкової організайії пам’яті

ОС повинна мати інформацію про поточний стан фізичної пам’яті (про зайнятість і незайнятість фреймів, їхню кількість тощо).

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


7.3.2. Порівняльний аналіз сторінкової організації пам’яті та сегментації


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

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



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

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

Сторінкова організація пам’яті не позбавлена і недоліків.

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

  • Таблиці сторінок мають бути більші за розміром, ніж таблиці сегментів. Так, для виділення неперервного діапазону пам’яті розміром 100 Кбайт знадобиться один елемент таблиці сегментів, що описує сегмент, виділений для цього діапазону. З іншого боку, у разі використання сторінок розміром 4 Кбайт для опису такого діапазону нам знадобиться 25 елементів таблиці сторінок – по одному елементу для кожної сторінки.


7.3.3. Багаторівневі таблиці сторінок


Щоб адресувати логічний адресний простір значного обсягу за допомогою однієї таблиці сторінок, її доводиться робити дуже великою. Наприклад в архітектурі ІА-32 за стандартного розміру сторінки 4 Кбайт (для адресації всередині такої сторінки потрібні 12 біт) на індекс у таблиці залишається 20 біт, що відповідає таблиці сторінок на 1 мільйон елементів.

Щоб уникнути таких великих таблиць, запропоновано технологію багаторівневих таблиць сторінок. Таблиці сторінок самі розбиваються на сторінки, інформацію про які зберігають в таблиці сторінок вехнього рівня. Кількість рівнів рідко перевищує 2, але й може доходити до 4.

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

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


7.3.4. Реалізація таблиць сторінок в архітектурі ІА-32


Архітектура ІА-32 використовує дворівневу сторінкову організацію, починаючи з моделі Intel 80386.

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

Лінійна адреса поділяється на три поля:


  • Каталогу (Directory)- визначає елемент каталогу сторінок, що вказує на потрібну таблицю сторінок;

  • Таблиці (Table)-визначає елемент таблиці сторінок, що вказує на потрібний фрейм пам’яті;

  • Зсуву (Offset)- визначає зсув у межах фрейму, що у поєднанні з адресою фрейму формує фізичну адресу.

Розмір полів каталогу і таблиці становить 10 біт, що дає таблиці сторінок, які містять 1024 елементи, розмір поля зсуву – 12 біт, що дає сторінки і фрейми розміром 4 Кбайт. Одна таблиця сторінок нижнього рівня адресує 4 Мбайт пам’яті (1 Мбайт фреймів), а весь каталог сторінок – 4 Гбайт.

Елементи таблиць сторінок всіх рівнів мають однакову структуру. Виокремимо такі поля елемента:



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

  • 20 найбільш значущих бітів, які задають початкову адресу фрейму, кратну 4 Кбайт (може бути задано 1 Мбайт різних початкових адрес);

  • Прапорець доступу (Accessed), який покладають рівним одиниці під час кожного звертання пристрою сторінкової підтримки до відповідного фрейму;

  • Прапорець зміни (Dirty), який покладають рівним одиниці під час кожної операції записування у відповідний фрейм;

  • Прапорець читання-записування (Read/ Write), що задає права доступу до цієї сторінки або таблиці сторінок (для читання і записування, або тільки для читання);

  • Прапорець привілейованого режиму (User/ Supervisor), який визначає режим процесора, необхідний для доступу до сторінки. Якщо цей прапорець дорівнює нулю, сторінка може бути адресована тільки із привілейованого режиму, якщо одиниці – доступна також із режиму користувача;

Прапорці присутності, доступу і зміни можна використовувати ОС для організації віртуальної пам’яті.

7.3.5. Асоціативна пам’ять


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

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

Для розв’язання цієї проблеми було запропоновано технологію асоціативної пам’яті або кеша трансляції (translation look-aside buffers, TLB). У швидкодіючий пам’яті (швидшій ніж основна пам’ять) створюють набір із кількох елементів (різні архітектури відводять під асоціативну пам’ять від 8 до 2048 елементів, в архітектурі ІА-32 таких елементів до Pentium 4 було 32, починаючи з Pentium 4 - 128 ). Кожний елемент кеша трансляції відповідає одному елементу таблиці сторінок.

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

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




Рис. 7.9 Принцип роботи кеша трансляції

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


1   ...   16   17   18   19   20   21   22   23   24



  • 7.3.1. Базові принципи сторінкової організації пам’яті
  • 7.3.2. Порівняльний аналіз сторінкової організації пам’яті та сегментації
  • 7.3.3. Багаторівневі таблиці сторінок
  • 7.3.4. Реалізація таблиць сторінок в архітектурі ІА-32
  • 7.3.5. Асоціативна пам’ять