Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 131
Текст из файла (страница 131)
Рассмотрим каждый из этих способов по очереди. Повторное использование свободного пространства При получении запроса на элемент размером Юслов самым простым способом его выполнения является поиск в списке свободного пространства блока, состоящего из )У и более слов. Блок из Мелов можно прямо выделить для удовлетворения запроса. Блок, состоящий нэ более чем ослов, следует разбить на два блока: один, состоящий из дГ слов, который тут же выделяется для удовлетворения запроса, и оставяв яйся блок, который возврщцастся в список свободного пространства. Используется несколько различных методов непосредственного распределения памяти из такого списка свободного пространства.
1. Метод первого подходяц1еао. Если требуется блок размером в Желев, список свободного пространства просматривается до обнаружения первого блока, состоящего из Хили более слов, который затем разбивается па блок 10.4. Управление кучей 477 из гу'слов и остаток, который возвращается в список свободного пространстваа.
2. Метод ёаиболее подходящего. Если требуется блок размером в Мелов, список свободного пространства просматривается до обнаружения минимального блока, количество слов в котором больше или равно дг. Если в этом блоке в точности гч'слов, то он распределяется целиком как единое целое; если же количество слов в нем болъше гУ, то он разбивается падве части и остаток возвращается в список свободного пространства.
Сохранение элементов в списке свободного пространства в порядке возрастания их размеров делает распределение достаточно эффективным. В этом случае надо сканировать список, пока не будет найден блок требуемого размера. Однако возрастает стоимость добавления элемента в список свободного пространства, так как приходится осуществлять поиск в списке подходящего места для добавления нового элемента.
Восстановление блоков памяти переменного размера Перед тем как рассматривать задачу уплотнения памяти, рассмотрим методы восстановления памяти в том случае, когда куча состоит из блоков переменного размера. Отличия от случая блоков постоянного размера невелики. Явный возврат освобождаемой памяти в список свободного пространства является простейшим методом, но по-прежнему присутствуют проблемы накопления мусора и появления повисших ссылок. Счетчики ссылок в этом случае могут использоваться обычным образом. Сбор мусора также представляет подходящий метод, хотя в случае блоков переменного размера возникает несколько дополнительных проблем.
Как и раньше, процедура сбора мусора состоит из двух стадий — стадии маркировки н следующей за ней стадии сбора. Маркировка должна основываться на той же методике следования по цепи указателей. Сложности появляются на стадии сбора. Раныпе ага задача решалась путем простого последовательного просмотра памяти и проверки бита сбора мусора каждого конкретного элемента, Если этот бит находился в состоянии «включен», элемент возвращался в список свободного пространства; если бит был «выключен», то это означало, что элемент в данный момент активен и его нужно пропустить. В случае элементов переменного размера хотелось бы использовать эту же схему, цо теперь у нас встает проблема определения границы между элементами, Где заканчивается один элемент и начинается другой? Без этой информации невозможно выполнить сбор мусора. Самым простым способом решения этой проблемы является хранение в первом слове каждого блока (и активного, и неактивного), наряду с битом сбора мусора, целочисленного идентификатора длины этого блока, который просто указывает, сколько слов содержится в данном блоке.
При наличии идентификатора длины мы вновь можем последовательно просматривать блоки памяти, анализируя только первое слово каждого блока. Во время этого просмотра, прежде чем возвращать освободившиеся свободные блоки в список свободного пространства, смежные свободные блоки можно объединять в один блок, тем самым устраняя проблему частичного уплотнения, обсуждаемую ниже. 478 Глава 10.
Управление памятью Сбор мусора можно также эффективно объединить с полным уплотнением, чтобы вовсе исключить необходимость в списке свободного пространства. В этом случае буде~ нужен только простой указатель кучи. Уплотнение и проблема фрагментации памяти Проблема, с которой мы сталкиваемся при использовании элементов переменного размера в любой системс управления кучей, — это проблема фрпаненглации. Мы начинаем с одного большого блока свободного пространства.
В ходе вычислений этот блок постепенно разбивается на меньшие блоки посредством операций выделения памяти, ее восстановления и повторного использования. Если для распределения памяти применяется только простой метод первого подходящего или наиболее подходящего блока, то очевидно, что блоки свободного пространства продолжают расщепляться на все более мелкие куски.
В конце концов наступит момент, когда программа распределения памяти пе сможет удовлетворить запрос на блок из й(слов, поскольку ие окажется ни одного достаточно большого блока, хотя в целом список свободного пространства может содержать гораздо более чем У слов свободной памяти. Без некоторого объединения (уплотпения) свободных блоков в блоки большего размера выполнение программы будет остановлено из-за нехватки свободной памяти раньше, чем реально закончатся ресурсы памяти. В зависимости от того, можно ли перемегцать активные блоки в куче, применяется один из двух возможных подходов к уплотнению.
1. '1истичиое уплотнение. Если активные блоки нельзя перемещать (или перемещение обходится слишком дорого), то можно объединять только смежные блоки из списка свободного пространства. 2. Полное уплотнение. Если активные блоки можно перемсьцатгь тогла все активные блоки могут быль перемещены в один конец кучи, при этом все свободное пространство оказывается сосредоточенным яа другом конце в одном непрерывном блоке.
Полное уплотнение подразумевает, что при перемещении активного блока все указатели на пего модифицируются таким образом, чтобы указывать па его новое местоположение. 10.5. Рекомендуемая литература В большей части текстов, посвященных конструированию компиляторов, рассматривается стратегия статического и стекового распределения памяти (см. ссылки в главе 3). Методы управления кучей изучались достаточно широко — см., например, [1011 В [291 представлен краткий обзор методов сбора мусора. В [85] описан метод выполнения анализа процесса компиляции, который позволяет избежать выполнения процедуры сбора мусора во время выполнения. В операционных системах часто предусмотрены некоторые возможности управления памятью, которые пересекаются с аналогичными возможностями языков программирования.
В настоящее время во многие операционные системы встроены сиолемы виртуальной памяши, которые распределяют память в виде сглриниц фиксированного размера или сегменшов переменного размера. Эти возможности иногда оказываются полезными, по обычно опи пе могут полностью заменить уп- 10.6. Задачи и упражнения 479 равление кучей, которое предусмотрено в реализации языка программирования.
Управление памятью при помощи операционной системы — тема многих работ по операционным системам. 10.6. Задачи и упражнения 1. 2. 3. 4. Проанализируйте методы управления памятью, применяемые в доступных вам реализациях языков. Рассмотрите различные элементы, которые должны быть представлены в памяти во время выполнения программы (перечисленныее в разделе 1О 1).
Имеются ли какие либо другие крупные структуры, которые требуют представления в памяти, помимо перечисленных в разделе 10.1? Существует альтернативный способ сбора мусора, в котором используются две области памяти. Во время первой фазы сбора мусора, маркировки, каждый объект, на который имеется ссылка, копируется в голову второй области. Таким образом, как только все активные узлы помечены, сбор мусора можно считать выполненным.
Теперь распределение памяти осуществляется из второй области. Когда эта область заполняется, фаза маркировки копирует активные элементы снова в первую область. Сравните этот алгоритм с двухпроходным алгоритмом (маркировка-сбор), описанным в разделе 10А.2. Проанализируйте элементарные операции языка, который вам хорошо знаком. Какие операции требуют выделения или освобождения памяти? Всегда ли используются блоки памяти одного размера или иногда требуются блоки переменных размеров? Когда происходит выделение и освобождение памяти — только при входе и выходе из подпрограмм или в произвольных точках во время выполнения? Что можно сказать о структурах управления, используемых в данной реализации языка, на основании общей модели выделения и освобождения памяти? Можете ли вы доказать, что требуется куча с переменным или, напротив, с фиксированным размером элементов? Можно ли доказать, что достаточно только центрального стека? Как показано на рис, 9.3, б, в большинстве реализаций языка Рааса! используется единый блок памяти как для центрального стека, так и для кучи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
