並行スレッドとは、その名が示すように「協調ルーチン」のことです。オペレーティング・システムの概念であるスレッドとは異なり、並行処理は、プログラミング言語の構文的セマンティクスを使用した、ユーザー空間でのマルチタスクと論理的に類似したプログラミング技術です。Knuthによると、「サブルーチンは並行スレッドの特別なケース」であり、サブルーチンはサブ関数呼び出しであるため、並行スレッドはプログラムの関数に似たコンポーネントであり、何十万もの関数呼び出しと同じように、スレッドの中に何十万もの並行スレッドを簡単に作成することができます。ただし、サブルーチンは呼び出しのエントリーポイントが1つしかなく、戻ると終了しますが、連結のエントリーポイントは開始ポイントにも前のリターンポイントからの実行の継続ポイントにもなります。もちろん、Knuthの「特別な場合」とは、連結がルーチンを模倣することもできるという事実を指しており、これは非対称連結と呼ばれています。
イベント・ドリブン・モデルに基づく
例として、対称的なスレッド呼び出しのシナリオを見てみましょう。最も馴染みのある「生産者-消費者」イベント駆動モデルで、一方のスレッドが商品を生産してキューに追加する役割を担い、もう一方のスレッドがキューから商品を取り出して使用する役割を担います。効率化のために、一度に複数の製品を追加したり削除したりしたいとします。擬似コードは次のようになります：
# producer coroutine
loop
while queue is not full
create some new items
add the items to queue
yield to consumer
# consumer coroutine
loop
while queue is not empty
remove some items from queue
use the items
yield to producer
ほとんどの教科書はマルチスレッドの例としてこのモデルを使用していますが、実際にはマルチスレッドはまだ少し「ヘビー級」のアプリケーションです。 降伏セマンティクスがないため、スレッドはグローバルリソースの状態を生成しないように同期メカニズムを使用せざるを得ず、必然的にスリープ、スケジューリング、コンテキストの切り替えなどのシステムオーバーヘッドや、スレッドスケジューリングにおけるタイミングの不確実性が発生します。このため、スリープ、スケジューリング、コンテキストの切り替えなどのシステムオーバーヘッドや、スレッドスケジューリングにおけるタイミングの不確実性が必然的に発生します。並行スレッドの「ハングアップ」の概念は、単にコードを実行する権利を移譲して別の並行スレッドを呼び出すことであり、移譲された並行スレッドが終了すると、再び呼び出されてハングアップ開始点から「ウェイクアップ」されます。このような並行スレッド間の呼び出しは論理的に制御可能であり、タイミング的にも決定論的であるため、すべてが制御下にあります。この種のプロセス間呼び出しは論理的に制御可能で、タイミングも決定され、すべてが制御下にあります。
現在、並行セマンティクスを持つ言語には、C#、erlang、golangなどのヘビー級から、python、lua、javascript、rubyなどのライト級、scala、schemeなどの関数型があります。これに対して、本来の言語であるCは、スタックフレームと呼ばれるルーチンの呼び出しに依存しており、ルーチンの状態や戻り値はスタック上に保持されるため、プロデューサーとコンシューマーが同じレベルで呼び合うことができないという厄介な立場にありますが、もちろん、プロデューサーをメインルーチンとして使い、プロダクトをパラメーターとしてコンシューマールーチンを呼び出すように書き換えることもできますが、これは大変ですし、見た目も悪いです。しかし、そのようなコードは、特にスレッド数が100,000のオーダーになると、書くのが大変で、見た目も非常に硬くなります。
各同時プロセスのコンテキストがスタック以外の場所に格納されている場合、同時並行プロセス同士が呼び出したときに、呼び出された同時並行プロセスがスタック以外の場所から譲り受けたポイントのコンテキストを復元するだけで、CPUのコンテキストスイッチに多少似ていますが、残念ながら低レベルのアセンブリ言語でしかできないようです。
C言語ではマルチスレッドしかないのでしょうか？幸いなことに、Cの標準ライブラリには2つの並行スケジューリングプリミティブが用意されています。1つはsetjmp/longjmpで、もう1つはucontextコンポーネントです。ucontextコンポーネントは並行スレッドのコンテキスト切り替えを内部的に実装しており、前者に比べてかなり不確実なアプリケーションであるため、後者の方が広く使われており、インターネット上のCの並行ライブラリの大部分もucontextコンポーネントの実装に基づいています。ucontext コンポーネント。
「フライ級」コプロセッサ・ライブラリ
ここでは、オープンソースの "フライ級 "Cプログラミング・ライブラリであるprotothreadsを紹介したいと思います。 これは、完全にANSI Cで書かれたライブラリで、"フライ級 "と呼ばれています。フライ級」と呼ばれるのは、実装がこれ以上無駄がなく、ほとんど原始言語レベルだからです。実際、プロトスレッドライブラリ全体をリンクしてロードする必要はありません。なぜなら、ソースコードはすべてヘッダであり、サードパーティライブラリに依存せず、どのプラットフォームでも移植可能なSTLに似ているからです。もちろん、この合理化は、次の分析で示すように、使用上の制限という代償を伴います。
まずは、protothreads の作者であるスウェーデンの王立工科大学出身のコンピュータの天才、 Adam Dunkels から始めましょう。彼は、BSDライセンスのもと、たくさんの軽量な作品を書いています。ところで、軽量なオープンソースソフトウェアは世界中にたくさんありますが、この人ほど有名な人はあまりいません。例えば、組み込みネットワークOSのContikiや、おなじみのTCP/IPスタックのuIPやlwIPも彼の手によるものです。これらのソフトウェアはすべて、何十年もの間、エンタープライズ・アプリケーションでテストされてきたもので、その品質は想像に難くありません。
多くの人は、このような「軽量」なコードがどのようにして実現されているのか不思議に思うことでしょう。Protothreadsのソースコードを分析する前に、C言語の基礎について再教育したいと思います;-^) 一言で言えば、C言語の特性の中の「トリック」を利用しています。もちろん、すべての人にこれを使うことを推奨しているわけではありませんし、実際に言語のコードルールを破っているわけですから、クビになりたくなければ、深刻なプロジェクトでは慎重に扱うべきです。
C 言語「yieldセマンティクス”
pythonのyieldセマンティクス関数は反復ジェネレータに似ていて、関数が呼び出されたときの状態を保持し、次に呼び出されたときに前のリターンポイントから継続することはご存知でしょう。C言語では次のようになります：
int function(void) {
int i;
for (i = 0; i < 10; i++)
return i; /* won't work, but wouldn't it be nice */
}
この関数は10回連続して呼び出され、0から9を返すことができます。goto文を使うことができます。また、関数に状態変数を追加すれば、このようなことが可能になります：
int function(void) {
static int i, state = 0;
switch (state) {
case 0: goto LABEL0;
case 1: goto LABEL1;
}
LABEL0: /* start of function */
for (i = 0; i < 10; i++) {
state = 1; /* so we will come back to LABEL1 */
return i;
LABEL1:; /* resume control straight after the return */
}
}
#p#
これは有効です。yieldが必要なすべての場所にラベルを貼り付けます。各ラベルには番号が振られ、その番号がステート変数に格納され、次の呼び出しでどのラベルにジャンプするかを知らせます。何度呼び出されても、ステート変数のswitch文がジャンプ先のラベルを見つけます。
しかし、それでも見づらい。最悪なのは、すべてのラベルを手作業で管理する必要があり、関数内のラベルと冒頭のswitch文のラベルが一致するようにしなければならないことです。新しいreturn文を追加するたびに、新しいラベル名を考えてswitch文に追加しなければなりません。return文を削除するたびに、対応するラベルも削除しなければなりません。これでは、コードを管理する労力が2倍になってしまいます。
考えてみれば、switch文を使ってジャンプ先を決定する代わりに、switch文そのものを使ってジャンプすればいいのです：
int function(void) {
static int i, state = 0;
switch (state) {
case 0: /* start of function */
for (i = 0; i < 10; i++) {
state = 1; /* so we will come back to "case 1" */
return i;
case 1:; /* resume control straight after the return */
}
}
}
なるほど！実は、C言語はアセンブリ言語から派生したもので、switch-caseはif-elseと同様、アセンブリの条件ジャンプ命令の代替実装にすぎません。また、__LINE__マクロを使うことで、より一般的にすることもできます：
int function(void) {
static int i, state = 0;
switch (state) {
case 0: /* start of function */
for (i = 0; i < 10; i++) {
state = __LINE__ + 2; /* so we will come back to "case __LINE__" */
return i;
case __LINE__:; /* resume control straight after the return */
}
}
}
これにより、マクロを使ってパラダイムを抽出し、コンポーネントにカプセル化することができます：
#define Begin() static int state=0; switch(state) { case 0:
#define Yield(x) do { state=__LINE__; return x; case __LINE__:; } while (0)
#define End() }
int function(void) {
static int i;
Begin();
for (i = 0; i < 10; i++)
Yield(i);
End();
}
全く新しい言語を発明したように見えますか？実は、switch-caseの分岐の性質とコンパイル済みの__LINE__マクロを使って暗黙のステートマシンを実装し、最終的に「降伏セマンティクス」を実現しているのです。
このあまり知られていないテクニックをプロジェクトに嬉々として適用し、自分の手柄にすることに成功したとき、上司がそのコードをどう思うかという問題もあります。 完全に一致しないマクロ定義の中括弧、コードブロック内の未使用ケースのインクルード、BeginマクロとYieldマクロ内の不完全な7......あなたは単にコーディング規範を守らない会社の正反対の例です！
ここでプログラミングの仕様を使うのはおかしい。記事で紹介されているコード例はそれほど長くも複雑でもないので、ステートマシン的に書き換えてもまだ理解できます。しかし、コードが長くなればなるほど、書き換えは難しくなり、書き換えによる直感の喪失はかなりのものになります。
次のような小さなコードブロックを含む関数を考えてみてください：
case STATE1:
/* perform some activity */
if (condition) state = STATE2; else state = STATE3;
コードを見る人にとっては、これは以下の小さなコードブロックを含む関数と大差ありません：
LABEL1:
/* perform some activity */
if (condition) goto LABEL2; else goto LABEL3;
そうです、2つの関数の構造は見た目には同じで、関数に実装されたアルゴリズムを見るには、どちらの関数も同じように不利なのです。コプロセッサ・マクロを使ったことであなたをクビにしたのと同じ人が、小さなコードの塊とgoto文で構成される関数を書いたことであなたを怒鳴るでしょう。なぜなら、そのように設計された関数は、アルゴリズムの構造を大きく狂わせてしまうからです。
プログラミング仕様の目標はコードの明瞭性です。スイッチやリターン、case文のような重要なものを、「目隠し」の役割を果たすマクロで隠してしまうと、プログラミング標準の観点からは、プログラムの構文を乱していることになり、明瞭性の要件に違反することになります。しかし、それはプログラムのアルゴリズム構造を強調するためであり、コードを見る人がもっと知りたいことなのです。
構文の明瞭さのためにアルゴリズムの明瞭さを犠牲にするようなプログラミング仕様は、すべて書き直すべきです。もし上司がこのテクニックを使ったことを理由にあなたを解雇したら、セキュリティがあなたをドアから引きずり出すときにこのことを伝え続けてください。
個人的には、連結自体はシングルスレッドでの解決策なので、アプリケーション環境はシングルスレッドであること、コードの再入力の問題がないことを前提に、コードのシンプルさと可読性を維持するために思い切って静的変数を使ってもいいのではないかと思います。実際、このような初歩的な連結の使用はマルチスレッド環境では考慮すべきではありませんが、どうしても必要な場合は、前述のglibcのucontextコンポーネントが有効な代替手段となり、連結-プライベートスタックコンテキストを提供します。
#p#
プロトスレッドの文脈
サイモン・タサム（Simon Tatham）さんの素晴らしい教えのおかげで、ソースコードをハックする時が来ました。プロトスレッドを実装するデータ構造を見てみましょう。 これは実際には、状態変数を保持するコプロセッサのコンテキスト構造で、「スタック」の長さが2バイトしかない理由はすぐにわかると思います：
struct pt {
lc_t lc;
}
この中には短い変数が1つだけありますが、これは実際には最後のイールドポイントのプログラムカウンタです。これはまた、スレッドに対する連結の柔軟性を示しています。連結はスタックレスにすることができるので、プロデューサー-コンシューマーモデルのようなイベント通知のような単一の関数を実装する必要がある場合、連結が保持する必要がある状態変数は実際には単なるプログラムカウンタです。pythonのジェネレータもスタックレスですが、もちろん反復ジェネレータを実装する場合、前のCの例のように静的変数で最後の反復を保持する必要があるかもしれませんし、コンテキスト構造に追加されるメンバ変数を設定することもできます。連結でスケジューリングするときにどれだけのステート変数を保持する必要があるか本当にわからない場合は、オンラインドキュメントで詳しく説明されているように、コンテキストがスタックとシグナルを提供し、リソースの割り当てをユーザーに任せるucontextを使う方がよいでしょう。
typedef struct ucontext {
struct ucontext_t *uc_link;
sigset_t uc_sigmask;
stack_t uc_stack;
...
} ucontext_t;
Protothreadsprotothreadsとコンポーネント
少し話がそれたので、プロトスレッドに戻り、提供されているコプロセッシングの「プリミティブ」を見てみましょう。ANSI Cでは、伝統的なswitch-case文です：
#define LC_INIT（s） s = 0; // 源码中是有分号的，一个低级 bug，啊哈～
#define LC_RESUME(s) switch (s) { case 0:
#define LC_SET(s) s = __LINE__; case __LINE__:
#define LC_END(s) }
LC_RESUMEとLC_ENDの間のコードでswitch-caseステートメントを使用することはできません！このため、protothreadsはGNU Cベースのディスパッチ「プリミティブ」を実装しました。また、GNU Cにはラベルポインタという構文糖があり、これは&&で始まるラベルで、voidポインタ型で保存し、gotoジャンプすることができます：
typedef void * lc_t
#define LC_INIT(s) s = NULL
#define LC_RESUME(s) \
do { \
if (s != NULL) { \
goto *s; \
}
} while (0)
#define LC_CONCAT2(s1, s2) s1##s2
#define LC_CONCAT(s1, s2) LC_CONCAT2(s1, s2)
#define LC_SET(s) \
do { \
LC_CONCAT(LC_LABEL, __LINE__): \
（s） = &&LC_CONCAT(LC_LABEL, __LINE__); \
} while (0)
まあ、前の基本で、これらの "プリミティブ "を理解することは簡単なことですが、次の "コンポーネント "を構築する方法を見て、またprotothreads APIは、最初のコプロセッサスケジューリングステートマシンとして4つの終了コードを定義しました：
#define PT_WAITING 0
#define PT_YIELDED 1
#define PT_EXITED 2
#define PT_ENDED 3
以下のAPIは、アプリケーションから直接呼び出すことができます：
/* スレッドの初期化、すなわち状態変数の初期化 */
#define PT_INIT(pt) LC_INIT((pt)->lc)
/* 声明一个函数，返回值为 char 即退出码，表示函数体内使用了 proto thread，（个人觉得有些多此一举） */
#define PT_THREAD(name_args) char name_args
/* 並行スレッドのエントリーポイント， PT_YIELD_FLAG=0譲歩を表示する，=1表示不出让，放在 switch 语句前面，下次调用的时候可以跳转到出让点继续执行 */
#define PT_BEGIN(pt) { char PT_YIELD_FLAG = 1; LC_RESUME((pt)->lc)
/* 終了点。スレッドが終了し、すべてのコンテキストとフラグがクリアされる。 */
#define PT_END(pt) LC_END((pt)->lc); PT_YIELD_FLAG = 0; \
PT_INIT(pt); return PT_ENDED; }
/* 协程出让点，如果此时协程状态变量 lc 已经变为 __LINE__ 跳转过来的，那么 PT_YIELD_FLAG = 1，は、譲り受けた点から実行を継続することを示す。 */
#define PT_YIELD(pt) \
do { \
PT_YIELD_FLAG = 0; \
LC_SET((pt)->lc); \
if(PT_YIELD_FLAG == 0) { \
return PT_YIELDED; \
} \
} while(0)
/* 追加オファー条件 */
#define PT_YIELD_UNTIL(pt, cond) \
do { \
PT_YIELD_FLAG = 0; \
LC_SET((pt)->lc); \
if((PT_YIELD_FLAG == 0) || !(cond)) { \
return PT_YIELDED; \
} \
} while(0)
/* 协程阻塞点(blocking),本质上等同于 PT_YIELD_UNTIL，只不过退出码是 PT_WAITING，信号ボリュームの同期をシミュレートする */
#define PT_WAIT_UNTIL(pt, condition) \
do { \
LC_SET((pt)->lc); \
if(!(condition)) { \
return PT_WAITING; \
} \
} while(0)
/* 同 PT_WAIT_UNTIL 条件逆転 */
#define PT_WAIT_WHILE(pt, cond) PT_WAIT_UNTIL((pt), !(cond))
/* 协程调度，调用协程 f 并检查它的退出码，直到协程终止返回 0，否则返回 1。 */
#define PT_SCHEDULE(f) ((f) < PT_EXITED)
/* 这用于非对称协程，调用者是主协程，pt 是和子协程 thread （可以是多个）关联的上下文句柄，主协程阻塞自己调度子协程，直到所有子协程终止 */
#define PT_WAIT_THREAD(pt, thread) PT_WAIT_WHILE((pt), PT_SCHEDULE(thread))
/* 用于协程嵌套调度，child 是子协程的上下文句柄 */
#define PT_SPAWN(pt, child, thread) \
do { \
PT_INIT((child)); \
PT_WAIT_THREAD((pt), (thread)); \
} while(0)
一時的にそんなに導入され、ユーザーはまた、信号の実装などのコンポーネントを拡張する独自のニーズに基づいてすることができます、あなたは信号のオペレーティングシステム環境のうち、とてもシンプルであることがわかります：
struct pt_sem {
unsigned int count;
};
#define PT_SEM_INIT(s, c) (s)->count = c
#define PT_SEM_WAIT(pt, s) \
do { \
PT_WAIT_UNTIL(pt, (s)->count > 0); \
--(s)->count; \
} while(0)
#define PT_SEM_SIGNAL(pt, s) ++(s)->count
生産者-消費者モデルの元の例に戻って、プロトスレッドのパフォーマンスを見てみましょう。
#p#
Protothreads
#include "pt-sem.h"
#define NUM_ITEMS 32
#define BUFSIZE 8
static struct pt_sem mutex, full, empty;
PT_THREAD(producer(struct pt *pt))
{
static int produced;
PT_BEGIN(pt);
for (produced = 0; produced < NUM_ITEMS; ++produced) {
PT_SEM_WAIT(pt, &full);
PT_SEM_WAIT(pt, &mutex);
add_to_buffer(produce_item());
PT_SEM_SIGNAL(pt, &mutex);
PT_SEM_SIGNAL(pt, &empty);
}
PT_END(pt);
}
PT_THREAD(consumer(struct pt *pt))
{
static int consumed;
PT_BEGIN(pt);
for (consumed = 0; consumed < NUM_ITEMS; ++consumed) {
PT_SEM_WAIT(pt, &empty);
PT_SEM_WAIT(pt, &mutex);
consume_item(get_from_buffer());
PT_SEM_SIGNAL(pt, &mutex);
PT_SEM_SIGNAL(pt, &full);
}
PT_END(pt);
}
PT_THREAD(driver_thread(struct pt *pt))
{
static struct pt pt_producer, pt_consumer;
PT_BEGIN(pt);
PT_SEM_INIT(&empty, 0);
PT_SEM_INIT(&full, BUFSIZE);
PT_SEM_INIT(&mutex, 1);
PT_INIT(&pt_producer);
PT_INIT(&pt_consumer);
PT_WAIT_THREAD(pt, producer(&pt_producer) & consumer(&pt_consumer));
PT_END(pt);
}
ソースパッケージのexample-buffer.cには、実行可能な完全な例が含まれているので、私はそれをすべて掲載することはありません。全体的なフレームワークは、メインスレッド driver_thread と2つのサブスレッド producer と consumer を含む非対称コルーチンです。コードは非常に明快で直感的です。 単純なイベント処理要件をシングルスレッドで実装することが可能で、システムのオーバーヘッドやリソース使用量を増やすことなく、何十万ものスレッドを自由に追加することができます。唯一の注意点は、プロトスレッドはスタックレスであるため、ローカル変数がないことです。しかし、実行環境はシングルスレッドであることが前提であり、単純化された要件に使用する「ローカル変数」はそれほど多くないため、問題にはなりません。反復ジェネレータのように、連結時に追加の状態を格納する必要がある場合は、数とサイズが定義され制御されている限り、連結コンテキスト構造を自分で拡張すればよいのです。
もちろん、これはプロトスレッドが万能であると言っているわけではありません。以下にprotothreadsの限界のいくつかを列挙します：
- 連結はスタックレスなので、その変数が連結の状態に無関係でない限り、ローカル変数を使用しないようにしてください。
- コプロセッサがswitch-caseプリミティブでカプセル化されたコンポーネントを使用する場合、GNU C構文でラベル付きポインタに置き換えられない限り、実用的なアプリケーションでのswitch-case文の使用は禁止されています。
- 連結の内部では、ライブラリ関数やシステム・コールなどの他のルーチンを呼び出すことができますが、そのルーチンがノンブロッキングであることを確認する必要があります。結局のところ、スレッドは実行の最小単位であり、並行スレッドは "タイム・スライス・ローテーション "のルーチンに過ぎません。
公式ウェブサイトには、さらに多くのサンプルがあり、どれも非常に便利です。さらに、Craig Graham というエンジニアが pt.h を拡張し、protothreads が sleep/wake/kill などの操作をサポートするようにしました。
