template<typename T>
class LockFreeStack
{
struct Node
{
Node(const T& value) : data(value)
{
}
T data;
Node* next;
};
public:
/*
이렇게 할 예정
(Push)
node->next에 기존의 node정보를 넣고
head에 새로 생성한 node를 넣을예정
(Pop)
head의 node를 가져오고
head->next를 다시 head로 연결
*/
// 1) 새 노드를 만들고
// 2) 새 노드의 next = head
// 3) head = 새 노드
// [ ][ ][ ][ ][ ][ ][ ]
// [head]
void Push(const T& value)
{
Node* node = new Node(value);
node->next = _head;
// atomic<Node*> _head;
// _head에 새로추가된 node의 주소를 넣고싶다
// 단, _head는 멀티 쓰레드에 의해 위험성이 존재
/*
* compare_exchange_weak의 동작, 아래동작을 atomic하게 처리해준다.
if (_head == node->next)
{
// 정상적이라면 여기에 들어와야함
// 위에서 node->next = _head; 해줬기 때문
_head = node;
return true;
}
else
{
// 다른 쓰레드에 의해 _head가 변경되었다면 여기로 오게된다.
node->next = _head;
return false;
}
*/
// (주의) 많은 쓰레드가 여기에 몰리며, 여기서 경합이 너무 심해서 라이브 락이 발생할 수 있음
while (_head.compare_exchange_weak(node->next, node) == false)
{
//node->next = _head;
}
// 이 사이에 새치기 당하면?
//_head = node;
}
// 1) head 읽기
// 2) head->next 읽기
// 3) head = head->next
// 4) data 추출해서 반환
// 5) 추출한 노드를 삭제
// [ ][ ][ ][ ][ ][ ]
// [head]
bool TryPop(T& value)
{
Node* oldHead = _head;
/*
if (_head == oldHead)
{
_head = oldHead->next;
return true;
}
else
{
oldHead = _head;
return false;
}
*/
while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)
{
//oldHead = _head;
}
if (oldHead == nullptr)
return false;
// Exception X
value = oldHead->data;
// 잠시 삭제 보류
//delete oldHead;
// 지우는게 문제이다. 내가 지우는 순간에 다른 쓰레드에서 쓰고있을 수 있다는게 어려운부분
// 다음강에서 해결한다.
// C#, Java 같이 GC가 있으면 사실 여기서 끝
return true;
}
private:
// [ ][ ][ ][ ][ ][ ]
// [head]
atomic<Node*> _head; // atomic은 초기값이 nullptr(0)임
};