4. Для обработки произвольного символа в последовательности требуется не более постоянного числа операций.

Содержимое

Шаг Вход Выход стека

Рис. 5.3.8. Преобразование выражения из инфиксной формы в постфиксную с помощью алгоритма ITP.

Упражнения 5.3

5.3.1. Рассмотрите следующее арифметическое выражение:

((Xi * Fl) + (Хз * Y)) * * i.) - ((Л + В) -I- С)

(а) Постройте это выражение, используя правила 1-5 для арифметических выражений и представьте эту конструкцию в виде таблицы, аналогичной рис. 5.3.1.

(б) Постройте представление в виде корневого двоичного дерева аналогично рис. 5.3.2.

5.3.2. Вычислите выражение в упр. 5.3.1 для значений Xi=3, Yi=A, Ха=4, Уг=6, А=Ъ, В=7, С=1. Воспользуйтесь рисунком, аналогичным рис. 5.3.3.

5.3.3. Рассмотрите следующее логическое выражение:

(X .OR. У).AND. (( .NOT. (А)) .OR. В) .OR. ( .NOT. (X))

(а) Постройте это выражение, используя правила 1-6 для логических выражений, и представьте эту конструкцию в виде таблицы, аналогичной рис. 5.3.1.

(б) Постройте представление в виде корневого двоичного дерева, аналогичного рис. 5.3.4.

5.3.4. Пройдите корневые двоичные деревья, построенные в упр. 5.3.1 и 5.3.3, в прямом, обратном и концевом порядках.

**5.3.5. Докажите правильность алгоритма IIP.

5.3.6. Примените алгоритм POSTFIX для вычисления выражения в упр. 5.3.1 для значений, заданных в упр. 5.3.2.

5.3.7. Алгоритм POSTFIX (реализация). Запрограммируйте алгоритм POSTFIX,

5.3.8. Примените алгоритм ITP для обработки выражения в упр. 5.3.1.

5.3.9. Напишите в префиксной и постфиксной форме логическое выражение на рис. 5.3.4.

5.3.10. Какое свойство арифметического выражения определяет высоту соответствующего двоичного дерева?

5.3.11. Постройте алгоритм типа POSTFIX для логических выражений.

5.3.12. Постройте алгоритм типа PREFIX для логических выражений.

*5.3.13. Алгоритм POSTFIX (анализ). Оцените верхнюю границу для максимального числа символов, которые должны размещаться в стеке алгоритма POSTFIX. Приведите пример выражения, реализующего наихудший случай.

*5.3.14. Алгоритм ITP (анализ). Повторите упр. 5.3.13 для алгоритма ITP. Каково поведение этого алгоритма в наихудшем случае?

5.4. Страничная организация памяти

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

Строить структуру компьютера так, чтобы каждая программа могла занимать всю память, или невозможно, или неэкономично. Следовательно, структура программ должна быть такова, чтобы различные сегменты могли размещаться в одних и тех же частях памяти в различные моменты времени. Обычно для этого используется метод перекрытия сегментов (оверлейный метод). При этом происходит обмен сегментами программы между оперативной памятью и вспо-могательньми накопителями (диски, барабаны, ленты). Однако по многим причинам предпочтительно освободить программиста от управления размещением сегментов программы.

Другой подход демонстрирует компьютер с виртуальной памятью (КВП). Программист может писать программу так, как будто бы ему

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

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

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

Число слов в странице обычно выбирается равным степени двух, скажем 2". Если число слов в программе равно 2" (n>m), то программа автоматически делится на 2= страниц, где k=n-m. Память также делится на-сегменты такой же длины, называемые страничнылш областями.

Теперь мы опишем последовательность действий при переносе страниц программы в память и из памяти.

1. Программа делится на страницы, некоторые из которых размещаются в памяти. Существенно отметить, что некоторые из этих страниц могут содержать только текст программы, а некоторые могут содержать только данные.

2. Во время исполнения может потребоваться доступ к странице, не находящейся в памяти. Это обнаруживается посредством обращения к таблице страниц, показывающей, находится ли данная страница в памяти.

3. Возникает ст.раничный отказ (прерывание по отсутствию страницы в памяти).

4. Программа КВП, называемая алгоритмом управления страничной памятью, помещает необходимую страницу в память, замещая.