23. [05] Каков двоичный адрес двойника блока размером 4, двоичный адрес которого равен 011011110000? Каким бы он был, если бы блок имел размер 16?

24. [20] Согласно приведенному в тексте раздела алгоритму наибольший блок (размером 2"*) не имеет двойника, так как представляет собой всю память. Будет ли правильным определение

двойник„(0) = О

(по сути, блок станет собственным двойником), и можно ли таким образом избежать проверки к = т т шаге S1?

► 26. [22] Раскритикуйте следующую идею: "Динамическое выделение памяти с помощью системы двойников на практике никогда не приводит к выделению блока размером 2"* (поскольку этим исчерпывается вся память), и, вообще говоря, имеется некоторый максимальный размер 2", такой, что блоки большего размера никогда не выделяются. Значит, начинать работу с такого размера блоков - пустая трата времени, как и объединение в алгоритме S блоков, образующих в результате свободный блок размером, превосходящим 2"".

► 26. [21] Поясните, каким образом можно использовать систему двойников для динамического выделения памяти с адресами от О до М - 1 даже в случае, когда М не имеет вид 2*", как требуется в тексте раздела.

27. [24] Напишите MIX-программу для алгоритма R и определите время ее работы.

28. [25] Напишите MIX-программу для алгоритма S и определите время ее работы, считая MIX двоичным компьютером с новой операцией X0R, с помощью обозначений из раздела 1.3.1 определяемой так: "С = 5, F = 5. Для каждого бита в ячейке М, равного 1, соответствующий бит в регистре А дополняется (изменяется с О на 1 или с 1 на 0); знак г А остается неизменным, время выполнения равно 2и"

20, [20] Может ли система двойников работать без бита дескриптора в каждом выделенном блоке?

80. [М48] Проанализируйте среднее поведение алгоритмов R и S, задавая обоснованные распределения для последовательности запросов на выделение памяти.

31. [М40] Можно ли построить аналогичную системе двойников систему динамического распределения памяти, основанную на последовательности чисел Фибоначчи, а не на степенях двойки? (Таким образом, можно начать с F,n свободных слов и разделить доступные блоки из Fk слов на два двойника длиной Fk~i и Fk~2 соответственно.)

32. [НМ47] Определите limn-tooOn, если он существует, где а„-среднее значение tn в случайной последовательности, определенной таким образом. Даны значения tk для 1 < А; < п; <п равновероятно выбирается из множества значений {1, 2,... ,дп}, где

дп = [\ шт(10000, /(tn-i - 1), /«п-2 - 2), ..., /(П - (п - 1)))J

и f{x) = X прн а; > о и f{x) = 00 при а: < О, [Примечание. Некоторые ограниченные эмпирические тесты показывают, что а» может быть примерно равно 14, но, вероятно, это не слишком точное значение.]

► 33. [28] {Сборка мусора и уплотнение.) Положим, что ячейки памяти 1,2, ..., AVAIL - 1 используются в качестве пула памяти для узлов переменного размера, имеющих следующий вид: первое слово NODE(P) содержит поля

SIZE(P) = количество слов в NODE(P);

Т(Р) = количество полей связей в NODE(P); Т(Р) < SIZE(P); LINK(P) = специальное поле связи для использованиятолько прн сборке мусора.

В памяти за NODE(P) следует NODECP 4- SIZE(P)). Предположим, что в NODE(P) в качестве связей с другими узлами используются LINK(P-l-l), LINK(P-l-2), .., LINK(P-Ь Т(Р)) и

каждое из этих полей связей лредставляет собой либо Л, либо адрес первого слова другого узла. И наконец, предположим, что в программе имеется еще одна переменная связи с именем USE, которая указывав на один из узлов.

Разработайте алгоритм, который (i) определяет все узлы, прямо или косвенно доступные из переменной USE, (ii) перемещает эти узлы в ячейки памяти от 1 до К - 1 для некоторого К, изменяя все связи так, чтобы сохранились структурные отношения, и (iii) устанавливает AVAIL <- К.

Например, рассмотрим следующее содержимое памяти, где INFO(L) обозначает содержимое ячейки L, исключая LINK(L):

1: SIZE = 2, Т = 1 6: SIZE = 2, Т = О AVAIL = 11,

2; LINK = 6, INFO = А 7: CONTENTS = D USE = 3.

3:SIZE = 3, T = l 8:SIZE = 3, T = 2

