Управление вычислительным процессом

Поддержка возможности рекурсивного вызова

Рейтинг:   / 0

Рекурсивный вызов (когда ПП вызывает сама себя) иногда бывает полезен. Классический пример - вычисление факториала с использованием соотношения

N ! = N * (N-1) !

Другой пример - решение задачи о "Ханойской башне".

Рекурсия при вызове подпрограммы может быть как прямая (ПП вызывает сама себя) так и цепная (подпрограмма A вызывает подпрограмму B, та, в свою очеред,ь вызывает подпрограмму C, а затем подпрограмма C вызывает подпрограмму A).

Проблем при рекурсивном вызове несколько:

  1. Запоминание адресов возврата: каждый экземпляр ПП имеет свой адрес возврата;
  2. Каждый экземпляр ПП должен иметь собственные наборы внутренних переменных;
  3. Иногда требуется, чтобы экземпляры ПП, вызванные позднее, имели доступ к внутренним переменным ранее вызванных экземпляров.

Решение всех этих проблем обеспечивается, когда при вызове ПП в стеке выделяется блок ячеек (стековый кадр) для параметров и временных переменных очередного экземпляра ПП (как в примере, рассмотренном выше). Адресацию внутри стекового кадра удобно делать относительно какого-либо его адреса. Для этого перед вызовом ПП параметры помещаются в стек:

push           par1
push           par2
call              subr

Вначале ПП применяется, как мы уже видели, типовая последовательность команд:

subr:           push      bp; запоминание старого значения регистра базы bp
mov        bp,sp;             передача в bp адреса начала стекового кадра

Теперь можно к локальным переменным ПП обращаться, используя адресацию относительно регистра базы:

mov          ax,[bp+4]
mov          bx,[bp+6]

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

enter frmsiz, level

Первый параметр команды определяет количество байтов, требуемых в стеке для временных (локальных) переменных. Второй параметр показывает уровень "рекурсивности" (для самого внешнего уровня level=1). Для доступа к элементам стекового кадра используется адресный регистр BP, который указывает на начало (самый старший адрес) стекового кадра.

Структура стекового кадра в х86 включает три компонента (см. рисунок ниже):

  • указатель на начало предыдущего стекового кадра (динамическая связь);
  • таблица указателей на начала каждого из ранее созданных кадров (индикатор);
  • локальные переменные.

 

Выполнение команды ENTER:

При выполнении команды делаются следующие действия (описание делается в предположении, что происходит рекурсивный вход в подпрограмму):

  1. TmpREG = SP; Запомнить адрес начала следующего стекового кадра
  2. BP -> в стек; Создание динамической связи
  3. Повторить (level-1) раз:; Создание индикатора BP -=2, [BP] -> в стек; Копирование элементов индикатора из предыдущего
    кадра
  4. TmpREG -> в стек; Добавление в индикатор ссылки на данный кадр
  5. BP = TmpREG; Установить BP на начало создаваемого кадра
  6. SP -= frmsiz; Выделение в стеке блока под временные переменные

Обращение к подпрограммам - обмен данными

Рейтинг:   / 0

При обращении к подпрограмме могут передаваться: сами данные или адрес участка памяти, где находятся данные. Данные могут находиться:

  • а) в регистре/ах, если данных мало или если в процессоре много регистров;
  • б) в стеке;
  • в) в оговоренном известном месте памяти (например, в DEC16 - программная память, слова, следующие за командой вызова ПП).

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

Пример на языке С.

int Calc (int x, int y) {
int iX, iY;
iX=2*x+y;
iY=3*y-x;
return iX*iY;
}

Эта процедура принимает два параметра x и y и возвращает результат вычисления несложного арифметического выражения в глобальную ёпеременную z. В процедуре объявлены две локальные переменные. Далее приведен результат компиляции этой процедуры после его дизассемблирования полноэкранным отладчиком TurboDebugger (см. таблицу ниже).

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

 

