Марк Руссинович - 2.Внутреннее устройство Windows (гл. 5-7)
• HeapAlloc — выделяет блок памяти из кучи;
• HeapFree — освобождает блок, ранее выделенный через HeapAlloc
• HeapReAlloc — увеличивает или уменьшает размер уже выделенного блока;
• HeapLock и HeapUnlock — управляют взаимным исключением (mutual exclusion) операций, связанных с обращением к куче;
• HeapWalk — перечисляет записи и области в куче.
Типы куч
У каждого процесса имеется минимум одна куча — куча, выделяемая процессу по умолчанию (default process heap). Куча по умолчанию создается в момент запуска процесса и никогда не удаляется в течение срока жизни этого процесса. По умолчанию она имеет размер 1 Мб, но ее начальный размер может быть увеличен, если в файле образа указано иное значение с помощью ключа /HEAP компоновщика. Однако этот объем памяти резервируется только для начала и по мере необходимости автоматически увеличивается (в файле образа можно указать и начальный размер переданной памяти).
Куча по умолчанию может быть явно использована программой или неявно некоторыми внутренними Windows-функциями. Приложение запрашивает память из кучи процесса по умолчанию вызовом Windows-функции GetProcessHeap. Процесс может создавать дополнительные закрытые кучи вызовом HeapCreate. Когда куча больше не нужна, занимаемое ею виртуальное адресное пространство можно освободить, вызвав HeapDestroy. Массив всех куч поддерживается в каждом процессе, и поток может обращаться к ним через Windows-функцию GetProcessHeaps.
Куча может быть создана в больших регионах памяти, зарезервированных через диспетчер памяти с помощью VirtualAlloc или через объекты «файл, проецируемый в память», отображенные на адресное пространство процесса. Последний подход редко применяется на практике, но удобен в случаях, когда содержимое блоков нужно разделять между двумя процессами или между частями компонента, работающими в режиме ядра и в пользовательском режиме. B последнем случае действует ряд ограничений на вызов функций куч. Во-первых, внутренние структуры куч используют указатели и поэтому не допускают перемещения на другие адреса. Во-вторых, функции куч не поддерживают синхронизацию между несколькими процессами или между компонентом ядра и процессом пользовательского режима. Наконец, в случае кучи, разделяемой между кодом пользовательского режима и режима ядра проекция пользовательского режима должна быть только для чтения, чтобы исключить повреждение внутренних структур кучи кодом пользовательского режима.
Структура диспетчера кучи
Как показано на рис. 7–5, диспетчер куч состоит из двух уровней: необязательного интерфейсного (front-end layer) и базового (core heap layer). Последний заключает в себе базовую функциональность, которая обеспечивает управление блоками внутри сегментов, управление сегментами, поддержку политик расширения кучи, передачу и возврат памяти, а также управление большими блоками.
Необязательный интерфейсный уровень (только для куч пользовательского режима) размещается поверх базового уровня. Существует два типа интерфейсных уровней: ассоциативные списки (look-aside lists) и куча с малой фрагментацией (Low Fragmentation Heap, LFH). LFH доступна лишь в Windows XP и более поздних версиях Windows. Единовременно для каждой кучи можно использовать только один интерфейсный уровень.
Синхронизация доступа к куче
Диспетчер куч по умолчанию поддерживает параллельный доступ из нескольких потоков. Однако, если процесс является однопоточным или использует внешний механизм синхронизации, он может отключить синхронизацию, поддерживаемую диспетчером куч, и тем самым избежать издержек, связанных с этим видом синхронизации. Для этого при создании кучи или при каждом запросе на выделение памяти такой процесс может указывать флаг HEAP_NO_SERIALIZE.
Процесс также может блокировать всю кучу и запретить другим потокам выполнение операций, требующих согласования состояний между несколькими обращениями к куче. Например, перечисление блоков в куче с помощью Windows-функции HeapWalk требует блокировки кучи, если над ней могут выполняться операции сразу несколькими потоками.
Если синхронизация куч разрешена, для каждой кучи выделяется по одной блокировке, которая защищает все внутренние структуры кучи. B приложениях с большим числом потоков (особенно когда они выполняются в многопроцессорных системах) блокировка кучи может превратиться в точку интенсивной конкуренции. B таком случае производительность можно повысить за счет использования интерфейсного уровня.
Ассоциативные списки
Это однонаправленные связанные списки (single linked lists), поддерживающие элементарные операции вроде заталкивания в список или выталкивания из него по принципу «последним пришел, первым вышел» (Last In, First Out, LIFO) без применения блокирующих алгоритмов. Упрощенная версия этих структур данных также доступна Windows-приложениям через функции InterlockedPopEntrySList и InterlockedPushEntrySList. Для каждой кучи создается 128 ассоциативных списков, которые удовлетворяют запросы на выделение блоков памяти размером до 1 Кб на 32-разрядных платформах и до 2 Кб на 64-разрядных.
Ассоциативные списки обеспечивают гораздо более высокую производительность, чем при обычных запросах на выделение памяти, так как несколько потоков могут одновременно выполнять операции выделения и возврата памяти, не требуя применения глобальной для кучи блокировки. Кроме того, благодаря модели размещения LIFO и обращению к меньшему числу внутренних структур данных при каждой операции над кучей оптимизируется локальность кэша.
Диспетчер куч поддерживает ряд блокировок в каждом ассоциативном списке и некоторые счетчики, помогающие независимо регулировать работу с каждым списком. Если поток запрашивает блок такого размера, которого нет в соответствующем ассоциативном списке, диспетчер куч переадресует этот вызов базовому уровню и обновит внутренний счетчик неудачных выделений, значение которого впоследствии будет использовано при принятии решений по оптимизации.
Диспетчер куч создает ассоциативные списки автоматически при создании кучи, если только эта куча расширяемая и не включен отладочный режим. У некоторых приложений могут возникать проблемы совместимости из-за использования диспетчером куч ассоциативных списков. B таких случаях для корректной работы нужно указывать флаг DisableHeapLookaside в параметрах выполнения файлов образов унаследованных приложений. (Эти параметры можно задавать с помощью утилиты Imagecfg.exe из Windows 2000 Server Resource Kit, supplement 1.)
Куча с малой фрагментацией
Многие приложения, выполняемые в Windows, используют сравнительно небольшие объемы памяти из куч (обычно менее одного мегабайта). Для этого класса приложений диспетчер куч применяет политику наибольшей подгонки (best-fit policy), которая помогает сохранять небольшим «отпечаток» каждого процесса в памяти. Однако такая стратегия не масштабируется для больших процессов и многопроцессорных машин. B этих случаях доступная память в куче может уменьшиться из-за ее фрагментации. B сценариях, где лишь блоки определенного размера часто используются параллельно разными потоками, выполняемыми на разных процессорах, производительность ухудшается. Дело в том, что нескольким процессорам нужно одновременно модифицировать один и тот же участок памяти (например, начало ассоциативного списка для блоков этого размера), а это приводит к объявлению недействительной соответствующей кэш-линии для других процессоров.
Эти проблемы решаются применением кучи с малой фрагментацией (LFH), которая использует базовый уровень диспетчера куч и ассоциативные списки. B отличие от ситуации, в которой ассоциативные списки по умолчанию применяются как интерфейсные, если это разрешено другими параметрами куч, поддержка LFH включается, только когда приложение вызывает функцию HeapSetInformation. B случае больших куч значительная доля запросов на выделение обычно раскладывается на относительно небольшое число корзин (buckets) определенных размеров. Стратегия выделения памяти, применяемая LFH, заключается в оптимизации использования памяти для таких запросов за счет эффективной обработки блоков одного размера.
Для устранения проблем с масштабируемостью LFH раскрывает часто используемые внутренние структуры в набор слотов, в два раза больший текущего количества процессоров в компьютере. Закрепление потоков за этими слотами выполняется LFH-компонентом, называемым диспетчером привязки (affinity manager). Изначально LFH использует для распределения памяти первый слот, но, как только возникает конкуренция при доступе к некоторым внутренним данным, переключает текущий поток на другой слот. И чем больше конкуренция, тем большее число слотов задействуется для потоков. Эти слоты создаются для корзины каждого размера, что также увеличивает локальность и сводит к минимуму общий расход памяти.
