同期とデータ競合フリー

同期メカニズムは、共有データが安全にアクセスされるように並行スレッドを調整し、データ競合フリーは並行プログラムを予測可能にする特性です。

Definition

同期とは、共有リソースに対する順序付けまたは相互排他を強制するために並行アクティビティを調整することであり、データ競合フリーとは、介入する同期なしに、2つのスレッドが同時に同じメモリ位置にアクセスし、少なくとも一方が書き込みを行うことがないという特性です。

Scope

このトピックでは、共有状態への並行アクセスを正しく行うためのメカニズムと特性について説明します。具体的には、相互排他、ロック、セマフォとモニター、条件変数、ロックフリーおよびウェイトフリーアルゴリズム、トランザクショナルメモリ、happens-before関係、データ競合の検出などが含まれます。また、デッドロック、アトミック性、およびプログラムをデータ競合フリーに保つために必要な規律についても扱います。

Core questions

• 相互排他はどのように達成され、その危険性（デッドロック、飢餓）は何ですか？
• ロックベースの同期とロックフリーの同期を区別するものは何ですか？
• happens-before関係はデータ競合をどのように定義しますか？
• データ競合はどのように自動的に検出できますか？

Key theories

相互排他

Dijkstraの並行制御問題に対する解決策は、相互排他を基本的な同期要件として確立し、クリティカルセクションが同時に実行されないことを保証しました。

トランザクショナルメモリ

HerlihyとMossはトランザクショナルメモリを提案しました。これは、メモリ操作のグループがアトミックに実行され、並行データ構造を構築するためのきめ細かいロックに代わる構成可能な代替手段を提供します。

Happens-beforeと動的競合検出

Lamportのhappens-before関係に基づいて、Eraser検出器は、ロック規律をチェックすることでデータ競合を動的に見つける方法を示し、自動競合検出の例となりました。

Clinical relevance

正しい同期は、信頼性の高い並行および並列ソフトウェアにとって不可欠です。データ競合は、実際には最もとらえどころのないバグの一部を引き起こします。競合検出器、トランザクショナルメモリ、および規律ある同期パターンは、信頼性の高いマルチスレッドシステムを構築するための中心的なツールです。

History

Dijkstraの1965年の相互排他ソリューションとそれに続くセマフォが同期の基礎を築き、その後、HoareとBrinch Hansenのモニターが続きました。Lamportの1978年のhappens-before関係は現代の競合定義の基礎となっており、HerlihyとMossは1993年にトランザクショナルメモリを導入し、Eraser（1997年）などの動的競合検出器やその後のhappens-beforeツールは、並行性のデバッグの標準となりました。

Debates

ロックとロックフリーおよびトランザクショナルアプローチ

設計者は、単純だがデッドロックや構成の悪さに陥りやすい従来のロックベースの同期と、複雑さやオーバーヘッドを犠牲にして構成可能性と進行保証を改善するロックフリーアルゴリズムやトランザクショナルメモリについて議論しています。

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

データ競合とは何ですか？

データ競合は、2つのスレッドが同時に同じメモリ位置にアクセスし、少なくとも1つのアクセスが書き込みであり、かつアクセスが同期によって順序付けられていない場合に発生します。これにより、ほとんどのメモリモデルで未定義または予測不能な動作が生じます。

ロックベースの同期とロックフリーの同期の違いは何ですか？

ロックベースの同期は相互排他を使用するため、一度に1つのスレッドのみがクリティカルセクションに入ります。一方、ロックフリーの同期はアトミック操作を使用して、ロックを保持せずに常に何らかのスレッドが進行することを保証し、デッドロックを回避します。