LockFree結(jié)構(gòu)開發(fā)注意事項

重寫內(nèi)存分配器，系統(tǒng)上用的內(nèi)存分配器很不方便，為了加入引用計數(shù)功能而犧牲了簡單性，而且為了線程安全用了一些鎖。這次做到了所有內(nèi)存分配和釋放都是Lock Free的。因為內(nèi)存塊之間是單鏈表，所以實現(xiàn)Lock Free比較簡單。難的地方是管理空閑資源是用的一個數(shù)組，這時要使用DCAS及類似的方法（k word compare and k-th swap）。我的電腦不支持CAS操作，所以無法判斷。在遠程服務器上，100個線程同時分配1000~100000不等個4字節(jié)大小的內(nèi)存，內(nèi)存池從40字節(jié)起增長，無鎖結(jié)構(gòu)用時15秒左右，有鎖結(jié)構(gòu)用時9秒左右。用10個線程同時分配900000~1000000不等個4字節(jié)大小的內(nèi)存，內(nèi)存池從40字節(jié)起增長，無鎖結(jié)構(gòu)用時14秒左右，有鎖結(jié)構(gòu)用時14秒左右。用5個線程同時分配1800000~2000000不等個4字節(jié)大小的內(nèi)存，內(nèi)存池從40字節(jié)起增長，無鎖結(jié)構(gòu)用時8秒左右，有鎖結(jié)構(gòu)用時13秒左右。
     測試顯示，無鎖結(jié)構(gòu)在線程數(shù)接近內(nèi)核實際數(shù)量的時候表現(xiàn)才優(yōu)于有鎖結(jié)構(gòu)。而在大量線程工作時候效果不佳。因為內(nèi)存分配使用的是數(shù)組結(jié)構(gòu)而不是單鏈表結(jié)構(gòu)，理論上，每次操作都和整個數(shù)組相關(guān)，因此會造成數(shù)個線程的原子操作都在等待一個數(shù)組的完成，產(chǎn)生大量垃圾代碼，影響了執(zhí)行效率。而在線程數(shù)量較少的情況下，鎖的開銷會比垃圾代碼執(zhí)行的開銷大。
    下面是DCAS利用CAS進行模擬的一個方法：
    bool cas(volatile void** x, void* new_x, void* old_x);
    bool dcas(volatile void** x, void* new_x, void* old_x, volatile void** y, void* new_y, void* old_y)
    {
    if (old_x == DCAS_BUSY_VAL)
    return false;
    if (!cas(x, DCAS_BUSY_VAL, old_x))
    return false;
    if (!cas(y, new_y, old_y))
    {
    x = old_x;
    return false;
    }
    x = new_x;
    return true;
    }
    基本模擬思路是在對y變量進行更新之前，用一個DCAS_BUSY_VAL的變量將x變量鎖定，然后就可以安全更新y變量，再安全更新x變量。其他的k-compare-and-k-swap都可以用這個思路實現(xiàn)。