Статьи

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

  1. управління пам'яттю Пам'ять є найважливішим ресурсом, що вимагає ретельного управління з боку мультипрограммной...
  2. Методи розподілу пам'яті без використання дискового простору
  3. Розподіл пам'яті фіксованими розділами
  4. Розподіл пам'яті розділами змінної величини
  5. переміщувані розділи
  6. Методи розподілу пам'яті з використанням дискового простору
  7. сторінкове розподіл
  8. сегментний розподіл
  9. Сторінково-сегментний розподіл
  10. свопінг
  11. Ієрархія запам'ятовуючих пристроїв. Принцип кешування даних

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

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

типи адрес

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

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

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

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

Мал. 2.7. типи адрес

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

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

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

Методи розподілу пам'яті без використання дискового простору

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

Почнемо з останнього, більш простого класу методів

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

Розподіл пам'яті фіксованими розділами

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

9, б)

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

Підсистема управління пам'яттю в цьому випадку виконує наступні завдання:

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

Розподіл пам'яті розділами змінної величини

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

На місце, що звільнилося після завдання П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. Механізм перетворення віртуальної адреси в фізичний
при сторінкової організації пам'яті

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

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

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

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

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

сегментний розподіл

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

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

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

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

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

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

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

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

Сторінково-сегментний розподіл

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

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

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

свопінг

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

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

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

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

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

Ієрархія запам'ятовуючих пристроїв. Принцип кешування даних

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

Кеш-пам'ять представляє деякий компромісне вирішення цієї проблеми

Мал. 2.17. ієрархія ЗУ

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

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

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

Мал. 2.18. Кеш-пам'ять

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

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

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

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

t = t1 ((1 - p) + t2 (p

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

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

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

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

попередня глава

|| Зміст || наступна глава

Новости