Микроконтроллеры

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

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

1) возникает прерывание;

2) процессор сохраняет контекст (регистры процессора в стек и адрес указателя стека в ту же структуру);

3) переключается стек на стек другой задачи;

4) откуда восстанавливается контекст и продолжается другая задача.

Адрес возврата -- часть состояния задачи, куда входит её стек и её регистры. Выделять его отдельно никакого смысла нет.

Разумеется, чтобы было куда вообще переключаться нужно уметь создавать задачи. Что заключается в выделении памяти под стек, создании на стеке контекста (сохранённых регистров) и собственно переключения туда.

То-есть в общем случае нужны функции:

1) аллокации памяти под стек;

2) создания нового контекста с заданными параметрами (адрес перехода, PC, адрес стека SP, аналог регистра FP, может какие-то ещё специфичные для архитектуры);

3) сохранения/восстановления контекста (часть функции обработчика прерывания).

Примитивы синхронизации: обязательно, кровь из носу, нужен такой примитив как test-and-set. Без него ничего не сделать вообще работа принимать исключительно теоретический характер. На его базе можно построить spinlock, семафоф, мьютекс... работающие в большинстве случаев без вызова функций ядра или запрета прерываний.

Другие прерывания в общем случае никак не мешают. Вся "многозадачность" -- это на самом деле как бы штука устроенная внутри одного потока биглупа, а прерывания стоят над всем сверху. Единственное что, из прерываний разумеется все подряд функции ОС использовать неполучится, только ограниченный набор.

Есть другая проблема, когда задача вызвала функцию ОС которую нельзя прерывать и тут случилось прерывание от таймера. И нужно переключать контекст. Запрет прерываний это не решение, т.к. можно попросту пропустить прерывание и неправильно считать время. Практическим решением может быть введение дополнительного прерывания:

1) прерывание от таймера -- обычный обработчик, который считает время и взводит флаг второго прерывания;

2) прерывание не связанное с конкретной периферией, флаг взводится из прерывания таймера для переключения задач.

Второе прерывание может временно запрещаться...

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

Практически на ПК симулятор многозадачной ОС можно сделать либо в Unix/Linux где есть понятие сигналов и соответствующие функции (makecontext, swapcontext).

В Windows симуляцию многозадачности внутри процесса на компьютере сделать невозможно! Да, да, именно так! Огораживание от микрософта начинается даже на таком уровне. Может быть средствами настоящего ядра виндов возможно, был бы рад если кто подскажет как, но средствами API Win32 -- невозможно. Там нельзя прервать поток и переключить в нём стек. Можно только создать совсем уж эмуляцию: множество потоков (или fibers) и их запускать/останавливать. Но контексты уже будет переключать сама Win32. Что тут научишься программировать?

Можно сделать в виртуалке с линуксом.... Но можно использовать qemu в которой выбрать подходящую архитектуру (тот же ARM) и сделать на голом "железе", без оси. Впрочем последнее уже мало отличается от работы с МК и вряд ли оправдано кроме каких-то экзотических случаев.

К сообщению приложен пример совсем уж простой проще некуда многозадачной системы с вытеснением:

http://coliru.stacked-crooked.com/a/99e0d7ee853d80f4

Она работает в линуксе. Для её переноса на железо нужно реализовать отсутствующие функции:

1) программирования таймера: timer_create, timer_settime, timer_delete...

2) останов процессора до ожидания прерывания: sleep(INT_MAX);

3) аллокации памяти... malloc, free, posix_memalign;

4) записи в компорт: write;

5) установки обработчиков прерывания и запрета/разрешения прерываний: sigprocmask, sigaction;

6) самое сложное: getcontext/makecontext, swapcontext -- клонирование текущего контекста и переключение контекстов (задач).

В последнем случае смысл примерно в том, чтоб сохранить регистры процессора (все, включая PC, SP, etc...) в одну структуру и загрузить из другой, и потом продолжить выполнение. На ассемблере написать не сложно.

PS: это не заранее заготовленная портянка, потратил пол дня, возможны баги...

Код на случай, если нас отрежут от интернета:

// (C) Copyright fk0@fk0.name

#define _GNU_SOURCE
#define _POSIX_C_SOURCE 200809L

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <limits.h>
#include <signal.h>
#include <time.h>
#include <ucontext.h>
#include <unistd.h>
#include <stdarg.h>


/////////////////////// OS header /////////////////////////////////////////////////////

// frequency of timer interrupt
#define TICKS_PER_SEC 10

// data type suitable for storing timer value
typedef long ticks;

// function returns current time in "ticks"
ticks os_get_ticks(void);

// structure which represent different tasks (threads) within OS
struct OsTask;
typedef struct OsTask OsTask;

// function type which used as task start function
typedef void* (*OsTaskFunc)(void *);

// This function should be called from main() to run scheduler,
// this function starts first task. Stack size of first task
// is defined by operation system and can't be changed.
void* os_init(OsTaskFunc, void *arg);

// this function allows creation of additional tasks
OsTask *os_create_task(OsTaskFunc, void *arg, size_t stack_size);

// this function wait until termination of previously created task
// and returns value returned by task function.
// This function isn't applicable to main task (which should control life time of other tasks)!
void* os_task_join(OsTask *task);

// this function allows to implement other synchronization primitives:
// call to this function wakes all tasks which wait on address `sync'.
// ONLY THIS FUNCTION CAN BE CALLED FROM INTERRUPT HANDLERS,
// OTHER OS_XXX functions should by called only from tasks code.
void os_wake(void *sync);

// task waits until any other task or interrupt handler not calls os_wake
void os_wait(void *sync);

// this function transfers control to other tasks
void os_yield(void);

// this function allows task to wait specified amount of time
void os_sleep(ticks);

// use this instead of regular `printf'
#define os_printf(...) (0 ? (void)printf(__VA_ARGS__) : _os_printf(__VA_ARGS__))

// this function shouldn't be used directly, use os_printf macro
void _os_printf(const char *fmt, ...);



/////////////////////  OS code ////////////////////////////////////////////////////////////////


// assuming atomic operation, interruption of which not leave variable in inconsistent state
// (which might be significant for 8-bit platforms)
#define ATOMIC(...)  (__VA_ARGS__)

// memory barrier
#define MEMORY_BARRIER()  __asm volatile ("":::"memory")

#define STATIC_ASSERT(COND,MSG) typedef char static_assertion_##MSG[(COND)?1:-1]

// signal numbers used as timer interrupt and interrupt for scheduler
#define TIMER_INTERRUPT SIGUSR1
#define SCHED_INTERRUPT SIGUSR2

// minimum 8192 bytes for linux
#define DEFAULT_STACK_SIZE 16384

static volatile sig_atomic_t ticks_flag;  // set to 1 to indicate, that ticks_count was changed
static volatile ticks ticks_count;        // increased in each timer interrupt

static unsigned next_tnum;  // next new task number
static OsTask *task_list;   // linked list of currently existing tasks (atomically replaceable!)
static OsTask *cur_task;    // currently running task (to use from running tasks)

// print debugging message
#define DBG(fmt, ...)  os_printf("%lu "  fmt, (long)ticks_count, ##__VA_ARGS__)

// print specified message and terminate (due to an error)
#define FATAL(...) (DBG(__VA_ARGS__), _exit(1))

// use this in OS code instead of assert() from stdlib.h
#define ASSERT(expr) ((expr) ? (void)0 : FATAL("FAIL AT %s:%u: %s", __FILE__, __LINE__, #expr))


typedef enum TaskState
{
    RUNNING = 1,    // task is running or ready to run
    WAIT = 2,       // task is waiting one some synchronization primitive
    TERMINATED = 3  // task is terminated and wait to be deleted with call to os_task_join
} TaskState;


// Basic safety checks
STATIC_ASSERT(sizeof(TaskState) <= sizeof(sig_atomic_t), task_state_should_be_atomically_writable);


