NBR: Neutralization Based Reclamation
| Autor: | Ajay Singh, Ali Mashtizadeh, Trevor Brown |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
020203 distributed computing Record locking Computer Science - Programming Languages Computer science Hazard pointer 020207 software engineering 02 engineering and technology Linked list Parallel computing Data structure computer.software_genre Tree (data structure) Handshaking Computer Science - Distributed Parallel and Cluster Computing Binary search tree Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Compiler Distributed Parallel and Cluster Computing (cs.DC) computer Programming Languages (cs.PL) |
| Zdroj: | PPoPP |
| Popis: | Safe memory reclamation (SMR) algorithms suffer from a trade-off between bounding unreclaimed memory and the speed of reclamation. Hazard pointer (HP) based algorithms bound unreclaimed memory at all times, but tend to be slower than other approaches. Epoch based reclamation (EBR) algorithms are faster, but do not bound memory reclamation. Other algorithms follow hybrid approaches, requiring special compiler or hardware support, changes to record layouts, and/or extensive code changes. Not all SMR algorithms can be used to reclaim memory for all data structures. We propose a new neutralization based reclamation (NBR) algorithm that is faster than the best known EBR algorithms and achieves bounded unreclaimed memory. It is non-blocking when used with a non-blocking operating system (OS) kernel, and only requires atomic read, write and CAS. NBR is straightforward to use with many different data structures, and in most cases, require similar reasoning and programmer effort to two-phased locking. NBR is implemented using OS signals and a lightweight handshaking mechanism between participating threads to determine when it is safe to reclaim a record. Experiments on a lock-based binary search tree and a lazy linked list show that NBR significantly outperforms many state of the art reclamation algorithms. In the tree NBR is faster than next best algorithm, DEBRA by upto 38% and HP by upto 17%. And, in the list NBR is 15% and 243% faster than DEBRA and HP, respectively. Accepted in PPoPP2021 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|