Дело в виртуальной памяти

Обзор

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

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

Люди, которые этого не понимают, будут думать, что виртуальная память — это всего лишь метод «использования места на жестком диске для расширения памяти», что неверно.Значение виртуальной памяти заключается в том, что она определяет непрерывное виртуальное адресное пространство., что снижает сложность программирования. и,Расширение памяти до места на жестком диске является лишь неизбежным результатом использования виртуальной памяти.Пространство виртуальной памяти будет существовать на жестком диске и будет кэшироваться памятью (по запросу).Вся память помещается в пространство жесткого диска и считывается из него. жесткий диск при переключении на процесс(Вот почему Windows так часто симулирует смерть...).

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

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

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

Автор этой статьиSylvanasSun(sylvanas.sun@gmail.com), впервые опубликовано вБлог SylvanasSun.
Оригинальная ссылка:sylva, то есть sun.GitHub.IO/2017/10/29/…
(Для перепечатки просьба сохранить заявление в этом абзаце и сохранить гиперссылку.)

Адресация ЦП

Память обычно организована как массив из M смежных блоков размером в байт, каждый байт имеет уникальный физический адрес (Physical Address PA) в качестве индекса в массиве. Самый простой и прямой способ доступа ЦП к памяти — это использование физических адресов.Этот метод адресации называется физической адресацией.

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

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

таблица страниц

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

Операционная система делит виртуальную память на блоки фиксированного размера в качестве единицы передачи между жестким диском и памятью.Этот блок называется виртуальной страницей (Virtual Page, VP).Размер каждой виртуальной страницы равенP=2^pбайт. Физическая память также делится на физические страницы (PP) таким образом, и размер такжеPбайт.

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

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

виртуальная страницаVP 0,VP 4,VP 6,VP 7кэшируются в физической памяти, виртуальные страницыVP 2иVP 5размещаются в таблице страниц, но не кэшируются в физической памяти, виртуальные страницыVP 1иVP 3не был назначен.

При динамическом распределении памяти, например.malloc()функции или другие языки высокого уровняnewключевое слово, операционная система создаст или применит виртуальное пространство памяти на жестком диске и обновит его до таблицы страниц (выделите PTE, чтобы PTE указывал на вновь созданную виртуальную страницу на жестком диске).

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

попадание на страницу

Как показано на рисунке выше, MMU адресуется в таблице страниц в соответствии с виртуальным адресом.PTE 4, эффективный бит PTE равен 1, что означает, что виртуальная страница была кэширована в физической памяти, и, наконец, MMU получает адрес физической памяти в PTE (указывающий наPP 1).

Отсутствующие страницы

Как показано на рисунке выше, MMU адресуется в таблице страниц в соответствии с виртуальным адресом.PTE 2, действительный бит PTE равен 0, что означает, что виртуальная страница не кэшируется в физической памяти.Виртуальные страницы, не кэшированные в физической памяти (промахи кэша), называются ошибками страниц.

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

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

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

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

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

многоуровневая таблица страниц

До сих пор мы обсуждали только одну таблицу страниц, но в реальной среде адреса виртуального пространства очень велики (адресное пространство 32-битной системы имеет2^32 = 4GB, не говоря уже о 64-битной системе). В этом случае использование одностраничной таблицы явно неэффективно.

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

Виртуальное адресное пространство разделено на страницы по 4 КБ, и каждый PTE занимает 4 байта.
Первые 2К страницы памяти отводятся под код и данные.
Следующие 6K страниц не были выделены.
Следующие 1023 страницы не выделяются, а следующая 1 страница выделяется пользовательскому стеку.

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

Эта структура очень похожа наB-Tree, эта иерархия эффективно снижает требования к памяти:

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

Процесс трансляции адресов

Формально,Преобразование адресов — это сопоставление между элементом в N-элементном виртуальном адресном пространстве и элементом в M-элементном физическом адресном пространстве.

На следующем рисунке показан процесс адресации MMU с использованием таблицы страниц:

Базовый регистр таблицы страниц (PTBR) указывает на текущую таблицу страниц.N-битный виртуальный адрес состоит из двух частей: p-битного смещения виртуальной страницы (Virtual Page Offset, VPO) и (n-p)-битного номера виртуальной страницы (Virtual Page Number, VPN).

MMU выбирает соответствующий PTE в соответствии с VPN,НапримерVPN 0представлятьPTE 0,VPN 1представлятьPTE 1.... Поскольку размер физической страницы и виртуальной страницы одинаковы, смещение физической страницы (PPO) совпадает с VPO. затем послеПока номер физической страницы (PPN) в PTE объединяется с VPO в виртуальном адресе, можно получить соответствующий физический адрес..

То же самое верно и для преобразования адресов многоуровневых таблиц страниц, но поскольку существует несколько уровней, VPN необходимо разделить на несколько сегментов.Если предположить, что имеется таблица страниц k-го уровня, виртуальный адрес будет разделен на k VPN и 1 VPO, каждая из которыхVPN iиндекс в таблице страниц на уровне i. Чтобы построить физический адрес, MMU должен получить доступ к k PTE, чтобы получить соответствующий PPN.

TLB

Таблица страниц кэшируется в памяти.Хотя скорость памяти очень высока по сравнению с жестким диском, она все же отстает от процессора.Чтобы предотвратить необходимость доступа к памяти для каждой операции преобразования адресов, ЦП использует кэш и TLB для кэширования PTE.

В худшем случае (исключая страничные ошибки) MMU должен получить доступ к памяти, чтобы получить соответствующий PTE.Эта стоимость составляет от десятков до сотен циклов.Если PTE кэшируется в кэше L1 (если L1 не , она также будет получена из кеша L1). Однако многим системам необходимо устранить даже эти незначительные накладные расходы, и из этого рождаются TLB.

TLB (Translation Lookaside Buffer, TLB) называется резервным буфером перевода или буфером обхода перевода.Буфер в MMU, где каждая строка содержит блок одного PTE. Поля индекса и тега, используемые для выбора группы и сопоставления строк, извлекаются из VPN, если они присутствуют в TLB.T = 2^tgroup, то индекс TLB (TLBI) состоит из t младших битов VPN, а флаг TLB (TLBT) состоит из оставшихся битов VPN.

На следующем рисунке показан процесс трансляции адреса (в случае попадания в TLB):

На первом этапе ЦП передает виртуальный адрес MMU для преобразования адреса.
На втором и третьем этапах MMU получает соответствующий PTE через TLB.
На четвертом этапе MMU транслирует физический адрес через PTE и отправляет его в кэш/память.
На пятом шаге кеш возвращает данные в ЦП (если кеш попадает, иначе ему нужен доступ к памяти).

Когда TLB отсутствует, MMU должен извлечь соответствующий PTE из кэша/памяти и сохранить вновь извлеченный PTE в TLB (перезаписывая существующий PTE, если TLB заполнен).

Система виртуальной памяти в Linux

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

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

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

mm_struct: описывает текущее состояние виртуальной памяти. pgd указывает на базовый адрес таблицы страниц первого уровня (когда ядро запускает этот процесс, pgd будет храниться в управляющем регистре CR3, который является регистром базового адреса таблицы страниц), mmap указывает на связанный список vm_area_structs, где каждая vm_area_structs описывает регион текущего виртуального адресного пространства.
vm_starts: указывает на начало этой области.
vm_end: указывает на конец этой области.
vm_prot: описывает разрешения на чтение и запись для всех страниц, содержащихся в этой области.
vm_flags: Описывает, являются ли страницы в этой области общими с другими процессами или частными для этого процесса, а также некоторую другую информацию.
vm_next: указывает на следующую структуру области связанного списка.

карта памяти

Linux инициализирует содержимое области виртуальной памяти, связывая его с файлом на жестком диске. Этот процесс называется отображением памяти. Этот метод интеграции системы виртуальной памяти в файловую систему позволяет легко и эффективно загружать программы и данные в память.

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

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

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

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

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

общий объект

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

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

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

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

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

Другим типичным примером являетсяfork()функция, которая используется для создания дочернего процесса. когдаfork()Когда функция вызывается текущим процессом, ядро создает различные необходимые структуры данных для нового процесса и присваивает ему уникальный PID. Чтобы создать виртуальную память для нового процесса, он копирует текущий процесс.mm_struct,vm_area_structи точная копия таблицы страниц. И пометьте каждую страницу в обоих процессах как доступную только для чтения, и пометьте каждую область в обоих процессах как приватную (копирование при записи).

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

динамическое выделение памяти

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

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

В этой статье объясняются только некоторые концепции динамического выделения памяти, а реализация динамического распределителя памяти выходит за рамки этой статьи. Если вы заинтересованы в этом, вы можете обратиться к немуdlmallocИсходный код , это умно разработанный распределитель памяти, реализованный Дугом Леа (тот, кто написал параллельный пакет Java), и в исходном коде есть много комментариев.

фрагментация памяти

Основной причиной низкого использования места в куче является явление, называемое фрагментацией.Фрагментация возникает, когда есть неиспользуемая память, но память не может удовлетворить запрос на выделение.. Различают две формы фрагментации:

Внутренняя фрагментация: происходит, когда выделенный блок больше полезной нагрузки. Например, программа запрашивает блок из 5 слов (здесь размер слова не важен, предположим, что слово 4 байта, размер кучи 16 слов и требуется граничное выравнивание по двойным словам) , распределитель памяти, чтобы гарантировать, что свободный блок будет двойным. Если граница слова выровнена (правила выравнивания в конкретной реализации могут немного отличаться, но выравнивание определенно есть), должен быть выделен блок из 6 слов . В этом примере выделенный блок составляет 6 слов, полезная нагрузка — 5 слов, а внутренняя фрагментация — это выделенный блок за вычетом полезной нагрузки, которая составляет 1 слово.
Внешняя фрагментация: происходит, когда свободной памяти достаточно для удовлетворения запроса на выделение, но ни один свободный блок не является достаточно большим для обработки запроса. Внешняя фрагментация трудно поддается количественной оценке и непредсказуема, поэтому распределители обычно используют эвристические стратегии, пытаясь поддерживать небольшое количество больших свободных блоков, а не большое количество маленьких свободных блоков. Распределитель также разделяет свободные блоки и объединяет свободные блоки (должны быть смежными) в зависимости от того, как политика соответствует запросу на выделение.

бесплатный список

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

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

Обычно существуют следующие стратегии поиска свободного блока:

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

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

Простая стратегия раздельного хранения: распределитель поддерживает массив свободных списков, а затем делит все возможные блоки на классы эквивалентности (также называемые размерными классами), каждый размерный класс представляет свободный список, и каждый свободный связанный список размерного класса содержит блоки одинакового размера, а размер каждого блока равен размеру самого большого элемента в классе размера (например, если диапазон класса размера определен как (17~32), то свободный связанный список состоит из всех размеры 32 блока).

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

Чтобы освободить блок, распределитель просто вставляет блок в начало соответствующего списка свободных блоков.

вывоз мусора

При написании программ на C память в куче может быть выделена и освобождена только явно (malloc()иfree()), программист должен не только выделять память, но и нести ответственность за освобождение памяти.

Многие современные языки программирования имеют встроенные механизмы автоматического управления памятью (в C/C++ также можно добиться автоматического управления памятью за счет введения библиотек автоматического управления памятью),Так называемое автоматическое управление памятью заключается в том, чтобы автоматически определить память кучи (называемую памятью мусора), которая больше не нужна, а затем автоматически освободить память мусора.

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

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

