Пишем свою операционку для Arduino. Шаг 2 — односвязный список

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

А сегодня мы будем писать на C++ односвязный список. Так как наша операционная система для AVR будет работать в крайне ограниченных по ресурсам условиях, мы будем стараться сэкономить как можно больше места и сделать код быстрее. Без какой-либо структуры данных для хранения списка запущенных (а позднее и приостановленных) задач не обойтись. Односвязный список займет мало программной памяти, потребует очень мало оперативной памяти и в целом хорошо подойдет для наших нужд. Он предельно прост, но при этом мы постараемся максимально его оптимизировать.

forward list

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

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

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

freertos task list

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

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

Так как FreeRTOS написана на C, сам список (xTasksWaitingTermination, например, в коде выше) у нас тоже нетипизированный. Это значит, что если мы случайно перепутаем название и передадим в функцию не тот список, который хотели, то компилятор молча это проглотит, а мы потом будем ловить ошибки на этапе выполнения ОС. В идеале хотелось бы иметь что-то подобное:

В таком случае не ошибешься: какой список указал, в такой задача и добавилась, причем внутренняя структура задачи не испортилась. Так и попробуем сделать. Мы пишем на C++, а не на C, поэтому у нас в руках больше козырей. Структура нашей задачи будет выглядеть гораздо проще (по крайней мере, пока) и компактней:

freertos task list structure

У нас будет класс задачи, который мы унаследуем от классов, каждый из которых будет представлять элемент списка. Таких классов может быть сколько угодно, потому что C++ поддерживает множественное наследование. В итоге, если мы захотим поместить задачу в один список, мы унаследуемся от одного класса-элемента списка, и это займет два дополнительных байта (размер указателя на следующий элемент списка) оперативной памяти. Если захотим иметь возможность включать задачу одновременно в два независимых списка, то унаследуемся от двух классов-элементов, и заплатим 4 байта оперативной памяти. Мы обойдемся без указателя на родительский элемент (потому что C++ и так знает, как его вычислить при таком наследовании). Мы сможем передать в функцию добавления или удаления элемента списка саму задачу, а не указатель на класс-элемент списка, а дальше C++ все разрулит самостоятельно. Если мы что-то сделаем не так, то получим ошибку компиляции. Гораздо меньше возможностей выстрелить себе в ногу.

Пора приступать к кодингу. Сначала добавим в проект вспомогательный файлик defines.h, в котором разместим определения всяких полезных макросов, которые потом будем использовать. Все эти макросы будут представлять из себя объявления различных атрибутов (для функций, классов, структур, параметров функций), которые поддерживаются компилятором GCC/G++.

Переходим к написанию кода для односвязного списка. Добавляем в проект файл forward_list.h, и поехали:

Подключили заголовочный файл, который только что сделали, и объявили пространства имен. Весь код разместим в одном заголовочном файле, чтобы потом подключить этот файл в другой cpp-файл, где будет реализация ядра операционной системы. Это позволит компилятору гораздо лучше оптимизировать код, чем если бы код списка был сам по себе разбит на h- и cpp-файлы.

Определили структуру, которая представляет из себя тот самый элемент списка. Она ничего не содержит, кроме указателя на следующий элемент списка. Этот указатель может иметь значение nullptr (0) в том случае, если этот элемент списка последний.

Мы не сможем несколько раз унаследоваться структуры forward_list_element. Компилятор выдаст ошибку о том, что мы пытаемся выполнить наследование от одного и того же класса более одного раза. Поэтому с такой структурой поместить задачу в два и более списков одновременно окажется невозможным. Этот вопрос мы решим позже.

Теперь я приведу объявление класса односвязного списка, который содержит указатель на начало списка и набор функций для работы с ним:

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

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

Я не буду приводить здесь реализацию методов этого класса, потому что она достаточно проста. Можете посмотреть ее в исходниках на GitHub [TODO] или скачать готовый проект в конце статьи.

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

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

В этом классе, который мы унаследовали от forward_list_base, содержатся те же функции, что и в базовом классе, но мы сделали их типизированными. Они будут принимать на вход указатель на структуру задачи и сами определять, какой из указателей next базового класса forward_list_element использовать. Если мы в какой-то из методов передадим класс, не унаследованный от класса forward_list_element_tagged с таким же тегом, как у списка, мы получим ошибку компиляции.

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

Взглянем, как это все можно использовать. Я сделал тестовый проект для Visual Studio 2015 (ссылка есть в конце статьи), где применяется наш список для иллюстрации работы с ним. Я приведу кусок кода с комментариями здесь:

Выведет эта программа следующее:

forward list sample result

Все выглядит достаточно элегантно. Компилятор выдаст ошибку, если мы попытаемся добавить элемент в тот список, который не должен содержать его. Как в примере выше: класс doge унаследован от sleeping_dog_list_element и black_dog_list_element, но не от red_cat_list_element. Поэтому, если мы попытаемся добавить элемент типа doge в список котов (или удалить его оттуда), то получим ошибку на этапе компиляции, что предотвратит ошибку в программе. Давайте еще посмотрим на иерархию классов в этом проекте:

forward list sample

На этом на сегодня все. Как обычно, вы можете лицезреть развитие проекта на GitHub и скачать код проекта atmos полностью. Также, по доступен тестовый проект для Visual Studio (про собак и котов).

Пишем свою операционку для Arduino. Шаг 2 — односвязный список: 3 комментария

  1. Спасибо большое за статьи, надеюсь их будет побольше <3.
    Оффтоп: подскажите, пожалуйста, как можно запустить программу из оперативки не выгружая на хард? Куда копать?

    1. Я когда-то пробовал загружать DLL из памяти, не выгружая на хард. В DllMain можно написать любой код, который будет выполняться. На эту тему есть много статей, вот, например: https://www.joachim-bauch.de/tutorials/loading-a-dll-from-memory/, или вот это тоже подойдет: https://forum.antichat.com/threads/132116/. Вот это еще можно пробовать: https://stackoverflow.com/questions/305203/createprocess-from-memory-buffer
      Но это все, конечно же, хаки, и не гарантируют работоспособности с произвольными бинарниками.

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *