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 practical application.The above inefficiency could be reduced by using the fine-grained locking mechanism as shown by Herlihy and Shavit. But, this would still be a blocking implementation, where some threads may be waiting forever for some other threads holding the locks that might have crashed or failed.Israeli and Rappoport gave a non-blocking implementation which supports deleteMin and insert operations using some primitives which they claim could be built using transactional memory. Moreover, their implementation has a limitation on the range of values a node in the heap can have. We propose a different implementation which supports all three operations using a primitive, called Double-Compare-And-Set(DCAS). DCAS is a synchronization operation supported in hardware by Motorola 68K family of processors. It was also going to be supported by Sunu27s canceled Rock processor. DCAS takes two memory locations as input, and writes new values to them only if they match input expected values. Our algorithm has no limitation on the range of numbers a node can have.
展开▼
