Search
Write a publication
Pull to refresh

Операционная система от А до Я: Таймер и HAL

Level of difficultyHard
Reading time11 min
Views900

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


Ключевые моменты

Прежде всего, мы будем делать не просто загрузчик, который выводит на экран Hello from my OS, а подойдём к делу со всей серьёзностью. Если ваша цель - не полноценная операционная система, а условный Hello World, рекомендую к прочтению вместо этой статьи туториал по Bare Bones. Что отличает нашу операционную систему от такой поделки?

  • многозадачность - современная ОС должна уметь выполнять несколько процессов параллельно;

  • независимость от архитектуры - вся платформо-зависимая логика будет вынесена в слой архитектурной абстракции (HAL);

  • драйвера - вместо прямой работы с видеобуфером, как в Bare Bones, мы абстрагируем устройства внутри пользовательского пространства и позволим им общаться с ядром посредством системных вызовов и IPC.

Список небольшой, но реализация - как минимум несколько вечеров отладки и высокой когнитивной нагрузки. У Линуса Торвальдса версия Linux 0.0.1 заняла год, и это был всего лишь переключатель задач, даже без полноценного планировщика.

Чтобы упростить задачу, на первых порах мы не будем трогать компьютер с x86, а возьмём архитектуру попроще: плату Adruino с AVR на борту. К ней не нужен загрузчик, не нужно настраивать GDT и IDT, можно прописать точку входа в ядро в функции main(), и всё заработает. К тому же, так будет проще разобраться в низкоуровневой логике. Да, наша операционная система пока не сможет выводить на экран монитора заветный Hello World. Более того - в этой статье мы ещё не сможем увидеть её работу в действии, поскольку реализуем лишь HAL и задачи, но не планировщик, который возьмёт на себя работу по распределению процессорного времени между задачами. Но это не Bare Bones, это то, ради чего стоит потерпеть. Планировщик будет рассмотрен в следующей статье.

Задачи

Задача - главный элемент любой операционной системы. Сама по себе ОС не представляет практического интереса, если не умеет выполнять какие либо задачи. Бывают системы однозадачные, как DOS, бывают мультизадачные, как Linux, бывают даже такие, которые предназначены для выполнения строго определённой задачи, как Bare Bones или первые вычислительные машины вроде Энигмы, но что-то система обязательно должна выполнять. Реализуем каркас наших задач на Си.

typedef uint8_t Byte;
typedef int64_t Address;
typedef int64_t Size;
typedef int64_t Tick;

typedef struct {
	Size size;
	Address top;
	Address base;
	Address limit;
} Stack;

typedef int64_t TaskID;
typedef int8_t TaskPriority;
typedef uint16_t TaskFlags;
typedef uint16_t TaskResult;

typedef enum {
	REI_TASK_READY = 0,
	REI_TASK_RUNNING,
} TaskState;

typedef TaskResult (*TaskEntry)();

typedef struct task_t {
	struct task_t * next;  // список задач в планировщике будет храниться в виде связного списка
	struct task_t * parent;  // то же, что и родительский процесс в Linux
	TaskID id;  // уникальный числовой идентификатор задачи, аналог PID
	TaskState state;  // текущее состояние, которым будет руководствоваться планировщик при выборе задач
	TaskPriority priority;  // а на основе приоритета планировщик будет расставлять задачи и выделять им процессорное время
	TaskFlags flags;  // пока не используется
	Tick ticks_left;  // процессорное время измеряется в тиках между прерываниями таймера, планировщик будет уменьшать данное значение, а по достижении 0 переключаться на следующую задачу
	Stack stack;  // у нас - обыкновенное хранение промежуточных данных в стеке, для каждой задачи он свой
	TaskEntry entry;  // функция с точкой входа, условный main() задачи
	Address saved_pc;  // нужен для переключения задач, задаётся таймером
	Byte saved_sreg;  // тоже
	uint64_t n_children;
	struct task_t ** children;  // будем хранить потомков задачи здесь же
} Task;

Структура не слишком большая, но её аналог в Linux, например, занимает более 1.7KB. У нас микроядро, и мы постараемся не раздувать размер до таких умопомрачительных масштабов.

