Какие сегменты имеет память

Сегментация памяти

Производительность микроЭВМ и микропроцессорной системы в целом во многом определяется емкостью ОЗУ. При этом МП должен иметь возможность адресации всего объема ОЗУ, т.е. вычисления адресов ячеек памяти и передачи их по ША в ОЗУ. Так, например, для адресации ОЗУ емкостью 1 Мбайт (2 20 байт) требуется вычисление 20-разрядных двоичных чисел — адресов ячеек ОЗУ и передача их в ОЗУ по шине адреса.

В то же время архитектура МП и разрядность его регистров определяется длиной обрабатываемых слов и обычно она составляет число, кратное восьми — 1 байту. Так, МГ1 Intel 8086, так же как и многие другие, обеспечивает обработку 16-разрядных слов и все его регистры, в том числе и адресные, 16-разрядные. Для расширения адресного пространства МП применяют механизм сегментации памяти. МП рассматривает весь объем памяти как набор сегментов памяти (рис. 4.14).

Сегмент — это часть памяти такого объема, адресация которого возможна с помощью одного регистра МП. Таким образом, разрядность регистров МП определяет размер сегментов памяти. Так, например, для 16-раз- рядных МП это 64 Кбайт, т.е. 2 16 байт. Выделение сегмента осуществляется определением его начального адреса, или базы сегмента. В МП Intel 8086 для выделения сегментов имеется четыре специальных сегментных регистра — CS, DS, SS, ES. Регистр CS содержит начальный адрес сегмента программы, DS — сегмента данных, SS — сегмента стека, a ES — дополнительного сегмента. Эти регистры, так же как и все остальные регистры МП, 16-разрядные, и в них нельзя записать все разряды начального адреса. Поэтому в них загружаются 16 старших разрядов начального адреса сегмента. Оставшиеся младшие разряды адреса считаются равными нулю. МП Intel 8086 имеет адресное пространство, равное 1 Мбайту, и равными нулю считаются четыре младших разряда адреса сегмента. Всего МП Intel 8086 одновременно работает с четырьмя сегментами, которые могут быть как смежными, так и перекрывающимися. В последнем случае одни и те же ячейки памяти могут быть адресованы как в одном, так и в другом сегментах (см. рис. 4.14). Местоположение ячейки памяти внутри сегмента определяется 16-разрядным внутрисегментным адресом. Полный физический адрес ячейки памяти образуется сложением адреса сегмента с внутрисегментным адресом, которое выполняет сумматор шинного интерфейса. Если это адрес команды, то складываются содержимые сегментного регистра программы и программного счетчика, если это адрес операнда, то внутрисегментный адрес поступает из операционного устройства и складывается с содержимым сегментного регистра данных. Младшие 16 разрядов вычисленного адреса поступают на внешнюю шину адреса/данных. Для передачи четырех старших разрядов используются еще четыре линии, которые также работают в мультиплексном режиме.

Сегментная адресация памяти в 32-х разрядных системах

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

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

Селектор сегмента

Первое из двух чисел в логическом адресе называется селектором, он 16-ти разрядный, среди которых старшие 13 бит являются индексом(порядковым номером) сегмента в таблице дескрипторов. Остальные три бита делятся следующим образом: 1 бит называется TI и указывает на тип дескрипторной таблицы(0 — глобальная, 1 — локальная), еще два бита отданы под RPL — запрашиваемый уровень привилегий.

При обращении к нужному дескриптору RPL будет сравниваться с DPL этого сегмента. Как вы уже могли догадаться, DPL(Descriptor privilege level) это уровень привилегий дескриптора.

Кстати, о доступе. Благодаря делению памяти на сегменты появилась возможность разграничивать права доступа и пресекать подлые попытки переписать чужую память, это стало настоящим прорывом. Всего существует 4 уровня привилегий: 0-2 соответствуют супервизору, при этом на нулевом уровне доступны самые привилегированные действия, 3 — уровень пользователя(пользовательских программ).

Таблицы дескрипторов

Глобальная таблица дескрипторов — GDT

Чуть более подробно об этой таблице. Все сегменты хранятся в определенной структуре, называемой GDT — Global Descriptor Table. Из названия видно, что она представляет из себя простую таблицу. Хранится в оперативной памяти всегда, подгружается при запуске операционной системы, на ее начало указывает специальный регистр GDTR. Кстати, это один из немногих регистров процессора, который хранит в себе физический адрес. И он же хранит размер таблицы, таким образом мы и операционная система всегда можем иметь доступ к нашим сегментам.

