Э. Таненбаум - Архитектура компьютера (1127755), страница 111

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 111)

Изучение рекурсивных процедур очень полезно для понимания того, как реализуются вызовы процедур и что в действительности представляют собой локальные переменные, поэтому давайте рассмотрим пример рекурсивной процедуры. Ханойская башня — это название древней задачи, которая благодаря рекурсии имеет простое решение. В одном монастыре в Ханое есть три золотых колышка. На первый из них надето 64 концентрических золотых диска. Диаметр дисков уменьшается снизу вверх.

Второй и третий колышки пусты. Монахи должны по одному перенести все диски на третий колышек, используя при необходимости второй колышек, но при этом после каждой итерации ни на одном из колышков диск большего диаметра не может оказаться на диске меньшего диаметра. Говорят, что когда они закончат, наступит конец света. Если вы хотите потренироваться, можете использовать пластиковые диски, и не 64, а поменьше. (Будем надеяться, что когда вы решите эту задачу, ничего страшного не произойдет. Чтобы произошел конец света, требуются именно 64 диска, причем обязательно золотых.) На рис.

5.23 показана начальная конфигурация для случая, когда число дисков (и) равно 5. Чтобы переместить и дисков с колышка 1 на кольпиек 3, нужно сначала перенести п — 1 дисков с колышка 1 на колышек 2, затем перенести один диск с колышка 1 на колышек 3, потом перенести л — 1 диск с колышка 2 на колышек 3. Решение этой задачи для трех дисков иллюстрирует рис.

5.24. Для решения задачи нам нужна процедура, которая позволяет переместить п дисков с колышка 1 на кольппек з: шнегз (и, и З) поток управления 445 Колышек 1 Колышек 2 Колышек 3 Рис. 6.23. Исходное положение дисков в задаче «Ханойская башня» для пяти дисков Первоначальное состояние Сначала перемещаем даа диска с колышка 1 на колышек 2 Затем перемещаем один диск с колышка 1 на колышек 3 Наконец, перемещаем два диска с колышка 2 на колышек 3 Рис. 5.24.

Решение задачи «Ханойская башня» для трех дисков 446 Глава б. Уровень архитектуры набора команд После вызова этой процедуры решение должно выводиться на экран. Сначала процедура проверяет, равно ли единице значение и. Если да, то решение тривиально: нужно просто переместить один диск с т на 3. Если п не равно 1, решение состоит из трех частей и каждая из этих частей представляет собой рекурсивную процедуру.

Все решение представлено в листинге 5.6. Рассмотрим такой вызов процедуры: Соиегд (3, 1. 3) Этот вызов порождает еще три вызова: соиега 12, 1, 2) тоиега (1, 1, 3) тоиегд (2. 2, 3) Первый и третий вызовы производят по три вызова каждый, и всего получится семь. Листинг 6.6. Процедура для решения задачи «Ханойская башня» роытс тоте Соиега (тта и тпт ., тпт 3) ( тпт к; тт (и == 1) 5уасеэ.оос.ргтпт)п("перекестить диск с " + т + "ка" + 3): е)ае ( К=б-т -3, Сонета(п-1, т.

К): Сонета (1, т, 3). Соиегь (и-1. к, 3), ) Для рекурсивных процедур нам нужен стек, чтобы, как и в 1)'АМ, хранить параметры и локальные переменные каждого вызова. Каждый раз при вызове процедуры на вертпине стека располагается новый стековый фрейм для процедуры.

