Пример виртуальной машины

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

Простой пример для чего это нужно — фрезерный станок с ЧПУ. И надо на нем выточить голову Сократа из цельного куска металла. Задача, на самом деле, не шибко сложная.

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

Другое дело если разбить программу на элементарные операции, вроде «Резец вверх», «резец вниз», «шаг на n мм», а прошивке скормить последовательность этих микроопераций в виде байт-кода или текстового скрипта. Как все серьезно упрощается. Да и попутно можно нашинковать Платона с Гераклом, было бы желание, да образец для копирования.

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

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

Ну, хватит воды, приведу пример того, что у меня получилось за вечерок курения в код. Код рабочий, но я там ничего не оптимизировал. Так, накидал чтоб работало, до ума доведете сами. Сделано все на базе ядра диспетчера. Я его уже описывал, поэтому работу его функций пояснять не буду

Итак, начну разматывать с самого верха. Есть у нас программа:

  • FWD
  • DLY,T(1000)
  • STP
  • DLY,T(1000)
  • BCK
  • DLY,T(2000)
  • STP
  • OFF

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

  • FWD — ехать вперед.
  • DLY — задержка, в скобочках время в мс
  • STP — стоп
  • BCK — назад
  • OFF — выключение.

Простенькая такая программка истинного партийца — шаг вперед, два шага назад. =)))

Программку я оформил в файле VM_PROG.h, чтобы не путаться где у нас что я буду звать этот скрипт надпрограммой

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define OFF 0
#define BCK 1
#define FWD 2
#define DLY 3
#define STP 4
#define T(X) ((X)& 0xFF),((X)>>8)
 
static u08 VM_PGM[]=
 
{
FWD,            //0
DLY,T(1000),    //1,2,3
STP,            //4
DLY,T(1000),    //5,6,7
BCK,            //8
DLY,T(2000),    //9,10,11
STP,            //12
OFF             //13
};

Тут все просто. Вначале через дефайны мы каждой мнемонике нашего ассемблера присваиваем номер команды (это важно!). А потом забиваем их в стандартный массив во флеше. Массив занял у нас 13 байт. Обрати внимание на то, что команды переменной длины. Т.е. есть простые — однобайтные, а есть двубайтные, например, задержка. Там байт на команду и два байта на выдержку.

Каждой команде присвоена своя процедура, содержимое процедур не важно особо, они для примера. Тут у меня «вперед» это зажигание одного светодиода на Pinboard, а «назад» другого. Команды эти лежат в файле VM.c, а хидеры в VM.h :

1
2
3
4
5
6
7
8
void VM_Back(void)
{
LED_PORT  ^=1<<LED3; 		// Зажигаем диод
VM_PC[0]++;			// Выбор следующей задачи VM
 
SetTask(VM);			// Вброс диспетчера виртуальной 
				// машины на конвейер диспетчера RTOS
}

Как видишь, тут мы что то делаем, а потом увеличиваем счетчик виртуальной машины. Заставляя выбирать ее следующую команду из нашей надпрограммы. Дальше обработчик виртуальной машины закидывается на конвейер ядра RTOS. Впрочем тут нет разницы каким образом организована главная логика программы. Это может быть и конечный автомат или же флаговый автомат. Остальные подзадачи аналогичны.

1
2
3
4
5
6
7
void VM_Stop(void)
{
LED_PORT  ^=1<<LED3;
VM_PC[0]++;
 
SetTask(VM);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void VM_Delay(void)
{
u16 delay;				// Двубайтная переменная
u08 *OneByte;				// Указатель на один байт
 
OneByte = (u08 *)&delay;		// Берем адрес переменной
 
*OneByte = VM_PGM[++VM_PC[0]];	// По байтикам собираем слово
OneByte++;
*OneByte = VM_PGM[++VM_PC[0]];
 
VM_PC[0]++;				// Прощелкиваем счетчиком надпрограммы
 
SetTimerTask(VM,delay);		// Запуск задачи VM через диспетчер таймеров.
}

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

1
2
3
4
void VM_OFF(void)
{
InitVM();
}

Тут просто идет переинициализация VM

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

1
2
3
4
5
6
7
8
9
//VM Task Table 
static TPTR VM_FUNC[] PROGMEM =
   {
   &VM_OFF,		//0
   &VM_Back,		//1
   &VM_Forward,      	//2
   &VM_Delay,		//3
   &VM_Stop		//4
   };

И вот тут важная деталь! Расположение адресов в таблице переходов ТОЧНО соответствует коду операции. Т.е. по нашей надпрограммной системе команд у команды OFF код 0, и ее адрес находится в нулевой ячейке массива VM_FUNC[].

И дальше все получается очень и очень просто! Мы тупо берем байты из которых состоит надпрограмма и по таблице переходов перебрасываемся на нужный обработчик. Переброску осуществляет диспетчер RTOS. Поэтому процедура обработки диспетчера виртуальной машины всего из одной строчки:

1
2
3
4
void VM(void)    // Виртуальная машина
{
SetTask((void*)pgm_read_word_near(VM_FUNC+VM_PGM[VM_PC[0]]));
}

То есть тут только вызов SetTask. Куда мы считываем ему адрес из памяти программ, из массива VM_FUNC, по смещению из массива VM_PGM, а само смещение берем из массива VM_PC. Вот такая вот Кащеева смерть (Кащей, кстати, знаю что читаешь — заходи бухать. Давно тебя не видел).

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

Меняя значение в VM_PC мы можем делать переходы на нужный оператор, а добавив в операнды обработчик условия получим в нашей надпрограмме ветвления и циклы. Если нужно, конечно. Главное правильно вычислять адрес, ведь у нас команды могут быть и многобайтными, а значит легко выполнить данные вместо кода.

Остается один только вопрос, а нафига VM_PC массив? Ведь хватит и одного байта. Хватит, ага, но кто сказал, что у нас может выполняться только одна надпрограмма? ;))))

Почему бы не запустить несколько параллельных процессов, каждая со своим VM_PC?

Надо только в обработчики операторов надпрограммы передавать номер обрабатываемой ветви, да следить чтобы конвейер ядра RTOS не сорвало. Плюс придумать что то с очередью таймеров. Т.к. сейчас DELAY прописывается в единственном числе под каждую задачу. Так что у нас не может быть в очереди таймеров, скажем, два FWD на ожидании. Также надо будет решить over 9000 проблем связанных с блокировками общих ресурсов и прочим загоном многозадачных систем. Но все эти проблемы давно уже описаны и известны, так что курить книжки Таненбаума и дорогу осилит идущий.

Запускается же виртуальная машина просто:

Вначале инициализация программных счетчиков, чтобы поехать точно с начала

1
2
3
4
5
6
7
8
9
void InitVM(void)
{
u08 i;
 
for(i=0;i!=10;i++)
   {
   VM_PC[i]=0;
   }
}

А дальше запускаем ее как обычную задачу из под диспетчера:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(void)
{
InitAll();		// Инициализируем периферию
InitRTOS();		// Инициализируем ядро
InitVM();
RunRTOS();		// Старт ядра.
 
// Запуск фоновых задач.
SetTask(VM);
 
while(1)		// Главный цикл диспетчера
{
wdt_reset();		// Сброс собачьего таймера
TaskManager();		// Вызов диспетчера
}
 
return 0;
}

Ну и, напоследок, как обычно, собранный проект для WinAVR+AVRStudio с этим примером

WM-GCC-RTOS.ZIP

З.Ы.
На сайт теперь прикручена кодопомойка с подсветкой синтаксиса. Цветами я еще поиграюсь, но уже работает. Теперь не будет проблемы с публикацией длинных кусков кода в комментарии. Достаточно разместить ее в кодопомойке, а в коммент вставить ссылку. Ссылка на кодопомойку встроена теперь в поле ответа на коммент (открывается в новом окне).

Кодопомойка

Работает только для зарегистрированных участников.

