Оперативная память. Эпизод IV. Управление памятью: взгляд изнутри
8 августа 2006 года
Введение
В предыдущих статьях читатель узнал о функциях выделения и освобождения памяти. Теперь рассмотрим, как операционные системы и среды разработки приложений хранят информацию о свободной и занятой памяти и как происходит выделение и освобождение с "внутренней" точки зрения. Будут рассмотрены преимущества и недостатки систем управления кучей, а также куча с пониженной фрагментацией (LFH). Данная статья призвана помочь программисту реализовать систему управления памятью "вручную", если стандартная не годится.
Куча - это информация о свободных и занятых блоках памяти
Кучей (heap) называют большую область памяти, используемую для хранения информации о свободных и занятых блоках памяти. Первоначально, при запуске приложения, ему выделяется куча некоторого размера, как правило, фиксированного для системы. Собственно функции выделения и освобождения памяти обращаются к куче, чтобы найти свободный блок достаточного размера, помечают этот блок как занятый и возвращают его адрес приложению. В случае переполнения кучи (когда в ней не окажется свободного блока запрошенного размера) куча расширяется, если есть такая возможность. Чтобы такая возможность была, операционная система Windows, к примеру, при создании кучи сразу выделяет для нее очень большой объем памяти, но лишь несколько стартовых виртуальных страниц непосредственно выделяются, а последующие лишь резервируются. При необходимости расширения кучи зарезервированные страницы выделяются. Такой подход позволяет не перерасходовать память без нужды и в то же время оставить для кучи возможность расширения. Некоторые системы позволяют иметь несколько куч, соответственно, в операциях выделения памяти можно указать ту кучу, в которой необходимо выделить блок. К таким системам относится ОС Windows с ее функциями HeapAlloc и HeapFree.
Автор не знает алгоритмов выделения и освобождения памяти в куче, однако предполагает, что информация о свободных блоках хранится в самих свободных блоках и представляет собой двоичное дерево поиска, индексированное по размеру блока. Таким образом, для управления кучей достаточно иметь лишь указатель на корневой элемент дерева свободной памяти в куче. Благодаря такому алгоритму, поиск свободного блока будет происходить с логарифмической скоростью, то есть, попросту говоря, быстро.
Однако у такого механизма есть серьезный недостаток - фрагментация. Это означает, что постоянно выделяя и освобождая память, мы в конце концов можем прийти к тому, что свободные и занятые блоки перемежаются между собой, тогда как разместить все свободные блоки рядом и вообще объединить их в один большой блок было бы лучше. Почему? Потому, что если мы имеем большое количество мелких свободных блоков, мы будем иметь достаточно большой общий объем свободной памяти, но тем не менее можем попасть в ситуацию, когда система откажет в выделении очередного блока, так как отдельно взятые блоки имеют малый размер. Объясню на примере. Куча размером 10 Кб, вначале идет свободный блок размером 3 Кб, затем занятый размером 4 Кб, затем снова свободный размером 3 Кб. Мы просим у системы выделить еще один блок размером 4 Кб. Общий объем свободной памяти составляет 6 Кб, но нет ни одного блока размером 4 Кб или более, и система откажет в выделении блока.
Системы со сборкой мусора могут оптимизировать кучу, для чего они периодически выполняют её дефрагментацию - собирают свободные блоки вместе. Для этого приходится перемещать объекты, находящиеся в куче. Для языков без сборки мусора, где обращение к объекту в куче происходит через адрес, дефрагментация кучи невозможна или очень затруднительна.
Куча с пониженной фрагментацией
Среды разработки Delphi и C++ Builder, насколько известно автору, не "доверяют" стандартным функциям управления кучей и реализовали свои. Здесь алгоритм другой: куча делится на несколько подкуч, каждая из которых предназначена для выделения блоков строго фиксированного размера: к примеру, одна предназначена для выделения 4-байтных блоков, вторая - 8-байтных, 3-я - для 16-байтных, и т. д. Такой подход имеет как минимум два преимущества. Во-первых, не нужно создавать дерево свободной памяти - достаточен простой список, так как нет необходимости в поиске свободного блока и можно взять просто первый попавшийся элемент списка (вспомним, что элементы фиксированного размера). Во-вторых, фрагментация практически отсутствует (по крайней мере, вероятность в какой-то момент получить отказ в выделении блока нужного размера резко снижается). Я уже не говорю о том, что в дефрагментации отпадает необходимость.
Алгоритм, примененный в Delphi и C++ Builder, оказался удачным, и его внедрили в последние версии операционной системы Windows под названием LFH (low-fragmentation heap). Теперь программист имеет возможность пользоваться как стандартной кучей, так и кучей с пониженной фрагментацией.
На этом я заканчиваю цикл статей об оперативной памяти и надеюсь, что читатель почерпал для себя что-то новое, что поможет ему в разработке. Прошу присылать отзывы, просьбы, предложения на mrbus@pisem.net с темой "codenet: оперативная память". Письмо без такой темы имеет шансы быть удаленным и непрочитанным, т. к. на ящик приходит спам.
Оставить комментарий
Комментарии
