Какие алгоритмы распределения памяти использует современная ос windows а какие ос linux - Windowsa.top

Управление памятью в операционных системах

Введение

Управление памятью – это критически важная и при этом довольно сложная задача для операционной системы. Это дает возможность запускать несколько процессов одновременно без сбоев.

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

В этой статье мы рассмотрим ключевые концепции управления памятью в операционных системах.

Что такое управление памятью?

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

Эффективность управления памятью зависит от двух факторов:

1. Организация блока памяти. Блок памяти состоит из нескольких типов памяти. Иерархия и организация памяти компьютера влияют на скорость доступа к данным и размер хранилища. Более быстрые и меньшие кэши хранятся ближе к процессору, а более крупная и медленная память – дальше.

2. Доступ к памяти. Процессор постоянно обращается к данным, которые хранятся в памяти. Эффективный доступ к памяти влияет на то, насколько быстро процессор выполняет задачи и становится доступным для новых. Доступ к памяти предусматривает работу с адресами и определение правил доступа на разных уровнях памяти.

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

Для чего нужно управление памятью?

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

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

Таким образом, управление памятью влияет на следующие факторы:

Использование ресурсов. Управление памятью – это ключевой аспект распределения ресурсов компьютера. Центральный компонент – оперативная память, и процессы используют ее для работы. Операционная система сама решает, как разделить память между процессами. Правильное распределение гарантирует, что каждый процесс получит необходимое количество памяти для одновременного выполнения.
Оптимизация производительности. Те или иные механизмы управления памятью оказывают значительное влияние на скорость и стабильность системы. Все эти механизмы направлены на то, чтобы сократить количество операций получения доступа к памяти, которые дают большую нагрузку на процессор.
Безопасность. Управление памятью обеспечивает безопасность данных и процессов. Изоляция памяти позволяет сделать так, чтобы процессы использовали только ту память, которую им предоставили. Кроме того, управление памятью позволяет реализовать механизм прав доступа, который поможет предотвратить вход в закрытые области памяти.

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

Адреса памяти

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

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

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

Физические адреса

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

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

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

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

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

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

Статическая и динамическая загрузка

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

Статическая загрузка распределяет память и адреса при запуске программы. Однако, когда программа заранее загружается в память вместе со всеми необходимыми ресурсами, мы получаем предсказуемое, но крайне неэффективное использование ресурсов. Системные утилиты и приложения используют статическую загрузку с целью упростить распространение программ. Исполняемые файлы требуют компиляции и, как правило, представляют собой довольно большие файлы. Как правило, статическую загрузку используют операционные системы реального времени, загрузчики и устаревшие системы.
Динамическая загрузка распределяет память и адреса непосредственно во время выполнения программы, и сама программа запрашивает ресурсы по мере необходимости. Динамическая загрузка позволяет снизить объем потребляемой памяти и обеспечивает многозадачную среду. Исполняемые файлы меньше по размеру, но добавляют дополнительную сложность за счет утечек памяти, потребления ресурсов и ошибок в процессе выполнения. Современные операционные системы (Linux, macOS, Windows), мобильные операционные системы (Android, iOS) и веб-браузеры используют именно динамическую загрузку.

Статическое и динамическое связывание

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

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

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

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

Подкачка

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

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

Swap-пространство позволяет превысить объем оперативной памяти за счет разделения данных на блоки фиксированного размера (страницы). Механизм подкачки отслеживает, какие страницы находятся в оперативной памяти, а какие откачиваются из-за ошибок страниц.

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

Фрагментация

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

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

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

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

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

Методы управления памятью

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

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

Схемы управления непрерывной памятью

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

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

Выделение общей непрерывной памяти

Персональное выделение непрерывной памяти – это один из первых методов управления памятью. При такой схеме оперативная память делится на два раздела:

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

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

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

Распределение с фиксированными разделами

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

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

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

Алгоритм двойников

Алгоритм двойников – это схема динамического управления памятью. Здесь оперативная память делится на блоки переменного размера. Зачастую размеры представляются степенями двойки (2 Кб, 4 Кб, 8 Кб, 16 Кб и т.д.).

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

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

Схемы управления несмежной памятью

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

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

Ниже мы привели описание самых важных механизмов управления несмежной памятью.

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

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

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

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

Страничная организация памяти позволяет сократить внешнюю фрагментацию. Это гибкий, переносимый и эффективный механизм управления памятью. Его используют многие современные операционные системы (Linux, Windows и macOS).

Сегментация

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

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

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

Заключение

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

Источник

6.2. Функции ОС по управлению памятью

Под памятью (memory) в данном случае подразумевается оперативная (основная) память компьютера. В однопрограммных операционных системах основная память разделяется на две части. Одна часть для операционной системы (резидентный монитор, ядро), а вторая – для выполняющейся в текущий момент времени программы. В многопрограммных ОС «пользовательская» часть памяти – важнейший ресурс вычислительной системы – должна быть распределена для размещения нескольких процессов, в том числе процессов ОС. Эта задача распределения выполняется операционной системой динамически специальной подсистемой управления памятью (memory management). Эффективное управление памятью жизненно важно для многозадачных систем. Если в памяти будет находиться небольшое число процессов, то значительную часть времени процессы будут находиться в состоянии ожидания ввода-вывода и загрузка процессора будет низкой.

