Пишем свою операционку для Arduino. Шаг 5 — настоящий sleep и yield

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

Начнем мы с усовершенствований и исправлений. Рекомендую вам открыть старый код ядра на GitHub прежде, чем читать дальше. Во-первых, у нас в коде класса kernel была объявлена функция run, запускающая ОС. Эта функция была помечена атрибутом naked. В этом нет никаких проблем, но вот в теле функции - есть. Из нее мы вызываем C++-функцию initialize_scheduler_timer, а этого, как вы помните из пояснений в предыдущих статьях, делать не стоит. Документация на атрибут naked крайне не рекомендует выполнять любой C/C++-код из таких функций, обещая нам неопределенное поведение. Нам повезло: ничего не упало и не сломалось, но ошибку все-таки придется исправить. Уберем атрибут naked. Но теперь, если мы попробуем скомпилировать код, то получим ошибку о том, что функция run не может быть помечена атрибутом noreturn, потому что она возвращает управление. Атрибут noreturn, напоминаю, сообщает компилятору о том, что функция никогда не возвращает управления. Именно для этого данный атрибут и был добавлен к функции run. Ошибку эту компилятор выдает, потому что тело функции завершается ассемблерным макросом, и компилятор C++ не может знать, что этот макрос в конце осуществляет переход на совершенно другой код (а именно, передает управление одному из процессов ОС). Чтобы сообщить компилятору о том, что макрос не вернет управление, в самый конец функции допишем строку __builtin_unreachable();. Эта встроенная в GCC функция сообщает ему, что до точки ее вызова управление не дойдет никогда. Теперь наше ядро снова собирается.

Есть еще одна проблема: все та же функция run в конце осуществляет переход на тело функции switch_to_next_process_context_func. А та сразу начинает выполнять макрос, который делает две (для некоторых контроллеров три) операции pop. Мы их туда в предыдущей части добавили, чтобы освободить место на стеке, которое требуется для вызова функции choose_next_process. Эти три pop'а, скорее всего, ничего плохого не сделают (потому что у нас на стеке есть кое-какие данные, как минимум, адрес возврата из функции run, и stack underflow не возникнет), но в данном случае эти инструкции совершенно лишние. Поэтому вместо вызова макроса switch_to_next_process_context_func мы будем вызывать напрямую choose_next_process, а потом осуществлять переход на метку внутри тела функции switch_to_next_process_context_func, которую мы поставим непосредственно перед записью в стековые регистры SPH и SPL.

Еще одна правка коснулась функции save_context_and_switch_to_next_process_func: ее я выпилил полностью вместе с прилагающейся функцией offset_of. Там была очень нетривиальная ассемблерная вставка ради того, чтобы только сохранить текущий стековый указатель процесса. Этот код я перенес внутрь функции switch_to_next_process_context_func, написанной на C++, немного изменив порядок действий.

Код после правок я буду приводить уже с нововведениями, касающимися операций sleep и yield. Поэтому ими мы теперь и займемся.

Начнем мы с нашего файла конфигурации config.h. Раз мы желаем иметь возможность приостановить любой процесс на заданный промежуток времени, нам это время придется как-то отслеживать. Для этого мы введем счетчик срабатываний прерывания планировщика (tick count), который будет инкрементироваться каждый раз, когда планировщик получает управление. Размер этого счетчика будет устанавливать пользователь, для этого мы добавим макрос ATMOS_TICK_COUNTER_TYPE, раскрываться который будет по умолчанию в uint8_t (однобайтовый счетчик, максимальное значение 255), но его можно будет изменить, выставив uint16_t (2 байта), __uint24 (3 байта), uint32_t (4 байта) или uint64_t (8 байтов). В зависимости от размера этого счетчика будет меняться максимальное непрерывное время ожидания процессов. Например, если у нас размер счетчика - 1 байт (т.е. его максимальное значение равно 255), а таймер настроен на срабатывания раз в 10 миллисекунд, то максимальное время ожидания будет равно 255 * 10мс = 2550мс ~ 2.5 секунды. Если же мы выберем двухбайтовый счетчик, у которого максимально допустимое значение равно 65535, то максимальное время ожидания процесса будет уже 65535 * 10мс ~ около 11 минут! Но при выборе более емкого счетчика и кода будет сгенерировано больше, и оперативной памяти потребуется тоже чуть дольше. Так что этот размер нужно будет выбирать по потребностям.

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

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

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

Мы же дадим свободу этот процесс вообще не создавать, выставив значение макроса ATMOS_ENABLE_SYSTEM_PROCESS в 0. Это даст возможность более гибкой настройки. Например, системный процесс нам не нужен, если хотя бы один из пользовательских процессов никогда не будет вызывать sleep. Выключив системный процесс, мы сэкономим оперативную и программную память.

Конечно, у нас будут опции конфигурации ATMOS_SUPPORT_YIELD и ATMOS_SUPPORT_SLEEP, которые будут включать поддержку системных вызовов yield и sleep, соответственно. Если включить только sleep, то и yield тоже будет включен автоматически, потому что sleep будет неявно использовать yield, и без последнего мы ничего сделать не сможем.

