Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

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

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

Рис. 10.5. Сторінкове розподіл пам'яті

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

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

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

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

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

• найдовше не використовувалася сторінка;

• перша-ліпша сторінка;

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

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

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

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

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

Віртуальний адресу при сторінковому розподілі може бути представлений у вигляді пари (р, sv), де р - порядковий номер віртуальної сторінки процесу (нумерація сторінок починається з 0), a sv - зміщення в межах віртуальної сторінки. Фізична адреса також може бути представлений у вигляді пари (n, sf), де n - номер фізичної сторінки, a sf - зміщення в межах фізичної сторінки. Завдання підсистеми віртуальної пам'яті полягає у відображенні (р, sv) в (n, sf).

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

Перше з них полягає в тому, що обсяг сторінки вибирається рівним ступеня двійки - 2k. З цього випливає, що зсув s може бути отримано простим відділенням k молодших розрядів в двійковій запису адреси, а решта старші розряди адреси представляють собою двійковий запис номера сторінки (при цьому неважливо, є сторінка віртуальної або фізичної). Наприклад, якщо розмір сторінки 1 Кбайт (210), то з двійкової запису адреси 50718 = 101000111 0012 можна визначити, що він належить сторінці в двійковому виразі 102, і зміщений щодо її початку на 1000111 0012 байт.

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

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

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

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

1. Із спеціального регістра процесора витягується адреса AT таблиці сторінок активного процесу. На підставі початкової адреси таблиці сторінок, номера віртуальної сторінки р (старші розряди ВА) і довжини окремого запису в таблиці сторінок L (системна константа) визначається адресу потрібного дескриптора в таблиці сторінок: a = AT + (p * L).

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

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

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

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

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

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

З іншого боку, якщо сторінка велика, то велика і фіктивна область в останній віртуальній сторінці кожної програми. У середньому на кожній програмі губиться половина обсягу сторінки, що в сумі при великій сторінці може скласти істотну величину. З наведених міркувань випливає, що вибір розміру сторінки є складною оптимізаційної завданням, що вимагає врахування багатьох факторів. На практиці ж розробники ОС і процесорів обмежуються якимось раціональним рішенням, придатним для широкого класу обчислювальних систем. Типовий розмір сторінки становить кілька кілобайт. Наприклад, найбільш поширені процесори х86 і Pentium компанії Intel, а також операційні системи, що встановлюються на цих процесорах, підтримують сторінки розміром 4096 байт (4 Кбайт). Так, процесор Pentium дозволяє використовувати також сторінки розміром до 4 Мбайт одночасно зі сторінками об'ємом 4 Кбайт.

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

Багаторівневі таблиці сторінок. Розмір сторінки впливає також на кількість записів в таблицях сторінок. Чим менше сторінка, тим більш об'ємними є таблиці сторінок процесів і тим більше місця вони займають у пам'яті. Враховуючи, що в сучасних процесорах максимальний об'єм віртуального адресного простору процесу, як правило, не менше 4 Гбайт (232), то при розмірі сторінки 4 Кбайт (212) і довжині запису 4 байта для зберігання таблиці сторінок може знадобитися 4 Мбайт пам'яті! Виходом в такій ситуації є збереження в пам'яті лише тієї частини таблиці сторінок, яка активно використовується в даний період часу. Так як сама таблиця сторінок зберігається в таких же сторінках фізичної пам'яті, що й описувані нею сторінки, то принципово можливо тимчасово витісняти частину таблиці сторінок з оперативної пам'яті. Це означає, що самі таблиці сторінок стають об'єктами сторінкової організації, як і будь-які інші сторінки.

Щоб обійти проблему необхідності постійного зберігання в пам'яті величезних таблиць сторінок деякі процесори використовують багаторівневу таблицю сторінок. При такій схемі є каталог таблиць сторінок, в якому кожен запис вказує на таблицю сторінок. Таким чином, якщо розмір каталогу - Х, а максимальний розмір таблиці - Y, то процес може складатися максимум з X * Y сторінок. Зазвичай максимальний розмір таблиці сторінок визначається умовою її розміщення в одній сторінці (як у Pentium).

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

Всі сторінки мають однаковий розмір, а розділи містять однакову кількість сторінок. Якщо розмір сторінки і кількість сторінок у розділі вибрати рівними ступеня двійки (2k і 2n відповідно), то приналежність віртуального адреси до поділу і сторінці, а також зміщення всередині сторінки, можна визначити дуже просто: молодші k двійкових розрядів дають зсув, такі n розрядів представляють собою номер віртуальної сторінки, а решта старші розряди (позначимо їх кількість m) містять номер розділу.

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

Рис. 10.7. Структура віртуального адресного простору з розділами

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

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

Простежимо більш детально схему перетворення адрес для випадку дворівневої структуризації віртуального адресного простору (рис. 10.8).:

1. Шляхом відкидання k + n молодших розрядів у віртуальному адресі визначається номер розділу, до якого належить даний віртуальний адресу.

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

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

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

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

Рис. 10.8. Схема перетворення віртуальної адреси для дворівневої структуризації адресного простору

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

Проблема прискорення пошуку вирішується на рівні архітектури комп'ютера.

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

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

Для вирішення цієї проблеми більшість використовуються схем віртуальної пам'яті використовують спеціальний високошвидкісний кеш для записів таблиць сторінок, який зазвичай називають буфером швидкого перетворення адреси, або буфером пошуку трансляції (translation lookaside buffer - TLB), або буфер асоціативної трансляції, або іноді асоціативної пам'яттю.

