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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

13
Начало
памяти
Низ Верх Верх Низ Конец
памяти
Ситуация ПЕРЕПОЛНЕНИЕ не возникнет до тех пор, пока суммар-
ный объём обоих списков не исчерпает всё свободное пространство в
памяти. Такое распределение памяти используется очень часто.
Можно легко убедиться в том, что не существует способа, который
позволяет хранить три и более стека переменного размера так, чтобы:
1) ПЕРЕПОЛНЕНИЕ возникало лишь в случае, когда суммарный
размер всех списков превысит отведённую для них область памяти;
2) «нижний» элемент каждого списка имел фиксированный адрес.
Если удовлетворять первому условию, то придётся нарушить вто-
рое. Это означает, что базовый адрес L
0
в формуле (1) не является более
константой и никакой указатель не может быть абсолютным адресом.
Кроме того, все ссылки должны быть относительны L
0
.
Предположим, что имеется n стеков, BASE [i] – базовый адрес, а
TOP[i] – указатель i-го стека. Тогда алгоритмы включения и исключения
узлов становятся такими:
(Включение) TOP [i] ← TOP [i] + 1; если TOP [i] > BASE [i + 1],
то ПЕРЕПОЛНЕНИЕ;
в противном случае
CONTENTS (TOP [i]) ← Y.
(8)
(Исключение) если TOP [i] = BASE [i], то НЕХВАТКА;
в противном случае
Y ← CONTENTS (TOP [i]), TOP [i] ← TOP [i] – 1.
В данной ситуации критичность ПЕРЕПОЛНЕНИЯ можно устра-
нить «переупаковав память». Рассмотрим простейший метод переупа-
ковки.
Пусть n стеков располагаются в общей области памяти, состоящей
из ячеек с адресами L такими, что L
0
< L ≤ L
∞
, где L
0
, L
∞
– границы облас-
ти памяти, предоставленной для использования. Можно считать, что вна-
чале все стеки пусты (BASE [i] = TOP [i] = L
0
для всех i). Для правильного
выполнения операции включения (8) при i = n базовый адрес
BASE [n + 1] гипотетического (n + 1)-го стека следует считать равным L
∞
.
Теперь ПЕРЕПОЛНЕНИЕ будет возникать всякий раз, когда в некоторый
стек, за исключением n-го, потребуется записать элементов больше, чем
когда-либо прежде.

Страницы