ダイナミックロックフリーメモリアロケータ

Question

ロックフリーのプログレス保証を満たすアルゴリズムまたはデータ構造の難点の1つは、ダイナミックメモリ割り当てです。mallocまたはnewのようなものは、ポータブルな方法でロックフリーであることが保証されていません。しかし、mallocまたはnewの多くのロックフリー実装が存在し、ロックフリーアルゴリズム/データ構造を実装するために使用できるさまざまなロックフリーメモリアロケータもあります。

しかし、私はまだあなたは、特に、いくつかの事前に割り当てられたスタティック・メモリ・プールにデータ構造やアルゴリズムを制限しない限り、これは実際には完全に、ロックフリー進捗保証を満たすことができる方法を理解していません。しかし、の動的メモリ割り当てであるが必要な場合は、ロングランでロックフリーのメモリアロケータが本当にロックフリーになることはありません。問題は、ロックフリーのmallocまたはnewがどれほど驚異的であっても、最終的にメモリが不足している可能性があります。その時点で、オペレーティングシステムにより多くのメモリを要求する必要があります。つまり、最終的にはbrk()またはmmap()またはそのような低レベルの同等物に電話して、実際にはより多くのメモリにアクセスする必要があります。また、これらの低レベル呼び出しのどれかがロックフリーの方法で実装されているという保証はありません。

メモリ保護を提供しないMS-DOSなどの古代OSを使用していないか、完全にロックフリーのオペレーティングシステムを作成しない限り、実用的ではない2つのシナリオおそらくどのような動的メモリアロケータが本当にロックフリーであるのでしょうか？

Answer 1

基本的なOSアロケータは、複数のプロセスやあらゆる種類の面白いものを処理しなければならないため、ロックフリーではない可能性が高いです。

いくつかのケースでは、しかし、「空きメモリの割り当てをロック」「そうめったにそれは本当に問題ではないことを統計的にロック」「決してロック」が、を意味しません。これは、最も厳しいリアルタイムシステム以外は何も問題ありません。あなたがあなたのロックに高い競争力を持っていない場合、ロックまたはロックは本当に重要ではありません - ロックフリーの目的は本当にロック自体のオーバーヘッドではなく、ボトルネックシステム内のすべてのスレッドまたはプロセスが有用な何かを行うためにこの1つの場所を通過しなければならない場合、それは待ち行列で待たなければなりません[本当の待ち行列でもないかもしれません。または現在の発信者の後に誰が次に出てくるかを決定する他のメカニズム]。

この解決するために、いくつかの異なるオプションがあります：

• はあなたが有限のサイズでメモリプールを持っている場合は、ソフトウェアが開始されているとき、あなたは、一度にすべてのそのメモリ用のOSを頼むことができます。また、メモリがOSからチャンクアウトされた後は、ロックフリーのプールとして使用できます。明らかな欠点は、どのくらいのメモリを割り当てることができるかに限界があることです。次に、割り当てを停止するか（アプリケーションを一斉に失敗させるか、その特定の操作を失敗させる）のいずれかです。

  もちろん、LinuxやWindowsのようなシステムでは、ロックフリーのシナリオでは、割り当てられたメモリへの即時アクセスを意味するとは保証されません。実際の物理メモリをバックアップし、実際にメモリが実際に使用されると、物理メモリページが割り当てられます。これには、スワップに他のページをページアウトするためのロックと、たとえばディスクI/Oの両方が含まれます。

• ロックを争うかもしれない単一システムコールの時間が「あまりにも大きい」ような厳密なリアルタイムシステムでは、ソリューションはもちろん、ロックフリーの専用OSを使用することはもちろんですアロケータは、OSの中に（あるいは、許容される既知のリアルタイム動作を持っている少なくとも1つ - それは多くてもXマイクロ秒[Xは1.0未満である可能性があります]）をロックします。リアルタイムシステムには、古い割り当てをリサイクルするためのメモリプールと固定サイズのバケットが用意されています（ロックされない方法で実行できます）。バケットはリンクリストであるため、アトミック比較& [再試行の可能性があるので、技術的にはロックフリーですが、競合状況ではゼロ待機時間ではありません。

• 「スレッドごとのプール」を使用することもできます。これは、スレッド間でデータを渡すと少し複雑になることがありますが、 "再利用のために解放されたメモリは別のスレッドで終了する可能性があります"（どちらが当然のことであるかは、他の多くのスレッドからの情報を収集して解放する1つのスレッド "）