Виртуальные машины

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

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

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

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

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

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

Без виртуальной машины
Машина 1
Виртуальные машины
Транслятор 1
Машина 2
Транслятор 2
Машина 3
Транслятор 3

С использованием виртуальной машины
Машина 1
Виртуальные машины
Виртуальная
машина 1
Машина 2
Машина 3
Транслятор
Виртуальная
машина 2
Виртуальная машина 3

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

Виртуальные машины
Одна из первых широко известных виртуальных машин такого рода была разработана Никлаусом Виртом при написании компилятора Pascal-P.
Этот компилятор генерировал специальный код, названный P-кодом и представляющий собой последовательность инструкций гипотетической стековой машины.

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

Виртуальные машины
Архитектура виртуальной машины Java
Виртуальная машина Java описывается следующими характеристики:
1. Поддерживаемые типы данных
2. Регистры
3. Локальные переменные
4. Стек операндов
5. Область метода
6. Среда выполнения
7. Куча и сборщик мусора
8. Система команд
9. Ограничения виртуальной машины

Виртуальные машины
Поддерживаемые типы данных JVM
– почти все примитивные типы данных Java, за исключением boolean:
byte, short, int, long, float, double, char
– ссылочный тип данных object;
– адрес возврата returnAdress
Для примитивных типов данных контроль соответствия типов осуществляется на этапе компиляции, для ссылочных типов – на этапе исполнения.

Виртуальные машины
Регистры JVM (32-разрядные)
pc
адрес следующей команды, которая будет исполняться виртуальной машиной;
vars
адрес области памяти для хранения локальных переменных метода;
optop
адрес вершины стека операндов;
frame
адрес структуры среды исполнения

Виртуальные машины
Локальные переменные
Локальные переменные метода хранятся в области памяти, начиная с адреса vars.
Для хранения одной переменной отводится 4 байта, значения типа long, double занимают 8 байт (как две переменные).
Для доступа к переменным указывается смещение от начала области (0, 4, 8, 12 и т.д.)

Виртуальные машины
Стек операндов
Стек операндов используется для передачи параметров методам и получения возвращаемого значения метода, а также для выполнения арифметических действий и хранения их результатов.
Каждый элемент стека операндов имеет размер 4 байта, значения всех типов хранятся в одной ячейке стека, значения типов long, double – две ячейки стека.

Виртуальные машины
Область метода
Область метода хранит код метода и таблицы символов метода.

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

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

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

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

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

Виртуальные машины
Куча и сборщик мусора
Во время исполнения Java-программы объекты хранятся в динамически распределяемой памяти – куче.
Периодически осуществляется "сборка мусора" – поиск и уничтожение объектов, не используемых в программе (на которые отсутствуют ссылки).
Для реализации сборщика мусора используются различные алгоритмы, в зависимости от требований системы.

Виртуальные машины
Система команд виртуальной машины
Инструкция виртуальной машины Java состоит из однобайтового кода операции, определяющего действие, которое будет выполнено, и может сопровождаться дополнительными операндами.
Число и размер дополнительных операндов определяется кодом операции.
Если дополнительный операнд содержит более одного байта, то они хранятся в порядке от старшего разряда к младшему.

Виртуальные машины
Ограничения виртуальной машины
Большинство существующих ограничений обусловлены тем, что для представления индексов операндов команд отводится 1-2 байта (8-16 бит).
Список констант ("пул констант") для каждого класса может содержать максимум 65535 элементов.
Длина кода метода ограничена 65535 байтами (включая код метода, таблицу исключений, таблицу номеров строк и таблицу локальных переменных).
Число аргументов в вызове метода ограничено 255.

Виртуальные машины
Система команд виртуальной машины Java
Система команд виртуальной машины Java включает в себя 201 инструкцию. Большинство из них относятся к двум группам:
– команды работы со стеком;
– арифметические команды.
Особенностью системы команд JVM является то, что имеется много схожих инструкций, отличающихся только обрабатываемым типом данных.

Виртуальные машины
Команды загрузки констант в стек (15 команд)
предназначены для загрузки в стек операндов часто используемых констант (null, -1, 0, 1, …)
типconst_значение
Примеры.
iconst_0 – загрузить в стек целочисленную константу 0
dconst_1 – загрузить в стек вещественную константу 0

Виртуальные машины
Команды загрузки констант из пула констант
предназначены для загрузки в стек значений констант, находящихся в пуле констант. Загрузка выполняется безразлично к фактическому типу значений.
ldc индекс
ldc2 индекс

Виртуальные машины
Команды загрузки значений переменных в стек (33 шт.)
предназначены для загрузки в стек значений локальных переменных из списка локальных переменных
типload индекс
Примеры.
iload 5 – загрузить в стек пятую локальную переменную (целочисленную)
dload 10 – загрузить в стек десятую локальную переменную (вещественную)

Виртуальные машины
Особенности команд загрузки переменных:
1. Параметры методов хранятся как локальные переменные (с индексами 0, 1, 2, …)
2. Для часто используемых индексов (0, 1, 2, 3) имеются сокращенные варианты команд, занимающие один байт, например:
fload_0
aload_1

Виртуальные машины
Команды сохранения значения вершины стека в локальной переменной (33 шт.)
извлекают значение из вершины стека операндов и сохраняют их в списке локальных переменных
типstore индекс
Примеры.
istore 5 – сохранить вершину стека в пятой локальной переменной (целочисленной)
dstore 10 – сохранить вершину стека в десятой локальной переменной (вещественной)

Виртуальные машины
Особенности команд сохранения переменных:
Для часто используемых индексов (0, 1, 2, 3) имеются сокращенные варианты команд, занимающие один байт, например:
fstore_0
astore_1

Виртуальные машины
Прочие команды работы со стеком (9 шт.)
К этой группе относятся команды, которые удаляют (pop, pop2), дублируют (dup, dup2), меняют местами верхние элементы стека операндов (swap), а также выполняют другие, более сложные манипуляции со стеком.

Виртуальные машины
Арифметические команды (24 шт.)
Все арифметические команды извлекают из стека два операнда, выполняют арифметическое действие и в стек заносят получившийся результат.
типдействие
Примеры.
iadd – сложение целых чисел
lsub – вычитание длинных целых чисел
fmul – умножение дробных чисел (одинарной точности)
ddiv – деление дробных чисел (двойной точности)
irem – остаток от деления целых чисел
fneg – изменение знака дробного числа

Виртуальные машины
Логические команды (12 шт.)
Логические команды выполняют действия с целыми (длинными целыми) числами: арифметический сдвиг, "и", "или", "исключающее или"
типдействие
Примеры.
iand – логическое "и" с двумя целыми числами
lor – логическое "или" с двумя длинными целыми числами
Логические команды также используются для вычисления истинности булевских выражений.

Виртуальные машины
Команды преобразования типа (15 шт.)
Используются для преобразования значений базовых типов
тип2тип
Примеры.
i2f – преобразование целого числа в дробное (одинарной точности)
d2f – преобразование дробного числа (двойной точности) в дробное число (одинарной точности)
В некоторых случаях требуется прибегнуть к цепочке преобразований, например: d2i i2s (double → short)

Виртуальные машины
Команды для работы с массивами
Используются:
– для создания массивов требуемого типа;
– для вычисления длины существующего массива;
– для загрузки элемента массива в стек;
– для сохранения вершины стека в элементе массива
Примеры.
newarray T_INT – создание целочисленного массива
iaload – загрузка целого числа из массива в стек
iastore – сохранение целого числа в массиве
При обращении к элементам массива
в стек должен быть загружен его индекс

Виртуальные машины
Команды передачи управления
Используются:
– для выполнения условного перехода;
– для выполнения безусловного перехода (goto);
– для организации выбора (switch);
– для вызова и возврата из подпрограмм;
– для вызова и возврата из методов
Команды условного и безусловного переходов используются для организации базовых алгоритмических структур (ветвление, повторение).

Виртуальные машины
Команды условного перехода (вариант 1, 8 шт.)
ifусловие адрес
Извлекается значение из вершины стека. Если условие истинно, осуществляется переход по указанному адресу, например:
ifeq – переход, если значение равно 0
ifgt – переход, если значение больше 0

Виртуальные машины
Команды условного перехода (вариант 2, 8 шт.)
if_типcmpусловие адрес
Из стека извлекаются два значения и сравниваются между собой. Если условие истинно, осуществляется переход по указанному адресу, например:
if_icmpeq – переход, если значения равны
if_icmpne – переход, если значения не равны

Виртуальные машины
Команды вызова методов
выполнение команд связано не только с передачей управления, но и с анализом разного рода таблиц.
invokevirtual – вызывает (виртуальный) метод на основе анализа информации времени выполнения;
invokenonvirtual – осуществляет вызов на основе информации времени компиляции (например, вызов метода родительского класса);
invokestatic – вызывает статический метод класса;
invokeinterface – вызывает метод, предоставленный интерфейсом.

Виртуальные машины
Команды манипулирования с полями объектов команды позволяют установить/прочитать обычное/статическое поле объекта:
getfield putfield
getstatic putstatic
Прочие объектные операции
создать объект, проверить тип объекта

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

Виртуальные машины
Реализация арифметических операций
Машинный код, генерируемый компилятором Java, позволяет вычислять значения арифметических выражений на основе ПОЛИЗ.

Виртуальные машины
Пример. Вычисление выражения S = a * b / 2
ПОЛИЗ выражения: a b * 2 /
Алгоритм вычисления по ПОЛИЗ:
1. Загрузить в стек значение переменной a
2. Загрузить в стек значение переменной b
3. Выполнить умножение
4. Загрузить в стек константу 2
5. Выполнить деление
6. Сохранить результат

Виртуальные машины
На языке Java:
float a,b,S;
S = a * b / 2;
Машинный код JVM:
fload_1 // загрузить в стек значение первой локальной переменной
fload_2 // загрузить в стек вторую локальную переменную
fmul // выполнить умножение
fconst_2 // загрузить в стек константу 2
fdiv // выполнить деление
fstore_3 // результат загрузить в третью локальную переменную

Виртуальные машины
Пример 1. Реализация оператора ветвления
if (выражение) оператор_1; else оператор_2;
Машинный код:
вычислить выражение
ifne оператор_2
оператор_1: …
…
goto конец
оператор_2: …
…
конец:

Виртуальные машины
Пример 2. Реализация оператора повторения
while (выражение) оператор;
Машинный код:
цикл: вычислить выражение
ifne конец
оператор
goto цикл
конец:

Виртуальные машины
Пример 3. Реализация оператора повторения
do оператор; while (выражение);
Машинный код:
цикл: оператор
вычислить выражение
ifne цикл
конец:

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

Виртуальные машины
Основные классы, используемые при реализации стековой ВМ
StackVM
стековая виртуальная машина
VariableStorage
хранилище переменных
Instruction
базовый класс для команд виртуальной машины