4: LINK = 8, INFO = В 9: LINK = 8, INFO = E

5: CONTENTS = С 10: LINK = 3, INFO = F

Ваш алгоритм должен преобразовать эти данные в

1: SIZE = 3, Т = 1 4: SIZE = 3, Т = 2 AVAIL = 7,

2: LINK = 4, INFO = В 5: LINK = 4, INFO = Е USE = 1.

3: CONTENTS = С 6: LINK = 1, INFO = F

34. [29] Напишите MIX-программу для алгоритма из упр. 33 и определите время ее работы.

35. [22] Сопоставьте методы динамического распределения памяти из этого раздела с технологиями последовательных списков переменного размера, рассмотренными в конце раздела 2.2.2.

► 36. [20] В некоторой закусочной в Голливуде (Калифорния) имеется 23 места для посетителей, которые приходят поодиночке или вдвоем. Хозяйка закусочной показывает посетителям их места Докажите, что она всегда сможет рассадить посетителей, не разбивая пары, если одновременно в закусочной будет находиться не более 16 посетителей, а одиночки не сидят на местах 2, 5, 8, ..., 20 (предполагается, что каждая пришедшая пара уходит вместе).

► 37. [26] Продолжая упр. 36, докажите, что хозяйка не всегда может так удачно рассадить посетителей, если в закусочной только 22 места. Независимо от используемой ею стратегии может возникнуть ситуация, когда в закусочной будет находиться всего 14 посетителей, но для вошедшей пары не найдется двух соседних пустых мест.

38. [М21] (Д. М. Робсон (J. М. Robson).) Задача о закусочной, изложенная в упр. 36 и 37, может быть обобщена для определения производительности в наихудшем случае для любого алгоритма динамического выделения памяти, который никогда не перемещает выделенные блоки. Пусть N{n,m) - наименьшее количество памяти, такое, что любая серия запросов на выделение и освобождение может быть выполнена без переполнения в случае, когда все размеры блоков не превышают т, а общее количество затребованной памяти не превосходит п. В упр. 36 и 37 доказано, что А(16, 2) = 23. Определите точное значение N{n, 2) для всех п.

39. [НМ23] (Д. М. Робсон.) Используя обозначения из упр. 38, покажите, что

JV(ni + П2, ш) < N{ni, т) + М{п2, т) + N{2m - 2, m). Следовательно, для фиксированного m существует

Ишп-юо N{n,m)ln = N{m).

40. [НМ50] Продолжая упр 39, определите А(3), JV(4) и iimm-»oo N(m)/lgm, если таковой существует.

41. [М27] Назначение этого упражнения состоит в рассмотрении наихудшего случая использования памяти в системе двойников В частности, плохой случай возникает, например, если начать с пустой па»ти и действовать следующим образом сначала выделить п = 2""" блоков длиной 1, которые будут занимать адреса с О по п - 1, затем для к = 1,2, , г освободить все блоки начинающиеся с адресов, которые не делятся на 2, и выделить 2~~п блоков длиной 2*, которые будут занимать адреса с j{l+k)n по {2 + к)п - 1 Для этой процедуры необходимо в 1 -Ь г раз больше памяти, чем выделено

Докажите, что наихудший случай не может быть существенно хуже этого когда все запросы приходят на блоки размером 1,2, , 2"" и общий размер запрошенной памяти в любой момент не превышает п, где п кратно 2, система двойников никогда не переполнит область памяти размером (г + 1)п

42. [М40] (Д М Робсон, 1975 ) Пусть JVBF(n, т) - количество памяти, необходимой, чтобы 1арантировать отсутствие переполнения при использовании для выделения метода наилучшего подходящего, как в упр 38 Найдите "атакующую" стратегию, показывающую, что Мвр{п, т) > тп - 0{п + т)

43. [НМ35] Продолжая упр 42, положим, что/VFF(n, т)-необходимая при методе первого подходящего память Найдите "оборонительную" стратегию, показывающую, что Nff {п, т) < Нтп/1п 2 (Следовательно, наихудший случай стратегии первого подходящего не так далек от наилучшего из наихудших случаев )

44. [М21] Предположим, что функция распределения F{x) - (вероятность того, что размер блока < х) непрерывна Например, F{x) равна (х - а)/{Ь - о) при а < х < Ь, если размеры равномерно распределены между о и 6 Приведите формулу, выражающую размеры первых N слотов при использовании метода распределенного подходящего