Управління пам'яттю

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

Для ідентифікації змінних і команд використовуються символьні імена (мітки), віртуальні адреси та фізичні адреси (малюнок 2.7).

Символьні імена присвоює користувач при написанні програми на алгоритмічній мові або асемблері.

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

Рис. 2.7. Типи адрес

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

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

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

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

Рис. 2.8. Класифікація методів розподілу пам'яті Розподіл пам'яті фіксованими розділами

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

Рис. 2.9. Розподіл пам'яті фіксованими розділами:
а - із загальною чергою; б - з окремими чергами

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

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

У цьому випадку пам'ять машини не ділиться заздалегідь на розділи. Спочатку вся пам'ять вільна. Кожній знову надходить задачі виділяється необхідна їй пам'ять. Якщо достатній обсяг пам'яті відсутній, то задача не приймається на виконання і стоїть у черзі. Після завершення завдання пам'ять звільняється, і на це місце може бути завантажена інша задача. Таким чином, в який момент часу оперативна пам'ять є випадковою послідовність зайнятих і вільних ділянок (розділів) довільного розміру. На малюнку 2.10 показано стан пам'яті в різні моменти часу при використанні динамічного розподілу. Так у момент t0 в пам'яті знаходиться тільки ОС, а до моменту t1 пам'ять розділена між 5 задачами, причому задача П4, завершуючись, залишає пам'ять. На звільнилося після завдання П4 місце завантажується задача П6, що надійшла в момент t3.

Рис. 2.10. Розподіл пам'яті динамічними розділами

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

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

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

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

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

Рис. 2.11. Розподіл пам'яті переміщуваними розділами

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 2.14. Розподіл пам'яті сегментами

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

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

Недоліком цього методу розподілу пам'яті є фрагментація на рівні сегментів і більш повільне у порівнянні з сторінкової організацією перетворення адреси. Сторінковому-сегментні розподіл

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

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

Різновидом віртуальної пам'яті є свопінг.

На малюнку 2.16 показаний графік залежності коефіцієнта завантаження процесора в залежності від кількості одночасно виконуваних процесів і частки часу, проведеного цими процесами в стані очікування вводу-виводу.

Рис. 2.16. Залежність завантаження процесора від числа задач і інтенсивності вводу-виводу

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

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

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

Рис. 2.17. Ієрархія ЗУ

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

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

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

Рис. 2.18. Кеш-пам'ять

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

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

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