Раздел 2. Механизмы последовательного выполнения программ

2.1. Классификация методов замены контекста

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

Целью этого рассмотрения является переход к знакомству с механизмами параллельного выполнения программ, т. е. с механизмами уровня 5.

Будем рассматривать выполнение программы как последовательность вызовов процедур различного вида. Переход от одной процедуры к другой происходит с помощью механизмов ВЫЗОВА и ВОЗВРАТА. При этом происходит ЗАМЕНА и ВОССТАНОВЛЕНИЕ КОНТЕКСТА процедуры.

Контекстом процедуры называют совокупность данных, доступных процессору во время выполнения этой процедуры. Контекст содержит, как правило, состояние процессора (регистры) и контекст памяти.

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

Классификация методов замены контекста приведена ниже:

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

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

Процедуры – это неравноправные программные вызовы, обладающие свойством вложенности.

Сопрограммы – это равноправные программные вызовы.

Процедуры ОС – программные вызовы.

Прерывания инициализируются внешними сигналами.

Исключения инициализируются внутренними событиями.

У всех методов есть некоторые общие свойства. Базовым для всех является ПРОЦЕДУРА. Для наших задач базовым средством являются СОПРОГРАММЫ, которые тоже основаны на механизмах процедур. Поэтому чтобы унифицировать наши с вами знания о процедурах, кратко рассмотрим и их.

2.2. Процедуры как синхронные методы замены контекста

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

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

Т. о. выполнение программы - это переход из одного активного состояния в другое. Этот переход осуществляется инструкциями ВЫЗОВ и ВОЗВРАТ. При этом происходит замена контекста одного активного состояния на контекст другого активного состояния.

Вызов и возврат осуществляются в несколько этапов:

Вызов:

1. Подготовка данных, передаваемых из вызывающей процедуры в вызываемую процедуру;

2. Сохранение контекста вызывающей процедуры;

3. Установление контекста вызываемой процедуры;

4. Создание локальной среды вызываемой процедуры.

Возврат:

1. Подготовка результатов, передаваемых из вызываемой процедуры в вызывающую;

2. Установление контекста вызывающей процедуры.

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

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

Напомню инструкции работы со стеком:

push ax sp = sp-2;

ss:[sp] = ax;

pop ax ax = ss:[sp];

sp = sp + 2;

call Q push cs;

push ip;

cs = seg(Q);

ip = ofs(Q);

ret pop ip

pop cs

int pushf

push cs

push ip

iret pop ip

pop cs

popf

В самом общем виде схема вызова и возврата выглядит следующим образом:

Стек

Лок. среда С

Лок. среда В

Лок. среда А

Код А Вызов В

Код В Вызов С

Код С

Когда выполняется код процедуры А, существует локальная среда А этой процедуры.

Когда происходит вызов процедуры В, в стек над локальной средой А пишутся передаваемые параметры и адрес возврата в А. Затем выделяется место для локальных параметров В и это все называется локальной средой В.

Аналогично происходит и с вызовом С.

При возврате из С локальная среда С разрушается простым смещением вниз вершины стека. Аналогично происходит и с возвратом из В.

Текущая среда в стеке описывается двумя параметрами: База стека и Вершина стека.

При вызове:

1. База стека (старая) -> в стек;

2. База стека (новая) := Вершина стека (старая);

3. Вершина стека (новая) := Вершина стека (старая) + Размер среды;

При возврате:

1. Вершина стека (новая) := База стека (старая);

2. Из стека -> База стека (новая);

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

Рассмотрим пример, который будет необходим для реализации лабораторных работ. Распишем по шагам состояние стека при вызове процедуры, имеющей следующее описание:

void name(int A, int B)

{

int i;

int k;

...

}

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

push A

push B {этап 1 - подготовка передаваемых параметров}

{----------------------------------------------------------------}

push cs {часть действий из call name, влияющих на стек}

push ip {Этапы 2 и 3 - сохранение контекста вызывающей

push bp {процедуры; сохранение старой базы в стеке}

{----------------------------------------------------------------}

mov bp,sp {новая база = старая вершина}

sub sp,4 {новая вершина = старая вершина + размер среды}

{Этап 4 - создание локальной среды}

{ ----------------------------------------------------------------}

Доступ к локальным переменным i и k осуществляется через косвенную адресацию:

i - [bp - 2]

k - [bp - 4]

Также осуществляется доступ к передаваемым параметрам:

B - [bp + 6]

A - [bp + 8]

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

mov sp,bp {вершина стека новая = база стека старая}

pop bp {база стека новая извлекается из стека}

ret 4 {дополнительный сдвиг sp на 4 из-за 2-ух слов – переданных

{параметров А и В}

После последней инструкции стек переходит в состояние до вызова процедуры Name.

Выводы

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

2. Компилятор всегда реализует некоторый протокол операций вызова и возврата. Фрагмент такого протокола приведен ниже:

1. Для параметров, передаваемых по ссылке, в стек заталкивается два слова – адрес соответствующей переменной;

2. Очередность заталкивания параметров в стек соответствует их перечислению в списке формальных параметров;

3. Для функции байтный результат возвращается в AL, слово - в AX; двойное слово - в DX:AX.

4. Меньше, чем слово в стек не заталкивается.

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