Cтраница 3
Вероятно, ни у кого не вызывает сомнения, что висячие ссылки потенциально опаснее мусора. Накопление мусора ведет к истощению пригодной для работы памяти, но висячие ссылки могут вызвать совершенный хаос, поскольку используемая память подвергается случайным изменениям. Конечно, обе эти проблемы взаимосвязаны: висячие ссылки появляются, когда память освобождается слишком быстро, а мусор - когда она слишком долго не освобождается. Если нежелательно или слишком дорого использовать какой-нибудь механизм вроде счетчиков ссылок для устранения сразу обеих проблем, то, очевидно, следует предпочесть присутствие мусора, но избежать висячих ссылок. Лучше вовсе не использовать память повторно, чем использовать ее раньше времени. [31]
Куча необходима, только когда в программе используются переменны или структуры данных с классом памяти BASED или CONTROLLED, которые могут создаваться и уничтожаться в произвольные моменты времени в ходе выполнения блока или подпрограммы, где они описаны. Поскольку использование кучи довольно ограничено, она занимает сравнительно немного места. Управление памятью в куче не вызывает затруднений. Память выделяется и освобождается только с помощью явного использования инструкций ALLOCATE и FREE, и не делается никаких попыток избежать появления мусора и висячих ссылок. Свободная память в куче выделяется в виде блоков переменной длины. Типичная техника управления памятью состоит в поддержании списка свободного пространства, соединяющего вместе все свободные блоки в куче в порядке возрастания адресов памяти. При запросе памяти из списка свободного пространства выделяется первый подходящий или наиболее подходящий блок, а возвращаемые блоки опять включаются в список в соответствующих точках, но перед этим выполняется частичное уплотнение списка путем слияния смежных блоков. Эти методы обсуждаются в разд. [32]
Допуская программиста к управлению памятью, приходится считаться с двумя трудностями: во-первых, на программиста может лечь тяжелое и часто нежелательное бремя; во-вторых, возникает взаимодействие двух механизмов управления, поскольку мы не можем обойтись без системного механизма. Уже простые запросы и освобождения памяти для структур данных, как в ПЛ / I, вероятно, открывают возможность появления мусора и висячих ссылок. [33]
Метод явного возврата мог бы показаться вполне естественным методом утилизации при организации памяти в виде кучи, но, к сожалению, он не всегда применим. Причина этого заключена в двух старых проблемах: проблеме мусора и проблеме висячих ссылок. Первый раз мы обсуждали эти проблемы в гл. Если структура уничтожается ( и занятая ею память освобождается) до разрушения всех путей доступа к этой структуре, то оставшиеся пути доступа становятся висячими ссылками. С другой стороны, если последний путь доступа к структуре уничтожается, а сама структура не уничтожается и память не освобождается, то эта структура становится мусором. Мусором является такой элемент, который пригоден для повторного использования, но не содержится в списке свободного пространства и потому недоступен. [34]
Поскольку при явном возврате, как мы видели, возникает немало проблем, желательно иметь другие методы. В одном из них, называемом сбором мусора, допускается порождение мусора, но не висячих ссылок. Затем, если список свободного пространства исчерпается, вызывается механизм сбора мусора, который находит мусор. Вторая альтернатива, метод счетчиков ссылок, требует явного возврата, но обеспечивает способ проверки числа указателей на данный элемент с тем, чтобы предотвратить образование висячих ссылок. [35]
Висячие ссылки возшп:::: /:, если структура данных уничтожается прежде, чем будут разрушены все пути доступа к этой структуре. Важнейшим источником путей доступа к структурам данных являются ассоциации идентификаторов. Однако висячие ссылки могут образовываться также, если в других структурах существуют указатели на разрушенную структуру; поэтому проблема висячих ссылок не является проблемой только управления данными, а имеет более общее зна чение. [36]
Висячие ссылки могут привести к полному хаосу. При попытке программы изменить с помощью висячей ссылки структуру данных, которая уже уничтожена, может измениться содержимое элемента списка свободного пространства. Если это изменение затронет указатель, связывающий этот элемент со следующим элементом списка свободного пространства, то весь остаток списка свободного пространства, вероятно, превратится в мусор. Что еще хуже, последующие попытки программы распределения памяти воспользоваться указателем в измененном элементе приведут к совершенно непредсказуемым результатам, например в качестве свободного пространства может быть выделена и позднее изменена область внутри выполняемой программы. Аналогичные проблемы возникают в случае, когда перед употреблением висячей ссылки элемент, на который она указывает, был уже перераспределен для других целей. [37]
Правила, регулирующие создание и уничтожение структур данных, связаны с классом памяти, указанным в описании для каждой структуры. Структуры с классом STATIC создаются во время компиляции до начала выполнения и существуют в течение всего времени выполнения программы. Структуры с классом AUTOMATIC создаются при входе в блок и уничтожаются при выходе. Структуры с классами CONTROLLED и BASED создаются путем явного использования во время выполнения программы инструкций ALLOCATE и уничтожаются инструкциями FREE. При неправильном использовании ALLOCATE и FREE могут легко появиться мусор и висячие ссылки. [38]
Висячие ссылки возшп:::: /:, если структура данных уничтожается прежде, чем будут разрушены все пути доступа к этой структуре. Важнейшим источником путей доступа к структурам данных являются ассоциации идентификаторов. Однако висячие ссылки могут образовываться также, если в других структурах существуют указатели на разрушенную структуру; поэтому проблема висячих ссылок не является проблемой только управления данными, а имеет более общее зна чение. [39]
Вероятно, ни у кого не вызывает сомнения, что висячие ссылки потенциально опаснее мусора. Накопление мусора ведет к истощению пригодной для работы памяти, но висячие ссылки могут вызвать совершенный хаос, поскольку используемая память подвергается случайным изменениям. Конечно, обе эти проблемы взаимосвязаны: висячие ссылки появляются, когда память освобождается слишком быстро, а мусор - когда она слишком долго не освобождается. Если нежелательно или слишком дорого использовать какой-нибудь механизм вроде счетчиков ссылок для устранения сразу обеих проблем, то, очевидно, следует предпочесть присутствие мусора, но избежать висячих ссылок. Лучше вовсе не использовать память повторно, чем использовать ее раньше времени. [40]
В общем случае попытка проследить за всеми путями доступа к структуре трудно реализуема и отнимает много вре-мени; поэтому когда для доступа к структуре используется один путь, часто невозможно сказать, единственный ли он. С этим связана главная проблема операций уничтожения. Предположим, что программисту позволено явно указывать, когда следует уничтожить конкретную структуру данных. Он должен указать путь доступа к структуре, и операция уничто-жения может легко уничтожить как путь доступа, так и саму структуру. Однако, если существуют какие-либо другие пути доступа к этой структуре, возникает серьезная ситуация: после уничтожения структуры остаются пути доступа, ведущие к неопределенной области памяти. Такие пути доступа к несуществующим структурам обычно называются висячими ссылками. [41]