R5. [Перемещение списка вверх.] Установить 6 NEWBASE[j] - BASE[j]. Установить CONTENTS(L-f <- CONTENTS(L) для L = TOP[j], TOP[j] - 1, BASE[j] + 1. (Как и во время выполнения шага R3, здесь возможен такой вариант, когда никаких действий предпринимать не потребуется.) Установить BASELj] <- NEWBASELj], TOP [j] <- TOP [j] + 6. Вернуться к шагу R4.

Обратите внимание, что стек 1 никогда не придется перемещать. Следовательно, если известно, какой стек обладает наибольшим размером, для повышения эффективности работы программы его можно расположить первым.

В алгоритмах G и R мы намеренно предположили, что выполняются следующие условия:

OLDTOP [j] = D[j] = NEWBASELj-f 1]

для I < j < n, т. e. эти три таблицы могут совместно использовать одну и ту же область памяти, поскольку находящиеся в них значения никогда не применяются одновременно с возникновением конфликтных ситуаций.

Описанные выше алгоритмы перераспределения предназначены для работы со стеками, хотя, очевидно, их можно легко адаптировать для любых таблиц с относительными адресами, в которых текущая информация хранится между BASE[j] и ТОР [j]. Для работы со списками могут применяться и другие указатели (например, FRONT[j] и REAR[j]), что позволяет манипулировать ими так же, как очередями и деками. В упр. 8 этот алгоритм подробно рассмотрен на примере очереди.

Математический анализ таких алгоритмов динамического распределения памяти чрезвычайно трудно выполнить. В приведенных ниже примерах можно найти некоторые интересные, хотя и поверхностные, результаты, поскольку в них, в основном, рассматривается общее поведение.

В качестве примера возможного построения теории рассмотрим случай, когда таблицы растут только за счет операций вставки. При этом игнорируются операции удаления и последующих вставок, которые компенсируют одна другую. Допустим, что каждая таблица заполняется значениями с одинаковой скоростью. Такая ситуация может моделироваться последовательностью операций вставки ai,a2,... ,ат, где каждый элемент - это целое число от 1 до п (представляющее вставку элемента в верхнюю часть стека а). Например, последовательность 1, 1, 2, 2, 1 означает две операции вставки в стек 1, две операции вставки в стек 2 и, наконец, еще одну вставку в стек 1. Допустим, что все п"* возможных реализаций ai,a2,...,am являются равновероятными. Каким тогда будет среднее количество операций, необходимых для перемещения одного слова из одной ячейки памяти в другую при переупаковке создаваемой таблицы? Для первого алгоритма, когда в исходном состоянии вся доступная память предоставляется п-му стеку, этот вопрос рассмотрен в упр. 9. В таком случае среднее количество необходимых операций перемещения равно

Таким образом, как и следовало ожидать, количество операций перемещения прямо пропорционально квадрату ко.личества последовательных увеличений размера таблицы. То же самое верно и для отдельных стеков с неравновероятными реализациями (см. упр. 10).

На основе этого анализа можно сделать следующий вывод: при значительном количестве операций встабки элементов в таблицы количество перемещений может быть очень большим. Это своеобразная компенсация за возможность компактной упаковки большого количеЬтва последовательных таблиц. Для анализа алгоритма G до сих пор не предложено ни одной теоретической модели, и маловероятно, что какая-либо простая теория сможет адекватно описать характеристики реальных таблиц при таких условиях работы. Однако в упр. 18 предлагается анализ самого неблагоприятного случая с оценкой времени выполнения, которое будет не таким большим, если память исчерпана не полностью.

Как показывает опыт, при заполнении памяти наполовину (т. е. когда доступная область занимает половину всей памяти) с помощью алгоритма G перераспределение памяти нужно выполнить лишь в незначительной степени. Здесь важно отметить, что этот алгоритм эффективен при заполнении памяти наполовину, а при практически полном заполнении, по крайней мере, можно достоверно оценить его эффективность.

Рассмотрим, однако, более подробно случай, когда таблицы почти полностью занимают память. Тогда алгоритму R для выполнения перераспределения потребуется очень много времени. Более того, события переполнения (OVERFLOW) будут происходить все чаще и чаще непосредственно перед исчерпанием памяти. Существует весьма ограниченное количество программ, которые способны работать на грани полного исчерпания памяти и без скорого ее переполнения. Причем многим программам, которые в таком режиме работы переполняют память, вероятно, приходится тратить огромное количество времени на перераспределение памяти согласно алгоритмам G и R незадолго до полного исчерпания памяти. К сожалению, недостаточно хорошо отлаженные программы часто приводят к быстрому исчерпанию ресурсов памяти. Во избежание таких затрат можно было бы прервать выполнение алгоритма G на шаге G3, если SUM меньше значения 5min, которое задается программистом для предотвращения выполнения избыточных операций перераспределения памяти. При наличии большого количества последовательных таблиц с изменяемыми размерами вряд ли стоит надеяться на то, что можно будет использовать доступную память на все 100% и избежать ее переполнения.

Исследование алгоритма G было продолжено Д. С. Вайсом и Д. К. Ватсоном (D. S. Wise, D. С. Watson, BIT 16 (1976), 442-450). А. С. Френкель предложил использовать пары стеков, которые увеличиваются по направлению друг к другу (А. S. Fraenkel, Inf. Proc. Letters 8 (1979), 9-10).

УПРАЖНЕНИЯ

► 1. [15] Сколько элементов может одновременно находиться в очереди без возникновения переполнения (OVERFLOW) при выполнении с очередью операций (6, а) и (7, а)?

► 2. [22] Обобщите метод на основе правил (6, а) и (7, а) так, чтобы он был применим для любого дека с менее чем М элементами. Иначе говоря, предложите правила выполнения двух других операций: "вывод элемента с конца" и "ввод элемента с начала".

3. [21] Предположим, что возможности компьютера MIX расширены следующим образом: 1-поле каждой инструкции имеет вид 8I1+I2, где О < Ii < 8, О < I2 < 8. В ассемблере используется команда ОР ADDRESS,Ii :l2 или, как сейчас, ОР ADDRESS,I2, если Ii = 0. Она обозначает сначала "модификацию адреса" Ii для адреса ADDRESS, затем - вьшолнение

"модификации адреса" I2 для результирующего адреса и, наконец, выполнение операции ОР для нового адреса. этом модификация адреса определяется следующим образом.

0: М = А

1: М = А + гИ

2: М = А + г12

6: М = А + г16

7: М = результирующий адрес, определенный по полям ADDRESS,Ii :I2 в ячейке А. При этом не допускается случай, когда li = I2 = 7 в ячейке А. (Обоснование этого ограничения приводится в упр. 5.)

Здесь А обозначает адрес до выполнения операции, а М - результат модификации адреса. Во всех случаях результат будет неопределенным, если значение М не умещается в два байта и знаковое поле. Время выполнения увеличивается на одну единицу для каждой выполненной операхдаи "косвенной адресации" (модификация 7).

В качестве нетривиального примера предположим, что ячейка памяти 1000 содержит NOP 1000,1:7, ячейка 1001 - NOP 1000,2, а индексные регистры 1 и 2 - 1 и 2 соответственно. В таком случае команда LDA 1000,7:2 эквивалентна команде LDA 1004, так как

1000,7:2 = (1000,1:7),2 = (1001.7),2 = (1000.2),2 = 1002,2 = 1004.

a) Используя эти средства косвенной адресации (если это необходимо), покажите, как упростить код в правой части выражений (8), чтобы экономить по две команды при каждом обращении к таблице. Насколько эффективнее будет этот код по сравнению с кодом (8)?

b) Допустим, имеется несколько таблиц, базовые адреса которых хранятся в позициях

BASE + 1, BASE + 2, BASE + 3,---- Как, используя средства косвенной адресации, можно

перенести 1-й элемент из J-й таблицы в регистр А за счет одной команды, предполагая, что I находится в регистре гП, а J - в регистре г12?

c) Каким будет результат выполнения команды ENT4 Х.7, если предположить, что поле (3:3) в ячейке X равно нулю?

4. [25] Допустим, что возможности компьютера MIX расширены так, как в упр. 3. Покажите, как можно выполнить перечисленные ниже действия с помощью одной команды (со вспомогательными константами).

a) Организовать бесконечный цикл за счет непрекращающейся косвенной адресации.

b) Внести в регистр А значение LINK (LINK (х)), в котором переменная связи х хранится в поле (0:2) ячейки X, значение LINK(a;) -в поле (0:2) ячейки хит. д., при условии, что поля (3:3) 6 этих ячейках равны нулю.

c) Внести в регистр А значение LINK (LINK (LINK (х))) при тех же условиях, что и в п. (Ь).

d) Внести в регистр А содержимое ячейки гИ + г12 4- г13 + г14 + г15 + г16.

e) Умножить на четыре текущее значение регистра г16.

5. [35] Предлагаемый в упр. 3 способ расширения возможностей компьютера MIX содержит нежелательное ограничение, которое запрещает использовать "7:7" в косвенно адресованной ячейке.

a) Приведите пример того, что без такого ограничения в компьютере MIX потребовалось бы на уровне аппаратного обеспечения реализовать большой внутренний стек трехбитовых элементов. (Даже для такого мифического компьютера, как MIX, аппаратное обеспечение может оказаться очень дорогим.)

b) Объясните, почему такой стек не нужен при использовании подобного ограничения. Иначе говоря, создайте такой алгоритм, с помощью которого аппаратное обеспечение компьютера может выполнять нужные модификации адреса без использования дополнительной емкости регистра.