учебники, программирование, основы, введение в,

 

Машинно-независимый Ассемблер RTL и Ассемблер Intel 80x86. Внешние устройства и прерывания. Виртуальная память и поддержка параллельных задач

RTL: машинно-независимый Ассемблер
Каждый процессор имеет свои специфические команды, наборы регистров и режимы адресации, поэтому программу на Ассемблере невозможно перенести с одной аппаратной платформы на другую. Для того чтобы не зависеть от конкретного процессора, часто используют язык описания команд RTL, от англ. Register Transfer Language — язык перемещения регистров. Фактически RTL представляет собой Ассемблер, не зависящий от конкретного процессора. Многие компиляторы, например, gcc, не переводят программу с языка высокого уровня сразу на язык машинных команд, а сначала транслируют ее на язык RTL. Затем на уровне RTL выполняется оптимизация кода, которая составляет 99% работы компилятора. И лишь на последнем этапе программа c языка RTL переводится на язык команд конкретного процессора. Поскольку RTL максимально приближен к Ассемблеру, трансляция из RTL в конкретный Ассемблер не представляет никакого труда.
Такой подход позволяет сделать компилятор с языка высокого уровня практически независимым от конкретной архитектуры. Зависим лишь модуль, осуществляющий перевод с RTL в Ассемблер, но его реализация требует минимальных усилий.
Мы будем использовать RTL для записи примеров несложных программ в кодах вместо какого-либо конкретного Ассемблера.
В RTL имеется неограниченное число регистров общего назначения
R0, R1, R2, R3, ...
и несколько выделенных регистров:

  1. счетчик команд PC;
  2. указатель стека SP;
  3. регистр флагов CC0 (от слов Conditional Codes), иногда добавляют также дополнительные регистры флагов CC1, CC2, ...;
  4. указатель кадра FP.

Слово памяти с адресом a обозначается в RTL через m[a]. Выражение a может быть константой, регистром или суммой регистра и константы, что соответствует абсолютному, косвенному и относительному режимам адресации. Примеры:
m[1000]; m[R0]; m[FP − 4].
Байт с адресом a обозначается через mb[a], короткое (двухбайтовое) слово — через ms[a].
Арифметические команды, такие, как сложение или умножение, записываются в RTL в естественном виде, например, команда сложения двух регистров R0 и R1, помещающая результат в R2, записывается в RTL в виде
R2 := R0 +R1
Команды перехода записываются следующим образом: фрагмент программы, на который осуществляется переход, отмечается меткой. Метка ставится между командами, т.е. строка с меткой всегда пустая (это позволяет добавлять в текст новые команды, не трогая строку с меткой). Сам переход выполняется с помощью команды goto, после которой указывается метка перехода, например,
L:
. . .
goto L;
Ветвление в RTL реализуется с помощью команд условного перехода, которые в зависимости от состояния различных битов или их комбинаций в регистре флагов CC0 либо осуществляют переход на указанную метку, либо ничего на делают. Например, команда
if (eq) goto L;
осуществляет переход на метку L в случае, когда результат предыдущей команды равен нулю (eq — от слова equal), т.е. в регистре CC0 установлен бит z (от слова zero). Большинство арифметических команд автоматически устанавливают биты-признаки результата в регистре флагов CC0. Очень часто требуется просто сравнить два числа, никуда не записывая результат. Команда сравнения присутствуют в системе команд любого процессора, чаще всего она называется cmp (от слова compare). Логически команду сравнения следует понимать как вычитание двух чисел, при этом результат как бы помещается в регистр флагов. На самом деле, в регистре флагов от результата остаются лишь биты-признаки (равен ли он нулю, больше нуля и т.п.). В RTL команда сравнения двух регистров R0 и R1 записывается следующим образом:
CC0 := R0 − R1;
Результат как бы помещается в регистр флагов CC0.
В командах условного перехода, таких как
if (eq) goto L;
можно использовать следующие условия:
eq     результат равен нулю (equal)
ne     результат не равен нулю (not equal)
g      результат больше нуля (greater)
l      результат меньше нуля (less)
ge     результат больше или равен нулю (greater or equal)
le     результат меньше или равен нулю (less or equal)
Перечисленные сравнения используются для чисел со знаком. Для неотрицательных чисел (например, в случае сравнения адресов памяти) вместо слов "больше" и "меньше" используются слова "выше" и "ниже" (above и below):
a      первое число выше второго (above)
b      первое число ниже второго (below)
ae     первое число выше или равно второму (above or equal)
be     первое число ниже или равно второму (below or equal)
Приведем простой пример реализации конструкции "если":
если R0 == R1
l то R2 := 77;
конец если
На RTL этот фрагмент реализуется так:
СС0 := R0 - R1;
if (ne) goto L;
R2 := 77;
L:
Отметим, что в команде условного перехода используется отрицание условия после слова "если", т.е. фактически условие обхода фрагмента кода после слова "то".