З.З.Ы.
В Карте Сообщества был добит зверский баг из-за которого многие точки теряли координаты и топились в Атлантическом Океане, где то в районе Африки. Глюк мы подчистили, а также зачистили базу с битыми точками. Битых точек было вагон, поэтому если кто ставил свои отметки — проверьте их наличие, возможно их уже там нет. Надо переставить. Ну и народу там понадобавлялось порядочно. Сама же карта теперь торчит в виде баннера в виде… хм, карты.

З.З.З.Ы.
У меня тут, ВНЕЗАПНО, родственники, ТЫСЯЧИ ИХ! Плюс еще дела мелкие, но по тому же сценарию. Так что не теряйте. Я не забил, просто очень занят :(

50 thoughts on “Пример виртуальной машины”

    1. На асме, кстати, получилось бы в разы проще. По крайней мере в концепции ядра диспетчара что у меня уже есть. Так там таже не нужно было вводить отдельную таблицу переходов — родные задачи работают на адресации по смещениям.

    2. Я тоже надеялся сейчас увидать ассемблер, а тут такое разочарование) Ну не понимаю я СИ. (Правда и ассемблер плохо понимаю, но с СИ у меня вообще несовместимость)

      1. Перед тобой алгоритм. Так на асме ты легко реализуешь эту идею. Если хочешь могу код накидать.

        1. Спасибо, но не нужно. Делать пока всё равно не буду. Читаю только для ознакомления, чтоб хоть примерно понимать как оно работает. А практикуюсь на гораздо более простых задачах. К тому же всегда могу попросить помочь брата (он в СИ шарит).

    3. На асме было бы понятней что да как. Обычно же DI выкладывал код на 2 языках… А сейчас что-то дал слабину… ;)

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

  1. 2 DI и остальным
    НИКОГДА ТАК НЕ ПИШИТЕ
    «for(i=0;i!=10;i++)»
    ЭТО может превратиться в бесконечный цикл
    Только «» «=». Иначе получите глюк который сложно отловить. Да еще этот глюк будет вылазить периодически, еще больше усложняя проблему.

    1. че за глюк. Вместо знаков — пустые кавычки вышли. Видимо, подумали что это теги… Вобщем, нужно ставить знаки «Больше», «Меньше», «Больше либо равно», «Меньше либо равно».

      1. Это хтмл :)))

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

        1. Учитывая то, что значение в переменной «i» вычисляется посредством арифметических действий, его новое значение может содержать не то, что предполагается. Ошибка возникает за счет «ошибки арифметических вычислений» процессора. В данном примере запросто может быть после 9 не 10, как ожидается, а 9,999999999999999999999999 или 10,0000000000000000000000000001. Количество знаков значения не имеет. Имеет значение только то, что это — не 10. И компилятор, которому сказали делать пока не будет РОВНО 10, будет это делать, т.е. этот цикл будет бесконечным…
          Конечно, это не всегда так, однако имеет место быть и вылазит очень редко, но в самый неподходящий момент…

              1. Какой переменную обьявишь, такой и будет. Не думаю, что кто-то переменную цикла обьявляет как REAL. Только вы, может… Кроме того, шаг цикла — тоже обычно величина целая.
                Проблема просто высосана из пальца. В программировании микроконтроллеров всегда стараются максимально использовать работу с целыми числами. И обьем кода сокращает, и работает быстрей. И точность выше, чем с плавающей точкой (при соблюдении некоторых простых правил).

                1. Проблема как раз таки не высосана из пальца, а имеет под собой практику. Если бы это не имело практики, не писал бы.
                  Кстати, в приведенном коде я не нашел объявления типа переменной «i».

                  1. Как это не нашел? А парой строк выше?

                    1
                    2
                    3
                    4
                    5
                    6
                    7
                    8
                    9
                    
                    void InitVM(void)
                    {
                    u08 i;    //<---------------------------
                     
                    for(i=0;i!=10;i++)
                       {
                       VM_PC[i]=0;
                       }
                    }

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

                    1. Это винавровские типы. Гораздо удобней чем писать unsigned char

                    2. Не, бывают оригиналы. Наш препод в универе (хотя какой он нах препод. Аспирант недоученный) делал флоат и i+=0.1 чтобы в одну переменную больше итераций влазило. =)

                    3. всё равно чума. могу согласиться с тем, что максимально кошерно писать с больше/меньше, и сразу нужно привыкать писать максимально кошерно, но устраивать из этого такую ДРАМУ при кодинге для мк — явно перебор.

                    4. «Аспирант недоученный) делал флоат и i+=0.1»
                      а что здесь не так?
                      Численные Алгоритмы последовательных приближений почти все так делаются,

    2. У меня, кстати, тоже есть некоторые претензии :)

      На Си принято (как в том анекдоте про мартышек и банан) писать циклы так:

      int i;
      for(i = 0; i < N; i++){
      //do something
      }

      Это «общепринятая» форма записи, большинство программистов поймет ее без труда. А можно написать, к примеру, так:

      int i = N;
      for(; i!=0; VM_PC[i—] = 0){}

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

      PS А если объявить i как unsigned, то даже в случае изменения i внутри цикла (случайного или злонамеренного) мы застрахуемся от выхода за границы массива.

      1. А где ты у меня такое увидел?

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

        З.Ы.
        Ясное дело ансигнед, смысл делать иначе для счетчика. Теряем половину емкости.

        1. У тебя там написано i!=10, тогда как «правильнее» писать i<10. Такая форма просто воспринимается и фактически стала стандартной.

          Есть неплохая книжка Б. Кернигана (того самого) и Р. Пайка «Практика программирования», там как раз в первой главе заостряют внимание на том, как _принято_ писать, например, инструкцию цикла.

          PS Как-то вникал в одну программу, где выход из switch() был организован не обычным break, а как-то хитро, по-моему, через goto default;. Человек то ли не знал про break, то ли решил, что «обычный учитель информатики» круче всех Керниганов со Страуструпами :)

    1. Ааа позор мне на мои старые костыли. В Атлантическом ессесно. Наша географичка бы высрала тонну кирпичей по этому поводу.

  2. Я предпочитаю использовать команды с параметром. Ведь их характеризует не только время исполнения, но и, например, расстояние, угол, координаты, и другие величины. Отсутствующий параметр или бесконечное выполнение некоторых команд можно задавать параметром «0». Задержку же использовать как отдельную команду, там, где она действительно нужна.
    В общем, вместо:
    FWD
    DLY,T(1000)
    STP
    DLY,T(1000)
    BCK
    DLY,T(2000)
    STP
    OFF

    использовать:
    FWD(1000)
    STP(1000)
    BCK(2000)
    STP(0)
    OFF

    Я, например, в своем роботе сделал 4х байтовый формат команды.
    1 байт — код операции
    2 байт — параметр (например, путь или скорость для левого двигателя)
    3 байт — параметр (например, путь или скорость для правого двигателя)
    4 байт — параметр (или контрольная сумма).
    Неиспользуемые байты параметра заполняются при передаче нулями.
    В большинстве команд было достаточно 2х байт параметра, но 4х байтовая удобнее для передачи пакетом, и дает дополнительный резерв для расширения в будущем.
    Раньше, до использования радиоканала, у меня была переменная длина команд, в виде строки с 0D в конце. Но для использования полной шкалы параметра 0-255 такой вариант не очень удобен, кроме того, при работе по радиоканалу простенькими пакетами типа яяя$CPPP фиксированная длина удобнее.
    («яяя» — для синхронизации приемника, «$» — признак пакета команды, «C» — байт кода операции, «P» — байт параметра).

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

  3. (Позёвывая)
    Вот, помнится, под конец сисилизьма, деток в школе пытались учить программированию на этаком вот языке:
    РИСУЙ
    ВПРАВО
    ВПЕРЕД 50
    ВПРАВО
    ВПЕРЕД 100
    НЕ РИСУЙ

  4. Я на данный момент в поддержку своей книги разрабатываю лабораторную установку, доступ к экспериментам которой предполагаю осуществлять через интернет. Железо у меня все готово (мотор с нагрузкой — l293- AVR- Ethernet (все на Freeuino)), а вот пока еще не решил как осуществить взаимодействие с пользователем. Пользователь должен составить программу действий- задать параметры регулятора и покрутить мотор в одну сторону, в другую с разными скоростями. То есть задача несколько схожа с постом. Это я к тому, что может кто нибудь встречал или сам делал подобные проекты. Извините за офтопик.

  5. В целом идея хорошая, сам на данный момент занимаюсь проектированием фрезерного станка. Тоже поначалу думал писать что то эдакое, как потом оказалось изобретать нужно только прошивку интерпретатор. Сам интерпретируемый код уже изобретен в виде стандарта ISO 6983-1:1982, и именуется «G-код». На вики да и в гугле по нему достаточно информации. Хотя в целом и в нем особой нужды нет, если конечно станок не сильно профессиональный. Программы подобные Mach3 способны сами переваривать G-код, и формировать из него некоторые сигналы для драйверов шаговых двигателей.

  6. Добрый вечер, как-то раньше было интересно сюда заходить, а сейчас как-то грустно….
    Хоть и Ди-Хальт пытается наполнить сайт чужими или просто скучными статьями, но это уже похоже диагноз….. Попытка поддержать коммерческую сторону сайта в ущерб потребительской…… Теперь сайт воспринимаю не более чем даташиит по применению авр.
    Похоже бобик сдох….. Жаль…..

    1. Кому как. НА всех не угодишь, а сайт с первого же дня имел коммерческую направленность. ЗА идею я не работаю никогда. Хотя многим так кажется.

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

  7. Да понятно что не за идею, но не стоит надеяться что сторонние авторские стать, публикуемые раз в 10 дней, будут поддерживать интерес к сайту! Рано Вам еще почивать на лаврах! -)))) Так что подымайте свою ….. тело и давайте авторскую работу!!!

    1. Да это само собой. Просто щас живу фактически на два города, а домой захожу только пожрать да поспать. Очень насыщенное лето выдается.

  8. З.Ы. А где обещанные ИНТЕРЕСсные примеры для Вашей отладочной платы? Бизнес необходимо поддерживать!

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

  9. А если серьезнее, то интересны примеры, использующие функционал платы, т.е. уже имеющуюся обвязку контроллера!

    1. Не все же за тебя будут писать. Программирование — это ведь творческий процесс. Тебе направления показали, дальше сам.

    2. Всю жизнь на чужих примерах не просидишь. Да и скучно это. Попробуй замутить что — нибудь сам. Причем не абстрактную мигалку, а что-нибудь реальное. Лучше всего — робота. Пусть даже механика у него будет примитивная, но можно наращивать до бесконечности датчики, исполнительные устройства, придать ему некое подобие интеллекта… Можно получить удовольствия на годы, пробуя разные варианты, добавляя что-то новое. Особенно если не покупать готового, (вроде Ардуино), а делать все самому. Для корпуса на первое время прекрасно подходит, например, коробка от CD-ROMа. Колеса можно взять готовые или сделать самому. Остальное — по мере надобности и наличия.

  10. концепция виртуальной машины понятна, спасибо за толковое разъяснение. Интересует как теперь по UART передавать команды, в каком формате. Например, если я напряму в COM порт проброшу команду «STP», на UART МК прийдёт набор байтов «535450», тогда как промапить этот код к соответвующему указателю функции ? На ум приходит лишь аналог ассоциативного массива указателей на сами фунции типа array[535450], но я так понимаю, что дергать функции по указателю из массива можно только по индексу, а не по стринге. Есть ли такие решения для AVR ? Или интерпритатору отдавать чистые индексы, потом по индексам из массива будут вызываться те или иные функции, а сами коды виртуальной машишы переводить в индексы на стороне ПК ?

    1. Посмотри как реализована надпрограмма. Видишь там все задефайненные операнды имеют однобайтные номера. Т.е. в пределах одного байта ты задефайнишь 256 команд. Этого более чем достаточно. Плюс операнды можно слать последовательно. Т.е. не нужно гнать по уарту адреса. Можно, но не нужно.

Добавить комментарий

Ваш e-mail не будет опубликован.

Перед отправкой формы:
Human test by Not Captcha