スレッドの実装

### 概要
タイマー割り込み，putsの実装ができたので，いよいよスレッドを実装する．多くのCPUがそうであるように，atmega328pでも関数呼び出しや割り込み処理を実行する時，呼び出し元，あるいは割り込み前の処理に戻るためにプログラムカウンタ(PC)をこそっとスタックに積む．そして，`ret`あるいは`reti`を実行すると，スタックポインタの指すメモリに格納されたアドレスにジャンプする．そこで，スレッドごとにスタック領域を確保し，タイマー割り込みの割り込みハンドラでスタックポインタを切り替えることでスレッドの並列実行を実現する．
しかし，これらの処理は割り込み，スタックの切り替え，CPUの仕様に従う必要があるなど，複雑な処理になるので，できるだけ細かい手順で動作を確認しながら実装する．具体的には，以下のように進めていく．

1. `ret`による関数へのジャンプ
2. スレッド１つとタイマー割り込みの組み合わせ
3. スレッド２つで順番に切り替え
4. スレッドの終了

### スレッドを切り替えるには
大前提として，スレッドの切り替えは，割り込みハンドラで行う．割り込みハンドラは，以下のような実装になっている．

```intr.s
(略)
    in   r31, 0x3f ; SREG
    push r31
    in   r24, 0x3d ; save current sp low  to r22
    in   r25, 0x3e ; save current sp high to r23
    ldi  r28, lo8(_intrstack) ; save intrrstack lo byte to r28
    ldi  r29, hi8(_intrstack) ; save intrstack hi byte to r29
    out  0x3d, r28 ; save intrstack low   ; change sp to intrstack
    out  0x3e, r29 ; save intrstack high
    push r24
    push r25
    eor  r1, r1
                   ; (1)切り替わる前のコンテキスト
    rcall handle   ; (2)割り込みハンドラの実行．スレッドを切り替える
                   ; (3)切り替わったあとのコンテキスト
    pop r29        ; pop old sp hi  from intrstack
    pop r28        ; pop old sp low from intrstack
    out 0x3d, r28  ; set sp low
    out 0x3e, r29  ; set sp high   -> change sp to original
    pop r31        ; restore SREG to r31
    out 0x3f, r31  ; set SREG
(略)
    reti
```

ここで，割り込みハンドラの前後に着目すると，

1. タイマ割り込みが入って現在実行中のスタックにレジスタが退避される．
1. 割り込みハンドラで別のスレッドが選択される．
1. スタックからレジスタを復元し，割り込みを許可するとともにスタックのPCにジャンプする(`reti`).

