Реклама

Наш канал:

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

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

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

Рис. 5.22. Значение счетчика команд как функция от времени (приближенно): без переходов (а); с переходами (б)

Если программист не знает, в какой последовательности процессор будет выполнять команды, это может привести к ошибкам. Такое наблюдение вызвало к жизни известную статью о необходимости избегать в программах оператора goto [55]. Эта статья привела к революции в программировании, одним из результатов которой стало появление операторов, позволяющих лучше структурировать поток управления, чем оператор goto. Естественно, подобные программы в конце концов все равно компилируются в программы уровня 2, содержащие многочисленные переходы, которых требует реализация операторов if, while и тому подобных высокоуровневых структур.

Процедуры

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

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

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

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