Lock Free 알고리즘에 대하여

LockFree 알고리즘이란?

. MultiThread에서의 동기화 기법(lock 등)을 사용하지 않고 다중 호출에 대하여 최소한 1개의 호출이 완료되는 알고리즘

. Game Server에서는 JobQueue등에서 사용할 수 있다.

. 원리는 자료구조에 대하여 변경을 수행할 때 다른 Thread가 접근한 경우 작업 시도를 취소하는 것이다.

 

LockFree 알고리즘을 사용하는 이유

. 잘못된 MultiThread 사용으로 인한 성능 하락이 없다.

. lock을 사용하지 않고 DeadLock 이슈를 피하기 위해서

. 다른 Thread의 상태와 상관없이 호출이 완료된다.

. non blocking 하면서 원장성을 유지해야 하는 경우

 

LockFree에서 사용하는 자료구조

. Queue : enqueue, dequeue

. Stack : pop, push

. BinaryTree : insert delete, search

 

//걍 대충 적은 코드

push(int x)
{
	var e = new Node(x);
    lock(new object())
    {
    	someTail.next = e;
        somTail = e;
    }
}

push_nonBlock(int x)
{
	var e = new Node(x);
    while(true)
    {
    	var t = someTail;
        var next = t.next;
        if(t != someTail)
        	continue;
        if(next == null)
        {
        	if(Interlocked.Compare(t.next, null, e))
        	{
            	Interlocked.Compare(someTail, t, e);
            	return;
        	}
        }
        else
        {
        	Interlocked.Compare(someTail, t, next);
        }
    }
}

 

 

LockFree 알고리즘의 단점

. 구현하기가 다소 난해하다.

. 코드가 복잡해져서 버그를 발견하기가 어렵다.

 

=> 요즘 장비 성능도 좋아지는데 걍 멀티스레드를 잘 활용하는게 좋은듯?