Google
ブログ(iiyu.asablo.jpの検索)
ホットコーナー内の検索
 でもASAHIネット(asahi-net.or.jp)全体の検索です。
 検索したい言葉のあとに、空白で区切ってki4s-nkmrを入れるといいかも。
 例 中村(show) ki4s-nkmr

ウェブ全体の検索

コンピュータ、アーキテクチャ、プログラミング、同期・排他制御、ざっくりまとめ2019年12月20日 07時11分16秒

ASAHIネット(http://asahi-net.jp )のブログサービス、アサブロ(https://asahi-net.jp/asablo/ )を使っています。
---
 共有資源の排他制御は、やり方を間違えると大変。しかも、並行処理・並列処理だから、タイミングによってバグが出たり出なかったり、非常にやっかい。
 ほんとは、モデルをきちんと定義して、数学的に間違いないことを証明してから、それを実装するのがいいが、なかなかそうもいかない。
 そういうことをやるのが、形式仕様記述(Formal Methods)という分野。興味があれば、最後に関連するぼくのブログを挙げておきますので、読んでください。

 コンピュータの歴史の中で、複数のプロセス、スレッドの同期、クリティカルセクションの排他制御は、非常にたくさん研究され、いろんなモデル、概念、手法、実装がある。
 単一プロセッサ内でのマルチスレッド、マルチプロセスの世界から、マルチプロセッサ、さらにはネットワークでつながった広域分散アーキテクチャの世界まで、さまざまなアイデアと実装がある。
 ざっくりwikipediaレベルの解説をまとめてみた。

■同期、排他制御に関連する概念
https://ja.wikipedia.org/wiki/同期_(計算機科学)
https://ja.wikipedia.org/wiki/排他制御
https://ja.wikipedia.org/wiki/共有メモリ
https://ja.wikipedia.org/wiki/クリティカルセクション
https://ja.wikipedia.org/wiki/不可分操作
https://ja.wikipedia.org/wiki/デッドロック
https://ja.wikipedia.org/wiki/スレッド_(コンピュータ)
https://ja.wikipedia.org/wiki/スレッドセーフ
https://ja.wikipedia.org/wiki/アクターモデル
https://ja.wikipedia.org/wiki/ABA問題

■アーキテクチャレベル
https://ja.wikipedia.org/wiki/NUMA
https://ja.wikipedia.org/wiki/シェアード・ナッシング・アーキテクチャ
https://ja.wikipedia.org/wiki/ビジーウェイト
https://ja.wikipedia.org/wiki/プロセス間通信
https://ja.wikipedia.org/wiki/キャッシュメモリ
https://ja.wikipedia.org/wiki/キャッシュコヒーレンシ
https://ja.wikipedia.org/wiki/バススヌーピング
 バススヌーピングは、スヌープキャシュともいわれる。

■ハードウェアレベル
 これらのハードウェアのサポートをベースに、後述、ソフトウェアレベルの実装が行われる。
https://ja.wikipedia.org/wiki/テスト・アンド・セット
https://ja.wikipedia.org/wiki/コンペア・アンド・スワップ
https://ja.wikipedia.org/wiki/フェッチ・アンド・アッド
https://ja.wikipedia.org/wiki/Load-Link/Store-Conditional

■ソフトウェアレベル
 OSのAPIでのサポートもさまざま。
 プログラミング言語では、専用構文を設けてサポートするものやライブラリレベルでサポートするものなど、さまざま。
 次のリストは、大体、下にいくほど抽象化レベルが高くなっているつもり。

https://ja.wikipedia.org/wiki/セマフォ
https://ja.wikipedia.org/wiki/ロック_(情報工学)
https://ja.wikipedia.org/wiki/スピンロック
https://ja.wikipedia.org/wiki/ミューテックス
https://ja.wikipedia.org/wiki/Lock-freeとWait-freeアルゴリズム
https://en.wikipedia.org/wiki/Readers–writer_lock
https://ja.wikipedia.org/wiki/リード・コピー・アップデート
 read-copy-update、RCU
https://ja.wikipedia.org/wiki/モニタ_(同期)
 モニタの説明の中に、条件変数の説明もある。
https://ja.wikipedia.org/wiki/メッセージ_(コンピュータ)
 メッセージの説明の中に、メッセージパッシングの説明もある。
https://ja.wikipedia.org/wiki/ソフトウェアトランザクショナルメモリ
https://ja.wikipedia.org/wiki/Future_パターン
 いわゆるFutureとPromise。C++やJavaScriptにも入っている。

 ざっくり、言語やライブラリのサポートでいうと。
 C++には、アトミック変数、ミューテックス、Future/Promiseがある。
 Javaの同期・排他制御のモデルの基本はモニタ。Futureもある。
 Scalaは、いっぱいある(笑)。
 Erlang, Elixirはメッセージパッシング(メールボックス)。
 Clojureはソフトウェアトランザクショナルメモリ(STM)もサポート。
 FutureとPromiseは、多くの言語で利用可能。最近だと、JavaScriptというかECMA Scriptに入った。

https://docs.scala-lang.org/ja/overviews/core/futures.html
ScalaのFutureとPromise
https://cpprefjp.github.io/reference/future/future.html
C++のstd::future
https://cpprefjp.github.io/reference/future/promise.html
C++のstd::promise

形式仕様記述(フォーマルメソッド、Formal Methods) 関連:
http://iiyu.asablo.jp/blog/2018/11/01/8986910
RISC-V原典 オープンアーキテクチャのススメ。FPGAマガジンNo.18 Googleも推す新オープンソースCPU RISC-Vづくり。FPGAマガジン、いろいろやっとるわ。FPGAと(形式手法, Formal Methods)
http://iiyu.asablo.jp/blog/2018/10/30/8985607
テスト駆動開発(TDD)より、形式手法(フォーマルメソッド、形式仕様記述、Formal Methods)。九州大学(九大)の荒木啓二郎先生が、熊本高等専門学校(熊本高専)の校長に!記念、形式手法とネットワーク技術シンポジウム
http://iiyu.asablo.jp/blog/2006/08/20/491884
形式仕様記述(フォーマルメソッド、Formal Methods)
https://ja.wikipedia.org/wiki/SPINモデルチェッカ

■おまけ
 C++のatomic変数は、ミューテックスより、より基本的、原始的なもの。処理が軽いが、使うのは難しい。ロックフリーなアルゴリズムの実装にも使えるが、ちゃんと動く実装は、ほんとに頭のいい人たちがやらないとだめ。
 ミューテックスは、atomic変数に比べたら遅いが、抽象化が進んでいるので、使うのが楽。
 std::lock_guardなどと一緒に使う。そうしないと、ロックを開放し忘れたりする。

 C++のstd::lock_guard, std::unique_lockなどは、コンピュータサイエンスの同期・排他制御でいうロックとは違う。コンピュータサイエンス一般でいうロックは、低レベルなプリミティブだが、C++のstd::lock_guard, std::unique_lockなどは、ミューテックスなどロック可能オブジェクト(Lockableなオブジェクト)を安全に使うためのクラスになっている。

 std::promise, std::futureは、抽象度が高いクラスで、スレッド間でデータを渡すのに使うといい。
https://cpprefjp.github.io/reference/future/future.html
C++のstd::future
https://cpprefjp.github.io/reference/future/promise.html
C++のstd::promise

 C++には、セマフォがないが、次は、C++11のきれいなコードで、セマフォを実装している。
https://yohhoy.hatenadiary.jp/entry/20120323/p1
yohhoyの日記 技術的メモをしていきたい日記
2012-03-23
mutexの制約とバイナリセマフォ

コメント

コメントをどうぞ

※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。

※なお、送られたコメントはブログの管理者が確認するまで公開されません。

※投稿には管理者が設定した質問に答える必要があります。

名前:
メールアドレス:
URL:
次の質問に答えてください:
一富士、二鷹、三は? ひらがなで。

コメント:

トラックバック