Что и почему?

Задумывались ли вы о том, зачем компьютерам нужна оперативная память (ОП, RAM), когда у них уже есть дисковое хранилище (диск)? Ответ кроется в скорости доступа. Хотя диск является постоянным, он намного медленнее, чем ОП. ОП жертвует изменчивостью ради скорости - данные исчезают при выключении питания, но время доступа гораздо меньше. Как следствие, центральный процессор (ЦП, CPU) имеет доступ только к ОП, а не к диску.

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

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

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

Как правило, на компьютере работает несколько процессов, каждому из которых выделяется собственное пространство памяти в ОП. Задача операционной системы (ОС, OS) — выделить память для каждого процесса таким об��азом, чтобы они не влияли друг на друга. Один из простейших способов выделения памяти — назначение процессов непрерывному блоку памяти переменного размера (variably sized contiguous block of memory), при этом каждый блок может содержать ровно один процесс.

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

При создании процессов ОС учитывает требования к памяти каждого процесса и объем доступного пространства памяти для выделения достаточного для процесса раздела. После выделения памяти процесс загружается в память и начинает выполняться. После завершения процесса ОП освобождает блок памяти, делая его доступным для других процессов. Если для входящего процесса недостаточно места, ОС может выгрузить некоторые процессы на диск, чтобы освободить место в памяти. В качестве альтернативы можно поместить такие процессы в очередь ожидания (wait queue). Когда память освобождается, ОС проверяет очередь ожидания и определяет, удовлетворяются ли требования к памяти какого-либо ожидающего процесса.

В процессе выделения памяти ОС должна найти достаточно большой непрерывный блок памяти для процесса. Для этого существует множество алгоритмов, таких как first-fit, best-fit и worst-fit. First-fit ищет первый достаточно большой блок и прекращает поиск, как только находит его. Best-fit ищет по всему пространству памяти наименьший достаточно большой блок. Worst-fit ищет по всему пространству памяти наибольший достаточно большой блок. First-fit и Best-fit показывают лучшие результаты, чем Worst-fit, как по времени, так и по использованию памяти. First-fit обычно быстрее, чем Best-fit, хотя эффективность использования памяти у них примерно одинаковая.

Внешняя фрагментация

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

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

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

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

На практике ОС используют более сложную стратегию распределения памяти, называемую страничной организацией памяти (пейджинг, paging), чтобы избежать внешней фрагментации. Пейджинг делит ОП на блоки фиксированного размера, называемы�� кадрами (frames). Вместо непрерывного блока памяти для каждого процесса ОС выделяет несколько кадров, которые могут быть разбросаны по всей ОП.

Говоря о страничной организации памяти, нельзя не сказать о физической и виртуальной (логической) памяти. Физическая память относится к ОП, установленной в компьютере, тогда как виртуальная память — это абстракция, которую ОС используют для управления памятью процессов. Процессы могут обращаться только к виртуальной памяти, а ОС отвечает за отображение (mapping) виртуальной памяти на физическую. Хотя физическая память процесса может быть несмежной, с точки зрения каждого процесса, он имеет собственное изолированное виртуальное пространство памяти, которое выглядит как непрерывный блок.

🧑‍💻 Чтобы лицезреть концепцию виртуальной памяти, вы можете запустить эту программу на Go, получить адрес памяти переменной для последующего сравнения, открыть другие программы, а затем снова запустить эту программу.

package main

func main() {
  x := 0
  println(&x)
}

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

Виртуальная память разделена на блоки фиксированного размера, называемые страницами (pages), которые имеют тот же размер, что и кадры в физической памяти. Разделяя виртуальную и физическую память и используя такие методы, как пейджинг по требованию/запросу (demand paging) (см. ниже), процесс может получить доступ к 18,4 миллионам ТБ памяти на 64-битной архитектуре или до 4 ГБ на 32-битной архитектуре, даже если фактической физической памяти значительно меньше, например, 512 МБ.

Каждая страница имеет номер страницы p, а каждый кадр — номер кадра f. Каждый адрес имеет смещение d, определяющее его конкретное положение внутри страницы или кадра. Значения p и f находятся в старших битах адреса, а d — в младших битах. Сопоставление (mapping) между виртуальными страницами и физическими кадрами поддерживается в структуре данных для каждого процесса, называемой таблицей страниц (page table). В таблице страниц каждая запись индексируется номером страницы p, а соответствующее значение — номером кадра f.

Аппаратное обеспечение пейджинга

Для получения физического адреса виртуального объекта выполняются следующие шаги:

  1. Номер страницы p извлекается из виртуального адреса.

  2. Номера кадра f извлекается из таблицы страниц.

  3. Номер страницы p заменяется на номер кадра f в виртуальном адресе.

Модель пейджинга

