ロック(コンピュータサイエンス)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスではロックまたはミューテックス相互排除から)は同期プリミティブです。つまり、実行スレッドが多い場合にリソースへのアクセスを制限するメカニズムですロックは、相互排除の同時実行制御ポリシーを適用するように設計されており、さまざまな方法で、さまざまなアプリケーションに複数の固有の実装が存在します。

タイプ

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

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

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

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

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

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

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

上記の例では、複数のタスクが同時にロックをテストできるため、タスクにロックがあることを保証するものではありません。両方のタスクがロックが解放されていることを検出するため、両方のタスクは、他のタスクもロックを設定していることを知らずに、ロックを設定しようとします。アトミックロック操作が利用できない場合は、デッカーまたはピーターソンのアルゴリズムが代わりになる可能性があります。

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

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

public  classAccount  //これはアカウントの モニターです{ privatedecimal_balance = 0 ; プライベートオブジェクト_balanceLock = new object ();

        
         

    public  void  Deposit decimal  amount 
    { 
        //一度に1つのスレッドのみがこのステートメントを実行できます。
        ロック _balanceLock 
        { 
            _balance  += 金額; 
        } 
    }

    public  void  Withdraw decimal  amount 
    { 
        //一度に1つのスレッドのみがこのステートメントを実行できます。
        ロック _balanceLock 
        { 
            _balance-  = 金額; 
        } 
    } 
}

lock(this)インスタンスにパブリックにアクセスできる場合、コードは問題を引き起こす可能性があります。[1]

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

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

粒度

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

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

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

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

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

データベースロック

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

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

  • ペシミスティックロック:レコードを更新する目的でレコードを読み取るユーザーは、他のユーザーがレコードを操作できないように、レコードに排他ロックを設定します。これは、ユーザーがロックを解除するまで、他の誰もそのレコードを操作できないことを意味します。欠点は、ユーザーが非常に長い間ロックアウトされる可能性があるため、システム全体の応答が遅くなり、フラストレーションが発生することです。
悲観的ロックを使用する場所:これは主に、データの競合(ユーザーがデータベースシステムに一度に要求する度合い)が激しい環境で使用されます。同時実行の競合が発生した場合に、ロックを介してデータを保護するコストがトランザクションをロールバックするコストよりも少ない場合。悲観的な同時実行は、レコードのプログラムによる処理のように、ロック時間が短い場合に最適に実装されます。悲観的な同時実行にはデータベースへの永続的な接続が必要であり、ユーザーがデータを操作しているときは、レコードが比較的長期間ロックされる可能性があるため、スケーラブルなオプションではありません。Webアプリケーション開発での使用には適していません。
  • 楽観的ロック:これにより、システムが各ユーザーによって作成された初期読み取りのコピーを保持しながら、複数の同時ユーザーがデータベースにアクセスできるようになります。ユーザーがレコードを更新する場合、アプリケーションは、別のユーザーが最後に読み取られてからレコードを変更したかどうかを判断します。アプリケーションは、メモリに保持されている初期読み取りをデータベースレコードと比較して、レコードに加えられた変更を確認することでこれを行います。初期読み取りとデータベースレコードの間に不一致があると、同時実行ルールに違反するため、システムは更新要求を無視します。エラーメッセージが生成され、ユーザーは更新プロセスを再開するように求められます。必要なロックの量を減らし、データベースサーバーの負荷を減らすことで、データベースのパフォーマンスを向上させます。ユーザーがロックアウトされていないため、限られた更新が必要なテーブルで効率的に機能します。ただし、一部の更新は失敗する可能性があります。欠点は、複数の同時ユーザーからの大量の更新要求による継続的な更新の失敗です。これは、ユーザーを苛立たせる可能性があります。
楽観的ロックを使用する場所:これは、データの競合が少ない環境、またはデータへの読み取り専用アクセスが必要な環境に適しています。楽観的同時実行制御は、モバイルおよび切断されたアプリケーションのニーズに対応するために.NETで広く使用されており、[4]データ行を長期間ロックすることは不可能です。また、レコードロックを維持するには、データベースサーバーへの永続的な接続が必要です。これは、切断されたアプリケーションでは不可能です。

短所

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

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

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

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

構成可能性の欠如

ロックベースのプログラミングの最大の問題の1つは、「ロックが構成されない」ことです。モジュールを変更するか、少なくともその内部について知らずに、小さくて正しいロックベースのモジュールを同じように正しい大きなプログラムに組み合わせるのは困難です。サイモンペイトンジョーンズ(ソフトウェアトランザクショナルメモリの提唱者)は、銀行アプリケーションの次の例を示しています。[5]複数の同時クライアントがアカウントにお金を預けたり引き出したりできる クラスアカウントを設計します。あるアカウントから別のアカウントに送金するアルゴリズムを提供します。問題の最初の部分に対するロックベースの解決策は次のとおりです。

