Методы программирования. Громов Ю.Ю - 15 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

15
дыдущего распределения памяти. Первоначально таблицы заполняются,
как и прежде, причём OLDTOP [i] = TOP [i], 1 ≤ i ≤ n.
Алгоритм G. (Перераспределение последовательных таблиц.)
Предполагается, что переполнение случилось в стеке i, в соответст-
вии с операцией включения (8). После выполнения алгоритма окажется,
что память либо израсходована вся, либо будет перераспределена так, что
можно выполнить NODE (TOP [i]) ← Y. Заметим, что TOP [i] был увели-
чен ещё в (8), прежде чем начал работу этот алгоритм.
G1. [Начальная установка.] SUM ← L
∞
– L
0
, INC ← 0.
G2. [Сбор статистики.] Для j = 1, 2, …, n выполнить SUM ← SUM –
(TOP [ j ] – BASE [ j ] ). Если TOP [ j ] > OLDTOP [ j ], то D [ j ] ← TOP [ j ] –
OLDTOP [ j ] и INC ← INC + D [ j ]; в противном случае D [ j ] ← 0.
(В результате значением SUM будет суммарное количество свободного
пространства в памяти, а значением INC – суммарный рост размеров сте-
ков с момента последнего распределения.)
G3. [Память полна?] Если SUM < 0, то дальше работать нельзя.
G4. [Вычисление коэффициентов распределения.] α ← 0.1 × SUM / n,
β ← 0.9 × SUM / INC. (Здесь α и β не целые числа, а дроби и вычислять их
следует с достаточной точностью. На следующем шаге приблизительно
10% свободного пространства будут поделены поровну между всеми сте-
ками, а остальные 90% свободной памяти – пропорционально росту раз-
мера стеков с момента предыдущего распределения.)
G5. [Вычисление новых базовых адресов.] NEWBASE [1] ← BASE[1],
σ ← 0. Для j = 2, 3, …, n τ ← σ + α + D [ j – 1] β, NEWBASE [ j ] ←
NEWBASE [ j – 1] + TOP [ j – 1] – BASE [ j – 1] +
σ−τ
и σ ← τ.
G6. [Переупаковка.] TOP [i] ← TOP [i] – 1. (Этим устанавливается
фактический размер i-го стека для того, чтобы не делалось попыток пе-
ремещать информацию, выходящую за его границу.) Выполнить алго-
ритм R, приведённый ниже, и TOP [i] ← TOP [i] + 1. (Восстановить зна-
чение TOP[i].) Затем OLDTOP [ j ] ← TOP [ j] для 1 ≤ j ≤ n. ■
Возможно, самой интересной частью всего этого алгоритма является
общий процесс переупаковки, который сейчас опишем. Переупаковка
оказывается нетривиальной, поскольку одни части памяти должны сдви-
гаться вверх, а другие вниз. Заметим, что при этих перемещениях важно
не затереть какую-либо полезную информацию.
Алгоритм R. (Перемещение последовательных таблиц.) Для j = 1,
2, …, n информация, специфицированная с помощью BASE [ j ] и TOP [ j ],
перемещается на новые места, заданные с помощью NEWBASE [ j ], а зна-
чения BASE [ j ] и TOP [ j ] соответствующим образом корректируются.
R1. [Начальная установка.] j ← 1. (Заметим, что никогда не возникает
необходимости перемещать стек 1. Поэтому ради эффективности програм-
мист должен поставить наибольший стек первым, если он знает его.)

Страницы