Файл: Tannenbaum.pdf

Типы команд 403

мое

 байта, слова и т. д., находящегося в ячейке с этим адресом. Такие команды на-

рушают

 типовую безопасность языка Java, но они нужны для С и C++.

В третью категорию входят команды для программ на С и C++, например вы-

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

Сравнение наборов команд

Рассмотренные наборы команд очень сильно отличаются друг от друга. Pentium II —

это классическая двухадресная 32-битная машина CISC. Она пережила долгую
историю, у нее особые и нерегулярные способы адресации, и она содержит множе-
ство команд, которые обращаются к памяти. UltraSPARC II — это современная
трехадресная 64-битная машина RISC с архитектурой загрузки/сохранения, всего
двумя способами адресации и компактным и эффективным набором команд. JVM —
это машина со стековой организацией, практически без способов адресации, с ре-
гулярными командами и очень плотным кодированием команд.

В основу разработки компьютера Pentium II легли три основных фактора:

1. Обратная совместимость.

2. Обратная совместимость.
3. Обратная совместимость.
При нынешнем положении вещей никто не стал бы разрабатывать такую нере-

гулярную машину с таким маленьким количеством абсолютно разных регистров.

По этой причине очень сложно писать компиляторы. Из-за недостатка регистров
компиляторам постоянно приходится сохранять переменные в памяти, а затем
вновь загружать их, что очень невыгодно даже при наличии трех уровней кэш-
памяти. Только благодаря таланту инженеров компании Intel процессор Pentium II

работает достаточно быстро, несмотря на все недостатки уровня команд. Но, как
мы увидели в главе 4, реализация этого процессора чрезвычайно сложна и требует
транзисторов в два раза больше, чем picojava II, и почти в полтора раза больше,
чем UltraSPARC II.

Современная разработка уровня команд представлена в процессоре Ultra-

SPARC II. Он содержит полную 64-битную архитектуру команд (с шиной на 128 би-

тов). Процессор содержит много регистров и имеет набор команд, в котором пре-
обладают трехрегистровые операции, а также имеется небольшая группа команд

LOAD и STORE. Все команды одного размера, хотя число форматов вышло из-под
контроля. Большинство новых разработок очень похожи на UltraSPARC II, но
содержат меньше форматов команд.

JVM — машина совершенно другого рода. Здесь уровень команд изначально

разрабатывался так, чтобы небольшие программы можно было передавать по

Интернету и интерпретировать на программном обеспечении другого компьюте-
ра. Это была разработка для одного языка. Все это привело к использованию стека
и коротким командам разной длины с очень высокой плотностью (в среднем всего

4 0 4 Глава 5. Уровень архитектуры команд

1,8 байта на команду). Создание аппаратного обеспечения, которое выполняет одну

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

Ядро современного компьютера представляет собой сильно конвейеризирован-

ное трехрегистровое устройство загрузки/сохранения типа RISC. UltraSPARC II
просто открыто сообщает об этой структуре пользователю. Pentium II скрывает
эту систему RISC, перенимая старую архитектуру команд и разбивая команды CISC
на микрооперации RISC. Машина picojava II также таит в себе ядро RISC, комбини-
руя несколько команд для получения одной команды RISC.

Поток управления

Поток управления — это последовательность, в которой команды выполняются

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

процедуры влечет за собой изменение потока управления, выполняемая в данный
момент процедура останавливается, и начинается выполнение вызванной про-
цедуры. Сопрограммы связаны с процедурами и вызывают сходные изменения

в потоке управления. Они нужны для моделирования параллельных процессов.

Ловушки (traps) и прерывания тоже меняют поток управления при возникнове-

нии определенных ситуаций. Все это мы обсудим в следующих разделах.

Последовательный поток управления и переходы

Большинство команд не меняют поток управления. После выполнения одной ко-

манды вызывается и выполняется та команда, которая идет вслед за ней в памяти.
После выполнения каждой команды счетчик команд увеличивается на число, соот-
ветствующее длине команды. Счетчик команд представляет собой линейную функ-
цию от времени, которая увеличивается на среднюю длину команды за средний про-
межуток времени. Иными словами, процессор выполняет команды в том же порядке,
в котором они появляются в листинге программы, как показано на рис. 5.24,

 а.

Если программа содержит переходы, то это простое соотношение между по-

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

 б.

 В результате последовательность выполнения команд из самой про-

