■ Thread.とは
プログラムの実行される単位のこと。
プログラムを一本の流れとしてとらえると、この流れから分岐するひとつの糸のこと。
CPU に割り振られることで実行される
WARNING
切り替わるタイミングは CPU がアセンブラ単位で切り替える。
C++ で１行でかいてあるコードも実際はその中の任意の場所でかわるということ。
( ソースコード 1 行単位ではない )
同期とは終わるまでまつことで、非同期とは終わるまでまたない方法のこと。
通常の関数よびだしは同期する( おわるまで待つ )。
■ スレッドのつかいどころ
WARNING
スレッドを増やしても、意味のない用途がある。
スレッドを使うときは、ハードの資源以上は超えられない。
たとえば、 ハードディスクが１つしかなければ
ファイルアクセスをするスレッドを２つ以上、作成しても実際は１つしか実行されない。
ファイルのロードなどは 処理時間の大半が待ち時間 ( latency )なので
その空き時間を他のことに回すことができる。
■ スレッドの危険性をしる
SAMPLE
グロバール変数を同時に操作する
どのスレッドを実行するかは、OS が気まぐれで変更するため
共有オブジェクトへの操作は危険になる。
int gCnt;
// 共有オブジェクト gCnt をインクリメントする仕事
void jobAdd( void *ptr )
{
DWORD id = GetCurrentThreadId();
printf( "start thread id = %d\n", id );
for( int i=0; i< 1000*1000; i++ ){
gCnt ++; // 複数のスレッドから共有物を変更する。ここが危険
}
printf( "finish thread\n" );
}
const int N = 3;
HANDLE trd[N];
int i;
for( i=0; i< N; i++ ){
trd[i] = CreateThread( 0, 0,
(LPTHREAD_START_ROUTINE)jobAdd,
NULL, 0, 0 );
}
// 終了をまつ
for( i=0; i< N; i++ ){
WaitForSingleObject( trd[i], 10*1000 );
}
// この結果が毎回ことなる。
printf( "result gCnt %d\n", gCnt );
gCnt ++;
1. メモリ上にある gCnt を レジスタへ移動 ( MOV )
2. CPUで +1 ( ADD )する
3. その結果を メモリ gCnt へ戻す ( MOV )
gCnt ++;
1. A さん : メモリ上にある gCnt を レジスタへ移動 ( MOV )
2. B さん : メモリ上にある gCnt を レジスタへ移動 ( MOV )
3. A さん : CPUで +1 ( ADD )する
4. A さん : その結果を メモリ gCnt へ戻す ( MOV )
5. B さん : CPUで +1 ( ADD )する
6. B さん : その結果を メモリ gCnt へ戻す ( MOV )
■ 共有物にはロック(鍵)をかける
SAMPLE
鍵をかけてからグロバール変数を同時に操作する
そこで共有物を操作する間は、他のスレッドがさわらないようにロックをする。
これで自分だけが操作できる状態になる。
それには Mutex をつかう。
Mutex は複数のスレッドの交通整理をする。
Mutex は bool 変数のように ON/OFF できる。
他のスレッドが、鍵のかかった Mutex をさわろうとすると眠ってしまう。
Win32 Thread では EnterCriticalSection を利用する
// 鍵自体は共有物
CRITICAL_SECTION cs;
void jobAdd( void *ptr )
{
DWORD id = GetCurrentThreadId();
printf( "start thread id = %d\n", id );
// 鍵をかけてから
EnterCriticalSection( &cs );
// 自分だけ共有物を操作する
for( int i=0; i< 1000*1000; i++ ){
gCnt ++;
}
// 仕事が終わったら、すばやく鍵をはずすこと
LeaveCriticalSecttion( &cs );
printf( "finish thread\n" );
}
{
// 鍵の初期化と終了処理をついか
InitializeCriticalSection( &cs );
CreateThread( ... )
DeleteCriticalSection( &cs );
}
vector< int > a;
// これを複数のスレッドからよびだしてはいけない。
a.push_back( 10 );
■ 状態
スレッドにはいくつかの状態がある ( Program を利用する際は意識する必要なし )
待ち
何かの理由で動作できない状態
例えばセマフォの資源が取得できるようになるのを待っている, といった状態がこれに当たる
待ち状態のスレッドに CPU が割り当てられることはない
起動直後のスレッドは待ち状態か実行可能状態のどちらかになる
実行可能
CPU が割り当てられれば動作することができる状態
例えばセマフォの資源は取得できたが, 空いている CPU がない, といった状態
実行可能状態になったスレッドはスケジューラのキューに登録される
スケジューラは CPU に空きができるとキューからスレッドをとりだし CPU を割り当てる
CPU を割り当てられたスレッドは実行状態になる
実行
CPU が割り当てられ, スレッドが動作している状態
この状態で資源の残っていないセマフォの取得を行なったりすると待ち状態になる
POINT
sleep は明示的に待ち状態に移行する操作です
タイムアウト付きの sleep は一定時間たつと待ち状態から実行可能状態に移行する
yield は実行可能状態に移行する操作
自スレッド以外に実行可能状態の スレッドがいれば, そのスレッドに CPU が渡される
いなかった場合は再び自スレッドが実行状態になる
終了
スレッドが終了した状態
スレッドは終了してもすぐに全てのリソースを 解放するわけではない
終了状態のスレッドに CPU が割り当てられることはなく、別の状態に移行することもない
■ 排他処理
ある処理しているスレッドを同時に 1 つだけに限定させるような処理のこと
排他処理をしている区間をクリティカルセクション( 危険領域 ) という
排他処理はクリティカルセクションに入る, クリティカルセクションから出る,
と いった操作で実装できる
POINT
排他処理のオブジェクトは １つのデータを複数のスレッドで操作する場合に
破壊されないように保護するために使う。
// var に対する処理を 1 つのスレッドだけに限定させるため に排他処理をする
void Add(int n)
{
EnterCriticalSection();
var += n;
LeaveCriticalSecttion();
}
■ Mutex
ミューテックスは[ 排他処理 ]をするために使用されるオブジェクト
ミューテックスには取得されている, いないの 2つの状態があり
一度にミュー テックスを取得できるのは 1 つのスレッドだけ
取得できなかったスレッドは待ち状態になる
ミューテックスでクリティカルセクションをつくる場合は
クリティカルセク ションに入る前にミューテックスを取得し, クリティカルセクションから抜ける時にミューテックスを返却する
ミューテックスをもっていたスレッドがミューテックスを返却すると
ミューテックスを待っていたスレッドは実行可能状態になる
複数のスレッドが待ち状態になっていた場合
どのスレッドが実行可能状態に なるのかはスケジューラに依存する
Windows ではクリティカルセクションの作成に限定したオブジェクトがある
このオブジェクトはミューテックスよりも効率よく動作するので
排他処理を行なう場合, Windows ではミューテックスよりもクリティカルセクションを使う
POINT
ミューテックスは取得しているスレッドを覚えていて
取得していないミューテックスを返却することはできない
■ セマフォ(Semaphore)
セマフォもミューテックスと同じように取得されている, いないの状態をもつが
セマフォでは状態を資源数で管理する
資源数の最大値と現在値を持ち
セマフォを取得すると資源数の現在値が減り, 返却すると増える
セマフォは取得をしたスレッドを覚えていないので
セマフォを取得した状態でさらに取得することができ
セマフォを取得していないスレッドが返却もできる
1 つしか資源のないセマフォはミューテックスと同じようにクリティカルセクションを作るのにも使える
しかしミューテックスの方が効率的
POINT
セマフォは決められた数だけのスレッドがはいる時に使う。
ジョブキューでいうと、マスタが Increment すると、ワーカーは目を覚まして Decrement をする。
■ 排他処理
スレッドはあらゆるタイミングで別スレッドに切り替わる可能性がある
この特徴はスレッド間で共有の領域を操作している時に問題になる
1 をタス Code
static int counter;
void Increment()
{
counter++;
}
Increment: Register を利用する必要があるんだ. ^ ^/
0: load r0, counter # counter から r0 に値をロードする.
1: add r0, r0, 1 # r0+1 を r0 に設定する.
2: store counter, r0 # r0 を couner にストアする.
3: ret # 関数から帰る.
// ミューテックスをつかって排他処理をしてみる
// 共有 Object
static int cnt;
void inc()
{
mutex.lock(); // mutex.lock() はそれ以降のコードを実行するスレッドを 1 つに限定する効果がある
cnt++;
mutex.unlock(); // この効果は mutex.unlock() まで続く
}
■ 同期処理
スレッド間で[ 足並みを揃える ]ための処理
別のスレッドでしている処理の完了をまったり
別のスレッドからのリクエストを待つ, といった時に使う
/// 別のスレッドからのリクエストを待って, 何らかの処理を始め るために同期処理をする
void Main()
{
WaitEvent();
:
}
■ 同期オブジェクト
排他処理, 同期処理を実装する際には同期オブジェクトを使う
同期オブジェクトはある条件を満たすまでスレッドを待機させることができるようなオブジェクト
ミューテックスとセマフォはほとんどの環境にある
もしくは比較的簡単に実装することが可能
一方, 条件変数はプラット フォームのサポートがないと実装するのが難しいオブジェクト
■ Event(イベント)
Windows でよく使われる同期オブジェクト
イベントにはシグナルと非シグナルの 2 つの状態があり
プログラムからは イベントのシグナル状態を問い合わせたり待つことができる
状態が 2 つしかない点はミューテックスに似ているが
イベントはどのスレッドからでもシグナル, 非シグナル状態にできる
イベントにはシグナル状態の問い合わせ成功と同時に非シグナル状態になるものと
問い合わせ成功後もシグナル状態のままになっているものがある
POINT
イベントは mutex とちがってクエリをすることができる。
■ 同期処理
複数のスレッドはそれぞれ勝手なタイミングで動く
Thread A の結果を受けて Thread B が処理をする必要がある場合
Thread B は Thread A の動作が完了待ちをする必要がある
このように複数のスレッドが[ 足並みを揃える ]ような処理を同期処理という
POINT
同期処理はセマフォ, イベント, 条件変数などの同期オブジェクトを使って実装する
// Thread A の動作が完了したら Thread A は FinishThreadA() を呼ぶ
void FinishThreadA()
{
event.signal();
}
void WaitThreadA()
{
event.waitSignal();
}
■ アトミック操作
別のスレッドに割り込まれずに処理できるような[ 操作 ]をアトミックであるという
マルチスレッドプログラミングではアトミックであるかどうかが非常に重要
マルチスレッドで動作するプログラムであっても, 全ての処理をアトミックにする必要はない
必要があるのは, 全体のほんの一部 だけ
POINT
[ スレッド間で共有する領域を使っている処理はアトミックにする ] 必要がある
それ以外はアトミックである必要はない
static int counter;
// 共有領域なので, Atomic に操作する必要あり.
void Increment()
{
counter++;
}
void Decrement()
{
counter--;
}
// Threed Local なので
int Add(int counter, int val)
{
return counter+val;
}
int Sub(int counter, int val)
{
return counter-val;
}
POINT
2 つ以上の命令になってしまう処理は全て割り込まれる可能性がある
なにがアトミックなのか
どこまでをアトミックにするかを判断すること
Node *top;
void Push(Node *node)
{
node->prev = 0;
node->next = top;
if (top != 0) {
top->prev = node;
}
top = node;
■ リーダライタロック
マルチスレッドプログラミングでは, スレッド間で共有される領域を操作する
ときは排他処理をする必要がある
排他処理はミューテックスを用いて実装することが多いが
ミューテックスでは効率的ではないケースがある
共有領域に対する操作は読み込み, 書き込みに分類されるが
ほとんどの操作が読込みで, 書込みはほとんどしないことがある
POINT
読込み処理と読込み処理同士であれば排他処理は不要
読み込み処理同士は並列動作可能
ミューテックスでつくられたクリティカルセクションでは読込みしか行なわない操作であったとしても
同時に実行できるのは必ず 1 つのスレッド だけになる
この制限を解消するのがリーダライタロック
リーダライタロックには読込むためのロックと書き込むためのロックがある
ミューテックスと異なるのは読込みロック時でも読込みロックが成功する点だけ
このルールにより, 読み込み動作が並列で動作できるようになる
■ ロックフリー
マルチスレッドプログラミングではアトミックであることが非常に重要
アトミックな操作を実装するのには同期オブジェクトを使った排他処理がよくされるが
いくつかの問題がある
排他処理はコスト 0 の操作ではなく、それなりにコストがかかる処理
同期オブジェクトを使ってアトミックな処理を実装することは簡単で判りやすいが
パフォーマンス面で問題になることがある
ロックフリーは[ アトミックな操作を同期オブジェクトなどのロックを伴わずに実装する方法 ]です
ロックフリー なアルゴリズムでは同期オブジェクトのかわりに CPU で用意されている特別な命令を使う
たとえば compare-and-swap という操作がある compare-and-swap は以 下のような操作
int CAS(int *var, int cmp, int swap)
{
int prev = *var;
if (prev == cmp) {
*var = swap;
}
return prev;
}
多くの CPU には compare-and-swap をアトミックに.する命令が用意されている
_
_
_
