並行性とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 活用形辞書 > 並行性の意味・解説 

並行性

読み方:へいこうせい

名詞並行」に、接尾辞「性」がついたもの
日本語活用形辞書はプログラムで機械的に活用形や説明を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ

並行性

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/19 14:34 UTC 版)

ナビゲーションに移動 検索に移動
食事する哲学者の問題は、並行性とリソース共有に関する古典的問題

並行性(へいこうせい、: concurrency)とは、計算機科学において、時間的にオーバーラップして実行される計算を伴うシステムの属性であり、そのような計算ではリソースを共有することがある。並行計算は、同一チップ上の複数のコア、単一プロセッサ上のプリエンプションを伴うマルチスレッド、物理的に分離した複数プロセッサ上などで行われる。並行計算のための数学的モデルとして、ペトリネットプロセス計算並列ランダムアクセス機械モデル、アクターモデルReo Coordination Language英語版 などが開発された。

問題

並行システムにおける計算は実行中に互いにやりとりできるため、考えられる実行経路は極めて多くなり、結果としてシステム全体が不確定英語版となる。共有リソースの並行使用が不確定性の源となる可能性もあり、デッドロックリソーススタベーションといった問題を引き起こす[1]

並行システムの設計では応答時間を最小化しスループットを最大化するため、データ交換、メモリ割り当て、実行スケジューリングなどに関わる技術の信頼性を追求する[2]

理論

並行性理論は、1960年代カール・アダム・ペトリが独創的なペトリネットの研究を行って以来、理論計算機科学の主要な研究領域となっている。以来、並行システムを理解するための様々な理論モデル、論理、ツールが開発されてきた。

モデル

モデル開発と並行システムの理解のための形式手法には様々なものが開発されてきた。以下に主なものを列挙する[3]

これら並行性モデルの一部は、第一に推論と仕様記述を目的としている。一方、他のモデルは開発サイクル全体(並行システムの設計、実装、証明、テスト、シミュレーション)をサポートすることを目的としている。

並行性モデルが乱立したことから、一部の研究者はそれら理論モデル群を統合する方法を模索することを考えた。例えば Lee と Sangiovanni-Vincentelli は各種並行性モデルの表示的意味論を定義する共通フレームワークを提供すべく "tagged-signal" モデルを提唱した[5]。一方、Nielsen、Sassone、Winskel は各種モデルを統合理解するのに圏論が有効であるとした[6]

アクターモデルにおける Concurrency Representation Theorem は、外部からの通信を受け付けないという意味で閉じている並行システムを汎用的に表現する方法を提供している。プロセス計算などの他の並行性システムは、2相コミットプロトコルを使ってアクターモデルでモデル化できる[7]。閉システム S は、その初期挙動 S に対して挙動近似関数 progressionS を適用することでよりよい近似を構築でき、S の数学的記述(意味)は次のようになる[8]

DenoteS ≡ ⊔i∈ω progressionSi(⊥S)

このようにすると、S は全てのとりうる挙動で数学的に特徴付けられることができる。

論理

様々な時相論理[9]が並行システムの理解を助けるために使われる。特に線形時相論理計算木論理は、並行システムの各時点の状態を確認するのに使用可能である。Action Computational Tree Logic や Hennesy-Miller Logic、レスリー・ランポートTemporal Logic of Actionsなどは、「アクション(状態変化)」の並びを確認することができる。これら論理の主な利用法は、並行システムの仕様を記述することである[1]

実際の並行処理

並行プログラミングは、並行システムを実装するのに使われるプログラミング言語とアルゴリズムから構成される。一般に並行プログラミングは並列プログラミングよりも範囲が広いとされ、様々な形態の通信および相互作用に関係する。一方、一般の並列システムは予め決められた整った構成の通信パターンを備えている。並行プログラミングの基本目標には「正当性」、「性能」、「堅牢性」が含まれる。オペレーティングシステムデータベース管理システムのような並行システムは、障害からの自動復旧など半永久的に動作することが求められ、不意な停止をしないことが期待されている(並行性制御参照)。一部の並行システムは透過的並行性を持つよう実装されている。その場合、並行動作する計算主体群は共有リソースを使用するものの、プログラマからはその実装は隠されている。

並行システムは共有リソースを使うため、共有リソースへのアクセスを制御するための一種の調停を行うもの(通常、ハードウェア)を実装する必要がある。調停者を使用することで並行計算における不確定性英語版が生じるおそれがあり、正当性と性能が求められる実装では重要な意味を持つ。例えば調停によって無制限の非決定性英語版が導入されると、モデル検査においてモデルが無限個の状態を持つことになり、問題が生じる。

並行プログラミングモデルによっては、コプロセスやコルーチンも含んでいる。そういったモデルでは、スレッドが自発的にタイムスライスをシステムまたは他のプロセスに対して譲る。

脚注

  1. ^ a b Cleaveland, Rance; Scott Smolka (December, 1996). “Strategic Directions in Concurrency Research”. ACM Computing Surveys 28 (4): 607. doi:10.1145/242223.242252. https://doi.org/10.1145/242223.242252. 
  2. ^ Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (August 2010). Parallel Programming with Microsoft .NET. Microsoft Press. ISBN 978-0-7356-5159-3. http://msdn.microsoft.com/en-us/library/ff963542.aspx 
  3. ^ Filman, Robert; Daniel Friedman (1984). Coordinated Computing - Tools and Techniques for Distributed Software. McGraw-Hill. ISBN 0-07-022439-0. http://home.comcast.net/~refilman/text/dpl/dpl.html 
  4. ^ Keller, Jörg; Christoph Keßler, Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons 
  5. ^ Lee, Edward; Alberto Sangiovanni-Vincentelli (December, 1998). “A Framework for Comparing Models of Computation”. IEEE Transactions on CAD 17 (12): 1217–1229. doi:10.1109/43.736561. 
  6. ^ Mogens Nielsen; Vladimiro Sassone and Glynn Winskel (1993). “Relationships Between Models of Concurrency”. REX School/Symposium. http://eprints.soton.ac.uk/261948/1/REX.pdf 
  7. ^ Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
  8. ^ William Clinger (June 1981). Foundations of Actor Semantics. Mathematics Doctoral Dissertation. MIT. https://hdl.handle.net/1721.1/6935. 
  9. ^ Roscoe, Colin (2001). Modal and Temporal Properties of Processes. Springer. ISBN 0-387-98717-7 

参考文献

  • Lynch, Nancy A. (1996). Distributed Algorithms. Morgan Kauffman. ISBN 1-55860-348-4 
  • Tanenbaum, Andrew S.; Van Steen, Maarten (2002). Distributed Systems: Principles and Paradigms. Prentice Hall. ISBN 0-13-088893-1 
  • Kurki-Suonio, Reino (2005). A Practical Theory of Reactive Systems. Springer. ISBN 3-540-23342-3 
  • Garg, Vijay K. (2002). Elements of Distributed Computing. Wiley-IEEE Press. ISBN 0-471-03600-5 
  • Magee, Jeff; Kramer, Jeff (2006). Concurrency: State Models and Java Programming. Wiley. ISBN 0-470-09355-2 

関連項目

外部リンク


並行性

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/08 04:44 UTC 版)

フローチャート」の記事における「並行性」の解説

二重の水平な線で表現され、上に複数流れ線(矢印)が入り、下から複数流れ線(矢印)が出る形で表現される。これによって複数同時並行的に行われる制御フローを表す。入ってくるフロー全て二重線に到達すると、出て行くフロー全て同時に開始される入力フロー1つ場合を「フォーク」、出力フロー1つ場合を「ジョイン」と呼ぶ。

※この「並行性」の解説は、「フローチャート」の解説の一部です。
「並行性」を含む「フローチャート」の記事については、「フローチャート」の概要を参照ください。

ウィキペディア小見出し辞書の「並行性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「並行性」の関連用語

並行性のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



並行性のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの並行性 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのフローチャート (改訂履歴)、Crystal (プログラミング言語) (改訂履歴)、ラムダ計算 (改訂履歴)、分散コンピューティング (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS