8

この論文でリーマンとヤオが提案したデータ構造（Bリンクツリー）とアルゴリズムに基づいてデータベースインデックスを実装しようとしています。2ページで、著者は次のように述べています。

ディスクは固定サイズのセクションに分割されています（物理ページ。このペーパーでは、これらはツリーのノードに対応します）。これらは、プロセスによって読み取りまたは書き込みができる唯一のユニットです。[強調鉱山]（...）

（...）プロセスはディスクページをロックおよびロック解除できます。このロックは、そのプロセスにそのページに対する排他的な変更権限を与えます。また、プロセスでページを変更するには、そのページをロックする必要があります。（...）ロック は、他のプロセスがロックされたページを読み取ることを妨げません。[強調鉱山]

私の解釈が正しいかどうかは完全にはわかりませんが（学術論文を読むことに慣れていません）、強調された文章から、著者はページを読み書きする操作が「アトミック」であると想定されていることを意味していると結論付けることができると思います、プロセスAがすでにページの読み取り（または書き込み）を開始している場合、別のプロセスBは、Aが読み取り（または書き込み）操作の実行を完了するまで、同じページの書き込み（または読み取り）を開始できないという意味です。 。もちろん、同じページを同時に読み取る複数のプロセスは、排他的に異なるページで任意の操作を同時に実行する複数のプロセス（PページのプロセスA、QページのプロセスB、RページのプロセスCなど）と同様に、正当な条件です。 ）。

  1. 私の解釈は正しいですか？

  2. POSIXread()とwrite()システムコールが上記の意味で「アトミック」であると想定できますか？ファイル記述子の位置と読み取りまたは書き込みされるチャンクの指定されたサイズに基づいて、特定の呼び出しread()または呼び出しを一時的にブロックする必要があるかどうかを判断するために、内部ロジックを持つこれらのシステムコールに依存できますか？write()

  3. 上記の質問に対する答えが「いいえ」の場合、自分のロック機構をどのように回転させる必要がありますか？

4

2 に答える 2

6

あなたが引用しているテキストがそのようなものを暗示しているとは思わない。read()またはwrite()POSIXについても言及していません。実際、アトミックであるread()とwrite()信頼することはできません。POSIXが言う唯一のことwrite()は、書き込みのサイズがバイト未満の場合はアトミックでなければならずPIPE_BUF、それでもパイプにのみ適用されるということです。

あなたが引用した論文の一部の文脈を読んでいませんでしたが、あなたが引用した箇所は、アルゴリズムが正しく機能するために実装に課さなければならない制約を述べているようです。つまり、このアルゴリズムの実装にはロックが必要であると述べています。

そのロックをどのように行うかは、あなた（実装者）次第です。fcntl(F_SETLKW)通常のファイルと複数の独立したプロセスを扱っている場合は、スタイルロックを試してみてください。データ構造がメモリ内にあり、同じプロセスで複数のスレッドを処理している場合は、別の方法が適切な場合があります。

于 2013-01-19T20:04:12.367 に答える
6

回答：

  1. OS、ファイリングシステム、およびファイルを開いたときのフラグによっては、読み取りと書き込みが同時に行われると、書き込みが破損する場合があります。フラグ、OS、ファイリングシステムごとの簡単な要約を以下に示します。

  2. POSIXのfcntl（）またはWindowsのLockFile（）を使用してアクセスする前に、ファイル内のバイト範囲をロックできます。

O_DIRECT / FILE_FLAG_NO_BUFFERINGなし：

NTFSを搭載したMicrosoftWindows10：更新アトミック性=1バイト

Linux 4.2.6 with ext4：更新アトミック性=1バイト

FreeBSD 10.2とZFS：更新アトミック性=少なくとも1Mb、おそらく無限（*）

O_DIRECT / FILE_FLAG_NO_BUFFERING：

NTFSを使用するMicrosoftWindows10：更新アトミック性=ページ整列の場合のみ最大4096バイト、それ以外の場合はFILE_FLAG_WRITE_THROUGHがオフの場合は512バイト、それ以外の場合は64バイト。このアトミック性は、（*）で設計されたものではなく、おそらくPCIeDMAの機能であることに注意してください。

Linux 4.2.6とext4：更新アトミック性=少なくとも1Mb、おそらく無限（*）。ext4を備えた以前のLinuxは間違いなく4096バイトを超えていなかったことに注意してください。XFSは確かにカスタムロックを使用していましたが、最近のLinuxがついにこれを修正したようです。

FreeBSD 10.2とZFS：更新アトミック性=少なくとも1Mb、おそらく無限（*）

生の経験的テスト結果はhttps://github.com/BoostGSoC13/boost.afio/blob/master/fs_probe/fs_probe_results.yamlで確認できます。結果は、すべてのプラットフォームで非同期ファイルi/oを使用して作成されたプログラムによって生成されました。引き裂かれたオフセットは512バイトの倍数でのみテストするため、512バイトのセクターの部分的な更新が読み取り-変更-書き込みサイクル中に破損するかどうかはわかりません。

于 2016-02-07T17:26:08.083 に答える