悩んでいる人
C言語で排他制御アルゴリズムを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
排他制御
排他制御は，1つのクリティカルセクションに複数のプロセス（またはスレッド）が同時に入ることを防ぐことです．
排他制御には，ハードウェアとソフトウェアの実装があります．
ハードウェアの実装はアーキテクチャ（x86-64，ARM64など）固有の専用命令（アトミック命令など）を利用します．
例えば，Linuxカーネルではアトミック命令を利用して排他制御を実現します．
Linuxカーネルの排他制御を知りたいあなたはこちらからどうぞ．
本記事では排他制御をソフトウェアで実装する方法を紹介していきます．
具体的には，以下のアルゴリズムを紹介します．
- デッカーのアルゴリズム
- ピーターソンのアルゴリズム
- ランポートのパン屋のアルゴリズム
本記事は以下の内容を理解していることを前提とします．
C言語で排他制御アルゴリズム
C言語で排他制御アルゴリズムを紹介します．
排他制御アルゴリズムは，ビジーウェイトを利用して実装します．
ただし，CPUのアウトオブオーダー実行やコンパイラの最適化により正常に動作しない場合があるので注意して下さい．
メモリバリア命令やvolatile型修飾子を利用すれば正常に実装可能です．
GCCではメモリバリア命令のビルトインである__sync_synchronize関数が実装されています．
コンパイラの最適化について深掘りしたいあなたは以下の記事を読みましょう！
デッカーのアルゴリズム
デッカーのアルゴリズムは，T・J・デッカーが提案したプロセスまたはスレッドが共有メモリを介してのみ通信する並行プログラミングにおける排他制御の最初のアルゴリズムです．
2スレッドの場合のデッカーのアルゴリズム
2スレッドの場合のデッカーのアルゴリズムは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> #include <pthread.h> #define LOOP_NUM 50000 #define NR_THREADS 2 volatile bool flags[NR_THREADS] = {0}; volatile int turn = 0; int total_count = 0; int counts[NR_THREADS] = {0}; void *func0(void *arg) { while (true) { /* acquire */ flags[0] = true; __sync_synchronize(); while (flags[1]) { if (turn != 0) { flags[0] = false; while (turn != 0) { } flags[0] = true; } __sync_synchronize(); } /* critical section */ counts[0]++; total_count++; /* yield */ turn = 1; flags[0] = false; __sync_synchronize(); /* exit */ if (counts[0] == LOOP_NUM) { break; } } return NULL; } void *func1(void *arg) { while (true) { /* acquire */ flags[1] = true; __sync_synchronize(); while (flags[0]) { if (turn != 1) { flags[1] = false; while (turn != 1) { } flags[1] = true; } __sync_synchronize(); } /* critical section */ counts[1]++; total_count++; /* yield */ turn = 0; flags[1] = false; __sync_synchronize(); /* exit */ if (counts[1] == LOOP_NUM) { break; } } return NULL; } int main(void) { pthread_t threads[NR_THREADS]; void *(*funcs[])(void *) = {func0, func1}; int i; for (i = 0; i < NR_THREADS; i++) { pthread_create(&threads[i], NULL, funcs[i], NULL); } for (i = 0; i < NR_THREADS; i++) { pthread_join(threads[i], NULL); } printf("total_count = %d\n", total_count); return 0; } |
実行結果は以下になります．
LOOP_NUMが50000で2スレッド実行したのでtotal_countが100000になっていることがわかります．
|
1 2 3 |
$ gcc dekker.c $ a.out total_count = 100000 |
nスレッドの場合のデッカーのアルゴリズム
nスレッド（n = 4に設定）の場合のデッカーのアルゴリズムは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdint.h> #include <stdbool.h> #include <stdatomic.h> #include <pthread.h> #define LOOP_NUM 50000 #define NR_THREADS 4 #define THREAD_MASK 0x1 atomic_uint flag = 0; unsigned int total_count = 0; void *func(void *arg) { uint32_t thread_id = *(uint32_t *) arg; uint32_t thread_mask = THREAD_MASK << thread_id; int i = 0; while (true) { if (atomic_fetch_or_explicit(&flag, thread_mask, memory_order_seq_cst) == 0) { i++; total_count++; } atomic_fetch_xor_explicit(&flag, thread_mask, memory_order_seq_cst); if (i == LOOP_NUM) { break; } } return NULL; } int main(void) { pthread_t threads[NR_THREADS]; unsigned int thread_ids[NR_THREADS]; int i; for (i = 0; i < NR_THREADS; i++) { thread_ids[i] = i; pthread_create(&threads[i], NULL, func, &thread_ids[i]); } for (i = 0; i < NR_THREADS; i++) { pthread_join(threads[i], NULL); } printf("total_count = %u\n", total_count); return 0; } |
実行結果は以下になります．
LOOP_NUMが50000で4スレッド実行したのでtotal_countが200000になっていることがわかります．
|
1 2 3 |
$ gcc dekker_n.c $ a.out total_count = 200000 |
ピーターソンのアルゴリズム
ピーターソンのアルゴリズムは，ゲイリー・ピーターソンが提案した通信のために共有メモリだけを使い2個以上のプロセスまたはスレッド間でリソースを競合することなく共有する排他制御アルゴリズムです．
2スレッドの場合のピーターソンのアルゴリズム
2スレッドの場合のピーターソンのアルゴリズムは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> #include <pthread.h> #define LOOP_NUM 50000 #define NR_THREADS 2 volatile bool flags[NR_THREADS]; volatile int turn = 0; int total_count = 0; void lock(int thread_id) { flags[thread_id] = true; turn = 1 - thread_id; __sync_synchronize(); while (flags[1 - thread_id] && turn == 1 - thread_id) { __sync_synchronize(); } } void unlock(int thread_id) { flags[thread_id] = false; __sync_synchronize(); } void *func(void *s) { int i = 0; int thread_id = *(int *) s; lock(thread_id); for (i = 0; i < LOOP_NUM; i++) { total_count++; } unlock(thread_id); return NULL; } int main(void) { pthread_t threads[NR_THREADS]; unsigned int thread_ids[NR_THREADS]; int i; for (i = 0; i < NR_THREADS; i++) { thread_ids[i] = i; pthread_create(&threads[i], NULL, func, &thread_ids[i]); } for (i = 0; i < NR_THREADS; i++) { pthread_join(threads[i], NULL); } printf("total_count = %d\n", total_count); return 0; } |
実行結果は以下になります．同様です．
|
1 2 3 |
$ gcc peterson.c $ a.out total_count = 100000 |
nスレッドの場合のピーターソンのアルゴリズム
nスレッド（n = 4に設定）の場合のピーターソンのアルゴリズムは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> #include <stdatomic.h> #include <pthread.h> #define LOOP_NUM 50000 #define NR_THREADS 4 volatile int flags[NR_THREADS] = {0}; volatile int turns[NR_THREADS - 1] = {0}; int total_count = 0; bool is_same_or_higher(int thread_id, int i) { int k; for (k = 0; k < NR_THREADS; k++) { if (k != thread_id && flags[k] >= i) { return true; } } return false; } void lock(int thread_id) { int i; for (i = 1; i < NR_THREADS; i++) { flags[thread_id] = i; turns[i - 1] = thread_id; __sync_synchronize(); while (is_same_or_higher(thread_id, i) && turns[i - 1] == thread_id) { __sync_synchronize(); } } } void unlock(int thread_id) { flags[thread_id] = 0; __sync_synchronize(); } void *func(void *s) { int i = 0; int thread_id = *(int *) s; lock(thread_id); for (i = 0; i < LOOP_NUM; i++) { total_count++; } unlock(thread_id); return NULL; } int main(void) { pthread_t threads[NR_THREADS]; unsigned int thread_ids[NR_THREADS]; int i; for (i = 0; i < NR_THREADS; i++) { thread_ids[i] = i; pthread_create(&threads[i], NULL, func, &thread_ids[i]); } for (i = 0; i < NR_THREADS; i++) { pthread_join(threads[i], NULL); } printf("total_count = %d\n", total_count); return 0; } |
実行結果は以下になります．同様です．
|
1 2 3 |
$ gcc peterson_n.c $ a.out total_count = 200000 |
ランポートのパン屋のアルゴリズム
ランポートのパン屋のアルゴリズムは，レスリー・ランポートが提案した排他制御アルゴリズムです．
デッカーのアルゴリズムやピーターソンのアルゴリズムとは異なり，ランポートのパン屋のアルゴリズムは最初からnスレッド（またはnプロセス）に対応するために設計されています．
ランポートのパン屋のアルゴリズム（n = 4に設定）は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> #include <stdatomic.h> #include <pthread.h> #define LOOP_NUM 50000 #define NR_THREADS 4 volatile int tickets[NR_THREADS] = {0}; volatile bool entering[NR_THREADS] = {false}; int total_count = 0; void lock(int thread_id) { int i; int ticket; int other; int max_ticket = 0; entering[thread_id] = true; for (i = 0; i < NR_THREADS; i++) { ticket = tickets[i]; if (ticket < max_ticket) { max_ticket = ticket; } } tickets[thread_id] = max_ticket + 1; entering[thread_id] = false; for (other = 0; other < NR_THREADS; other++) { __sync_synchronize(); while (entering[other]) { __sync_synchronize(); } while (tickets[other] != 0 && (tickets[other] < tickets[thread_id] || (tickets[other] == tickets[thread_id] && other < thread_id))) { __sync_synchronize(); } } } void unlock(int thread_id) { tickets[thread_id] = 0; __sync_synchronize(); } void *func(void *s) { int i = 0; int thread_id = *(int *) s; lock(thread_id); for (i = 0; i < LOOP_NUM; i++) { total_count++; } unlock(thread_id); return NULL; } int main(void) { pthread_t threads[NR_THREADS]; unsigned int thread_ids[NR_THREADS]; int i; for (i = 0; i < NR_THREADS; i++) { thread_ids[i] = i; pthread_create(&threads[i], NULL, func, &thread_ids[i]); } for (i = 0; i < NR_THREADS; i++) { pthread_join(threads[i], NULL); } printf("total_count = %d\n", total_count); return 0; } |
実行結果は以下になります．同様です．
|
1 2 3 |
$ gcc lamport_bakery.c $ a.out total_count = 200000 |
まとめ
C言語で排他制御アルゴリズムを紹介しました．
具体的には，デッカーのアルゴリズム，ピーターソンのアルゴリズム，ランポートのパン屋のアルゴリズムを解説しました．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