Что можно делать с задачей? Её, прежде всего, можно создать и запустить. Этим и займёмся:

#define REI_MAX_TASKS 8

extern ReiCore rei_core;

bool rei_task_create(Task * parent, Stack * stack, TaskEntry entry) {
	if (rei_core.next_task_id >= REI_MAX_TASKS) {
		return false;
	}

	TaskID id = rei_core.next_task_id++;
	Task * task = &rei_core.tasks[id];
	++rei_core.n_tasks;

	task->next          = NULL;
	task->parent        = parent;
	task->id            = id;
	task->state         = REI_TASK_READY;
	task->priority      = 0;
	task->flags         = 0;
	task->ticks_left    = 0;
	task->stack         = *stack;
	task->entry         = entry;
	task->n_children    = 0;
	task->children      = NULL;

	if (!rei_core.hal.init_context(task)) {
		return false;
	}

	rei_scheduler_add(task);

	return true;
}

Пока задач всего 8, но для AVR и этого много, ведь ATmega32U4, на которой работают "ардуины", имеет всего 2.5KB SRAM. Задачи у нас, как видно из 11 строки, хранятся прямым массивом прямо в ядре. Почему? В будущем мы, возможно, реализуем динамическое выделение памяти под новые задачи, но пока никакой динамики у нас попросту нет. Хоть Adruino и умеет динамическую аллокацию через malloc и new, этого стараются избегать, а учитывая, что наша система платформо-независимая, здесь мы не можем использовать даже эти возможности. Почувствуйте уровень: у нас пока ещё не реализована даже куча, мы можем полагаться лишь на выделенные при компиляции области памяти. Вот почему OSdev - высший пилотаж.

Мы уже затронули некий rei_core. Что это, и почему не kernel? Простой ответ: kernel принято называть монолитное ядро, которое помимо переключения задач умеет много чего ещё. Наше не умеет, поэтому закономерно называется core. Нюансы английского технического языка. Давайте этот core реализуем.

typedef int64_t Frequency;

typedef void (*TickHandler)();

typedef struct {
	Frequency interval;
	TickHandler handler;
} Timer;

typedef struct {
	Task * current_task;
	Task * ready_head;
	Task * ready_tail;
} Scheduler;

typedef struct {
	HAL hal;  // Hardware Abstraction Layer - структура с функциями, которые реализованы в платформо-зависимом коде
	Task tasks[REI_MAX_TASKS];  // собственно, массив задач, в будущем постараемся перестроить его в динамически выделяемую структуру
	TaskID n_tasks;
	TaskID next_task_id;  // нужен, чтобы задавать каждой задаче уникальный ID
	Timer timer;  //  а это таймер - рассмотрим его позже
	Scheduler scheduler;  // планировщик, рассмотрим в следующей статье
} ReiCore;

static Task rei_tasks[REI_MAX_TASKS];

ReiCore rei_core = {
	.hal = {0},
	.tasks = rei_tasks,
};

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

typedef struct {
	bool (*init)();
    bool (*init_context)(Task * task);
	bool (*init_timer)(Frequency interval);
	void (*switch_task)(Task * old_task, Task * new_task);
	void (*enable_irqs)();
	void (*disable_irqs)();
	void (*on_tick)(IRQHandler isr);
	void (*halt)();
} HAL;

Если вы впервые встречаетесь с таким кодом, объясню. Функции в си могут представлять из себя указатели на точки входа в себя, а потому храниться как переменные в структурах. Это не методы из C++, поскольку здесь нет инкапсуляции, но позволяют реализовать функции второго порядка, например

bool rei_core_init(HAL hal, Frequency timer_interval) {
	rei_core.hal = hal;

	if (!rei_core.hal.init()) {
		return false;
	}

	rei_core.hal.on_tick(rei_core_tick);
	if (!rei_core.hal.init_timer(timer_interval)) {
		return false;
	}

	return true;
}

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

#include <avr/io.h>
#include <avr/interrupt.h>

extern ReiCore rei_core;

/*
Функции, просящие аппаратуру включить или отключить аппаратные прерывания,
чтобы таймер не выдернул задачу в самый неподходящий момент - при выполнении
атомарных операций, которые мы реализуем сильно позже.
*/

inline static void hal_enable_irqs() {
	sei();
}

inline static void hal_disable_irqs() {
	cli();
}

/*
Инициализация. Здесь мы отключаем аппаратные прерывания, чтобы успеть
сначала успеть настроить таймер и планировщик.
*/

static bool hal_init() {
	cli();
	return true;
}


Один из самых ответственных моментов - инициализация контекста в стеке задачи
при её создании. Когда задача создаётся, у неё есть область памяти, именуемая стек,
но остальное аппаратное состояние ещё не настроено: не заполнены регистры, и самое
главное - HAL не знает, где брать точку входа в задачу. Ассемблер не понимает сишные
функции, ему нужен адрес, с которого начинать выполнение. Но заполнить регистры
и запустить задачу непосредственно при создании мы не можем, ведь у нас есть другие задачи, которые выполняются в данный момент. Что же делать? Сначала нужно изучить, как задачи переключаются.

Итак, при обработке прерывания таймера текущая задача останавливается. Её состояние включает в себя регистры и адрес текущей операции, что на деле тоже регистр PC. Из всего этого добра нужно сформировать фрейм контекста и положить в стек. Вот зачем в структуре стека нужен limit и вот почему rei_core.hal.init_context(task) может вернуть false - стек задачи ограничен на самом деле не объёмом выделенной памяти, а её объёмом за вычетом места под фрейм контекста. В моей реализации HAL для AVR фрейм выглядит следующим образом:

  • Внизу лежит адрес текущей операции, или адрес возврата в задачу.

  • Выше находится байт, отображающий регистр SREG - флаги состояния.

  • Наверху - регистры R0-R31, от меньшего к большему.

Таким образом, для инициализации контекста мы должны сформировать фрейм, инициализировав регистры нулями, SREG - значением 0b10000000 (флаг прерываний включён), а в самый низ подсунуть тот самый entry, как бы продолжив выполнение задачи при переключении с самого начала.

#define CONTEXT_SIZE 35

static bool hal_init_context(Task * task) {
	if (task->stack.size < CONTEXT_SIZE) {
		return false;
	}

	Byte * sp = (Byte*) task->stack.base + task->stack.size;

	// Build stack frame: [R31..R0][SREG][PC]

	// PC
	sp -= 2;
	uint16_t pc = (Address) task->entry;
	sp[1] = (Byte) (pc & 0xFF);
	sp[0] = (Byte) (pc >> 8);

	// SREG
	--sp;
	*sp = 0x80;

	// R0..R31
	sp -= 32;
	memset(sp, 0, 32);

	task->stack.top = (Address) sp;
	task->stack.limit = (Address) task->stack.base + CONTEXT_SIZE;

	return true;
}

Обратите внимание, что мы кладём байты адреса возврата PC в обратном порядке: снизу верхний, сверху нижний. Потому что AVR - это little endian, и при взятии адреса со стека он будет интерпретироваться именно так.

Ну а теперь - сердце нашего ядра, переключение контекста на ассемблере.

inline static void rei_save_context(Task * task) {
	const Byte * sp = (Byte*) task->stack.top - 1;
	Byte pc_low = task->saved_pc & 0xFF;
	Byte pc_high = task->saved_pc >> 8;
	Byte * old_sp;

	task->stack.top -= CONTEXT_SIZE;

    // сохраняем текущий стек, чтобы затем вернуться туда, откуда вызвана rei_save_context
	asm volatile (
		"in   %A0, __SP_L__ \n"
		"in   %B0, __SP_H__ \n"
		: "=z"(old_sp)
	);

	asm volatile (
        // подменяем стек на стек заданной задачи
		"out  __SP_L__, %A0 \n"
		"out  __SP_H__, %B0 \n"

		"push %1            \n"  // PC low
		"push %2            \n"  // PC high
		"push %3            \n"  // SREG

		"push r0            \n"
		"push r1            \n"
		"clr  r1            \n"  // очищаем r1 - на AVR он должен быть 0
		"push r2            \n"
		"push r3            \n"
		"push r4            \n"
		"push r5            \n"
		"push r6            \n"
		"push r7            \n"
		"push r8            \n"
		"push r9            \n"
		"push r10           \n"
		"push r11           \n"
		"push r12           \n"
		"push r13           \n"
		"push r14           \n"
		"push r15           \n"
		"push r16           \n"
		"push r17           \n"
		"push r18           \n"
		"push r19           \n"
		"push r20           \n"
		"push r21           \n"
		"push r22           \n"
		"push r23           \n"
		"push r24           \n"
		"push r25           \n"
		"push r26           \n"
		"push r27           \n"
		"push r28           \n"
		"push r29           \n"
		"push r30           \n"
		"push r31           \n"
		:
		: "z"(sp), "r"(pc_low), "r"(pc_high), "r"(task->saved_sreg)
		: "r0", "r1", "memory"
	);

    // возвращаем старый стек, чтобы вернуться туда, куда положено, например в rei_switch_context
	asm volatile (
		"out  __SP_L__, %A0 \n"
		"out  __SP_H__, %B0 \n"
		:
		: "z"(old_sp)
		: "memory"
	);
}

