比较并交换符合POSIX的文件系统对象 [英] Compare-and-Swap over POSIX-compliant filesystem objects

问题描述

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

There are several operations which POSIX-compliant operating systems can do atomically with filesystem objects (files and folders). Here is a list of such presumably atomic operations:

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

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

Is it possible to build Compare-and-Swap algorithm for manipulating a file based on these operations?

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

Let’s suppose we have several processes which are performing concurrent read/write on a single file. A file is characterized by its revision. Let’s say the revision is added to file name, and there is a symlink to the file which can be used by the processes to read it. The processes cannot (for some reasons) synchronize with mutexes, semaphores and so on, but they are able to create auxiliary files and folders. Are they able to perform revision-based Compare-and-Swap modifications of the file (create a new file, create and rename symlink), in the meaning that if several processes are going to modify it simultaneously, one will success and the rest will fail with some error code?

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

The algorithm has to be resistant to sudden termination of any processes at any step of algorithm.

推荐答案

哦，男孩.

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

Let's assume that each process has access to a unique identifier, to avoid problems breaking symmetry. Here's a wait-free implementation of a one-shot consensus object.

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

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

Now it's possible to simulate an arbitrary object in a wait-free manner, using standard results in distributed computing. Have fun garbage collecting =P

这篇关于比较并交换符合POSIX的文件系统对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！