LockFree - Stack (1)

경우의 수는 이것보다 훨씬 많을 수 있지만 몇개만 추려보았고

크래쉬기 나지 않고 Lock free를 시도 하려는 중간 과정이라 보면 되겠다

 

스택이기 때문에 끝에서 추가되고 삭제 된다는것과

다른 스레드에 의해서 현재 동작하고있는것이 우선순위가 뒤로 밀리고 다시 원래 스레드로 돌아온다 할지라도

스택의 자료구조상 가장 위에 있는 부분에서 추가 또는 삭제가 된다는 부분을 생각하며 보면된다

 

 

일반 Stack 코드를 보면 다음과 같은 형태일 것이다 아직 pop은 없음

template<typename T>
class LockFreeStack
{
	struct Node 
	{
		Node(const T& value) : data(value) {}
		T data;
		Node* next;
	};

public :

	//node 추가는 head 바로 다음에 새로운 노드가 추가 되는 방식이다
	void push(const T& value)
	{
		Node* node = new Node(value);
		node->next = _head;
		_head = node;
	}


private :

	//head 가 다음 노드를 가르키는 방식
	atomic<Node*> _head;

};

새 노드 만드는 순서

 

1. 새 노드를 만든다
2. 새 노드의 next = nead
3. head = 새노드

 

//node 추가는 head 바로 다음에 새로운 노드가 추가 되는 방식이다
void push(const T& value)
{
이 라인은 new Node 가 공용의 힙에 생성하고 유일한 메모리에 생성하는 것이고 포인터로 의도적으로 어떤 조작을 하지 않는 이상 해당 주소를 할당 받는건 유니크하다 => thread safe

 

node 는 스택 이라 thread safe 
즉 이 한줄은 thread safe 하다
Node* node = new Node(value);

lock free 로 만든다는 것은 mutex 를 쓰지 않고 동기화 처리를 가능하게 만드는 것인데(단  mutex 를 사용하지 않고)

그냥 구현한 stack 을 스레드로 사용할 경우 이 라인이 문제가 되는데

_head 는 다른 스레드로 push , pop 을 돌릴때 값이 바뀔 수 있는 공유 변수가 되기 때문에 이 부분을 동기화 처리해줘야한다 

 

그런데 명령어가 두줄이기도 하고 __asm 이 어떻게 처리 되는지 확인이 되진 않은 상태이지만

__asm 을 보진 않더라도 동기화가 필요해보인다는걸 알 수있는 부분이다

node->next = _head;

이 사이에서 다른 스레드가 _head 를 바꾼다면? 문제가 생김
_head = node;

}

 

 

 

 

 

 

여기까진 Push 로직 순서대로 싱글 스레드라 가정하고 추가 하면 이렇게 된다 (추가를 몇번 한 것)

 

 

 

 

우선 위 코드에서 tryPop 을 싱글 스레드라 가정하고 코드를 추가하고

bool tryPop(T& value)
	{
		Node* oldHead = _head;

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)			//atomic 으로 한번에 처리가 됨
		{
			// oldHead = _head;
		}
		if (oldHead == nullptr)
		{
			return false;
		}

		value = oldHead->data;

		//그냥 삭제 해버리면 기존에 참조하고 있던 포인터가 오염되어 기존 삭제된 포인터 사용시 크래쉬 발생
		//delete oldHead;	//나중에 해결
		return true;
	}

삭제에 대해 따라가면 아래 그림 처럼 나온다

trypop 을 두번 한 것 = 검은색 화살표 -> 붉은색 화살표 -> 녹색 화살표 순

노드를 실제 delete 하는 부분은 우선 논외로 한다

 

 

 

 

 

 

 

 

Lockfree Stack - "Test code" 1

아직 불안전한 상태 이지만 이걸로 우선 흐름을 살펴봅니다

 

push 와 pop 로직을 lockfree push 로 만든다

 

다음과 같이 push, tryPop 함수가 된다

	void push(const T& value)
	{
		Node* node = new Node(value);		
		node->next = _head;			
		while (_head.compare_exchange_weak(node->next, node) == false)			//atomic 으로 한번에 처리됨
		{
			//node->next = _head; //없어도 push 로직상 맞아 떨어짐
		}
	}
    
    bool tryPop(T& value)
	{
		Node* oldHead = _head;

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)			//atomic 으로 한번에 처리가 됨
		{
			// oldHead = _head;
		}
		if (oldHead == nullptr)
		{
			return false;
		}
		value = oldHead->data;
		return true;
	}

 

 

 

 

경우의 수는 이것보다 훨씬 많을 수 있지만 몇개만 추려보았다

 

경우의 수1

 

주의사항 그림의 왼쪽 push 나 tryPop 또는 pop 글자는 무시하고 보는것이 좋다
(정확하게 쓴 내용은 아님 copy & paste 하다보니 미스가 있을 수 있음)

 

만약! push를 하던 도중 

Node* node = new Node(value);
node->next = _head;

까지만 하고 t2 스레드로 넘어가 pop 을 시도하려는 상황을 보자

아래 그림은 push 두줄 실행한 이후다

 

 

 

그다음 tryPop 쓰레드가 우선순위를 얻어 tryPop 을 모두 다 처리하게 되면 다음와 같을 것이다

아직 head 에 어떤 변화도 가하지 않았음

while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)

tryPop 의 while 문에 compare_exchange_weak 함수의 리턴이 true 를 리턴하기 때문에 빠져나오고 종료됨

여기까지는 이렇게 된다

 

 

그다음 t1 스레드로 되돌아가 다시 push 를 이어서 하면

while (_head.compare_exchange_weak(node->next, node) == false)

compare_exchange_weak 리턴은 false 임으로 다시 한번 push 의 compare...를 시도 하게 되는데 다시 한번 시도하면

while (_head.compare_exchange_weak(node->next, node) == false)

다음 그림 처럼 된다

노란 색 박스는 유효한 노드, 그리고 compare_exchange_weak 은 true 를 리턴하여 종료 되고 push 는 끝난다

 

최초 3개의 노드에서 시작해서 중간에 tryPop 스레드가 먼저 실행되어 당시의 끝 노드가 제거 된다음 다시 push 스레드가 돌아서 노드 하나를 추가되고 끝나게 된다 결과는 3개로 끝난다 생성됐다 제거된 노드 변화 개수를 보면 : 3->4->3

 

 

 

 

경우의 수2 

 

경우의수 1 에서 반대 상황의 경우를 보면

tryPop 먼저 할때 

Node* oldHead = _head; 까지 진행 된 다음

t1 스레드로 전환되서 push 를 하는 상황이 됐다

 

 

이상황에서 push를 전부 진행된다면 다음과 같이 된다

 

Node* node = new Node(value);
node->next = _head;
while (_head.compare_exchange_weak(node->next, node) == false)  while 문도 break 됨

 

여기까지 해서 push 가 완료되고

 

 

다시 tryPop 으로 되돌아 오면..

이 상태로 복귀 되고 

 

TryPop 구문 중..

while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)

여기부터 다시 실행이 되면 파란선 즉 다음과 같게 된다
compare_exchange_weak 리턴은 false 가 되고

 

이렇게 삭제처리가 되지 않고 한번 미뤄지게 된다 아래는 선만 정리

 

 

 

compare_exchange_weak 이 false 를 리턴해서 while 계속 돌아가게 되니 한번더 실행해보면 

TryPop 구문 중..

while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)

head 와 oldHead 가 같음으로 다음과 같이 된다 (녹색)

compare_exchange_weak 은 true 를 리턴함으로 while 루프가 끝나게 된다

 

tryPop을 하다가 중간에 push 가 들어와서 원소가 추가 됐다가 다시 tryPop나머지 구문이 실행되면서 원래도 돌아온다