Грунтуючись на правилі "дев'яносто до десяти" (правилі локалізації), що більшість програм схильне робити величезну кількість звернень до невеликої кількості сторінок, комп'ютер забезпечується невеликим апаратним пристроєм, що служить для відображення віртуальних адрес у фізичні без проходу по таблиці сторінок. Воно зазвичай знаходиться всередині диспетчера пам'яті і складається з кількох записів, від 8 до 4096. Так, в архітектурі Intel-32 таких елементів до Pentium-4 було 32 (що забезпечується 98% попадань в кеш), починаючи з Pentium-4 - 128.

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

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

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

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

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

Припустимо, наприклад, що для визначення адреси в разі кеш-промаху через таблицю сторінок необхідно 100 нс (t1), а для визначення адреси в разі кеш-попадання через асоціативну пам'ять - 20 нс (t2). З 90% hit ratio (p - імовірність кеш-попадання) середній час визначення адреси за формулою повної ймовірності t = t1 (1 - p) + t2p = 100 * 0,1 + 20 * 0,9 = 28 нс.

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

Інвертовані таблиці сторінок, хеш-таблиці. Традиційні таблиці сторінок вимагають по одному запису на кожну сторінку. Якщо адресний простір складається з 232 байт з розміром сторінки 4096 байт, тоді таблиця сторінок містить більше мільйона записів. При цьому таблиця сторінок займатиме мінімум 4 Мбайт. При 64-розрядному адресному просторі з розміром сторінки 4 Кбайт і розміром записи таблиці в 8 байт, таблиця займе більше 30 Тбайт. Це, звичайно, нереально навіть у майбутньому.

Тому ще одним підходом до використання одно-або дворівневих таблиць сторінок є застосування інвертованою таблиці сторінок. Цей підхід застосовується на машинах PowerPC, деяких робочих станціях Hewlett-Packard, IBM RT, IBM AS/400 і ряді інших.

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

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

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

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

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

Наприклад, вставка елемента в таблицю відбувається наступним чином.

1. Перетворимо мітку елемента в майже випадкове число n між 0 і М-1 методом розподілу мітки по модулю М.

2. Використовуємо отримане значення n в якості індексу в хеш-таблиці:

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

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

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

Середня тривалість пошуку елемента при відкритій хеш-таблиці з використанням таблиць переповнення з ланцюжками, рівна 1 + (N-1) / 2M, для великих значень N = M прагне до 1.5, зокрема для бінарного пошуку в сортувати списки тривалість пошуку елемента дорівнює Log2M .

Визначення найкращого розміру сторінки. Найчастіше розмір сторінки є параметром, обираним ОС. Навіть, якщо апаратне забезпечення передбачає, наприклад, розмір сторінки 512 байт, ОС може просто розглядати сторінки 0 і 1, 2 і 3, 4 і 5 і т.д. як сторінки розміром 1 Кбайт, завжди представляючи для них два послідовних сторінкових блоку.

Визначення найкращого розміру сторінки вимагає врівноваження декількох факторів. Тому не існує абсолютного оптимального рішення. Існує два доводи на користь маленького розміру сторінок. Випадково обраний текст, дані або сегмент стека не заповнює ціле кількість сторінок. В середньому половина останньої сторінки виявляється порожньою. Якщо в пам'яті n сегментів при розмірі сторінки р байт, то np / 2 байт буде витрачено даремно в результаті внутрішньої фрагментації. Це розумний аргумент на користь сторінок невеликого розміру.

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

З іншого боку, невеликий розмір сторінки означає, що програмам буде потрібно багато сторінок, отже, величезна таблиця сторінок. Як правило, сторінка за раз переноситься на диск і з нього. При цьому велика частина часу йде на пошук циліндра і затримку обертання. Так що переміщення маленької сторінки займає майже стільки ж часу, скільки і великий. Може знадобитися 64 * 10 мс, щоб завантажити 64 сторінки розміром 512 байт, і всього лише 4 * 12 мс для завантаження 4-х сторінок по 8 Кбайт.

Враховуючи все це можна математично проаналізувати розмір сторінки. Нехай середній розмір процесу дорівнює S байт, а сторінки - Р байт. Крім того, припустимо, що запис для кожної сторінки вимагає Е байт. Тоді приблизну кількість сторінок, необхідне для процесу, так само S / P, що забере SE / P байт для таблиці сторінок. Втрата пам'яті в останній сторінці процесу дорівнює P / 2. Таким чином, загальні накладні витрати внаслідок підтримки таблиці сторінок і втрати від внутрішньої фрагментації дорівнюють сумі цих складових: витрата = SE / P + P / 2.

Перший доданок (розмір таблиці сторінок) збільшується при зменшенні розміру сторінок. Другий доданок (внутрішня фрагментація) при збільшенні розміру сторінок зростає. Оптимальний варіант повинен знаходитися десь посередині. Якщо взяти 1-у похідну по перемінної Р і прирівняти її до нуля, отримаємо рівність: -SE/P2 + ½ = 0.

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

Для середнього розміру процесу S = 1 Мбайт і розміру запису в таблиці сторінок E = 8 байт оптимальний розмір сторінки буде дорівнює 4 Кбайт. У сучасних комп'ютерах більш часто зустрічаються розміри сторінок 4 Кбайт або 8 Кбайт. Так як пам'яті стає більше, то розмір сторінок також має тенденцію росту (але залежність нелінійна).

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Поняття віртуальної пам'яті	\|	Сегментний розподіл

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.015 сек.