AOP_Tom1 (1021736), страница 173
Текст из файла (страница 173)
тП э— з О, т12 ш Р. А1 1ЮА И тА г — М. ЕМТ2 АЧА11 Р г — ЬОС(АЧА15). А2А ЕМТ1 0,2 Ц +- Р. А2 1.02 0,1(1.1МК) Р +- 1.1МК(0). АМ ОЧЕВРЬОМ Если Р = Л,нет памяти. АЗ СИРА 0,2(512Е) 30 А2А Переход при М > 512Е(Р). А4 509 0,2(Я12Е) тА +- М вЂ” 5115(Р) ш К. оАМЗ о+3 Переход при К ~ О.
501 0,2(1.1МК) ЯТХ 0.1(1.1МК) 1.1МК(0) л- 11МК(Р). ЯТА 0,2(5115) Я12Е(Р) л- К. 101 0,2(5118) Возможное окончание 1ИС1 0,2 с установкой гП л- Р+ К. 3 5. Вероятно, не стоит. Недоступная область памяти непосредственно перед адресом Р станет впоследствии свободной, и ее длина увеличится на величину К; увеличение на 99 не является незначительным. 6. Идея заключается в поиске подходящего блока всякий раз в различных частях списка АУА1П Например, можно воспользоваться блуждающим указателем (тотбпК ро(плот) с именем КОЧЕК, который работает следующим образом. На шаге А1 установить 0 +- КОЧЕК. После шага А4 установить ВОЧЕВ л- 1.1МК(0), если 1.1МК(0) ф.
Л; в противном случае установить КОЧЕК +- 1.0С(АЧАП.). На шаге А2, когда впервые при некотором выполнении алгоритма А Р = Л, установить О +- 1.ОС(АЧАП.) и повторить шаг А2. Когда Р = Л во второй раг, алгорити завершается неудачно. Таким образом, НОЧЕВ будет стремиться указывать на случайные места в списке АЧА11 и размеры окажутся более сбалансированными. В начале программы установите КОЧЕК ь- 1.ОС(АЧАТЫ. Необходиио также устанавливать ВОЧЕЯ равным Г.ОС(АЧА11) каждый раз, когда блок, адрес которого равен текущему значению КОЧЕК, удаляется из списка АЧА1П (Впрочем, иногда полезно иметь в начале памяти блоки малого размера, как и случае метода первого подходящего; например, в конце памяти может храниться последовательный стек.
В таких ситуациях можно уменьшить время поиска с помощью деревьев, как предложено в упр. 6 2,3-30.) 7. 2000, 1000 с запросами на выделение блоков размером 800, 1300. (Пример, когда работает метод наихудшего подходящего, но не работает метод наилучшего подходящего, был предложен Р. Д. Вейландом (В. д. Ъре(1апс1),) 6. На шаге А1 установить М ь- со, В +- Л. На шаге А2, если Р = Л, перейти к шагу Аб. На шаге АЗ перейти к шагу А5 (а не к шагу А4).
Добавить следующие шаги. Аб. (Наилучший подходящийу) Если И > 512Е(Р), установить Н е- Ц и И г — 512Е(Р). Затем установить Ц е- Р и вернуться к шагу й2. Аб. (Найден ли блок?] Если Н = й, алгоритм завершается неудачно. В противном случае установить Ц е- Н, Р е- 11ИК(Ц) и перейти к шагу А4. $ 9. Очевидно, что если нам везет и мы находим блок с Б12Е(Р) = И, то найден наилучший подходящий блок и дальнейший поиск на этом прекращается.
(Если используются блоки лишь нескольких разных размеров, это происходит достаточно часто.) Если применить метод "помеченной границы" наподобие использованного в алгоритме С, можно содержать список АЧА11 в рассортированном по размерам блоков виде. При этом длительность поиска в среднем может быть снижена до половины длины списка (или даже до меньшей величины). Однако наилучшим решением представляется размещение списка АЧА11 в виде структуры сбалансированного дерева, описываемого в разделе 6.2.3, в случае, если список имеет достаточно большой размер. 10.
Необходимо сделать следующие изменения. Шаг В2: вместо "Р > РО" вставить "Р > РО". Шаг ВЗ: вставить "Если РО+ И > Р и Р ф й, установить Р г- (.1ИК(Р) и повторить шаг ВЗ". Шаг В4: вместо "О+ 5125(Ц) = РО" вставить "Ц+ 512Е(Ц) > РО", а вместо "512Е(Ц) г- 512Е(Ц) + И" — "512Е(Ц) е- РО+ И вЂ” Ц". 11. Если РО > КОЧЕК, на шаге В1 вместо Ц +- (.ОС(АЧА1(.) можно установить Ц +- КОЧЕК. Если в списке АЧА11 имеется и элементов, среднее количество итераций на шаге В2 составляет (2п + 3)(п + 2)/6(п + 1) = -'и + ~1 + О (Ц. Например, если и = 2, будет получено 9 равновероятных ситуаций, в которых Р1 и Р2 указывают на два существующих свободных блока. РО < Р1 Р1 < РО < Р2 Р2 < РО НОЧЕВ = Р1 КОЧЕК = Р2 КОЧЕК = СОС(АЧА11) На этой диаграмме показано число итераций, необходимых в каждом случае.
Среднее значение составляет 12. А1. Установить Р е- КОЧЕК, Р +- О. А2. Если Р = СОС(АЧА11) и Р = О, установить Р +- АЧА11, Р ь- 1 и повторить шаг А2. Если Р = (.ОС(АЧАП.) и Р ~ О, алгоритм завершается неудачно. АЗ. Если 512Е(Р) > И, перейти к шагу А4; в противном случае установить Р е- 11ИК(Р) и вернуться к шагу Л2. А4. Установить КОЧЕК+- 1.1ИК(Р), К г — 512Е(Р) — И.
Если К < с (где с — константа > 2), установить 11ИК(11ИК(Р-~-1)) г- КОЧЕК, 11ИК(КОЧЕК+1) е- 11ИК(Р4-1), 1 е- Р, впротивном случае установить Ь е- Р+К, 512Е(Р) г — 511Е(1 — 1) е- К, ТАО(1 — 1) г- "-", 5125(1) е- И. И наконец, установить ТАО(1) + — ТАС(1 + 5125(Ы вЂ” 1) е- "+". ) 13. г11 щ Р, гХ ш Р, г12 г— я 1. 11ИК ЕЦО 4:5 БТЕЕ ЕЦО 1:2 Т512Е ЕЦО О:2 ТАС ЕЦО О:О гАьМ. Сдвиг в поле 512Е Р ь О. Р +- КОЧЕК Р Ф 07 Установить Р ь 1 Р ь АЧА11.. Переход, если К > с.
г13+ — 1.1ИК(Р + 1). 1.1МК(г)3) +- КОЧЕК. 11МК(КОЧЕК;- 1) +- г)3 1. ь Р г13 ь Б1ХЕ(Р). 1. +- Р + К. гА +- -К. 512Е0. — 1) +- К, ТАС(1. — 1) ь "-". г13 ь М. ТАС(й) ь "+", установить также 51ХЕ(1) ь г13. шаге С2. Его можно нием) связью с первым как иногда нужно вынадо знать количество 15 16. гП = РО, г12: — Р1, г13: — Р, г14 ш В, г1б = — М. А1 ЕОА М БЕА 3 ЕМТХ 0 Ю1 КОЧЕК )ИР А2 АЗ СИРА 0,1(512Е) )ЕЕ А4 Переход, если М ( 51ХЕ(Р). Ы1 0,1(1.1МК) Р ь 1 1МК(Р). А2 ЕМТ2 -АЧА11,1 г12 +- Р— ЕОС(АЧА11). 32МХ АЗ ЗХМХ ОУЕКРЕОЧ ЕИТХ 1 101 АЧА11(11МК) Л(Р А2 А4 102 0,1Й1МК) БТ2 КОЧЕК КОУЕК ь 1.1МК(Р).
ЮА 0,1(Я12Е) гА = К + — 512Е(Р) — М. ЯОВ М СМРА =с= 1СЕ 1Р 103 1,1(1.1МК) БТ2 0,3(11МК) ЯТЗ 1,20 1МК) ЕМТ2 0,1 1.03 0,1(512Е) 1ИР 2Р 1Н ЯТА 0,1(51ХЕ) 51ХЕ(Р) ь К. 102 0,1(51ХЕ) 1МС2 0,1 СВАИ 0,1(БТХЕ) БТА -1,2(Т51ХЕ) ЮЗ И 2Н ЯТЗ 0,2(Т51ХЕ) 1МСЗ 0,2 ЯТХ -1,3(ТАС) ТАСЬ + 512Е(С) — 1) ь "+". 3 14. (а) Это поле необходимо для определения начала блока на заменить (возможно, с преимуществом перед исходным расположе словом блока (см, также упр. 19) (Ь) Это поле необходимо, так делить более М слов (например, если К = 1) и при освобождении выделявшейся памяти. И ь 51ХЕ(РО). Р1 +- РО + М.
01 101 1.02 ЕИМЯ 1ИС2 105 )ЯМ 02 105 )ЯМ РО 0,1(512Е) 0,2 0,1 0,2(Т51ХЕ) 04 -1,1(15135) 07 Перейти к шагу П4, если ТАС(Р1) = "-". Р2. Перейти к шагу ()7, егли ТАС(РΠ— 1) = "— ". 03 СОЗ АЧА15(СТМК) РЗ. Установить Р +- АЧАП., ЕМТ4 АЧА11 В +- СОС(АЧА11). 1МР 05 Перейти к шагу Р5. 04 1МСБ 0,5 Р4. М <- М+ 312Е(Р1). СОЗ 0,2(11МК) Р +- СТЕК(Р1), 104 1,2(ЫМК) В <- 11МК(Р1 + 1). СМР2 КОЧЕК (Новый код, связанный со свойством 1МЕ э+3 КОЧЕК из упр. 12. ЕМТХ АЧА11 Если Р1 = КОЧЕК, БТХ КОЧЕК установить БОЧЕК < — СОС(АЧА11) .) ОЕС2 О,Б Р1 +- Р1 + 312Е(Р1).
БВБ -1,1(ТЯ12Е) 155 06 Перейти к шагу Рб, если ТАС(РΠ— 1) = "-". 05 БТЗ 0,1(Й1МК) РБ. ЫМК(РО) +- Р. ЯТ4 1,1(01МК) 1.1МК(РО + 1) ь- В. БТ1 1,3(1.1МК) С1МК(Р + 1) ь- РО. БТ1 0,4(11МК) 11МК(В) ь- РО. )МР 08 Перейти к шагу РЗ. 06 ЯТЗ 0,4(С1МК) Рб. 11МК(В) е- Р, БТ4 1,3(11МК) 1.1МК(Р+ 1) е- В. 07 1МСБ 0,5 Р7. М ь- М+ 313Е(РΠ— 1). 1МС1 0,5 РО +- РΠ— 3135(РΠ— Ен 08 ЯТб 0,1(15125) РВ. 313Е(РО) +- М, ТАС(РО) < — "-". ЯТ6 -1,2(ТЯ12Е) 512Е(Р1 — 1) +- М, ТАС(Р1 — 1) <†" †".
З 17. Оба поля 51МК равны СОС(АЧА1Е). 18. Алгоритм А выделяет верхнюю часть большого блока. Когда вся память доступна, метод первого подходящего начинает работу с выделения памяти в старших адресах, од- нако повторно после освобождения зти блоки памяти не резервируются, поскольку обычно подходящие свободные блоки находятся в мла,лших адресах. Таким образом, большой свободный блок, расположенный в начале памяти, при использовании метода первого под- ходящего быстро исчезает. Однако большой блок редко оказывается наиболее подходящим, а потому метод наиболее подходящего оставляет большой блок и начале памяти. 19.
Используйте алгоритм из упр. 12 с исключением из шага А4 ссылок на Б12Е(С вЂ” 1), ТАС(1 — 1) и ТАС(5+31280.) — 1); вставьте также следующие новые шаги между А2 и АЗ. А2я. Установить Р1 ь- Р+ 312Е(Р) . Если ТАС(Р1) = "+", перейти к шагу АЗ. В противном случае установить Р2 < — С1МК(Р1), 51МК(Р2 + 1) +- 11МК(Р1 + 1), С1МК(11МК(Р1 -~- 1)) ь- Р2, 312Е(Р) е- 5125(Р) + 312Е(Р1). Если КОЧЕК = Р1, установить МОЧЕК с- Р2. Повторить шаг А2-'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
