Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.313

Код, который сохраняет старый указатель фрейма, устанавливает новый указатель фрейма и увеличивает указатель стека, чтобы зарезервировать пространство для локальных переменных, называется прологом процедуры. При выходе из процедуры стек должен быть очищен, и эта задача решается в эпилоге процедуры. Одна из важнейших характеристик компьютера — насколько быстро он может выполнять пролог и эпилог. Если они очень длинные и выполняются медленно, вызывать процедуры оказывается невыгодно. Команды ENTER и LEAVE в Pentium 4 были разработаны специально для того, чтобы эффективно работали прологи и эпилоги процедур. Конечно, они поддерживают определенную модель обращения с указателем фрейма, и, если компилятор поддерживает другую модель, использовать эти команды нельзя.

А теперь вернемся к Ханойской башне. Каждый вызов процедуры добавляет новый фрейм в стек, а каждый выход из процедуры удаляет фрейм из стека. Посмотрим, как используется стек при реализации рекурсивных процедур, и начнем с вызова

towers (3, 1. 3)

На рис. 5.25, а показано состояние стека сразу после вызова процедуры. Сначала процедура проверяет, равно ли п единице, а установив, что п = 3, заполняет к и совершает вызов

towers (2, 1, 2)

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

towers (1, 1, 3)

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

towers (1, 1, 2)

Этот вызов добавляет новый фрейм в стек (рис. 5.25, Э). Печатается еще одна строка. После выхода из процедуры фрейм удаляется из стека. Вызовы процедур

продолжаются до тех пор, пока не завершится выполнение первой процедуры и пока фрейм, изображенный на рис. 5.25, я, не будет удален из стека. Чтобы лучше понять, как работает рекурсия, нужно, использовав только ручку и бумагу, полностью воспроизвести выполнение процедуры

towers (3, 1. 3)

Сопрограммы

В обычной последовательности вызовов между вызывающей и вызываемой процедурами есть очевидное различие. Рассмотрим процедуру А, которая вызывает процедуру В (рис. 5.26).

Рис. 5.26. Выполнение вызванной процедуры всегда начинается с ее начала

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

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