Текущий фрейм — это фрейм, созданный последним. В наших примерах стек растет снизу вверх, от малых адресов к большим, как и в 1(Ъ"М. Помимо указателя стека (алтае(с Рошгег, БР), который указывает на вершину стека, удобно иметь указатель фрейма (Ргаше Ро(псег, РР), указывающий на заданное место во фрейме, например, на связующий указатель, как в () Ъ'М, или на первую локальную переменную. На рис. 5.25 изображен стековый фрейм для машины с 32-разрядным словом. При первом вызове процедуры соиегз в стек помещаются значения и, 1 и 3, а затем выполняется команда СА(3., которая помещает в стек адрес возврата, 1012.

Вызванная процедура сохраняет в стеке старое значение РР (1000) в ячейке 1016, а затем передвигает указатель стека для обозначения места хранения локальных переменных. При наличии только одной 32-разрядной локальной переменной ((с), указатель стека увеличивается на 4 — до 1020. На рис. 5.25, а показан результат всех этих действий. Поток управления 447 Адрес 1О6В 1064 1О6О 1056 1052 1048 1040 1036 1032 1028 тог4 1ого 1016 1о1г 1ООВ 1004 1ООО б в г а Рис. 6.26.

Состояние стека во время выполнения программы из листинга 5.6 448 Глава б. Уровень архитектуры набора команд Первое, что должна сделать процедура после вызова, — сохранить предыдущее значение РР (так, чтобы его можно было восстановить при выходе из процедуры), скопировать значение ЯР в РР и, возможно, увеличить ЯР на одно слово, в зависимости от того, куда указывает РР нового фрейма. В этом примере РР указывает на первую локальную переменную (хотя в 11Ъ'М регистр 1Х указывал на связующий указатель).

Разные маеиины оперируют указателем фрейма немного по-разному, иногда помещая его в самый низ стекового фрейма, иногда — в вершину, а иногда— в середину, как на рис. 5.25. В этом отношении стоит сравнить рис. 5.25 с рис. 4.10, чтобы познакомиться с двумя разными способами обращения со связующим указателем.

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

Одна нз важнейших характеристик компьютера — насколько быстро он может выполнять пролог и эпилог. Если они очень длинные и выполняются медленно, вызывать процедуры оказывается невыгодно. Команды Ев1Ен и ЕЕАЧЕ в Репе)цш 4 были разработаны специально для того, чтобы эффективно работали прологи и эпилоги процедур. Конечно, они поддерживают определенную модель обращения с указателем фрейма, и, если компилятор поддерживает другую модель, использовать эти команды нельзя. А теперь вернемся к Ханойской башне. Каждый вызов процедуры добавляет новый фрейм в стек, а каждый выход из процедуры удаляет фрейм из стека.

Посмотрим, как используется стек при реализации рекурсивных процедур, и начнем с вызова еоиеге 13. 1. 31 На рис. 5.25, а показано состояние стека сразу после вызова процедуры. Сначала процедура проверяет, равно ли п единице, а установив, что л = 3, заполняет Е и совершает вызов 1оиеге 12. 1. 21 Состояние стека после завершения этого вызова показано на рис.

5.25, б. Далее процедура выполняется снова (вызванная процедура всегда начинается с начала). На этот раз условие л = 1 снова не подтверждается, поэтому процедура снова заполняет 1 и совершает вызов Гоиеге 11, 1. 31 Состояние стека после этого вызова показано на рис. 5.25, в.

Счетчик команд указывает на начало процедуры. На этот раз условие подтверждается, и на экран выводится строка. Затем совершается выход из процедуры. Для этого удаляется один фрейм, а значения РР и 5Р переопределяются (рис. 5.25, г). Далее продолжается выполнение процедуры с адреса возврата: гоиеге 11.

1, 21 Этот вызов добавляет новый фрейм в стек (рис. 5.25, д). Печатается еще одна строка. После выхода из процедуры фрейм удаляется из стека. Вызовы процедур Поток управления 449 продолжаются до тех пор, пока не завершится выполнение первой процедуры и пока фрейм, изображенный на рис. 5.25, а, не будет удален из стека. Чтобы лу ппе понять, как работает рекурсия, нужно, использовав только ручку и бумагу, полностью воспроизвести выполнение процедуры гонегз (3. 1. 31 Сопрограммы В обычной последовательности вызовов между вызывающей и вызываемой про- цедурами есть очевидное различие. Рассмотрим процедуру А, которая вызывает процедуру В (рис.

5.26). Вызывающая процедура Вызываемая процедура Процедура А вызывается из основной программы Процедура А возвращает управление основной программе Рис. 5.26. Выполнение вызванной процедуры всегда начинается с ее начала 450 Глава б. Уровень архитектуры набора команд Процедура В работает какое-то время, затем возвращает управление А. На первый взгляд может показаться, что эти ситуации симметричны, поскольку ни А, ни В не являются главными программами — это процедуры (хотя процедуру А при желании можно было бы назвать основной программой, в данном случае это неправильно). Более того, сначала управление передается от А к В (при вызове), а затем — от В к А (при возвращении).

Характеристики

Список файлов книги