На самом деле структура таблицы страниц не так проста и может иметь разные формы для эффективного управления памятью. Один из распространенных подходов, используемый в Linux, — это многоуровневая (иерархическая) таблица страниц (multi-level (hierarchical) page table), где каждый уровень содержит таблицы страниц, которые отображаются на следующий уровень, в конечном итоге приводя к физическому кадру. Другой метод — это хешированная таблица страниц (hashed page table), где хеш-функция сопоставляет виртуальные номера страниц с записями в хеш-таблице, которые указывают на физические кадры. Третий вариант — это инвертированная таблица страниц (inverted page table), где каждая запись представляет собой кадр в физической памяти и хранит виртуальный адрес страницы, которая в данный момент там находится, а также информацию о процессе-владельце.

Иерархическая таблица страниц

Хешированная таблица страниц

Инвертированная таблица страниц

Виртуальная память позволяет нескольким процессам использовать одни и те же файлы и память посредством совместного доступа к страницам (page sharing). Например, в браузере Chrome каждая вкладка представляет собой отдельный процесс, но использует одни и те же общие библиотеки, такие как libc и libssl. Вместо загрузки отдельных копий для каждой вкладки, ОС отображает одни и те же физические страницы в каждый процесс, что значительно снижает потребление памяти.

Пейджинг по запросу

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

Пейджинг по запросу

При выполнении программы некоторые страницы загружаются в память, а другие остаются на диске (т.е. в резервной памяти). Для управления этим процессом в таблицу страниц добавляется дополнительный столбец, называемый битом допустимости/недопустимости (valid-invalid bit), определяющий состояние каждой страницы. Если бит установлен в значение valid (v) , страница является допустимой (т.е. принадлежит логическому адресному пространству процесса) и в данный момент загружена в память. Если бит установлен в значение invalid (i), страница либо находится за пределами логического адресного пространства процесса (является недопустимой), либо является допустимой, но в данный момент находится на диске.

Когда процесс пытается получить доступ к странице, у которой бит допустимости/недопустимости установлен в значение invalid (i), происходит ошибка доступа к странице (page fault), что приводит к передаче управления ОС. ОС выполняет следующие шаги для обработки этой ошибки:

  1. Она проверяет внутреннюю таблицу процесса, чтобы определить, является ли обращение к памяти допустимым.

  2. Если адрес недействителен (т.е. не является частью логического адресного пространства процесса), процесс завершается.

  3. Если адрес действителен, но страница в данный момент не находится в памяти, она загружается в память.

  4. ОС находит свободный кадр в физической памяти.

  5. Это дает указание диску прочитать необходимую страницу в только что выделенный кадр.

  6. После завершения процесса внутренняя таблица и таблица страниц обновляются, чтобы отразить наличие страницы.

  7. Процесс возобновляет выполнение с той инструкции, которая вызвала ошибку доступа к странице.

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

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

Хотя абстракция виртуальной памяти освобождает программистов пользовательского пространства от непосредственного управления физической памятью, при выделении памяти все еще возникают проблемы. Разработчикам необходимо учитывать такие вопросы, как место выделения памяти, допустимость данного адреса и наличие конфликтов с зарезервированными областями, такими как сегмент кода (code segment). Для решения этих проблем ОС вводят концепцию структуры виртуальной памяти (virtual memory layout). С точки зрения процесса, это выглядит так, как показано ниже, причем адреса растут снизу вверх.

Структура виртуальной памяти процесса Linux x86-64

Виртуальная память делится на несколько сегментов:

  1. Пространство виртуальной памяти ядра: зарезервировано для ядра и недоступно для процессов пользовательского пространства.

  2. (Пользовательский) стек (stack): содержит кадры стека основного потока процесса и растет (увеличивается в размерах) вниз.

  3. Области, отображаемые в память (memory mapped regions): память, выделенная с помощью mmap для общего доступа, отображения в файл или анонимного доступа.

  4. Куча (heap): память, выделяемая процессом для динамического распределения памяти, размер которой увеличивается вверх.

  5. Сегмент инициализированных данных ( .data): содержит глобальные и статические переменные, инициализируемые программой.

  6. Сегмент неинициализированных данных ( .bss): содержит неинициализированные глобальные и статические переменные программы.

  7. Сегмент кода только для чтения: содержит исполняемый код пр��граммы, который обычно доступен только для чтения.

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

Выделение стека

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

Каждый поток (thread) имеет собственный стек. Поскольку процесс может содержать несколько потоков, в рамках одного процесса может быть несколько стеков. Когда говорят о "стеке процесса", обычно подразумевается стек основного потока. При создании потока ему назначается стек, отдельный от стека основного потока. Поскольку каждый поток имеет изолированный стек, выделение памяти в стеке не требует синхронизации. Если новый поток создается с помощью системного вызова pthread_create, ​​по умолчанию, ядро автоматически выбирает подходящую область памяти для стека. В качестве альтернативы мы можем вручную указать начальный адрес стека с помощью системного вызова pthread_attr_setstack. Это поведение также применяется к потокам, созданным с помощью системного вызова clone.

