Важно:
1. Эта серия уроков для новичков. Цель — сформировать целостную картину мира. Очень долго у меня в голове была теория Таненбаума и я не мог ее связать с практикой. Тем у кого то же самое — посвящаю эту статью.
2. Код самый простой и тупой, но максимально понятный. Моя цель дать вам понимание чтобы вы смогли написать свое ядро, гораздо более крутое чем это.
3. Репо опубликую как только посчитаю его готовым для широкого круга. Я пишу небольшую часть, отлаживаю, и снимаю видеоурок. У меня нет готового продукта.
Честно говоря я долго думал стоит ли начинать писать статьи и делать видеоуроки на столь изьезженную тему. Но страсть к системному программированию и отсутствие структурированной информации на русском языке все же подтолкнули меня на этот эксперимент. Посему, если труд мой окажется востребованным, статьи планирую выпускать не реже чем раз в месяц и не чаще чем раз в неделю.
Свою ОС я мечтал написать еще в десятом классе. Книга Таненбаума обладает удивительным свойством. Всяк кто к ней прикоснется рано или поздно начинает мечтать написать свою операционную систему. Вот только я тогда ничего не написал, после того как понял что на мастдае невозможно нормально скомпилить и слинковать чистый бинарник с сишным кодом. Пришлось изучать Linux, поступать в универ, идти на работу. Все бы ничего. Да только мечта осуществилась лишь через десять лет. Сейчас, верстая скучные формочки на React, я оглядываюсь назад, вспоминаю, с какой страстью я просиживал часами за дизассемблером и отладчиком, снимал упаковщики, ломал крякмисы, на ночь вместо школьных романов зачитывался статьями мыщьха… и понимаю что моя жизнь могла бы сложиться иначе. Совсем иначе. Если бы только у меня был человек, который смог бы мне помочь в самом начале. Но время ушло. Программы ломать стало трудно. Ядро Linux разрослось до неимоверных размеров. Появились гиппервизоры. Ассемблер Intel стал настолько большим что взглянув на один список команд в мануале пропадает всякий энтузиазм что либо о нем изучать. Хлеб пришлось зарабатывать в вебе. Да. Мир системного программирования пережил свои золотые годы.
Посему всем школьникам, чей энтузиазм еще не иссяк, я посвящаю подробный туториал на тему как взять и с нуля написать простейшее многозадачное микроядро ядро со своей оболочкой. А всех, у кого он еще не появился, хочу предостеречь, что дело это неблагодарное и малополезное, хотя и жутко интересное. А у молодости, как вы знаете, свои заботы.
Поехали!
Данная статья содержит видеоурок снятый в моей домашней студии. Он посвещен непосредственно коду.
Приступим к разработке менеджера кучи.
extern void *kmalloc(size_t size);
extern void kfree(void *addr);
Для написания аллокатора кучи нужно хранить регионы свободных и занятых адресов. Проще всего это реализовать в виде направленного списка. Саму же реализацию направленого списка придется делать через статический массив.
struct slist_head_t
{
struct slist_head_t *prev;
struct slist_head_t *next;
bool is_valid;
void *data;
} attribute(packed);
struct slist_definition_t
{
size_t base;
u_int slots;
size_t slot_size;
struct slist_head_t *head;
struct slist_head_t *tail;
};
Элементами такого ограниченного списка будут являться записи о регионах памяти. Причем между смежными регионами дырок быть не может. Если присутствует свободная память, она описывается отдельным элементом списка.
struct kheap_entry_t
{
struct slist_head_t list_head; /* static (array placed) list */
size_t addr; /* physical address */
size_t size; /* memory block size */
bool is_buzy; /* whether block used */
} attribute(packed);
struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES];
struct slist_definition_t kheap_list = {
.head = null,
.tail = null,
.slot_size = sizeof(struct kheap_entry_t),
.slots = KHEAP_MAX_ENTRIES,
.base = (size_t)kheap_blocks
};
В начале структуры kheap_entry_t стоит slist_head_t что позволяет безболезненно приводить тип записи кучи к элементу списка.
Теперь рассмотрим простейший алгоритм аллокатора кучи (kmalloc):
- Если нет свободных блоков, выделяем новый блок нужного размера (но не более чем максимальный размер кучи).
- В противном случае просматриваем все свободные блоки. Если мы нашли свободный блок, смотрим его размер. Если он достаточен, занимаем. Если есть излишек то создаем новый пустой блок размера излишка. Иначе, если же он недостаточен и последний, расширяем границу кучи (но не более максимума).
Алгоритм освобождения памяти будет похож (kfree):
- Найти блок адрес которого начинается с освобождаемого адреса. Проверить что он занят. Пометить как свободный.
- Если справа или слева есть свободный сосед обьединитьс с ним в один блок.
Следующая статья будет посвящена реализации алгоритма кучи.
Напишем простейший планировщик. Задача будет выглядеть так:
struct task_t
{
struct clist_head_t list_head; /* cyclic list */
u_short tid; /* task id */
struct gp_registers_t gp_registers; /* general purpose registers */
struct op_registers_t op_registers; /* other purpose registers */
struct flags_t flags; /* processor flags */
u_int time; /* time of task execution */
bool reschedule; /* whether task need to be rescheduled */
u_short status; /* task status */
int msg_count_in; /* count of incomming messages */
struct message_t msg_buff[TASK_MSG_BUFF_SIZE]; /* task message buffer */
void *kstack; /* kernel stack top */
void *ustack; /* user stack top */
} attribute(packed);
struct clist_definition_t task_list = {
.head = null,
.slot_size = sizeof(struct task_t)
};
Мы уже умеем выделять память и поэтому организуем задачи как кольцевой список. Так удобнее брать для выполнения следующую задачу относительно текущей с нужным статусом (мы будем использовать статус TASK_RUNNING если задача выполняется). Для начала будем предполагать что все задачи выполняются в кольце защиты ядра (так проще отлаживать планировщик) и обойдемся одним стеком. В будущем прикрутим TSS.
С задачами разобрались, теперь само планирование. Добавляем в IDT обработчик таймера и разрешаем прерывание нужной линии IRQ в PIC. По прерыванию таймера (и в конце кода инициализации ядра) передаем управление планировщику, передав из прерывания таймера адрес возврата и адрес предварительно сохраненных регистров:
/*
* Handle IRQ0
* void asm_ih_timer(unsigned long *addr)
*/
asm_ih_timer:
cli
pushal
mov %esp,%ebp
mov %ebp,%ebx
pushl %ebx # ®
add $32,%ebx
pushl %ebx # &ret addr
call ih_timer
mov %ebp,%esp
popal
sti
iretl
В планировщике проверяем выполнялась ли какая либо задача в этот момент. Если да увеличиваем счетчик времени ее выполнения и смотрим не превышает ли оно квоту. Если нет спокойно возвращаемся. Если превышает, нужно перепланировать задачу. Сохраняем ее состояние (пригодится адрес сохраненных регистров и адрес возврата сохраненный в стеке прерыванием таймера).
/* save task state */
current_task->op_registers.eip = *ret_addr;
current_task->op_registers.cs = *(u16 *)((size_t)ret_addr + 4);
*(u32 *)(¤t_task->flags) = *(u32 *)((size_t)ret_addr + 6) | 0x200;
current_task->op_registers.u_esp = (size_t)ret_addr + 12;
current_task->gp_registers.esp = current_task->op_registers.u_esp;
memcpy(¤t_task->gp_registers, (void *)reg_addr, sizeof(struct gp_registers_t));
Берем адрес стека новой задачи и формируем там фрейм возврата для команды iret. После чего вызываем ассемблерную функцию переключения контекста.
/* prepare context for the next task */
next_task->op_registers.u_esp -= 4;
*(u32 *)(next_task->op_registers.u_esp) = (*(u16 *)(&next_task->flags)) | 0x200;
next_task->op_registers.u_esp -= 4;
*(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.cs;
next_task->op_registers.u_esp -= 4;
*(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.eip;
next_task->gp_registers.esp = next_task->op_registers.u_esp;
next_task->op_registers.u_esp -= sizeof(struct gp_registers_t);
memcpy((void *)next_task->op_registers.u_esp, (void *)&next_task->gp_registers, sizeof(struct gp_registers_t));
/* update current task pointer */
current_task = next_task;
/* run next task */
asm_switch_context(next_task->op_registers.u_esp);
Само переключение контекста выглядит так:
#
# Switch context
# void asm_switch_context(u32 esp)
#
asm_switch_context:
mov 4(%esp),%ebp # ebp = esp
mov %ebp,%esp
popal
sti
iretl
Планировщик готов.
Код полностью смотри в видеоуроке, прилагаемом к статье. Там рассматривается не только планировщик но еще и процесс загрузки, компиляции, и настройки IDT для тех кто подзабыл:
Комментарии (40)
FForth
24.08.2019 16:05Возможно, данной микроядерной ОС, удастся «поконкурировать» с KolibriOS.
saipr
24.08.2019 16:18Неправильный посыл — это KolibriOS надо пытаться поконкурировать с Minix3.
netch80
24.08.2019 18:19+2Учитывая, что Minix сейчас в Intel ME, у всех конкурентов шансов мало.
saipr
24.08.2019 19:30Честно я не знал (как и сам Таненбаум). Так что Minix ни с кем не конкурирует, он идет своей прямой дорогой. А вот KolibriOS и иже с ним с него могут брать пример.
arsboretskiy Автор
25.08.2019 08:33Это не готовый продукт. Я пишу небольшую часть и снимаю видеоурок. Когда все причешу выложу репу полностью. Эта статья — пощупать аудиторию чтобы понять есть ли вообще смысл снимать видеоуроки. Как я понял многие отнеслись скептически. Буду думать как улучшить уроки, пока понял что слишком быстро переключаю экраны, надо было бы выделять маркером текущую обьясняемую область. Выпущу еще 2 урока и если все также вяло пойдет, закончу на этом.
justhabrauser
24.08.2019 22:57+5«Код полностью смотри в видеоуроке» — этапяц, я считаю.
Круче только копия картин Айвазовского шрифтом Брайля.arsboretskiy Автор
25.08.2019 08:27-1Целью было обьяснить код новичкам. Сэкономить их время и силы. Дать общую связь теории и практики. Эта статья НЕ для опытных разработчиков у которых есть понимание картины в целом.
justhabrauser
25.08.2019 09:12+1Речь не о цели, а о средствах.
Показывать код по видео — это как объяснять слепому краски заката.
Нет, ну можно, конечно… Не запрещено же ж.arsboretskiy Автор
25.08.2019 11:46В след раз буду подсвечивать моменты о которых идет речь, есть такое, слишком быстро экраны переключаются.
justhabrauser
25.08.2019 12:26Ok, попробую с другой стороны: код удобно читать как текст, а не смотреть на него по телевизору.
И читать столько, сколько нужно читателю — а не столько, сколько Вы решили его снять на видео.
Возвращаться, перчитывать, вчитываться, копипастить в конце концов.
А не пытаться тормознуть и/или перематывать видео.
Давайте еще код издавать в виде аудиокниг, ага.arsboretskiy Автор
25.08.2019 18:24Т.е. видеоуроки больше не снимать?
justhabrauser
25.08.2019 20:50Это не ко мне вопрос.
Лично я видеоуроки не воспринимаю.
Но это я лично.
Кому-то наоборот комфортнее именно видео (не представляю, но допускаю).
Можете в конец статьи добавить голосовали и узнаете.
AVI-crak
25.08.2019 00:04Ну это не ос, это переглючатель задач. (ошибки нет)
Lex20
25.08.2019 07:50Нынешняя молодёжь думает что ОС это что-то, что может запустить самые последние игры. На wikibooks дан длинный список того что должна делать ОС. В википедии есть краткое определение — комплекс взаимосвязанных программ, предназначенных для управления ресурсами компьютера и организации взаимодействия с пользователем. По википедии получается что это полноценная ОС
arsboretskiy Автор
25.08.2019 08:22+1Я использовал название ОС как маркетинговый ход. Стали бы вы читать статью про переключатель задач? Иначе эта статья осталось бы безызвестной
AVI-crak
25.08.2019 10:50Переглючатель у меня есть, эта та вещь что обычно скрыта за многоэтажными макросами — по этому посмотреть на ваш вариант было интересно.
Но сами переключатели задач могут иметь причудливые реализации для разных типов процессоров. Конкретно в вашем варианте полностью игнорирована система защиты памяти, или я её просто не вижу без вашего акцента внимания.arsboretskiy Автор
25.08.2019 11:47Она будет в следующих статьях, если они будут. Просто я пишу статьи вместе с разработкой ядра по выходным. Первая статья это просто примитивный планировщик.
babylon
25.08.2019 01:35Можете посоветовать список современной литературы от отечественных авторов по данной теме?
arsboretskiy Автор
25.08.2019 08:21Честно не видал ничего более менее структурированного. Так или иначе приходится собирать материал по крупицам.
babylon
26.08.2019 03:09Мы никуда не торопимся. Надеюсь по крупицам соберёте на книжку. Я первый в очереди на неё если что:)))
GBK
25.08.2019 07:53+2Статья — шедевр! Спасибо! Проще и понятнее туториала я еще не видел!
arsboretskiy Автор
25.08.2019 08:20+2Спасибо за лестные слова, из которых я заключаю что у вас математический склад ума)
Lex20
25.08.2019 08:00-1Зачем используете сокращённые названия в коде? У вас букв мало?
arsboretskiy Автор
25.08.2019 08:15+1что-то среднее между любовью к unix стилю и читабельностью
assembled
25.08.2019 15:31Это не стиль, просто когда-то давно сишные компиляторы учитывали в идентификаторах только первые несколько букв (по моему даже 5 когда-то было).
SadAngel
25.08.2019 09:50Для тех кто хочет написать свою RTOS (там С + ASM), очень советую: www.edx.org/course/real-time-bluetooth-networks-shape-the-world-3
KonstantinSpb
25.08.2019 21:53Вдобавок познавательный канал
www.youtube.com/watch?v=TEq3-p0GWGI&list=PLPW8O6W-1chyrd_Msnn4LD6LBs2slJITs
axe_chita
27.08.2019 20:19Не бросайте писать, читать статью очень интересно. Так сказать немного black magic в на службе света.
С нетерпением жду продолжения.
saipr
Какие золотые слова!
Недавно книге Эндрю Таненбаума «Operating Systems: Design and Implementation» (1987, ISBN 0-13-637406-9) исполнилось 30-лет.
А введение в язык Си и Ассемблер, данное в книге, просто привело в восторг
Я тоже проходил этот путь и писал МИНОС (Мобильная ИНструментальная Операционная Система для первых советских персоналок ЕС-184х):
А серию надо продолжать.
arsboretskiy Автор
Вы, можно сказать, счастливчик!
saipr
Наверное да. И в чем по-вашему?
arsboretskiy Автор
Раз у вас было столько времени для системного программирования) Я тока 1 день в неделю этому посвящаю, и то не всегда.
saipr
А это и моя любимая работа, и мое хобби, и даже стиль жизни.