Hatena::ブログ(Diary)

常世の国から組込みを叫ぶ

2011年01月26日

RTOS3時間クッキング

これはカーネル/VM Advent Calendar51日目の担当として書いた記事です。

前置き

i386規模になると経験者でなければ無理ですが、AVR/PIC/M16C等の8bit〜16bitマイコンならば日曜日の午後の空いた時間を使ってRTOSっぽいものが作れると主張しているのですが、中々賛同が得られません。

OSを作るのは簡単でしかも楽しいと言うことを主張するために、実際にAVR上に3時間程度で簡単なRTOSを作ってみました。

制約等

今回は3時間程度で作るために以下の部分で手を抜いています。

  • タスクのスタックエリアはグローバル変数領域を使います。
  • スケジューリングは静的有線順位付きのプリエンプティブスケジューリングです。
  • 優先度はタスクのIDを用います。N個のタスクの場合、ID:0のタスクがが最も高い優先度のINITタスクとなり、ID:N-1が最も低い優先度を持つDIAGタスクとなります。
  • タスク数はコンパイル時に決定します。動的な生成は行いません。
  • システムコールはタスクの起動、終了、休眠、復帰のみです。
  • 動作の確認は以下の環境で行っています。
    • ATMega328P
      • 自作評価ボード
      • AVRStudio4.19付属シミュレータ
    • ATMega186
      • Arduino Duemilanove (ATMega186)
      • AVRStudio5付属シミュレータ

開発環境

  • Windows XP Professional SP3
  • AVRStudio 4.18.684
  • WinAVR-20090313

ソースコード

#include <avr/interrupt.h>

#define TASK_NUM (4)
#define NULL ((void*)0)
#define STACK_SIZE (64)
#define KERNEL_STACK_SIZE (64)

typedef void (*task_proc_t)(void* param);
unsigned char stack[TASK_NUM][STACK_SIZE];
extern const task_proc_t task_proc[TASK_NUM];

typedef enum {
    NON_EXISTS,     /**< 未初期化状態  */
    DORMANT,        /**< 休止状態:未起動、実行可能 */ 
    READY,          /**< 実行状態:起動済み、実行可能 */
    PAUSE,          /**< 待ち状態:起動済み、実行不可能 */
} state_t;

typedef struct tcb_t {
    unsigned char*    stack_pointer;   /**< スタックポインタ */
    state_t            state;          /**< タスクの状態 */
} tcb_t;

typedef struct context_t {
    unsigned char R31, R30, R29, R28, R27, R26, R25, R24, R23, R22, R21, R20, R19, R18, R17, R16, 
                  R15, R14, R13, R12, R11, R10, R9 , R8 , R7 , R6 , R5 , R4 , R3 , R2 , R1; /**< R1〜R31までの汎用レジスタ */
    unsigned char RSTATUS;    /**< ステータスフラグ */
    unsigned char R0;        /**< 汎用レジスタR0 */
    unsigned char return_address_high;    /**< 戻り先アドレスの上位8bit */
    unsigned char return_address_low;    /**< 戻り先アドレスの下位8bit */
} context_t ;

tcb_t tcb[TASK_NUM];

tcb_t *currentTCB;

#define SAVE_CONTEXT()                        \
asm volatile (                                \
    "push    r0                     \n\t"     \
    "in      r0   ,__SREG__         \n\t"     \
    "cli                            \n\t"     \
    "push    r0                     \n\t"     \
    "push    r1                     \n\t"     \
    "clr     r1                     \n\t"     \
    "push    r2                     \n\t"     \
    "push    r3                     \n\t"     \
    "push    r4                     \n\t"     \
    "push    r5                     \n\t"     \
    "push    r6                     \n\t"     \
    "push    r7                     \n\t"     \
    "push    r8                     \n\t"     \
    "push    r9                     \n\t"     \
    "push    r10                    \n\t"     \
    "push    r11                    \n\t"     \
    "push    r12                    \n\t"     \
    "push    r13                    \n\t"     \
    "push    r14                    \n\t"     \
    "push    r15                    \n\t"     \
    "push    r16                    \n\t"     \
    "push    r17                    \n\t"     \
    "push    r18                    \n\t"     \
    "push    r19                    \n\t"     \
    "push    r20                    \n\t"     \
    "push    r21                    \n\t"     \
    "push    r22                    \n\t"     \
    "push    r23                    \n\t"     \
    "push    r24                    \n\t"     \
    "push    r25                    \n\t"     \
    "push    r26                    \n\t"     \
    "push    r27                    \n\t"     \
    "push    r28                    \n\t"     \
    "push    r29                    \n\t"     \
    "push    r30                    \n\t"     \
    "push    r31                    \n\t"     \
    "lds     r26  , currentTCB      \n\t"     \
    "lds     r27  , currentTCB + 1  \n\t"     \
    "in      r0   , __SP_L__        \n\t"     \
    "st      x+   , r0              \n\t"     \
    "in      r0   , __SP_H__        \n\t"     \
    "st      x+   , r0              \n\t"     \
);

