AOP_Tom1 (1021736), страница 70
Текст из файла (страница 70)
(Здесь 1.е и 1. — константы, которые задают общий размер доступной памяти в словах.) Начнем с рассмотрения случая, когда все стеки пусты, т. е. ВАЯЕЦ] =ТОР[)] =1е для 1 < у < и. Предположим также, что ВАЯЕ[в+ 1] = 1., и тогда алгоритм (9) будет применим ДЛЯ 1 = и. При переполнении (ОЧЕВРЬОМ) стека 1 возможны три варианта развития событий. а) Найдем наименьшее А, для которого 1 < )4 < и и ТОР[А] < ВАЯЯ[А+ Ц, если такое А существует.
Теперь переместим все элементы на один узел вверх: СОИТЕИТЯ(1.+ 1) 4 — СОИТЕИТЯ(1) для ТОР[)4) > Ь > ВАЯЕ[1+ 1). (Во избежание утраты информации это следует делать в порндке убывания, а не возрастания значений Е. Если ТОР[А] = ВАЯЕ[1+ Ц, такие перемещения выполнять не потребуется.) Наконец, ВАЯВ[)] +- ВАЯВ[у] + 1 н ТОР[А +в ТОР [)'] + 1 для 1 < ) < /4. Ь) Допустим, что ни одно 14 не удовлетворяет условию (а), но существует такое наибольшее Й, для которого 1 < )4 < 1 и ТОР [В] < ВАЯВ[1+ 1). Переместим все элементы на один узел вниз: СОИТЕИТЯ(Ь вЂ” 1) 4- СОИТЕИТЯ(1.) для ВАЯЕ[А + 1) < 1.
< ТОР[1]. (Это нужно сделать только в порядке возрастания значений 1.) Затем ВАЯЕ[у] +- ВАЯЕ[)] — 1 и ТОР[Я 4- ТОР[у] — 1 для Й < у < 1. с) Допустим, что ТОРЫ = ВАЯЯ[14 + П для всех 14 з~ е Тогда очевидно, что для нового элемента стека нельзя найти свободное пространство, и поэтому работу программы придется прервать. На рис. 4 показан пример конфигурации памяти для случая, когда и = 4, ье = О, Е< = 20, по окончании последовательного выполнения действий (12) 11 11 14 12 ])1 13 11 11 12 14 1)2 1)1' (Здесь 1, и Пу относятся к операциям вставки и удаления в стеке )] а звездочка обозначает переполнение (07ЕВРЬОМ). При этом предполагается, что в начальный момент для стеков 1 — 3 пространство в памяти не выделялось.) Ясно что в начальный момент многих ситуаций переполнения стеков можно избежать, если выбрать оптимальные начальные условия вместо выделения сразу всего доступного пространства в памяти для и-го стека, как предлагается в условии (П).
Например, если предполагается, что размеры всех стеков равны, то следует 1 2 3 4 5 6 7 В 9 10 11 12 13 14 15 10 17 18 10 20 ° -~ л ° сч > В а ° ы о а $ я Ю 4Ч а СЭ ь о) сб ы а м ы оы я ья а1 ю а СР ы Рис. 4. Пример конфигурации памяти после выполнения нескольких операций вставки в удаления.
выбрать следующие начальные условия: / 1' — 11 ВАЯЕ[Я = ТОР[Д = ~ — ](1, — 1в) + 1в длЯ 1 < 7' < и. (13) Алгоритм С (Перераспределение последовательных таблиц). Предположим, что переполнение (ОЧЕ1Ж.ОИ) произошло в стеке 1 согласно условиям (9). После выполнения алгоритма С либо будет исчерпана емкость памяти, либо память будет переупорядочена таким образом, что сможет быть выполнена операция ИОВЕ(ТОР [е3 ) +- Т (Обратите внимание, что значение ТОР [е3 увеличено в (9) еще до применения алхоритма С.) С1.
[Инициализация.] Пусть БОИ е — 1. — 1.о, 1ИС < — О. Выполним шаг С2 ддя 1 < 7' < и. (В результате БОИ будет равно общему размеру доступного пространства в памяти, а 1ИС вЂ” общему количеству последовательных увеличений размеров стеков по завершении последнего распределения памяти.) Выполнив эти действия, перейдем к шагу СЗ. С2.[Сбор статистических данных.] Пусть БОИ < — БОИ вЂ” (ТОР[Д вЂ” ВАЯЕ[33).
Есвя ТОР[Д > ОЕОТОР[Д, то О[Д + — ТОР[Д вЂ” ОЫТОР[Д и 1ИС е- 1ИС + О[Д; в противном случае ОЦ3 < — О, СЗ. [Ресурсы памяти исчерпаны?) Если БОИ < О работа не может быть продолжена. Очевидно, что, обладая определенным опытом работы с некоторой программой. можно предложить более подходящие начальные значения. Однако независимо от типа начального распределения таким образом можно избежать лишь незначительного фиксированного количества событий переполнения, причем этот эффект будет заметен только на начальных стадиях работы программы (см. упр, 17). Другой возможный способ усовершенствования рассматриваемого метода основан на выделении при каждой переупаковке памяти объема свободного пространства, достаточного для размещения более чем одного нового элемента таблицы.
Эта идея была использована Й. В. Гарвиком, который предложил полностью переупаковывать память при каждом событии переполнения на основе изменения каждого стека по окончании последней переупаковки. В его алгоритме используется дополнительный массив значений ОЕРТОР[Д, 1 < 3 < и, которые равны значениям ТОР [Д сразу после предыдущего вьщеления памяти. В исходном состоянии таблицы выглядят так же, как и прежде, т. е. ОЕОТОРЯ = ТОР[Д. Этот алгоритм состоит из следующих шагов. С4. (Вычисление показателей перераспределения памяти.] Пусть о ~- 0.1 х ЯОИ(и, ~3 ~- 0.9 х ЯОИ/1ИО.
[Здесь о и д — дробные, а не целые числа, которые необходимо вычислить с заданной точностью. На следующем этапе доступное пространство будет равпределено среди отдельных списков следующим образом: приблизительно 10% доступной памяти будет распределено поровну среди и стеков, а оставшиеся 90% будут разделены пропорционально увеличению размера стеков со времени предыдущего распределения памяти.) Сб. [Вычисление новых базовых вдресов.] Пусть ИЕЫВАЯЕ[Ц +- ВАЯЕШ и а < — 0; тогда для у = 2,3, ..,и установим такие значения: т <- а + о + О[у — Ц,Я, МЕИВАЯЕ[у] +- ИЕИВАЯЕ[у — Ц + ТОР[у' — Ц вЂ” ВАЯЕ[] — Ц + ~т] — ]и] и а +- т. Сб.
(Переупаковка.] Пусть ТОР [1] +- ТОР [1] — 1. (Таким образом задается истинный размер 1-го стека для того, чтобы не предпринимались попытки переместить информацию за его пределами,) Выполните приведенный ниже алгоритм К, а затем установите ТОРЫ +- ТОР[1] + 1. Наконец., установите 01.ВТОР[1] ~— ТОР[у] для 1 < З < и. 1 Вероятно, наиболее интересной частью всего этого алгоритма является сам процесс перераспределения, который описывается ниже.
Он не совсем тривиален, поскольку одни фрагменты памяти смещаются вниз, а другие — вверх. Очевидно, что очень важно не наложить перемещаемый фрагмент памяти на другую полезную информацию, после чего она может быть полностью утрачена. Алгоритм К (Перемещение последовательных таблиц). Для 1 < у' < п информация, заданная с помощью адресов ВАЯЕ [у] и ТОР []] в соответствии с указанными выше соглашениями, перемещается на новое место, задаваемое с адресами ИЕИВАЯЕ [Д, а сами величины ВАЯЕ[]] н ТОР [у'] после этого принимают новые значения. Данный алгоритм основан на легко проверяемом условии, что перемещаемые вниз данные не должны пересекаться с любыми другими перемещаемыми вверх данными, а также с любыми неперемещаемыми данными.
К1. (Инициализация.] Установить у' +- 1. к2. (поиск начала перемещения.] [теперь все перемещаемые вниз стеки с 1- до эьго перемещены в новое место.) Будем последовательно увеличивать значение 1 с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий: а) ИЕМВАЯЕ []] < ВАЯЕ []]: перейти к шагу КЗ; Ь) у ) п: перейти к шагу В.4.
ВЯ. (Перемещение списка вниз.] Установить б < — ВАЯЕ[у] — МЕМВАЯЕ[у]. Установить СОИТЕИТЯ[Ь вЂ” 6) < — СОИТЕИТЯ[1) для 1. = ВАЯЯ[у] + 1, ВАЯЕ[)] + 2,..., ТОРЫ. (Возможен вариант, когда значение ВАЯЕ[у] равно ТОР[у]; тогда никаких действий предпринимать не следует.) Установить ВАЯЯ[у] < — МЕЫВАЯЕ[1], ТОР[у] < — ТОР[у] — д. Вернуться к шагу К2. К4. (Поиск начала перемещения.] (Теперь все перемещаемые вниз стеки с учго по п-й перемещены в нужное место.) Будем последовательно уменьшать значение у с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий: а) ИЕИВАЯЕ[у] > ВАЯВ [1]; перейти к шагу Кб; Ъ) 1 = 1: прервать выполнение алгоритма.
КБ. ~Перемещение списка вверх.) Установить д < — ИЕИВАЯЕ[)з — ВАЯЕ[)). Установить СОИТЕИТБ[1. + д) +- СОИТЕИТЯ(1) для 1. = ТОР[Я, ТОР[)'3 — 1, ..., ВАЯЯ[)1 + 1. (Как и во время выполнения шага НЗ, здесь возможен такой вариант, когда никаких действий предпринимать не потребуется.) Установить ВАЯЕ[)) +-ИЕИВАЯЕ[)], ТОР[)) е- ТОР[)з +б.
Вернуться к шагу В4. $ Обратите внимание, что стек 1 никогда ие придется перемещать. Следовательно, если известно, какой стек обладает наибольшим размером, для повышения эффективности работы программы его можно расположить первым. В алгоритмах С и Е мы намеренно предположили, что выполняются следующие условия: СИТОР[)3 = — О[Я = — ИЕИВАЯЕ[)'+ 13 для 1 ( ) ( и, т. е. эти три таблицы могут совместно использовать одну и ту же область памяти, поскольку находящиеся в них значения никогда не применяются одновремеиио с возникновением конфликтных ситуаций.
Описанные выше алгоритмы перераспределения предназначены для работы со стеками, хотя. очевидно, их можно легко адаптировать для любых таблиц с относительными адресами, в которых текущая информация хранится между ВАБЕ [)) и ТОР [) 3. Для работы со списками могут применяться и другие указатели (например, РВОИТ[)з и ВЕАЕ[))), что позволяет манипулировать ими так же, как очередями и деками. В упр.
8 этот алгоритм подробно рассмотрен на примере очереди. Математический анализ таких алгоритмов динамического распределения памяти чрезвычайно трудно выполнить. В приведенных ниже примерах можно найти некоторые интересные, хотя и поверхностные, результаты, поскольку в них, в основиом, рассматривается общее повеление. В качестве примера возможного построения теории рассмотрим случай, когда таблицы растут только за счет операций вставки.
При этом игнорируются операции удаления и последующих вставок, которые компенсируют одна другую. Допустим, что каждая таблица заполняется значениями с одинаковой скоростью. Такая ситуация может моделироваться последовательностью операций вставки аыаг,...,а где каждый элемент а; — это целое число от 1 до п [представляющее вставку элемента в верхнюю часть стека а,). Например, последовательность 1, 1, 2, 2, 1 означает две операции вставки в стек 1, две операции вставки в стек 2 и, наконец, еще одну вставку в стек 1. Допустим, что все и возможных реализаций аы аг,..., а,ь являются равновероятными. Каким тогда будет среднее количество операций, необходимых Лля перемещения одного слова из одной ячейки памяти в другую при переупаковке создаваемой таблицыу Для первого алгоритма, когда в исходном состоянии вся доступная память предоставляется и-му стеку, этот вопрос рассмотрен в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
