AOP_Tom1 (1021736), страница 130
Текст из файла (страница 130)
Змачит, начинать работу с такого размера блоков -- пустая трата времени, как и объединение в алгоритме Б блоков, образующих в результате свободный блок размерам, превосходящим 2"". ь 20. ]01] Поясните, каким образом можно использовать систему двойников для динамического выделения памяти г адресами от 0 до М вЂ” 1 даже в случае, когда М ме имеет вид 2 как требуется в тексте раздела, 27. ]34] Напишите М1Х-программу для алгоритма В и определите время ее работы.
23. ]35] Напишите М1Х-программу для алгоритма Я и определите время ее рабаты, считая М1Х двоичным компьютером с новой операцией ХОВ, с помощью обозначений из раздела 1.3.1 определяемой так: "С = 5, г = 5. Для каждого бита в ячейке М, равного 1, соответствующий бит в регистре А дополняется (изменяется г 0 ме 1 или с 1 на О); знак гА остается неизменным, время выполмемия равно 2и" 20, [УО] Мажет ли система двойммков работать без бита дескриптора в каждом выделеимам блоке? 30.
]М45] Проанализируйте среднее поведение алгоритмов В и Б, задавая обоснованные распределения для последовательности запросов иа выделемие памяти. 31. (М40] Можно ли построить аналогичную системе двойников систему динамического распределения намети, основанную на последовательности чисел Фибомаччи, а ме ма степенях двойки? (Таким образом, можно начать с Г,„свободных глав и разделить доступные блоки из Гь слов на два двойника длиной рь ~ и Ге е соответственно.) 32. (НМ47] Определите 1пп, а„, если ом существует, где а„— среднее змачемие 1„ в случайной паследовательмости, определенной таким образам.
Дины значения ее для 1 < й ( и; Ел равновероятна выбирается из множества значений (1, 2,..., ул], где уе ( 1 шш(10000> з ((х 1 1) Я вЂ” е 2) ° ~(Н (и 1)))] и )(х) = к при х > 0 и г(х) = сс при х ( О. ]Приме шиве. Некоторые аграмичеммые змпирические тесты показывают, что ол может быть примерно равна 14, на, вероятно, зто ме слишком точное значение.) ь 33. ]УУ] (Сборка мусоре и Уплашнеиме.) Положим, чта ячейки памяти 1, 2,..., ХКХ11 — 1 используются в качестве пула памяти для узлов перемеммага размера, имеющих следующий вид: первое слово МОРЕ(Р) содержит поля 312Е(Р) = количества слав е МРОЕ(Р); Т(Р) = количество полей связей в МОРЕ(Р); Т(Р) ( 312Е(Р); ь)МК(Р) = специальное пале связи для испальзовамиятолько при сборке мусора.
В памяти за МОРЕ(Р) следует МОРЕ(Р+ 3123(Р)). Предположим, чта в МОРЕ(Р) в качестве связей с другими узлами используются (1МК(Р+ 1), 01МК(Р+ 2),, Е!МК(Р+ Т(Р)) и каждое иэ этих полей связей представляет собой либо Л, либо адрес первого слава другого узла.
И наконец, предположим, чта в программе имеется еще одна переменная связи с именем ОБЕ, которая указывает на один из узлов. Разработайте алгоритм, который (!) определяет все узлы, прямо или косвенно доступные из переменной ОБЕ, (И) перемещает эти узлы в ячейки памяти ат 1 до К вЂ” 1 для некоторого К, изменяя все связи так, чтобы сохранились структурные отношения, и (!Й) устанавливает АЧАП. <- К. Например, рассмотрим следующее содержимое памяти, где 1МУО (1) обозначает содержимое ячейки 1, исключая ПИК(1): АЧА11 = 11, ОБЕ = 3.
1: 812Е=2,Т=1 2: !.1ИК = 6, 1ИРО ж А 3: Бтге=з,т=1 4: 1.1МК = 8, ТИБО = В 5: СОМТЕМТБ = С 6: 312Е=2,Тж0 7: сОитеи18 = 1) 8: ЯТЕМ ж 3, т = 2 9: !.1ИК = 8, 1МРО = Е 10; 1.1МК = 3, 1МУО = Р Ваш алгоритм должен преобразовать эти данные в 1: Бтге=з,т=1 4: 31ге=З,т=2 2: 1.1МК = 4, 1ИРО = В 5; 51ИК=4,1МРО=Е 3: СОМТЕМТБ = С 6: !.1МК = 1, 1МУО = Р АЧА11.
= 7, ОБЕ = 1. 34. [20[ Напишите И11-программу для алгоритма из упр. 33 и определите время ее рабо- ты. 35. [22) Сопоставьте методы динамического распределения памяти из этого раздела с технологиями последовательных списков переменного размера, рассмотренными в конце раздела 2.2.2. ь 36. [20) В некоторой закусочной в Голливуде (Калифорния) имеется 23 места для посетителей, которые приходят поодиночке или вдвоем. Хозяйка закусочной показывает посетитеэшм их места Докажите, что она всегда сможет рассадить посетителей, не разбивая пары, если одновременно в закусочной будет находиться не более 16 посетителей, а одиночки не сидят на местах 2, 5, 8, ..., 20 (предполагается, что каждая пришедшая пара уходит вместе). ° 37. [20] Продолжая упр. 36, докажите, чта хозяйка не всегда может так удачно рассадить посетителей, если в закусочной только 22 места, Независимо ат используемой ею стратегии может возникнуть ситуация, когда в закусочной будет находиться всего 14 посетителей, но для вошедшей пары не найдется двух соседних пустых мест.
38. [М21) (Д. М. Робсон (1. М. НаЬвоп).) Задача о закусочной, изложенная в упр. 36 и 37, может быть обобщена для определения производительности в наихудшем случае для любого алгоритма динамического выделения памяти, который никогда пе перемещает выделенные блоки. Пусть Ю(и,т) — наименьшее количество памяти, такое, что любая серия запросов на выделение и освобождение может быть выаолнена без переполнения в случае, когда все размеры блоков не превышают т, а общее количество затребованной памяти не превосходит п. В упр.
36 и 37 доказана, что )Ч(16, 2) = 23. Определите точное значение )Ч(п, 2) для всех п. 39. [НМЯЗ) (Д. М. Робсон.) Используя обозначения из упр. 38, покажите, чта )Ч(п1 + пш т) < Ж(пп тп) + )Ч(пм т) + ТЧ(2т — 2, т). Следовательно, для фиксираваннога т существует !пп,, )Ч(п,т)/п = Х(т). 40. [НМбб) Продолжая упр 39, определите )Ч(3), )Ч(4) и !1ш, )Ч(т)/!8 т, если таковой существует. 41. (М27) Назначение этого упражнения состоит в рассмотрении наихудшего случая использования памяти в системе двойников В частности, плохой случай возникает, например, если начать с пустой памяти и действовать следующим образом сначала выделить и = 2"е' блоков длиной 1, которые будут занимать адреса с Р по п — 1, затем для х' = 1, 2,, г освободить все блоки начинающиеся с адресов, которые не делятся на 2, и выделить 2 ~ 'облоков длиной 2", которые будут занимать адреса с 1(1+А)п по -'(2+ )с)п — 1 Для этой процедуры необходимо в 1 + -'г раз больше памяти, чем выделено Докажите, чта наихудший случай не может быть существенна хуже этого когда все запросы приходят на блоки размером 1, 2,, 2" и общий размер запрошенной памяти в любой момент не превышает и, где и кратно 2", система двойников никогда не переполнит область памяти размерам (г+ 1)п 42.
(М40) (Д М Робсон, 1975 ) Пусть Хвр(п, т) — количества памяти, необходимой, чтобы гарантировать отсутствие переполнения при использовании для выделения метода наилучшего подходящего, как в упр 38 Найдите "атакующую" стратегию, показывающую, что Хвр(п, т) ) гоп — О(п+ т ) 43. (НМЗ5) Продолжая упр 42, положим, чта Хрр(п, т) — необходимая при методе первага подходящего память Найдите "оборонительную" стратегию, показывающую, чта Хрр(п, т) < Н пДа 2 (Следовательно, наихудший случай стратегии первого подходящего не так далек ат наилучшего из наихудших случаев ) 44.
(М21] Предположим, чта функция распределения Г(х) = (вероятность того, что размер блока < х) непрерывна Например, Е(х) равна (х — а)/(Ь вЂ” а) при а < х < б, если размеры равномерно распределены между а и 6 Приведите формулу, выражающую размеры первых Х слатов при использовании метода распределенного подходящего 2.6. ИСТОРИЯ И БИБЛИОГРАФИЯ Диикйиын списки и прямоугольные массивы информации, содержащиеся в последовательных ячейках пймяти, широко использовались с первых дней появления компьютеров с хранимой программой, и в самых ранних работах по программированию приведены базовые алгоритмы для прохождения этих структур. (См., например, 3, хоп Хепшапп, Со!!ес!ес! Игаг)гя 5, 113-116 (написана в 1946 году); М. Ч. %!1!сеэ, Р.
3, %Ьее!ег, 6. О!И, ТЛе РгерагаВап аГ Ргойгвтв юг ап Е!ее!гоп!с Р!К!га! Сошрплег (Неа0!пй, Мавэл АсЫ!эоп-Жеэ!еу, 1951), эпЬгапВпе 1Ь1. Обратите особое внимание па работу Конрада Зусе (Копгас! Хпэе) ВеНсЛге с(ег Севе!!всЬаВ бйг Ма!Леша!!!г ппг! Рагепгегэгбе!гппд 63 (Вопп, 1972), написанную в 1945 гаду.
Зусе первым создал нетривиальные алгоритмы для работы со списками динамически изменяемой длины.] До появления индексных регистров работа с последовательными линейнымн списками вьшолнвлась при помощи арифметических операций над самими машинными командами, и использование такай арифметики стало одним из самых ранних обоснований создания компьютеров, в которых программа разделяла с обрабатываемыми данными общее пространство памяти, Технологии, позволяющие лие спискам переменной длины занимать последовательные адреса памяти такилл образом, чтобы при необходимости их можно было сдвигать в ту или иную сторону, как описано в разделе 2,2.2, бьши, повидимому, гораздо более поздним открытием.
Д, Данлэп (3. Рпп!ар) из Р!к!ле)г Согрета!!ап разработал такие технологии до 1963 года в связи с созданием ряда компилирующих программ. Прилгерно в то же время данная идея независимо возникла при создании компилятора СОВОЬ в 1ВМ Согрогабоп и набора связанных с ним подпрограмм, называвшегося С1Т1Ж5, который впоследствии использовался в различных коллпьютерах.
Технологии оставались неопубликованными до тех пар, пока не были независимо разработаны Янам Гарвиком (3ап Оагибсй) нз Норвегии; см. ШТ 4 (1964), 137 — 140. Идея размещении линейного списка не в последовательных ячейках памяти, видимо, появилась в связи с разработкой компьютеров с устройствами хранения информации на магнитных барабанах. После выполнения кол~анды из ячейки и такой компьютер обычно не был готов к работе с командой нз следующей ячейки и + 1, так как барабан уже прошел эту точку.
В зависимости от выполняющейси команды наиболее благоприятным местом расположения следующей команды лложет оказаты'я, например, ячейка и+ 7 или и+ 18, и прн оптимальном размещении команд быстродействие мвшнвы может увеличиться в 6 — 7 раз. (Обсуждение интересных задач, относящихся к оптимальному расположению кол~вид, люжно найти в статье автора этой книги в 3АСМ 8 (1961), 119 — 150.] Поэтому в каждой машинной команде появлялось дополнительное адресное поле, служившее связью са следующей командой. Такая идея, названная "адресация 1+1", обсуждалась в работе 3о!лп МапсЫу, Т!лепту апг! Тес!лп!г!пеэ !ог гйе Рсв!кп оГ Е!ее!гоп!с Сошрпгегэ 4 (11.
о! Реппву!тап!а, 1946), Ьеслпге 37. В ней в зачаточной форме содержится понятие связанного списка, хотя так часто использовавшпесв нами в этой главе операции динамической вставки и удалении оставались неизвестными. Другое раннее упоминание о связях в программах приведено в меморандуме Г.
П. Дана (Н. Р. Ьпйп) (1953 г.), в котором для внешнего поиска предлагалось примешпь "цепочки" (гм. раздел 6.4). Реально технологии непользования связанной памяти родились, когда А. Ньювелл (А, 1чеэте!!), Д. К. Шоу (Л. С. 8Ьаи) и Г. А. Саймон (Н. А. Я)шоп) начали свои исследования эвристического решения задач с помощью компьютера. Весной 1956 года для написания программ поиска доказательств в математической логике онн разработали первый язык обработки списков — 1РЫ1. (1Р1. означает 1п(отшат!оп Ртосевгйпб Ьапбпабе — язык обработки информации.) Это была система, использующая указатели и включающая важные концепции наподобие списка свободного пространства, однако концепция стека тогда еще не была достаточно разработана. Созданный годом позже 1Р1.-Н1 включал команды для помещения в стек и выборки из стека в качестве важных основных операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
