読む人へ

なるべくわかりやすく説明を行うつもりではありますが、
マルチスレッドにおけるStack(スタック)、Context Switching(コンテキストスイッチング)、Blocking(ブロッキング)等の概念をお持ちの方が対象でありますので予めご了承お願いします。
それから、本記事に関してはあくまで自己責任で参考までにさせてください。

はじめに

Embedded(組込み)S/W世界では多様なH/W構成に直面することが一般的であります。
特にIoTが流行ってる現時代ではOSまでも要らない小規模なH/W構成で完結する場合が多いです。

例えば、センサーをばら撒き、ある特定の場所の気温を計測したい場合は
考慮事項としてコストや省電等(他の要素もある)を考え、
最小限のH/W構成で気温装置を実現するのが求められます。

そんなH/W構成でリソース、特にメモリ等が限った時に役に立つ
Protothreads(プロトスレッド)を紹介しようと思います。

Protothreads(プロトスレッド)

プロトスレッドとは

小さな組み込みシステムやワイヤレスセンサーネットワークノードなど、
メモリに深刻な制約があるシステム向けに設計された非常に軽量なスタックレススレッドです。

プロトスレッドの特徴

非常に小さなRAMオーバーヘッド。
- 独自のスタックを持ってない。
- プロトスレッドごとにわずか2Byte使用。
移植性が高い
- 100％純粋なCであり、アーキテクチャ固有のアセンブリコードは無い。
OSの有無にかかわらず使用可能。
完全なマルチスレッドまたはスタックスイッチング無しでBlocking可能。
BSDのようなオープンソースライセンスの下で無料で利用可能。

Sample Code

Code

#include "pt.h"

#include <stdio.h>

static int protothread1_flag, protothread2_flag;

static int
protothread1(struct pt *pt)
{
  PT_BEGIN(pt);

  while(1) {
    PT_WAIT_UNTIL(pt, protothread2_flag != 0);
    printf("Protothread 1 running\n");

    protothread2_flag = 0;
    protothread1_flag = 1;
  }

  PT_END(pt);
}

static int
protothread2(struct pt *pt)
{
  PT_BEGIN(pt);

  while(1) {
    protothread2_flag = 1;

    PT_WAIT_UNTIL(pt, protothread1_flag != 0);
    printf("Protothread 2 running\n");
    
    protothread1_flag = 0;
  }

  PT_END(pt);
}

static struct pt pt1, pt2;
int
main(void)
{
  PT_INIT(&pt1);
  PT_INIT(&pt2);
  
  while(1) {
    protothread1(&pt1);
    protothread2(&pt2);
  }
}

Compileしてから実行すると下記の「Result」になります。

Result

pt-1.4$ ./a.out
Protothread 1 running
Protothread 2 running
Protothread 1 running
Protothread 2 running
・
・
・

どうでしょうか。

pthread等をプログラミングした経験をお持ちの方は
こんなに簡単にマルチスレッドが実現できるのをみて驚くかも知れないです。

Sample Codeの解析

まず、理解し易くするために、
protothreadsライブラリで定義されてるマクロを纏めて見ました。

  1 struct pt {
  2   lc_t lc;
  3 };
  4 
  5 #define LC_INIT(s) s = 0;
  6 #define LC_RESUME(s) switch(s) { case 0:
  7 #define LC_SET(s) s = __LINE__; case __LINE__:
  8 #define LC_END(s) }
  9 
 10 #define PT_INIT(pt)   LC_INIT((pt)->lc)
 11 #define PT_BEGIN(pt) { char PT_YIELD_FLAG = 1; LC_RESUME((pt)->lc)
 12 #define PT_WAIT_UNTIL(pt, condition)            \
 13   do {                                          \
 14     LC_SET((pt)->lc);                           \
 15     if(!(condition)) {                          \
 16       return PT_WAITING;                        \
 17     }                                           \
 18   } while(0)
 19 #define PT_END(pt) LC_END((pt)->lc); PT_YIELD_FLAG = 0; \
 20                    PT_INIT(pt); return PT_ENDED; }