Из размерности поля индекса в селекторе можно посчитать максимальное возможное количество дескрипторов в таблице — 213 = 8192 дескриптора.

Размер дескриптора равен 8 байтам или 32 битам. Вот как выглядит такая запись, называемая дескриптором.

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

Локальная таблица дескрипторов — LDT

Кроме GDT еще существует LDT — Local Descriptor Table — которая отвечает за сегменты каждого отдельного процесса. Ссылки на все LDT содержатся в GDT, но в любой локальной таблице не может быть ссылок на другую локальную. А во всем остальном локальные таблицы не отличаются от глобальной.

Трансляция адресов в сегментной модели памяти

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

• Первым делом сравниваются RPL селектора и DPL сегмента, если запрашиваемый уровень привилегий меньше или равен уровню доступа сегмента, то доступ разрешен.
• Теперь мы должны взять базовый адрес сегмента и прибавить к нему смещение из логического адреса.
• Проверить, что полученный физический адрес не выходит за границы сегмента. Для этого существует поле limit в дескрипторе.
• Если все условия соблюдены, мы получаем доступ к ячейке памяти по физическому адресу(база сегмента + смещение).

Заключение

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

Организация и модели памяти, адресация

Память – способность объекта обеспечивать хранение данных.
Все объекты, над которыми выполняются команды, как и сами команды, хранятся в памяти компьютера.

Память состоит из ячеек, в каждой из которых содержится 1 бит информации, принимающий одно из двух значений: 0 или 1. Биты обрабатывают группами фиксированного размера. Для этого группы бит могут записываться и считываться за одну базовую операцию. Группа из 8 бит называется .

Байты последовательно располагаются в памяти компьютера.

• 1 килобайт (Кбайт) = 2 10 = 1 024 байт
• 1 мегабайт (Мбайт) = 2 10 Кбайт = 2 20 байт = 1 048 576 байт
• 1 гигабайт (Гбайт) = 2 10 Мбайт = 2 30 байт = 1 073 741 824 байт

Для доступа к памяти с целью записи или чтения отдельных элементов информации используются идентификаторы , определяющие их расположение в памяти. Каждому идентификатору в соответствие ставится адрес . В качестве адресов используются числа из диапазона от 0 до 2 k -1 со значением k, достаточным для адресации всей памяти компьютера.Все 2 k адресов составляют адресное пространство компьютера .

Способы адресации байтов

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

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

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

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

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

• сегментированную модель
• страничную модель
• плоскую модель

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

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

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

• Сегмент кодов ( .CODE ) – содержит машинные команды для выполнения. Обычно первая выполняемая команда находится в начале этого сегмента, и операционная система передает управление по адресу данного сегмента для выполнения программы. Регистр сегмента кодов ( CS ) адресует данный сегмент.
• Сегмент данных ( .DATA ) – содержит определенные данные, константы и рабочие области, необходимые программе. Регистр сегмента данных ( DS ) адресует данный сегмент.
• Сегмент стека ( .STACK ). Стек содержит адреса возврата как для программы (для возврата в операционную систему), так и для вызовов подпрограмм (для возврата в главную программу). Регистр сегмента стека ( SS ) адресует данный сегмент. Адрес текущей вершины стека задается регистрами SS:ESP .

Регистры дополнительных сегментов ( ES, FS, GS ), предназначены для специального использования.

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

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

сегмент : смещение

Страничная модель памяти – это надстройка над сегментной моделью. ОЗУ делится на блоки фиксированного размера, кратные степени 2, например 4 Кб. Каждый такой блок называется страницей . Основное достоинство страничного способа распределения памяти — минимально возможная фрагментация. Однако такая организация памяти не использует память достаточно эффективно за счет фиксированного размера страниц.

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

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

В абсолютном большинстве современных 32(64)-разрядных операционных систем (для микропроцессоров Intel) используется плоская модель памяти.

Модели памяти

Директива .MODEL определяет модель памяти, используемую программой. После этой директивы в программе находятся директивы объявления сегментов ( .DATA, .STACK, .CODE, SEGMENT ). Синтаксис задания модели памяти

.MODEL модификатор МодельПамяти СоглашениеОВызовах

