8

我正在尝试基于Lehman 和 Yao 在本文中建议的数据结构（B链接树）和算法来实现数据库索引。在第 2 页中，作者指出：

磁盘被划分为固定大小的部分（物理页；在本文中，这些对应于树的节点）。这些是唯一可以被进程读取或写入的单元。[强调我的]（...）

(...) 允许进程锁定和解锁磁盘页面。该锁赋予该进程对该页面的独占修改权限；此外，进程必须锁定页面才能修改该页面。(...)锁 不会阻止其他进程读取锁定的页面。[强调我的]

我不完全确定我的解释是否正确（我不习惯阅读学术论文），但我认为可以从强调的句子中得出结论，作者的意思是读取和写入页面的操作被假定为“原子” ，从某种意义上说，如果进程 A 已经开始读取（相应地写入）页面，则另一个进程 B 可能不会开始写入（相应地读取）同一页面，直到 A 完成其读取（相应地写入）操作. 多个进程同时读取同一个页面当然是合法的条件，因为多个进程同时在完全不同的页面上执行任意操作（页面 P 上的进程 A，页面 Q 上的进程 B，页面 R 上的进程 C 等）也是如此。 ）。

  1. 我的解释正确吗？

  2. 我可以假设 POSIX'read()和write()系统调用在上述意义上是“原子的”吗？我是否可以依靠这些具有一些内部逻辑的系统调用来根据文件描述符的位置和要读取或写入的块的指定大小来确定是否应该暂时阻止特定read()或调用？write()

  3. 如果上述问题的答案是“否”，我应该如何推出自己的锁定机制？

4

2 回答 2

6

我不相信你引用的文字暗示了任何类似的东西。它甚至没有提到read()或write()或POSIX。事实上，read()并write()不能指望它是原子的。POSIX 唯一说的是，write()如果写入的大小小于PIPE_BUF字节，则它必须是原子的，即使这仅适用于管道。

我没有阅读您引用的论文部分的上下文，但听起来您引用的段落是在说明必须放在实现上的约束，以便算法正常工作。换句话说，它表明该算法的实现需要锁定。

如何进行锁定取决于您（实施者）。如果我们正在处理一个常规文件和多个独立进程，您可以尝试fcntl(F_SETLKW)-style 锁定。如果您的数据结构在内存中，并且您正在处理同一进程中的多个线程，那么其他可能是合适的。

于 2013-01-19T20:04:12.367 回答
6

答案：

  1. 根据操作系统、文件系统以及您打开文件时使用的标志，并发读取到写入可能会看到写入损坏。下面是标志、操作系统和文件系统的快速摘要。

  2. 您可以使用 POSIX 上的 fcntl() 或 Windows 上的 LockFile() 来锁定文件中的字节范围，然后再访问它们。

没有 O_DIRECT/FILE_FLAG_NO_BUFFERING：

带有 NTFS 的 Microsoft Windows 10：更新原子性 = 1 字节

带有 ext4 的 Linux 4.2.6：更新原子性 = 1 字节

带有 ZFS 的 FreeBSD 10.2：更新原子性 = 至少 1Mb，可能是无限的 (*)

O_DIRECT/FILE_FLAG_NO_BUFFERING：

带有 NTFS 的 Microsoft Windows 10：更新原子性 = 仅在页面对齐时最多 4096 字节，否则如果 FILE_FLAG_WRITE_THROUGH 关闭，则为 512 字节，否则为 64 字节。请注意，这种原子性可能是 PCIe DMA 的一个特性，而不是在 (*) 中设计的。

带有 ext4 的 Linux 4.2.6：更新原子性 = 至少 1Mb，可能是无限的 (*)。请注意，带有 ext4 的早期 Linux 肯定不会超过 4096 字节，XFS 肯定曾经有自定义锁定，但看起来最近的 Linux 终于修复了这个问题。

带有 ZFS 的 FreeBSD 10.2：更新原子性 = 至少 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 回答