论文标题
有效的部分快照实现
Efficient Partial Snapshot Implementations
论文作者
论文摘要
在这项工作中，我们提出了$λ$ -SCANNER快照，即快照对象的变体，该对象在任何给定时间都支持任何固定量的$ 0 <λ\ leq n $ scan $ scan $操作。每当$λ$等于系统中的进程$ n $时，$λ$ -Scanner对象会实现多扫描器对象，而如果$λ$等于$ 1 $，则$λ$ -Scanner对象实现单个扫描器对象。我们介绍$λ-SNAP $快照对象，这是一个无需等待的$λ$ -Scanner快照实现，该实现的步骤复杂度为$ O（λ）$，用于$ update $ uperations和$ o O（λm）$ for $ scan $ operations。 $λ-Snap $的空间复杂性为$ O（λm）$。 $λ-SNAP $提供了步骤/空间复杂性与系统可以在任何给定时间点上活跃的$ SCAN $操作数量之间的权衡。我们实施提供的低空间复杂性使它们在实际系统应用中更具吸引力。此外，我们提供了$λ-SNAP $实现的略微修改版本，该版本称为部分$λ-SNAP $，该版本能够支持动态的部分扫描操作。在这样的对象中，过程可以执行称为$ partial \ _scan $的修改后的$ scan $ operations，该操作可以获取快照对象的一部分，以避免读取整个组件。 在这项工作中，我们首先提供了$λ-Snap $的简单单扫描器版本，称为$ 1-SNAP $。我们仅出于演示目的提供$ 1-SNAP $，因为它比$λ-Snap $简单。 $ Update $ in $ 1-SNAP $具有$ O（1）$的步骤复杂性，而$ scan $的步骤复杂性为$ O（m）$。此实施使用$ O（m）$ $ $ cas $寄存器。
In this work, we propose the $λ$-scanner snapshot, a variation of the snapshot object, which supports any fixed amount of $0 < λ\leq n$ different $SCAN$ operations being active at any given time. Whenever $λ$ is equal to the number of processes $n$ in the system, the $λ$-scanner object implements a multi-scanner object, while in case that $λ$ is equal to $1$, the $λ$-scanner object implements a single-scanner object. We present the $λ-Snap$ snapshot object, a wait-free $λ$-scanner snapshot implementation that has a step complexity of $O(λ)$ for $UPDATE$ operations and $O(λm)$ for $SCAN$ operations. The space complexity of $λ-Snap$ is $O(λm)$. $λ-Snap$ provides a trade-off between the step/space complexity and the maximum number of $SCAN$ operations that the system can afford to be active on any given point in time. The low space complexity that our implementations provide makes them more appealing in real system applications. Moreover, we provide a slightly modified version of the $λ-Snap$ implementation, which is called partial $λ-Snap$, that is able to support dynamic partial scan operations. In such an object, processes can execute modified $SCAN$ operations called $PARTIAL\_SCAN$ that could obtain a part of the snapshot object avoiding to read the whole set of components. In this work, we first provide a simple single-scanner version of $λ-Snap$, which is called $1-Snap$. We provide $1-Snap$ just for presentation purposes, since it is simpler than $λ-Snap$. The $UPDATE$ in $1-Snap$ has a step complexity of $O(1)$, while the $SCAN$ has a step complexity of $O(m)$. This implementation uses $O(m)$ $CAS$ registers.
