ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12158
Скачиваний: 10
4 0 8 Глава 5. Уровень архитектуры команд
место во фрейме. Он может указывать на связующий указатель, как в IJVM, или
на первую локальную переменную. На рис. 5.27 изображен стековый фрейм для
машины с 32-битным словом. При первом вызове процедуры towers в стек поме-
щаются n, i и j, а затем выполняется команда
CALL,
которая помещает в стек адрес
возврата, 1012. Вызванная процедура сохраняет в стеке старое значение FP (1000)
в ячейке 1016, а затем передвигает указатель стека для обозначения места хране-
ния локальных переменных. При наличии только одной 32-битной локальной
переменной (k) SP (Stack Pointer — указатель стека) увеличивается на 4 до 1020.
На рис. 5.27,
а
показан результат всех этих действий.
Первое, что должна сделать процедура после того, как ее вызвали, — это сохра-
нить предыдущее значение FP (так, чтобы его можно было восстановить при вы-
ходе из процедуры), скопировать значение SP в FP и, возможно, увеличить на одно
слово, в зависимости от того, куда указывает FP нового фрейма. В этом примере
FP указывает на первую локальную переменную, а в IJVM LV указывает на свя-
зующий указатель. Разные машины оперируют с указателем фрейма немного по-
разному, иногда помещая его в самый низ стекового фрейма, иногда — в вершину,
а иногда — в середину, как на рис. 5.27. В этом отношении стоит сравнить рис. 5.27
с рис. 4.12, чтобы увидеть два разных способа обращения со связующим указате-
лем. Возможны и другие способы. Но в любом случае обязательно должна быть
возможность выйти из процедуры и восстановить предыдущее состояние стека.
Код, который сохраняет старый указатель фрейма, устанавливает новый указа-
тель фрейма и увеличивает указатель стека, чтобы зарезервировать пространство
для локальных переменных, называется
прологом процедуры.
При выходе из
процедуры стек должен быть очищен, и этот процесс называется
эпилогом про-
цедуры.
Одна из важнейших характеристик компьютера — насколько быстро он
может совершать пролог и эпилог. Если они очень длинные и выполняются мед-
ленно, делать вызовы процедур будет невыгодно. Команды ENTER и LEAVE в машине
Pentium II были разработаны для того, чтобы пролог и эпилог процедуры работа-
ли эффективно. Конечно, они содержат определенную модель обращения с указа-
телем фрейма, и если компилятор имеет другую модель, их нельзя использовать.
А теперь вернемся к задаче «Ханойская башня». Каждый вызов процедуры до-
бавляет новый фрейм к стеку, а каждый выход из процедуры удаляет фрейм из
стека. Ниже мы проиллюстрируем, как используется стек при реализации рекур-
сивных процедур. Начнем с вызова
towers (3. 1, 3)
На рис. 5.27,
а
показано состояние стека сразу после вызова процедуры. Сначала
процедура проверяет, равно ли п единице, а установив, что п=3, заполняет к и совер-
шает вызов
towers (2. 1. 2)
Состояние стека после завершения этого вызова показано на рис. 5.27,
б.
После
этого процедура начинается с начала (вызванная процедура всегда начинается
с начала). На этот раз условие п=1 снова не подтверждается, поэтому процедура
снова заполняет к и совершает вызов
towers (1. 1, 3)
Поток управления
409
SP -
FP "
S P - ^
FP-K
k
Старое
значение FP
Адрес
возврата
j=3
i=1
n=3
SP -
FP -
->
>
k
Адрес
возврата
Старое
значение FP
=1000
j=2
i=1
n=2
k=2
Старое
значение FP
Адрес
возврата
j=3
i=1
n=3
->
Г
>
>
k
Старое
-значение FP
=1024
Адрес
возврата
J=3
i=1
n=1
k=3
Старое
значение FP
=1000
Адрес
возврата
j=2
i=1
n=2
k=2
Старое
значение FP
Адрес
возврата
J=3
i=1
n=3
SP -
FP -
k=3
Старое
-значение FP
=1000
Адрес
возврата
j=2
i=1
n=2
k=2
Старое
значение FP
Адрес
возврата
j=3
i=1
n=3
->
>
k=3
Старое
-значение FP
=1024
Адрес
возврата
j=2
i=1
n=1
k=3
Старое
значение FP
=1000
Адрес
возврата
j=2
i=1
n=2
k=2
Старое
значение FP
Адрес
возврата
j=3
i=1
n=3
Адрес
1068
1064
1060
1056
1052
1048
1044
1040
1036
1032
1028
1024
1020
1016
1012
1008
1004
1000
а
б в г д
Рис. 5.27.
Состояние стека во время выполнения программы листинга 5.6
4 1 0 Глава 5. Уровень архитектуры команд
Состояние стека после этого вызова показано на рис. 5.27,
в.
Счетчик команд
указывает на начало процедуры. На этот раз условие подтверждается, и на экран
выводится строка. Затем совершается выход из процедуры. Для этого удаляется
один фрейм, а значения FP и SP переопределяются (см. рис. 5.27,
г).
Затем про-
цедура
продолжает выполняться в адресе возврата:
towers (1. 1. 2)
Это добавляет новый фрейм в стек (см. рис. 5.27, д). Печатается еще одна стро-
ка. После выхода из процедуры фрейм удаляется из стека. Вызовы процедур про-
должаются до тех пор, пока не завершится выполнение первой процедуры и пока
фрейм, изображенный на рис. 5.27,
а,
не будет удален из стека. Чтобы вы лучше
смогли понять, как работает рекурсия, вам нужно произвести полное выполнение
процедуры
towers (3. 1. 3)
используя ручку и бумагу.
Сопрограммы
В обычной последовательности вызовов существует четкое различие между вызы-
вающей процедурой и вызываемой процедурой. Рассмотрим процедуру А, кото-
рая вызывает процедуру В (рис. 5.28).
Процедура В работает какое-то время, затем возвращается к А. На первый взгляд
может показаться, что эти ситуации симметричны, поскольку ни А, ни В не явля-
ются главной программой. И А, и В — это процедуры. (Процедуру А можно было
бы назвать основной программой, но это в данном случае неуместно.) Более того,
сначала управление передается от А к В (при вызове), а затем — от В к А (при
возвращении).
Различие состоит в том, что когда управление переходит от А к В, процедура В
начинает выполняться с самого начала; а при переходе из В обратно в А выполне-
ние начинается не с начала процедуры А, а с того момента, за которым последовал
вызов процедуры В. Если А работает некоторое время, а потом снова вызывает
процедуру В, выполнение В снова начинается с самого начала, а не с того места,
после которого произошло возвращение к процедуре А. Если процедура А вызы-
вает процедуру В много раз, процедура В каждый раз начинается с начала, а про-
цедура А уже никогда больше с начала не начинается.
Это различие отражается в способе передачи управления между А и В. Когда А
вызывает В, она использует команду вызова процедуры, которая помещает адрес
возврата (то есть адрес того выражения, которое последует за процедурой) в такое
место, откуда его потом легко будет вытащить, например в вершину стека. Затем
она помещает адрес процедуры В в счетчик команд, чтобы завершить вызов. Для
выхода из процедуры В используется не команда вызова процедуры, а команда
выхода из процедуры, которая просто выталкивает адрес возврата из стека и поме-
щает его в счетчик команд.
Иногда нужно иметь две процедуры А и В, каждая из которых вызывает дру-
гую в качестве процедуры, как показано на рис. 5.29. При возврате из В к А про-
Поток управления
4 1 1
цедура В совершает переход к тому оператору, за которым последовал вызов про-
цедуры В. Когда процедура А передает управление процедуре В, она возвращается
не к самому началу В (за исключением первого раза), а к тому месту, на котором
произошел предыдущий вызов А. Две процедуры, работающие подобным образом,
называются
сопрограммами.
Вызывающая
процедура
Вызываемая
процедура
Процедура А
вызывается
из основной
программы
Процедура А
возвращается *
в основную
программу
Рис. 5.28. Выполнение вызванной процедуры всегда начинается
с самого начала этой процедуры
Сопрограммы обычно используются для того, чтобы производить параллель-
ную обработку данных на одном процессоре. Каждая сопрограмма работает как бы
параллельно с другими сопрограммами, как будто у нее есть собственный процес-
сор. Такой подход упрощает программирование некоторых приложений. Он так-
же полезен для проверки программного обеспечения, которое потом будет рабо-
тать на мультипроцессоре.
412
Глава 5. Уровень архитектуры команд
Процедура А
вызывается
из основной
программы
Процедура А
возвращается
в основную
программу
Рис. 5.29. После завершения сопрограммы выполнение начинается с того места, на котором
оно завершилось в прошлый раз, а не с самого начала
Обычные команды
CALL
и
RETURN
не подходят для вызова сопрограмм, поскольку
адрес для перехода берется из стека, как и при возврате, но, в отличие от возврата,
при вызове сопрограммы адрес возврата помещается в определенном месте, чтобы
в последующем к нему вернуться. Было бы неплохо, если бы существовала коман-
да для замены вершины стека на счетчик команд. Эта команда сначала выталкива-
ла бы старый адрес возврата из стека и помещала бы его во внутренний регистр,
затем помещала бы счетчик команд в стек и, наконец, копировала бы содержание
внутреннего регистра в счетчик команд. Поскольку одно слово выталкивается из
стека, а другое помещается в стек, состояние указателя стека не меняется. Такая
команда встречается очень редко, поэтому в большинстве случаев ее приходится
моделировать из нескольких команд.
Ловушки
Ловушка (trap)
— это особый тип вызова процедуры, который происходит при
определенном условии. Обычно это очень важное, но редко встречающееся усло-
вие. Один из примеров такого условия — переполнение. В большинстве процессо-
ров, если результат выполнения арифметической операции превышает самое боль-