Алгоритмы обновления содержимого заполненных строк, снуппинг

Каждая кэш-память имеет собственную служебную память, где хранятся биты, характеризующие содержимое ее строк: биты обращения, используемые для определения строки, содержимое которой будет обновляться, и биты состояния (бит модификации М, бит достоверности V и другие), с помощью которых обеспечивается когерентность содержимого строки в кэш-памяти и ОЗУ.

Если при чтении произошел кэш-промах, и кэширование данной области памяти разрешено, то производится обновление содержимого одной из строк набора, заданного полем SET адреса, в которую вводится информация из основной памяти. Новая информация замещает ранее имеющуюся в данной строке. В первую очередь замещается содержимое незаполненной («пустой») строки или недостоверной строки, содержание которой было аннулировано специальной командой. Такие строки имеют значение бита достоверности V=0. Если в данном наборе нет недостоверной ("пустой") строки, то производится удаление из кэш-памяти содержимого строки, которая дольше всего оставалась невостребованной.

Обычно используемый алгоритм обновления содержимого заполненных строк называется "замещение менее используемой информации" (LRU – Least Recently Used) и реализуется с помощью битов обращения. Рассмотрим реализацию этого алгоритма для кэш-памяти, наборы которой содержат по четыре строки. В этом случае в служебной памяти для каждого набора хранятся три бита обращения b0-b2 (биты LRU), значения которых определяют выбор строки, замещаемой в данном наборе при кэш-промахе.

Рис. 3.2. Установка битов LRU при обращении к строкам кэш-памяти

При инициализации процессора и очистке кэш-памяти биты LRU всех наборов кэш-памяти сбрасываются в 0. В ходе работы процессора значения битов b0-b2 устанавливаются в соответствии с тем, к каким из строк набора производились последние обращения (рис. 3.2). Если в данном наборе последнее обращение выполнялось к одной из пары строк L0 или L1, устанавливается b0=1, если к LЗ или L4, то устанавливается b0=0. Биты b1 и b2 указывают, к какой из строк пары L1-L2 и L3-L4 осуществлялось последнее обращение. Значение b1=0 устанавливается при обращении к L0, значение b1 = 1 - при обращении к L1. Соответственно, значение b2=0 или 1 устанавливается при обращении к строке L2 или L3. В соответствии с алгоритмом LRU для замены выбирается пара строк, к которым не производилось последнее обращение, а в этой паре замене подлежит строка, к которой не производилось последнее обращение. Выбранная таким образом строка считается дольше всего неиспользуемой в данном наборе, поэтому ее содержимое замещается строкой, выбираемой из ОЗУ при кэш-промахе.

Данное описание соответствует использованию наборов из четырех строк, что чаще всего реализуется в кэш-памяти микропроцессоров. Для кэш-памяти, содержащей две строки в наборе, требуется только один бит LRU для каждого набора, который принимает значение b0=0 при обращении к строке L0, и b0=1 при обращении к L1.

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

Если выполняется захват системной шины другим процессором (активным устройством) в мультипроцессорной системе, то отключаемый от шины процессор продолжает выполнение команд и обработку данных, содержащихся в кэш-памяти. Активный процессор может обратиться к данным, копии которых уже находятся в кэш-памяти процессора, отключенного от системной шины. Поэтому необходимо принять меры для обеспечения идентичности копий данных, используемых различными процессорами. Такие меры реализуются с помощью специальных средств, выполняющих снуппинг (snoop) - слежение за содержимым кэш-памяти разных процессоров, входящих в систему. При этом отключенный от системной шины процессор принимает адреса, выдаваемые на адресные линии активным процессором. Если этот адрес совпадает с адресом данных, хранящихся в одной из заполненных строк кэш-памяти данных отключенного процессора, то выполняются следующие процедуры. Если активный процессор производил запись по данному адресу, то содержимое соответствующей строки в отключенном от шине процессоре аннулируется (устанавливается значение бита V=0). Если активный процессор производил чтение по адресу модифицированной строки, имеющей значение бита модификации М=1, то отключенный процессор выполняет специальный цикл выдачи адресованных данных на внешнюю шину, чтобы активный процессор получил их модифицированный вариант.

Специальные команды управления процессором позволяют производить очистку кэш-памяти (аннулирование содержимого строк) путем установки значений бита достоверности V=0. При этом для обеспечения когерентности содержимое модифицированных строк переписывается в ОЗУ.

Организация памяти

Хранение информации в памяти микропроцессорных систем может быть организовано различными способами. Наиболее часто реализуются следующие варианты организации памяти:

· линейная,

· сегментная (блочная),

· страничная.

Использование того или иного способа организации памяти определяется функциями системы, объемом памяти и рядом других факторов. Многие микропроцессоры обеспечивают возможности реализации любого из этих способов.

