Computer Engineering Commons^™

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 …