В файл checks.h мы добавим код, который проверит, что пользователь задал допустимое значение макроса ATMOS_TICK_COUNTER_TYPE:

Мы задали шаблонную структуру tick_counter_checker, в которую будем передавать значение макроса. Если оно является одним из допустимых, то компилятор выберет при инстанциации шаблона одну из его явных специализаций, и ошибка выведена не будет, потому что во всех этих специализациях выставлено значение is_valid = true. А вот если значение недопустимо, то будет выбрана структура по умолчанию, и компилятор выдаст ошибку о том, что тип счетчика некорректен.

В файл defines.h мы добавим новые макросы:

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

Затем, в файле forward_list.h в класс forward_list_tagged мы добавим пару методов:

Первый метод будет устанавливать для элемента списка elem следующий элемент next, а второй метод - устанавливать для списка первым элементом (head) elem. Это все нам потребуется, когда мы будем манипулировать списком выполняющихся и ожидающих процессов.

Теперь перейдем к файлу process.h, там тоже кое-что новенькое добавится. Подключим к этому файлу наш конфиг config.h, а затем в теле класса process определим следующий тип:

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

Значение этого поля будет указывать, до какого срабатывания таймера процесс будет приостановлен. Это займет некоторый объем памяти для каждого из процессов (зависит от размера типа tick_t, определенного пользователем). Наконец, добавим несколько публичных функций в интерфейс класса process:

Если включена опция ATMOS_SUPPORT_SLEEP или ATMOS_SUPPORT_YIELD, то добавится объявление функции yield. Эта функция будет передавать управление от текущего процесса (который и вызвал функцию) следующему по очереди. Мы добавили к этой функции атрибуты naked и noinline. Первый необходим, потому что мы напишем код функции сами, используя ассемблерные вставки и макросы, и нам не нужен сгенерированный компилятором пролог и эпилог. Второй атрибут нужен, чтобы функция не встраивалась в тело других функций и имела отдельный адрес. Когда процесс будет ее вызывать, этот адрес будет автоматически контроллером добавляться на вершину стека процесса. Поведение будет полностью аналогично тому, которое мы имеем при срабатывании прерывания планировщика: на стеке мы всегда будем иметь адрес возврата в тело процесса, в то место, с которого нужно будет продолжать выполнение, когда процесс получит управление в следующий раз. Только в случае yield (или sleep) процесс сам добровольно будет отказываться от положенного ему процессорного времени, в отличие от прерывания планировщика, который принудительно передает управление другому процессу.

Функции sleep, sleep_us и sleep_ms позволяют приостановить выполнение текущего процесса на заданное количество срабатываний прерывания планировщика, либо на заданное количество микросекунд/миллисекунд. Это системный вызов sleep, который по-настоящему приостановит выполнение процесса на заданное время, а другие процессы смогут в это время спокойно выполняться.

Теперь начинается самая мякотка - файл kernel.cpp. Сперва обсудим, как мы будем реализовывать наш функционал. У нас уже есть список выполняющихся процессов running_processes. Теперь же нам понадобится еще список ожидающих процессов. На время, пока процесс спит, он будет удален из списка выполняющихся процессов и будет добавлен в список приостановленных. В этом списке мы будем упорядочивать процессы в порядке возрастания номера срабатывания прерывания планировщика (будем называть его дальше tick). Например, если текущий tick равен 2, и какой-либо процесс говорит ядру, что желает ждать 5 tick'ов, то tick, когда ядро должно будет его разбудить - это 2 + 5 = 7. Но тут есть еще одна загвоздка: значение tick'а может переполняться. Например, если у нас tick_t - это uint8_t (однобайтовый тип), а текущий номер tick'а планировщика равен 250, и тут какой-то процесс просит усыпить его на 10 тиков... То значение 260 у нас в один байт не влезет. Произойдет переполнение, и мы при сложении 250 + 10 получим 4. Это не совсем то, чего мы ожидали, но с этим можно работать. Более того, переполнение беззнакового типа абсолютно легально в C++. Добавим вместо одного списка ожидающих процессов два: waiting_processes и waiting_processes_overflown. Если вдруг значение tick'а, до которого хочет спать процесс, вызывает переполнение, то мы будем помещать этот процесс во второй список. Если же не вызывает, то в первый. Каждый раз, когда срабатывает планировщик, мы значение текущего tick'а будем увеличивать на единицу, и рано или поздно это значение тоже переполнится и станет равным нулю. В этот момент мы поменяем местами содержимое наших списков waiting_processes и waiting_processes_overflown. Такой трюк позволит справиться с переполнением. Давайте теперь перейдем к коду:

Если включена поддержка системного процесса, то определим указатель на него. Если включена поддержка ожидания, то у нас появляется сразу несколько переменных: указатель на процесс, который должен выполняться следующим (next_process), два списка, которые я описал выше, и счетчик tick'ов планировщика. next_process необходим, потому что в условиях перемещений процессов между списками нам будет недостаточно информации о том, какой процесс выполнить следующим при использовании старой логики, которую мы придумали в предыдущей статье. Например, если текущий процесс заснул, и мы его переместили в список waiting_processes, то при попытке получить следующий элемент списка (process_list::next(current_process)) мы получим лажу. Этот вызов вернет нам либо нулевой указатель (если за ним больше нет элементов), либо указатель на другой заснувший процесс, который следует за текущим в списке waiting_processes. Но мы не можем на него переключаться, ведь он еще спит! Поэтому нам и необходим явный указатель, который будет явно сообщать, на какой процесс переключаться.

Далее рассмотрим функцию, которая будет увеличивать текущий счетчик tick'ов планировщика и будить процессы, которые дождались своего tick'а:

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

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

Переходим к функции choose_next_process. Так как ее вотчина расширилась, я переименовал ее в save_sp_and_choose_next_process. Я приведу ее код полностью, хотя часть кода осталась с прошлой версии ОС:

Так как я снова все пояснил в комментариях, подробнее раскрою только один момент. Объявление функции у нас будет меняться в зависимости от того, включена ли поддержка sleep'а. Если она включена, то функция будет принимать аргумент uint8_t increment_tick_count. Это флаг, который будет говорить о том, нужно ли инкрементировать значение счетчика tick'ов и будить процессы, или нет. Так как функция save_sp_and_choose_next_process будет вызываться из разных мест (и из процессов, желающих заснуть, и из прерывания планировщика), то инкрементировать этот счетчик нам нужно будет не всегда, а только при вызове из прерывания.

Функцию switch_to_next_process_context_func я тоже переименовал, теперь она называется save_context_and_switch_to_next_process_context_func. Рассмотрим отличия от предыдущей версии:

Что это за две инструкции - clr r24 и bld r24, 0, которых раньше не было? Они добавляются в код только в том случае, если у нас включена поддержка sleep'а. Так как функция save_sp_and_choose_next_process в этом случае у нас имеет аргумент uint8_t increment_tick_count, то нам нужно передать этот аргумент в функцию. По соглашению вызовов AVR GCC первый однобайтовый аргумент в функцию передается всегда в регистре R24. Поэтому мы сначала инструкцией clr r24 очищаем его значение. Мы можем манипулировать значением этого регистра, потому что к моменту выполнения этого кода его изначальное значение уже сохранено в контексте процесса. Вторая инструкция bld r24, 0 загружает значение флага T из регистра SREG в нулевой бит регистра R24. Таким образом, если этот флаг будет выставлен в единицу, то и значение R24 станет равно единице, и функция save_sp_and_choose_next_process на входе получит значение аргумента increment_tick_count, равное единице. Бит T регистра SREG может быть использован для передачи пользовательской информации. Больше ни для каких целей он не годится. Мы будем выставлять значение этого бита в единицу (после сохренения значения SREG в контексте процесса) перед вызовом функции из прерывания планировщика и в ноль при вызове этой функции из других мест.

Метка switch_to_stack будет упоминаться дальше по тексту.

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

Мы объявили эту функцию naked и написали ее тело на ассемблере - это всего лишь одна инструкция jmp, которая осуществляет переход на саму себя, выполняя таким образом бесконечный цикл. Вот вам и процесс "Бездействие системы" (он же - "System idle process").

Код прерывания планировщика изменится совсем чуть-чуть:

Мы сохраняем значение регистров R31 и SREG в контексте процесса, а затем выставляем значение флага T регистра SREG в единицу. Для этого используется инструкция set. Далее следует вызов функции save_context_and_switch_to_next_process_context_func (через соответствующий макрос).

Код функции run, запускающей ОС, изменился чуть сильнее:

Осталось разобраться с функциями yield и sleep. Начнем с первой.

Здесь ничего сложного - два макроса и одна ассемблерная инструкция. Функция sleep несколько толще:

Готово! Теперь наше ядро умеет усыплять процессы по их запросу, а потом будить их, когда необходимо. Давайте же воспользуемся этими фишками! Откроем файл main.cpp и заменим все вызовы _delay_ms на process::sleep_ms. Скомпилируем код и проверим его, прошив в Arduino, как поясняется в предыдущих статьях. На Arduino Mega 2560 код у меня теперь занимает 996 байтов программной памяти и 225 байтов оперативной (я немного увеличил объем стека всем процессам), а на Arduino Uno R3 - 864 байта программной и 221 байт оперативной. При этом, мы оставили возможность отключить все ненужные опции и получить тот же размер ОС, как и в предыдущей версии!

Вах, теперь наши светодиоды моргают с теми периодами, которые мы задали, а не в три раза медленнее, как в предыдущей версии ОС! Первый светодиод загорается и гаснет 10 раз в секунду, второй - раз в 300 миллисекунд, а третий - раз в секунду. Можно поздравить себя: поставленная цель достигнута!

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

А пока что скачать текущую версию ОС можно по ссылке: atmos source code, также код проекта доступен на GitHub.