#define RESTORE_CONTEXT()                          \
asm volatile (                                     \
    "lds     r26        , currentTCB     \n\t"     \
    "lds     r27        , currentTCB + 1 \n\t"     \
    "ld      r28        , x+             \n\t"     \
    "out     __SP_L__   , r28            \n\t"     \
    "ld      r29        , x+             \n\t"     \
    "out     __SP_H__   , r29            \n\t"     \
    "pop     r31                         \n\t"     \
    "pop     r30                         \n\t"     \
    "pop     r29                         \n\t"     \
    "pop     r28                         \n\t"     \
    "pop     r27                         \n\t"     \
    "pop     r26                         \n\t"     \
    "pop     r25                         \n\t"     \
    "pop     r24                         \n\t"     \
    "pop     r23                         \n\t"     \
    "pop     r22                         \n\t"     \
    "pop     r21                         \n\t"     \
    "pop     r20                         \n\t"     \
    "pop     r19                         \n\t"     \
    "pop     r18                         \n\t"     \
    "pop     r17                         \n\t"     \
    "pop     r16                         \n\t"     \
    "pop     r15                         \n\t"     \
    "pop     r14                         \n\t"     \
    "pop     r13                         \n\t"     \
    "pop     r12                         \n\t"     \
    "pop     r11                         \n\t"     \
    "pop     r10                         \n\t"     \
    "pop     r9                          \n\t"     \
    "pop     r8                          \n\t"     \
    "pop     r7                          \n\t"     \
    "pop     r6                          \n\t"     \
    "pop     r5                          \n\t"     \
    "pop     r4                          \n\t"     \
    "pop     r3                          \n\t"     \
    "pop     r2                          \n\t"     \
    "pop     r1                          \n\t"     \
    "pop     r0                          \n\t"     \
    "out     __SREG__,    r0             \n\t"     \
    "pop     r0                          \n\t"     \
);

unsigned char kernel_stack[KERNEL_STACK_SIZE];

#define SET_KERNEL_STACKPOINTER()                         \
    asm volatile (                                        \
        "ldi    r28     , lo8(kernel_stack+%0)     \n\t"  \
        "ldi    r29     , hi8(kernel_stack+%0)     \n\t"  \
        "out    __SP_H__, r29                      \n\t"  \
        "out    __SP_L__, r28                      \n\t"  \
        : : "M"((unsigned char)(KERNEL_STACK_SIZE-1))        \
    );

typedef enum syscallid_t {
    SVCID_startTASK,
    SVCID_exitTASK,
    SVCID_pauseTASK,
    SVCID_resumeTASK,
} syscallid_t;

typedef struct syscallparam_t {
    syscallid_t id;
    int         result;
} syscallparam_t;

typedef struct PAR_startTASK_t {
    syscallparam_t syscallparam;
    int id;
    void *arg;
} PAR_startTASK_t;

typedef struct PAR_exitTASK_t {
    syscallparam_t syscallparam;
} PAR_exitTASK_t;

typedef struct PAR_pauseTASK_t {
    syscallparam_t syscallparam;
} PAR_pauseTASK_t;

typedef struct PAR_resumeTASK_t {
    syscallparam_t syscallparam;
    int id;
} PAR_resumeTASK_t;

__attribute__ ((naked))
void syscall(register struct syscallparam_t* param) {
    (void)param;
    asm volatile(
        "    sbi    0x0B,    2      \n\t" /**< 外部割り込み0番のポートに1を出力すると割り込み発生。 */
        "    ret                    \n\t" /**< 外部割り込みから戻ってくるとここから実行が再開 */
    );
}

int startTASK(int id, void* arg) {
    PAR_startTASK_t param;
    param.syscallparam.id = SVCID_startTASK;
    param.id = id;
    param.arg = arg;
    syscall((syscallparam_t*)&param);
    return     param.syscallparam.result;
}

int exitTASK(void) {
    PAR_exitTASK_t param;
    param.syscallparam.id = SVCID_exitTASK;
    syscall((syscallparam_t*)&param);
    return     param.syscallparam.result;
}

