AOP_Tom1 (1021736), страница 120
Текст из файла (страница 120)
В алгоритмах А и С можно довольно просто избежать маркировки слов-атомов, пока все слова-не атомы правильно маркированы. Тогда одного прохода по всем данным будет достаточно для маркировки всех слов-атомов. Алгоритм В можно еще проще модифицировать. так как для этого придется всего лишь сохранить слова-атомы вне стека. Почти так же просто можно адаптировать алгоритм Е, хотя, если АЫМК и ВЫМК указывают на данные атомы, потребуется в словах-не атомах ввести другое 1-битовое поле. Обычно это не так А1.1МК[ИАВК] ВВХМК[АТОИ] 6 В11МК[АТОМ] А1.1МК[ИАВК] В11МК[АТОИ] А1 1МК [ИАВК] ВВ1МК[АТОМ] А1.1МК[ИАВК] В11МК[АТОМ] ь[о] . Л[1] .
ь с[О] . [1] . [О] Л -[о] .. [1] -[1] . ь[о] . )[о] . е [О] ][о] . л[о] . с[о] трудно сделать. (Например, если узел состоит из двух слов, младший бит каждого поля связи можно использовать для хранения промежуточной информации.) Хотя время в1 п1олнения алгоритма Е прямо пропорционэлыю количеству маркируемых узлов, константа пропорциональности не так мала, как для алгоритма В. Наиболее быстрый метод сборки мусора основан на сочетании алгоритмов В и Е (подробности приводятся в упр.
5). Попробуем теперь дать количественную оценку эффективности сборки мусора по сравнению с подходом на основе команды "АЧА11 ~ Х', которая использовалась в болыпинстве предыдущих примеров настоящей главы. В каждом из этих случаев можно было бы опустить все особые упоминания о возврате узлов в свободную область памяти и использовать вместо них сборку мусора. (В специализированных приложениях по сравнению с множеством универсальных программ обработки Списков программирование и отладка программ сборки мусора выполняются гораздо сложнее, чем описанных до сих пор методов, и, конечно, для сборки мусора в каждом узле необходимо выделить дополнительный бит. Но в данном случае нас интересует сравнительная скорость выполнения уже готовых и отлаженных программ.) Время выполнения наилучших программ сборки мусора можно представить в виде с1М + сзМ, где с1 и сз — константы, М вЂ” количество маркированных узлов, а М вЂ” общее количество узлов в памяти.
Таким образом, М вЂ” И---это количество найденных свободных узлон, а среднее время, необходимое для возврата одного узла в свободную область памяти, равно (с1М + сзМ)/(М вЂ” М). Пусть М = рМ; тогда это выражение принимает вид (с1р+ сз)/(1 — р). Поэтому, если р = 4, т. е. если память заполнена на три четверти, для возврата в свободную память одного узла потребуется Зсз + 4сз единиц времени. А при заполнении р = „-' соответствующие затраты времени составят всего -с1+ -сз единиц времени. Если не использовать 1 4 з. з.' метод сборки мусора, то количество времени для возврата одного узла в свободную память будет равно некоторой константе сз, а отношение сз/с1 вряд ли будет очень большим. Следовательно, нетрудно сделать вывод о том, насколько неэффективен метод сборки мусора при высокой степени заполнения памяти и соответственно насколько он эффективен при незначительном ее заполнении.
Для многих программ характерно то, что отношение количества маркированных узлов к общему объему памяти р = М/М достаточно малб. Если в таких случаях пул полностью заполняется, то лучп1е всего, наверное, переместить все активные Списки в другой пул такого же размера, используя упомянутый н упр. 10 метод копирования, но не беспокоясь о сохранении содержимого копируемых узлов.
Тогда при заполнении второго пула можно снова переместить данные в первый пул. Благодаря такому методу в оперативной памяти можно одновременно хранить гораздо больше данных, поскольку поля связи указывали бы на соседние узлы. Более того, не потребовалось бы применять фазу маркировки, а распределение памяти было бы просто последовательным. Сборку мусора можно использовать совместно с другими методами возврата ячеек в свободную память. Они не являются взаимно исключающими, и в некоторых системах применяются как метод счетчика ссылок так и метод сборки мусора, причем программист может удалять узлы даже явным образом. Основная идея в этом случае заключается в применении метода сборки мусора только "в крайнем случае", когда все другие методы возврата неиспользуемых ячеек памяти уже не помогают.
Хорошо продуманная система, в которой реализована эта идея и включен механизм отложенных операций со счетчиками ссылок для достижения повышенной эффективности, предложена Л. П. Дойчем (Ь. Р. ПецгвсЬ) и Д. Е Бобровым (1У. С. ВоЬгош) [см. САСМ 19 (1976), 522 — 526]. Кроме того, для Списков можно использовать последовательное представление, которое позволяет сэкономить пространство, занимаемое многими полями связи, за счет более сложного управления памятью.
[См. Х. Е, 1У(вешап апг[ д. О. Н)1ев, Согпр. Х 10 (1968), 338-343:, 1У. 1. Напвеп, САСМ 12 (1969), 499-506; С. 3. СЬепеу, САСМ 13 (1970), 677-678.[ Даниэль П. Фридман (!уап!е! Р. Рг!ейпап) и Дэвид С. Вайс (1Уав!г[ 8. %!ве) обнаружили, что метод счетчика ссылок можно успешно применять даже в тех случаях, когда Списки указывают на самих себя, если только не учитывать при подсчете ссылок некоторые поля связи [1пГ. Ргос. Ьеггегв 8 (1979), 41 — 45[. В настоящее время накоплено огромное количество усовершенствованных вариантов алгоритмов сборки мусора.
Подробный анализ всей научной литературы на эту тему, опубликованной до 1981 года, вместе с комментариями о дополнительных затратах на операции доступа к памяти при перекачках страниц памяти между оперативной и дисковой памятью можно найти в обзоре Ж. Коэна (дасг!псв СоЬеп) [Сотрийпд 8оггеув 13 (1981), 341 — 367[. Описанные здесь методы сборки мусора не совсем подходят для "интерактивныхк приложений (чгеа! Гппеч арр1!сат!опв), в которых все основные операции работы со Списками должны выполняться очень быстро. Даже если сборка мусора осуществляется не часто, все равно придется затратить довольно большую часть времени вычислений.
В упр. 12 рассмотрены некоторые способы реализации метода сборки мусора в интерактивных приложениях. Печально, что в наши лнн осталось тзк мало бесполезной информации. — ОСКАР УАЙЛЬД (О5САР 'чУ!ЬОЕ) (1894) УПРАЖНЕНИЯ 1. [М21! В разделе 2.3.4 было показано, что "дерево" — это особый случай "классического" математического понятия "ориентированный граф". Можно ли описать Списки ив основе терминологии теории графов? 2.
[20] В разделе 2.3.1 показано, что обход дерева можно упроститгч используя прошитое представление данных внутри компьютера. Можно ли аналогичным образом прошить структуру Списка? 3. [М2б! Докажите корректность алгоритма Е. [Укаэаниа См. доказательство алгоритма 2 3.1Т.! 4. [22! Создайте программу дли компьютера И1Х, которая реъчизует шчгоритм Е при условии, что узлы представлены одним словом компьютера И1Х, причем маркировочный бит ИАКК находится в паче (О: О) [ "+" = О, "-" = Ц, узел-атом АТОИ вЂ” в поле (1: 1), А1.1ИК-- в паче (2:3), Вь1ИК вЂ” в поле (4:5), а А = О.
Определите также время выполнения этой программы иа основе соответствующих параметров. (При работе с компьютером И1Х не так уж просто определить, что содержится в ячейке памяти: — О или +О. Поэтому данная особенность может существенным образом повлиять на вашу программу.) б. [20] (Задача Шорра и Вэйта.) Предложите алгоритм маркировки, который представляет собой комбинацию алгоритмов В и Е со следующими свойствами. Остаются в силе допущения алгоритма Е в оКношении полей внутри узлов и т. д. Но вспомогательный стек БТАСКШ, БТАСК(21, ..., БТАСК(М) используется так же, как в алгоритме В, и механизм алгоритма Е применяется только при полном заполнении стека. 6.
[00] При осуществлении количественной оценки в конце данного раздела сказано, что время выполнения программы сборки мусора приблизительно равно с~И + сзи единицам. На каком основании в эту оценку включен член "сзИ"? 7. [04] (Задача Р. В. Флойда (К. 1Ч, Г!оуб).) Создайте алгоритм маркировки, в котором так же, как и в алгоритме Е, не используется вспомогательный стек, за исключением того, что (!) он имеет гораздо более сложное управление, поскольку в каждом узле содержатся полн МАКК, Аь1НК и Вь1НК, а поля АТОИ, которые помогают упростить управление, в нем отсутствуют: (И) он имеет более простое управление, так как маркирует только бинарное дерево, а не Список общего типа. В этом случае связи АСТМЕ и ВЕ1МК являются обычными связями ШМК и Вь1НК бинарного дерева.
В. [07] (Задача Л. П. Дейча (1.. Р. ПеогэсЬ).) Создайте алгоритм маркировки, в котором так же, как в алгоритмах П и Е, не используется вспомогательная память для стека. Однако измените этот метод так, чтобы его можно было применять для узлов переменного размера и для переменного количества указателей в следующем формате. В первом слове узла находятся два поля: МАКК и Б12Е; поле МАЕК имеет тот же смысл, что и в алгоритме Е, а поле Б12Е содержит число и > О. Это значит, что вслед за первым словом последовательно располагается и слов, каждое нз которых содержит поле ИАНК (которое равно нулю и должно оставаться таким) н поле Ь1МК (которое равно Л или указывает на первое слово другого узла). Например, узел с тремя указателями будет содержать четыре последовательно расположенных слова.
Первое слово Второе слово Третье слово Четвертое слово (будет установлено равным 1) ьТМК = первый указатель ь1МК = второй указатель ьТНК = третий указатель Б12Е = 3 МАКК = О МАКК = О МАКК = О МАКК = О Созданный вами алгоритм должен маркировать все узлы, к которым можно добраться из заданного узла РО. 9. [ЕБ] (Задача Д. Эдвардса (1). Ебзтаг<Ь).) Создайте алгоритм для второй фазы сборки мусора, который "упаковывает память" в указанном ниже смысле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