// structure which represent different tasks (threads) within OS
struct OsTask
{
    sig_atomic_t state;     // task state
    void *sync;             // synchronization primitive on which task is waiting
    void *stack_seg;        // stack segment for the task
    size_t stack_size;      // size of the stack segment
    void *result;           // result returned by task function
    unsigned number;        // task number for displaying
    struct OsTask *next;    // next task in the list
    ucontext_t context;     // tasks context (register, stack...)
};


// this function disables interrupts from the scheduler
static void os_int_disable()
{
    sigset_t sigset;
    sigemptyset(&sigset);
    sigaddset(&sigset, SCHED_INTERRUPT);
    sigprocmask(SIG_BLOCK, &sigset, NULL);
}

// this function enables interrupt from the scheduler
static void os_int_enable()
{
    sigset_t sigset;
    sigemptyset(&sigset);
    sigaddset(&sigset, SCHED_INTERRUPT);
    sigprocmask(SIG_UNBLOCK, &sigset, NULL);
}


void _os_printf(const char *fmt, ...)
{
    va_list args;
    va_start(args, fmt);

    char buf[256];
    int len = vsnprintf(buf, sizeof(buf), fmt, args);
    if (len > 0)
    {
        buf[len] = '\n';
        write(STDOUT_FILENO, &buf, len + 1);
    }

    va_end(args);
}


// function returns current time in "ticks"
ticks os_get_ticks(void)
{
    ticks result;
    do {
        ticks_flag = 0;
        result = ticks_count;
    } while (ticks_flag);

    return result;
}


// this function should only be used from timer interrupt!
static void _os_wake_internal(void *sync)
{
    // assuming, that task_list updated atomically!
    OsTask *task = task_list;
    while (task != NULL)
    {
        // assuming, that task->sync is set strictly before task->state!
        // assuming, that task->state might be written atomically!
        if (task->state == WAIT && task->sync == sync)
        {
            DBG("waking task %u", task->number);
            task->state = RUNNING;
        }
        task = task->next;
    }
}

// this function allows to implement other synchronization primitives:
// call to this function wakes all tasks which wait on address `sync'.
void os_wake(void *sync)
{
    os_int_disable();
    _os_wake_internal(sync);
    os_int_enable();
}


// task waits until any other task or interrupt handler not calls os_wake
void os_wait(void *sync)
{
    cur_task->sync = sync;
    MEMORY_BARRIER();
    ATOMIC(cur_task->state = WAIT);
    os_yield();
}


// function handles interrupts from the timer
static void os_timer_interrupt(int signo, siginfo_t *si, void *context)
{
    (void)signo, (void)si, (void)context;

    // increase time counter
    ticks_flag = 1;
    ticks_count++;

    // wake all sleeping tasks to check time expiration
    _os_wake_internal(NULL);

    raise(SCHED_INTERRUPT);
}


// this function transfers control to other tasks
void os_yield(void)
{
    raise(SCHED_INTERRUPT);
}


// function handles scheduler's interrupt and performs task preemption
void os_scheduler_interrupt(int signo, siginfo_t *si, void *context)
{
    int sp;
    (void)signo, (void)si, (void)context;

    #ifndef NDEBUG
    // determine interrupted task
    OsTask *task = task_list;
    while (task != NULL)
    {
        if ((void*)&sp >= task->stack_seg && (char*)&sp < (char*)task->stack_seg + task->stack_size)
            break;

        task = task->next;
    }
    if (task == NULL) FATAL("unable to determine current task, sp = %p", &sp);
    ASSERT(task == cur_task);
    #endif    

    #ifdef i386
    DBG("SCHEDULER: interrupted task %u, sp = %#x, pc= %#x", task->number,
        ((ucontext_t*)context)->uc_mcontext.gregs[REG_ESP], ((ucontext_t*)context)->uc_mcontext.gregs[REG_EIP]);
    #else
    DBG("SCHEDULER: interrupted task %u, stack = %p", task->number, &sp);
    #endif

    // find next task
    OsTask *next_task = cur_task->next;
    while (1) 
    {  
        // reached end of the list: start from the beginning
        if (next_task == NULL) next_task = task_list;

        // all tasks idle or no more tasks exists
        if (next_task == cur_task)
        {
            if (task->state != RUNNING)
            {
                // issue SLEEP instruction for CPU (timer interrup should wake us)
                DBG("SCHEDULER: CPU IS HALTED TILL TIMER INTERRUPT");
                sleep(INT_MAX);
                return;
            }

            DBG("SCHEDULER: NO TASKS TO SWITCH, RUNNING TASK %u", cur_task->number);
            return;
        }

        // find task suitable for running
        if (next_task->state == RUNNING)
        {
            // function swaps contexts, switches stacks, so execution continues
            // in other task, with other stack pointer, but from a place, where
            // swapcontext was called previously.
            cur_task = next_task;
            #ifdef i386
            DBG("SCHEDULER: SWITCH TASK TO %u, sp = %#x, pc = %#x", next_task->number,
                next_task->context.uc_mcontext.gregs[REG_ESP], next_task->context.uc_mcontext.gregs[REG_EIP]);
            #else
            DBG("SCHEDULER: SWITCH TASK TO %u", next_task->number);
            #endif

            if (!~swapcontext(&task->context, &next_task->context))
                FATAL("swapcontext failed: %s", strerror(errno));

            return;
        }

        // try another task
        next_task = next_task->next;
    }
}


