кэширование

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

Виртуальная память. Кэширование памяти
Принципы кэширования.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Виртуальный адрес

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

Совокупность виртуальных адресов процесса называется виртуальным адресным пространством.

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

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

При каждом обращении к оперативной памяти аппаратными средствами выполняются следующие действия:

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

Использование в пункте (3) того факта, что размер страницы равен степени 2, позволяет применить операцию конкатенации (присоединения) вместо более длительной операции сложения, что уменьшает время получения физического адреса, а значит повышает производительность компьютера.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Сегментное распределение

Странично-сегментное
распределение

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

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Свопинг и виртуальная память

Так как памяти, как правило, не хватает. Для выполнения процессов часто приходится использовать диск.

Основные способы использования диска:
Свопинг (подкачка) - процесс целиком загружается в память для работы
Виртуальная память - процесс может быть частично загружен в память для работы

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

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

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

Программа при этом общается с виртуальной памятью, а не с физической.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Страницы – основа виртуальной памяти

Страницы - это части, на которые разбивается пространство виртуальных адресов.

Страничные блоки - единицы физической памяти.

Страницы всегда имеют фиксированный размер. Передача данных между ОЗУ и диском всегда происходит в страницах.

Х - обозначает не отображаемую страницу в физической памяти.

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

Таблица страниц - используется для хранения соответствия адресов виртуальной страницы и страничного блока.

Таблица может быть размещена:
в аппаратных регистрах (преимущество: более высокое быстродействие)
в ОЗУ

Типичная запись в таблице страниц

Присутствие/отсутствие - загружена или незагружена в память
Защита - виды доступа, например, чтение/запись.
Изменение - изменилась ли страница, если да то при выгрузке записывается на диск, если нет, просто уничтожается.

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Хранение страничной памяти на диске: Статическая и динамическая области свопинга

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

На диске всегда есть дубликат страницы, которая находится в памяти.

Статическая область свопинга

Динамическая область свопинга

Предполагается не выделять страницам место на диске, а выделять только при выгрузке страницы, и как только страница вернется в память освобождать место на диске.

Этот механизм сложнее, так как процессы не привязаны к какому-то пространству на диске, и нужно хранить информацию (карту диска) о местоположении на диске каждой страницы.

Статический и динамический методы организации свопинга.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: История

Впервые слово «кэш» в компьютерном контексте было использовано в 1967 году во время подготовки статьи для публикации в журнале «IBM Systems Journal». Статья касалась усовершенствования памяти в разрабатываемой модели 85 из серии IBM System/360. Редактор журнала Лайл Джонсон попросил придумать более описательный термин, нежели «высокоскоростной буфер», но из-за отсутствия идей сам предложил слово «кэш». Статья была опубликована в начале 1968 года, авторы были премированы IBM, их работа получила распространение и впоследствии была улучшена, а слово «кэш» вскоре стало использоваться в компьютерной литературе как общепринятый термин.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: История

Кэш-память — это высокоскоростная память произвольного доступа, используемая процессором компьютера для временного хранения информации. Она увеличивает производительность, поскольку хранит наиболее часто используемые данные и команды «ближе» к процессору, откуда их можно быстрее получить

definition

Кэш-память — это высокоскоростная память произвольного доступа, используемая процессором компьютера для временного хранения информации.

Гэри Антес – главный редактор journal of Computer World

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Идеология

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Принципы кэширования

Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных из основной памяти.
Каждая запись об элементе данных включает в себя:

значение элемента данных

адрес, который этот элемент
данных имеет в основной памяти

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

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

!

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Принципы кэширования

Возможен один из двух вариантов развития событий:
если данные обнаруживаются в кэш-памяти, то есть произошло кэш-попадание (cache-hit), они считываются из нее и результат передается источнику запроса;
если нужные данные отсутствуют в кэш-памяти, то есть произошел кэш-промах (cache-miss), они считываются из основной памяти, передаются источнику запроса и одновременно с этим копируются в кэш-память.