int pauseTASK(void) {
    PAR_pauseTASK_t param;
    param.syscallparam.id = SVCID_pauseTASK;
    syscall((syscallparam_t*)&param);
    return     param.syscallparam.result;
}

int resumeTASK(int id) {
    PAR_resumeTASK_t param;
    param.syscallparam.id = SVCID_resumeTASK;
    param.id = id;
    syscall((syscallparam_t*)&param);
    return     param.syscallparam.result;
}


/** 外部割り込み0の割り込み処理を記述する */
__attribute__ ( ( signal, naked ) )  void INT0_vect(void);
void INT0_vect(void) {
    extern void syscall_entry(void);

    /* 割り込みの直前まで実行されていたコンテキストを保存 */
    SAVE_CONTEXT();

    /* カーネルスタックに切り替え */
    SET_KERNEL_STACKPOINTER();

    /* EXT0割り込みをリセット */
    PORTD &= ~_BV(PORTD2);

    /* システムコール呼び出し処理に移動 */
    syscall_entry();
}

int SVC_startTASK(struct PAR_startTASK_t *par) {
    if (par == NULL) { return -1; }
    if (par->id <  0) { return -1; }
    if (par->id >= 8) { return -1; }
    if (tcb[par->id].state == DORMANT) {
        context_t* ctx = (context_t*)(tcb[par->id].stack_pointer+1);
        tcb[par->id].state = READY;
        ctx->R25 = ((unsigned short)par->arg) >> 8;
        ctx->R24 = ((unsigned short)par->arg) & 0xFF;
        return 1;
    } else {
        return 0;
    }
}

int SVC_exitTASK(struct PAR_exitTASK_t *par) {
    if (par == NULL) { return -1; }
    if (currentTCB == NULL) { return -1; }
    if (currentTCB->state == READY) {
        context_t* ctx = NULL;
        int i = currentTCB - tcb;
        currentTCB->stack_pointer = (&stack[i][STACK_SIZE-1]);
        currentTCB->stack_pointer -= sizeof(context_t);
        ctx = (context_t*)(currentTCB->stack_pointer+1);
        ctx->return_address_high = (unsigned char)(((unsigned short)task_proc[i]) >> 8);
        ctx->return_address_low  = (unsigned char)(((unsigned short)task_proc[i]) & 0xFF);
        ctx->R1 = 0x00;
        currentTCB->state = DORMANT;

        return 1;
    } else {
        return 0;
    }
}

int SVC_pauseTASK(struct PAR_pauseTASK_t *par) {
    if (par == NULL) { return -1; }
    if (currentTCB == NULL) { return -1; }
    if (currentTCB->state == READY) {
        currentTCB->state = PAUSE;
        return 1;
    } else {
        return 0;
    }
}

int SVC_resumeTASK(struct PAR_resumeTASK_t *par) {
    if (par == NULL) { return -1; }
    if (par->id <  0) { return -1; }
    if (par->id >= 8) { return -1; }
    if (tcb[par->id].state == PAUSE) {
        tcb[par->id].state = READY;
        return 1;
    } else {
        return 0;
    }
}

void syscall_entry(void) {
    extern void schedule();

    context_t* ctx;
    syscallparam_t *par;

    /* 呼び出し元のコンテキストからシステムコールの引数を得る */
    ctx = (context_t*)(currentTCB->stack_pointer+1);
    par = (syscallparam_t *)((ctx->R25 << 8) | (ctx->R24));

    /* システムコールのIDに応じた処理 */
    switch (par->id) {
        case SVCID_startTASK   : par->result = SVC_startTASK((PAR_startTASK_t*)par); break;
        case SVCID_exitTASK    : (void)        SVC_exitTASK((PAR_exitTASK_t*)par); break;
        case SVCID_pauseTASK   : par->result = SVC_pauseTASK((PAR_pauseTASK_t*)par); break;
        case SVCID_resumeTASK  : par->result = SVC_resumeTASK((PAR_resumeTASK_t*)par); break;
        default                : par->result = -1; break;
    }

    schedule();
    RESTORE_CONTEXT();
    asm volatile ("reti");
}

void schedule(void) {
    int i;
    for (i=0; i<TASK_NUM; i++) {
        if (tcb[i].state == READY) {
            currentTCB = &tcb[i];
            return;
        }
    }
    currentTCB = NULL;
}

__attribute__ ((naked)) 
void start(void) {
    extern void reset();

    /* 外部割り込み INT0(PD2) は出力モード */
    DDRD  |=  _BV(PORTD2);
    PORTD &= ~_BV(PORTD2);

    /* 外部割り込み条件: INT0(PD2) の立ち上がりで発生 */
    EICRA |= (_BV(ISC01)|_BV(ISC00));

    /* 外部割り込みマスクレジスタ: INT0(PD2) の割り込みを許可 */
    EIMSK |= _BV(INT0);

    reset();    
    schedule();
    RESTORE_CONTEXT();
    asm volatile ("reti");
}