В ранних ОС управление памятью сводилось просто к загрузке программы и ее данных из некоторого внешнего накопителя (перфоленты, магнитной ленты или магнитного диска) в ОЗУ. При этом память разделялась между программой и ОС. На рис. 6.3 показаны три варианта такой схемы. Первая модель раньше применялась на мэйнфреймах и мини-компьютерах. Вторая схема сейчас используется на некоторых карманных компьютерах и встроенных системах, третья модель была характерна для ранних персональных компьютеров с MS-DOS.

Рис.
6.3.
Варианты распределения памяти

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

Функциями ОС по управлению памятью в мультипрограммных системах являются:

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

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

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

Рис.
6.4.
Типы адресов

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

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

Совокупность виртуальных адресов процесса называется виртуальным адресным пространством. Диапазон адресов виртуального пространства у всех процессов один и тот же и определяется разрядностью адреса процессора (для Pentium адресное пространство составляет объем, равный 2³² байт, с диапазоном адресов от 0000.0000₁₆ до FFFF.FFFF₁₆).

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

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

6.3. Распределение памяти

Существует ряд базовых вопросов управления памятью, которые в различных ОС решаются по-разному. Например, следует ли назначать каждому процессу одну непрерывную область физической памяти или можно выделять память участками? Должны ли сегменты программы, загруженные в память, находиться на одном месте в течение всего периода выполнения процесса или их можно время от времени сдвигать? Что делать, если сегменты программы не помещаются в имеющуюся память? Как сократить затраты ресурсов системы на управление памятью? Имеется и ряд других не менее интересных проблем управления памятью [5, 10, 13, 17].

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

Рис.
6.5.
Классификация методов распределения памяти

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

Рис.
6.6.
Варианты фиксированного распределения памяти

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

Программа может быть слишком велика для размещения в разделе. В этом случае программист должен разрабатывать программу, использующую оверлеи, чтобы в любой момент времени требовался только один раздел памяти. Когда требуется модуль, отсутствующий в данный момент в ОП, пользовательская программа должна сама его загрузить в раздел памяти программы. Таким образом, в данном случае управление памятью во многом возлагается на программиста.
Использование ОП крайне неэффективно. Любая программа, независимо от ее размера, занимает раздел целиком. При этом могут оставаться неиспользованные участки памяти большого размера. Этот феномен появления неиспользованной памяти называется внутренней фрагментацией (internal fragmentation).

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

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

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

Недостаток заключается в том, что отдельные очереди для разделов могут привести к неоптимальному распределению памяти системы в целом. Например, если в некоторый момент времени нет ни одного процесса размером от 7 до 12 Мбайт, то раздел размером 12 Мбайт будет пустовать, в то время как он мог бы использоваться меньшими процессами. Поэтому более предпочтительным является использование одной очереди для всех процессов. В момент, когда требуется загрузить процесс в ОП, выбирается наименьший доступный раздел, способный вместить данный процесс.

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

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

Для преодоления сложностей, связанных с фиксированным распределением, был разработан альтернативный подход, известный как динамическое распределение. В свое время этот подход был применен фирмой IBM в операционной системе для мэйнфреймов в OS/MVT (мультипрограммирование с переменным числом задач – Multiprogramming With a Variable number of Tasks). Позже этот же подход к распределению памяти использован в ОС ЕС ЭВМ [12] .

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

Рис.
6.7.
Вариант использования памяти

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

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

Перечислим функции операционной системы по управлению памятью в этом случае.

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

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

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

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

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

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

Рис.
6.8.
Преобразование адресов

Источник

Практическое
занятие №3

Тема: Управление
памятью

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

Ход работы

1. Ознакомиться с краткими
теоретическими сведениями.

2. Выполнить задания.

3. Ответить на контрольные
вопросы.

4. Оформить отчет.

Теоретическая часть

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

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

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

Информацию о параметрах разных
видов памяти в ОС MS Windows можно получить с помощью
Диспетчера задач.

Диспетчер задач позволяет
просматривать общее использование памяти на вкладке Быстродействие, где
отображается информация в трех разделах:

1) в
разделе Выделение памяти содержатся три статистических параметра
виртуальной памяти:

а) Всего — это общий объем
виртуальной памяти, используемой как приложениями, так и ОС;

б) Предел — объем
доступной виртуальной памяти;

в) Пик — наибольший объем
памяти, использованный в течение сессии с момента последней загрузки;

2) в
разделе Физическая память содержатся параметры, несущие информацию о
текущем состоянии физической памяти машины, которая не имеет отношения к файлу
подкачки:

а) параметр Всего — это
объем памяти, обнаруженный ОС на компьютере;

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

в) системный кэш – объем физической
памяти, доступный кэш-памяти системы и оставленный ОС после удовлетворения
своих потребностей;

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