http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gifПримеры программ на RTL и Ассемблере Intel 80x86

Рассмотрим несколько простых примеров программ на "виртуальном Ассемблере" RTL и на конкретном Ассемблере для процессора Intel 80x86.

Вычисление наибольшего общего делителя

Реализуем функцию, вычисляющую наибольший общий делитель двух целых чисел. Мы уже записывали алгоритм вычисления НОД на псевдокоде. На языке Си эта функция выглядит следующим образом:

int gcd(int x, int y) { // цел алг. gcd(цел x, цел y)
    int a, b, r;        // | цел a, b, r;
    a = x; b = y;       // | a := x; b := y;
    while (b != 0) {    // | цикл пока b != 0
        r = a % b;      // | | r := a % b;
        a = b;          // | | a := b;
        b = r;          // | | b := r;
    }                   // | конец цикла 
    return a;           // | ответ := a;
}                       // конец алгоритма

Вместо НОД мы назвали функцию "gcd" (от слов greatest common divizor), поскольку в языке Си русские буквы в именах функций и переменных использовать нельзя. Запишем эту программу на языке RTL. Переменные a, b, r мы будем хранить в регистрах R0, R1, R2.

                     // Вход в функцию:
    push FP;         // сохраним значение FP в стеке;
    FP := SP;        // определим новое значение FP;
    push R1;         // сохраним значения регистров R1
    push R2;         //                           и R2
                     //
    R0 := m[FP+8];   // a := x;
    R1 := m[FP+12];  // b := y;
L1:                  // метка начала цикла
    CC0 := R1 - 0;   //   сравнить b с нулем
    if (eq) goto L2; //   если результат равен нулю,
                     //       то перейти на метку L2
    R2 := R0 % R1;   //   r := a % b;
    R0 := R1;        //   a := b;
    R1 := R2;        //   b := r;
    goto L1          //   перейти на метку L1
L2:                  // метка конца цикла
                     // ответ уже содержится в R0
                     // выход из функции:
    pop R2;          // восстановим значения R2
    pop R1;          //                    и R1
    pop FP;          // восстановим значение FP
    return;          // вернемся в вызывающую программу

Эта программу можно переписать на конкретный Ассемблер, например, на Ассемблер "Masm" фирмы Microsoft для процессоров Intel 80x86. Первое, что надо сделать при переводе с RTL на Ассемблер — это распределить регистры, т.е. задать отображение виртуальных регистров R0, R1, ... на конкретные регистры данного процессора. У процессоров серии Intel 80x86 есть всего 8 общих регистров: это регистры

EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP. 

Процессор Intel сконструирован таким образом, что каждый регистр выполняет в определенных командах свою особую роль (Intel 80x86 — это CISC-процессор; в RISC-процессорах все регистры равноправны). В частности, команда деления всегда использует в качестве делимого длинное восьмибайтовое целое число, содержащееся в паре регистров (EDX, EAX), где старшие байты в регистре EDX. В результате выполнения команды деления вычисляется как частное, так и остаток от деления: частное помещается в регистр EAX, остаток — в регистр EDX.
В данной программе на языке RTL остаток от деления помещается в регистр R2. Поэтому регистр R2 удобно отобразить на регистр EDX, это позволит избежать лишних пересылок результата из одного регистра в другой. Итак, зафиксируем следующее распределение регистров:

R0 — EAX
R1 — EBX
R2 — EDX
FP — EBP
SP — ESP

После того как распределены регистры, остается только переписать каждую строку RTL программы на конкретный Ассемблер. Для этого необходимо знать ограниченный набор команд, реализующих операции языка RTL в конкретном Ассемблере. Например, в нашем случае операция пересылки из одного регистра в другой или из памяти в регистр реализуется командой mov, операция деления реализуется командой div и т.д. Программа на языке Ассемблера Intel 80386 записывается следующим образом:

.386
.model flat, stdcall
.code
 
gcd:                      ; Вход в функцию:
    push    EBP           ; сохраним старое значение EBP
    mov     EBP, ESP      ; определим новое значение EBP
    push    EBX           ; сохраним значения EBX
    push    EDX           ;                 и EDX.
                          ;
    mov     EAX, [EBP+8]  ; EAX := x
    mov     EBX, [EBP+12] ; EBX := y
L1:                       ; метка начала цикла
    cmp     EBX, 0        ;   сравнить EBX с нулем
    je      L2            ;   если результат равен нулю,
                          ;       то перейти на метку L2
    mov     EDX, 0        ;
    div     EBX           ;   EDX := EAX % EBX
    mov     EAX, EBX      ;   EAX := EBX
    mov     EBX, EDX      ;   EBX := EDX
    jmp     L1            ;   перейти на метку L1
L2:                       ; метка конца цикла
                          ; ответ уже содержится в EAX
                          ; выход из функции:
    pop EDX               ; восстановим значения EDX
    pop EBX               ;                    и EBX
    pop EBP               ; восстановим значение EBP
    ret                   ; возврат из функции
 
public gcd
end

Суммирование массива

Рассмотрим еще один простой пример программы на Ассемблере. Требуется вычислить сумму элементов целочисленного массива заданной длины. Прототип этой функции на языке Си выглядит следующим образом:

int sum(int a[], int n);

Функции передается (как обычно, через аппаратный стек) адрес начала целочисленного массива a и его длина n. На RTL функция sum записывается следующим образом:

               // Вход в функцию:
    push FP;        // сохраним старое значение FP;
    FP := SP;       // определим новое значение FP;
    push R1;        // сохраним значения регистров R1,
    push R2;        //                             R2
    push R3;        //                           и R3.
                    //
    R0 := 0;        // обнулим сумму
    R1 := m[FP+8];  // R1 := a  (адрес начала массива)
    R2 := m[FP+12]; // R2 := n  (число эл-тов массива)
L1:                 // метка начала цикла
    CC0 := R2 - 0;  //   сравнить R2 с нулем
    if (le) goto L2; //  если результат  ‹ =  0,
                    //       то перейти на метку L2
    R3 := m[R1];    //   R3 := очередной элемент массива
    R0 := R0 + R3;  //   прибавим очередной эл-т к сумме
    R1 := R1 + 4;   //   увеличим адрес очер. эл-та на 4
    R2 := R2 - 1;   //   уменьшим счетчик необр. эл-тов
    goto L1         //   перейти на метку L1
L2:                 // метка конца цикла
                    // ответ уже содержится в R0
                    // выход из функции:
    pop R3;         // восстановим значения R3,
    pop R2;         //                      R2
    pop R1;         //                    и R1
    pop FP;         // восстановим старое значение FP
    return;         // вернемся в вызывающую программу