クラスアカウント:
    メンバーバランス:整数
    メンバーミューテックス:ロック

    メソッドdeposit(n:整数)
           mutex.lock()
           バランス←バランス+n
           mutex.unlock()

    メソッドwithdraw(n:整数)
           デポジット(-n)

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

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

並行プログラムでは、このアルゴリズムは正しくありません。これは、一方のスレッドが転送の途中で、もう一方のスレッドが最初のアカウントから金額が引き出されたが、もう一方のアカウントにはまだ入金されていない状態を観察する可能性があるためです。つまり、システムからお金が失われています。この問題は、2つのアカウントのいずれかを変更する前に両方のアカウントでロックを取得することによってのみ完全に修正できますが、デッドロックを防ぐために、任意のグローバルな順序に従ってロックを取得する必要があります。

function transfer(from:Account、to:Account、amount:integer)
     if from<to     //ロックの任意の順序
        from.lock()
        閉める()
    そうしないと
        閉める()
        from.lock()
    from.withdraw(amount)
    to.deposit(amount)
    from.unlock()
    to.unlock()

より多くのロックが含まれる場合、このソリューションはより複雑になり、伝達関数はすべてのロックについて知る必要があるため、それらを非表示にすることはできません。

言語サポート

プログラミング言語は、同期のサポートが異なります。

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

も参照してください

参照

  1. ^ 「ロックステートメント(C#リファレンス)」
  2. ^ 「ThreadPoolPriority、およびMethodImplAttribute」MSDN。p。?? 2011年11月22日取得
  3. ^ 「Java開発者の観点からのC#」2013-01-02にオリジナルからアーカイブされました2011年11月22日取得
  4. ^ 「データ層コンポーネントの設計と層を介したデータの受け渡し」Microsoft2002年8月。2008年5月8日のオリジナルからアーカイブ2008年5月30日取得
  5. ^ ペイトン・ジョーンズ、サイモン(2007)。「美しい並行性」(PDF)ウィルソンでは、グレッグ。オラム、アンディ(編)。ビューティフルコード:一流のプログラマーが彼らの考え方を説明しますオライリー。
  6. ^ ISO / IEC 8652:2007。「保護されたユニットと保護されたオブジェクト」Ada2005リファレンスマニュアル2010年2月27日取得保護されたオブジェクトは、保護されたサブプログラムまたは保護されたエントリである、表示された保護された操作の呼び出しを通じて、共有データへの調整されたアクセスを提供します。
  7. ^ ISO / IEC 8652:2007。「タスクと同期の例」Ada2005リファレンスマニュアル2010年2月27日取得
  8. ^ マーシャル、デイブ(1999年3月)。「相互排除ロック」2008年5月30日取得
  9. ^ 「同期」msdn.microsoft.com 2008年5月30日取得
  10. ^ 「同期」サンマイクロシステムズ2008年5月30日取得
  11. ^ 「Appleスレッドリファレンス」アップル株式会社 2009年10月17日取得
  12. ^ 「NSLockリファレンス」アップル株式会社 2009年10月17日取得
  13. ^ 「NSRecursiveLockリファレンス」アップル株式会社 2009年10月17日取得
  14. ^ 「NSConditionLockリファレンス」アップル株式会社 2009年10月17日取得
  15. ^ 「NSLockingプロトコルリファレンス」アップル株式会社 2009年10月17日取得
  16. ^ 「群れ」
  17. ^ 「Mutexクラス」
  18. ^ Lundh、Fredrik(2007年7月)。「Pythonのスレッド同期メカニズム」2020-11-01にオリジナルからアーカイブされました2008年5月30日取得
  19. ^ ジョンリード(2010)。「次のFortran標準のCo-Array」(PDF)2020年2月17日取得
  20. ^ 「Rubyのプログラミング:スレッドとプロセス」2001 2008年5月30日取得
  21. ^ "std :: sync::Mutex-Rust"doc.rust-lang.org 2020年11月3日取得
  22. ^ 「共有状態の並行性-Rustプログラミング言語」doc.rust-lang.org 2020年11月3日取得
  23. ^ マーロウ、サイモン(2013年8月)。「基本的な並行性:スレッドとMVar」。Haskellでの並列および並行プログラミングオライリーメディアISBN 9781449335946
  24. ^ マーロウ、サイモン(2013年8月)。「ソフトウェアトランザクショナルメモリ」。Haskellでの並列および並行プログラミングオライリーメディアISBN 9781449335946
  25. ^ "同期パッケージ-同期-pkg.go.dev"pkg.go.dev 2021-11-23を取得

外部リンク