この記事は、インテル® ソフトウェア・ネットワークに掲載されている「Using Locks Effectively in Parallel Programming (http://software.intel.com/en-us/articles/using-locks-effectively-in-parallel-programming-v4/)」の日本語参考訳です。
**********************************************
研究論文のタイトル:
並列プログラミングにおけるロックの効率的な使用
研究分野:
並列プログラミングにおけるロックの効率的な使用
チーム ID: TC2009028
著者名:
Rishabh Rao
6th semester, Department of Information Science & Engineering
(rishabhsrao@hotmail.com)
Narendra G S
6th semester, Department of Information Science & Engineering
(naren_2110@yahoo.com)
Naga Anudeep Reddy
4th semester, Department of Computer Science & Engineering
(deepuneo@gmail.com)
Faculty Mentor:
Mr. Manjunath
Department of Computer Science & Engineering
(majubt_rvce@yahoo.co.in)
機関名:
JSS Academy of Technical Education, Bangalore
**********************************************
1. 抄録:
マルチスレッド/並列プログラムでデータの正当性を維持するにはスレッドの同期が必要です。そして、競合状態を防ぐためにロックが使用されます。本論文ではこのロックを効率的に使用するための最適化手法について述べます。
本論文では、最初にマルチスレッドの必要性と競合状態の問題点について説明し、その後、ロックの手法を紹介します。手法には、最小限のクリティカル・セクションの使用、スピンロック、待機スレッドのブロック、複数のロックの使用、高水準 API の使用、ロック・マネージャーの使用、読み取り/書き込みロックの使用が含まれます。これらの手法の長所と短所についても説明します。
2. 背景:
シングルスレッドの (特に GUI ベースの) プロセスで複雑な操作 (大きなテキストファイルの印刷、プロセッサー負荷の高い計算の実行、非常に遠距離のサーバーへの接続など) を行うと、システムが反応しなくなることがあります。この問題は、インテル® ハイパースレッディング・テクノロジー [ref. W1b] の登場やマルチコア・プロセッサーの普及とともに、マルチスレッド/並列プログラミングのパラダイムの助けを借りて解決できるようになりました。
このマルチスレッド/並列プログラミングのパラダイムにより、プライマリー・スレッドを実行しながら追加のセカンダリー・スレッドをバックグラウンドで実行することが可能になりました。各スレッド (プライマリーまたはセカンダリー) はプロセスにおけるユニークな実行パスとなり、すべての共有データに対して同時アクセスを行います。
マルチスレッド化によりアプリケーションのパフォーマンスは向上しますが、競合状態と呼ばれる新しい問題も発生します。
3. 問題ステートメント:
競合状態は、機器やシステムが (ハイパースレッディング・テクノロジーを使用して、あるいはマルチコア・プロセッサー上で) 2 つ以上の操作を同時に行おうとした際に発生する望ましくない状態です。システムの特性により、操作を正しく完了するには操作を適切なシーケンスで行う必要があります。
例えば、T1 と T2 の 2 つのスレッドが、どちらも共有の整変数 ‘i’ (初期値 0) を 1 だけインクリメントするとします。また、スレッド T1 はレジスター r_A (初期値 0) を、スレッド T2 はレジスター r_B (初期値 0) を使用するとします。
理想的な操作 (擬似機械語命令) のシーケンスを以下に示します。
‘i’ の最終的な値は 2 になります。ただし、競合状態問題により、実際には以下のシーケンスで操作が行われます。
ここでも、’i’ の初期値は 0 であると仮定しています。並行する命令は (ハイパースレッディング・テクノロジーを使用して、あるいはマルチコア・プロセッサー上で) 並列に実行されることに注意してください。
‘i’ の最終的な値は予想値の 2 ではなく、1 になります。
原因は、両方のスレッドが共有変数 ‘i’ を同時に読み取って変更したため、データが無効になったことです。つまり、2 つのスレッド間の同期が行われていなかったために、共有メモリーリソースへのアクセスが制御されなかったことが原因です。
4. 手法:
同期の鍵となるのはモニター (セマフォーとも呼ばれる) の概念です。モニターは、mutually exclusive (相互排他) ロックまたは mutex として使用されるオブジェクトです。一度に同じモニターを所有できるスレッドは 1 つだけです。スレッドがロックを獲得すると、そのスレッドはモニター (またはクリティカル・セクション) に入ったことになります。
最初のスレッドがモニターから出るまで、ロックされたモニターに入ろうとするほかのすべてのスレッドは休止されます (またはオペレーティング・システムに応じた別のアクションが行われます)。これらのほかのスレッドは、モニター (ロック) を待機しているスレッドと呼ばれます。
4.1. ロックの手法:
4.1.1. 最小限のクリティカル・セクションの使用:
理想としては、スレッドは必要最小限の処理のみをクリティカル・セクションで実行すべきです。
例えば、以下のシーケンスの代わりに、
以下のようにシーケンスに変更することを推奨します。
4.1.2. スピンロック:
スレッドがクリティカル・セクションにある場合、そのクリティカル・セクションに入ろうとするほかの処理は、エントリーコード内で連続してループする必要があります。この種類のセマフォーは、スレッドがロックを待っている間「スピン」するため、スピンロックと呼ばれます。
POSIX.1c PThreads を使用したスピンロックの実装例を以下に示します。
echoThis() 関数は、標準出力にテキストを出力するすべてのスレッドから呼び出されます。この関数は、一度に 1 つのスレッドのみが標準出力にテキストを出力できることを保証します。
/* spinlock.cpp */
#include
<pthread.h>
#include <iostream>
using namespace std;
/* create a mutex lock */
static pthread_spinlock_t echoLock;
void *echoThis(void *text){
/* spin until lock is acquired */
if(pthread_spin_lock(&echoLock))
{
/* error acquiring spin lock */
/* NOTE: if the lock is already acquired by another thread, */
/* then it is not an error, the thread will simply spin */
/* until the lock is acquired */
perror("pthread_spin_lock");
}
/* lock was successfully acquired */
/* ***** START OF CRITICAL SECTION ***** */
/* print the text */
cout << "TID: " << pthread_self() << "\t\tTEXT: " << (char *) text << endl << flush;
/* ***** END OF CRITICAL SECTION ***** */
/* release the lock */
if(pthread_spin_unlock(&echoLock))
{
/* error releasing lock */
perror("pthread_spin_unlock");
}
/* lock successfully released */
}
int main(int argc, char *argv[])
{
/* create as many threads as the number of command line arguments */
int maxThreads = argc - 1;
int i;
pthread_t tid;
/* initialize the spin lock */
if(pthread_spin_init(&echoLock, PTHREAD_PROCESS_PRIVATE))
{
/* error initializing lock */
perror("pthread_spin_init");
}
/* create threads which will call echoThis */
for(i = 1; i <= maxThreads; i++)
{
/* create a thread with the default properties */
if(pthread_create(&tid, NULL, echoThis, argv[i]))
{
/* error creating thread */
perror("pthread_create");
}
}
/* wait for all the threads to join */
while(!pthread_join(tid, NULL))
{
/* do nothing */
;
}
/* destroy the spin lock */
if(pthread_spin_destroy(&echoLock))
{
/* error removing the spin lock */
perror("pthread_spin_destroy");
}
return 0;
}
/* end of spinlock.cpp */
上記の例において、main() 関数はスピンロック echoLock を初期化して、同じプロセスのすべてのスレッドで使用できるようにします。次に、echoThis() 関数を呼び出し標準出力にコマンドライン引数を表示するスレッドを、コマンドライン引数ごとに 1 つずつ作成します。echoThis() 関数は同時に 1 つのスレッドのみを処理するので、この関数を同時に呼び出すスレッドの数は重要ではありません。
上記プログラムの 2 つの実行結果を以下に示します。
このプログラムを実行した環境構成は以下のとおりです。
プロセッサー: インテル® Pentium® D プロセッサー 2.80GHz
RAM: 1024MB
OS: Knoppix 5.1 (KDE デスクトップ環境で X Window System を使用)
スレッドモデル: POSIX
コンパイラー: gcc バージョン 4.1.2 20061028 (プレリリース版) (Debian 4.1.1-19)
$ g++ spinlock.cpp -lpthread $ ./a.out The quick brown fox jumps over the lazy dog TID: 3049794480 TEXT: jumps TID: 3066571696 TEXT: brown TID: 3083348912 TEXT: The TID: 3041405872 TEXT: over TID: 3033017264 TEXT: the TID: 3074960304 TEXT: quick TID: 3016240048 TEXT: dog TID: 3058183088 TEXT: fox <p>$ ./a.out The quick brown fox jumps over the lazy dog TID: 3075533744 TEXT: quick TID: 3058756528 TEXT: fox TID: 3050367920 TEXT: jumps TID: 3041979312 TEXT: over TID: 3083922352 TEXT: The TID: 3067145136 TEXT: brown TID: 3033590704 TEXT: the TID: 3025202096 TEXT: lazy TID: 3016813488 TEXT: dog $
確かに echoThis() 関数は一度に 1 つのスレッドのみ処理していますが、コマンドライン引数の順序が正しくありません。また、最初の実行では、”lazy” に対応するスレッドが未知のバグにより全く実行されていません。
4.1.3. 待機スレッドのブロック:
この手法はスピンロックのビジーウェイト手法に似ています。ただし、ロックを待つ代わりにスレッド自身をブロックします。ブロック操作はロックに関連する待機キュー (Solaris ではターンスタイルとしても知られる) にスレッドを入れてスレッドを待機状態に切り替えます。次に、その制御は CPU スケジューラーに移され、実行する別のスレッドが選択されます。
上記の spinlock.cpp プログラムにこの手法を使用した echotext.cpp を以下に示します。
以下のコードのほとんどの部分は、spinlock.cpp と同じであることに注意してください。わかりやすいように、同じコードが記述されている部分は代わりに /* … */ で表記してあります。
/* echotext.cpp */
/* ... */
/* create a mutex lock */
static pthread_mutex_t echoLock;
void *echoThis(void *text)
{
/* acquire the mutex lock */
if(pthread_mutex_lock(&echoLock))
{
/* error acquiring lock */
perror("pthread_mutex_lock");
}
/* ... critical section code here ... */}
int main(int argc, char *argv[]){
/* ... */
/* initialize the mutex lock */
if(pthread_mutex_init(&echoLock, NULL))
{
/* error initializing lock */
perror("pthread_mutex_init");
}
/* ... */
/* remove the mutex */
if(pthread_mutex_destroy(&echoLock))
{
/* error removing the mutex */
perror("pthread_mutex_destroy");
}
/* ... */
}
/* end of echotext.cpp */
4.1.4. 複数のロックの使用:
mutex ロックは対象のクリティカル・セクションが長くなるとともに非効率的になる傾向があります。単純なソリューションは、クリティカル・セクションを小さなサブセクションに分割して、各サブセクションをロックすることです。
ここでは、1 つの大きなクリティカル・セクションが 3 つの独立した共有データ/リソースを保護しています。あるスレッドがクリティカル・セクションに入ると、ほかのスレッドはそのスレッドがクリティカル・セクションを出るのを待つ必要があります 。
各共有データ/リソースに個別のロックを提供するほうが効率的です。その結果、3 つのスレッドがそれぞれのクリティカル・セクションに同時に入ることができるようになります。
4.1.5. 高水準 API の使用:
セマフォーは便利で効率的なスレッド同期化のメカニズムを提供しますが、使用法が正しくないと、これまでどおりタイミングエラーが発生することがあります。これらのエラーはある特定の実行シーケンスでのみ発生し、そのシーケンスは毎回実行されるとは限らないため、検出が困難です。この状況は、プログラマーのプログラミング・エラーにより発生します。
このようなプログラミング・エラーを減らすには、Java (synchronized キーワード [ref. TB3]) や C# (lock キーワード [ref. TB2]) などの単純で優れた高水準スレッド同期 API を使用すると良いでしょう。これにより、プログラミングも容易になり、エラーも減少します。
Java での実装例を以下に示します。main() 関数は ThreadCreator クラスを使用して 4 つのサンプルスレッドを作成します。そして、ThreadCreator クラスは、Printer クラスの printThis() 関数を呼び出して各スレッドの引数を出力します。
printThis() 関数では、スレッドがしばらくスリープすることに注意が必要です。この結果、スレッド・スケジューラーにより別のスレッドへのコンテキストスイッチが行われ、競合状態が発生します。printThis() 関数には synchronized キーワードが使用されているので、1 つのスレッドのみ関数に入ることができます。つまり、printThis() 関数へのアクセスはシリアルに行われます。
package threadsynch;
class Printer{
synchronized void printThis(Thread t, String text)
{
System.out.println("My thread ID: " + t);
/* let the current thread sleep */
/* so that the thread-scheduler context-switches */
/* to another thread, introducing a race condition */
try
{
Thread.sleep(100);
}
catch(InterruptedException exp)
{
System.out.println("INTERRUPTED: Thread.sleep()");
}
/* now print the string */
System.out.println("My payload: " + text);
}
}
class ThreadCreator implements Runnable{
String txt;
Printer dest;
Thread thr;
/* Initialize and create the threads */
public ThreadCreator(Printer d, String t)
{
dest = d;
txt = t;
thr = new Thread(this);
thr.start();
}
public void run()
{
dest.printThis(thr, txt);
}
}
public class Main{
public static void main(String[] args)
{
Printer destination = new Printer();
/* Create 4 sample threads */
ThreadCreator tc1 = new ThreadCreator(destination, "the quick");
ThreadCreator tc2 = new ThreadCreator(destination, "brown fox");
ThreadCreator tc3 = new ThreadCreator(destination, "jumps over");
ThreadCreator tc4 = new ThreadCreator(destination, "the lazy dog");
/* Wait for all threads to join */
try
{
tc1.thr.join();
tc2.thr.join();
tc3.thr.join();
tc4.thr.join();
}
catch(InterruptedException exp)
{
System.out.println("INTERRUPTED: Thread.join()");
}
}
}
上記プログラムは、次のような結果を出力します。
My thread ID: Thread[Thread-0,5,main] My payload: the quick My thread ID: Thread[Thread-1,5,main] My payload: brown fox My thread ID: Thread[Thread-3,5,main] My payload: the lazy dog My thread ID: Thread[Thread-2,5,main] My payload: jumps over
ここでは、スレッドの生成順序とテキストの出力順序が同じである必要はありません。
synchronized キーワードを使用しないでコードを記述した場合、
class Printer{
synchronized void printThis(Thread t, String text)
{
つまり、上記のコードを下記のように変更した場合、
class Printer{
void printThis(Thread t, String text)
{
関数は同期されなくなります。同期を行わない場合は、次のような実行結果になります。
My thread ID: Thread[Thread-0,5,main] My thread ID: Thread[Thread-1,5,main] My thread ID: Thread[Thread-2,5,main] My thread ID: Thread[Thread-3,5,main] My payload: the quick My payload: jumps over My payload: brown fox My payload: the lazy dog
すべてのスレッドが printThis() 関数に同時に入って処理を完了しようとするため、スレッド間で競合が発生します。その結果、出力順序が変わります。
4.1.6. ロック・マネージャーの使用:
この手法は、食事する哲学者の問題 (Dining Philosophers’ Problem) [ref. TB1] で食卓にウェイターを配置する解法と似ています。ロック・マネージャーは、ロックを競っているスレッドのうちの 1 つに mutex を渡します。このスレッドは、クリティカル・セクションを出るとロック・マネージャーに mutex を返します。次に、ロック・マネージャーは残りのスレッドから別のスレッドを選択し、同じ操作を繰り返します。ロック・マネージャーは、ロックを競っているスレッド (ブロックまたはスピンのいずれか) のキューを管理し、ある優先順位により順序付けを行います。
ロック・マネージャーの動作を簡単にまとめた図を以下に示します。
4.1.7. 読み取り/書き込みロックの使用:
読み取り/書き込みロックは mutex ロックに似ていますが、読み取り専用または書き込み専用目的で獲得できます。読み取り専用ロックは、1 つ以上のスレッドで同時に使用できます。
書き込み専用ロックは、同時に 1 つのスレッドのみ使用できます。読み取り専用または書き込み専用ロックを獲得しようとしているほかのスレッドは、ロックがリリースされるまで待つ必要があります。また、書き込み専用ロックを獲得しようとしているスレッドは、読み取り専用ロックがすべてリリースされるまで待つ必要があります。
5. 各手法のまとめ:
最小限のクリティカル・セクションを使用することでパフォーマンスは明らかに向上します。実装によっては、効率性を最大限に引き出すことができます。
スピンロックにはビジーウェイトが必要です。スレッドの連続ループは、別のスレッドが使用できる可能性のある CPU サイクルを浪費するため、シングル CPU コンピューターにおいて問題となります。スピンロックの長所は、スレッドが実行状態のままとなるため、コンテキストスイッチとスレッドの再スケジューリングが必要ないことです。場合によっては、命令の実行よりもコンテキストスイッチの実行に、より多くの CPU 時間が費やされることがあります。ロックが短時間だけ保持されると予想される場合、スピンロックは効率的です。
スピンロックの代わりに待機スレッドをブロックすることもできますが、この手法はスレッドのコンテキストスイッチのオーバーヘッドが大きくなります。そのため、この手法は長いクリティカル・セクションが含まれている場合に使用するべきです。
クリティカル・セクションを分割してより多くのロックを使用するのも 1 つの手法ですが、各サブセクションでスレッドがロックを競う時間が長くなるとパフォーマンスが低下するため、ロックを多くしすぎないように注意する必要があります。
高水準 API では特定の同期実装の詳細を見ることはできません。一般に内部実装ではプリミティブな同期ツールが使用されています。
同期問題を穏やかに解決する場合は、ロック・マネージャー手法が効率的です。しかし、ロック・マネージャー用にスレッドが 1 つ必要になるため、追加のオーバーヘッドが発生します。
読み取り/書き込みロックでは、少なくとも1 つの読み取りスレッドがロックを保持している間は書き込みスレッドがロックを獲得できないため、書き込みスタベーションが発生することがあります。読み取り/書き込みロックのバリエーションである書き込み優先ロックでは、キューにロックを待っている書き込みスレッドがある場合、新しい読み取りスレッドはロックを獲得できません。読み取り/書き込みロックの長所はもちろん、共有データを同時に読み取ることができることです。POSIX.1c では読み取り/書き込みロックを定義していません。
6.今後の改良の余地:
マルチスレッド/並列プログラミングの分野では標準化が遅れています。今後、IEEE、POSIX、ANSI、ISO のような国際機関による標準化が進み、世界中の開発者が互換性のあるアプリケーションを作成できるようになることが望まれます。
7. 結論:
万能なロック手法というものはありません。アプリケーションに適した最良の手法を選択するのはプログラマーの責任です。マルチスレッド/並列プログラミングのパラダイムが一般的になるとともに、より優れた同期ツールが求められるでしょう。
8. 引用文献:
8.1. Web/インターネットのリソース:
[W1a] SIGCSE thoughts: Preparing Students for Ubiquitous Parallelism: http://software.intel.com/en-us/blogs/2009/04/01/sigcse-thoughts-preparing-students-for-ubiquitous-parallelism/
[W1b] Intel Hyper-Threading technology: http://www.intel.com/products/ht/hyperthreading_more.html
[W1c] Intel Multi-Core Community: http://software.intel.com/en-us/multi-core/
[W1d] Intel Training: http://software.intel.com/en-us/developertraining/
[W1e] Intel Threading Glossary: http://software.intel.com/en-us/blogs/2008/5/07/parallel-programming-glossary-of-technical-terms/
[W1f] Intel Threading Knowledge Base: http://software.intel.com/en-us/articles/all/1/
[W2] ThinkingParallel.com
[W3] Wikipedia.org
[W4] CodeProject.com
[W5] Differences – mutex vs. semaphore: http://geekswithblogs.net/shahed/archive/2006/06/09/81268.aspx
[W6] Keyword Definitions: WhatIs.com and http://searchnetworking.techtarget.com/
[W7] Writing a Research Paper: http://owl.english.purdue.edu/workshops/hypertext/ResearchW/
[W8] How to avoid race conditions: http://www.asta.va.fh-ulm.de/LDP/HOWTO/Secure-Programs-HOWTO/avoid-race.html
[W9] POSIX.1c Thread (PThread) Tutorial: https://computing.llnl.gov/tutorials/pthreads/
[W10] Using Spin Locks (Multithreaded Programming Guide) – SUN Microsystems: http://docs.sun.com/app/docs/doc/816-5137/ggecq?a=view
8.2. 書籍:
[TB1] Operating System Concepts (6th edition) by Silberschatz, Galvin, Gagne (2002, John Wiley & Sons, Inc.)
[TB2] C# and the .NET Platform (2nd edition) by Andrew Troelsen (2003, Apress, Berkeley, CA, USA)
[TB3] The Complete Reference Java 2 (5th edition) by Herbert Schildt (2002, Tata McGraw Hill)
[TB4] Unix System Programming Using C++ (1st impression) by Terrence Chan (2008, Pearson Education, Inc.)
