Дескриптор сторінки

Базова

фізична адреса

Другий сторінки

етап

Вихідна

фізична адреса

Розглянемо ще одну схему керування пам'яттю, засновану на сегментно-сторінковому підході.

Логічна адреса

Н омер сегменту s

Н омер сторінки р всередині сегменту s

Зміщення всередині с торінки d

Таблиця сегментів

Таблиця сторінок сегмента s

Фізична сторінка

Cегмент s

Cторінка p

Елемент d

Відмінність цього підходу полягає в тому, що віртуальні сторінки нумеруються не в межах усього адресного простору процесу, а в межах сегмента. Віртуальна адреса в цьому випадку виражається трійкою (номер сегмента, номер сторінки, зміщення у сторінці). Для кожного процесу створюється своя таблиця сегментів, а для кожного сегмента - своя таблиця сторінок. Тоді

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

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

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

Кеш пам'ять

Пам’ять ЕОМ - це ієрархія запам’ятовуючих пристроїв, які відрізняються середнім часом доступу до даних, об’ємом і вартістю зберігання 1 біта інформації.

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

Кешем часто називають ще й один із пристроїв - швидкий запам’ятовуючий пристрій. Він дорожчий і має порівняно невеликий обсяг порівняно з «повільним» - оперативною пам’яттю.

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

Вміст кеш-пам’яті являє собою сукупність записів про всі завантажені в неї елементи даних з основної пам’яті. Кожен запис містить:

• елементи даних;

• адресу цього елемента в основній пам'яті;

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

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

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

Далі можливі два варіанти дії:

1. дані виявлені в кеш-пам'яті (тобто має кеш-влучення), і вони зчитуються й передаються джерелу запиту;

2. потрібні дані відсутні (тобто відбувся кеш-промах), і вони зчитуються з основної пам’яті, передаються джерелу запиту й одночасно копіюються в кеш-пам’ять.

Ефективність кешувания залежить від імовірності влучення в кеш.

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

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

1. наскрізний запис (write through). При запиті до основної пам'яті (у тому числі при записі) проглядається кеш. Якщо дані по запитуваній адресі відсутні, запис виконується тільки в основну пам’ять. Якщо дані перебувають у кеші, запис робиться у кеш і у пам’ять.

2. зворотний запис (write back). Виконується перегляд кешу. Якщо даних там немає, то запис робиться в основну пам’ять. Інакше запис робиться тільки в кеш. При цьому встановлюється ознака модифікації. При витисненні даних з кешу ці дані будуть переписані в основну пам’ять.

Алгоритми пошуку й заміщення даних у кеші залежать від того, як основна пам’ять відображається на кеш. Використаються дві схеми відображення:

1. випадкове відображення;

2. детерміноване відображення.

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

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

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

Між номерами рядків кеш- пам’яті й адресами оперативної пам’яті встановлюється відповідність «один до багатьох»: одному номеру рядка відповідає декілька (досить багато) адрес оперативної пам’яті.

Можна використати просте виділення декількох розрядів з адреси оперативної пам’яті, які інтерпретуються як номер рядка кеш-пам’яті. Таке відображення називається прямим. Наприклад, кеш розрахований на 1024 записа (1024 рядка). Тоді будь-яка адреса оперативної пам'яті може бути відображена на адресу кеш- пам’яті простим відділенням 10 двійкових розрядів.

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

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

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

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

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

Завдання на виконання роботи

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

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

2. Продемонструвати роботу моделі та перетворення віртуальної адреси у фізичну згідно алгоритму.

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

Якщо потрібно за алгоритмом, додатково продемонструвати процес вивантаження-завантаження сегментів або сторінок.

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

Мова програмування довільна.

Вміст звіту

1. Індивідуальне завдання на виконання роботи згідно варіанту.

2. Код (текст) програми.

3. Результати роботи програми.

4. Висновки щодо алгоритму управління пам’яттю за результатами роботи.