멀티스레드 프로그래밍에서 여러 스레드가 한 변수의 값을 동시에 변경하고자 하는 상태를 경쟁상태(Race Condition)라고 한다. 이때, 값을 읽고 새 값을 대입하는 과정을 원자적(atomic)으로 진행하지 못하면 충돌이 발생한다. 이를 해결하는 방법은 여러가지가 있다. 여기 C++과 C#으로 각각 구현한 코드를 알아보자.
C/C++
아래의 코드는 C/C++에서 Lock-free로 단일 연결 리스트(Linked List)를 구현한 예제의 일부다.
#include <iostream>
#include <Windows.h>
#include <thread>
#include <time.h>
using namespace std;
#define NodeAddress unsigned long long
#define NodeAddressMask 0x000FFFFFFFFFFFFF
#define NodeTagMask 0xFFF0000000000000
class Node
{
private:
int value;
Node *next;
public:
Node(int value)
{
this->value = value;
this->next = NULL;
}
int GetValue()
{
return this->value;
}
Node *GetNext()
{
return this->next;
}
void SetNext(Node *next)
{
this->next = next;
}
static Node *GetTagged(Node *node)
{
return (Node *)(((NodeAddress)rand() << 52) | (NodeAddress)node);
}
static Node *GetUntagged(Node *node)
{
return (Node *)((NodeAddress)node & NodeAddressMask);
}
};
class LinkedList
{
private:
Node *head;
public:
LinkedList()
{
this->head = NULL;
}
void Push(Node *node)
{
if (node == NULL) return;
while (true)
{
Node *head = this->head;
Node *tagged = Node::GetTagged(node);
node->SetNext(head);
if (InterlockedCompareExchangePointer((PVOID *)&this->head, tagged, head) == head)
break;
}
}
Node *Pop()
{
while (true)
{
Node *head = this->head;
if (head == NULL) return NULL;
Node *untagged = Node::GetUntagged(head);
Node *next = untagged->GetNext();
if (InterlockedCompareExchangePointer((PVOID *)&this->head, next, head) == head)
return untagged;
}
}
};이 코드는 객체의 주소(64bit) 중 일부가 이용되지 않는 점을 이용하여 ABA Problem을 해결한다. 각 Node는 Push 될 때 임의의 tag를 부여받고, tag가 합쳐진 Node 주소를 List에 저장한다. 해당 Node에 실제로 접근할 때는 tag 부분을 0으로 설정하고 접근하면 된다. 64bit 주소에서 사용되지 않는 부분은 CPU에 따라 다른데, MSB 12bit, LSB 2bit 정도는 거의 모든 환경에서 사용되지 않는 것으로 보인다. 위 코드에서는 MSB 12bit에 임의의 tag를 삽입했다.
C#
아래의 코드는 C#에서 Mutex와 Interlocked를 사용하여 이중 연결 리스트(Doubly Linked List)를 구현한 예제의 일부다.
abstract class LinkedListType
{
public Node next = null;
public Node prev = null;
}
class Node : LinkedListType
{
private int value;
public Node(int value)
{
this.value = value;
}
}
class LinkedList : LinkedListType
{
public Mutex mutex = new Mutex();
public int prohibit = 0;
/*
Get the length of this list
*/
public int GetLengthByNext()
{
int n = 0;
Node next = this.next;
while (next != null)
{
next = next.next;
n++;
}
return n;
}
public int GetLengthByPrev()
{
int n = 0;
Node prev = this.prev;
while (prev != null)
{
prev = prev.prev;
n++;
}
return n;
}
/*
Add a node
*/
public void AddFirstAtomic(int i)
{
Node node = new Node(i);
Node first;
while (true)
{
if (Interlocked.CompareExchange(ref next, node, null) == null)
{
prev = node;
break;
}
if (next != null)
{
first = next;
if (Interlocked.CompareExchange(ref first.prev, node, null) == null)
{
node.next = first;
next = node;
break;
}
}
}
}
public void AddFirstNonAtomic(int i)
{
Node node = new Node(i);
if (next == null)
prev = node;
else
{
node.next = next;
next.prev = node;
}
next = node;
}
public void AddLastAtomic(int i)
{
Node node = new Node(i);
Node last;
while (true)
{
if (Interlocked.CompareExchange(ref prev, node, null) == null)
{
next = node;
break;
}
if (prev != null)
{
last = prev;
if (Interlocked.CompareExchange(ref last.next, node, null) == null)
{
node.prev = last;
prev = node;
break;
}
}
}
}
public void AddLastNonAtomic(int i)
{
Node node = new Node(i);
if (prev == null)
next = node;
else
{
node.prev = prev;
prev.next = node;
}
prev = node;
}
/*
Delete a node
*/
public Node DeleteFirstAtomic()
{
Node node = null;
while (next != null)
{
node = next;
if (Interlocked.CompareExchange(ref next, next.next, node) == node)
{
if (next != null)
next.prev = null;
else
prev = null;
node.next = null;
break;
}
}
return node;
}
public Node DeleteFirstNonAtomic()
{
Node node = next;
if (node != null)
{
next = next.next;
if (next != null)
next.prev = null;
else
prev = null;
node.next = null;
}
return node;
}
public Node DeleteLastAtomic()
{
Node node = null;
while (prev != null)
{
node = prev;
if (Interlocked.CompareExchange(ref prev, prev.prev, node) == node)
{
if (prev != null)
prev.next = null;
else
next = null;
node.prev = null;
break;
}
}
return node;
}
public Node DeleteLastNonAtomic()
{
Node node = prev;
if (node != null)
{
prev = prev.prev;
if (prev != null)
prev.next = null;
else
next = null;
node.prev = null;
}
return node;
}
/*
Add and delete a node
*/
public void AddFirstPreventABA(int i)
{
while (true)
{
if (Interlocked.CompareExchange(ref prohibit, 1, 0) == 0)
{
AddFirstNonAtomic(i);
prohibit = 0;
break;
}
}
}
public void AddLastPreventABA(int i)
{
while (true)
{
if (Interlocked.CompareExchange(ref prohibit, 1, 0) == 0)
{
AddLastNonAtomic(i);
prohibit = 0;
break;
}
}
}
public Node DeleteFirstPreventABA()
{
Node node;
while (true)
{
if (Interlocked.CompareExchange(ref prohibit, 1, 0) == 0)
{
node = DeleteFirstNonAtomic();
prohibit = 0;
break;
}
}
return node;
}
public Node DeleteLastPreventABA()
{
Node node;
while (true)
{
if (Interlocked.CompareExchange(ref prohibit, 1, 0) == 0)
{
node = DeleteLastNonAtomic();
prohibit = 0;
break;
}
}
return node;
}
}여러 스레드가 동시에 노드를 추가(또는 삭제)할 때, NonAtomic 함수를 사용하면 일부 노드가 소실된다. Atomic 함수들은 이를 방지하기 위해 노드의 추가(또는 삭제)를 원자적으로 수행한다. 하지만 노드의 추가와 삭제가 여러 스레드에서 동시에 실행될 때 ABA Problem이 발생한다. 코드의 마지막 부분에 ABA Problem을 피하기 위한 4개의 함수가 있음을 확인하라. ABA Problem을 피하는 방법은 매우 다양한데, C#에서 Class Instance의 주소를 직접 조작하려면 unsafe를 이용하고 C/C++처럼 주소의 사용되지 않는 비트를 활용하면 된다.