VBR: Version Based Reclamation
| Autor: | Gali Sheffi, Erez Petrank, Maurice Herlihy |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Scheme (programming language)
FOS: Computer and information sciences Hazard pointer Computer science Speculative execution Software and its engineering → Garbage collection computer.software_genre Land reclamation Software and its engineering → Concurrent programming structures Theory of computation → Parallel computing models Software and its engineering → Multithreading concurrency Software and its engineering → Concurrent programming languages computer.programming_language linearizability Database Concurrent data structure Epoch (reference date) Variable bitrate Safe memory reclamation Shared memory Computer Science - Distributed Parallel and Cluster Computing Theory of computation → Concurrent algorithms Distributed Parallel and Cluster Computing (cs.DC) lock-freedom computer |
| Zdroj: | SPAA |
| Popis: | Safe lock-free memory reclamation is a difficult problem. Existing solutions follow three basic methods (or their combinations): epoch based reclamation, hazard pointers, and optimistic reclamation. Epoch-based methods are fast, but do not guarantee lock-freedom. Hazard pointer solutions are lock-free but typically do not provide high performance. Optimistic methods are lock-free and fast, but previous optimistic methods did not go all the way. While reads were executed optimistically, writes were protected by hazard pointers. In this work we present a new reclamation scheme called version based reclamation (VBR), which provides a full optimistic solution to lock-free memory reclamation, obtaining lock-freedom and high efficiency. Speculative execution is known as a fundamental tool for improving performance in various areas of computer science, and indeed evaluation with a lock-free linked-list, hash-table and skip-list shows that VBR outperforms state-of-the-art existing solutions. LIPIcs, Vol. 209, 35th International Symposium on Distributed Computing (DISC 2021), pages 35:1-35:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|