C LANGUAGE TECHNOLOGY

【C言語】排他制御アルゴリズム

悩んでいる人

C言語で排他制御アルゴリズムを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

排他制御

排他制御は,1つのクリティカルセクションに複数のプロセス(またはスレッド)が同時に入ることを防ぐことです.

排他制御は,ハードウェアとソフトウェアの方法がありますので,それぞれ解説していきます.

本記事は以下の内容を理解していることを前提とします.

C言語 スレッド
【C言語】スレッドの生成と実行【pthread,マルチスレッド,スレッドIDの取得】

こういった悩みにお答えします. こういった私から学べます. 目次1 スレッド2 pthreadによるマルチスレッドプログラミング3 pthreadでスレッドIDの取得3.1 pthread_self関 ...

続きを見る

C言語 ミューテックス
【C言語】ミューテックスとは

こういった悩みにお答えします. こういった私から学べます. 本記事ではスレッドとプロセスを理解している前提で説明します. スレッドとプロセスを学びたいあなたはこちらからどうぞ. 目次1 ミューテックス ...

続きを見る

C言語 _Atomic
【C言語】アトミック型修飾子「_Atomic」の使い方

こういった悩みにお答えします. こういった私から学べます. 本記事はC11規格のスレッドを理解していることを前提とします. 目次1 アトミック型修飾子「_Atomic」1.1 memory_order ...

続きを見る

C言語で排他制御アルゴリズム

C言語で排他制御アルゴリズムを紹介します.

排他制御アルゴリズムは,ビジーウェイトを利用して実装します.

ただし,CPUがアウトオブオーダー実行やコンパイラの最適化により正常に動作しない場合があるので注意して下さい.

メモリバリア命令やvolatile型修飾子を利用すれば正常に実装可能です.

GCCではメモリバリア命令のビルトインである__sync_synchronize関数が実装されています.

コンパイラの最適化について深掘りしたいあなたは以下の記事を読みましょう!

C言語 コンパイラ最適化
【C言語】コンパイラの最適化と戦うあなたへ

こういった悩みにお答えします. こういった私から学べます. 目次1 C言語のコンパイラの最適化による不具合2 C言語からアセンブリ言語への変換箇所を特定する方法3 ループ処理のコード例4 コンパイラの ...

続きを見る

デッカーのアルゴリズム

デッカーのアルゴリズムは,T・J・デッカーが提案したプロセスまたはスレッドが共有メモリを介してのみ通信する並行プログラミングにおける排他制御の最初のアルゴリズムです.

2スレッドの場合のデッカーのアルゴリズム

2スレッドの場合のデッカーのアルゴリズムは以下になります.

実行結果は以下になります.

LOOP_NUMが50000で2スレッド実行したのでtotal_countが100000になっていることがわかります.

nスレッドの場合のデッカーのアルゴリズム

nスレッド(n = 4に設定)の場合のデッカーのアルゴリズムは以下になります.

実行結果は以下になります.

LOOP_NUMが50000で4スレッド実行したのでtotal_countが200000になっていることがわかります.

ピーターソンのアルゴリズム

ピーターソンのアルゴリズムは,ゲイリー・ピーターソンが提案した通信のために共有メモリだけを使い2個以上のプロセスまたはスレッド間でリソースを競合することなく共有する排他制御アルゴリズムです.

2スレッドの場合のピーターソンのアルゴリズム

2スレッドの場合のピーターソンのアルゴリズムは以下になります.

実行結果は以下になります.同様です.

nスレッドの場合のピーターソンのアルゴリズム

nスレッドの場合のピーターソンのアルゴリズムは以下になります.

実行結果は以下になります.同様です.

ランポートのパン屋のアルゴリズム

ランポートのパン屋のアルゴリズムは,レスリー・ランポートが提案した排他制御アルゴリズムです.

デッカーのアルゴリズムやピーターソンのアルゴリズムとは異なり,ランポートのパン屋のアルゴリズムは最初からnスレッド(またはnプロセス)に対応するために設計されています.

ランポートのパン屋のアルゴリズムは以下になります.

実行結果は以下になります.同様です.

まとめ

C言語で排他制御アルゴリズムを紹介しました.

具体的には,デッカーのアルゴリズム,ピーターソンのアルゴリズム,ランポートのパン屋のアルゴリズムを解説しました.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , ,