Оперативна пам'ять

FIFO (first-in-first-out). Найбільш простим алгоритмом заміщення сторінок є алгоритм FIFO. Цей алгоритм асоціює з кожною сторінкою час, коли ця сторінка була поміщена в пам'ять. Для заміщення вибирається найбільш стара сторінка.

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

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

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

Алгоритм LRU (least recently used). Алгоритм вибирає для заміщення ту сторінку, на яку не було посилання на протязі найдовшого періоду часу. Він асоціює з кожною сторінкою час останнього використання цієї сторінки. Для заміщення вибирається та сторінка, яка не використовувалась довше за інші. Зазвичай застосовуються два підходи при використанні цього алгоритму:

підхід на основі логічного годинника (лічильника) – асоціюють з кожним рядком таблиці поле „час використання”, а в CPU додається логічний годинник. Логічний годинник збільшує своє значення при кожному звертанні до пам'яті. Кожен раз, коли здійснюється посилання на сторінку, значення регістра логічного годинника копіюється в поле „час використання”. Заміняється сторінка з найменшим значенням в цьому полі шляхом сканування всієї таблиці сторінок. Сканування буде відсутнім, якщо використовується підхід на основі стеку;

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

Алгоритм LFU (least freqently used). Цей алгоритм заміняє ту сторінку, яка використовується найменш частіше. Спосіб упорядкування схожий на LRU.

Також можливий випадковий вибір сторінки. Такий алгоритм називається random – замінюється сторінка, яка вибирається випадково.

В більшості сучасних ОС використовується дисципліна заміщення сторінок LRU, як сама ефективна. Так, саме ця дисципліна використовується в OS/2 і Linux. Але в такій ОС, як Windows NT, розробники, прагнучи зробити систему максимально незалежною від апаратних можливостей процесора, пішли на відмову від цієї дисципліни і застосували правило FIFO.

 

 

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

На наступному рівні розташовується більш швидкодіюча (час доступу1 дорівнює приблизно 10-20 наносекундам) і менш об'ємна (від десятків мегабайт до декількох гігабайт) ОП, реалізована на відносно повільній динамічній пам'яті DRAM.

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

І нарешті, верхівку в цій піраміді складають внутрішні регістри процесора, що також можуть бути використані для проміжного збереження даних. Загальний обсяг регістрів складає кілька десятків байт, а час доступу визначається швидкодією процесора і дорівнює в даний час зразково 2-3 нc.

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

 

 

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

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

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