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

Оглавление

Система сборки (make, gcc, gas). Первоначальная загрузка (multiboot). Запуск (qemu). Библиотека C (strcpy, memcpy, strext).

Библиотека C (sprintf, strcpy, strcmp, strtok, va_list ...). Сборка библиотеки в режиме ядра и в режиме пользовательского приложения.

Системный журнал ядра. Видеопамять. Вывод на терминал (kprintf, kpanic, kassert).
Динамическая память, куча (kmalloc, kfree).

Организация памяти и обработка прерываний (GDT, IDT, PIC, syscall). Исключения.
Виртуальная память (каталог страниц и таблица страниц).

Процесс. Планировщик. Многозадачность. Системные вызовы (kill, exit, ps).
Файловая система ядра (initrd), elf и его внутренности. Системные вызовы (exec).

Драйверы символьных устройств. Системные вызовы (ioctl, fopen, fread, fwrite). Библиотека C (fopen, fclose, fprintf, fscanf).

Оболочка как полноценная программа для ядра.

Пользовательский режим защиты (ring3). Сегмент состояния задачи (tss).

Многозадачность

Как ты помнишь, каждый процесс должен иметь свое адресное пространство.

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

Поэтому мы должны описать память процесса:

/*
 * Process memory description
 */
struct task_mem_t {
    void* pages; /* task physical pages */
    u_int pages_count; /* task physical pages count */
    void* page_dir; /* page directory */
    void* page_table; /* page table */
};

Процессы как-то должны обмениваться информацией между собой. Для этого введем понятие сообщения:

struct message_t {
    u_short type; /* message type */
    u_int len; /* data length */
    u8 data[IPC_MSG_DATA_BUFF_SIZE]; /* message data */
};

После этого нужно описать сам процесс как элемент циклического списка.

Циклический список здесь удобен по тому, что в планировщике от каждой задачи нужно выбирать следующую, пока список не пуст.

Этим мы убираем вырожденный случай, значит облегчаем логику.

/*
 * Process descriptor
 */
struct task_t {
    struct clist_head_t list_head; /* should be at first */
    u_short tid; /* task id */
    char name[8]; /* task name */
    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 */
    struct task_mem_t task_mem; /* task memory */
} attribute(packed);

Каждому процессу мы будем выделять квоту, количество прерываний таймера после истечение которых процесс будет перепланирован.

#define TASK_QUOTA 3

Далее нужно написать функцию создания нового процесса.

Пока у нас нет уровней привилегий, поэтому будем использовать селекторы ядра.

Нам потребуется на будущее 2 стека, один для пользовательского режима, другой для ядра.

Первоначальный статус будем задавать как TASK_UNINTERRUPTABLE чтобы задача не успела выполниться до полной инициализации.

/*
 * Api - Create new task
 */
extern bool task_create(u_short tid, void* address, struct task_mem_t *task_mem)
{
    struct task_t* task;
    struct clist_head_t* entry;

    /* allocate memory */
    entry = clist_insert_entry_after(&task_list, task_list.head);
    task = (struct task_t*)entry->data;
    task->kstack = malloc(TASK_KSTACK_SIZE);
    task->ustack = malloc(TASK_USTACK_SIZE);
    /* fill data */
    task->tid = tid;
    task->name[0] = '\0';
    task->status = TASK_UNINTERRUPTABLE;
    task->msg_count_in = 0;
    task->time = 0;
    memcpy(&task->task_mem, task_mem, sizeof(struct task_mem_t));

    /* set flags */
    *(u32*)(&task->flags) = asm_get_eflags() | 0x200;
    /* set general purpose registers */
    memset(&task->gp_registers, 0, sizeof(struct gp_registers_t));
    /* set other purpose registers */
    task->op_registers.cs = GDT_KCODE_SELECTOR;
    task->op_registers.ds = GDT_KDATA_SELECTOR;
    task->op_registers.ss = GDT_KSTACK_SELECTOR;
    task->op_registers.eip = (size_t)address;
    task->op_registers.cr3 = (size_t)task_mem->page_dir;
    task->op_registers.k_esp = (u32)task->kstack + TASK_KSTACK_SIZE;
    task->op_registers.u_esp = (u32)task->ustack + TASK_USTACK_SIZE;

    printf(MSG_SCHED_TID_CREATE, tid, (u_int)address, task->kstack, task->ustack);

    return true;
}

