一尘不染

比较并交换兼容POSIX的文件系统对象

algorithm

符合POSIX的操作系统可以对文件系统对象(文件和文件夹)进行原子操作。这是大概这些原子操作的列表:

  • 重命名或移动文件或文件夹
  • 创建硬链接
  • 创建符号链接
  • 创建文件夹
  • 创建并打开一个空文件

是否可以基于这些操作构建比较和交换算法来处理文件?

假设我们有几个进程正在对单个文件执行并发读/写。文件的特点是修订。假设修订版本已添加到文件名中,并且该文件有一个符号链接,进程可以使用它来读取它。进程不能(由于某些原因)与互斥锁,信号灯等同步,但是它们能够创建辅助文件和文件夹。他们是否能够对文件执行基于修订的“比较并交换”修改(创建新文件,创建并重命名符号链接),这意味着如果多个进程要同时进行修改,那么一个将成功,而其余的将失败并显示一些错误代码?

该算法必须能够抵抗在算法的任何步骤突然终止的任何过程。


阅读 234

收藏
2020-07-28

共1个答案

一尘不染

好家伙。

假设每个进程都可以访问唯一的标识符,以避免破坏对称性的问题。这是一次达成共识对象的免等待实现。

  1. 创建具有唯一名称的目录。
  2. 在该目录中创建一个文件,该文件的名称是创建过程的输入。
  3. 将目录重命名为共识对象的名称。除非这是第一个这样的重命名,否则它将失败。
  4. 列出我们试图重命名自己的目录。内部文件的名称是共识决定。

现在,可以在分布式计算中使用标准结果,以免等待的方式模拟任意对象。玩得开心垃圾收集=
P

2020-07-28