а) Всего — объем
виртуальной памяти, необходимый ОС;

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

в) Невыгружаемая — объем
физической памяти, потребляемой ОС.

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

— в
окне Диспетчера задач представлены процессы, зарегистрированные в Windows, не включены драйверы устройств, некоторые
системные службы;

— требования
к памяти отражают текущее состояние процесса (объемы памяти, занимаемые
приложениями в текущий момент);

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

Утилита TaskList доставляет более обширную информацию по сравнению с Диспетчером задач.
Запускается утилита из окна командной строки.

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

— полный
объем установленной в компьютере физической памяти;

— общий
объем виртуальной памяти и доступной (свободной) в данный момент времени
виртуальной памяти;

— размещение
и объем файла подкачки.

Практические задания

Задание 1. Щелкните на кнопке Ресурсы аппаратуры, а затем на кнопке Память,
и получите сведения об использовании физической памяти аппаратными компонентами
компьютера.

Задание 2. Изменение размера файла подкачки.

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

Для самостоятельной установки
размера файла подкачки нужно выполнить следующую последовательность действий:

а) щелкнуть правой кнопкой мыши
по значку Мой компьютер и выбрать в контекстном меню строку Свойства;

б) перейти на вкладку Дополнительно
и нажать кнопку Параметры в рамке Быстродействие;

в) в появившемся окне Параметры
быстродействия нажать кнопку Изменить.

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

Основное правило — при небольшом
объеме оперативной памяти файл подкачки должен быть достаточно большим. При
большом объеме оперативной памяти (512 Мбайт) файл подкачки можно уменьшить.
Можно установить Исходный размер файла подкачки, равный размеру
физической памяти, а Максимальный размер не более двух размеров
физической памяти.

После этого нажмите кнопку Задать
и убедитесь, что новое значение файла подкачки установлено.

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

Нажмите ОК.

Задание 3. Используя командную строку, получите отчеты о распределении памяти в
системе с помощью команд

wmic os get FreePhysicalMemory

wmic os get FreeSpaceInPagingMemory

wmic os get FreeVirtualMemory

wmic os get MaxProcessMemorySize

wmic os get SizeStoredInPagingFiles

wmic os get TotalSwapSpaceSize

wmic os get TotalVirtualMemorySize

wmic os get TotalVisibleMemorySize

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

Содержание
отчета

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

Контрольные вопросы

1. Зачем нужна оперативная память компьютеру?

2. Что такое виртуальная память, ее назначение.

3. Какие алгоритмы распределения памяти использует современная ОС Windows, а какие ОС Linux?

Источник

Уровень сложностиПростой

Время на прочтение20 мин

Количество просмотров37K

Начнем издалека. В спецификации любого компьютера и в частности сервера непременно числится надпись «N гигабайт оперативной памяти» — именно столько в его распоряжении находится физической памяти.

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

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

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

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

Как многие знают, существует виртуальная память — это то, что создаёт операционная система для работы программ с ней. Это сама ОЗУ и все SWAP разделы. Выделяемая память процессу может быть либо резидентная, либо виртуальная. В листинге ниже видно у процессов резидентную (rss) и виртуальную память (vsz). Эта память отображается в KB.

$ ps -C apache2 -o pid,user,rss,vsz,comm
    PID USER       RSS    VSZ COMMAND
    403 root      7316  11188 apache2
    405 www-data  7032 1216200 apache2
    406 www-data 11128 1216200 apache2

Виртуальная память (VSZ) — это память которую выделили процессу, но не факт что он успел в эту память что-то записать.

Резидентная память (RSS) — это память которую процесс занял, то есть что-то сохранил в виртуальную память. Именно резидентная память показывает сколько процесс потребляет физической памяти.

Приложение может запросить много памяти, а использовать малую её часть. Поэтому почти всегда rss меньше чем vsz.

Раздел подкачки (SWAP) — это раздел на жестком диске, куда помещаются:

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

Если какие-то данные из rss сбрасываются в swap то rss освобождается, а vsz нет. От сюда следует что данные процесса, которые лежат в swap, входят в виртуальную память этого процесса.

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

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

Посмотреть более подробно на используемую память процесса поможет файл /proc/<pid>/status.

Кластеры — это блоки на уровне файловой системы, с которыми происходит работа. Запись и чтение происходит блоками. Размер по умолчанию — 4KB.

Вся виртуальная память состоит из страниц. Страницы — это набор ячеек памяти в виртуальном пространстве, которому сопоставлена реальная память на диске. Страницы бывают обычные — 4 килобайта и huge page — блоки по 2 мегабайтам, либо гигабайту. Используется, когда происходит работа с большими данными, например базами данных (также структура таблицы страниц становится оптимальнее).

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

Больше всего в системе память занимает страничный кеш (Page Cache). Вся работа с файлами на диске (запись или чтение) идет через Page Cache. Запись в linux всегда быстрее чтения (Не всегда, например, если использовать O_SYNC), так как запись вначале идет в Page Cache, а затем сбрасывается на диск. А при чтении ядро ищет файл в Page Cache, и если не находит читает файл с диска. Узнать сколько сейчас система тратит памяти на Page Cache можно выполнив команду free:

$ free -h

               total        used        free      shared  buff/cache   available

Mem:           976Mi        74Mi       764Mi       0,0Ki       137Mi       765Mi

Swap:          974Mi          0B       974Mi

Страничный кеш показан в колонке buff/cache. Как мы видим у нас занято 137MB страничным кешем. Хотя тут не только Page Cache, тут также находится Buffer, который тоже связан с файлами на диске.

Посмотреть информацию по Page Cache и Buffer отдельно можно в файле /proc/meminfo:

egrep "^Cach|^Buff" /proc/meminfo

Buffers:           16012 kB

Cached:           101220 kB

При создании нового файла, запись идет в cache, а страницы памяти для этого файла помечаются как грязные (dirty). Раз в какой-то промежуток времени грязные страницы сбрасываются на диск, и если таких страниц будет слишком много, то они тоже сбросятся на диск. Управлять этим можно через параметры sysctl (sudo nano /etc/sysctl.conf):

vm.dirty_expire_centisecs — интервал сброса грязных страниц на диск в сотых долях секунд (100 = 1с);
vm.dirty_ratio — объем оперативной памяти в процентах который может быть выделен под Page Cache.

$ sudo sysctl vm.dirty_expire_centisecs

vm.dirty_expire_centisecs = 3000

$ sudo sysctl vm.dirty_ratio

vm.dirty_ratio = 20

Существует утилита — vmtouch, она может показать какой процент указанного файла находится в страничном кеше. Она есть в репозиториях Debian и в Arch User Repository.

$ sudo apt update

$ sudo apt install vmtouch

$ vmtouch /etc/passwd

           Files: 1

     Directories: 0

  Resident Pages: 1/1  4K/4K  100%

         Elapsed: 6.3e-05 seconds

Видно что весь файл /etc/passwd сейчас находится в Page Cache (Resident Pages).

Узнать объем грязных страниц можно из файла /proc/meminfo. А команда sync записывает грязные страницы на диск:

$ grep Dirty /proc/meminfo

Dirty:                24 kB

# sync

$ grep Dirty /proc/meminfo

Dirty:                 0 kB

HugePages

Поговорим немного про большие страницы HugePages. Особенности таких страниц:

размер таких страниц равен 2MB;
приложение должно уметь работать с такими страницами;
эти страницы никогда не сбрасываются в swap.

Выделить под HugePages страницы можно параметром sysctl:

vm.nr_hugepages = <число страниц> (так если указать 1024 то выделится 1024*2МБ=2048MB).
vm.hugetlb_shm_group = <gid> — только члены этой группы могут использовать HugePages.

После исправления /etc/sysctl.conf нужно перезагрузиться и посмотреть на результат в файле /proc/meminfo:

$ egrep "HugePages_T|HugePages_F" /proc/meminfo

HugePages_Total:    1024

HugePages_Free:     1024

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

Методы управления подсистемой памяти

swap

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

С анонимной памятью такой трюк не работает: ей не соответствует никакой файл, по-этому чтобы данные не пропали безвозвратно, их нужно положить куда-то ещё. Для этого можно использовать так называемый «swap» раздел или файл. Можно, но на практике не нужно. Если swap выключен, то анонимная память становится невытесняемой, что делает время обращения к ней предсказуемым.

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

mlock

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

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

Несколько примеров, когда это может быть целесообразно:

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

OOM killer

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

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

cgroups

По-умолчанию все пользовательские процессы наравне претендуют на почти всю физически доступную память в рамках одного сервера. Это поведение редко является приемлемым. Даже если сервер условно-однозадачный, например только отдает статические файлы по HTTP с помощью nginx, всегда есть какие-то служебные процессы вроде syslog или какой-то временной команды, запущенной человеком. Если же на сервере одновременно работает несколько production процессов, например, популярный вариант — подсадить к веб-серверу memcached, крайне желательно, чтобы они не могли начать «воевать» друг с другом за память в случае её дефицита.

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

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

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

NUMA

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

Таким образом, каждый процессор может обращаться к определенной 1/N части физической памяти быстрее (примерно раза в полтора), чем к оставшимся (N-1)/N.

Ядро Linux самостоятельно умеет это всё определять и по-умолчанию достаточно разумным образом учитывать при планировании выполнения процессоров и выделении им памяти. Посмотреть как это все выглядит и подкорректировать можно с помощью утилиты numactl и ряда доступных системных вызовов, в частности get_mempolicy/set_mempolicy.

Работа с памятью в Linux

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

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

Физическая — оперативная память машины.
Линейная — виртуальная память, она может быть больше, чем реально физической памяти у вас есть.

