Как заставить ядро ​​компактировать фрагментированную память

Я бегу Fedora 26.

Это очень странное задание, данное моим профессором по алгоритмам. Назначение говорит:

Фрагментация памяти в C:
проектирование, внедрение и выполнение C-программы, которая выполняет следующие функции: выделяет память для последовательности 3mмассивов размером 800 000 элементов каждая; затем он явно освобождает все четные массивы и выделяет последовательность mмассивов размером 900 000 элементов каждый. Измерьте количество времени, которое ваша программа требует для выделения первой последовательности и для второй последовательности. Выберите, mчтобы исчерпать почти всю основную память, доступную для вашей программы. "

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

В классе я спросил, как нам следует поступить так, поскольку память визуализируется и не является смежной, на что он ответил: «Ну, тебе придется отключить [виртуальную память]». Некоторые другие ученики спросили в классе, как мы должны знать, когда мы добрались до этой «сборки мусора», и он сказал, что: «Время для второго распределения должно быть больше, чем первое из-за времени, затрачиваемого на сборку мусора»

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

Я запускал программу с увеличением mи в конечном итоге нашел точку, где время для второго распределения было больше, чем время для первого распределения. Однако по пути я попал в точку, где процесс был остановлен перед вторым распределением. Я проверил dmesgи увидел, что он был убит oom-killer. Я нашел и прочитал несколько статей о oom-killer и обнаружил, что вы можете отключить перераспределение памяти ядром.

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

У меня есть три вопроса, первый из которых не так уж важен:

1. Правильный ли для этого сбор мусора? Мой профессор очень непреклонен, говоря, что это сборка мусора, но я полагал, что сборка мусора была сделана языками программирования и что это будет считаться более дефрагментирующим.

2. Возможно ли уплотнение, как он хочет, в системе Linux?

3. Почему я смог достичь точки, где время для второго выделения было больше, чем первое, когда я отключил подкачку, но по-прежнему включал перераспределение памяти? Действительно ли произошло уплотнение? Если так, то почему я не смог достичь точки, в которой произошло сжатие после того, как я отключил перераспределение памяти?

Слава вашему исследованию, это действительно интересный набор вопросов.

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

Теперь, чтобы ответить на ваши вопросы ...

1. На мой взгляд, сборка мусора на один шаг удалена от того, что вы здесь делаете. Я полагаю, вы пишете на C, используя malloc()и free(). Сборка мусора , поддерживаемая языком программирования и средой выполнения, заботится о последней части: она идентифицирует блоки памяти, которые были выделены ранее, но больше не используются (и, что важно, никогда больше не будут использоваться), и возвращает их распределителю. Вопрос, связанный в комментарии JdeBP , дает некоторую предысторию, но я нахожу его в основном интересным, потому что он демонстрирует, что разные люди имеют очень разные мнения по поводу сбора мусора и даже того, что составляет сборку мусора.

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

2. С точки зрения программирования пользовательского пространства, то, что просит ваш профессор, невозможно, в C, под Linux, по одной простой причине: здесь нас интересует не фрагментация физической памяти, а фрагментация адресного пространства. Когда вы выделите свои 800 000-байтовые блоки, вы получите столько же указателей на каждый блок. В Linux на данный момент сама операционная система мало что сделала, и вам не обязательно иметь физическую память, поддерживающую каждое выделение (кроме этого, при меньших выделениях операционная система вообще не будет задействована, только ваша Распределитель библиотеки C, но выделения здесь достаточно велики, чтобы библиотека C использовалаmmap, который обрабатывается ядром). Когда вы освобождаете блоки с нечетными номерами, вы возвращаете эти блоки адресного пространства, но вы не можете изменить имеющиеся у вас указатели на другие блоки. Если вы распечатаете указатели по ходу работы, вы увидите, что разница между ними не намного больше, чем запрос на выделение (802 816 байт в моей системе); между двумя указателями нет места для блока размером 900 000 байт. Поскольку ваша программа имеет фактические указатели на каждый блок, а не более абстрактное значение (в других контекстах, дескриптор), среда выполнения ничего не может с этим поделать, и поэтому она не может сжимать свою память для объединения свободных блоков.

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

3. Упражнения вашего профессора эффективно измеряют производительность mmap, которая включает в себя алгоритм свободной ходьбы. Сначала вы выделяете 3 × m блоков, затем освобождаете половину из них, а затем снова начинаете выделять m блоков; освобождение всех этих блоков приводит к огромной загрузке свободных блоков в распределителе ядра, которое необходимо отслеживать (и время, затрачиваемое на freeвызовы, показывает, что в данный момент оптимизация не проводится). Если вы отследите время выделения каждого отдельного блока, то увидите, что первое выделение 900 тыс. Занимает много, многодольше, чем другие (три порядка в моей системе), второй намного быстрее, но все же занимает намного больше времени (два порядка), а третье распределение возвращается к типичным уровням производительности. Так что что-то происходит, но возвращенные указатели показывают, что это не было сжатие памяти, по крайней мере, не сжатие выделенных блоков (что, как объяснено выше, невозможно) - предположительно, время соответствует времени обработки структур данных, которые ядро ​​использует для отслеживать доступное адресное пространство в процессе (я проверяю это и обновлю позже). Эти длинные распределения могут вырасти, чтобы затмить общие последовательности распределения, которые вы измеряете, то есть, когда выделения 900 КБ в целом занимают больше времени, чем распределения 800 КБ.

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