처음 노드는 4개였고 tryPop 부터 시작해서 push 가 끼어들어 다시 원래의 노드4개가 되었다

최초에 4번째 노드를 삭제 하려 했지만 중간에 push 가 되면서 5번재 노드가 추가 됐고 마지막으로 추가된 5번재 노드가 삭제되는 형태로 스택에서 최상단의 것이 삭제 되는 루틴과 동일하지만 처음 네번째 것을 삭제하려 했던 대상을 삭제하는 형태는 아닐 수 있다 4->5->4

 

 

 

경우의 수3

 

아래 순서는 프로그램 라인이 하나씩 실행 되면서 스레드가 전환될때의 상황을 가정한것이다

Push 부터 시작

compare_exchange_weak 리턴이 false 임으로 한번 더 실행해보면 

 

while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)

이렇게 되고 compare_exchange_weak 은 true 를 리턴해 while 문은 종료 되어 위의 결과 처럼 된다

 

 

처음 시작은 push 로 하고  최초에 3개이던 노드가 push, tryPop 스레드가 왔다갔다 가 push 가 우선순위로 올라와 4개가 됐다가 중간에 tryPop 이 실행이 반복 되면서 원래의 3개로 된것을 알 수 있다 3->4->3

 

 

 

경우의 수4 

 

 

위 PUSH 는 아직 실행 되지 않고 선만 정리 한것 

 

 

_head.compare_exchange_weak 리턴이 false 임으로 한번 더 실행하면

즉 원소를 추가 할때 head 가 추가 되는 노드의 다음 노드를 head 가 가르키게끔 처리를 해야 push 로직에서 노드 추가가 완료 되기 때문에 이런 처리가 있는 것

 

_head.compare_exchange_weak 라 true 를 리턴하면서 끝난다 마지막 유효한 노드는 3개가 된다

 

결과적으로 아래와 같이 된다

trypop 부터 시작해 push 와 번갈아가면서 한번씩 실행하고 tryPop 이 먼저 원소를 제거 하는 while 에 들어가게 된다 다시 push 로 복귀 하면서 마지막 추가된 노드와 head 와의 연결을 해주면서 중간 노드는 (3번재) 노드는 삭제와 비슷한 처리가 된다 그래서 최종 유효한 노드는 3개가 된다 3->4->3

 

여기서도 나머지 노드에 대한 제거 처리는 우선 고려하지 않음

 

 

 

 

4가지 케이스 모두다  push 와 tryPop 을 어떻게 번걸아 갈지 순서는 어떻게 될지

예측하긴 어렵지만 노드의 변화 과정 개수는

n-> n+1 ->n  개의 꼴을 보이는 것을 알 수 있다

n개로 시작해서 n 개로 끝난다

 

stack 의 룰을 따라 가려고 하긴 하지만 중간에 스레드 특성상 중간 노드가 제거 될때도 있고

처음 지우려고 했던 노드가 지워지지 않을 수도 있다

하지만 노드 개수는 n-> n+1 -> n 개의 꼴을 보인다

 

1. 중요한 특징 한가지 어떤 경우던 oldHead 는 마지막에 삭제할 노드를 가리키고 있다는 것
2. 스레드간의 간섭이 심해서 꼭 삭제 하려던 그 당시의 마지막 대상이 삭제 되는게 아니고 다른 스레드에 의해 추가된 마지막것이 삭제 되는 경우도 있다는 것

 

노드가 중간에 삭제가 될 수 있고 삭제 경로에 대해 애매한 부분들이 있기 때문에

노드 삭제에 대해선 shared_ptr 을 고려해 볼 수도 있겠지만

 

이 코드에서 보이듯 shared_ptr 은 lock free 가 아님으로 LockFree - Stack 를 만드는 과정에서

shaed_ptr 을 사용한다면 lock free 가 아닐 것이다..