Вся физическая память разбита на страничные кадры. Размер страничного кадра — платформозависимая величина, для x86 она обычно равна 4 Кб, хотя может быть и 4 Мб. Каждый физический кадр описывается фундаментальной структурой данных — struct page (include/linux/mm_types.h). Структура используется, чтобы отслеживать состояние страничного кадра: свободен или выделен, кому он принадлежит, что на нём хранится: данные, код и т.д. Struct page организована в блоки двойных слов для выполнения над ними атомарных операций, работающих с двойными словами. Опишем некоторые важные поля struct page:

atomic_t _refcount — количество ссылок на структуру page. Из функции init_free_pfn_range() (mm/init.c) следует, что если _refcount равен 0, то страничный кадр свободен, если >0, то кем-то или чем-то занят.
unsigned long flags — содержит флаги, описывающие состояние страничного кадра. Все флаги описаны в файле (include/linux/page-flags.h).

Физическая память 32-битной машины в Linux разделяется на 3 части — зоны:

ZONE_DMA — первые 16 Мб физической памяти,
ZONE_NORMAL — занимает адреса с 16 Мб по 896 Мб,
ZONE_HIGHMEM — содержит страничные кадры выше 896 Мб

Такое разбиение физической памяти в 32 битных системах связано с тем, что в них можно адресовать только лишь 4 Гб линейной памяти, при этом процессу необходимо работать, как в пользовательском режиме, так и в режиме ядра, например, для выполнения системных вызовов. Потому линейное пространство адресов процесса разбивается на несколько частей: 3 Гб под пользователя и 1 Гб под ядро. В первых 3 Гб в адресах до 0xС0000000 процесс работает в режиме обычного пользователя, а адреса выше 0xС0000000 используются в режиме суперюзера. Зоны NORMAL и DMA напрямую отображаются в 4-ый Гб линейного адресного пространства. К объектам, расположенным в этих областях, всегда можно получить доступ, так как для них существуют линейные адреса. А вот HIGHMEM зона содержит кадры, к которым ядро так просто обратится не может. Из-за того, что HIGHMEM содержит кадры, линейные адреса которых просто напросто не существуют в 32-битной системе. Потому функция для выделения страничных кадров — alloc_page() возвращает указатель(линейный адрес) не на первый страничный кадр, а на первый страничный дескриптор, описывающий этот кадр. При этом все дескрипторы страничных кадров находятся в NORMAL зоне, потому для них всегда существует линейный адрес. Для отображения верхних адресов в линейное адресное пространство используются верхние 128 МБ NORMAL адресов. Вообще для отображения HIGHMEM есть несколько техник:

постоянное отображение,
временное отображения,
работа с несмежными областями памяти.

Linux — современная кроссплатформенная операционная система, а такая система обязана уметь эффективно работать с многопроцессорными системами. В таких системах существует несколько подходов к реализации компьютерной памяти. Первая — Uniform memory access (UMA). В этой схеме доступ ко всей физической памяти примерно равноценен по времени, потому нет абсолютно никакой разницы для производительности операционной системы к каким адресам обращаться. Надо заметить, что не в каждой вычислительной системе поддерживается одинаковый доступ к памяти, потому в Linux в качестве базовой модели поддерживается — Non-Uniform memory access (NUMA). В этой модели физическая память системы разделяется на несколько узлов. Каждый узел описывается структурой pg_data_t (include/linux/mmzone.h). Каждый узел потенциально может содержать любую из зон памяти, потому структура pg_data_t содержит их описатели. Все дескрипторы страничных кадров узлов хранятся в глобальном массиве zone_mem_map, который располагается в описателе соотвествующей зоны:

                     pg_data_t
                         |
     ________________node_zones_______________
    /                    |                    \
ZONE_DMA            ZONE_NORMAL          ZONE_HIGHMEM
    |                    |                     |
zone_mem_map        zone_mem_map           zone_mem_map

Красота такого подхода при работе с памятью заключается в том, что UMA представляется просто, как NUMA с одним узлом, что так же позволяет использовать везде одинаковые методы — универсальность во всём, так сказать.

На 64-битных машинах, физическая память так же разделяется на 3 части, но в силу объективных причин, реальные 64-битные машины не могут сейчас содержать все 2^64 степени байт памяти. В x86, например, поддерживается память только до 2^48 байт = 256 Тб, что, согласитесь, достаточно много. Так как реальной физической памяти много меньше линейной, то у 64-битных систем надобность в HIGHMEM зоне пока отсутствует, она нулевая, а вся помять делиться между DMA и NORMAL.

Теперь мы знаем, как Linux описывает доступную ему физическую память, пришло время разобрать, как ядро работает с памятью. Для этого важно разобрать, как Linux её выделяет, или, иными словами, как работают аллокаторы.

Bootmem

Самый первый доступный ядру алокатор памяти — bootmem(mm/bootmem.c). bootmem алокатор используется только при загрузке ядра для начального выделения физической памяти до того, как подсистема управления памятью станет доступной. bootmem работает очень прямолинейно по алгоритму первый подходящий — ищет первый свободный кусок(страницу) физической памяти и выдаёт. Для представления физической памяти использует bitmap, если 1, то страница занята, если 0, то свободна. Для выделения памяти меньше страницы он записывает PFN последней такой алокации, и следующая маленькая локация будет, если возможно, располагаться на той же физической странице. Алокатор с алгоритмом первый наиболее подходящий, не сильно страдает от фрагментации, но из-за использования bitmap крайне медленный.

