9. 6.4. Язык программирования lisp

Язык LISP является наиболее развитым и распространенным языком обработки списков. Идеология и терминология языка в значительной степени повлияла на общепринятые подходы к обработке списков и использовалась и нами в предыдущем изложении.

Все данные в языке представляются в виде списков, структура элемента списка соответствует рис. 6.15. Язык LISP обеспечивает базовые функции обработки списков car, cdr, cons, atom. Также многие вторичные функции реализованы в языке как базовые для повышения их эффективности. Помимо списковых операций в языке обеспечиваются операции для выполнения арифметических, логических операций, отношения, присваивания, ввода-вывода и т.д.

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

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

10. 6.5. Управление динамически выделяемой памятью

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

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

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

В общем случае при распределении памяти должны быть решены следующие вопросы:

• способ учета свободной памяти;

• механизм выделения памяти по запросу;

• обеспечение утилизации освобожденной памяти.

Рассмотрим эти вопросы по порядку. В распоряжении программы обычно имеется адресное пространство, которое может рассматриваться как последовательность ячеек памяти с адресами, линейно возрастающими от 0 до N. Какие-то части адресного пространства обычно заняты системными программами и данными, другие – кодами и статическими данными самой программы, оставшаяся часть доступна для динамического распределения.

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

В некоторых системах программирования выделение памяти автоматизировано полностью: система не только сама определяет адрес выделяемой области памяти, но и момент, когда память должна выделяться. Например, память автоматически выделяется под элементы списков в языке LISP, под символьные строки в языках SNOBOL и REXX.

В других системах программирования – к ним относится большинство универсальных процедурных языков – моменты выделения и освобождения памяти определяются пользователем. Требуется выдать запрос на выделение/освобождение памяти при помощи стандартной подпрограммы – ALLOCATE/FREE в PL/1, malloc/free в C, New/Dispose в PASCAL. Система сама определяет размещение выделяемого блока, и затем функция выделения памяти возвращает его адрес.

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

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

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

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

В методах битовой карты создается «карта памяти» – массив бит, в котором каждый однобитовый элемент соответствует единице доступной памяти и отражает ее состояние: 0 – свободна, 1 – занята. Если считать единицей распределения единицу адресации – байт, то сама карта памяти будет занимать 1/8 часть всей памяти, что делает ее слишком дорогостоящей. Поэтому при применении методов битовой карты обычно единицу распределения делают более крупной, например, 16 байт. Карта, таким образом, отражает состояние каждого 16-байтного кадра. Если карту представить как строку бит, то задача поиска участка памяти для выделения будет сведена к поиску в этой строке подстроки нулей требуемой длины.

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

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

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

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

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

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

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

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

Другой метод – освобождать любой блок, как только он перестает использоваться. Метод обычно реализуется посредством счетчика ссылок, в который записывается, сколько указателей на данный блок имеется в данный момент времени. Когда значение счетчика становится равным 0, соответствующий блок оказывается недоступным и, следовательно, не используемым. Блок возвращается в свободный список.

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

Существуют различные решения проблемы:

• запретить циклические и рекурсивные структуры;

• отмечать циклические структуры флажками, и обрабатывать их особым образом;

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

Практическая эффективность описанных методов зависит от многих параметров, таких как частота запросов, статистическое распределение размеров запрашиваемых блоков, способ использования системы.