AOP_Tom1 (1021736), страница 124
Текст из файла (страница 124)
[Замечание. На самом деле "ОР" заменяется точкой в языке РЬ/1> а порядок является реверсивным. Так, вместо 'СС ОР АА" в языке Р1./1 используется обозначение "АА. СС", но для данного упражнения зто несущественно.) Покажите, как можно модифицировать алгоритм В, чтобы он удовлетворял соглашениям, принятым для языка РЬ/1, 7. (15) Что означает в языке СОВОЬ команда ИОЧЕ СОЕБЕБРОМОТМО БАЬЕБ ТО РОЕСЕАЯЕЯ по отношению к структуре данных (1)? 8. (10] При каких условиях команда МОЧЕ СОБЕЕБРОМО1МО и ТО 11 означает то же самое, что и команда ИОЧЕ и ТО 5, в соответствии с данным в этом разделе определением? 9. [А/33) Докажите корректность алгоритма С.
10. [33) (а) Как можно было бы выполнить проверку условия МАМЕ(Б) = Рь на шаге Вб, если бы в узлах таблицы данных не было связи ИАМЕ? (Ь) Как можно было бы выполнить проверку МАМЕ(Р) = МАМЕ(Ц) на шаге СЗ, если бы в узлах таблицы данных не было связи МАИЕ? (Предположим, что все другие связи присутствуют, как описано в этом разделе.) ь 11. [33) Какие дополнительные связи или изменения в стратегии создания алгоритмов могли бы ускорить работу алгоритма В или С? 12.
[35) (Задача Д. БЬ Дама (1). МЬ РаЬ|п) ) Рассмотрим представление таблицы данных в последовательных ячейках памяти с помощью всего двух связей для каждого элемента данных: РБЕЧ (так же, как в данном разделе); БСОРЕ (связь с последним простейшим элементом в данной группе). Получим БСОРЕ(Р) = Р тогда и только тогда, когда МОВЕ(Р) представляет собой простейший элемент. Например, таблица данных (Б) будет заменена таким представлением. РБЕУ БСОРЕ А1: Л 04 ВЗ: Л Э7 С7: Л С7 07: Л П7 ЕЗ: Л ЕЗ РБЕУ гЗ; Л 04: Л Н1: Л г5: гЗ 08: 04 БСОРЕ 04 04 09 08 08 РБЕУ БСОРЕ В5: ВЗ В5 С5: С7 09 Е9: ЕЗ Е9 П9: П7 09 09: 08 09 (Ср.
с (5) из раздела 2.3,3.) Обратите внимание, что БОБЕ(Р) является частью дерева под узлом МООЕ(Ц) тогда и только тогда, когда Ц < Р < БСОРЕ(Ц) . Создайте алгоритм, который выполняет функции алгоритма В, если таблица данных имеет такой формат. ° 13. ]ээ] Предложите вместо алгоритма А другой алгоритм для работы с таблицей данных с форматом, описанным в упр, 12. э 14.
]ЯБ] Предложите вместо алгоритма С другой алгоритм для работы с таблицей данных с форматом, описанным в упр. 12, 15. ]Бб] (Задача Дэвида С. Вайса (ПатЫ Б. ЯЪе),) Измените алгоритм А твк, чтобы для стека не использовалось никакое дополнительное пространство. [Укаэаиие. Поля Б18 всех узлов с указателями в стеке в этой формулировке равны Л,] 2,6, ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ В пгидыдущих Рлздкллх было показано, как использование связей приводит к тому, что структурхь данных могут располагаться в памяти непоследовательно; несколько таблиц могут независимо расти и уменьшаться в области общего пула памяти. Однако мы всегда молчаливо предполагали, что узлы имеют один и тот же размер, т.
е, каждый узел занимает некоторое фиксированное количество ячеек памяти, Для очень многих приложений можно найти компромиссное решение, при котором в действительности используется один размер узле для всех структур (например, см. упр. 2). Вместо максимального размера (и потери памяти в малых узлах) зачастую выбирается меньший размер узла и применяется метод, который можно назвать классической филасофиеп связанной памлюш "Если для размещения информации в одном месте не хватает памяти, разместим ее в другом месте и установим с ней связь", Однако для очень большого количества приложений использовать единый размер узлов неразумно, ведь частп необходимы узлы различных размерпв, разделяющие общую область памяти, т, е. нужны алгоритмы для резервирования и освобождекия блоков переменного размера в большой области памяти, причем зти блоки должны састонть из последовательных ячеек памвти, Такие технологии, в целом, незываютси алгоритмами дниа иическаео еыдахеннл памяти.
Зачастую в моделирующих программах требуется динамическое выделение памяти для узлов весьма малого размера (скажем, от одного до десяти слон), В других случаях, чаще всего — в операционных системах, мы, в первую очередь, работаем с довольно болыпнми блоками информации, Такие "точки зрения" приводят к несколько отличающимся подходам к динамическому выделению памяти, хотя в этих методах много общего. Чтобы унифицировать терминологию рассматриваемых подходов, в данном разделе дли обозначения множества последовательных ячеек памяти вместо термина узел будем использовать термины блек и облаешь.
Некоторые авторы начиная примерно с 1076 года называют пул доступной паня тн кучей (Ьеар), однако в настоящем издании этот термин используется только в более традиционном смысле, связанном с приоритетными очередями (см, раздел 6,2.3), А. Резервирование. На рис, 42 представлена типичнаи карта памлгпи, или "шахматная доска",— диаграмма, отображающая текущее состояние некоторого пула памяти, В приведенном примере оиа разбита на 63 блока, которые "зарезервированы" (гееегуег)), т. е. используются вперемешку с 21 "свободным" (?гее) или "доступным" (аувйаЫе) блокам, которь1й не используется, Память компьютера спустя некоторое время работы системы динамическогп выделения, вероятно, будет выглядеть примерно так.
Нан~а первая задача состоит в поиске ответов на два вопроса, а) Как можно представить такое разбиение свободной памяти в компьютере? Ь) Какой алгоритм при данном распределении свободной памяти достаточно хорош для поиски блока из н последовательных свободных ячеек и его резервировании?. Ответ на вопрос (а) кроется, конечно, в содержании списка свободной памяти в некотором месте; почти всегда для зтай цели лучше всего испольэовать ту самую свободную памнть, сведения о которой содержатся в списке (исключением иэ зтогь 0 !опп гппо зооо хппа босо попо тоаа вапа аааа 40000 ааааа ааааа 40000 ааааа ааааа 100000 100000 арезерннронаннан облагты ! 4 Свободнее область; ! ! Рис 42. Кврта памяти.
првиилв может быть дисковви или другая пвмять с различным временем доступв; в таком случае лучше иметь квтвлог доступного пространства отдельно). Следовательно, можно облаешь е44есте доступные сегменты: первое слово амидой свободной области памяти может содержать размер етого блока и адрес следу. ющей свободной области. Свободные блоки могут быть связаны в порядке возрастания илн убыввния по размерам, адресам пвмяти либо в произвольном порядке, Рассмотрим, например, рнс. 42, нв котором иллюстрируется состояние памяти объемом 131072 слова, адресуемых от 0 до 131071.
Чтобы снизить свободные блохи в порядке их вдресов, потребуется переменнвя А7А1(н уквзывающвя нв первый свободный блок (в пишем случке АУА11. рввнв О) ! другие же блоки будут предстввлены следующим обрезом. Адрес 3123 11НН О 101 632 632 42 1466 (17 подобных записей) 73664 1909 77619 77319 33663 Л (Специвльный маркер для последней свяви) Следоввтельно, ячейки 0-100 образуют первый свободный блок; после звнятых облвстей в ячейюпс 101-290 н 291-631, поквзвнных нв рнс, 42, имеется свободное про. стрвнство с адресами 632-673; н т.
д, По поводу вопроса (Ь) понятно, что, если иеобходямв облвсть размером и посо!ь доввтсльных слов, нужно выполнить поиск некоторого блокв нз 4п ) и доступных слов и уменьшить его размер до т — и. (Кроме того, при т = и слебует уделить двииый блок из списки свободных.) В наличии может быть несколько блоков рвзме)юм и или более ячеек, в потому один вопрос превращается в другой: "Конел !вменив облвсть должна быть выделеив7н. Двв основных ответи нв втот вопрос нвпрвшиввются сами собой. можно использовать метод неилучшеео ппдяодлогеео или метод карпово яодяодлщееа.
Э первом случае мы выбирвем облвсть с 4п ячейхвми памяти, где 4п — паимгньцше знвчеиие из имеющихся, не меньшее и, Для твкого выбора может потребоваться поиск по всему списку свободного прострвнствв. Метод первого подходящего, с другой стороны, просто вгнбиреет первую полившуюся облвсть размером не менее и слов. Исторически чаще использовался метод наилучшего подходящего, так как более разумным представляется подход, сохраняющий ббльшие свободные области вна потом", когда онн могут понадобиться, Однако имеется ряд претензий к этому методу: он достаточно медленный, поскольку требует длинного полного поиска, и если он не намного лучше метода первого подходящего в других отношениях, то временем выделения памяти при оценке метода пренебречь нельзя. Еще более важно то, что метод лучшего подходящего имеет тенденцию к увеличению количества блоков свободной памяти малого размера, что обычно нежелательно.
Существует ряд ситуаций, в которых метод первого подходящего превосходит метод наилучшего подходящего. Так, например, предположим, что есть толь(со две свободные области памяти размером 1300 и 1200 и три последовательных запроса на выделение блоков памяти размером 1000, 1100 и 250. Запрос блока раг нером Доступные области, Доступные области, метод первого метод наилучшего подходящего подходящего 1300, 1200 300, 1200 300, 100 50, 100 1300, 1200 1300, 200 200, 200 Нужного блока нет 1000 1100 250 (Противоположный пример приведен в упр. 7.) Поскольку ни один метод явно не превосходит другой, можно порекомендовать метод первого подходящего*. * Видимо, именно из-за отсутствия явного превосходства какого-лабо а~стола над другим программисту во времена ВОЯ предоставлялось право (хотя и не рекомендовалось) изменять стратегию выделения памяти операнионной системой при помощи функции бгв прерывания 21Ь путем выбора метода первого подходящего, лучшего подходягнего или последнего подходянсего (включая в более поздних версиях указание на возможность использования верхней (Ысй) памяти).
Прим. перев. Алгоритм А (Метод первого подходящего). Пусть АЧА11. указывает на первый доступный блок памяти, и предположим, что каждый свободный блок с адресом Р имеет два поля; Я12Е(Р) количество слов в блоке и 1.1ИК(Р) — указатель на следующий свободный блок. Последний указатель равен Л (что указывает на завершение списка блоков свободной памяти). Алгоритм находит и выделяет блок размером И слов (или сообщает о невозможности выделения запрошенной памяти). А1. [Инициализация.[ Установить Ц +- 1.0С(АЧА11.).
(Везде в алгоритме используются два указателя, Ц и Р, которые, вообще говоря, связаны соотношением Р = 1.1ИК(Ц). Мы полагаем, что 11ИК(1.0С(АЧА11.) ) = АЧА11.) А2. [Конец списка?[ Установить Р < — 11ИК(Ц). Если Р = Л, алгоритм завершается неудачно и блок размером И последовательных гзов не может быть выделен. АЗ. [Достаточен ли размер блока?) Если Я12Е(Р) > И, перейти к шагу А4; в противном случае установить Ц +- Р и вернуться к шагу А2. А4. [Выделение блока.) Установить К с — Я12Е(Р) — И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