Размер стека фиксируется во время создания потока и не может быть динамически изменен. Размер стека по умолчанию определяется ограничением ресурсов RLIMIT_STACK. Дефолтным значением RLIMIT_STACK обычно является 2 МБ на большинстве архитектур или 4 МБ на POWER и Sparc-64. RLIMIT_STACK является глобальным. С помощью pthread_attr_setstacksize можно установить больший размер стека, если поток создает большие переменные или выполняет вложенные вызовы функций большой глубины (возможно, из-за рекурсии).

Для отслеживания вершины стека процессор использует специальный регистр, называемый указателем стека (stack pointer). В зависимости от архитектуры, он может называться RSP на x86-64, ESP на x86 или SP на ARM. Перед началом выполнения потока указатель стека инициализируется указателем на вершину стека. Поскольку стек предварительно выделяется при создании потока, выделение переменной в стеке — это просто перемещение указателя стека вниз, что является очень быстрой операцией. Загрузка переменной из стека также быстрая, поскольку требует только чтения значения по адресу, на который указывает указатель стека.

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

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

Общий кадр стека

На рисунке выше показана общая структура стекового кадра, когда функция P вызывает функцию Q. Кадр для текущей выполняемой процедуры всегда находится на вершине стека. Базовый указатель (%rbp) отмечает начало текущего стекового кадра, а указатель стека (%rsp) указывает на вершину стека. Во время выполнения функции P, она может выделять место в стеке, увеличивая указатель стека для хранения локальных переменных.

Когда P вызывает Q, она помещает адрес возврата в стек, что сообщает программе, откуда продолжать выполнение P после возврата из Q. Этот адрес возврата считается частью стекового кадра P, поскольку он содержит состояние, относящееся к P. На данном этапе P также может сохранить значения регистров и подготовить аргументы для вызванной процедуры. Когда управление переходит к Q, базовый указатель %rbp больше не указывает на стековый кадр P; он обновляется и указывает на начало кадра Q. Затем Q освобождает свой стековый кадр, уменьшая указатель стека при возврате.

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

Выделение кучи

Размещение переменных в куче означает поиск свободного блока памяти в сегменте кучи или изменение размера кучи, если такого блока памяти нет. Текущий предел кучи называется прерыванием программы (program break) или сокращенно brk, как показано на рисунке ниже.

Положение brk в структуре виртуальной памяти

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

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

malloc сначала сканирует список блоков памяти, ранее освобожденных free, пытаясь найти подходящий по размеру блок (большего или равного размера). В зависимости от реализации, для этого сканирования могут применяться разные стратегии, например, First-fit или Best-fit. Если размер блока точно совпадает с требуемым, он возвращается вызывающему. Если размер блока больше требуемого, он разделяется на два блока: блок нужного размера возвращается вызывающему, а второй остается в списке свободных блоков. Если в списке нет подходящего блока, malloc вызывает sbrk для выделения дополнительной памяти. malloc увеличивает brk на больший размер, чем необходимо, и помещает лишнюю память в список свободных блоков. Это позволяет снизить количество вызовов sbrk.

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

Список свободных блоков

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

Отображение памяти

Как показано на приведенной ниже схеме виртуальной памяти, помимо кучи и стека, существует также сегмент памяти, называемый отображаемыми областями памяти (memory mapped regions). Существует два типа отображения памяти: отображение в файл и анонимное отображение. Отображение в файл напрямую отображает область файла в виртуальную память вызывающего процесса, позволяя получать доступ к его содержимому с помощью операций над байтами в соответствующей области памяти. Анонимное отображение не имеет соответствующего файла; вместо этого страницы отображения инициализируются нулями. Другими словами, анонимное отображение — это отображение виртуального файла, содержимое которого всегда инициализируется нулями.

Структура памяти для программ ELF

Отображаемая память может быть частной (private) (копируемой при записи, copy-on-write) или разделяемой (shared). Частная область доступна только создавшему ее процессу. Всякий раз, когда процесс пытается изменить содержимое страницы, ядро ​​сначала создает новую, отдельную копию этой страницы для процесса и корректирует таблицы страниц этого процесса. И наоборот, если область является разделяемой, то все процессы, которые ее используют, могут видеть внесенные любым из них изменения.

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

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

Linux предоставляет системный вызов mmap для создания нового отображения памяти в виртуальном адресном пространстве процесса. Наиболее важным параметром является addr, который задает предпочтительный начальный адрес отображения. Если addr установлен в NULL, ядро самостоятельно выбирает подходящий адрес. Если указано значение, отличное от NULL, ядро ​​рассматривает его как подсказку и пытается разместить отображение рядом с этим адресом, округляя его при необходимости до ближайшей границы страницы. Во всех случаях ядро ​​гарантирует, что выбранный адрес не будет конфликтовать с существующими отображениями.

Ссылки