После входа в процедуру в bp заносится базовый адрес стекового кадра. Благодаря этому, к параметрам можно получить доступ косвенно-регистровой адресацией через bp с положительным смещением [bp+disp], а к локальным переменным - с отрицательным смещением [bp-disp].

Обращение к подпрограммам - передача управления

Рейтинг:   / 0

Для работы с подпрограммами в составе системы команд любого процессора есть две команды (см. рисунок ниже):

  1. Команда обращения к подпрограмме ОП (для этой команды используются мнемоники call, jsr). Эта команда должна автоматически запоминать адрес возврата, т.е. адрес команды, следующей за командой call. В современных процессорах при выполнении команды обращения к ПП адрес возврата запоминается автоматически в стеке.
  2. Команда возврата из ПП (используются мнемоники ret, rts).

 

Связь с подпрограммой по управлению

Обращение к подпрограммам - сохранение/восстановление контекста

Рейтинг:   / 0

Для обращения к подпрограмме используется специальная команда вызова подпрограммы. В системе команд х86 она имеет мнемонику call.

Минимальный набор действий, которые выполняет такая команда, это:

  1. сохранение адреса возврата, т.е. адреса команды, следующей за call;
  2. загрузка в счетчик команд адреса первой исполняемой команды ПП.

Для возврата из ПП в системе команд есть специальная команда (в i*86 ее мнемоника ret). Эта команда загружает ранее сохраненный адрес возврата в счетчик команд.

В х86 имеются две разновидности команды call: ближний near вызов (внутри текущего сегмента кода) и дальний far вызов (в другой сегмент кода). В случае использования дальнего вызова в стеке сохраняется, наряду со счетчиком команд (e)ip, и сегментный регистр cs.

Соответственно имеются и две команды возврата ret near и ret far. Состояние стека при ближнем и дальнем вызовах иллюстрируется следующим рисунком (см. рисунок ниже).

 

Состояние стека при ближнем и дальнем вызовах

Понятие контекста (вектора состояния): в каждой конкретной точке выполнения программы - содержимое всех переменных элементов (регистров, ячеек памяти), которое требуется установить/восстановить, чтобы стало возможным запустить выполнение программы с этой точки.

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

Рассмотрим типовую последовательность команд, используемую при вызове подпрограммы. Пусть подпрограмма использует два входных параметра (два аргумента) типа int, возвращает значение тоже типа int и использует две локальные переменные. Две команды mov в вызывающей части помещают в стек параметры, после чего выполняется команда вызова подпрограммы call.

Первые две команды подпрограммы сохраняют старое значение ebp (элемент контекста) и устанавливают ebp на адрес внутри стекового кадра. Следующая команда (sub esp,8) занимает в стеке место под две локальные переменные.

Теперь подпрограмма может, используя адресацию косвенно-регистровую со смещением через регистр ebp, иметь доступ к параметрам, используя положительные значения смещения (в примере для доступа к первому параметру смещение должно быть равно 12), и к локальным переменным, используя отрицательные смещения (в примере смещение -8 позволяет обращаться к локальной переменной 2).

Результат, вычисляемый подпрограммой, можно передавать в вызывающую часть разными способами, но чаще всего это делают, помещая результата в регистр перед возвратом из подпрограммы, как сделано в примере. Для освобождения места, занятого локальными переменными, следует вернуть указателю стека то значение, которое он имел в начале подпрограммы (оно хранится в ebp). После этого выполняется команда возвврата ret, использующая сохраненный в стеке адрес возврата в вызывающую часть программы.

После возврата следует освободить место в стеке, занятое параметрами. В нашем примере это делает команда add esp, 8 , однако в архитектуре х86 это может быть сделано с помощью разновидности команды возварата из подпрограммы ret n, она не только осуществляет возварт, но и извлекает из стека (в "никуда") число байтов, указываемое параметром n.

Для облегчения сохранения-восстановления контекста в разных реализациях процессоров могут быть использованы:

1) Специальные команды:

  • В iх86+ команды pusha, popa сохраняют в стеке - восстанавливают регистры данных и адресные в таком порядке: (e)ax, (e)cx, (e)dx, (e)bx, (e)sp, (e)bp, (e)si, (e)di. При этом значение (e)sp берется то, которое было до начала выполнения команды pusha.
  • В Motorola 60ххх есть команды movem (MOVE Multiple), сохраняющие/восстанавливающие регистры в/из памяти. Особенность - можно указать (битовой маской), какие регистры сохранять. Место сохранения указывается с использованием стандартных способов адресации.

2) Несколько экземпляров наборов регистров:

  • TMS9900 - регистров данных и адресов не было вообще. В качестве регистров использовалось несколько ячеек памяти, положение которых в адресном пространстве указывал специальный регистр - указатель рабочей области (аналогично в Transputer фирмы Inmos).
  • Transputer (семейство процессоров фирмы Inmos) - регистров данных/адресов всего 3, и они образуют стек. Переход (и к подпрограмме) производится только, когда стек пуст, поэтому сохранять надо только адрес возврата.
  • IA-64 (Itanium) динамическое переименование регистров в регистровом файле при вызове процедуры (см. Intel IA-64 Architecture Software Developer's Manual, vol.2, IA-64 System Architecture, раздел 6 - IA-64 Register Stack Engine).

Организация иерархической структуры программы

Рейтинг:   / 0

Современные "большие" программы содержат и более команд. Для того чтобы можно было в такой программе разобраться (не говоря уже о том, что ее надо перед этим написать и отладить), программа должна быть структурирована. Основное средство структурирования на уровне системы команд процессора - это поддержка аппаратным уровнем (система команд, способы адресации) организации подпрограмм.

В 60...70 годах развилась манера, называемая "структурным программированием", которая широко использовала подпрограммную структуру и еще ряд договоренностей. Структурное программирование позволило значительно увеличить производительность труда при написании сложных программ и повысить их надежность. Сущность понятия подпрограмма (ПП) состоит в следующем.

Некоторые "законченные" функции требуется выполнять в разных местах программы. Примеры: а) определить сумму элементов массива; б) напечатать какой-либо текст на экране или принтере. После того, как написан и отлажен программный фрагмент, выполняющий подобную функцию, этот фрагмент можно рассматривать как новую мощную команду. Использовать написанный фрагмент можно двумя способами.

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

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

При этом необходимо обеспечить несколько дополнительных действий:

  1. После выполнения ПП управление надо вернуть в место вызова (каждый раз оно может быть разным, т.е. требуется при каждом вызове запоминать адрес возврата) - будем называть это действие связью по управлению.
  2. При передаче управления ПП надо передать ей также и исходные данные (при суммировании элементов массива это могут быть начальный адрес массива и число элементов), а при возврате управления в место вызова надо туда также вернуть и результат (в приведенном примере это сумма массива) - это действие будем называть связью по данным.
  3. Вызываемый фрагмент кода (подпрограмма) может использовать при своей работе ресурсы, такие как регистры процессора и т.п. К моменту вызова эти регистры могут содержать результаты работы предшествующих команд, которые будут нужны в дальнейшем. Совокупность переменных величин (содержимых регистров процессора, ячеек памяти), полностью характеризующих состояние программы, будем называть контекстом программы. При вызове подпрограммы нужно сохранить ту часть контекста вызывающей программы, которую подпрограмма при своей работе может изменить (испортить).
  4. Подпрограмме для работы могут потребоваться локальные переменные величины. Часть из них может располагаться в регистрах, другая часть - в ячейках памяти. Эти переменные нужны только до окончания работы подпрограммы (до возврата в вызывающую программу). При возврате занятую память хорошо бы освободить.
  5. В некоторых случаях одновременно может существовать несколько экземпляров одной подпрограммы, каждая со своим контекстом. Соответственно нужно несколько экземпляров локальных переменных. Простейший пример - рекурсивный вызов, когда подпрограмма вызывает сама себя.

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

Яндекс.Метрика