38. Доказательство легко обобщается: N{n, 2) = [(Зп - 1)/2J для п > 1. [Если хозяйка использует стратегию первого подходящего вместо оптимальной, то, как доказано Робсоном, необходимо и достаточно [(5п - 2)/3j мест.]

39. Разделим память на три независимые области размерами N{ni,m), N{n2, тп) и Л(27П - 2, тп). Для обработки запроса на выделение памяти поместим каждый блок в первую же область, для которой указанная емкость не будет превышена, с помощью подходящей оптимальной стратегии для этой области. Такое выделение не может не работать, так как если невозможно выполнить запрос для х ячеек памяти, то должно быть минимум (ш - а: + 1) + (п2 - а: + 1) + (27П - а: - 1) > m + пг - а: уже занятых ячеек.

Теперь, если /(п) = М{п,тп) + Л(27П - 2, тп), то для /(п) выполняется свойство полуаддитивности /(ni + nj) < /(ni) + /(пг). Следовательно, существует lim/(n)/n. (Доказательство. f{a + be) < f{a) + bf{c); значит,

limsup„ , f{n)/n = maxo<a<c hmsup(, ,<,„ /(o + be)/(a + be) < f{c)/c

для всех с и

limsup„ , f{n)/n < liminf„ ,<x. f{n)/n. )

Таким образом, существует UmN{n,m)/n.

[Из упр. 38 мы знаем, что Л(2) = . Значение N{m) неизвестно для любого m > 2. Несложно показать, что множитель для двух размеров блоков, 1 и Ь, равен 2 - 1/6, поэтому А(З) > l- Методы Робсона приводят к выводу о том, что Л(3) < 1у и 2 < Л(4) < 2g.]

40. Робсон доказал, что Л(2") < 1 + г, используя следующую стратегию: выделить для каждого блока размером к, где 2"" < < 2"*\ первый свободный блок из fc ячеек, начинающийся с адреса, который кратен 2".

Пусть A({6i,62,... ,6п}) обозначает мультипликативный коэффигщент, когда все размеры блоков вынуждены находиться в множестве {6i, 62,..., 6п}, так что N{n) = Л({1, 2,..., п}). Робсон и Ш. Крогдал (S. Krogdahl) открыли, что A({6i,62,... ,6„}) =

п-(61/62 Н-----l-6n-i/6„) при 6,, кратном 6, i, для 1 < г < п. В действительности

Робсон нашел точную формулу Л(2т, {1,2,4,..., 2}) = 2m(l + fr) - 2 + 1. Таким образом, в частности, N{n) > 1 + [Ignj. Он также определил верхнюю границу N{n) < 1.1825Inп + 0(1) и на основе экспериментов предположил, что N{n) = Нп- Это предположение можно было бы легко доказать, если бы A({6i,62,... ,6п}) было равно п - (61/62 + ••• + bn-i/bn), но, к сожалению, это не так, поскольку Робсон доказал, что ЛГ({3,4}) > 1. (См. Inf. Proc. Letters 2 (1973), 96-97; JACM 21 (1974), 491-499.)

41. Рассмотрим поддержку блоков размером 2*: либо запросы на размеры 1, 2, 4, ..., 2*" будут периодически вызывать разделение нового блока размером 2*, либо будет возвращаться блок этого размера. Можно доказать по индукции по fc, что общая память, расходуемая при таком разделении блоков, никогда не превышает кп. После каждого запроса на разделение блока размером 2*+ используется не более кп ячеек памяти при разделении 2*-блоков и не более п ячеек памяти без разделения.

Доказательство можно усилить, показав, что достаточно оп ячеек, где ао = 1 и а*, = 1 +afc-i(l -2"*). Имеем

fc= О 1 2 3 4 5

, 1 1 п1 955 о 697 А 18535

2 8 64 " 1024 32768

Напротив, для г < 5 может быть показано, что система двойников иногда требует атП ячеек, если механизм шагов R1 и R2 модифицирован так, чтобы выбрать наихудший из возможных 2--блоков вместо первого такого блока.

Доказательство Робсона того, что Л(2) < 1 + г (см. упр. 40), легко модифицировать, чтобы показать, что такая "самая левая" стратегия никогда не потребует более (1 + г)п

ячеек для выделения пространства под блоки размерами 1, 2, 4, ..., , поскольку блоки размером 2*" никогда не будут размещаться по адресам > (1 + \к)п. Хотя его алгоритм кажется очень похожим на систему двойников, он приведет к тому, что система двойников не будет такой хорошей, даже если модифицировать шаги R1 и R2, чтобы для разделения выбирались наилучшие возможные 2-блоки. Например, рассмотрим такую последовательность "снимков" памяти для п = 16иг = 3.

illlllll 10101010 11110000 Illlllll 10101010 10001000 10000000

Illlllll 10101010 11110000 11110000 10102-2-10002-00 10000000

00000000 2-2-2-2-2-110000 11110000 10102-2-10002-00 10000000

00000000 00000000 00000000 00000000

00000000 4---4---

4-0000

Здесь О означает свободный адрес, а к - начало fc-блока. Также имеется последовательность операций, когда п кратно 16, которая приводит к заполнению блоков размером 8 на , а других блоков-на . Если п кратно 128, последовательные запросы на yIjji блоков размером 8 потребуют больше чем 2.Ъп ячеек памяти. (Система двойников позволяет нежелательным единицам "переползти" в из 8-блоков, поскольку нет других свободных двоек для разделения в критический момент; алгоритм "самого левого" поддерживает все единицы ограниченными.)

42. Можно считать, что m > 6. Основная идея заключается в установлении шаблона занятости Rm-2(fm-3Ri)° в начэле памяти для /с = О, 1, где Rj и Fj обозначают выделенные и свободные блоки размером j. Переход от к + 1 начинается с

Rm-iiFm-iRl) Rm-2(fm-3Rl)°Rm-2Rm-2

- Rm.-2{Fm-3Rl)~ Fim-iRm-l

-f Rm-2(Fm-3Rl)° RmRm-bRlRm-2

-> Rm.-2iFm.-3R1) FmRm-bRi;

затем коммутационная последовательность Fm-zRlFmRm-bRl -+ Fm-3RlRm-2R2Rm-bRl

-+ F2m-iR2Rm-bRi ->• HmRm-5RiНгНт-бRi ->• FmRm-bRiFm-zRi использувтся fc раз до тех пор, пока не будет получено FmRm-bRiiFm-sRi) ->• F2m-5Ri(fm-3Ri)* ->• Rm-iiFm-zRi). и наконец, когда fc становится достаточно большим, наступает завершающая фаза, которая вызывает переполнение, если только размер памяти не превышает (п - 4т + 11)(т - 2). Детальное описание можно найти в Сотр. J. 20 (1977), 242-244. [Заметьте, что наихудший из возможных наихудших случаев, который начинается с шаблона Fm-iRiFm-iRiFm-iRi , ТОЛЬКО номногим хужв ЭТОГО; К такому шаблону может привести стратегия "следующего подходящего", рассмотренная в упр. 6.]

43. Покажем, что если Di, D2, ... представляет собой последовательность чисел, такую, что Di/m + D2/{m + l)+-+Dm/i2m-l) > 1 для всех m > 1, и если Cm = D1/I + D2/2 + ----h Dm/m, то NFF{n,m) < пСт- в частности, поскольку

т m + l

2m + 1 2

2т - 3 2т - 2 2т - 1

> In 2,

последовательность констант Dm = 1/1п2 удовлетворяет необходимым условиям. Доказательство осуществляется по индукции по т. Пусть Л; = nCj для j > 1, и предположим, что некоторый запрос на блок размером m не может быть удовлетворен в результате выделения в Лт левых ячеек памяти. Тогда m > 1. Для О < j < m обозначим через Л крайние справа позиции, выделенные для блоков размерами < j (либо это значение равно О, если

все выделенные блоки больше j). По индукции имеем Л < Nj. Кроме того, пусть Л означает крайние справа занятые позиции < Nm, так что Л > Лт -m + l. Тогда интервал --Щ] содержит как минимум \j{Nj - Nj i)/{m + j - 1)] занятых ячеек,

поскольку размеры свободных блоков в нем меньше тп, а размеры его зарезервированных блоков > j. Отсюда следует, что п - m не меньше числа занятых ячеек, а последнее не меньше YlTi 3{N-Nj i)l{m+3-l) = mAr;„/(2m-l)-(m-l)Er=~i Щ 1{т+з){ш+з-\) > mNm/{2m-l)-m~{m - l)£T=i Nj{l/{m+j-l)-l/{m+j)) = YlJi nDj/im+j-l)-m > п - тп, что приводит к противоречию.

[Здесь доказано несколько больше, чем требовалось. Если определить D как Di/тп + ••• + Dm/{2m - 1) = 1, то последовательностью Ci, Сг, ... будет 1, ЦЦ,

результат может быть улучшен даже для m = 2, как в упр. 38.]

44. \F-il/N)], \F-{2/N)],..., \F-{N/N)].