NON-BLOCKING ALGORITHM Homepage: https://sites.google.com/site/doc4code/ Email: goldpotion@outlook.com 2011/10/23 멀티쓰레드환경에서알아두면유용한자료구조에대해소개해본다. HARDWARE PRIMITIVE 효율적인구현을위해, Hardware 에서제공하는기능을이용해야한다. 자주쓰는기능에대해 알아보자. COMPARE-AND-SET (CAS) bool CompareAndSet(int *address, int oldvalue, int newvalue) atomic if *address == oldvalue *address = newvalue return true else return false
CompareAndSet(CAS) 함수는 address 주소의값이 oldvalue 인지비교해서같으면 newvalue 로 바꾼다. 소프트웨어 lock 을사용하는것이아니고, 하드웨어에서제공하는기능이므로더빠르고 간편하다. X86 에서는 _InterlockedCompareExchange() 함수를이용해위의기능을구현한다. bool CompareAndSet(int *address, int oldvalue, int newvalue) return _InterlockedCompareExchange(address, newvalue, oldvalue) == oldvalue 어떤하드웨어에서는 4 byte 데이터대신, 8 byte 를처리하는기능을제공하기도한다. bool CompareAndSetWide( int64 *address, int64 oldvalue, int64 newvalue) CompareAndSetWide(CASW) 함수는한번에 8 byte 를비교하고, 바꾸는명령이다. InterlockedCompareExchange64() 함수를이용해구현할수있다. 그밖에, 알아두면유용한함수들이다. int _InterlockedIncrement(int *address) atomic *address = *address + 1 return *address int _InterlockedDecrement(int *address) atomic *address = *address - 1 return *address LOAD-LINKED/STORE-CONDITIONALLY (LL/SC) 다음은 LoadLinked() 와 StoreConditionally() 기능에대해알아보자. // hidden registers of process
int *LinkAddress; int LinkThread = -1; int LoadLinked(int *address) atomic LinkThread = GetCurrentThreadId(); LinkAddress = address return *address bool StoreConditionally(int *address, int value) atomic if (LinkThread == GetCurrentThreadId()) && (LinkAddress == address) LinkThread = -1 *address = value return true return false // *address = value void Store(int *address, int value) atomic if LinkAddress == address LinkThread = -1 *address = value 이기능은 LoadLinked() 와 StoreConditionally() 의두개의짝으로이루어진다. 먼저 LoadLinked() 를호출하여입력주소의값을읽어들인다. 그리고, StoreConditionally() 함수가호출되면, 실행되는중간에데이터가바뀐적이있는지검사한다. 바뀌지않았을때만새로운값으로변경시킨다. 위에서 Store 함수는 Hardware 에서어떤주소의값을바꿀때, 실행되는기능을알려준다. 메모리에값을저장할때마다, 이전에 LoadLinked() 의입력주소와같은지검사해서, 같다면 나중에 StoreConditionally() 가실패하도록만든다.
Alpha, PowerPC, MIPS, ARM 같은하드웨어에서는 LL/SC 기능을지원한다. ldl_l/stl_c, ldq_l/stq_c(alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM) 라는명령에서이 기능을제공한다. ARM 하드웨어에서는 CAS 기능이없다. 이럴경우, 다음처럼 LL/SC 기능을이용해구현할수 있다. bool CompareAndSet(int *address, int old, int new) if LoadLinked(address) == old return StoreConditionally(address, new) else return false 또, 반대로 X86 하드웨어에서는 LL/SC 기능이없다. 이런하드웨어에서는 CASW 기능으로 LL/SC 기능을구현한다. 이것에대해서는 Stack 을구현할때설명하겠다. NON-BLOCKING ALGORITHM 의종류 Non-Blocking 의 Algorithm 은 Thread 가해당작업을최악의경우얼마나빨리진행할수 있느냐에따라서다음세가지로나눈다. Obstruction-free An algorithms is obstruction-free if at any point, a single thread executed in isolation (i.e., with all obstructing threads suspended) for a bounded number of steps will complete its operation. 어떤쓰레드하나만실행되고나머지쓰레드는중지 (suspend) 되었다면, 그쓰레드는자신의 작업을완료하는게보장된다. lock 을사용하지않는알고리즘은모두 obstruction-free 이다. void Function() A1 Lock() A2 Value = 1 A3 Unlock()
쓰레드 1 이 A2 줄에서중지 (suspend) 되었다면, 다른 Thread 2 에서는 Function() 을완료할수없다. 만약, 이상태에서쓰레드 2 만실행되고다른쓰레드들은중지된다면, 쓰레드 2 는무한정 기다려야한다. 그러므로, lock 을사용하는알고리즘은 obstruction-free 가아니다. Lock-free An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of threads makes progress. 모든 lock-free 알고리즘은 obstruction-free 이다. 그런데, 위설명만가지고는 obstruction-free 와 lock-free 가어떻게다른지이해하기어렵다. 나중에설명할테니, 일단넘어가자. Wait-free An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes. 모든 wait-free 알고리즘은 lock-free 이다. Lock-free 알고리즘은일정시간실행되면한개이상작업이완료되는게보장되지만, wait-free 알고리즘은모든쓰레드당하나이상의작업이완료되는게보장된다. 즉, lock-free 은개별쓰레드의진행 (progress) 은보장못하지만전체프로그램의진행은보장되며, wait-free 는개별쓰레드의진행까지보장한다. class Object int m_nref; Object() m_nref = 0 void AddRef()
_InterlockedIncrement(&m_nRef) void Release() if _InterlockedDecrement(&m_nRef) == 0 delete this 흔히, 사용되는 Reference 알고리즘이다. 여기서 AddRef() 와 Release() 함수는 wait-free 이다. 다른 Thread 가어떤상태에있더라도상관없이일정한시간내에해당작업을완료할수있다. LOCK-FREE SINGLE-LINKED-LIST STACK 우선가장많이사용하는 stack 을구현하는방법에대해서알아보자. struct Node value_type value; Node *next; ; Node* Top; void A1 A2 A3 A4 A5 Push(Node *node) loop Node *top = Top; node->next = top if CompareAndSet(&Top, top, node) return Node *Pop() B1 loop B2 B3 Node *top = LoadLinked(&Top); if top == NULL
B4 B5 B6 B7 return NULL Node *next = top->next; if StoreConditionally(&Top, next) return top 간단하니까, 이해하기쉬울것이다. 가능성은낮지만, Node 의 free() 를구현하는방법에따라서 access violation 이발생할가능성이남아있다. 만약쓰레드 1 이 B5 를실행하려는순간에정지되었다고가정하자. 쓰레드 2 에서 Pop() 을실행하고, 그 Node 를 free() 해버리면, 그후쓰레드 1 에서 top->next 를읽어들이는순간에 Access Violation 이발생할가능성이있다. 그러나, 보통의 free() 구현방법은이런문제를발생시키지않는다. ABA PROBLEM ABA Problem 을이해하기위해 CompareAndSet 을이용해서잘못구현된 Stack 알고리즘을살펴 보자. Node *Pop() B1 loop B2 B3 B4 B5 B6 B7 Node *top = Top; if top == NULL return NULL Node *next = top->next; if CompareAndSet(&Top, top, next) return top
그림 1. 원래자료구조가그림 1 과같았다고가정하자. 그리고, 쓰레드 1 이 B5 줄까지실행되고 중단되었다고하자. 그림 2. 이때, Thread2 에서 Pop() 을두번실행했다고하면, 그림 2 처럼된다. 그림 3. 그리고, Thread2 에서 Push(A) 를하면그림 3 처럼된다. 여기서, 원래쓰레드 1 이 B6 줄부터다시 시작된다고하면, next 에는엉뚱한 node B 의주소가들어가있어서자료구조가꼬이게된다. 이것은 Top 의내용이노드 A-> 노드 B-> 노드 C-> 노드 A 로바뀌었는데, 쓰레드 1 에서는중간에 바뀐것을감지할수없어서발생하는에러이다. 이렇게값이 A->B->A 로바뀌어서발생하는 문제를 ABA Problem 이라고부른다. CAS 을사용하면 ABA 문제가발생할가능성이있으므로, 알고리즘에따라 LL/SC 를이용해야 하는경우가많다. 하드웨어에서 LL/SC 를지원하지않는다면, CASW 를이용해구현할수있다. 다음은 CASW 를이용해제대로구현한예이다. #define NODE(v) ((Node *) (int) v) #define COUNT(v) ((int) (v >> 32)) #define MAKE_INT64(a, b) ((unsigned) a + (b << 32)) int64 Top64; void A1 Push(Node *node) loop
A2 A3 A4 A5 Node *top = NODE(Top64); node->next = top if CompareAndSet(&Top64, top, node) return Node *Pop() B1 loop B2 B3 B4 B5 B6 B7 B8 int64 top64 = Top64; Node *top = NODE(top64); int count = COUNT(top64); if top == NULL return NULL if ComapreAndSetWide(&Top64, top64, MAKE_INT64(top->next, count+1)) return top LOCK-FREE SINGLE-LINKED-LIST QUEUE 또, 아주유용하게사용할수있는알고리즘이 FIFO Queue 이다. #define END 0 Node *Head; Node *Tail; 큐는항상하나의더미노드를가지고있다. Head 의값은이더미노드의주소이다. 그리고, Tail 은더미노드또는큐에들어있는노드중의하나를가리킨다. 큐가비어있을때, 더미노드의 next 필드의값은 END 이다. 그리고, Tail 은더미노드를가리킨다. 큐가하나이상의노드를가질때, 더미노드의 next 필드의값은첫번째노드의주소이다. 그리고, Tail 의정상적인값은마지막노드의주소이다. 하지만, 처리도중에더미노드또는큐에들어있는 노드중의하나를가리킬수있다. 각노드의 next 필드는다음노드의주소값이다. 단, 마지막노드의 next 필드는 END 이다. void Initialize()
A1 Head = new Node // make dummy node A2 Head->next = END A3 Tail = Head void B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 Push(value_type value) Node *node = new Node; node->value = value node->next = END loop Node *tail = LoadLinked(&Tail); Node *next = tail->next; if next!= END // Tail is incorrect, try to correct StoreConditionally(&Tail, next) continue if CompareAndSet(&tail->next, END, node) StoreConditionally(&Tail, node) // ok, even if failed, someone else correct Tail pointer return bool Pop(value_type *value) C1 loop C2 Node *head = LoadLinked(&Head); C3 Node *next = head->next; C4 if next == END C5 if StoreConditionally(&Head, head) // head not changed C6 return false // empty C7 continue C8 if head == Tail // Tail is incorrect, try to correct C9 Node *tail = LoadLinked(&Tail); C10 Node *next = tail->next; C11 if next!= END C12 StoreConditionally(&Tail, next) C13 continue
C14 C15 C16 C17 *value = next->value if StoreConditionally(&Head, next) free(head) return true 우선 Push () 의 B10 줄을살펴보자. 여기서, tail->next 의값과 Tail 의값을동시에바꿀수 있다면좋겠지만, 현재하드웨어에서는불가능하다. 그래서, tail->next 의값을먼저바꾸고, Tail 의값은바꾸는데실패하더라도무시한다. Tail 의값을바꾸는데실패하면, 나중에교정한다. 만약, 쓰레드 1 이 B11 줄을실행하기바로전에정지되었다고가정하자. 아직 Tail 의값이제대로 설정되지않은상태이다. Thread 2 가 Push() 을실행하면 Tail 의값을 B8 줄에서교정하게된다. 마찬가지로, Thead2 가 Pop() 를실행할때, C8-C13 줄에서비정상적인 Tail 의값을교정한다. 이 때, Tail 의값을고치지않으면 Head 가전진할때, Tail 은반환 (free) 된노드의주소를가리킬 위험이있다. 그리고, 조심해야할부분이있다.. B10 줄을보면 tail->next 의값이 END 인지검사하는데, tail 은이미 free 되었을수있다. 그러므로, Node 가 free 되더라도 next 멤버변수값이 END 가되지 않도록해야한다. OBSTRUCTION-FREE STACK WITH ARRAY 다음알고리즘은효용성이별로없지만 objection-free 와 lock-free 알고리즘간의차이를 설명하기위해소개하겠다. Buffer 를이용해스택을구현한예이다. #define CASW CompareAndSetWide int64 Buffer[MAX+2]; void Initialize() A1 Buffer[0] = MAKE_INT64(1, 0); A2 for (int i = 1; i <= MAX+1; ++i) A3 Buffer[i] = 0;
int oracle() B1 for (int i = 1; i <= MAX+1; ++ i) B2 if NODE(Buffer[i]) == 0 B3 return i; bool Push(Node *node) C1 assert(node!= 0) C2 loop C3 int k = oracle(); C4 int64 prev = Buffer[k-1]; C5 int64 cur = Buffer[k]; C6 if NODE(prev)!= NULL && NODE(cur) == NULL C7 if k == MAX+1 C8 return false // FULLL C9 if CASW(&Buffer[k-1], prev, MAKE_INT64(NODE(prev), COUNT(prev)+1)) C10 if CASW(&Buffer[k], cur, MAKE_INT64(node, COUNT(cur)+1)) C11 return true Node* Pop() D1 loop D2 int k = oracle(); D3 int64 cur = Buffer[k-1]; D4 int64 next = Buffer[k]; D5 if NODE(cur)!= NULL && NODE(next) == NULL D6 if k == 1 D7 return NULL // EMPTY D8 if CASW(&Buffer[k], next, MAKE_INT64(NODE(next), COUNT(next)+1)) D9 if CASW(&Buffer[k-1], cur, MAKE_INT64(NULL, COUNT(cur)+1)) D10 return NODE(cur)
이알고리즘에서 NODE(Buffer[0]) 의값은항상 0 이아니고, NODE(Buffer[MAX+1]) 의값은항상 0 이다. 그리고, 앞에서부터차례대로 Node 의포인터값을채워나가게된다. 여기서쓰레드 1 이 C9 까지실행된후정지되었다고가정하자. 그다음, 쓰레드 2 가 D8 까지 실행한후정지되었다고가정하자. 그후, 두쓰레드가다시실행되면 C10 과 D9 줄의 if 문은 모두실패하게된다. 이런최악의상황이계속반복되면두쓰레드는무한반복하게된다. 이알고리즘은일정시간안에작업이하나도완료되지않을수있으므로, lock-free 가아니다. 그렇지만, 다른쓰레드들이정지돠고한쓰레드만실행된다면, 그쓰레드의작업이완료될수 있다. 그러므로, obstruction-free 이다.