6. 고성능 Lock free 큐 직접구현 및 성능비교

AtomicReference활용해서 락 프리 큐 구현을 설명. 강의 참고!

락 프리가 무조건 좋은게아니다. 하드웨어 환경, 경합하는 스레드가 큰 경우, 다루는 데이터의 크기 등을 모두 고려하고 테스트해봐야된다.

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.ReentrantLock;
 
class SpinLockBool {
    private final AtomicBoolean owner = new AtomicBoolean(false);
 
    public void lock() {
        while (!owner.compareAndSet(false, true))
            LockSupport.parkNanos(1);
    }
 
    public void unlock() {
        owner.set(false);
    }
}
 
class UserData {
    UserData(String name) {
        this.name = name;
    }
    String name;
    UserData next;
}
 
class MyList {
    //protected SpinLockBool lock = new SpinLockBool();
    protected ReentrantLock lock = new ReentrantLock();
    protected UserData headNode = new UserData("DummyHead");
    protected UserData tailPointer = headNode;
 
    public int getCount() {
        int count = 0;
        UserData tmp = headNode.next;
        while(tmp != null) {
            ++count;
            tmp = tmp.next;
        }
        return count;
    }
 
    public void appendNode(String name) {
        UserData newUser = new UserData(name);
        lock.lock();
          tailPointer.next = newUser;
          tailPointer = newUser;
        lock.unlock();
    }
}
 
class LockFreeUser {
    LockFreeUser(String name) {
        this.name = name;
        next = new AtomicReference<LockFreeUser>(null);
    }
    String name;
    AtomicReference<LockFreeUser> next;
}
 
class LockFreeList {
    protected LockFreeUser headNode;
    protected AtomicReference<LockFreeUser> tail;
 
    LockFreeList() {
        headNode = new LockFreeUser("DummyHead");
        tail = new AtomicReference<LockFreeUser>(headNode);
    }
 
    public int getCount() {
        int count = 0;
        LockFreeUser tmp = headNode.next.get();
        while(tmp != null) {
            ++count;
            tmp = tmp.next.get();
        }
        return count;
    }
 
    public void push(String name) {
        LockFreeUser newUser = new LockFreeUser(name);
        while (true) {
            LockFreeUser last = tail.get(); //last = tail;
            LockFreeUser next = last.next.get(); //next = last.next;
            if (last == tail.get()) { //last == tail;
                if (next == null) { //last node?
                    if (last.next.compareAndSet(null, newUser)) {
                        //last.next = newUser;
                        tail.compareAndSet(last, newUser); //tail = newUser;
                        return;
                    }
                }
                else
                    tail.compareAndSet(last, next);
            }
            LockSupport.parkNanos(1);
        }
    }
}
 
class TestThread extends Thread {
    TestThread(MyList db) {
        list = db;
    }
 
    private final MyList list;
    @Override
    public void run() {
        for (int i = 0; i < 1000000; i++)
            list.appendNode("TEST" + i);
    }
}
 
class LockFreeTestThread extends Thread {
    LockFreeTestThread(LockFreeList db) {
        list = db;
    }
 
    private final LockFreeList list;
    @Override
    public void run() {
        for (int i = 0; i < 1000000; i++)
            list.push("TEST" + i);
    }
}
 
public class Main {
    private static void testNormalList() throws InterruptedException {
        MyList db = new MyList();
        int threadCount = 2;
        TestThread[] threads = new TestThread[threadCount];
 
        long beginTime = System.currentTimeMillis();
        for (int i = 0; i < threadCount; i++)
            threads[i] = new TestThread(db);
        for (int i = 0; i < threadCount; i++)
            threads[i].start();
        for (int i = 0; i < threadCount; i++)
            threads[i].join();
        long endTime = System.currentTimeMillis();
 
        System.out.println("Duration: " + (endTime - beginTime) + " ms");
        System.out.println("getCount(): " + db.getCount());
    }
 
    private static void testLockfreeList() throws InterruptedException {
        LockFreeList db = new LockFreeList();
        int threadCount = 2;
        LockFreeTestThread[] threads = new LockFreeTestThread[threadCount];
 
        long beginTime = System.currentTimeMillis();
        for (int i = 0; i < threadCount; i++)
            threads[i] = new LockFreeTestThread(db);
        for (int i = 0; i < threadCount; i++)
            threads[i].start();
        for (int i = 0; i < threadCount; i++)
            threads[i].join();
        long endTime = System.currentTimeMillis();
 
        System.out.println("Duration: " + (endTime - beginTime) + " ms");
        System.out.println("getCount(): " + db.getCount());
    }
 
    public static void main(String[] args) throws InterruptedException {
        testNormalList();
        testLockfreeList();
    }
}