Структура буфера TLB страничного преобразования

           Наличие буфера TLB позволяет в большинстве случаев обойтись без считывания элементов PDE и PTE из ОП при преобразовании линейного адреса в физический.

TLB — суть КЭШ-память.

 

                                              

 

 

атрибуты U/S, R/W, D

       С буфером TLB (как и с КЭШ-памятью) определены очереди поиска и записи данных с привлечением регистров TR7, TR6 (TR3, TR4, TR5).

Алгоритмы управления многоуровневой памятью

           

       верхний уровень — ОП

       нижний уровень — внешняя П

1. Важность алгоритмов управления памятью при страничной организации.

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

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

 

 

	В ОП находится r страниц программы Q 1<r<k

 

 

           

 

 

       Q={1, 2,..., k}

       программа состоит из k страниц

       Выполнение пргораммы вызывает обращение к страницам программы:

                                          q₀, q₁, q₂, q₃... q_t   qÎQ

                              Пр:  1, 2, 4, 3, 4,...

Пусть S_t — множество страниц прграммы Q, находящихся в данный момент (t) в памяти, тогда

страницы нет в ОП

                                  

           

       Трудность в определении vt заключается в том, что отсутствует информация о последующих обращениях в программе.

       Алгоритмы делятся на две группы:

1) физически нереализуемые (используют информацию о последующих обращениях); физически нереализуемые (используют информацию о

2) физически реализуемые (используют информацию только об истории процесса)

       Виды алгоритмов:

1) физически нереализуемые:

 — Алгоритм Михновеного-Шора

  алгоритм основан на использовании информации о реальном поведении программы.

  При каждом замещениистраницы в ОП из нее отсылается страница, очередное обращение к которой произойдет позже всего (минимально возможная для данной программы зам)

                          1, 2, 3, 4, 5, 6, 2, 3, 4, 2, 3, 4, 1, 5, 1, 2, 3

                          удал наруш

2) физически реализуемые алгоритмы:

¾ алгоритм случайного замещения;

¾ первым пришел — первым ушел.

                                          (FIFO)

                   удаляется самая “старая” страница

                              список, упорядочен по номерам страниц

       При каждом страничном нарушении элемент списка суммируется с единицей по модулю k (k — количество физических страниц). В случае замещении страницы самая “старая” при суммировании с 1 станет равной 0, ее и необходимо удалить.

¾  алгоритм LRU (Last Resently Used)

(вытеснение по давности использования)

Необходима аппаратная поддержка для сохранения информации об использовании страницы (бит А). На основании опроса этих бит через определенные интервалы времени составляется таблица, где ведется учет, какая из страниц наиболее давно использовалась.

¾ Алгоритм “последним пришел — первым ушел”

       отсылается страница, позже других поступившая в память

¾ алгоритм “??????????????? страница”

       St = j1, j2,... jm-1, jm, jm+1,..., jr

последовательность страниц при страничном нарушении:

 

(а) не изменяется

(б) “попавшая” страница перемещается вверх на одну позицию

(в) последняя удаляется и на ее место записывается новая

 

 

“ — “ необходимо изменять таблицу при каждой смене страницы.

— алгоритм рабочий комплект.

       Страницы в ОП, использовавшиеся в течение заданного интервала времени образуют “рабочий комплект”. Страницы из памяти, не вошедшие в РК формируют две очереди кандидатов на удаление:

1 — страницы, в которых производилась запись и

2 — страницы, которые не изменялись.

       Замещение при страничном сбое производится по правилу: первый пришел из РК, первый ушел из памяти верхнего уровня, причем сначала удаляются страницы из очереди 2, так как их не нужно сохранять.

       Физически нереализуемый алгоритм служит эталоном для определения эффективности того или иного алгоритма.