// This function should be called from main() to run scheduler,
// this function starts first task. Stack size of first task
// is defined by operation system and can't be changed.
void* os_init(OsTaskFunc func, void *arg)
{
    // prepare main task for runnning
    OsTask main_task;
    main_task.stack_seg = (char*)&main_task - 65536;
    main_task.stack_size = 65536;                // dirty hack, need to fix
    main_task.number = next_tnum++;
    main_task.state = RUNNING;
    main_task.next = NULL;
    task_list = cur_task = &main_task;
    MEMORY_BARRIER();

    // configure interrupts: timer interrupt
    struct sigaction sa;
    sa.sa_sigaction = os_timer_interrupt;
    sigemptyset(&sa.sa_mask);
    sigaddset(&sa.sa_mask, SCHED_INTERRUPT);  // scheduler can't interrupt timer!
    sa.sa_flags = SA_SIGINFO;
    if (!~sigaction(TIMER_INTERRUPT, &sa, NULL))
        FATAL("sigaction: %s", strerror(errno));

    // same for scheduler's interrupt (which can be interrupted by timer)
    sa.sa_sigaction = os_scheduler_interrupt;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = SA_SIGINFO;
    if (!~sigaction(SCHED_INTERRUPT, &sa, NULL))
        FATAL("sigaction: %s", strerror(errno));

    // configure the timer
    struct sigevent sev;
    timer_t timer_id;
    sev.sigev_notify = SIGEV_SIGNAL;
    sev.sigev_signo = TIMER_INTERRUPT;
    if (!~timer_create(CLOCK_MONOTONIC, &sev, &timer_id))
        FATAL("timer_create: %s", strerror(errno));
   
    struct itimerspec tspec;
    tspec.it_value = (struct timespec){0, 1000000000UL / TICKS_PER_SEC};
    tspec.it_interval = tspec.it_value;
    if (!~timer_settime(timer_id, 0, &tspec, NULL))
        FATAL("timer_settime: %s", strerror(errno));
  
    int sp; 
    DBG("running main task, stack = %p", &sp);
    void *result = func(arg);
    DBG("main task finished with result = %p", result);

    // stop timer interrupts
    timer_delete(timer_id);

    return result;
}

// internal helper function: runs user task, waits for its termination,
// saves result code and signals to the scheduler
static void os_task_init(OsTaskFunc func, void *arg)
{
    DBG("running task %u", cur_task->number);
    cur_task->result = func(arg);
    DBG("task %u finished with result %p (need to be joined)", cur_task->number, cur_task->result);

    ATOMIC(cur_task->state = TERMINATED);
    MEMORY_BARRIER();
    os_wake(cur_task);

    while (1) os_yield();
}