Параметр МодельПамяти является обязательным.

Основные модели памяти:

Модель tiny работает только в 16-разрядных приложениях MS-DOS. В этой модели все данные и код располагаются в одном физическом сегменте. Размер программного файла в этом случае не превышает 64 Кбайт.
Модель small поддерживает один сегмент кода и один сегмент данных. Данные и код при использовании этой модели адресуются как near (ближние).
Модель medium поддерживает несколько сегментов программного кода и один сегмент данных, при этом все ссылки в сегментах программного кода по умолчанию считаются дальними (far), а ссылки в сегменте данных — ближними (near).
Модель compact поддерживает несколько сегментов данных, в которых используется дальняя адресация данных (far), и один сегмент кода с ближней адресацией (near).
Модель large поддерживает несколько сегментов кода и несколько сегментов данных. По умолчанию все ссылки на код и данные считаются дальними (far).
Модель huge практически эквивалентна модели памяти large.

Особого внимания заслуживает модель памяти flat , которая используется только в 32-разрядных операционных системах. В ней данные и код размещены в одном 32-разрядном сегменте. Для использования в программе модели flat перед директивой .model flat следует разместить одну из директив:

• .386
• .486
• .586
• .686

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

Параметр модификатор используется для определения типов сегментов и может принимать значения use16 (сегменты выбранной модели используются как 16-битные) или use32 (сегменты выбранной модели используются как 32-битные).

Параметр СоглашениеОВызовах используется для определения способа передачи параметров при вызове процедуры из других языков, в том числе и языков высокого уровня (C++, Pascal). Параметр может принимать следующие значения:

• C,
• BASIC,
• FORTRAN,
• PASCAL,
• SYSCALL,
• STDCALL.

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

Name already in use

kpi-spos / lec / 4-mem / 4-mem-ru.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

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

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

Режимы работы процессора x86:

• реальный — прямой доступ к памяти по физическому адресу
• защищенный — использование виртуальной памяти и колец процессора для разграничения доступа к ней

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

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

Виды адресов памяти:

• физический — адрес аппаратной ячейки памяти
• логический — виртуальный адрес, которым оперирует приложение

