Жмакин А.П. Архитектура ЭВМ (2006) (1186252), страница 20
Текст из файла (страница 20)
попадании или заполнении строки. Они используются для реализации алгоритма замещения строки следующим образом.
Обозначим строки в множестве как LO, LI, L2, L3. Каждому множеству в блоке LRU соответствуют три бита ВО, Bl, В2, которые модифицируются при каждом кэш-попадании или заполнении строки множества следующим образом:
□ если последнее обращение было к строке L0 или L1, то бит ВО устанавливается в 1, иначе — сбрасывается в 0;
□ если последнее обращение в паре L0—L1 было к строке L0, то бит В1 устанавливается в 1, иначе — сбрасывается в 0;
□ если последнее обращение в паре L2—L3 было к строке L2, то бит В2 устанавливается в 1, иначе — сбрасывается в 0.
Выбор заменяемой строки (когда все строки множества достоверны) определяет содержимое битов ВО, Bl, В2 (табл. 5.1).
Цикл записи при наличии кэш-памяти может реализоваться по-разному. Различают кэш со сквозной записью и кэш с обратной записью.
В первом случае в цикле записи всегда осуществляется запись как в кэш, так и в ОЗУ. Этот способ записи не приводит к сокращению цикла записи даже при кэш-попадании, но гарантирует идентичность данных по адресам ОЗУ и кэш.
При обратной записи в случае кэш-попадания запись осуществляется только в кэш, при этом в соответствующей ячейке ОЗУ сохраняется прежнее (уже неверное) значение. Запись в ОЗУ происходит при очистке (замещении) строки кэш, если ее содержимое изменялось в процессе пребывания в кэш. Ситуация временного несоответствия содержимого ячеек кэш и ОЗУ может быть допустима в одних случаях и недопустима в других (например, когда несколько процессоров со своими кэш общаются через общее поле ОЗУ). Поэтому в большинстве случаев пользователю предоставляется возможность выбора способа записи в кэш — за счет модификации некоторых программно-доступных флагов в регистре управления.
В 80486 строки кэш-памяти можно по отдельности объявить недостоверными, задавая операцию недостоверности кэш-памяти на шине процессора. При инициализации такой операции кэш сравнивает объявленный недостоверным адрес с тегом строк, находящихся в кэш, и сбрасывает бит достоверности при обнаружении соответствия тегов. Предусмотрена также операция очистки, которая превращает в недостоверное все содержимое кэш. Конфигурацией кэш-памяти управляют два бита регистра CR0 состояния машины:
□ CD (Cache Disable) — запрещение кэш-памяти;
□ NW (Not Write-through) — несквозная (обратная) запись.
При CD = 1 и NW = 1 запрещено заполнение строк, сквозная запись и объявление кэш-памяти недостоверной. Такая конфигурация позволяет использовать внутреннюю кэш-память как быстродействующее ЗУПВ. При CD = 1 и NW = 0 заполнение строк запрещено, а сквозная запись и объявление кэш-памяти недостоверной разрешено. Эта конфигурация позволяет программе запрещать кэш-память на короткое время, а затем разрешать без очистки содержимого.
При СО = 0 и NW = 0 заполнение строк, сквозная запись и объявление кэшпамяти недостоверной разрешены. Такая конфигурация является обычной рабочей для кэш-памяти.
При СО = 0 и NW = 1 осуществляется работа кэш в режиме обратной записи. Когда кэширование разрешено, кэшируются считывания данных из ОЗУ и предвыборка команд, если внешняя схема подает входной сигнал разрешения кэш-памяти в данном цикле шины или текущий элемент таблицы страниц разрешает кэширование. В тех циклах, где кэширование запрещено при промахе, заполнение строки кэш-памяти не производится. Однако кэш-память продолжает действовать, несмотря на то, что она запрещена для заполнения. Уже находящиеся в кэш-памяти данные используются, если, конечно, они являются достоверными. (Фактически реализуется режим быстродействующего ОЗУ.) Только когда все данные в кэш-памяти отмечены как недостоверные, что происходит при ее очистке, все внутренние запросы считывания приводят к формированию внешних циклов шины.
Когда разрешена сквозная запись, все записи, в том числе и при кэш-попадании, инициируют запись в память. Когда сквозная запись запрещена, внутренний запрос записи, вызвавший попадание, не приводит к производству записи в ОЗУ, а операции недостоверности запрещены. Когда запрещены кэширование и сквозная запись, кэш-память можно использовать как быстродействующее статическое ОЗУ. В такой конфигурации на шину процессора передаются только записи, вызвавшие промах, а операции недостоверности игнорируются. Если предполагается использовать этот режим (cd =1 и nw = 1), следует предварительно загрузить достоверные строки, используя операции чтения из памяти или регистров.
5.3. Виртуальная память
Выше были рассмотрены способы организации сверхоперативной памяти и ее взаимодействия с оперативной. Не менее, а порой и более важной проблемой является организация взаимодействия в паре ОЗУ — ВЗУ.
Известно, что в современных ЭВМ (кроме простейших) реализовано динамическое распределение памяти между несколькими задачами, существующими в ЭВМ в процессе решения. Даже для однозадачных конфигураций проблема динамического распределения памяти не теряет актуальности, т. к. в памяти, помимо задачи пользователя, всегда присутствует операционная система или ее фрагмент.
Наличие динамического распределения памяти предполагает, что программа компилируется в т. н. "логических" адресах, а в процессе работы происходит автоматическое преобразование логических адресов в физические.
Наибольшее распространение в ЭВМ получил метод динамического распределения памяти, называемый страничной организацией виртуальной памяти. При использовании этого метода вся память ЭВМ (ОЗУ и ВЗУ) рассматривается как единая виртуальная память. Адрес в этой памяти называется виртуальным или логическим. Вся виртуальная память делится на фрагменты одинакового размера, называемые виртуальными страницами. Размер страницы обычно составляет 0,5—4 Кбайт. Виртуальный адрес представляется состоящим из двух частей— номера страницы и номера слова на странице (смещения).
Физическая память ЭВМ (ОЗУ и ВЗУ) так же делится на страницы, причем размер физической страницы выбирается равным размеру виртуальной. Таким образом, одна физическая страница может хранить одну виртуальную, причем порядок следования виртуальных страниц в программе совсем не обязательно сохранять на физических страницах. Достаточно лишь установить однозначное соответствие между номерами виртуальных и физических страниц.
Соответствие между номерами виртуальных и физических страниц устанавливается с помощью специальной страничной таблицы (СТ), которую поддерживает операционная система. Размер физической страницы равен размеру виртуальной, поэтому преобразования смещений на странице не производятся.
Поскольку размер СТ достаточно велик, она хранится целиком в ОЗУ и модифицируется операционной системой всякий раз, когда в распределении памяти происходят изменения.
Для увеличения скорости обращения к памяти активная часть СТ обычно хранится в специальной быстродействующей памяти, организованной, как правило, по ассоциативному принципу. При этом в поле признаков АЗУ СТ хранятся виртуальные адреса страниц (иногда вместе с номером программы — в мультипрограммных системах), а в информационной части — соответствующие им номера физических страниц.
Если в результате преобразования виртуального адреса в физический оказывается, что требуемая физическая страница располагается в ВЗУ, то выполнение программы становится невозможным, пока не произойдет "подкачка" требуемой страницы в ОЗУ. Такая ситуация называется страничным сбоем и должна формировать внутреннее прерывание, по которому запускается подпрограмма чтения страницы из ВЗУ в ОЗУ.
При этом возникает серьезная проблема поиска той страницы, которую можно удалить из ОЗУ, чтобы на освободившееся место записать требуемую страницу. Серьезность проблемы обусловлена тем, что неудачный выбор удаляемой страницы (в ближайшее время она вновь понадобится) связан со значительной потерей времени на передачу страниц между ОЗУ и ВЗУ.
5.3.1. Алгоритмы замещения
Правило, по которому при возникновении страничного сбоя выбирается страница для удаления из ОЗУ, называется алгоритмом замещения. Для данной программы, порождающей некоторый поток обращений к памяти, существует, по крайней мере, одна такая последовательность замещений страниц, которая дает для этой программы минимальное количество страничных сбоев.
Теоретически доказано, что минимальное число страничных сбоев будет получено, если в алгоритме замещения использовать информацию о потоке обращений к страницам в будущем (алгоритм Минховского — Шора) или, по крайней мере, о вероятности обращений к страницам в будущем. Алгоритмы замещения, использующие "информацию о будущем", называются физически нереализуемыми, их обычно применяют для оценки качества эвристических алгоритмов замещения.
Эвристические алгоритмы замещения используют информацию о потоке обращений к страницам в прошлом (историю процесса) для экстраполяции характеристик потока обращений в будущем. Как правило, используют три типа информации о прошлом: время пребывания страницы в ОЗУ (или, что то же— очередность поступления страниц), число обращений к страницам за определенный промежуток времени или отрезки времени с момента последнего обращения к страницам.
Эффективность эвристического алгоритма можно характеризовать отношением:
где N0 — число страничных сбоев при решении данной задачи с применением физически нереализуемого алгоритма; Ne — то же с применением исследуемого эвристического алгоритма.
Эвристический алгоритм можно считать выбранным удачно (для данного класса задач), если коэффициент к близок к 1. Значение NQ может быть получено путем моделирования решения задачи (повторное) с предварительно зафиксированным потоком обращений к страницам.
При выборе подходящего алгоритма замещения следует учитывать не только его эффективность к, но и аппаратные затраты и затраты времени на его реализацию.
Например, для реализации т. н. НДИ-алгоритма (наиболее давно используемая) каждой странице, находящейся в ОЗУ, ставится в соответствие таймер, который сбрасывается при обращении к странице. При страничном сбое необходимо осуществить поиск максимального элемента массива таймеров страниц. Для некоторых задач выигрыш времени за счет увеличения к при применении НДИ-алгоритма, по сравнению с алгоритмом случайного замещения, может быть сравним с потерей времени на поиск максимальных значений таймеров.
Некоторые алгоритмы замещения учитывают одновременно несколько параметров прошлого потока обращений.
Алгоритм "Карабкающаяся страница" (КС-алгоритм) поддерживает последовательность номеров страниц, находящихся в ОЗУ. При любом обращении к странице ее номер в последовательности перемещается на одну позицию в направлении начала, меняясь местами с предыдущим в последовательности номером (исключение — обращение к странице, номер которой стоит в начале последовательности). При возникновении страничного сбоя из ОЗУ удаляется страница, номер которой расположен в конце
последовательности, а номер вновь поступившей страницы помещается в конец последовательности. КС-алгоритм учитывает как время пребывания страницы в ОЗУ, так и интенсивность обращения к странице, причем не требует значительных аппаратных затрат, а при страничном сбое — времени на поиск.
Алгоритм "Рабочий комплект" (РК-алгоритм) более сложен в реализации, но позволяет адаптировать свои параметры под конкретный класс задач. Все страницы ОЗУ, к которым было обращение в течение отрезка времени Т, образуют т. н. рабочий комплект и не подлежат удалению из ОЗУ. Остальные страницы (не вошедшие в рабочий комплект) образуют две очереди кандидатов на замещение, причем в первую очередь попадают страницы, на которые не было записи во время пребывания их в ОЗУ. При страничном сбое удаляется страница из первой очереди (FIFO — первый пришел из рабочего комплекта — первый ушел из ОЗУ), а если первая очередь пуста, то — из второй. Из очереди страница может опять попасть в рабочий комплект, если к ней будет обращение. Для реализации РК-алгоритма каждой странице ставится в соответствие таймер на Т, причем каждое обращение к странице сбрасывает таймер (и переводит страницу в рабочий комплект, если она там отсутствовала), а переполнение таймера выводит страницу из рабочего комплекта. Подбором величины Т можно оптимизировать РК-алгоритм под конкретный класс задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
