устанавливается AVAIL 4- AVAIL-t-N. Для освобождения этих N слов просто устанавливается AVAIL <- AVAIL - N.

Аналогично для метода "первым выделен - первым освобожден" используются операции с циклической очередью.

2. Количество памяти, необходимой для хранения элемента длиной I, составляет к\1/{к - Ь)], среднее значение которого равно кЬ/{к - Ь) + (1 - а)к, где а предполагается равным 1/2, не зависящим от к. Это выражение минимально (для действительных значений к) при к = Ь+ \/2ЬЬ. Поэтому выбор к равным ближайшему (сверху или снизу) к этой величине целому значению дает наименьшее значение кЬ/(к - Ь) + к. Например, при b = 1 и L = 10 следует принять к х 1 + д/20 = 5 или 6; оба значения одинаково хороши. Более детально эта задача рассматривается в JACM 12 (1965), 53-70.

4. rll = Q, rI2 = P.

rA 4- N.

P 4- LOC(AVAIL). Q <- P.

P i- LINK(Q).

Если P = A, нет памяти.

Переход при N > SIZE (Р). rA<-N-SIZE(P) =К. Переход при К 0.

LINK(Q) <- LINK(P). SIZE(P) 4-К. Возможное окончание

с установкой гИ 4- Р -t- К.

5. Вероятно, не стоит. Недоступная область памяти непосредственно перед адресом Р станет впоследствии свободной, и ее длина увеличится на величину К; увеличение на 99 не является незначительным.

6. Идея заключается в поиске подходящего блока всякий раз в различных частях списка AVAIL. Например, можно воспользоваться блуждающим указателем (roving pointer) с именем ROVER, который работает следующим образом. На шаге Al установить Q <- ROVER. После шага А4 установить ROVER <- LINK(Q), если LINK(Q) А; в противном случае установить ROVER <- LOC (AVAIL). На шаге А2, когда впервые при некотором выполнении алгоритма А Р = А, установить Q 4- LOC (AVAIL) и повторить шаг А2. Когда Р = А во второй раз, алгоритм завершается неудачно. Таким образом, ROVER будет стремиться указывать на случайные места в списке AVAIL и размеры окажутся более сбалансированными. В начале программы установите ROVER 4- LOC (AVAIL). Необходимо также устанавливать ROVER равным LOC (AVAIL) каждый раз, когда блок, адрес которого равен текущему значению ROVER, удаляется из списка AVAIL. (Впрочем, иногда полезно иметь в начале памяти блоки малого размера, как в случае метода первого подходящего; например, в конце памяти может храниться последовательный стек. В таких ситуациях можно уменьшить время поиска с помощью деревьев, как предложено в упр. 6.2.3-30.)

7. 2000, 1000 с запросами на выделение блоков размером 800, 1300.

[Пример, когда работает метод наихудшего подходящего, но не работает метод наилучшего подходящего, был предложен Р. Д. Вейландом (R. J. Weiland).]

8. На шаге Al установить М 4- оо, R 4- А. На шаге А2, если Р = А, перейти к шагу Аб. На шаге A3 перейти к шагу А5 (а не к шагу А4). Добавить следующие шаги.

А5. [Наилучший подходящий?] Если М > SIZE(P), установить R •(- Q и М <- SIZE(P). Затем установить Q «- Р и вернуться к шагу А2.

Л6. [Найден ли блок?] Если R = Л, алгоритм завершается неудачно. В противном случае установить Q 4- R, Р 4- LINK(Q) и перейти к шагу А4.

9. Очевидно, что если нам везет и мы находим блок с SIZE(P) = N, то найден наилучший подходящий блок и дальнейший поиск на этом прекращается. (Если используются блоки лишь нескольких разных размеров, это происходит достаточно часто.) Если применить метод "помеченной границы" наподобие использованного в алгоритме С, можно содержать список AVAIL в рассортированном по размерам блоков виде. При этом длительность поиска в среднем может быть снижена до половины длины списка (или даже до меньшей величины). Однако наилучшим решением представляется размещение списка AVAIL в виде структуры сбалансированного дерева, описываемого в разделе 6.2.3, в случае, если список имеет достаточно большой размер.

10. Необходимо сделать следующие изменения. Шаг В2: вместо "Р > РО" вставить "Р > РО".

Шаг ВЗ: вставить "Если P0-t-N>PHP7iA, установить Р <- LINK(P) и повторить шаг ВЗ".

Шаг В4: вместо "Q-i-SIZE(Q) = РО" вставить "Q-i-SIZE(Q) > РО", а вместо "SIZE(Q) <-SIZE(Q)-t-N" -"SIZE(Q) <-РО-t-N - Q".

11. Если РО > ROVER, на шаге BI вместо Q <- LOC(AVAIL) можно установить Q <- ROVER. Если в списке AVAIL имеется п элементов, среднее количество итераций на шаге В2 составляет (2п + 3)(п -t- 2)/6(п -Ь 1) = п -Ь § -Ь О (). Например, если п = 2, будет получено 9 равновероятных ситуаций, в которых Р1 и Р2 указывают на два существующих свободных блока.

РО < Р1 Р1 < РО < Р2 Р2 < РО ROVER = Р1 1 I 1 2

ROVER = Р2 1 2 I 1

ROVER = LOC (AVAIL) 1 2 3

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

l{il)<hQHl)Hl))-mhQ)-i-

12. Al. Установить Р <- ROVER, F <- 0.

А2. Если Р = LOC(AVAIL) и F = О, установить Р <- AVAIL, F <- 1 и повторить шаг А2. Если Р = LOC (AVAIL) и F О, алгоритм завершается неудачно.

A3. Если SIZE(P) > N, перейти к шагу А4; в противном случае установить Р <- LINK(P) и вернуться к шагу А2.

А4. Установить ROVER LINK(P), К <- SIZE(P) -N. Если К < с (где с -константа > 2), установить LINK (LINK (P-t-D) <- ROVER, LINK(ROVER-t-l) <- LINK(P-t-l), L <- P; в противном случае установить L <- P-t-K, SIZE(P) •(- SIZE(L-l) <- K, TAG(L - 1) <- "-", SIZE(L) <- N. И наконец, установить TAG(L) <- TAG(L -t- SIZE(L) - 1) <- "-t-". I

13. rll = P, rX = F, rI2 = L.

LINK EQU 4:5

SIZE EQU 1:2

TSIZE EQU 0:2

TAG EQU 0:0

rI3.

14. (a) Это поле необходимо для определения начала блока на шаге С2. Его можно заменить (возможно, с преимуществом перед исходным расположением) связью с первым словом блока (см, также упр. 19) (Ь) Это поле необходимо, так как иногда нужно выделить более N слов (например, если К = 1) и при освобождении надо знать количество выделявшейся памяти.

15, 16. rll = РО, г12 = Р1, г13 = F, г14 = В, г16 s -N.

D1 LDI РО

LD2 O.KSIZE)

ENN6 0,2

INC2 0.1

LD5 0,2(TSIZE)

J5N D4 D2 LD5 -l.KTSIZE)

J5N D7

N <-PI

SIZE(PO). -PO-t-N.

Перейти к шагу D4, если TAG (PI) = D2.

Перейти к шагу D7, если TAG(P0 - 1) =