ロック（コンピュータサイエンス）

コンピュータサイエンスにおいて、ロックまたはミューテックス(相互排他性から) は、複数の実行スレッドによって同時に状態が変更されたりアクセスされたりするのを防ぐ同期プリミティブです。ロックは相互排他同時実行制御ポリシーを実施し、さまざまな方法が考えられるため、さまざまなアプリケーションに対して複数の固有の実装が存在します。

一般的に、ロックはアドバイザリ ロックであり、各スレッドは対応するデータにアクセスする前にロックを取得して協力します。一部のシステムでは強制ロックも実装されており、ロックされたリソースへの不正アクセスを試みると、アクセスを試みたエンティティで 例外が強制されます。

最も単純なタイプのロックはバイナリセマフォです。これは、ロックされたデータへの排他的アクセスを提供します。他のスキームでは、データの読み取りに共有アクセスも提供されます。広く実装されているその他のアクセス モードには、排他、除外意図、アップグレード意図があります。

ロックを分類する別の方法は、ロック戦略によってスレッドの進行が妨げられた場合に何が起こるかによって分類することです。ほとんどのロック設計では、ロックを要求しているスレッドの実行は、ロックされたリソースへのアクセスが許可されるまでブロックされます。スピンロックを使用すると、スレッドはロックが使用可能になるまで単に待機 (「スピン」) します。これは、スレッドが短時間ブロックされる場合は効率的です。オペレーティング システム プロセスの再スケジュールのオーバーヘッドが回避されるからです。ロックが長時間保持される場合、またはロックを保持しているスレッドの進行がロックされたスレッドのプリエンプションに依存する場合は非効率的です。

通常、ロックを効率的に実装するにはハードウェア サポートが必要です。このサポートは、通常、「テスト アンド セット」、「フェッチ アンド アド」、「比較 アンド スワップ」などの 1 つ以上のアトミック命令の形式をとります。これらの命令により、単一のプロセスでロックが解放されているかどうかをテストし、解放されている場合は単一のアトミック操作でロックを取得できます。

ユニプロセッサアーキテクチャには、割り込み不可能な命令シーケンス (特殊な命令または命令プレフィックスを使用して一時的に割り込みを無効にする) を使用するオプションがありますが、この手法はマルチプロセッサ共有メモリ マシンでは機能しません。マルチプロセッサ環境でロックを適切にサポートするには、かなり複雑なハードウェアまたはソフトウェア サポートが必要になり、同期の問題もかなり生じます。

アトミック操作が必要な理由は、複数のタスクが同じロジックを実行する同時実行性のためです。たとえば、次のCコードを考えてみましょう。

if ( lock == 0 ) { // ロックを解除して設定しますlock = myPID ; }    
    
      

上記の例では、複数のタスクが同時にロックをテストする可能性があるため、タスクがロックを持っていることが保証されません。両方のタスクがロックが空いていることを検出するため、両方のタスクがロックを設定しようとしますが、もう一方のタスクもロックを設定していることはわかりません。アトミック ロック操作が利用できない場合は、 DekkerまたはPeterson のアルゴリズムを代替として使用できます。

ロックを不注意に使用すると、デッドロックやライブロックが発生する可能性があります。設計時と実行時の両方で、デッドロックやライブロックを回避または回復するための戦略がいくつか用意されています。(最も一般的な戦略は、ロック取得シーケンスを標準化して、相互に依存するロックの組み合わせが常に明確に定義された「カスケード」順序で取得されるようにすることです。)

一部の言語では、構文的にロックをサポートしています。C #の例を次に示します。

public class Account // これはアカウントのモニターです{ private decimal _balance = 0 ; private object _balanceLock = new object ();   

        
         

    public void Deposit (小数点付きの金額) { // 一度に 1 つのスレッドだけがこのステートメントを実行できます。lock ( _balanceLock ) { _balance += amount ; } }   
    
        
         
        
              
        
    

    public void Withdraw (小数点付き金額) { // 一度に 1 つのスレッドだけがこのステートメントを実行できます。lock ( _balanceLock ) { _balance -= amount ; } } }   
    
        
         
        
              
        
    

lock(this)インスタンスがパブリックにアクセスできる場合、コードによって問題が発生する可能性があります。 ^[1]

Javaと同様に、C#でもMethodImplOptions.Synchronized属性を使用してメソッド全体を同期することができます。^{[2] [3]}

[MethodImpl(MethodImplOptions.Synchronized)] 
public void SomeMethod () { // 何かを行う}  

    

ロックの粒度について説明する前に、ロックに関する 3 つの概念を理解する必要があります。

• ロック オーバーヘッド: ロックに使用するための追加リソース。ロックに割り当てられるメモリ領域、ロックを初期化および破棄するための CPU 時間、ロックの取得または解放にかかる時間など。プログラムが使用するロックが増えるほど、使用に関連するオーバーヘッドも大きくなります。
• ロック競合: これは、あるプロセスまたはスレッドが別のプロセスまたはスレッドによって保持されているロックを取得しようとするたびに発生します。使用可能なロックの粒度が細かいほど、あるプロセス/スレッドが他のプロセス/スレッドによって保持されているロックを要求する可能性は低くなります。(たとえば、テーブル全体ではなく行をロックしたり、行全体ではなくセルをロックしたりします)。
• デッドロック: 少なくとも 2 つのタスクのそれぞれが、他のタスクが保持しているロックを待機している状況。何らかの処理が行われない限り、2 つのタスクは永久に待機することになります。

同期におけるロックの数を選択する場合、ロックのオーバーヘッドの削減とロックの競合の削減の間にはトレードオフがあります。

ロックの重要な特性は、その粒度です。粒度は、ロックが保護するデータの量の尺度です。一般に、粗い粒度 (少数のロックで、それぞれが大きなデータ セグメントを保護する) を選択すると、保護されたデータに1 つのプロセスがアクセスしているときのロック オーバーヘッドは少なくなりますが、複数のプロセスが同時に実行されているときの性能は低下します。これは、ロック競合が増加するためです。ロックが粗いほど、ロックによって無関係なプロセスの進行が停止される可能性が高くなります。逆に、細かい粒度 (多数のロックで、それぞれがかなり少量のデータを保護する) を使用すると、ロック自体のオーバーヘッドは増加しますが、ロック競合は減少します。各プロセスが共通のロック セットから複数のロックを保持しなければならない粒度の細かいロックでは、微妙なロック依存関係が発生する可能性があります。この微妙な依存関係により、プログラマが知らないうちにデッドロックを導入する可能性が高くなります。^[要出典]

たとえば、データベース管理システムでは、ロックは、粒度の降順で、フィールドの一部、フィールド、レコード、データ ページ、またはテーブル全体を保護できます。テーブル ロックの使用などの粗い粒度では、単一のユーザーに対して最高のパフォーマンスが得られる傾向がありますが、レコード ロックなどの細かい粒度では、複数のユーザーに対して最高のパフォーマンスが得られる傾向があります。

データベース ロックは、トランザクションの同期性を保証する手段として使用できます。つまり、トランザクション処理を並行して行う場合 (トランザクションをインターリーブする場合)、2 フェーズ ロックを使用すると、トランザクションの並行実行がトランザクションのシリアル順序と同等になることが保証されます。ただし、データベースのロックの残念な副作用としてデッドロックが発生します。デッドロックは、トランザクション間のロック順序を事前に決定することで防止するか、待機グラフを使用して検出します。デッドロックを回避しながらデータベースの同期性を確保するためのロックの代替手段として、完全に順序付けられたグローバル タイムスタンプの使用があります。

データベース上で複数の同時ユーザーのアクションを管理するメカニズムが採用されています。その目的は、更新の損失やダーティ リードを防ぐことです。ロックには、悲観的ロックと楽観的ロックの 2 種類があります。

• 悲観的ロック: レコードを更新する目的でレコードを読み取るユーザーは、他のユーザーがレコードを操作できないようにレコードに排他ロックをかけます。つまり、ユーザーがロックを解除するまで、他のユーザーはそのレコードを操作できません。欠点は、ユーザーが長時間ロックアウトされる可能性があるため、システム全体の応答が遅くなり、フラストレーションが生じることです。

悲観的ロックを使用する場所: これは主に、データ競合 (データベース システムに対するユーザーの同時要求の度合い) が激しい環境で使用されます。つまり、同時実行の競合が発生した場合に、ロックによるデータ保護のコストがトランザクションのロールバックのコストよりも低くなります。悲観的同時実行は、レコードのプログラム処理のように、ロック時間が短い場合に最適です。悲観的同時実行では、データベースへの永続的な接続が必要であり、レコードが比較的長い期間ロックされる可能性があるため、ユーザーがデータを操作している場合にはスケーラブルなオプションではありません。Web アプリケーション開発での使用には適していません。

• 楽観的ロック: 複数のユーザーが同時にデータベースにアクセスでき、システムは各ユーザーによる初期読み取りのコピーを保持します。ユーザーがレコードを更新する場合、アプリケーションは、最後に読み取られてから別のユーザーがレコードを変更したかどうかを判断します。アプリケーションは、メモリに保持されている初期読み取りをデータベース レコードと比較して、レコードに加えられた変更を検証することでこれを行います。初期読み取りとデータベース レコードの間に矛盾があると同時実行ルールに違反するため、システムは更新要求を無視します。エラー メッセージが生成され、ユーザーは更新プロセスを再度開始するように求められます。必要なロックの量を減らすことでデータベースのパフォーマンスが向上し、データベース サーバーの負荷が軽減されます。ユーザーがロックアウトされないため、更新が制限されるテーブルで効率的に機能します。ただし、更新が失敗する場合があります。欠点は、複数の同時ユーザーからの大量の更新要求により更新が頻繁に失敗することです。これはユーザーにとってストレスになる可能性があります。

楽観的ロックを使用する場所: これは、データの競合が少ない環境、またはデータへの読み取り専用アクセスが必要な環境に適しています。楽観的同時実行は、モバイル アプリケーションや切断されたアプリケーションのニーズに対応するために .NET で広く使用されています^[4]。これらのアプリケーションでは、データ行を長時間ロックすることは不可能です。また、レコード ロックを維持するには、データベース サーバーへの永続的な接続が必要ですが、これは切断されたアプリケーションでは不可能です。

これらの主要なロック タイプには、それぞれ異なるブロッキング動作を伴ういくつかのバリエーションと改良版があります。最初のロックが別のロックをブロックする場合、2 つのロックは非互換 と呼ばれます。それ以外の場合は、ロックは互換です。多くの場合、ロック タイプのブロッキング相互作用は、技術文献でロック互換性テーブルとして提示されます。以下は、一般的な主要なロック タイプの例です。

• ✔は互換性を示します
• X は非互換性を示します。つまり、オブジェクトの最初のタイプのロック (左の列) が、同じオブジェクトで (別のトランザクションによって) 2 番目のタイプのロック (上の行) が取得されるのをブロックする場合です。オブジェクトには通常、それぞれのロックを持つ、トランザクションによって要求された待機中の操作のキューがあります。キュー内の操作に対する最初のブロックされたロックは、既存のブロック ロックがオブジェクトから削除されるとすぐに取得され、その後、それぞれの操作が実行されます。キュー内の操作に対するロックが既存のロックによってブロックされていない場合 (同じオブジェクトに複数の互換性のあるロックが同時に存在する可能性があります)、そのロックはすぐに取得されます。

コメント:一部の出版物では、表の項目は単に「互換性がある」または「互換性がない」、あるいはそれぞれ「はい」または「いいえ」とマークされています。^[5]

ロックベースのリソース保護とスレッド/プロセスの同期には多くの欠点があります。

• 競合: 一部のスレッド/プロセスは、ロック (またはロックのセット全体) が解放されるまで待機する必要があります。ロックを保持しているスレッドの 1 つが停止、停止、ブロック、または無限ループに入ると、ロックを待機している他のスレッドは、コンピューターの電源が入れ直されるまで無期限に待機する可能性があります。
• オーバーヘッド: ロックを使用すると、衝突の可能性が非常に低い場合でも、リソースへのアクセスごとにオーバーヘッドが追加されます。(ただし、このような衝突の可能性があれば、競合状態になります。)
• デバッグ: ロックに関連するバグは時間に依存し、デッドロックなど、非常に微妙で再現が非常に難しい場合があります。
• 不安定性: ロック オーバーヘッドとロック競合の最適なバランスは、問題領域 (アプリケーション) に固有であり、設計、実装、さらには低レベルのシステム アーキテクチャの変更に左右される可能性があります。これらのバランスは、アプリケーションのライフ サイクルを通じて変化する可能性があり、更新 (再バランス) に多大な変更が必要になる場合があります。
• 構成可能性: ロックは、比較的複雑な (オーバーヘッドの) ソフトウェア サポートと、アプリケーション プログラミングによる厳格な規則への完全な準拠によってのみ構成可能です (たとえば、テーブル A から項目 X をアトミックに削除し、テーブル B に X を挿入するために複数の同時ロックを管理するなど)。
• 優先度の逆転: 共通ロックを保持している優先度の低いスレッド/プロセスは、優先度の高いスレッド/プロセスの進行を妨げる可能性があります。優先度の継承を使用すると、優先度の逆転の期間を短縮できます。優先度上限プロトコルは、単一プロセッサ システムで使用して、最悪の場合の優先度の逆転の期間を最小限に抑え、デッドロックを防ぐことができます。
• コンボイ: ロックを保持しているスレッドがタイムスライス割り込みまたはページ フォールトのためにスケジュール解除された場合、他のすべてのスレッドは待機する必要があります。

一部の同時実行制御戦略では、これらの問題の一部またはすべてを回避できます。たとえば、ファネルまたはトークンのシリアル化により、最大の問題であるデッドロックを回避できます。ロックの代替手段としては、ロックフリープログラミング手法やトランザクション メモリなどの非ブロッキング同期方法があります。ただし、このような代替方法では、実際のロック メカニズムをオペレーティング ソフトウェアのより基本的なレベルで実装する必要があることがよくあります。したがって、アプリケーションレベルはロック実装の詳細から解放されるだけで、上記の問題はアプリケーションの下で対処する必要があります。

ほとんどの場合、適切なロックは、CPU がアトミック命令ストリーム同期の方法を提供しているかどうかに依存します (たとえば、パイプラインにアイテムを追加または削除するには、特定のアイテムを追加または削除するために必要なメモリ コンテンツを操作している間、パイプ内の他のアイテムを追加または削除する必要があるすべての同時操作を一時停止する必要があります)。したがって、アプリケーションは、オペレーティング システムにかかる負荷を認識し、不可能な要求の報告を丁寧に認識できると、より堅牢になることがよくあります。^{[引用が必要]}

ロックベースのプログラミングの最大の問題の 1 つは、「ロックは構成されない」ことです。つまり、モジュールを変更するか、少なくともその内部構造を知らずに、小さくて正しいロックベースのモジュールを、同様に正しい大きなプログラムに結合することは困難です。Simon Peyton Jones (ソフトウェア トランザクション メモリの提唱者) は、次のような銀行アプリケーションの例を示しています^{[6] 。複数の同時クライアントが 1 つの口座に預金または引き出しを行える}Accountクラスを設計し、ある口座から別の口座に送金するアルゴリズムを提供します。

問題の最初の部分に対するロックベースの解決策は次のとおりです。

クラスAccount:
    メンバーbalance: Integer
    メンバーmutex: Lock

    メソッドdeposit(n: Integer)
           ミューテックス.ロック()
           バランス ← バランス + n
           ミューテックス.ロック解除()

    メソッドwithdraw(n: Integer)
           預金(−n)

問題の2番目の部分ははるかに複雑です。シーケンシャルプログラムに適した転送ルーチンは次のようになります。

関数transfer(from: アカウント、to: アカウント、amount: 整数)
    from.withdraw(金額)
    to.deposit(金額)

並行プログラムでは、このアルゴリズムは正しくありません。なぜなら、1 つのスレッドが転送の途中にあるときに、別のスレッドが、最初の口座から金額が引き落とされたが、他の口座にはまだ入金されていない状態を観察する可能性があるためです。つまり、お金がシステムから消えてしまいます。この問題を完全に解決するには、どちらかの口座を変更する前に両方の口座にロックをかけるしかありませんが、その場合、デッドロックを防ぐために、ロックを任意のグローバル順序に従って配置する必要があります。

function transfer(from: Account, to: Account, amount: Integer)
     if from < to     // ロックの順序は任意
        .lock() から
        ロック()
    それ以外
        ロック()
        .lock() から
    from.withdraw(金額)
    to.deposit(金額)
    .unlock() から
    ロック解除()

このソリューションは、関係するロックの数が増えると複雑になり、転送関数はすべてのロックについて知る必要があるため、ロックを非表示にすることはできません。

プログラミング言語によって同期のサポートは異なります。

• Adaは、可視の保護されたサブプログラムまたはエントリ^[7]とランデブー^{[8]を持つ保護されたオブジェクトを提供します。}
• ISO/IEC C標準は、 C11以降、標準的な相互排他(ロック)アプリケーション プログラミング インターフェイス(API)を提供しています。現在の ISO/IEC C++標準は、C++11以降、スレッド機能をサポートしています。OpenMP標準は一部のコンパイラでサポートされており、プラグマを使用してクリティカル セクションを指定できます。POSIX pthread API はロック サポートを提供します。^[9] Visual C++ は同期するメソッドの属性を提供しますが、これはWindowsアーキテクチャとVisual C++コンパイラの COM オブジェクトに固有のものです。^[10] C と C++ は、ネイティブ オペレーティング システムのロック機能に簡単にアクセスできます。 synchronize
• C# では、スレッドにキーワードを提供してlock、リソースへの排他的アクセスを保証します。
• Visual Basic (.NET) はSyncLock、C# のキーワードのようなキーワードを提供しますlock。
• Javaはsynchronizedコードブロック、メソッド、またはオブジェクトをロックするためのキーワード^[11]と、並行処理安全なデータ構造を備えたライブラリを提供しています。
• Objective-Cは、コードブロックにロックをかけるキーワード@synchronized^[12]を提供し、また、ロック用のNSLockingプロトコル^[16]とともに、 NSLock、^[13]、 NSRecursiveLock、^[14]、NSConditionLock ^[15]などのクラスも提供しています。
• PHPはファイルベースのロック^[17]と拡張機能Mutex内のクラス^[18]pthreadsを提供します。
• Pythonはモジュールのクラスを使用して低レベルのミューテックスメカニズムを提供します。^[19]Lock threading
• ISO/IEC Fortran標準（ISO/IEC 1539-1:2010）では、Fortran 2008以降、lock_type組み込みモジュールiso_fortran_envとlock/文に派生型が提供されています。^[20]unlock
• Rubyは低レベルのミューテックスオブジェクトを提供し、キーワードは提供しない。^[21]
• RustはMutex<T>^[22]構造体を提供する。^[23]
• x86 アセンブリ言語は、LOCK特定の操作のアトミック性を保証するためにプレフィックスを提供します。
• Haskell は、と呼ばれる可変データ構造を介してロックを実装します。MVarこの構造は、空であるか、通常はリソースへの参照である値を含むことができます。リソースを使用するスレッドは、 の値を「取得」しMVar、空のままにして、使用が終了したら に戻します。空の からリソースを取得しようとすると、MVarリソースが利用可能になるまでスレッドがブロックされます。^{[24]ロックの代替として、}ソフトウェア トランザクション メモリの実装も存在します。^[25]
• Goは標準ライブラリのsyncパッケージで低レベルのMutexオブジェクトを提供しています。 ^{[26]これはコードブロック、}メソッド、またはオブジェクトをロックするために使用できます。

• クリティカルセクション
• 二重チェックのロック
• ファイルロック
• ロックフリーおよび待機フリーのアルゴリズム
• モニター（同期）
• 相互排除
• 読み取り/書き込みロックパターン

• ロックとクリティカルセクションに関するチュートリアル