граммы уже не видна. Если программисты не знают, в какой последовательности
процессор будет выполнять команды, это может привести к ошибкам. Такое на-
блюдение побудило Дейкстру [31] написать статью под названием «Оператор
GOTO нужно считать вредным», в котором он предлагал избегать в программах
оператора goto. Эта статья дала толчок революции в программировании, одним из
нововведений которой было устранение операторов goto более структурирован-
ными формами потока управления, например циклами while. Конечно, эти про-

Поток управления

4 0 5

граммы компилируются в программы второго уровня, которые могут содержать

многочисленные переходы, поскольку реализация операторов if, while и структур
языков высокого уровня требует совершения переходов.

Время

Время

б

Рис. 5.24. Счетчик команд как функция от времени (приближенно):

без переходов (а); с переходами (б)

Процедуры

Самым важным способом структурирования программ является процедура. С од-
ной стороны, вызов процедуры, как и команда перехода, изменяет поток управле-

ния, но в отличие от команды перехода после выполнения задачи управление воз-
вращается к команде, которая вызвала процедуру.

С другой стороны, тело процедуры можно рассматривать как определение но-

вой команды на более высоком уровне. С этой точки зрения вызов процедуры можно
считать отдельной командой, даже если процедура очень сложная. Чтобы понять

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

Особый интерес представляет

 рекурсивная процедура.

 Это такая процедура,

которая вызывает сама себя либо непосредственно, либо через цепочку других
процедур. Изучение рекурсивных процедур дает значительное понимание того, как
реализуются вызовы процедур и что в действительности представляют собой ло-
кальные переменные. А теперь рассмотрим пример рекурсивной процедуры.

«Ханойская башня» — это древняя задача, которая имеет простое решение с

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

диски на колышек 3 по одному диску, но диск большего размера не может нахо-
диться сверху на диске меньшего размера. Говорят, что когда они закончат, насту-

пит конец света. Если вы хотите потренироваться, вы можете использовать пласти-

4 0 6

 Глава 5. Уровень архитектуры команд

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

дисков (п) равно 5.

Колышек 1

Колышек 2 Колышек 3

J

J

Рис. 5.25. Исходное положение в задаче «Ханойская башня» для пяти дисков

Чтобы переместить п дисков с колышка 1 на колышек 3, нужно сначала перене-

сти п-1 дисков с колышка 1 на колышек 2, затем перенести один диск с колышка1
на колышек 3, а потом перенести п-1 диск с колышка 2 на колышек 3. Решение
этой задачи проиллюстрировано на рис. 5.26.

Для решения задачи нам нужна процедура, которая перемещает п дисков с ко-

лышка i на колышек]. Когда эта процедура вызывается,

towers (n I j)

решение выводится на экран. Сначала процедура проверяет, равно ли п единице.
Если да, то решение тривиально: нужно просто переместить один диск с i на j. Если
п не равно 1, решение состоит из трех частей, как было сказано выше, и каждая из
этих частей представляет собой рекурсивную процедуру.

Полное решение показано в листинге 5.6. Вызов процедуры

towers (3. 1 3)

порождает еще три вызова

towers (2 1 2)

towers (I 1.3)

towers (2, 2 3)

Первый и третий вызовы производят по три вызова каждый, и всего получится

семь.

Листинг 5.6.

 Процедура для решения задачи «Ханойская башня»

public void towers (int n. int l. int j)

int k.

if (n==l)

System out рппШС'Переместить диск из" + i + "на" +  j ) . else

k=6-i-j.

towers(n-l. l, k)
towers  ( 1 .  i .  j ) .
towers (n-1. k.  j ) .

Поток управления

4 0 7

Первоначальное

состояние

Сначала

перемещаем

два диска

с колышка 1

на колышек 2

Затем перемещаем

один диск

с колышка 1

на колышек 3

Наконец,

перемещаем

два диска

с колышка 2

на колышек 3

Рис.

 5.26. Решение задачи «Ханойская башня» для трех дисков

Для рекурсивных процедур нам нужен стек, чтобы хранить параметры и ло-

кальные переменные для каждого вызова, как и в IJVM. Каждый раз при вызове

процедуры на вершине стека новый стековый фрейм для процедуры. Текущий
фрейм — это тот фрейм, который был создан последним. В наших примерах стек
растет снизу вверх от малых адресов к большим, как и в IJVM.

Помимо указателя стека, который указывает на вершину стека, удобно иметь

указатель фрейма (FP — Frame Pointer), который указывает на фиксированное