Thursday, February 28, 2013

The problem of not having a Garbage Collector

As mentioned on a previous post, one of the problems of not having a GC in C or C++ is that some algorithms are very tricky to implement. Sure, you can use a Hazard-Pointer-Manager like the one described here, and I even have made one that is Wait-Free (a subject for a future post), but then you're just replacing a nasty problem with a slightly more complex one.
It's always simpler to modify the algorithm (when possible) to get rid of the issue, than to try to implement your own GC or HPM, and that's what we did.

My pain comes from the algorithm described in this post not being applicable to C or C++, mostly because the helper array can be removed at any time by a new thread or one that is about to terminate.
Any call to addState() or to removeState() will create a new helper array for readersArray and release the memory for the old one.

Andreia had the idea of replacing the array with a ConcurrentLinkedQueue (or a similar lock-free implementation in C++) which would make it safer. Still, in C++ we will  need to call exclusiveLock()/exclusiveUnlock() in removeState() to prevent other threads from having a pointer to the current state of the reader that we are trying to delete. The reason is that, we know that the only place in the code where a pointer for that entry may be kept by another thread is in exclusiveLock(), so in order to prevent that from happening, we call exclusiveLock() from the thread that is about to terminate, which will set the writerOwner to tid_self and prevent the other thread from taking the pointer. By the time the other thread acquires the lock on writerOwner, the ConcurrentLinkedQueue will no longer have that entry and, therefore,  there is no way for it to grab that pointer:

    public void exclusiveLock() {
        final long tid_self = Thread.currentThread().getId();
        // Try to acquire the lock in write-mode
        while (!writerOwner.compareAndSet(SRWL_INVALID_TID, tid_self))

        // Transform the ConcurrentLinkedQueue into an array to make it 
        // easier to scan
        AtomicInteger[] readersArray =  
            readersCount.toArray(new AtomicInteger[readersCount.size()]);
        int[] waitForReaders = new int[readersArray.length];
        int numWaitReaders = 0;       
        // Write-Lock was acquired, now wait for any running Readers to finish
        for (int i = 0; i < readersArray.length; i++) {
            if (readersArray[i].get() > 0)
                waitForReaders[numWaitReaders++] = i;           
        for (int i = 0; i < numWaitReaders; i++) {
            while (readersArray[waitForReaders[i]].get() > 0)

Truly devious!

No comments:

Post a Comment