17. Оба поля LINK равны LOC (AVAIL).

18. Алгоритм A выделяет верхнюю часть большого блока. Когда вся память доступна, метод первого подходящего начинает работу с выделения памяти в старших адресах, однако повторно после освобождения эти блоки памяти не резервируются, поскольку обычно подходящие свободные блоки находятся в младших адресах. Таким образом, большой свободный блок, расположенный в начале памяти, при использовании метода первого подходящего быстро исчезает. Однако большой блок редко оказывается наиболее подходящим, а потому метод наиболее подходящего оставляет большой блок в начале памяти.

19. Используйте алгоритм из упр. 12 с исключением из шага А4 ссылок на SIZE(L - 1), TAG(L - 1) и TAG (L-t-SIZE (L) - 1); вставьте также следующие новые шаги между А2 и A3.

A2i. Установить Р1 <- Р-Н SIZE(Р). Если TAG(Pl) = "-f", перейти к шагу A3. В противном случае установить Р2 <- LINK(Pl), LINK(P2 -t- 1) <- LINK(P1 -t- 1), LINK(LINK(P1-t-D) <-P2, SIZE(P) <- SIZE(P) -t-SIZE(Pl). Если ROVER = Pl, установить ROVER <- P2. Повторить шаг A2. Ясно, что ситуации (2)-(4) здесь встретиться не могут; единственный реальный эффект от такого распределения памяти заключается в тенденции к удлинению поиска по сравнению с упр. 12, а иногда в том, что К будет меньше, чем с, хотя реально будет существовать доступный блок, предшествующий данному, о котором нам ничего не известно.

(Имеется альтернативный вариант, при котором слияние блоков выносится из внутреннего цикла A3 и выполняется только на шаге А4 перед окончательным выделением памяти или во внутреннем цикле, если иначе алгоритм завершится неудачно. Такой альтернативный вариант требует модельного изучения для того, чтобы установить, имеются ли у него какие-либо преимущества.)

[Этот метод с небольшими усовершенствованиями, как было доказано, вполне удовлетворителен для реализации ТХ и METflFONT. См. Т: The Program (Addison-Wesley. 1986), §125.]

20. Когда обнаруживается свободный двойник, при выполнении цикла слияния необходимо удалить блок из списка AVAIL [fc], однако неизвестно, какие связи следует обновить. Для получения ответа на этот вопрос можно (i) выполнить длинный поиск или (ii) сделать список двусвязным.

21. Если п = 2*Q, где 1 < а < 2, а„ равно 2+(а - ) + Ь Ь„ равно 2-Q -t- 2>-а. Отношение Оп/Ьп для больших п, по сути, равно величине 4(а - )/а, которая принимает минимальное значение при а = 1 и 2 и максимальное значение при а = l. Так что йп/Ьп не имеет предела, колеблясь между этими двумя крайними значениями. Методы усреднения из раздела 4.2.4, однако, дают нам среднее отношение, равное 4(1п2)- S{a - )da/a = (ln2)-i « 1.44.

22. Для этой идеи необходимо поле TAG в нескольких словах блока из 11 слов, а не только в первом слове. Она работоспособна, если можно выделить дополнительные биты TAG, и, скорее всего, подходит, в первую очередь, для аппаратной реализации.

23. 011011110100; 011011100000.

24. Это привнесет ошибку в программу; можно оказаться на шаге S1 при TAG(O) = 1, поскольку из шага S2 можно вернуться к шагу S1. Для работоспособности программы

- необходимо на шаге S2 добавить "TAG(L) <- О" после "L Р". (Впрочем, проще считать, что TAG(2") = 0.)

25. Идея абсолютно верна (критика не всегда должна быть только отрицательной). Заголовки списков AVAIL [fc] могут быть обрезаны для п < к < т; приведенные в тексте раздела алгоритмы могут использоваться с заменой m на п на шагах R1 и S1. Начальные условия (13) и (14) должны быть изменены таким образом, чтобы указывалось г""" блоков размером 2", а не один блок размером 2".

26. Используя двоичное представление М, можно легко изменить начальные условия (13) и (14) так, чтобы вся память была разделена на блоки, размеры которых представляют собой степени двойки, с блоками в порядке убывания размеров. В алгоритме S TAG(P) должен рассматриваться как О всякий раз, когда Р > М - 2*.

27. гИ : fc, г12 = j, г13 = j-k, rI4 = L, LOC (AVAIL [j] ) = AVAIL -t- j.

Предполагаем, что имеется вспомогательная таблица TWO[j] = 2, хранящаяся в ячейках TWO + j, для О < j < т. Предположим далее, что "+" и "-" представляют дескрипторы О и 1 и что TAG(LOC(AVAIL [j])) = но в качестве признака конца памяти TAG (LOC (AVAIL [m-t-1])) = "+".

RI. Поиск блока. jk.

Переход при AVAILF [j] # LOC (AVAIL [j] ) .

Увеличение j.

j < m?

01 02 03 04 05 06 07 08 09 10 11 12 13

15 16 17 18 19 20 21 22 23 24 25 26 29.

гИ = к, г15 = Р, г14 = L; полагаем TAG (г") = "+"

S1 LD4 LD1

1Н ENTA XOR STA LD5 LDA

0.4 TWO.l TEMP TEMP 0,5 JANN S3

CMPl 0.5(KVAL) JNE S3 S2 LD2 0,5(LINKF) LD3 0,5(LINKB) ST3 0,2(LINKF) ST2 0,3(LINKB) INCl 1

CMP4 TEMP . JL IB ENT4 0,5 JMP IB

1+5 1+5 1 + 5 1 + 5 1 + 5 1 + 5 B + S B + S

SS LD2 ENNA STA ST2 STl ST4 ST4

Может,

AVAIL.1(LINKF) AVAIL.1 0,4(0:4) 0.4(LINKF) 0.4(KVAL) 0,2(LINKB) AVAIL,1(LINKF)

SI. Свободен ли двойник?

г A 4- двойник/ь (L). Р <- гА.

Переход при TAG(P) = 0.

Переход при KVAL(P) ф к.

52 Объединение с двойником.

LINKF(LINKB(P)) <-LINKF(P). LINKB(LINKF(P)) •(-LINKB(P). Увеличение к.

Если L > Р, установить L 4- Р. S3. Помещение в список.

LOC(AVAIL[fc]).

TAG(L) <- 1, LINKB(L) LINKF(L) <- AVAILF[fc]. KVAL(L) <- fc. LINKB(AVAILF[fc]) <- L. AVAIL [fc] <- L. I

HO только за счет некоторого поиска или (что предпочтительнее) дополнительной каким-либо образом упакованной таблицы битов TAG. (Заманчиво объединить двойников не в алгоритме S, а только в алгоритме R, если нет достаточно большого блока, чтобы отвечать запросу. Но, вероятно, это вызовет повышенную фрагментацию памяти.)

31. См. David L. Russell, SICOMP в (1977), 607-621.