Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CAS
Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CAS
复制标题
时间最优、空间高效的单扫描仪快照
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Nikolaos D. Kallimanis
中科院分区：
文献类型：
--
作者：
P. Fatourou;Nikolaos D. Kallimanis
快照是基本的共享对象，它提供共享内存块的一致视图。快照对象由m个存储单元的数组组成，并允许进程执行SCANS以在任何快照单元中写入新值，并返回所有m个单元的一致视图。一个有趣的（较弱的）快照形式与几个应用程序是一个单一的扫描器快照，它只允许一个进程，称为扫描器，执行SCANS（扫描器仍然可以并发执行）。
我们提出了第一个时间最优的，单扫描器快照实现从读写寄存器的异步系统的n个进程。我们的第一个算法是非常简单的，时间复杂度为O（1）更新和O（m）扫描，这是最佳的。但是，在没有垃圾收集器的系统中，它使用的寄存器数量与执行的SCANS数量成比例。我们的第二个实现采用了一个有趣的回收技术，以减少空间的复杂度O（mn）有界大小的寄存器仍然实现最佳的时间复杂度为两个操作。这些算法简单实用，在时间和空间复杂度上都优于以往的算法。对于提供更强原语的系统，如比较和交换（CAS），我们提供了一个多扫描器快照实现，它使用m+1个CAS寄存器和m个读写寄存器，UPDATE的时间复杂度为O（1），SCAN的时间复杂度为O（m）。
Snapshots are fundamental shared objects which provide consistent views of blocks of shared memory. A snapshot object consists of an array of m memory cells and allows processes to execute UPDATES to write new values in any of the snapshot cells, and SCANS to return consistent views of all m cells. An interesting (weaker) form of snapshot with several applications is a single-scanner snapshot which allows to only one process, called scanner, to execute SCANS (UPDATES can still be executed concurrently).
We present the first time-optimal, single-scanner snapshot implementations from read-write registers for an asynchronous system of n processes. Our first algorithmis very simple and has time complexity O(1) for UPDATE and O(m) for SCAN, which is optimal. However, in systems with no garbage collector, the number of registers it uses is proportional to the number of executed SCANS. Our second implementation employs an interesting recycling technique to reduce the space complexity to O(mn) bounded-size registers still achieving optimal time complexities for both operations. These algorithms are simple and practical, and improve upon all previous algorithms in terms of time and space complexity. For systems that provide stronger primitives, like Compare-And-Swap (CAS), we provide a multi-scanner snapshot implementation that uses m+1 CAS registers and m read-write registers, and has time complexity O(1)for UPDATE and O(m) for SCAN.