Счетчик ссылок: Счетчик добавляется к физическому пространству данных.Когда есть другие данные, связанные с ним (ссылка), счетчик увеличивается на единицу, и наоборот. Периодически проверяя значение счетчика, пока он равен 0, он считается мусорной памятью, и выделенные блоки, которые он занимает, могут быть освобождены. Используя счетчик ссылок, реализация проста и понятна, но недостаток также очевиден, он не может повторно использовать два объекта, на которые ссылается цикл (при условии, что есть объект A и объект B, они ссылаются друг на друга, но на самом деле, как объект A, так и объект B уже не имеют значения (используемый объект).
Анализ достижимости: сборщик мусора обрабатывает память кучи как ориентированный граф, а затем выбирает набор корневых узлов (например, в Java обычно загрузчик классов, глобальные переменные, переменные ссылочного типа в пуле констант времени выполнения) и т. д.), корневой узел должен быть достаточно "живым" объектом. Затем вычислите достижимый путь из набора корневых узлов, если недостижимые узлы из корневого узла считаются мусорной памятью.

Существует несколько алгоритмов, используемых сборщиком мусора для сборки:

Отметка-развертка: Алгоритм разделен на два этапа: отметка и развертка. Сначала отметьте все объекты, которые необходимо переработать, а затем равномерно переработайте все отмеченные объекты после завершения маркировки. Алгоритм маркировки-развертки прост в реализации, но он неэффективен и вызывает сильную фрагментацию памяти.
Пометка для очистки: Алгоритмы пометки для очистки и пометки для очистки в основном одинаковы, за исключением того, что последующие шаги не очищают объекты, подлежащие переработке, а перемещают все уцелевшие объекты в один конец, а затем непосредственно очищают. память за гранью.
копировать:Разделите пространство памяти, принадлежащее программе, на два блока одинакового размера и используйте только один из них за раз. Когда этот участок памяти будет израсходован, скопируйте уцелевшие объекты в другой участок памяти, а затем очистите используемое пространство памяти.. Этот метод не должен учитывать проблему фрагментации памяти, но использование памяти очень низкое. Это соотношение не является абсолютным.Чтобы избежать потерь, виртуальная машина HotSpot делит память на пространство Eden и два пространства Survivor и каждый раз использует только Eden и одно пространство Survivor. При переработке скопируйте уцелевшие объекты из Эдема и Выжившего в другое пространство Выжившего за один раз, а затем очистите Эдем и только что использованное пространство Выжившего. Соотношение размеров виртуальной машины Eden и Survivor of HotSpot по умолчанию составляет 8:1, и только 10% пространства памяти будет простаивать и тратиться впустую.
Поколение:Алгоритм генерации делит память на несколько блоков в соответствии с жизненным циклом объекта, поэтому для разных поколений можно использовать разные алгоритмы рециркуляции.. Обычно делится на новое поколение и старое поколение.Новое поколение хранит объекты с низкой выживаемостью, и можно использовать алгоритм копирования;старое поколение хранит объекты с высокой выживаемостью.Если используется алгоритм копирования, память места будет недостаточно, поэтому необходимо использовать алгоритмы маркировки-развертки или маркировки-сортировки.

Суммировать

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

Во-первых, MMU сначала отправляет виртуальный адрес в TLB для получения PTE (адресуется в соответствии с VPN).
Если PTE кэшируется в TLB, то он возвращается в MMU, в противном случае MMU должен получить PTE из кэша/памяти, а затем обновить кэш в TLB.
После того, как MMU получит PTE, он может получить соответствующий PPN от PTE, а затем построить физический адрес в сочетании с VPO.
Если в PTE будет обнаружено, что виртуальная страница не кэширована в памяти, будет запущено исключение ошибки страницы. Обработчик исключения ошибки страницы кэширует виртуальную страницу в физической памяти и обновляет PTE. После возврата обработчика исключения ЦП перезагрузит этот виртуальный адрес и преобразует его.

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

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

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

использованная литература

CS:APP3e, Bryant and O'Hallaron
Virtual memory - Wikipedia
Garbage collection (computer science) - Wikipedia