В этой программе адрес очередного элемента массива содержится в регистре R1. Сумма просмотренных элементов массива накапливается в регистре R0. Регистр R2 содержит число еще не обработанных элементов массива. В начале программы в регистр R1 записывается адрес начала массива, а в R2—число элементов массива. В теле цикла очередной элемент массива читается из памяти и помещается в регистр R3, затем содержимое R3 прибавляется к сумме R0. После каждого выполнения тела цикла адрес очередного элемента увеличивается на 4 (т.к. целое число занимает 4 байта), а количество необработанных элементов уменьшается на единицу. Цикл продолжается, пока содержимое регистра R2 (т.е. число необработанных элементов) больше нуля.
Для переписывания программы на Ассемблер Intel 80386 зафиксируем следующее распределение виртуальных регистров:

R0 — EAX
R1 — EBX
R2 — ECX
R3 — EDX
FP — EBP
SP — ESP

Программа переписывается таким образом:

.386
.model flat, stdcall
.code
 
sum:                    ; Вход в функцию:
   push    EBP          ; сохраним старое значение EBP
   mov     EBP, ESP     ; определим новое значение EBP
   push    EBX          ; сохраним значения регистров EBX,
   push    ECX          ;                             ECX
   push    EDX          ;                           и EDX.
                        ;
   mov     EAX, 0       ; EAX := 0
   mov     EBX, [EBP+8] ; EAX := a
   mov     ECX, [EBP+12]; ECX := n
L1:                     ; метка начала цикла 
   cmp     ECX, 0       ;  сравнить ECX с нулем
   jle     L2           ;  если результат  ‹  = 0,
                        ;      то перейти на метку L2
   mov     EDX, [EBX]   ;  EDX := очередной эл-т массива
   add     EAX, EDX     ;  EAX := EAX+EDX
   add     EBX, 4       ;  EBX := EBX+4 (адрес след. эл-та)
   dec     ECX          ;  ECX := ECX-1 (счетчик)
   jmp     L1           ;  перейти на метку L1
L2:                     ; метка конца цикла
                        ; ответ содержится в регистре EAX
                        ; выход из функции:
   pop EDX              ; восстановим значения EDX,
   pop ECX              ;                      ECX
   pop EBX              ;                    и EBX.
   pop EBP              ; восстановим значение EBP
   ret                  ; вернемся в вызывающую программу
 
public sum
end

Отметим, что мы использовали команду уменьшения значения регистра на единицу dec (от слова decrement) для реализации следующей строки RTL:

R2 := R2 - 1; // уменьшим счетчик необр. эл-тов

В Ассемблере Intel 80386 она записывается как

dec ECX; ECX := ECX-1