Виртуальные машины
Класс StackVM
public class StackVM {
private VariableStorage storage;
private Stack
stack;
public StackVM(VariableStorage storage) {
this.storage = storage;
stack=new Stack
();
}
Экземпляр виртуальной машины использует внешнее (глобальное) хранилище переменных и локальный стек для реализации алгоритма вычисления по ПОЛИЗ.

Виртуальные машины
Вычисление арифметического выражения сводится к последовательному выполнению отдельных команд виртуальной машины.
public double execute(Instruction[] program) {
stack.clear();
for(Instruction instruction:program) {
instruction.execute(stack,storage);
}
return stack.peek();
}
Результат вычислений извлекается из вершины стека.
public double getLastValue() {
return stack.peek();
}

Виртуальные машины
Все команды виртуальной машины реализуются как классы-потомки одного абстрактного класса (интерфейса).
public interface Instruction {
public void execute(Stack
stack, VariableStorage storage);
}

Виртуальные машины
Реализация арифметических команд выполняется тривиально.
public class Add implements Instruction {
public void execute(Stack
stack, VariableStorage storage) {
double op2=stack.pop();
double op1=stack.pop();
stack.push(op1+op2);
}
}

Виртуальные машины
Реализация команд загрузки в стек значений переменных и констант.
public class Variable implements Instruction {
private String variable;
public Variable(String variable) {
this.variable = variable;
}
public void execute(Stack
stack, VariableStorage storage) {
stack.push(storage.getVariable(variable));
}
}
public class Constant implements Instruction {
private double value;
public Constant(double value) {
this.value = value;
}
public void execute(Stack
stack, VariableStorage storage) {
stack.push(value);
}
}

Виртуальные машины
Реализация команды присваивания.
public class Assign implements Instruction {
private String variable;
public Assign(String variable) {
this.variable = variable;
}
public void execute(Stack
stack, VariableStorage storage) {
storage.putVariable(variable, stack.peek());
}
}

Виртуальные машины
Пример. Вычисление дискриминанта
Instruction[] expr1={ new Constant(1), new Assign("a") }; // a=1;
Instruction[] expr2={ new Constant(-5), new Assign("b") }; // b=-5;
Instruction[] expr3={ new Constant(6), new Assign("c") }; // c=6;
Instruction[] expr4={ // d=b*b-4*a*c;
new Variable("b"),
new Variable("b"),
new Mul(),
new Constant(4),
new Variable("a"),
new Mul(),
new Variable("c"),
new Mul(),
new Sub(),
new Assign("d")
};

Виртуальные машины
Пример. Вычисление дискриминанта
Instruction[] expr1={ new Constant(1), new Assign("a") }; // a=1;
Instruction[] expr2={ new Constant(-5), new Assign("b") }; // b=-5;
Instruction[] expr3={ new Constant(6), new Assign("c") }; // c=6;
Instruction[] expr4={ // d=b*b-4*a*c;
new Variable("b"),
new Variable("b"),
new Mul(),
new Constant(4),
new Variable("a"),
new Mul(),
new Variable("c"),
new Mul(),
new Sub(),
new Assign("d")
};

Виртуальные машины
VariableStorage storage = new VariableStorage();
StackVM stackVM = new StackVM(storage);
stackVM.execute(expr1); // a=1;
stackVM.execute(expr2); // b=-5;
stackVM.execute(expr3); // c=6;
stackVM.execute(expr4); // d=b*b-4*a*c;
System.out.println("Ответ: " + stackVM.getLastValue());

Виртуальные машины
Алгоритм объектно-ориентированной реализации виртуальной машины, интерпретирующей синтаксическое дерево программы
При разнообразной обработке структур данных, содержащих объекты различных классов, оказывается удобным следовать паттерну проектирования Visitor ("Посетитель")

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

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

Виртуальные машины
Было Стало
class A { class A {
операция1(); принятьПосетителя();
операция2(); }
} class B {
class B { принятьПосетителя();
операция1(); }
операция2(); class Посетитель1 {
} операцияНадА();
операцияНадB();
}
class Посетитель2 {
операцияНадА();
операцияНадB();
}

Виртуальные машины
Преимущества, получаемые в результате реализации паттерна Visitor ("Посетитель")
Однотипные операции над различными объектами локализуются в одном классе, а не "размазываются" по нескольким классам.
Легко добавлять новые операции над объектами, не изменяя их, а добавляя новые классы-посетители.

Виртуальные машины
Особенности реализации паттерна Visitor ("Посетитель")
1. Все классы-посетители являются предками абстрактного класса, в котором для каждого типа объекта объявлен свой метод вида:
class АбстрактныйПосетитель {
операцияНадА(ТипА объект);
операцияНадB(ТипB объект);
. . .
}

Виртуальные машины
2. В каждом классе-элементе структуры данных объявляется метод, обращающийся к классу-посетителю:
class A {
принятьПосетителя(АбстрактныйПосетитель п) {
п.операцияНадА(this);
}
}
class B {
принятьПосетителя(АбстрактныйПосетитель п) {
п.операцияНадB(this);
}
}

Виртуальные машины
3. Описываются классы-посетители, выполняющие требуемую обработку объектов структуры.
4. Пользователь паттерна должен
а) сформировать требуемую структуру данных;
б) выполнить полный обход структуры данных и для каждого элемента структуры вызвать метод "принятьПосетителя".