AOP_Tom1 (1021736), страница 175
Текст из файла (страница 175)
Шаг С1 опущен. 01 02 11МК 1НРО 51ЕЕ Т С2 ОЯ 04 06 Об 07 1 1 1 1 а+1 а+1 а+1 а а+Ь Ь Ь Ь Ь Ь а — 1 а — 1 а — 1 1 1 1 1 1.1НК(Р) г — Ц. Ц +- Ц+ 51ЕЕ(Р). Р +- Р+ 51ЕЕ(Р). Сб. П исвоенне новых а+1 а+с+1 а+с+1 есов. а+1 1 1 1 1 1 1 г( 6 с+6 с+8 с+6 с+6 с 05Е г- 1.1МК(ОЗЕ). АЧА11 +- Ц. Р+- 1. г16 г- Р+ 51ЕЕ(Р) . 08 ОО 10 11 12 1Э Ц 16 16 17 18 19 80 МТ 82 88 81 26 87 88 29 ЯО Я1 88 ЭЭ Я4 Эб Яб 87 Яб 10 41 48 48 й 46 16 87 48 СЗ С4 1Н С5 1Н Сб СЗА СЗ 1Н С7 2Н ЕЦО ЕЦО ЕЦО ЕЦО 101 102 ЗТ2 ЗТЕ ЕИТЗ 101 )1Е ЬО4 14Е 1МСЗ ОЕС4 502 1.ОА ЯАНЕ ЗТ1 ЕМТ1 )ИР ЕМТ2 ЗТ2 ЕИТЗ ЯИР ЗТ2 1502 1НСЗ ЮА 105 ЯАЕ )ЗМЕ 501 ЬОА ЗТА ЗТ2 ЕМТЗ ЯИР 106 1МС5 ЕМТб 1МСб ЬОА ЯАЕ ЗТ5 1НСЗ .) ИР ОЕС4 4:5 0:3 1:2 3:3 АЧАП.
0,1(ЫМК) 0,20.1НК) 0,1 0,1 И.1МК) 05 0,3(Т) СЗ 1 1 0,3(11МК) 0,2(11ИК) 1В 0,2(51МК) 0,2 15 1 0,3 1 Сб 0,3(11МК) 0,5 0,5 0,3(ПМК) 0.3(31ЕЕ) С7 1В ОЗЕ 0,1(11НК) АЧАП. 1 СЗР 0,6(31ЕЕ) 0,6 0.3 0,5 0,6(1.1МК) 1В 0,3(51ЕЕ) 0,5 СВА 1 С2 Инн нализ ня взы ма кн овкн. ТОР г — 05Е. 1.1ИК(ТОР) +- АУАП., 1.1МК(АЧАП.) г- Л. Шаг.
ян *~~ т ТОР г- ЬТИК(ТОР). Перейти к шагу СЬ при ТОР = Л, С4 Поместить новые связи в стек й г — Т(Р). А =07 Рг — Р+1. Ь е- й — 1, Ц +- ЫМК(Р). Переход, если 1.1МК(Ц) ~ Л. Иначе — установить 1.ТИК ЬЦ) е- ТОР, ТОР г- Ц. Сб Инн налива ня сл ю ей азы. Ц < — 1. 11ИК(АЧА11) г- 1, 51ЕЕ(АЧА1Ы +- О. Р+- 1. Переход, если 1.1ИК(Р) = Л. Переход, если ЗТЕЕ(Р) ,-А О. СЯ. П еоб азоваигге всех связей. г15 +- г!5 + 31ЕЕ(Р+ 51ЕЕ(Р)). С7. Слияние св ных областей.
Переход, если 1.1ИК(г16) гн Л. 51ЕЕ(Р) + — г15. Р г- Р+ 51ЕЕ(Р), 49 1ИС2 1 Ь О с- О+ 1. 50 105 0,2 (11ИК) Ь 51 СОА О, Б(11МК) Ь 58 БТА 0,2(11МК) Ь 11МК(0) +- 11МК(11МК(0)). ВВ 1Н 14ИЕ 2В а+ Ь Переход, если )с ЧА О. Ц ЗН 1МСЗ 0,5 а+с Р+- Р+ 512Е(Р). 55 СВР СОА 0,3(11МК) 1 + а + с 56 105 0,3(31ЕЕ) 1 + а ч-с 57 )АЕ ЗВ 1+а+с 11МК(Р) = Л7 ВВ 104 0,3(Т) 1+а )с ~ Т(Р). 50 ЕМТ2 О,З 1+а 0 с-р. 60 1БМЕ 1В 1+ а Переход, пока не будет получено 51ЕЕ(Р) = О. 61 С9 ЕИТЗ 1 ас. пя сь 68 ЕМТ1 1 1 Установить г11 для операции МОЧЕ.
ВВ 1ИР 09Р 1 64 1Н ЯТЕ 0,3(11ИК) а 51ИК(Р) +- Л. 65 БТБ с+1(4с4) а 66 ИОЧЕ 0.3(в) а МОВЕ(гП) с — ИОВЕ(Р), гП с- гП+ 51ЕЕ(Р). 67 ЗН 1МСЗ 0.5 а+с Р+- Р+ 51ЕЕ(Р). 68 С9Р СОА 0,3(11МК) 1+а+с 69 105 0,3(81ЕЕ) 1 + а -~- с 70 1АЕ ЗВ 1 + а + с Переход, если 1.1МК(Р) = Л. 71 15МЕ 1В 1 + а Переход, пока не будет получено 81ЕЕ(Р) = О. 3 В строке бб предполагается, что размер каждого узла достаточно мал, так что он может быть перемещен с помощью одной операции ИОЧЕ.
Похоже, что это предположение применимо в большинстве случаев такой сборки мусора. Общее время работы данной программы составляет (44а + 175+ Ею+ 25с + 8с(+ 47) и, где а — количество доступных узлов, Ь вЂ” количество полей связи в них, с — количество недоступных узлов, которым ие предшествует недоступный узел, с( — количество недо. ступных узлов, которым аредсавсшвуеш недоступный узел, и св — общее количество слов в доступных узлах. Если в памяти содержится и узлов, и рп из них недоступно, то можно оценить а = (1 — р)п, с = (1 — р) рп, В = р~п, например узлы, состоящие в среднем из пяти слов, в среднем с двумя полями связей на узел и памятью на 1000 узлов.
Тогда при р =— 1 программа требует 374и времени на восстановление одного свободного узла; при р =— время работы составляет 104и, а при р = с — всего 33и. 36. Посетитель, который пришел оцин, может сесть на одно из 16 мест — 1, 3, 4, б, ..., 23, Если прихсщит пара, для нее должно оставаться свобоцное место, так как иначе минимум два посетителя будут находиться на местах (1, 2, 3), минимум два — на местах (4, Б, Б), ..., минимум два — на местах (19,20, 21) и минимум один — на месте 22 или 23, так что в этот момент в закусочной будет находиться как минимум 15 человек.
37. Хозяйка усадила первых 16 одиноких мужчин. В результате между занятыми местами есть 17 промежутков, включая промежутки на концах ряда мест (предполагается, что между соседними занятыми местами имеется промежуток нулевой длины). Общее количество пустых мест, т. е. сумма всех семнадцати промежутков, равна б. Предположим, что имеется х промежутков нечетной длины; тогда к услугам вновь вошедшей пары — б — х свободных мест. (Заметьте, что б — х четно и > О.) Теперь каждый посетитель номер 1, 3, 5, 7, 9, 11с 13, 15 слева направо, у которого четны промежутки с обеих сторон, встает и уходит. Каждый нечетный промежуток препятствует уходу не более одного из посетителей, следовательно, уйдут по меньшей мере 8 — х человек.
Остается все еще только б — х мест для того, чтобы посадить вошедшие пары, которых вдруг оказывается (8 — х)/2. 38. Доказательство легко обобщается: Н(п, 2) = ИЗи — 1)/2) для и > 1. [Если хозяйка использует стратегию первого подходящего вместо оптимальной, то, как доказано Робсоном, необходимо и достагочко ((Ьп — 2)/32| мест.] 39. Разделим память иа три независимые области размерами 12(п1,|и), 127(пз, т) и Ю(2т — 2, т). Для обработки запроса на выделение памяти поместим каждый блок в первую же область, для которой указанная емкость не будет превышена, с помощью подходящей оптимальной стратегии для этой области.
Такое выделение не может не работать, так как если невозможно выполнить запрос для х ячеек памяти, то должно быть минимум (п| — х + 1) + (лз — х + 1) + (2т — х — 1) > п| + п| — х уже занятых ячеек. Теперь, если /(и) = Х(п,т) + Ф(2т — 2, т), то для /(л) выполняется свойство полуаддитивиости /(и| + п|) < /(п1) + /(пз). Следовательно, существует !!п| /(п)/и. (Доказательство. /(а + Ьс) < /(а) + Ь/(с); значи'г, !ппвпр„ /(и)/и = шаха«, !пибпрб /(а+ ьс)/(а+ ьс) < /(с)/с для всех с и 4 5 3 —, 4— 627 16626 1024 22766 !2= 0 1 аь= 1 2 2 2- 6 3 2— 66 64 Напротив, для г < 5 может быть показано, что система двойников иногда |иребует а п ячеек, если механизм шагов В1 и В2 модифицирован так, чтобы выбрать наихудший из возможных 21-блоков вместо первого такого блока.
Доказательство Робсона того, что 127(2') < 1 + г (см. упр. 40), легко модифицировать, чтобы показать, что такая "самая левая" стратегия никогда ие потребует более (1 + -г)п 1 !|тбир„ /(и)/и < !пп!п(6 /(п)/и ) Таким образом, существует !!ш 1|7(п, т)/и. (Из упр. 38 мы знаем, что 147(2) = 2. Значение !77(т) неизвестно для любого т > 2. Несложно показать, что множитель для двух размеров блоков, 1 и Ь, равен 2 — 1/Ь, поэтому 1|7(3) > 122. методы Робсона приводят к выводу о том, что 217(з) < 1 2 и 2 < 147(4) < 2Д 40.
Робсон доказал, что !27(2") < 1 + г, используя следующую стратегию: выделить для каждого блока размером Ь, где 2 < Ь < 2 7', первый свободный блок из Ь ячеек, начинающийся с адреса, который кратен 2 Пусть Н((61, Ь2,..., Ь„) ) обозначает мультипликативный коэффициент, когда все размеры блоков вынуждены находиться в множестве (61, 62,..., Ь„), так что 117(71) Х((1,2,...,п)). Робсон и Ш. Крогдал (8. КгоббаЫ) открыли, что 117((61,62,...,66)) = п — (Ь|/Ь2+ +Ь„1/Ь„) при Ь„кратном Ь, 1, для 1 < | < и.
В действительности Робсон нашел и|очную формулу 127(2"т,(1,2,4,...,2")) = 2"т(1 + -'г) — 2" + 1. Таким образом, в частности, 267(п) > 1 + -'(!8и). Он также определил верхнюю границу 177(и) < 1.18251пи+ 0(1) и на основе экспериментов предположил, что !27(п) = и„. это предположение можно было бы легко доказать, если бы Х((61,62,...,66)) было равно п — (Ь|/62 + + Ь„1/Ь„), но, к сожалению, это ие так, поскольку Робсон доказал, что 127((З, 4)) > 1 16. (См.
1пб Ргос. Тессегв 2 (1973), 95-97; ЗАСМ 21 (1974), 491 — 499 ) 41. Рассмотрим поддержку блоков размером 22: либо запросы на размеры 1, 2, 4,..., 26 будут периодически вызывать разделение иового блока размером 2", либо будет возвращаться блок этого размера. Можно доказать по индукции по Ь, что общая память, расходуемая при таком разделении блоков, никогда ие превышает !еи. После каждого запроса иа разделение блока размером 2 + используется не более Ьи ячеек памяти при разделении 2.1 1 22-блоков и не более п ячеек памяти без разделения.
Доказательство можно усилить, показав, что достаточно а„и ячеек, где ао = 1 и аь = 1+ ал-1(1 — 2 ь). Имеем ячеек для выделения пространства под блоки размерами 1, 2, 4, ..., 2", поскольку блоки размером 2 никогда не будут размещаться по адресам > (1+ -й)п. Хотя его алгоритм ! 1 кажется очень похожим на систему двойников, он приведет к тому, что система двойников не будет такой хорошей, даже если модифицировать шаги Н.! и К2, чтобы для разделения выбирались наилучшие возможные 2'-блоки. Например, рассмотрим такую последовательность "снимков" памяти для и = 16 и г = 3. Здесь О означает свободный адрес, а !с — начало !с-блока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