inline static void rei_restore_context(Task * task) {
	Byte * sp = (Byte*) task->stack.top - 1;
	task->stack.top += CONTEXT_SIZE;

	asm volatile (
        // снова подменяем стек, на этот раз на новую задачу,
        // старый стек не сохраняем, он нам больше не нужен:
        // возврат из функции произведётся прямо в задачу
		"out  __SP_L__, r30 \n"
		"out  __SP_H__, r31 \n"

		"pop  r31           \n"
		"pop  r30           \n"
		"pop  r29           \n"
		"pop  r28           \n"
		"pop  r27           \n"
		"pop  r26           \n"
		"pop  r25           \n"
		"pop  r24           \n"
		"pop  r23           \n"
		"pop  r22           \n"
		"pop  r21           \n"
		"pop  r20           \n"
		"pop  r19           \n"
		"pop  r18           \n"
		"pop  r17           \n"
		"pop  r16           \n"
		"pop  r15           \n"
		"pop  r14           \n"
		"pop  r13           \n"
		"pop  r12           \n"
		"pop  r11           \n"
		"pop  r10           \n"
		"pop  r9            \n"
		"pop  r8            \n"
		"pop  r7            \n"
		"pop  r6            \n"
		"pop  r5            \n"
		"pop  r4            \n"
		"pop  r3            \n"
		"pop  r2            \n"
		"pop  r1            \n"
		"pop  r0            \n"

		"pop  r27           \n"
		"out  __SREG__, r27 \n"

        // один из самых древних костылей:
        // сейчас у нас в фрейме на стеке остался лишь адрес возврата в задачу, и мы,
        // вместо того, чтобы возвращать старый стек, используем именно этот адрес,
        // вызываем ret, и PC прыгает прямо в выполнение задачи, а фрейм на стеке опустошается
		"ret                \n"
		:
		: "z"(sp)
		: "r0", "r1", "r27", "memory"
	);
}

inline static void rei_switch_context(Task * old_task, Task * new_task) {
	if (old_task) {
		rei_save_context(old_task);
	}
	rei_restore_context(new_task);
}

Должен признаться, у меня реализация сохранения контекста получилась довольно грязной: я затёр несколько регистров. Но для демонстрации этого пока хватит, а лучше мне, возможно, помогут сделать гуру ассемблера в комментариях. Ещё момент: во время вызова rei_switch_context многие отключают аппаратные прерывания, и затем по завершении включают снова, поскольку переключение контекста - операция атомарная, и нам не нужно, чтобы меняющийся стек внезапно поехал. Это хорошая практика, но пока у нас из прерываний будет настроен лишь таймер, и вот для него прерывания отключать бесполезно. Во первых, мы внутри восстанавливаем SREG, который их снова включит в процессе, ведь у него выставлен первый флаг, а во вторых, даже если бы процедура переключения заблокировала 1-2 тика таймера, зачем нам такой таймер, который по истечении switch снова тут же вызовет тот же switch, почти не дав повыполняться непосредственной задаче? rei_switch_context вызывается практически сразу при таймере, и её длительность должна быть намного меньше интервала таймера, чтобы занимать минимум процессорного времени, а отдать побольше задачам. Лично у меня при тактовой частоте ардуины 16 МГц переключение сейчас занимает менее 50 мкс, значит, интервал между тиками стоит задавать как минимум 1 мс. Тогда свитчи будут занимать 1/20 процессорного времени, и мы почти не заметим просадки производительности в самих задачах.

Это была лирика, а теперь - ближе к делу. У нас остался таймер. С божьей помощью и помощью ClaudeAI я разработал алгоритм, преобразующий время в микросекундах в делитель таймера и выбирающий подходящий прескейл. Что это такое - тема не для этой статьи, а уроков по Arduino, а я просто выложу код.

static bool hal_init_timer(Frequency interval) {
	rei_core.timer.interval = interval;

	uint32_t target_freq = 1000000UL / interval;  // 1MHz / interval (us)

	struct {
		uint16_t prescaler;
		uint8_t cs_bits;
	} prescalers[] = {
		{ 1,     _BV(CS10)             },  // divisor 1
		{ 8,     _BV(CS11)             },  // divisor 8
		{ 64,    _BV(CS11) | _BV(CS10) },  // divisor 64
		{ 256,   _BV(CS12)             },  // divisor 256
		{ 1024,  _BV(CS12) | _BV(CS10) }   // divisor 1024
	};

	uint16_t best_ocr = 0;
	uint8_t best_cs = 0;
	uint32_t best_error = UINT32_MAX;

    for (uint8_t i = 0; i < 5; i++) {
        uint32_t timer_freq = F_CPU / prescalers[i].prescaler;
        uint32_t ocr_value = timer_freq / target_freq - 1;

        if (ocr_value > 65535) continue;

        uint32_t real_freq = timer_freq / (ocr_value + 1);
        uint32_t real_interval = 1000000UL / real_freq;
        uint32_t error = (real_interval > interval)
			? (real_interval - interval)
			: (interval - real_interval);

        if (error < best_error) {
            best_error = error;
            best_ocr = ocr_value;
            best_cs = prescalers[i].cs_bits;
        }
    }

	if (best_cs == 0) {
		return false;
	}

	TCCR1A  = _BV(COM1A1);  // clear on compare match
	TCCR1B  = _BV(WGM12) | best_cs;  // CTC mode, chosen prescaler
	OCR1A   = best_ocr;
	TIFR1  |= _BV(OCF1A);
	TIMSK1 |= _BV(OCIE1A);  // Timer0 Compare Match A

	return true;
}

inline static void hal_switch_task(Task * old_task, Task * new_task) {
	rei_switch_context(old_task, new_task);
}

static void hal_on_tick(IRQHandler isr) {
	rei_core.timer.handler = isr;
}

ISR(TIMER1_COMPA_vect) {
	if (rei_core.scheduler.current_task) {
        // именно здесь мы сохраняем адрес возврата в прерванную задачу
		rei_core.scheduler.current_task->saved_pc = (Address) __builtin_return_address(0);
		rei_core.scheduler.current_task->saved_sreg = SREG |= 0x80;
	}

	if (rei_core.timer.handler) {
        // и вызываем переключение через посредника - планировщика
		rei_core.timer.handler();
	}
}

HAL hal_avr = {
	.init         = hal_init,
	.init_timer   = hal_init_timer,
	.init_context = hal_init_context,
	.switch_task  = hal_switch_task,
	.enable_irqs  = hal_enable_irqs,
	.disable_irqs = hal_disable_irqs,
	.on_tick      = hal_on_tick,
	.halt         = hal_halt,
};

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

Исходный код: https://github.com/arebaka/rei

Only registered users can participate in poll. Log in, please.
Насколько сложным показалось повествование?
42.86%Легко, читается как дышится6
14.29%Есть проблемы с комментированием кода, не всегда понятно, что как работает2
35.71%Средне — всё таки тема тяжёлая для понимания, новичкам разобраться непросто5
0%Разобраться непросто и опытным системным программистам, нужно больше растолкований0
7.14%Очень сложно, лучше всё переписать1
14 users voted. 1 user abstained.
Tags:
Hubs:
+3
Comments1

Articles