Удаление процесса будет происходить планировщиком если статус процесса TASK_KILLING.
При удалении нам нужно просто освободить стеки, страницы выделенные под секции данных и кода, а также уничтожить каталог страниц процесса.

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

/*
 * Api - Delete task by id
 */
extern void task_delete(struct task_t* task)
{
    printf(MSG_SCHED_TID_DELETE, (u_int)task->tid);
    assert(task != null);

    /* free stack memory */
    free(task->kstack);
    free(task->ustack);
    task->kstack = null;
    task->ustack = null;
    
    /* free user pages memory */
    if (task->task_mem.pages_count > 0) {
        mm_phys_free_pages(task->task_mem.pages, task->task_mem.pages_count);
        task->task_mem.pages = null;
        task->task_mem.pages_count = 0;
    }
    /* clear resources */
    if (task->task_mem.page_dir != null) {
      mmu_destroy_user_page_directory(task->task_mem.page_dir, task->task_mem.page_table);
    }

    clist_delete_entry(&task_list, (struct clist_head_t*)task);
}

Теперь нужно написать сам планировщик.

Сначала мы должны понять, выполняется ли текущая задача или это первый запуск.
Если задача исполняется, нужно проверить не исчерпана ли ее квота.
Если так, то нужно сохранить ее состояние, явно указав флаг разрешения прерываний.
После этого нужно найти следующую задачу на исполнение в статусе TASK_RUNNING.
Далее нужно завершить текущую задачу, если она находится в статусе TASK_KILLING.
После этого подготавливаем стековый фрейм для следующей задачи и переключаем контекст.

/*
 * Api - Schedule task to run
 */