// this function allows creation of additional tasks
OsTask* os_create_task(OsTaskFunc func, void *arg, size_t stack_size)
{
    size_t pagesize = sysconf(_SC_PAGESIZE);
    
    if (stack_size == 0) stack_size = DEFAULT_STACK_SIZE;
    if (stack_size < MINSIGSTKSZ) stack_size = MINSIGSTKSZ;

    void *stack_ptr = NULL;
    posix_memalign(&stack_ptr, pagesize, stack_size);
    ASSERT(stack_ptr != NULL);
    ASSERT(((intptr_t)stack_ptr & (pagesize-1)) == 0);

    // assuming stack grows down
    size_t reserve = (sizeof(ucontext_t) + __BIGGEST_ALIGNMENT__ - 1) & ~(size_t)(__BIGGEST_ALIGNMENT__ - 1);
    ucontext_t *context = (void*)((char*)stack_ptr + stack_size - reserve);
    getcontext(context);

    context->uc_stack.ss_size = stack_size - reserve;
    context->uc_stack.ss_sp = stack_ptr;
    context->uc_link = NULL;

    makecontext(context, (void (*)())os_task_init, 2, func, arg);

    OsTask *task = malloc(sizeof(OsTask));
    ASSERT(task != NULL);

    task->stack_seg = stack_ptr;
    task->stack_size = stack_size;

    task->context = *context;
    ATOMIC(task->state = RUNNING);

    // following code must not be interrupted by scheduler, but still can be interrupted by timer
    os_int_disable();
    {
        // append task to tasks list
        task->number = next_tnum++;
        task->next = task_list;
        ATOMIC(task_list = task);
    }
    os_int_enable();

    DBG("created new task %u, stack = %p", task->number, stack_ptr);
    return task;
}

// this function wait until termination of previously created task
// and returns value returned by task function.
void* os_task_join(OsTask *task)
{
    DBG("waiting for task %u to end", task->number);

    while (ATOMIC(task->state != TERMINATED))
        os_wait(task);

    void *result = task->result;
    DBG("task %u result = %p", task->number, task->result);

    // following code must not be interrupted by scheduler, but still can be interrupted by timer
    os_int_disable();
    {
        // remove task from tasks list
        OsTask **taskp = &task_list;
        while (*taskp != NULL && (*taskp)->next != task)
            taskp = &(*taskp)->next;

        if (*taskp == NULL) FATAL("wrong task pointer %p", task);

        *taskp = task->next;
    }
    os_int_enable();
    
    free(task->stack_seg);
    free(task);
    return result;
}


// this function allows task to wait specified amount of time
void os_sleep(ticks time)
{
    ticks alarm = os_get_ticks() + time;
    DBG("task %u sleeping for %lu ticks", cur_task->number, time);
    while (1)
    {
        os_wait(NULL);

        ticks delta = alarm - os_get_ticks();
        if (delta <= 0)
        {
            DBG("task %u woken", cur_task->number);
            return;
        }

        DBG("task %u will wake after %lu ticks", cur_task->number, delta);
    }    
}



/////////// User code ////////////////////////////////////////////////////////////////////////////

volatile sig_atomic_t second_finish = 0;

void* second_task(void *arg)
{
    (void)arg;
    os_printf("hello from second task");
    while (!second_finish)
        os_sleep(TICKS_PER_SEC/2), os_printf("second task heartbeat");

    return NULL;
}


volatile sig_atomic_t third_finish = 0;

void* third_task(void *arg)
{
    (void)arg;
    os_printf("hello from third task");
    while (!third_finish)
        os_sleep(TICKS_PER_SEC/4), os_printf("second third heartbeat");

    return NULL;
}

void* main_task(void *arg)
{
    (void)arg;
    os_printf("hello from main task");

    OsTask *second = os_create_task(second_task, NULL, 0);
    OsTask *third = os_create_task(third_task, NULL, 0);

    int i;
    for (i = 0; i<10; i++)
    {
        os_sleep(TICKS_PER_SEC / 3);
        os_printf("main task hearbeat");
    }

    second_finish = 1;
    third_finish = 1;

    os_task_join(second);
    os_task_join(third);
    return NULL;
}

int main()
{
    os_init(main_task, NULL);
    return 0;
}