という処理をしているので，(1)で積まれるスタックの順番に合わせてスタックのメモリのデータを作成し，関数のアドレスもそのスタックの一番下に積み，**作成したスタックの一番上のアドレスにスタックポインタを設定したら**，(3)の処理のスタックの復元処理が終わったあとに指定した関数にジャンプする．つまり，**コンテキストを切り替えられる**．(3)の部分では，この**スタックポインタの書き換え**は行わないので，コンテキストを切り替えるには，スタックポインタを書き換え，(3)の処理を実行すれば良い．そして，切り替えるスタックポインタをどうやって与えるか，だけど，関数の引数で渡すことにする．
[ここ](https://www.dbpro.xyz/avrwiki/wiki.cgi?page=avrgcc%A4%C7%A5%A2%A5%BB%A5%F3%A5%D6%A5%E9%A4%F2%BB%C8%A4%A6)によると，AVRでは第一引数に`r24`, `r25`を使うので，これを使ってアドレスをを受け取り，スタックポインタに設定したあと，(3)の処理を実行する関数を作れば良い．そして，この関数を割り込みハンドラ内部で呼び出すと，(3)の処理は実行されず，別のコンテキストの実行が再開される．つまり，**スレッドが切り替わる**．

### retによる関数ジャンプ
先のことを一気にはできないので，スタックを切り替えてコンテキストを復元し，`ret`で目的の関数にジャンプする，ことを目指す．具体的には，以下を実装する

1. スタックのための領域を確保
2. コンテキストを保存するための構造を定義
3. コンテキストの作成
4. コンテキストのスタックポインタを引数にとり，コンテキスト復元後に`reti`でジャンプする関数の作成と呼び出し

#### スタックのための領域を確保
リンカスクリプトを変更し，コンテキストのための領域(userstack)を確保する.

```ld.scr
MEMORY
{
(略)
    ram(rwx)        : o = 0x800100, l = 0x800600 - 0x800100
    userstack(rw)   : o = 0x800600, l = 0x000000 ; /* これ */
    intrstack(rw)   : o = 0x800700, l = 0x000000
    bootstack(rw)   : o = 0x8007fc, l = 0x000000
}
    .userstack : {
        _userstack = .;  /* これ */
    } > userstack

    .intrstack : {
        _intrstack = .;
    } > intrstack
```

#### コンテキストを保存するための構造を定義
スタックポインタと，スタックの底のアドレスを保持する構造(`context_t`)を定義する．

```c:main.c
typedef struct {
    char *stack;
    unsigned int sp;
} context_t;

static context_t *current = NULL;
static context_t contexts[1];
```

#### コンテキストの作成
コンテキストを作成するための関数を作る．また，`reti`の実行でジャンプしたい関数も定義する．

```c:main.c
void test_t() {    // retiでジャンプする関数
    puts("Hello\n");
}

void thread_end() {　// スレッドの実行が終わったときに呼ばれる関数．
    current = NULL;
    puts("end");
    while(1) {
    }
}

// コンテキストを作る関数
void thread_create() {
    int i;
    int stacksize = 128;  // とりあえずスタックサイズは128固定
    unsigned char *sp;
    extern char _userstack;
    static char *thread_stack = &_userstack;  // userstackアドレスを取得．0x600のはず
    current = &contexts[0];

    memset(current, 0, sizeof(*current));

    current->stack = thread_stack;           // コンテキストのstackにスタックの開始アドレスを設定
    memset(thread_stack - stacksize, 0, stacksize);
    thread_stack -= stacksize;               // 次のコンテキストのためにthread_stackをずらしておく

    sp = (unsigned char*) current->stack;    // spにスタックの開始アドレスがセットされる
    *(sp--) = (unsigned char) (((unsigned int)thread_end >> 0) & 0xff); // スレッドが終わったときに呼ばれる関数のアドレスをセット
    *(sp--) = (unsigned char) (((unsigned int)thread_end >> 8) & 0xff);  

    *(sp--) = (unsigned char) (((unsigned int)test_t >> 0) & 0xff); // コンテキストの切り替えで呼ばれる関数をセット
    *(sp--) = (unsigned char) (((unsigned int)test_t >> 8) & 0xff);

    *(sp--) = 0; // SREG

    for (i = 31; i >= 0; --i) { // 復元時のr0~r31の初期化
        *(sp--) = 0;
    }
    current->sp = (unsigned int)sp;  // spをcurrent->spに設定
}
```

#### retiでジャンプする関数
スタックのアドレスを受け取ってスタックポインタにセットし，`intr_time`の(3)を実行する関数をアセンブリ言語で定義する．

```intr.s
dispatch:
        mov r30, r24  ; 引数はr24, r25を使って渡される
        mov r31, r25  ; r30, r31はZレジスタの上位バイトと下位バイトである
        ld  r24, Z    ; Zレジスタに保存された値をアドレスとして考え，間接参照してr24に代入
        ldd r25, Z+1  ; Zをインクリメントし，間接参照してr25に代入
        out 0x3d, r24 ; スタックを設定．スタックのアドレスは0x3d, 0x3e
        out 0x3e, r25 ; set stack 
        pop r31       ; pop SREG レジスタの値を戻す
        out 0x3f, r31 ; set SREG
        pop r0
        pop r1
        pop r2
        pop r3
        pop r4
        pop r5
        pop r6
        pop r7
        pop r8
        pop r9
        pop r10
        pop r11
        pop r12
        pop r13
        pop r14
        pop r15
        pop r16
        pop r17
        pop r18
        pop r19
        pop r20
        pop r21
        pop r22
        pop r23
        pop r24
        pop r25
        pop r26
        pop r27
        pop r28
        pop r29
        pop r30
        pop r31
        reti
```
この実装から，`dispatch`はポインタを受け取ることがわかる(間接参照で値を取り出すから)．
なので，この関数のプロトタイプは

```c:
void dispatch(unsigned int *sp);
```
となる．

#### dispatchの呼び出し
以下のように`main`を書き換えて実行してみる

```c:main.c
int main(void) {
    INTR_DISABLE;

    vector_init();
    serial_init();

    thread_create();
    if (current != NULL) {
        puts("current go\n");
        dispatch(&current->sp); // ここで呼び出している
    }

//	timer_init();

    INTR_ENABLE;

    while (1) {
        puts("main\n");
    }

    return 0;
}

```
ここでは，タイマー設定をコメントアウトしているので，タイマー割り込みは入らない．そして，`thread_create`で`context`に`context[0]`を設定しているので，"current go"が出力されたあと`dispatch`が呼び出されるはずである．
また，`dispatch`から呼び出される関数は以下の２つ

```c:
void test_t() {    // retiでジャンプする関数
    puts("Hello\n");
}

void thread_end() {　// スレッドの実行が終わったときに呼ばれる関数．
    current = NULL;
    puts("end");
    while(1) {
    }
}
```

まず，`test_t`が呼び出され，"Hello"が出力されたあと，この関数の終わりでは`ret`が実行されるため，その次にスタックに積んだのが`thread_end`のアドレスなので"end"が出力され，その後`while(1)`の無限ループに入る．そのため，`main`の`puts("main\n")`に戻ることはない，となることが予想できる．

<img width="843" alt="Screen Shot 2019-07-17 at 12.43.39.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/57629/dadefff5-2e54-0e3d-1991-1811a35c3b0b.png">

実行すると，上記の結果を得る．動いているようだ．

この実装は，以下のコマンドで試すことができる

```
>git clone https://github.com/hiro4669/iosv.git
>cd iosv
>git branch thread_ver1 origin/thread_ver1
>git checkout thread_ver1
>cd thread
>make
>make write
```

### スレッド１つとタイマー割り込みの組み合わせ
次は，タイマー割り込みを使いつつ，`dispatch`呼び出してみる．そして，タイマー割り込みで呼び出す割り込みハンドラを以下のように変更する(`intr.s`の`intr_time`の`rcall`で呼び出す)．

```c:main.c

void test_t() {
    while (1) {
        puts("Hello\n");
    }
}


static int idx = 0;
void handle(unsigned int sp) {
    if (idx == 0) {
        idx = 1;
        puts("0\n");
    } else {
        idx = 0;
        puts("1\n");
    }
}
```
`idx`の値を出力することによって，割り込みが入ったことを確認できる．続いて，mainを書き換える．

```c:main.c

int main(void) {
    INTR_DISABLE;

    vector_init();
    serial_init();

    thread_create();
    timer_init();

    INTR_ENABLE;
    if (current != NULL) {
        dispatch(&current->sp);
    }
    while (1) {
        puts("main\n");
    }
    return 0;
}
```
この実装では，タイマーをONにし，その後`dispatch`を呼び出す．`dispatch`の呼び出しで実行する`test_t`は無限ループで，"Hello"を出力する．この関数が呼び出されると，定期的に"Hello"出力されるが，"Hello"の途中で割り込みが入るので，適当なタイミングで"0"と"1"が混在するはず．

<img width="844" alt="Screen Shot 2019-07-14 at 18.18.52.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/57629/943000ba-2dbf-42c2-66d5-460096f34032.png">

予想通り混在した．うまく動いているようだ．

この実装は，以下のコマンドで試すことができる

```
>git clone https://github.com/hiro4669/iosv.git
>cd iosv
>git branch thread_ver2 origin/thread_ver2
>git checkout thread_ver2
>cd thread
>make
>make write
```

### スレッド２つで順番に切り替え
`thread_create`を改良し，スレッドで実行する関数と，インデックスを引数に取るようにして2つのコンテキストを作る．そして，この2つを交互に実行してみる．

```c:main.c
void thread_create(thread_func f, int idx) {
    int i;
    int stacksize = 128;
    unsigned char *sp;
    extern char _userstack;
    static char *thread_stack = &_userstack;
    context_t *current = NULL;
    current = &contexts[idx];

    memset(current, 0, sizeof(*current));

    current->stack = thread_stack;
    memset(thread_stack - stacksize, 0, stacksize);
    thread_stack -= stacksize;

    sp = (unsigned char*) current->stack;
    *(sp--) = (unsigned char) (((unsigned int)thread_end >> 0) & 0xff);
    *(sp--) = (unsigned char) (((unsigned int)thread_end >> 8) & 0xff);

    *(sp--) = (unsigned char) (((unsigned int)f >> 0) & 0xff); // スレッドで実行する関数
    *(sp--) = (unsigned char) (((unsigned int)f >> 8) & 0xff);

    *(sp--) = 0; // SREG

    for (i = 31; i >= 0; --i) {
        *(sp--) = 0;
    }
    current->sp = (unsigned int)sp;
}
```

続いて，割り込みハンドラもスタックポインタを保存するように改良

```c:main.c
void handle(unsigned int sp) {
    contexts[idx].sp = sp; // ここでスタックを保存
    if (idx == 0) {
        idx = 1;
    } else {
        idx = 0;
    }
    dispatch(&contexts[idx].sp);
}
```

最後に，`main`関数で作成したコンテキストを実行するため，`dispatch`を呼び出す

```c:main.c

int main(void) {
    INTR_DISABLE;

    vector_init();
    serial_init();

    thread_create(test_t, 0);
    thread_create(test_t2, 1);
    timer_init();

    INTR_ENABLE;
    dispatch(&contexts[idx].sp); // dispatchの呼び出し．idxの初期値は0

    // ここにはこない
    while (1) {
        puts("CCCCC");
    }

    return 0;
}
```

こうした上で，スレッドで実行する関数を以下のように定義する

```c:main.c
void test_t() {
    while (1) {
        puts("ABCDEFG\n");
    }
}
void test_t2() {
    while (1) {
        puts("1234567\n");
    }
}
```
うまく行けば，"ABCDEFG"と"1234567"の文字列が混ざりあって出力されるはず

![Screen Shot 2019-07-18 at 12.12.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/57629/3a5694bf-8883-1ead-18cc-14b1f76e1539.png)

うまくいっているようです．

この実装は，以下のコマンドで試すことができる

```
>git clone https://github.com/hiro4669/iosv.git
>cd iosv
>git branch thread_ver3 origin/thread_ver3
>git checkout thread_ver3
>cd thread
>make
>make write
```