Линейная организация. Это наиболее простой способ организации памяти, при котором формируемый процессором адрес непосредственно поступает на адресную шину, обеспечивая обращение к соответствующей ячейке памяти. В этом случае адрес, который формируется процессором в соответствии с заданным в команде способом адресации (линейный адрес), выдается на системную шину как физический адрес выбираемой ячейки памяти.

Сегментная организация. Данный способ обеспечивает разбиение памяти на отдельные сегменты (блоки), обращение к которым реализуется в соответствии с определенными правилами. В первую очередь реализуется разделение памяти на область (сегмент) команд и данных. Область данных может подразделяться на сегмент стека и несколько сегментов обрабатываемых данных. Размер сегментов может быть фиксированным (от 64 Кбайт до 4 Гбайт) или переменным (программируемым).

Рис. 3.3. Реализация доступа при сегментной адресации памяти

Реализация сегментной адресации обеспечивается с помощью специальных сегментных регистров, в которых хранится базовый (начальный) адрес, определяющий позицию первого байта данного сегмента. В этом случае формируемый при выполнении программы линейный адрес выбираемой команды или операнда является относительным адресом, который определяет их положение в сегменте, начальный адрес которого задается содержимым сегментного регистра (рис. 3.3). Физический адрес при сегментной организации памяти образуется путем арифметического суммирования базового адреса сегмента и относительного адреса операнда (команды).

В ряде микропроцессоров, например, в Pentium, обращение к сегментам выполняется согласно определенным правилам, которые обеспечивают защиту сегментов в соответствии с заданной системой привилегий (защищенный режим). В этом случае кроме сегментных регистров для организации обращения к сегментам используются специальные структуры данных - дескрипторы, которые задают базовый адрес и размер сегмента, а также указывают его атрибуты, определяющие возможность доступа к содержимому сегмента.

Страничная организация.Этот способ организации памяти предполагает разбиение адресуемых массивов данных или команд на относительно мелкие фрагменты - страницы.Типичный объем страницы составляет 4 Кбайт, хотя в ряде микропроцессоров обеспечивается возможность работы со страницами разного размера - от 256 байт до 4 Мбайт. Страницы могут размещаться в различных местах адресуемого пространства памяти, а их расположение определяется специальными таблицами адресов, которые обычно хранятся в ОЗУ. Страничная организация позволяет наиболее полно использовать имеющийся объем памяти, гак как обеспечивает разбиение информации и ее размещение в любом свободном фрагменте памяти размером не менее одной страницы.

При страничной организации реализуется иерархический уровень разбиения информации, аналогичный принятому в печатных изданиях, когда материал разбивается на отдельные части - главы, разделы и подразделы, состоящие из страниц. Такое разбиение отражается в оглавлении печатного издания. В микропроцессорных системах со страничной организацией памяти, функции оглавления выполняют специальные таблицы адресов, которые хранятся в ОЗУ. Обычно реализуется двухступенчатое разбиение типа «раздел-страница», при котором для обращения к соответствующей странице необходимо предварительно определить адрес ее размещения с помощью соответствующих таблиц адресов (рис. 3.4).

Рис. 3.4. Реализация доступа при страничной организации памяти

При страничной организации памяти формируемый процессором линейный адрес используется для получения физического адреса, который образуется путем

трансляции (преобразования) с помощью обращения к соответствующим таблицам адресов. На рис. 3.4 иллюстрируется процесс страничной трансляции 32-разрядного линейного адреса, выполняемый в процессорах Pentium. При этом линейный адрес обеспечивает выбор одного из 1024 разделов, каждый из которых может содержать 1024 страницы емкостью 4 Кбайт. Каталог разделов и таблицы адресов страниц хранятся в ОЗУ системы. Поле "Раздел" линейного адреса задает номер выбираемого раздела в каталоге, базовый адрес которого обычно хранится в специальном регистре страничной адресации. При этом из каталога разделов выбирается базовый адрес одной из 1024 таблиц, в которых хранятся базовые адреса страниц, входящих в соответствующий раздел. Поле "Страница" указывает в этой таблице базовый адрес страницы раздела, к которой производится обращение. Поле «Смещение» определяет позицию выбираемого операнда или команды на данной странице. Таким образом, их физический адрес формируется после процесса трансляции путем суммирования базового адреса страницы, полученного из соответствующей таблицы, и смещения, задаваемого 12 младшими разрядами линейного адреса.

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