Интуитивно понятно, что эффективность кэширования
зависит от вероятности попадания в кэш.

Пусть имеется основное запоминающее устройство со средним временем доступа к данным tl и кэш-память, имеющая время доступа t2, очевидно, что t2 Пусть t — среднее время доступа к данным в системе с кэш-памятью, ар — вероятность кэш-попадания.
По формуле полной вероятности имеем:

t - t1(d - р) + t2p - (t2 -t1)p + t1

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Принципы кэширования

t - t1(d - р) + t2p - (t2 -t1)p + t1

Важно отменить, среднее время доступа к данным в системе с кэш-памятью линейно зависит от вероятности попадания в кэш и изменяется от среднего времени доступа в основное запоминающее устройство t1 при р=0 до среднего времени доступа непосредственно в кэш-память t2 при р=1.
видно, что использование кэш-памяти имеет смысл только при высокой вероятности кэш-попадания.

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

Тем не менее в большинстве реализаций кэш-памяти процент кэш-попаданий оказывается весьма высоким — свыше 90 %.

Такое высокое значение вероятности нахождения данных в кэш-памяти объясняется наличием у данных объективных свойств: пространственной и временной локальности.

!

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Принципы кэширования

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Принципы кэширования. Проблема согласования данных

Поведение кэш-контроллера при операции записи в память, когда копия затребованной области находится в некоторой строке кэша, определяется его алгоритмом – политикой записи в кэш.

Существуют 2 основные политики записи данных
из кэша в основную память

Сквозная запись
(write through)
При каждом запросе к основной памяти,
в том числе и при записи, просматривается кэш.
Если данные по запрашиваемому адресу отсутствуют,
то запись выполняется только в основную память.
Если же данные, к которым выполняется обращение,
находятся в кэше, то запись выполняется
одновременно в кэш и основную память.

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Проблема согласования данных

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

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

Два подхода к решению этой проблемы

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Принципы кэширования.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

http://www.ixbt.com/cpu/intel-ci7-theory.shtml
http://citforum.ru/programming/digest/gaisarian/
http://docstore.mik.ua/svk/glava_9.htm
http://www.ixbt.com/news/all/index.shtml?06/21/44
http://alasir.com/articles/cache_principles/cache_associativity_rus.html
http://education.aspu.ru/view.php?olif=gl5
http://www.x-drivers.ru/articles/technologies/20/full.html
http://www.intuit.ru/department/hardware/microarch/4/3.html
http://www.intuit.ru/department/hardware/microarch/4/2.html
http://www.yudenisov.narod.ru/EIS/Vol07/b4.htm
http://iproc.ru/parallel-programming/lection-7/
http://www.3dnews.ru/cpu/pentium4-vs-g4e/index5.htm
http://www.intuit.ru/department/hardware/mcoreproc/5/
http://www.kit-e.ru/articles/dsp/2008_3_32.php
http://www.intuit.ru/department/os/modernos/6/4.html
http://www.osp.ru/cw/2000/15/4418/
Анимация работы наборно-ассоциативного кэша:
http://www.scss.tcd.ie/~jones/vivio/caches/cache.htm

Используемые Интернет-ресурсы:

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

Книга «Ассемблер. Учебник для ВУЗов», авторы Михаил Гук, Виктор Юров
Книга «Архитектура ЭВМ»,автор Мюллер
Книга «Процессоры Pentium4, Athlon и Duron», авторы Михаил Гук, Виктор Юров
Книга «Архитектура ЭВМ», автор Танненбаум

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память:

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память:

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память:

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память:

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Используемые Интернет-ресурсы:

http://citforum.ru/operating_systems/sos/glava_7.shtml
http://x86.migera.ru/text/glava_2.html
http://www.intuit.ru/department/os/osintro/10/
http://www.moodle.ipm.kstu.ru/mod/resource/view.php?id=57