Хабрахабр

[Из песочницы] Разработка многозадачной микроядерной ОС — Планировщик

После того, как вы прочитали базовые шаги по написанию Hello World ядра из цикла имеющихся на Хабре статей, самое время приступить к серьезной разработке самых базовых инструментов: аллокатора кучи и планировщика.

Но страсть к системному программированию и отсутствие структурированной информации на русском языке все же подтолкнули меня на этот эксперимент. Честно говоря я долго думал стоит ли начинать писать статьи и делать видеоуроки на столь изьезженную тему. Книга Таненбаума обладает удивительным свойством. Посему, если труд мой окажется востребованным, статьи планирую выпускать не реже чем раз в месяц и не чаще чем раз в неделю.
Свою ОС я мечтал написать еще в десятом классе. Вот только я тогда ничего не написал, после того как понял что на мастдае невозможно нормально скомпилить и слинковать чистый бинарник с сишным кодом. Всяк кто к ней прикоснется рано или поздно начинает мечтать написать свою операционную систему. Все бы ничего. Пришлось изучать 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):

  1. Если нет свободных блоков, выделяем новый блок нужного размера (но не более чем максимальный размер кучи).
  2. В противном случае просматриваем все свободные блоки. Если мы нашли свободный блок, смотрим его размер. Если он достаточен, занимаем. Если есть излишек то создаем новый пустой блок размера излишка. Иначе, если же он недостаточен и последний, расширяем границу кучи (но не более максимума).

Алгоритм освобождения памяти будет похож (kfree):

  1. Найти блок адрес которого начинается с освобождаемого адреса. Проверить что он занят. Пометить как свободный.
  2. Если справа или слева есть свободный сосед обьединитьс с ним в один блок.

Следующая статья будет посвящена реализации алгоритма кучи.

Задача будет выглядеть так: Напишем простейший планировщик.

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 *)(&current_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(&current_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 для тех кто подзабыл: Код полностью смотри в видеоуроке, прилагаемом к статье.

Теги
Показать больше

Похожие статьи

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

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

Кнопка «Наверх»
Закрыть