За счет наличия механизма виртуальной памяти компиляторы прикладных програм могут генерировать исполняемый код в рамках упрощенной абстрактной линейной модели памяти, в которой вся доступная память представляется в виде непрерывного массива машинных слов, адресуемого с 0 до максимально возможного адреса для данной разрядности ( 2^N , где N — количество бит, т.е. для 32-разрядной архитектуры максимальный адрес — 2^32 = #FFFFFFFF ). Это значит что результирующие программы не привязаны к конкретным параметрам запоминающих устройств, таких как их объем, режим адресации и т.д.

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

На аппаратном уровне виртуальная память, как правило, поддерживается специальным устройством — Модулем управления памятью.

Страничная организация памяти

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

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

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

Размер страницы и количество страниц зависит от того, какая часть адреса выделяется на номер страницы, а какая на смещение. К примеру, если в 32-разрядной системе разбить адрес на две равные половины, то количество страниц будет составлять 2^16, т.е. 65536, и размер страницы в байтах будет таким же, т.е. 64 КБ. Если уменьшить количество страниц до 2^12, то в системе будет 4096 страницы по 1МБ, а если увеличить до 2^20, то 1 миллион страниц по 4КБ. Чем больше в системе страниц, тем больше занимает в памяти таблица страниц, соответственно работа процессора с ней замедляется. А поскольку каждое обращение к памяти требует обращения к таблице страниц для трансляции виртуального адреса, такое замедление очень нежелательно. С другой стороны, чем меньше страниц и, соотвественно, чем они больше по объему — тем больше потери памяти, вызванные внутренней фрагментацией страниц, поскольку страница является единицей выделения памяти. В этом заключается диллема оптимизации страничной памяти. Она особенно актуальна при переходе к 64-разрядным архитектурам.

Для оптимизации страничной памяти используются следующие подходы:

• специальный кеш — TLB (translation lookaside buffer) — в котором хранится очень небольшое число (порядка 64) наиболее часто используемых адресов страниц (основные страницы, к которым постоянно обращается ОС)
• многоуровневая (2, 3 уровня) таблица страниц — в этом случае виртуальный адрес разбивается не на 2, а на 3 (4. ) части. Последняя часть остается смещением внутри страницы, а каждая из остальных задает номер страницы в таблице страниц 1-го, 2-го и т.д. уровней. В этой схеме для трансляции адресов нужно выполнить не 1 обращение к таблице страниц, а 2 и более. С другой стороны, это позволяет свопить таблицы страниц 2-го и т.д. уровней, и подгружать в память только те таблицы, которые нужны текущему процессу в текущий момент времени или же даже кешировать их. А каждая из таблиц отдельного уровня имеет существенно меньший размер, чем имела бы одна таблица, если бы уровень был один

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

Сегментная организация памяти

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

Историческая модель сегментации в архитектуре х86

В архитектуре х86 сегментная модель памяти была впервые реализована на 16-разрядных процессорах 8086. Используя только 16 разрядов для адреса давало возможность адресовать только 2^16 байт, т.е. 64КБ памяти. В то же время стандартный размер физической памяти для этих процессоров был 1МБ. Для того, чтобы иметь возможность работать со всем доступным объемом памяти и была использована сегментная модель. В ней у процессора было выделено 4 специализированных регистра CS (сегмент кода), SS (сегмент стека), DS (сегмент данных), ES (расширенный сегмент) для хранения базы текущего сегмента (для кода, стека и данных программы).

Физический адрес в такой системе расчитывался по формуле:

Это приводило к возможности адресовать большие адреса, чем 1МБ — т.н. Gate A20.

Плоская модель сегментации

32-разрядный процессор 80386 мог адресовать 2^32 байт памяти, т.е. 4ГБ, что более чем перекрывало доступные на тот момент размеры физической памяти, поэтому изначальная причина для использования сегментной организации памяти отпала.

Однако, помимо особого способа адресации сегментная модель также предоставляет механизм защиты памяти через кольца безопасности процессора: для каждого сегмента в таблице сегментов задается значение допустимого уровня привилегий (DPL), а при обращении к сегменту передается уровень привилегий текущей программы (запрошенный уровень привилегий, RPL) и, если RPL > DPL доступ к памяти запрещен. Таким образом обеспечивается защита сегментов памяти ядра ОС, которые имеют DPL = 0 . Также в таблице сегментов задаються другие атрибуты сегментов, такие как возможность записи в память, возможность исполнения кода из нее и т.д.

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

В современных процессорах x86 используется «Плоская модель сегментации», в которой база всех сегментов выставлена в нулевой адрес.

Виртуальная память в архитектуре x86

Системные вызовы для взаимодействия с подсистемой виртуальной памяти:

• brk , sbrk — для увеличения сегмента памяти, выделенного для данных программы
• mmap , mremap , munmap — для отображения файла или устройства в память
• mprotect — изменение прав доступа к областям памяти процесса

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

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

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

Способы учета свободных участков:

• битовая карта (bitmap) — каждому блоку памяти (например, странице) ставится в соответствие 1 бит, который имеет значение занят/свободен
• связный список — каждому непрерывному набору блоков памяти одного типа (занят/свободен) ставится в соответствеи 1 запись в связном списке блоков, в которой указывается начало и размер участка
• использование нескольких связных списков для участков разных размеров — см. алгоритм Buddy allocation

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

По принципу записи данных в кеш выделяют:

• сквозной (write-through) — данные записываются синхронно и в кеш, и непосредственно в запоминающее устрйоство
• с обратной записью (write-back, write-behind) — данные записываются в кещ и иногда синхронизируются с запоминающим устройством

По принципу хранения данных выделяют:

• полностью ассоциативные
• множественно-ассоциативные
• прямого соответствия

Алгоритмы замещения записей в кеше

Поскольку любой кеш всегда меньше запоминающего устройства, всегда возникает необходимость для записи новых данных в кеш удалять из него ранее записанные. Эффективное удаление данных из кеша подразумевает удаление наименее востребованных данных. В общем случае нельзя сказать, какие данные являются наименее востребованными, поэтому для этого используются эвристики. Например, можно удалять данные, к которым происходило наименьшее число обращений с момента их загрузки в кеш (least frequently used, LFU) или же данные, к которым обращались наименее недавно (least recently used, LRU), или же комбинация этих двух подходов (LRFU).

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

Более сложным вариантом является использование аппаратного счетчика для каждой ячейки. Если этот счетчик фиксирует число обращений к ячейке, то это простой вариант алгоритма LFU. Он обладает следующими недостатками:

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

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