Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Computer Engineering
Non-Blocking Concurrent Operations On Heap, Mahesh Acharya
Non-Blocking Concurrent Operations On Heap, Mahesh Acharya
UNLV Theses, Dissertations, Professional Papers, and Capstones
We present a non-blocking implementation for the concurrent Heap data structure in the asynchronous shared memory system. The system may be a traditional one with a single processor with multiple threads, or it may be the one with multiple processors each possibly with multiple threads. Our implementation supports readMin, deleteMin, and insert operations on the heap. The deleteMin and insert operations are non-blocking operations, whereas the readMin is wait-free. One easy approach of using a heap in multi-threading environment could be by locking the entire heap before performing any operation. This would make the implementation very slow to have any …