これを元にSample Codeを解析すると
下記になります。

  /*                   protothread1,2関数のCall   1回目  2回目
  ==================================================================*/
  1 static int
  2 protothread1(struct pt *pt)
  3 {
  4   {
  5     char PT_YIELD_FLAG = 1;
  6 
  7     switch((pt)->lc) {
  8       case 0:                                 ①
  9 
 10     while(1) {
 11         do {
 12            pt->lc = 12; case 12:              ②    ⑩⑮
 13            if(!(protothread2_flag != 0)) {    ③    ⑪⑯
 14               return PT_WAITING;              ④    ⑰
 15            }
 16         } while(0);
 17         printf("Protothread 1 running\n")           ⑫
 18         protothread2_flag = 0;                      ⑬
 19         protothread1_flag = 1;                      ⑭
 20     } //wihle
 21 
 22     } //switch
 23 
 24     PT_YIELD_FLAG = 0;
 25     pt->lc = 0;
 26     return PT_ENDED;
 27   }
 28 }
 29 
 30 static int
 31 protothread2(struct pt *pt)
 32 {
 33   {
 34     char PT_YIELD_FLAG = 1;
 35 
 36     switch((pt)->lc) {
 37       case 0:                                  ⑤
 38 
 39     while(1) {
 40         protothread2_flag = 1;                 ⑥    ㉒
 41 
 42         do {
 43            pt->lc = 43; case 43:               ⑦    ⑱㉓
 44            if(!(protothread1_flag != 0)) {     ⑧    ⑲㉔
 45               return PT_WAITING;               ⑨     ㉕
 46            }
 47         } while(0);
 48         printf("Protothread 2 running\n");           ⑳
 49 
 50         protothread1_flag = 0;                       ㉑
 51     } //wihle
 52 
 53     } //switch
 54 
 55     PT_YIELD_FLAG = 0;
 56     pt->lc = 0;
 57     return PT_ENDED;         
 58   }
 59 }
 60 
 61 static struct pt pt1, pt2;
 62 int
 63 main(void)
 64 {
 65   &pt1->lc = 0;
 66   &pt2->lc = 0;
 67 
 68   while(1) {
 69     protothread1(&pt1);
 70     protothread2(&pt2);
 71   }
 72 }

お分かりますかね。
分かり易く、逐次的処理の流れに番号を付けました。
番号の順番通り、コードを読めばきっと分かるはずです。

念のため、重要な箇所は補足説明しておきます。
(もう既に理解した人はこの内容は飛ばしてください。)

補足説明

 72   while(1) {
 73     protothread1(&pt1);
 74     protothread2(&pt2);
 75   }

上記のmain関数で
最初にprotothread1、protothread２をそれぞれCallするのを1回目関数Callと
次回にCallするのを2回目関数Callと記載します。

まず、mainの方でprotothread1関数をCall(1回目関数Call)したら、
8行のcase 0(pt->lcの初期値が「0」であるため)から逐次的に処理します。

  8       case 0:

12行目でlcに12を設定してからは12行から処理を開始します。

 12            pt->lc = 12; case 12:              ②    ⑩⑮
 13            if(!(protothread2_flag != 0)) {    ③    ⑪⑯

それから、protothread2_flagが立つ([0]以外)までは「PT_WAITING」をReturnし、関数は終了します。

 12            pt->lc = 12; case 12:              ②    ⑩⑮
 13            if(!(protothread2_flag != 0)) {    ③    ⑪⑯
 14               return PT_WAITING;              ④    ⑰
 15            }

次は「protothread2」の関数をみましょう。
mainの方でprotothread2関数をCall(1回目関数Call)したら、
一旦、protothread2_flagを1に設定し、
protothread1_flagが立つ([0]以外)までは「PT_WAITING」をReturnし、関数は終了します。

 40         protothread2_flag = 1;                 ⑥    ㉒
 41 
 42         do {
 43            pt->lc = 43; case 43:               ⑦    ⑱㉓
 44            if(!(protothread1_flag != 0)) {     ⑧    ⑲㉔
 45               return PT_WAITING;               ⑨     ㉕
 46            }
 47         } while(0);

続いてprotothread1をCall(2回目関数Call)したら

 40         protothread2_flag = 1;                 ⑥    ㉒

のフラグが1として設定されてるので、下記の処理(「Protothread 1 running」を出力)を行います。

 17         printf("Protothread 1 running\n")           ⑫
 18         protothread2_flag = 0;                      ⑬
 19         protothread1_flag = 1;                      ⑭

次はprotothread2をCall(2回目関数Call)したら、

 19         protothread1_flag = 1;                      ⑭

のフラグが1として設定されてるので、

 48         printf("Protothread 2 running\n");           ⑳
 49 
 50         protothread1_flag = 0;                       ㉑

上記の出力(「Protothread 2 running」)処理を行います。

結局、「Protothread 1」 → 「Protothread 2」の出力処理を繰り返すことになります。

考察

Loop文中のswitch statement

  7     switch((pt)->lc) {
  8       case 0:                                 ①
  9 
 10     while(1) {
 11         do {
 12            pt->lc = 12; case 12:              ②    ⑩⑮
 13            if(!(protothread2_flag != 0)) {    ③    ⑪⑯

ところで、
解析のSample Codeの中で普段使っていないパターンもしくは
違和感を感じる箇所はありませんでしたか。

多分、do-whileのloop文の中にswitch statement(②のcase文)があることに拒否感を感じたのではないでしょうか。
その説明は論文¹から引用します。

This does seem surprising at first,but is in fact valid ANSI C code.
This use of the switch statement is likely to first have been publicly described by Duff as part of Duff’s device².
The same technique has later been used by Tatham to implement coroutines in C³.

意訳すると
初めてこんな処理を見ると驚きます。(自分も同感でした。^^)
しかし、実際には有効なANSI C Codeです。
こんなSwtich文のstatement使用は、Duff's device²の一部として公開されたようです。
その後、同じテクニックがcoroutines in C³にてTathamにより使われたようです。

ローカル変数

pthreadのSample Code

... 省略
 12 int
 13 main(int argc, char *argv[])
 14 {
... 省略
 18         ret1 = pthread_create(&thread1,NULL,(void *)f1,NULL);
 19         ret2 = pthread_create(&thread2,NULL,(void *)f2,NULL);
... 省略
 42 }
 43 
 44 void
 45 f1(void)
 46 {
 47         size_t i;
 48 
 49         for(i=0; i<8; i++){
 50             printf("one\n");
 51             usleep(3);
 52         }
 53 }
 54 
 55 void
 56 f2(void)
 57 {
 58         size_t j;
 59 
 60         for(j=0; j<4; j++){
 61             printf("two\n");
 62             usleep(2);
 63         }
 64 }

% ./pthread2
one
two
one
two
one
two
one
two
one
one
one
one

pthreadのマルチスレッドプログラミング経験者は特に注意すべきですが、
上記の「pthreadのSample Code」のようにマルチスレッドプログラミングではcontext Switchが行われるため、スレッドの中で定義したローカル変数(size_t i,size_t j)はマルチスレッドが並列で実行されてもお互いに影響なく、意図通りに実行されます。

しかし、protothreadsではcontext switchが行われないため、
Protothread 1関数である値を持ったローカル変数は再びProtothread 1関数の実行時には同じ値を保持していないのでローカル変数にはstatic修飾子を付けるか、Global変数に変えるかでstack(スタック)メモリを使わない工夫が必要になります。

参考例

... 省略
static int
protothread1(struct pt *pt)
{
  PT_BEGIN(pt);

  static uint32_t cnt = 0;

  while(1) {
    PT_WAIT_UNTIL(pt, protothread2_flag != 0);
    printf("Protothread 1 running, count =%d\n", cnt++);
... 省略
  }

  PT_END(pt);
}
... 省略

Constraints on Switch Constructs

protothreadsはswitch文と一緒に使えない制約があります。
詳細は論文¹から引用します。

programs cannot utilize switch statements together with protothreads. If a switch statement is used by the program using protothreads, the C compiler will in some cases emit an error, but in most cases the error is not detected by the compiler. This is troublesome as it may lead to unexpected run-time behavior which is hard to trace back to an erroneous mixture of one particular implementation of protothreads and switch statements.

意訳すると
protothreadsを使用するprogramにてswitchステートメントを使うと
C Compilerがエラーを出す場合があります。
しかし、エラーはほとんどの場合、コンパイラーから検出されないです。
これは、protothreadsとswitch文で一つの特定実装が誤ったらBacktraceも難しい、予想できないRuntime動作に繋がるため、問題になります。

Possible C Compiler Problems

C compilerで問題が発生する可能性があります。
詳細は論文¹から引用します。

It could be argued that the use of a non-obvious, though standards-compliant, C construct can cause problems with the C compiler because the nested switch statement may not be properly tested. We have, however, tested protothreads on a wide range of C compilers and have only found one compiler that was not able to correctly parse the nested C construct. In this case, we contacted the vendor who was already aware of the problem and immediately sent us an updated version of the compiler. We have also been in touch with other C compiler vendors, who have all assured us that protothreads work with their product.

実装例

このprotothreadsは実際にどこで使われているかをみましょう。

マイクロIP(μIP)

μIPは小規模な8ビットまたは16ビットのマイクロコントローラーで使用することを想定したTCP/IPのプロトコルスタックのオープンソース⁴であります。
protothreadsの開発者である「Adam Dunkels」さんがこのμIPも開発してます。
当然ながら、同開発者なのでこのμIPにはprotothreadsが使われております。すごいですね。
(個人的にはマイコンでTCP/IP Serverを立てる時にすごく役に立ちました。)

Nordic SD card library

Nordic SD card ライブラリ⁵では、coroutinesの実装にProtothreadsを使用してます。
SD cardコマンドのresponseを待つ時のBlocking処理等に使われてます。

おわりに

簡易でありながらSample Codeの解析とここまでの説明だと
protothreadsの仕組みについてはある程度理解はできたと思います。
その上、Arduino、RaspberryPi等のデバイスで実際に試してみては如何でしょうか。
きっとマルチスレッド化の手軽さとコードの軽量化に驚く程感じ取ると思います。