/include/linux/bootmem.h
/*
 * node_bootmem_map is a map pointer - the bits represent all physical
 * memory pages (including holes) on the node.
 */
typedef struct bootmem_data {
    unsigned long       node_min_pfn;
    unsigned long       node_low_pfn;
    void                *node_bootmem_map;
    unsigned long       last_end_off;
    unsigned long       hint_idx;
    struct list_head    list;
} bootmem_data_t;

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

---------------
|   kmalloc   |
------------------------
|   kmemcache | vmalloc|
------------------------
|         buddy        |
------------------------

Buddy

Buddy — аллокатор смежных страничных кадров, а не линейных страниц, так как для некоторых задач, таких как DMA нужны именно смежные физические страницы, потому что DMA-устройства работают с памятью напрямую. Ещё одной причиной такого подхода является то, что это позволяет не трогать таблицы страниц ядра, что ускоряет работу с памятью. Проблема аллокаторов смежных страниц — внешняя фрагментация, потому в buddy аллокаторе в Linux применяется стандартный подход — разбиение всех доступных страничных кадров на списки по степени двойки: 1, 2, 4, 8, 16, …, 1024. 1024*4096 = 4МВ. Физический адрес первого страничного кадра в блоке кратен размеру группы. Алгоритм работы: хотим выделить 256 кадров. Аллокатор проверит в списке 256, если нет, заглянет в 512, если есть возьмёт 256 кадров, а оставшиеся поместит в список 256. Если и в 512 нет, то проверяет в 1024, если есть, то возвращает 256 кадров запросившему, а оставшиеся 768 разобьёт по двум спискам 512 и 256, если и в 1024 нет, то сигналит об ошибке. У системы buddy есть глобальный объект, хранящий дескрипторы всех доступных кадров, а на каждом отдельном процессоре есть свои локальные списки доступных кадров, если в локальных списках закончилась память, то он подтягивает из глобального и наоборот возвращает если в локальных они свободны. У каждой зоны свой собственный buddy аллокатор. Для работы с buddy аллокатором необходимо использовать функции alloc_page/__rmqueue()(mm/page_alloc.c) — выделение, __free_pages()- освобождение. При работе с этими функциями необходимо отключать прерывания и брать спин блокировку zone->lock.

Плюсы buddy:

Быстрее bootmem(не использует bitmap).
Можно выделять несколько страничных кадров подряд.

Минусы buddy:

Нельзя выделить меньше страничного кадра, всегда выделяет >= PAGESIZE.
Выделяет только идущие по очереди в физической памяти, что всё равно приводит к фрагментации.

Vmalloc

У работы со смежными физическими областями есть свои плюсы в виде быстрой работы с памятью, однако и минусы в виде внешней фрагментации. В Linux есть возможность работать с несмежными областями физической памяти, к которым можно обращаться через смежные области линейного пространства. Начало области линейного пространства, где отображаются несмежные области физического, можно получить из макроса VMALLOC_START, конец — VMALLOC_END. Каждая несмежная область памяти описывается структурой(include/linux/vmalloc.h)

struct vm_struct {
    struct vm_struct    *next;      // <- список
    void                *addr;      // линейный адрес первой ячейки
    unsigned long       size;       // size + 4096(окно безопасности между несмежными областями)
    unsigned long       flags;      // тип памяти, отображаемой несметной области
    struct page         **pages;
    unsigned int        nr_pages;
    phys_addr_t         phys_addr;
    const void          *caller;
};

Выделение страниц производится функцией void *vmalloc(unsigned long size) (mm/vmalloc.c). size — размер запрашиваемой области. Выделяет память кратно странице, потому первым делом округляет size до кратного странице размера. Он выдаёт последовательные страницы, но уже в виртуальном адресном пространстве. vmalloc берёт физические страницы у buddy по страничному кадру. Освобождать память можно с помощью vfree(). Минус заключается в том, что наступает фрагментация, но уже в виртуальном памяти, плюс появляется необходимость обращаться в таблицы страниц, что долго. Потому vmalloc редко вызывают. Его применяют для модулей, буферы ввода /вывода, сетевого экрана,отображение верхней памяти.

Kmemcache

Очевидно, что для работы с маленькими областями памяти произвольной длины не buddy, не vmalloc не подходят, из-за их расточительности. Потому в Linux есть ещё одна система памяти — kmemcache, которая позволяет выделять память под небольшие объекты в пределах страничного кадра. Однако тут надо быть осторожнее, так как может возникнуть проблема внутренней фрагментации. Вообще говоря под kmemcache скрывается аде целых 3 системы: SLAB/SLUB/SLOB. Суть этих систем достаточно похожа, но имеются и существенные отличия:

SLOB — для встраиваемых подсистем, отсюда следует то, что он использует минимум памяти и показывает низкую производительность, так же страдает от внутренней фрагментации.
SLAB — был введён в солярисе и изначально был только он, но системы становились большими и SLAB стал себя плохо показывать в системах с большим количеством процессоров.
SLUB — эволюция SLAB — быстрее, выше, сильнее.

Сначала опишем интерфейс SLAB. Slab базируется на нескольких наблюдениях. Во-первых, ядро часто запрашивает и возвращает области памяти одного и того же размера для различных структур, потому для ускорения можно не освобождать, а оставлять их в кеше для себя, а потом переиспользовать, что сэкономит время. Лучше как можно реже обращаться к buddy, так как каждое обращение к нему загрязняет аппаратный кэш. Так же можно создать объекты размером не кратным двойки, если к ним происходит частое обращение, что ещё может улучшить работу аппаратного кэша. Slab группирует объекты в кэш. Каждый кэш — хранилище объектов одного типа( размера). Кеш имеет несколько slab-списков: с полностью свободными объектами, частично свободными и полностью занятыми. Кэш работает с гранулярностью 1-2-4-8 страниц.

kmem_cache       slab - список
________
|      |——————> | | -  | | - | |  - полностью свободны
|      |
|      |
|      |——————> | | -  | | - | |  - частично свободны
|      |
|      |——————> | | -  | | - | |  - полностью заняты
|      |

(include/linux/slub_def.h)

Для того чтобы пользоваться struct kmem_cache надо получить хэндл через функцию:

struct kmem_cache *kmem_cache_create(size);

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

void kmem_cache_alloc(kc, flags);

И освобождать:

void kmem_cache_free(kc);

Уничтожить кэш можно с помощью:

kmem_cache_destroy()

Всю информацию по SLAB можно получить в /proc/slabinfo.

Под SLAB тоже нужно было выделять память, дескриптор описывающий SLAB мог лежать: У другого kmem_cache — off-slab. Дескриптор slab может лежать в голове страницы, которую выдаёт buddy — on-slab. Но buddy выдавал нам страницу и struct page, который по размеру совпадал со slab -> struct page можно забрать у системы и использовать его под slab. Потому появился slub. Минус SLAB allocator — выделяет объекты константного размера, хотя нам не всегда известен размер объекта под который нужно выделить память.

Более высокого уровня аллокатор kmalloc/kfree(include/linux/slab.h). Он обращается к необходимому kmem_cache, получая его через статическую функцию kmalloc_index(size). В статической функции, если размер будет известен на этапе компиляции, то вызов функции будет компилятором заменён на итоговый индекс.:

static __always_inline int kmalloc_index(size_t size)
{
...
if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
        return 1;
if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
	return 2;
if (size <= 8)
	return 3;
...
}

0 = zero alloc
1 = 65 .. 96 bytes
2 = 129 .. 192 bytes
n = (2$^{n-1}$+1) .. 2$^n$ //todo

Кэши размером 0/ 8/ 16/ 32/ 64/ 96/ 128/ 192 /256 …/2$^{26}$. 96 и 192 — эвристически вычисленные часто запрашиваемые значения.

Все аллокаторы работаю с группой флагов gfp_flags(include/linux/gfp.h) — get free page flags. Изначально они появились в buddy потом просочись на уровни повыше.

Типы флагов:

Откуда выделять: __GFP_DMA (Get Free Page), __GFP_HIGHMEM, __GFP_DMA32. По умолчанию система старается выделять память в ZONE_NORMAL.
Поведение при нехватке памяти — контекст, в котором мы работаем по сути. Если памяти нет, то её нужно найти, например:
- в дисковом кэше — требуется брать мютекс;
- ядерном кэше — требуется брать мютекс;
- освободить грязный дисковый кэш — требуется брать мютекс и обращаться к файловой системе и блокам;
- swap требуется брать мютекс и обращаться к блокам;
- kill кого-нибудь; Пример, __GFP_ATOMIC — ничего нельзя делать и buddy вернёт NULL. __GFP_NOFS — используются кэшами и буферами, чтобы быть уверенными, что их рекурсивно не позовут. __GFP_NOIO.
Всё остальное — __GFP_ZERO — память которую выдаст аллокатор должен быть забит нулями. __GFP_TEMPORARY — мне нужно выделить страницу подержу её недолго и верну. (пути) GFP_NORETRY GFP_NOFAIL

User memory management

Запросы ядра на выделение памяти: alloc_pages() и kmalloc(), приводят к немедленному выделению памяти, если могут быть удовлетворены. Это оправдано, потому что:

Ядро — самый приоритетный компонент системы, его запросы критические.
Ядро себе доверяет, предполагается, что в ядре нет ошибок.

Для процессов, работающих в режиме пользователя, всё иначе:

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

Адресное пространство процесса

Адресное пространство процесса — линейные адреса, к которым процесс может обращаться. Ядро может динамически изменять адресное пространство процесса с помощью добавления или удаления областей памяти(vm_area_struct).