Рассмотренная реализация страничной организации требует дополнительной памяти для хранения каталога разделов (до 4 Кбайт) и до 1024 таблиц страниц по 4 Кбайт каждая. Кроме того, трансляция адреса требует двух дополнительных циклов обращения к памяти для получения базовых адресов раздела и страницы. Чтобы избежать потерь времени на выборку этих адресов в микропроцессорах обычно имеется специальная память - буфер страничной трансляции,где хранятся базовые адреса страниц, к которым производились последние обращения. При последующих обращениях к этим страницам их базовый адрес выбирается непосредственно из буфера, и не требуется затрат времени на трансляцию адреса. Обычно емкость буфера составляет несколько десятков или сотен базовых адресов. При этом трансляция адреса с обращением к таблицам страниц производится достаточно редко - только в том случае, если базовый адрес страницы отсутствует в буфере, т.е. к данной странице ранее не было обращений, или эти обращения происходили достаточно давно, и ее базовый адрес был замещен адресами других страниц. Таким образом, буфер

страничной трансляции обеспечивает страничную адресацию без существенной потери производительности системы.

Внешние ЗУ

В качестве внешних ЗУ в микропроцессорных системах обычно используются накопители на жестких и гибких магнитных дисках, магнитных лентах и постоянная память на оптических компакт-дисках (CD-ROM). Эти устройства подключаются к системной шине микропроцессорной системы как внешние устройства, и сохраняют информацию при отключении питания. В последнее время все большее распространение получает постоянная память на оптических DVD – дисках.

Организация хранения информации во внешних ЗУ существенно отличается от организации хранения в регистровых ЗУ и ОЗУ. Вследствие физических особенностей реализации магнитных и оптических ЗУ для них характерно использование последовательного доступа к хранящейся информации с помощью механического перемещения носителя - диска или ленты. Управление работой этих ЗУ осуществляется с помощью специализированных устройств - контроллеров, которые подключаются к системной шине и функционируют под управлением программного обеспечения процессора.

Основным типом внешних ЗУ для современных микропроцессорных систем являются накопители на жестких магнитных дисках ("винчестер"), которые имеют емкость до нескольких сотен и тысяч Гбайт. Они служат для постоянного хранения используемой информации - операционной системы, пакетов прикладных программ, массивов данных, разнообразных служебных программ. Время обращения к другим ЗУ составляет несколько миллисекунд, скорость записи-чтения - десятки Мбайт/с. Контроллеры этих накопителей используют специальные протоколы обмена – IDE (применяется в большинстве персональных компьютеров) или SCSI (применяется в серверах, рабочих станциях и других высокопроизводительных системах).

Для временного хранения и переноса информации с одной системы на другую служат дискеты емкостью 1,44 Мбайт (диаметр 3,5 дюйма), которые вставляются в дисковод, работающих под управлением контроллера. Накопители на магнитных лентах - стримеры производят запись информации на кассеты емкостью до нескольких десятков Гбайт и обычно служат для создания резервных копий.

Для переноса и хранения больших объемов информации используются оптические компакт- и DVD - диски, емкость которых составляет сотни и тысячи Мбайт (емкость стандартного DVD – диска равна 4,7 Гбайт). При работе в системе производится не только считывание содержимого оптического диска, но и запись на него (однократная или многократная). В последнее время все большее распространение для тех же целей переноса и хранения больших объемов информации (до нескольких Гбайт) применяются флэш- карты памяти, которые подключаются к USB разъему компьютера с помощью карт – ридера или напрямую, а также переносные флэш – диски емкость в несколько сотен Гбайт.

Обращение к внешним ЗУ требует значительных затрат времени. Обычно микропроцессорная система реализует обмен с ними в режиме прямого доступа, осуществляя загрузку в ОЗУ или пересылку из него значительных объемов информации - фрагментов программ или массивов данных. Основной процесс обработки информации выполняется с использованием ОЗУ, кэш-памяти и регистрового ЗУ,что позволяет обеспечить высокий уровень производительности систем.

Контрольные вопросы и задания

1. Какие виды запоминающих устройств (ЗУ) используются в микропроцессорных системах?

2. Сколько времени занимает обращение к оперативному ЗУ?

3. Какие из запоминающих устройств являются самыми быстродействующими?

4. Назовите разновидности постоянных запоминающих устройств.

5. Как происходит обращение к кэш-памяти?

6. Что понимают под когерентностью в микропроцессорных системах?

7. Охарактеризуйте механизмы обеспечения когерентности.

8. Как происходит обновление содержимого строк кэш-памяти?

9. Что такое снуппинг?

10. Объясните назначение служебных битов кэш-памяти.

11. Охарактеризуйте различные способы организации памяти.

12. Как формируется физический адрес памяти при сегментной организции?

13. Как происходит выбор байта при страничной организации памяти?

14. Чему равен типичный размер страницы?

15. Для каких целей используются различные типы внешних запоминающих устройств?