extern void sched_schedule(size_t* ret_addr, size_t* reg_addr)
{
    struct task_t* next_task = null;

    /* finish current task */
    if (current_task != null) {
        /* update running time */
        current_task->time += 1;

        /* check quota exceed */
        if (current_task->time < TASK_QUOTA && !current_task->reschedule) {
            return; /* continue task execution */
        }

        /* reset quota */
        current_task->time = 0;
        current_task->reschedule = false;

        /* 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));
    }

    /* pick next task */
    if (current_task) {
        next_task = task_get_next_by_status(TASK_RUNNING, current_task);
    } else {
        next_task = task_get_by_status(TASK_RUNNING);
        tss_set_kernel_stack(next_task->kstack);
    }
    assert(next_task != null);

    /* whether should kill current task */
    if (current_task && current_task->status == TASK_KILLING) {
        /* kill current task */
        task_delete(current_task);
    } else {
        /* try to kill killing tasks */
        struct task_t* task;
        task = task_find_by_status(TASK_KILLING);
        if (task) {
            task_delete(task);
        }
    }

    /* 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 */
    printf(MSG_SCHED_NEXT, next_task->tid, next_task->op_registers.u_esp,
        *ret_addr, next_task->op_registers.eip);
    asm_switch_ucontext(next_task->op_registers.u_esp,
        next_task->op_registers.cr3);
}

Осталось написать функцию переключения контекста задач.

Для этого нужно загрузить новый каталог страниц и восстановить все регистры общего назначения, включая флаги.

Также необходимо переключиться на стек следующей задачи.

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

Для в том, что в последствии нам это потребуется для переключения уровней привилегий.

/*
 * Switch context (to kernel ring)
 * void asm_switch_kcontext(u32 esp, u32 cr3)
 */
asm_switch_kcontext:
    mov 4(%esp),%ebp # ebp = esp
    mov 8(%esp),%eax # eax = cr3
    mov %cr0,%ebx    # ebx = cr0
    and $0x7FFFFFFF,%ebx  # unset PG bit
    mov %ebx,%cr0
    mov %eax,%cr3
    or $0x80000001,%ebx   # set PE & PG bits
    mov %ebx,%cr0
    mov %ebp,%esp
    popal
    sti
    iretl

Реализуем простейший механизм обмена сообщениями между процессами.

Когда мы посылаем сообщение процессу, его нужно разморозить если он заморожен так как ждет сообщений.

А вот когда мы принимаем сообщение мы должны заморозить процесс если очередь сообщений пуста.

После этого нужно передать управление планировщику.

/*
 * Api - Send message to task
 */
extern void ksend(u_short tid, struct message_t* msg)
{
    struct task_t* task;

    /* get target task */
    task = task_get_by_id(tid);
    /* put message to task buffer */
    task_pack_message(task, msg);
    /* whether task has frozen */
    if (task->status == TASK_INTERRUPTABLE) {
        /* defrost task */
        task->status = TASK_RUNNING;
    }
}

/*
 * Api - Receive message to task
 *   This function has blocking behaviour
 */
extern void kreceive(u_short tid, struct message_t* msg)
{
    struct task_t* task_before; /* before yield */
    struct task_t* task_after; /* after yield */

    /* get current task */
    task_before = sched_get_current_task();
    assert(tid == task_before->tid);
    assert(task_before->status == TASK_RUNNING);
    /* whether task has not incomming messages */
    if (task_before->msg_count_in == 0) {
        /* freeze task */
        task_before->status = TASK_INTERRUPTABLE;
    }
    /* wait fot message */
    sched_yield();
    /* get current task */
    task_after = sched_get_current_task();
    assert(task_after == task_before);
    assert(tid == task_after->tid);
    assert(task_after->status == TASK_RUNNING);
    /* fetch message from buffer */
    task_extract_message(task_after, msg);
    assert(msg != null);
}

Теперь нужно написать системные вызовы для работы с процессами из пользовательских приложений.

Туда же мы закинем системные вызовы для посылки и приема сообщений.

/*
 * Api - Syscall handler
 */
extern size_t ih_syscall(u_int* function)
{
    size_t params_addr = ((size_t)function + sizeof(u_int));
    size_t result = 0;
    struct task_t *current = sched_get_current_task();

    printf(MSG_SYSCALL, *function, current->tid);

    asm_lock();

    /* handle syscall */
    switch (*function) {
    case SYSCALL_KSEND: {
        /* send message */
        u_short tid = *(u_int*)params_addr;
        ksend(tid, *(struct message_t**)(params_addr + 4));
        break;
    }
    case SYSCALL_KRECEIVE: {
        /* receive message */
        u_short tid = *(u_int*)params_addr;
        kreceive(tid, *(struct message_t**)(params_addr + 4));
        break;
    }
    case SYSCALL_KILL: {
        /* kill task */
        u_short tid = *(u_int*)params_addr;
        struct task_t* task = task_find_by_id(tid);
        if (task != null) {
            assert(task->tid == tid);
            task->status = TASK_KILLING;
            task->reschedule = true;
            result = true;
        } else {
            result = false;
        }
        break;
    }
    case SYSCALL_EXIT: {
        /* exit task */
        int errno = *(int*)params_addr;
        u_int tid = current->tid;
        printf(MSG_TASK_FINISHED, tid, errno);
        current->status = TASK_KILLING;
        sched_yield();
        break;
    }
    case SYSCALL_TASK_LIST: {
        /* get tasks list */
        result = (size_t)task_get_task_list();
        break;
    }
    default:
        unreachable();
    }

    printf(MSG_SYSCALL_RET, *function);

    asm_unlock();

    return result;
}

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

/*
 * Call kernel
 * void asm_syscall(unsigned int function, ...)
 */
asm_syscall:
    push %ebx
    push %ebp
    mov %esp,%ebp
    mov %ebp,%ebx
    add $8,%ebx # skip registers
    add $4,%ebx # skip return address
    push %ebx # &function
    int $0x80
    mov %ebp,%esp
    pop %ebp
    pop %ebx
    ret

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

Ссылки

Подробности и объяснения в видеоуроке.

Исходный код в git репозиторий (тебе нужна ветка lesson7).

Список литературы

1. James Molloy. Roll your own toy UNIX-clone OS.
2. Зубков. Ассемблер для DOS, Windows, Unix
3. Калашников. Ассемблер — это просто!
4. Таненбаум. Операционные системы. Реализация и разработка.
5. Роберт Лав. Ядро Linux. Описание процесса разработки.