我正在尝试基于Lehman和Yao在this paper中建议的数据结构(Blink树)和算法来实现数据库索引。 。在第 2 页中,作者指出:
The disk is partitioned in sections of fixed size (physical pages; in this paper, these correspond to the nodes of the tree). These are the only units that can be read or written by a process. [emphasis mine] (...)
(...) a process is allowed to lock and unlock a disk page. This lock gives that process exclusive modification rights to that page; also, a process must have a page locked in order to modify that page. (...) Locks do not prevent other processes from reading the locked page. [emphasis mine]
我不完全确定我的解释是否正确(我不习惯阅读学术论文),但我认为从强调的句子可以得出结论,作者的意思是读取和写入页面的操作被假定为“原子”,意思是,如果进程 A 已经开始读取(或写入)一页,则另一个进程 B 可能不会开始写入(或读取)同一页,直到 A 完成读取(或写入)该页。写)操作。当然,多个进程同时读取同一页是一个合法的条件,因为多个进程同时在完全不同的页上执行任意操作(进程 A 在页 P 上、进程 B 在页 Q 上、进程 C 在页 R 上等)。 )。
我的解释正确吗?
我可以假设 POSIX 的
read()
和write()
系统调用是上述意义上的“原子”吗?我可以依靠这些具有一些内部逻辑的系统调用来确定是否应根据文件描述符的位置暂时阻止特定的read()
或write()
调用以及指定要读取或写入的 block 的大小?如果上述问题的答案是“否”,我应该如何推出自己的锁定机制?
最佳答案
我不认为您引用的文字暗示任何此类内容。它甚至没有提到 read()
或 write()
或 POSIX。事实上,read()
和 write()
不能被认为是原子的。 POSIX 唯一说的是,如果写入的大小小于 PIPE_BUF
字节,则 write()
必须是原子的,即使这仅适用于管道。
我没有阅读您引用的论文部分的上下文,但听起来您引用的段落正在说明必须对实现施加的约束才能使算法正常工作。换句话说,它表明该算法的实现需要锁定。
如何进行锁定取决于您(实现者)。如果我们正在处理常规文件和多个独立进程,您可以尝试 fcntl(F_SETLKW) 式锁定。如果您的数据结构位于内存中,并且您正在同一进程中处理多个线程,则其他方法可能更合适。
关于concurrency - POSIX 的 read() 和 write() 系统调用是原子的吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14417806/