void reset(void) {
    int i;
    for (i=0; i<TASK_NUM; i++) {
        context_t *ctx;
        tcb[i].stack_pointer = (&stack[i][STACK_SIZE-1]);
        tcb[i].stack_pointer -= sizeof(context_t);
        ctx = (context_t*)(tcb[i].stack_pointer+1);
        ctx->return_address_high = (unsigned char)(((unsigned short)task_proc[i]) >> 8);
        ctx->return_address_low  = (unsigned char)(((unsigned short)task_proc[i]) & 0xFF);
        ctx->R1 = 0x00;
        tcb[i].state = DORMANT;
    }

    tcb[TASK_NUM-1].state = READY;
}

/* 以下はユーザー機能として実装する部分 */

#include <stdio.h>

#define LED_DDR  DDRB
#define LED_PORT PORTB
#define LED_PIN  PINB
#define LED      PINB5

void delay(volatile unsigned long n) {
    while (n > 0) {
        n--;
    }
}

void task0_proc(void* param) {
    cli();
    printf("task0 enter\r\n");
    sei();

    /* turn on LED */
    LED_PORT |= _BV(LED);
    delay(800000);
    LED_PORT &= ~_BV(LED);
    delay(800000);

    cli();
    printf("task0 leave\r\n");
    sei();
    exitTASK();
}

void task1_proc(void* param) {
    cli();
    printf("task1 enter\r\n");
    sei();
    startTASK(0, NULL);
    cli();
    printf("task1 leave\r\n");
    sei();
    exitTASK();
}

void task2_proc(void* param) {
    cli();
    printf("task2 enter\r\n");
    sei();
    startTASK(1, NULL);
    cli();
    printf("task2 leave\r\n");
    sei();
    exitTASK();
}

void task3_proc(void* param) {
    cli();
    printf("task3 enter\r\n");
    sei();
    for (;;) {
        startTASK(2, NULL);
    }
}

const task_proc_t task_proc[TASK_NUM] = {
    task0_proc,
    task1_proc,
    task2_proc,
    task3_proc,
};

int uart_putchar(char c, FILE *fp) {
    loop_until_bit_is_set(UCSR0A, UDRE0);
    UDR0 = c;
    return 0;
}

int main(void) {
    LED_DDR |= _BV(LED);

    fdevopen( uart_putchar, NULL);

    printf("Start Kernel.\n");

    start();

    for (;;) {}    /* ここが実行されることはない */
}

実装解説

コンテキストスイッチの実装

手順は以下のようになっています。

  1. 現在の実行コンテキストに関する情報をスタック上に保存
  2. スタックポインタをタスクコントロールブロックに保存
  3. 切り替え先のタスクのスタックポインタを設定
  4. 実行コンテキストを復帰
タスクの起動

タスクを起動する際には、つじつまが合うようにスタック上のコンテキスト構造体を埋めてから復帰させればいいことになります。

スケジューラ

TCB配列の先頭から最初のREADY状態のタスクを選択しているだけです。

カーネルモードとシステムコールの追加

通常通りソフトウェア割り込み経由でカーネルモードに切り替えようと思いましたが、AVRにはソフトウェア割り込みがありません。通常はここで頭を抱えるのですが、AVRでは面白い仕掛けが施されています。通常、外部割り込みのポートは入力専用になっているのですが、AVRではこれを出力モードに設定でき、この状態の外部割り込みのポートに'1'を出力するとソフトウェアから外部割り込みを発生させることができます。そこで、これをソフトウェア割り込みの代用として利用しています。

まとめ

このように、素直なアーキテクチャのCPUならば3時間程度でOSの骨組みが作れてしまいます。さらに、Arduino Duemilanoveのように安価で簡単な開発環境も存在します。興味を持たれた方は、これをきっかけにOS自作やTOPPERS-ASPなどの世界に踏み込んでみませんか?

最後に

元々は教育用として作成した教材の派生物ですが、もう少し多機能にしてCortex-M3(NXP Xpresso 1343)に移植したりしたRTOSをBSDライセンスとして以下のURLで公開しています。

http://www.rts.soft.iwate-pu.ac.jp/mono/kernel/ukernel-s/index.html

投稿したコメントは管理者が承認するまで公開されません。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト

コメントを書くには、なぞなぞ認証に回答する必要があります。

リンク元