Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 71
Текст из файла (страница 71)
Впрочем, метод надгробий был оценен вне области языков программирования. Этот метод широко используется системой программного обеспечения компьютеров Мас1п1оз1з для обнаружения разыменований висячих указателей и для содействия повторному размещению в памяти динамически распределяемых ячеек памяти. Глава 5. Тины данных а) без нспспьжжаннн нал~робнй 61 с использованием мявяобнй Рис.
э. 72. Ресмнзиция динатгческит иере ченнык г исноль ювиннеч ля;робий и без пик Альтернативой для решения проблемы висячих указателей является метод замков и :.;ючей, использованный а реализации компилятора 1.1%-разса1 (Г)зйег апд ЕеВ1апс. 1977, 980). В этом компиляторе значения указателей прелставляются упорядоченными пара' ц 1ключ, алрос), в которых ключом является целое число.
Объем памяти, выделяемой . з динамическую переменную. предусматривает хранение собственно переменной и - .ейкн заголовка. вмегцающей целочисленное запирающее значение (" замок" ). При разь ешении динамической переменной в памяти создается запирающее значение. которое ".вмещается как в ячсйлу замка динамической переменной, так ц в ячейку ключа указателя. которому при вызове устанавливается атрибут печ. При каждом обращении к разыченованному указателю кчючевое значение указателя сравнивается с запирающим зна- :ением динамической переменной. Если они совпадают, то поступ к переменной разрешен, в противном случае обращение интерпретируется как ошибка периода выполнения.
Любое копирование значения указателя должно копировать и значение ключа. Следовательно, на данную динамическую переменную может ссылаться любое число указателей Как только оператор б' врезе удаляет дцналшчеслую перел~сивую из памяти. ее запирающее значение очищается и устанавливается равным значению. принятоьгу лля недопустимой операции. У всех остальных указателей. не перечисленных прп выполнении оператора с) х яро ае, значение адресов не изменяется. но при разыменовании такого у каззтеля его ключевое значение уже не булет соответствовать замкь, вследствие чего доступ к улаленной переменной разрешен не будет.
Как указывалось ранее. язык эата не содержит явной операции удачения из линамической памяти, поэтому ссылки этого языка никогда не могут становиться висячими. 265 5.10. Указатели 5. 10. 10.3. Управление динамической памятью Управление диачпческой памятью может оказаться очень сложным процессом, производимым прп выполнении программы. Мы рассмотрим этот процесс в двух ситуациях: когда при размещении н удачензззз переменных из динамической памяти используются ячейки постоянного размера, и когда используются ячейки переменного размера. Поскольку основательный анализ этих процессов и связанных с ними проблем относится скорее к вопро.ам реализации. чем к вопросам разработки языка, то наше обе)ждение будет кратким и далеко не всеобъемлющим.
Ячейки ззисзззонззззого рлзззера. Простейшая ситуация: при размещении и удалении переменных из динамической памяти используются ячейки постоянного размера. Для простоты будем считать. что кажлая ячейка содержит указатель. Описанная ситуация соответств) ет многим реачизацияьз языка ЫБР.
разработчики которого первыми столкнулись с серьезными проблемами. связанными с динамическим размещением переменных в памяти. Все программы и большинство данных языка !.(БР состоят из ячеек, соединенных в связные списки. Мы не будем рассматривать некоторые связанные с динамической памятью процессы управления строками, а сконцентрируем наше внимание собственно на динамической памяти. В динамической памяти. имеющей ячейки постоянного размера, все доступные ячейки связаны вместе с помощью указателей ячеек, образуя список доступной памяти.
Размещение в памяти заключается в простом получении по мере необходимости требуемого числа ячеек из этого списка. Удаление же из памяти несколько сложнее. Основная проблема. яозникаюшая при удачении из памяти, расслзатривалась в разделе 5.(0.4 в связи с рассмотрением процедуры б' врало языка Разса!. На динамическую переменную могут ссылаться несколько указателей. поэтому можно определить момент.
когда переменная перестает использоваться в программе. Тот факт. что олин из указателей открепляется от ячейки. еше не значит. что ячейка становится мусором: мозуг существовать еше несколько у казателей, ссылающихся на ланную ячейку. В языке Е(БР несколько часто употребляемых операций создают набор ячеек, доступ к которым из программы невозможен. и которые. как следствие, не могут быть освобождены (возвращены в список доступной памяти). Одной из основных целей, стоявших перед разработчиками языка (.(БР, было обеспечить освобождение неиспользуемой памяти системой поддержки выполнения программ, а не программистом.
Эта цель порошша следующий основной вопрос разработки: когла должно производиться удаление из памяти? Существует два различных, и в некотором смысле противоположных. процесса освобождения памяти, занятой мусором: подсчет ссылок, при котором освобождение неиспользуемых ячеек происходит при их возникновении, и сборка мусора, при которой освобождение памяти происходит только, когда доступная память будет, исчерпана.
Другими названиями этих методов являются энергичный подход (еадег арргоас!з) и ленивый подход (!азу арргоас(з), соответственно. При использовании метода подсчета ссылок (ге(егепсе соцпгег тег(зоз!) в каждую ячейку памяти помещается счетчик, содержащий число указателей, ссылающихся в данный момент на зту ячейку. При откреплении указателя от ячейки значение счетчика уменьшается и одновременно проверяется. ни равен ли он нулю.
Если счетчик достигает ззулево~ о значения, то в программе уже не существует указателей. ссылающихся на данн)ю ячейлу. следовательно, она стала мусором и может возвращаться в список доступной памяти. 266 Глава 5. Типы данных ззествуют три различные проблемы, связанные с методом подсчета ссылок. Во. -: .. з. если ячейки памяти имеют относительно небольшой размер. то на все счетчики —.сб>ется значительный объем памяти. Во-вторых. для эксплуатации значений счет:". счевпдно, требуется затратить некоторое время выполнения программы.
При ка- .. ° »зменении значения указателя должны меняться значения лвух счетчиков: счетчик. :.-кашийся в ячейке, на которую ссылался >казатель, должен уменьшить свое значе. ча единицу. а счетчик ячейки, на которую стал ссылаться указатель. должен увели;вое значение на единицу. В языке. подобном (.!5Р, в котором практически каждое -зпе сопровождается изменениел~ указателей. описанные процессы будут занимать -»тельную часть всего времени выполнения программы. Разумеется, если указатели : -= от свои значения нечасто.
то такая ситуация не представляет собой проблемы. Тре. -: лроблема возникает, если набор ячеек связан циклично. и заключается в том, что -..-ение счетчика ссылок на кажа>ю ячейку в кольцевом списке не цельнее ), и мо пре:.ств>ет перемещению ячейки в список доступной памяти. Решение последней пробле. можно найти в книге Фрилмана и Вайса (Гпедшап апд (ч')зе. )979). О новной альтернативой методу подсчета ссылок является метод сборки мусора э-.Ьайс сойесбоп), при котором система поддержки исполнения программ распределяет ;.кп памяти и открепляет от них указатели по требованию.
не заботясь прп этом об .з. оождении памяти (позволяя мусору накапливаться). Как только все лоступное про. —.знство исчерпается, включается процесс сборки мусора. очищающий всю кучу от муга Для облегчения этого процесса в каждой ячейке памяти есть особый индикаторный -. пли поле, используемые алгоритмом сборки. Сам процесс сборки проходит в три этапа. Вначале все ячейки памяти с помощью ин: ~зторов помечаются, как содержащие мусор.
Разумеется, на самом деле это справед"ьо только лля некоторых из них. Затем прослеживаются все указатели программы, и :-елки, на которые они ссылаются, помечаются как используемые. После этого наступа- .-. очередь третьего этапа: все ячейки линамической памяти, не помеченные на втором '-апе как используемые, возвращаются в список доступной памяти. Чтобы пояснить особенности алгоритмов маркировки ячеек.
используемых в данный ' эчент, ниже приводится простой пример. Мы предполагали, что все динамические перс- .".нные (или ячейки динамической памяти) состоят нз информационной части. метки ай : двух указателей 111п)с и г11л)с. Эти ячейки используются для создания ориентирован-, го графа, имеющего не более двух ребер, выходящих из каждого узла. Алгоритм марки: вки прохолит по остовным деревьям графа, помечая все найденные ячейки. Отметим. что ащ алгоритм. как и другие ачгоритмы перемещения по дереву, использует рекурсию.
гог каждого указателя г с(о маг)с(г) ргооес)иге жагМ(ргг) хй рсг <> пи11 Ваап дг' р г".га9 не отмечен ц)эеп установить ргг".га9 взаг)г(рГг".111п)с) маг)г (ргг". г11п1) а йй. еЫ дг 26У 5.10. Указатели Пример выполнения данной процедуры для конкретного графа приведен на рис. 5.13. Отметим, что недостатком этого простого алгоритма маркировки является использование значительного объема памяти (для стека, поддерживающего рекурсию). Шорром и Уейтом (БсЬоп апд Майе, 1967) был разработан процесс маркировки, не требующий дополнительной стековой памяти. Их метод заключается в перестановке указателей в обратном порядке при прохождении связных структур, В таком случае при достижении конца всего списка процесс может проследовать за указателями к выходу из структуры.
зг к Штрикоааннмми линиями показан порняок маркировки узлов Рис. 5.13. Пример выполнения атгоритыожоркировки Самую серьезную проблему, связанную со сборкой мусора, можно сформулировать следующим образом: когда она более всего необходима, она работает хуже всего. Более всего этот процесс нужен, когда программе действительно требуется большинство ячеек динамической памяти. В этом случае сборка мусора занимает значительное время, поскольку нужно просмотреть большинство ячеек и пометить их как полезные. Однако в этолз же случае процессу доступно только небольшое число ячеек, которые можно поместить в список доступной памяти.
Мало того. существуют еше и затраты на дополнительную память для меток ячеек (для которых требуется всего по одному биту), при этом время сборки лзусора включается во время выполнения программы. Впрочем, эти проблемы не так уж серьезны. Во-первых, в большинстве современных компьютеров объем памяти значителен; во-вторых, все большие компьютеры используют виртуальную память, что еше больше увеличивает обьем доступной памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