Команда увеличения регистра на единицу обычно записывается как inc (от слова increment). Эти команды, как правило, присутствуют в наборе инструкций любого процессора.
Внешние устройства и аппаратные прерывания
Согласно рассмотренному ранее алгоритму работы компьютера, процессор в любой момент времени выполняет команду, адрес которой находится в регистре PC. После чтения команды из оперативной памяти содержимое PC увеличивается на длину прочитанной команды. Затем команда выполняется, читается следующая команда, и все это повторяется в бесконечном цикле. Однако предусмотрена возможность нарушения этого бесконечного цикла. Она продиктована необходимостью реагировать на события, связанные с внешними устройствами компьютера.
Например, рассмотрим ситуацию, когда нажата клавиша на клавиатуре компьютера. Процессор должен временно прервать выполнение текущей задачи и отреагировать на нажатие клавиши. Затем он, возможно, возобновит выполнение прерванной задачи. Прерывание от клавиатуры относится к классу так называемых аппаратных, или асинхронных, прерываний. Бывают также и синхронные прерывания, которые происходят не в результате внешних событий, а при выполнении команд процессора. Например, синхронное прерывание происходит при попытке выполнить деление на ноль.
Инициатором аппаратного прерывания всегда является какое-либо внешнее устройство. Все внешние устройства подключены к компьютеру параллельно с помощью шины. Шина представляет собой, попросту говоря, набор проводов, соединяющих различные компоненты компьютера. Порядок обмена данными по шине определяется протоколом работы шины. В частности, шина содержит несколько линий, отвечающих за аппаратные прерывания. Когда внешнее устройство определяет наступление некоторого события, требующего немедленной обработки, оно выставляет на шине сигнал аппаратного прерывания. Как правило, это сигнал о наличии прерывания плюс индентификатор прерывания, т.е. целое число, которое устанавливается в виде двоичного кода на соответствующих линиях шины. Процессор по идентификатору прерывания определяет, с каким внешним устройством связано данное прерывание.
Получив по шине сигнал прерывания, процессор прерывает текущую работу и переключается на обработку прерывания. Текущее состояние процессора запоминается в аппаратном стеке. (Состояние процессора определяется набором его самых важных регистров, включающим, например, регистр PC и регистр флагов; конкретный набор запоминаемых в стеке регистров зависит от конструкции процессора.) Затем процессор переходит к выполнению специальной программы-обработчика прерывания. Эта программа определяется по номеру прерывания, выставленному внешним устройством на шине.
Во время выполнения обработчика прерывания другие прерывания запрещены. Программа обработки прерывания должна быть короткой и быстрой, чтобы по возможности не нарушить нормальную работу компьютера. Так, программа обработки прерывания от клавиатуры должна прочесть код нажатой или отпущенной клавиши, для этого процессор читает данные из портов ввода-вывода, соответствующих клавиатуре. (Чтение и запись в порты ввода-вывода также производятся через шину.) Затем команда, соответствующая нажатой или отпущенной клавише, ставится в очередь запросов к драйверу клавиатуры. На этом программа-обработчик прерывания от клавиатуры завершает свою работу. По завершению обработчика прерывания процессор восстанавливает свое состояние, которое было ранее запомнено в аппаратном стеке. После восстановления процессор продолжает работу с того места, на котором она была прервана.
Реально клавиатурная команда будет обработана, когда до нее дойдет черед, т.е. только после выполнения всех команд, поступивших от клавиатуры ранее и сохраненных в очереди клавиатурного драйвера, а также поступивших ранее команд от других внешних устройств.

http://localhost:3232/img/empty.gifВиртуальная память и поддержка параллельных задач

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

Страничная организация памяти

Выполняемые параллельно на одном и том же компьютере различные задачи оперируют одними и теми же адресами памяти. Адрес памяти, который указывается в конкретной команде процессора, называется виртуальным. Для поддержки многозадачности операционная система должна отображать одни и те же виртуальные адреса у разных задач на различные физические адреса памяти.
Для отображения виртуальной памяти на физическую используется механизм страничной организации памяти. Вся физическая память делится на страницы, обычный размер страницы -- 4096 байтов (4 килобайта). Для каждой задачи выделяется специальная область памяти, в которой записаны адреса физических страниц, соответствующих виртуальным страницам. Адрес этой области содержится в специальном регистре процессора. Когда программа обращается к некоторому виртуальному адресу, то он делится на 4096, таким образом определяется номер виртуальной страницы. Затем адрес физической страницы, соответствующий данному номеру, извлекается из специальной области памяти, хранящей физические адреса виртуальных страниц. После этого к вычисленному таким образом адресу физической страницы прибавляется смещение внутри страницы, т.е. остаток от деления виртуального адреса на 4096 (на размер страницы).
Таким образом, разные задачи работают с одними и теми же виртуальными адресами, но с разными физическими адресами, не мешая друг другу.
Отметим еще один очень важный аспект виртуальной памяти. Объем физической памяти может быть меньше, чем объем виртуальной памяти. В этом случае используется механизм своппинга, т.е. вытеснения страниц физической памяти на диск. Считается, что объем пространства на диске компьютера практически бесконечен. Поэтому при нехватке физической памяти страницу виртуальной памяти можно разместить на диске. При обращении к этой странице операционная система сначала загружает ее с диска в физическую память. При этом, возможно, какая-то другая страница вытесняется на диск, чтобы освободить место. Отсюда и слово своппинг (swapping), что в переводе означает ``обмен''. Загрузка виртуальной страницы с диска происходит в результате синхронного прерывания в связи с отсутствием физической страницы в памяти.
Своппинг может замедлить выполнение программы в миллионы раз, это крайне нежелательное явление. Следует писать программы так, чтобы им всегда хватало физической памяти.

