AOP_Tom1 (1021736), страница 174
Текст из файла (страница 174)
Ясно, что ситуации (2)-(4) здесь встретиться не могут; единственный реальный эф- бэект от такого распределения памяти заключается в тенденции к удлинению поиска по сравнению с упр. 12, а иногда в том, что К будет меньше, чем с, хотя реально будет суще- ствовать доступный блок, предшествующий данному, о котором нам ничего не известно. (Имеется альтернативный вариант, при котором слияние блоков выносится из вну- треннего цикла АЗ и выполняется только на шаге А4 перед окончательным выделением памяти или во внутреннем цикле, если иначе алгоритм завершится неудачно. Такой аль- тернативный вариант требует модельного изучения для того, чтобы установить, имеются ли у него какие-либо преимущества.) [Этот метод с небольшими усовершенствованиями, как было доказано, вполне удовле- творителен дли реализации ТЕХ и ЫЕТНРОЫТ.
См. 2Ез(: Тйе РгоВгаш (Ас)сйзоп-)1)н!еу. 1986), (~125.] 20. Когда обнаруживается свободный двойник, при выполнении цикла слияния необходимо удалить блок из списка АЧА1! [А], однако неизвестно, какие связи следует обновить. Для получения ответа на этот вопрос можно (!) выполнить длинный поиск или (й) сделать список двусвязным. 21. Если и = 2~п, где 1 < а < 2, а„равно 2зьы(о — 1) + -', а Ь«равно 2ы 'оз + 2ь ~а. Отношение а«/Б«для больших и, по сути, равно величине 4(а — 1~)/а~, которая принимает минимальное значение К при п = 1 и 2 и максимальное значение з при и = 1з.
А з 1 Так что а«/Б«не имеет предела, колеблясь между этими двуми крайними значениями. Методы усреднения из раздела 4.2.4, однако, дают нам среднее отношение, равное 4()п2) 'Л (а — з)4п/а = (!п2) ' = 1.44. 22. Для этой идеи необходимо поле ТАС в нескольких словах блока из 11 слов, а не только в первом слове. Она работоспособна, если можно выделить дополнительные биты ТАС, и, скорее всего, подходит, в первую очередь, для аппаратной реализации. 23. 011011110100; 0110П100000.
24. Это привнесет ошибку в программу; можно оказаться на шаге Б1 при ТАС(0) = 1, поскольку из шага Б2 можно вернуться к шагу Б1. Для работоспособности программы . необходимо на шаге Б2 добавить «ТАС(1) г — О" после «Е с — Р". (Впрочем, проще считать, что ТАС(2 ) = О.) 26. Идея абсолютно верна (критика не всегда должна быть только отрицательной). Заголовки списков АЧА11[А] могут быть обрезаны для и < Й < пИ приведенные в тексте раздела алгоритмы могут использоваться с заменой га на и на шагах К1 и Б1.
Начальные условия (13) и (14) должны быть изменены таким образом, чтобы указывалось 2~ " блоков размером 2", а не один блок размером 2 26. Используя двоичное представление И, можно легко изменить начальные условия (13) и (14) так, чтобы вся память была разделена на блоки, размеры которых представляют собой степени двойки, с блоками в порядке убывания размеров. Н алгоритме Б ТАС(Р) должен рассматриваться как 0 всякий раз, когда Р > И вЂ” 2 . 27. гП ш А, г]2 ш 1, г13 ш 1 — й, г14 ш 1, 100(АЧА11[1] ) ж АЧА11 + 1. Предполагаем, что имеется вспомогательная таблица ТИО [1] = 2~, хранящаяся в ячейках ТЧО + 1, для 0 < 1 < гл, Предположим далее, что «+«и "—" представляют де. скрипторы 0 и 1 и что ТАС(ьОС(АЧА1ь[1]) ) = "-", но в качестве признака конца памяти ТАС(10С(АЧА11 [пг+1])) = «+".
00 КЧА1 ЕСО Б:Б 01 ТАС ЕСО О:О 03 11ИКР ЕСО 1:2 08 11ИКВ ЕСО 3:4 04 Т( ИКР ЕСО О:2 05 Е1 101 К 1 21. Поиск блока 00 ЕИТ2 0,1 1 1<-)г. 07 ЕИТЗ О 1 ОВ 104 АЧА11,2(11МКР) 1 09 1Н ЕМТБ АЧА)!.,2 1+В 10 ВЕСЕ 0,4 1+Я 11 1БИ2 М2 1+ В Переход при АЧА11Р[1] ЧА 10С(АЧА11Ц]). 12 1ИС2 1 В Увеличение 1. 1Я 1ИСЗ 1 11 Ц 104И АЧА11,2(ТСИКР) Я 10 14ИИ 1В В 1<ту 10 1МР ОЧЕКРСОЧ 1 22. У аление нз списка. 1 АЧА11Р[1) с в 11ИКР(1), 1 1 11МКВ(1) +- 10С(АУА11[1З). 1 ТАСИ.) +- О.
1 ЙЗ. Т еб ется аз е ение? 1.1ИКРИ.1ИКВ(Р) ) +- 1.1МКР(Р) 11МКВ(11МКР(Р)) +- 1.1МКВ(Р) Увеличение 1с. 17 52 105 0,4(11МКР) 18 5ТБ АЧА11,2(11ИКР) 19 ЕМТА АЧАП.,2 50 БТА 0,5(11ИКВ) 91 БТЗ 0,4(ТАС) ЕЕ ЕЗ 131 ООМЕ 58 К4 ОЕСЗ 1 с 84 ОЕС2 1 17 Уменьшение 1. 58 105 ТМО,2 1( г15 = Р. Яб 1МСБ 0,4 В Рс-1+2с. 57 ЕММА АЧАП.,2 В 88 ЯТА 0,5(71МКР) В ТАС(Р) с- 1, 11ИКР(Р) с- 10С(АУА11[1З). 89 ЯТА 0,5(11МКВ) В 11МКВ(Р) с в 100(АЧА11[1З ). 80 ЯТБ АЧАП.,2И.1ИКР) В АЧАП.9[12 с- Р. 81 БТ5 АЧА1ь.2(ь1МКВ) В АЧА115[1) с- Р.
85 5Т2 0,5(КЧА1) В КЧАБ(Р) +- 1. 88 13Р 54 1( Переход к шагу [[3. 84 ООМЕ ! 25. гП ш )с, г15 ш Р, г[4 шб; полагаем ТАС(2 ) = "+". 01 51 104 1 ЗЕ Сноб еи лн йиик? 05 101 К 1 08 15 ЕМТА 0,4 1+8 01 105 ТЧО, 1 1+ 8 гА с- двойника(1). 06 ЯТА ТБИР 1+8 06 105 ТЕИР 1+8 Рс — гА, 07 ЫА 0,5 1+8 08 ЗАКИ 53 1 + 8 Переход при ТАС(Р) = О. 09 СИР1 0.5(КУАС) В+8 10 ЛИЕ 53 В+ 8 Переход при КЧАБ(Р) и'.
А. 11 52 102 0.5(11МКР) 8 82 Объ инение с войну м. 15 103 0,5И.1МКВ) 8 18 ЯТЗ 0,2(11ИКР) 8 Ц ЯТ2 0,3(11ИКВ) 8 15 1МС1 1 8 16 СИР4 ТЕИР 8 17 11 1В 8 18 ЕМТ4 0,5 А Если 1. ) Р, установить 1. с — Р. 19 ЛИР 1В А 90 53 102 АЧАП..1(11МКР) ! 53. Поме ение в список. 81 ЕММА АУА11,1 1 88 БТА 0,4(0:4) 1 ТАСЮ ь- 1, 11МКВ(1) +- 10С(АЧА11[А)). 58 ЯТ2 0,4(11МКР) 1 1.1МКРИ.) +- АЧА1ЬР[/с). 58 ЯТ1 0.4(КЧА1) 1 КЧА1.И.) +- )с. 85 5Т4 0,2(11МКВ) 1 11ИКВ(АЧАТЙР[)с)) '; 1' Яб ЯТ4 АЧА11,1(11ИКР) 1 АЧА11[А) с- П $ 25. Может, но только за счет некоторого поиска или (что предпочтительнее) дополни- тельной каким-либо образом упакованной таблицы битов ТАС.
(Заманчиво объединить двойников не в алгоритме Б, а только в алгоритме Н, если нет достаточно большого блока, чтобы отвечать запросу. Но, вероятно, это вызовет повышенную фрагментацию памяти.) 31. См. [)атЫ [ . Нише)1, 61СОМР 6 (1977), 607-621. ЗЗ. С1. [Очистка полей связей.] Установить Р +- 1 и повторять операции 1.1ИК(Р) е- Л н Р е- Р+ 512Е(Р) до тех пор, пока не будет выполнено условие Р = АЧА1!.. (Таким образом поля Ь1МК в первых словах каждого узла устанавливаются равными Л. В большинстве случаев можно считать, что этот шаг не является необходимым, поскольку поле Ь1ИК(Р) устанавливается равным Л на шаге С9 ниже, а также может быть сброшена распределителем памяти.) СЗ.[Инициализация фазы маркировки.] Установить ТОР е- ОБЕ, 1.1МК(ТОР) +- АЧА1Ь, 1.1ИК(АЧА1Ь) +- й. (ТОР указывает на вершину стека, как в алгоритме 2.3.51).) СЗ.[Поднятие стека.] Установить Р +- ТОР, ТОР с в !.1МК(ТОР).
Если ТОР = Л, перейти к шагу С5. С4. [Поместить новые связи в стек.] Для 1 < А < Т(Р) выполнить следующие операции: установить Ц е- ЬТИК(Р + /с): затем, если Ц ф Л и !.1ИК(Ц) = Л, установить 1.1МК(Ц) +- ТОР, ТОР ь- Ц,после чего вернуться к шагу СЗ. С5.[Инициализация следующей фазы.] (Теперь Р = АЧАТЬ и фаза лгаркировки завершена, так что первое слово каждого доступного узла имеет ненулевую связь 1.1МК. Цель наших последующих действий — объединение смежных недоступных узлов для ускорения последующих шагов и назначение новых адресов доступным узлам.) Установить Ц с — 1, Ь1МК(АЧА1Ь) ь- Ц, 512Е(АЧА11.) с — О, Р с- 1. (Ячейка АЧА1!. используется в качестве ограничителя для указания конца цикла в последующих фазах.) Сб.
[Присвоение новых адресов.] Если !.1МК(Р) = й, перейти к шагу 07. Егли условие не соблюдено, то при 512Е(Р) = 0 перейти к свату С8, иначе — установить 1 1МК(Р) +- Ц, Ц +- Ц + 312Е (Р), Р +- Р + 512Е (Р) и повторить этот шаг. СТ. [Слияние свободных областей ] Если Ь1МК(Р+ 512Е(Р)) = Л, увеличить 312Е(Р) на 312Е(Р + 312Е(Р) ) и повторить этот шаг. Иначе — установить Р +- Р + 812Е(Р) и вернуться к шагу Сб.
СБ. [Преобразование всех связей.] (Теперь в поле ЬТИК первого слова каждого доступного узла содержится адрес, куда будет перемещен узел.) Установить ОБЕ с- !.1МК(ОБЕ) и АЧ АТЬ +- Ц. Затем установить Р +- 1 и повторять следующие операции до тех пор, пока не будет выполнено условие 512Е(Р) = 0; если 1.1МК(Р) ,-А Л, установить !.1МК(Ц) +- Ь1ИК(11МК(Ц)) для всех Ц, таких, что Р < Ц < Р+ Т(Р) и Ь1МК(Ц) ,-А Л; затем независимо от значения Ь1МК(Р) установить Р +- Р + 512Е(Р) . С9. [Перемещение.] Установить Р +- 1 и повторять следующие операции до тех пор, пока не будет выполнено условие 512Е(Р) = О установить Ц е- Ь1МК(Р) и, если Ц ф Л, установить Ь1ИК(Р) < — Л и МООЕЬЦ) е- МООЕ(Р); зател~ независимо от того, справедливо ли условие Ц = Л, установить Р с- Р+312Е(Р).
(Операция МОРЕМ) +- МООЕ(Р) приводит к перемещению 912Е(Р) слов; всегда Ц < Р, так что перемещение этих слов из меньших адресов в большие безопасно.) 3 [Этот метод называется "сборщик мусора в Ь!БР 2". Другой интересный метод, не требующий наличия поля Ь1МК в начале узла, может основываться на идее связывания всех указателей на каждый узел. См. ! агэ-Егсй Тйоге!й, В1Т 16 (1976), 426.441; В.
В. К. Нежат авс! А. Р. МсСавп, БоГсиаге Ргасбсе Аг Ехр. 7 (1977), 95 — 113; Р. Ьос)юуоос) Магна, САС)И 21 (1978), 662-665, 22 (1979), 571; Н. В. М. 3оп)сегэ, ГлГ. Ргос. ЬеСсегэ 9 (1979), 26-30; 1..!. МагНп, САСМ 25 (1982), 571 — 581; Г. Ьос(гшоос( Магна, ГвГ. Раас.
Ьессегэ 15 (1982), 139 — 142, 16 (1983), 215. Другие методы можно найти в работах В К. На<Ыов авг( Ъ)с. ИЬ ЧЧа!се, Сотр. Х 10 (1967), 162-165; В. Ъреббгесс, Сотр Х 15 (1972), 204-208; Ы А. Еаге, ГпГ. Ргос. Ьешегэ 3 (1975), 167-169. Коэн (Собегс) и Никалау (Кко!ап) проанализировали четыре из этих подходов в АСМ Тгалэ. Ргоб. Ьавйпабез апс( Зуэсетз 5 (1983), 532-553.] Р=г11,0 га С4, что 34. Пусть ТО упрощения ша сп г12, Р сп г13, /г = г14, 51ЕЕ(Р) гн г15. Положим также для Л = 0 и 1.1МК(0) ф О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