Процесс может получить новые области памяти, например, с помощью вызывов: malloc(), calloc(), mmap(), brk(), shmget() + shmat(), posix_memalign(), mmap() и т.д. В основе всех этих вызовов лежит void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);:

addr — адрес, где выделять память.
flags:
- NULL — нет никакой разницы, где выделять память. Параметр addr используется, как рекомендация.
- MAP_FIXED — именно там, где указано в addr.
- MAP_ANON(MAP_ANONYMOUS) — изменения не будут видны ни в каком файле.
- MAP_FILE — мапим из файла или устройства.
prot:
- PROT_EXEC
- PROT_READ
- PROT_WRITE
- PROT_NONE

Дескриптор памяти

Вся информация относительно адресного пространства процесса хранится в mm_struct (дескриптор памяти), на который указывает поле mm в task_struct.

task_struct
_________
|   …   |     mm_struct
---------    _________
|   mm  | -> |   …   |
---------    ---------
|   …   |    |  mmap |  ->   vm_area_struct * (VMA) – список двунап.
---------    ---------
             |  pgd  |  - указатель на глобальный каталог страниц
             ---------

Описание структур mm_struct и vm_area_struct монжо найти в /include/linux/mm_types.h.

Область памяти

struct vm_area_struct {
    /* The first cache line has the info for VMA tree walking. */

    unsigned long vm_start;     /* Our start address within vm_mm. */
    unsigned long vm_end;       /* The first byte after our end address
                       within vm_mm. */

    /* linked list of VM areas per task, sorted by address */
    struct vm_area_struct *vm_next, *vm_prev;
             ...................
             struct rb_node               vm_rb;
             ………..
    /* Function pointers to deal with this struct. */
    const struct vm_operations_struct *vm_ops;
}

У области памяти есть два поля vm_start и vm_end, обозначающие соответственно адрес начала и первого бита после конца выделенной области. Если применить mmap() с одинаковыми аргументами, то ядро не будет создавать новый VMA, а просто изменит vm_end уже существующего.

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

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root {
    struct rb_node *rb_node;
};

mm_struct -> pgd — указатель на глобальный каталог страниц каждого процесса. На x86 при переключении процесса mm_struct -> pgd помещается в cr3. Изменение cr3 в свою очередь приводит к сбросу TLB. Однако, у двух task_struct может быть один и тот же mm, например, у двух потоков, тогда изменения cr3 не будет, что существенно ускоряет работу с памятью.

Помимо потоков переключение cr3 так же не происходит для kernel_thread. Для них просто нет необходимости в областях памяти, так как они всегда обращаются к фиксированным линейным адресам выше TASK_SIZE = PAGE_OFFSET = 0xffff880000000000 (x86_64). Потому собственный mm kernel_thread в task_struct просто не нужен, он равен NULL. Зато в task_struct есть active_mm, равный active_mm вытесненного процесса.

Ещё одним интересным полем в VMA является vm_ops, оно определяет операции, которые можно выполнять для конкретной области памяти.

Работа с областями памяти

Описание функций:

do_mmap() (/mm/mmap.c) – выделение новой области памяти
do_munmap() (/mm/mmap.c) – возвращение области памяти
find_vma()(/mm/mmap.c) – поиск области ближайшей к данному адресу
find_vma_intersection() (/include/linux/mm.h) – поиск области, содержащей адрес.
get_unmapped_area() (/mm/mmap.c) — поиск свободного интервала
insert_vm_struct() (/mm/mmap.c) – внесение области в список дескрипторов

Выделение интервала линейных адресов

Линейные адреса, которые выделяются, могут быть связаны с файлом (FILE) или нет (ANON). При этом, процесс, который запрашивает память, может владеть ими совместно с кем-то (MAP_SHARED) или уникально (MAP_PRIVATE).

do_mmap

	FILE	ANON
MAP_SHARED	vma->file(get_page)	файл на tmpfs(shmat)
MAP_PRIVATE	library(COW)	HIGHMEM, ZERO(buddy)

Отложенное выделение

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

В x86 каждая запись в таблице страниц выровнена по 4096(2^12), потому первые 12 бит несут служебную информацию относительно страницы, например:

0 бит — P (Present) Flag
1 бит — R/W (Read/Write) Flag
2 бит — U/S (User/Supervisor) Flag

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

                             page fault
                                 \/
              Принадлежит ли адрес пространству процесса?
                  Да /                       Нет  \
                    \/                            \/
   Соответствуют ли права доступа?         Исключение возникло в режиме пользователя?
    Да /                     Нет\           Да /                             Нет \
      \/                        \/            \/                                 \/
Выделить новый                  Послать SIGSEGV                      Ошибка ядра: уничтожить процесс
страничный кадр

Если обращение происходит рядом со stack VMA – область созданная с флагом MAP_GROWDOWN, то происходит расширение области.

Заключение

Вся информация взята из открытых источников.

Документация физической памяти в ядре Linux

Документация на русском «Управлению памятью в Linux»

Если вам понравилась статья, то ставьте плюсы! Следующая статья будет об монтировании и обнаружении дисков в Linux.

Источник