Переключение между процессами и нитями

В многозадачной операционной системе процессор периодически переключается между различными задачами. В момент переключения выполнение текущей задачи приостанавливается, ее состояние сохраняется ядром операционной системы, и система переключается на выполнение другой задачи. Такие переключения происходят регулярно по прерываниям от таймера. Таймер -- это внешнее устройство, входящее в конструкцию любого компьютера. Таймер может быть реализован внутри микросхемы процессора или отдельно от нее. Продолжительность кванта времени, в котором не происходит переключение задач, обычно измеряется сотыми или тысячными долями секунды и зависит от операционной системы.
В современных операционных системах различают понятия процесса и нити (thread). В рамках одного процесса могут существовать несколько нитей. Все нити одного процесса разделяют одно и то же виртуальное адресное пространство, соответствующее статическим и глобальным переменным программы. Однако стек, стековая (локальная) память и наборы значений регистров у каждой нити свои.
Каждая нить выполняется по отдельности, поэтому нити иногда называют легковесными процессами (light-weight process). Переключение между нитями происходит аналогично переключению между процессами. Нити очень удобны в программировании, поскольку разные нити параллельно выполняют совместную работу над одними и теми же глобальными переменными, расположенными в статической памяти процесса. Это позволяет избежать сложных механизмов передачи данных между различными процессами, которые приходилось использовать в старых операционных системах до изобретения нитей. На использовании нитей основано, например, программирование графических задач в операционных системах типа Windows. Здесь одна нить отвечает за обработку действий пользователя и поддержку оконного интерфейса (нажатий на мышь, клавиатуру, перерисовку окон и т.п.). Другие нити могут выполнять вычислительную работу и сетевой обмен, поддерживать анимацию и т.п. Выполнять вычислительную работу внутри нити, отвечающей за графический интерфейс, нельзя, потому что длительные вычисления приводят к визуальному подвисанию программы и к замедленным реакциям на действия пользователя.
Для синхронизации нитей и процессов, а также исключения одновременного обращения к критическим данным операционная система предоставляет программисту специальные объекты синхронизации -- семафоры, критические секции, события, мьютексы и др. Идея заключается в том, что для каждого критического набора данных выделяется специальный объект, который может в любой момент времени принадлежать только одной нити. Так, на железных дорогах в старой Англии, когда существовал только один путь, используемый в обоих направлениях, поезд не мог выехать на этот путь, пока машинист не получал в свои руки специальное маркерное кольцо, соответствующее данному перегону. Это исключало встречное движение и столкновение поездов.
Для защиты критических данных используется объект синхронизации типа мьютекс, от англ. MUTual EXclusive -- взаимно исключающий. Нить перед обращением к критическим данным пытается захватить мьютекс, соответствующий этим данным. Если он уже захвачен, то операционная система приостанавливает нить до тех пор, пока объект не будет освобожден. После этого мьютекс передается нити, нить пробуждается и выполняет необходимые действия. По завершении критических действий нить сама должна освободить мьютекс, подобно тому как машинист поезда должен сам оставить маркерное кольцо на станции после проезда участка пути, ``защищенного'' этим кольцом.

 

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика