• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International symposium on distributed computing >Fair Synchronization
【24h】

Fair Synchronization

机译：公平同步

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Most published concurrent data structures which avoid locking do not provide any fairness guarantees. That is, they allow processes to access a data structure and complete their operations arbitrarily many times before some other trying process can complete a single operation. Such a behavior can be prevented by enforcing fairness. However, fairness requires waiting or helping. Helping techniques are often complex and memory consuming. Does it mean that for enforcing fairness it is best to use locks? The answer is negative. We show that it is possible to automatically transfer any non-blocking or wait-free data structure into a similar data structure which satisfies a strong fairness requirement, without using locks and with limited waiting. The fairness we require is that no beginning process can complete two operations on a given resource while some other process is kept waiting on the same resource. Our approach allows as many processes as possible to access a shared resource at the same time as long as fairness is preserved. To achieve this goal, we introduce and solve a new synchronization problem, called fair synchronization. Solving the new problem enables us to add fairness to existing implementations of concurrent data structures, and to transform any solution to the mutual exclusion problem into a fair solution.
机译：大多数避免锁定的已发布并发数据结构不提供任何公平性保证。也就是说，它们允许进程访问数据结构并多次任意完成其操作，然后其他尝试进程才能完成单个操作。可以通过强制公平来防止这种行为。但是，公平需要等待或帮助。帮助技术通常很复杂且占用内存。这是否意味着为了加强公平性，最好使用锁？答案是否定的。我们表明，可以自动将任何无阻塞或无需等待的数据结构转换为满足强烈公平性要求的类似数据结构，而无需使用锁和有限的等待时间。我们要求的公平性是，没有任何一个开始进程可以在给定资源上完成两项操作，而其他进程则在等待同一资源。我们的方法允许在保持公平的前提下，尽可能多的进程同时访问共享资源。为了实现此目标，我们引入并解决了一个新的同步问题，称为公平同步。解决新问题使我们能够为并发数据结构的现有实现增加公平性，并将对互斥问题的任何解决方案都转换为公平解决方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号