• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Distributed Computing >Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks
【24h】

Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks

机译：无形的读写器锁不如中转互斥锁锁

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

摘要

When a process attempts to acquire a mutex lock, it may be forced to wait if another process currently holds the lock. In certain applications, such as real-time operating systems and databases, indefinite waiting can cause a process to miss an important deadline [19]. Hence, there has been research on designing abortable mutual exclusion locks, and fairly efficient algorithms of O(logn) RMR complexity have been discovered [11,14] (n denotes the number of processes for which the algorithm is designed). The abort feature is just as important for a reader-writer lock as it is for a mutual exclusion lock, but to the best of our knowledge there are currently no abortable reader-writer locks that are starvation-free. We show the surprising result that any abortable, starvation-free mutual exclusion algorithm of RMR complexity t(n) can be transformed into an abortable, starvation-free reader-writer exclusion algorithm of RMR complexity O(t(n)). Thus, we obtain the first abortable, starvation-free reader-writer exclusion algorithm of O(log n) RMR complexity. Our results apply to the Cache-Coherent (CC) model of multiprocessors.
机译：当一个进程试图获取一个互斥锁，它可能会被迫等待，如果另一个进程当前持有的锁。在某些应用中，如实时操作系统和数据库，无限制地等待可导致进程错过重要的期限[19]。因此，出现了设计上可中止的互斥锁研究，和方面是相当有效的算法O（logn）时间复杂RMR已发现[11,14]（n表示用于该算法被设计工序数）。异常终止特性是一样的读写锁，因为它是一个互斥锁很重要，但据我们所知，目前还没有中止的读写锁是饥饿免费。我们展示了令人惊奇的结果的RMR复杂的t（n）的任何中止的，无饥饿互斥算法可以转化为一个可中止，无饥饿读写器排除RMR复杂度为O（T（N））的算法。因此，我们获得第一个可中止，无饥饿读写器排除的O（log n）的复杂性RMR算法。我们的研究结果应用到多处理器的高速缓存一致性（CC）模式。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号