Lock Based Concurrent Data Structure (1)

지금까지 Multi Threading 환경을 계속 다뤄왔는데, Multi Threading을 다룰 때 중요한 것이

'thread safe' 문제이다. 즉 Library나 System Call 등을 호출 할 때 각 Thread가 경쟁적으로 호출을 하더라도

Race Condition과 같은 문제가 없어야 한다는 뜻이다. 이를 'MT-safe' 라는 용어를 사용한다.

참고로 Multi Thread가 나오면서 많은 라이브러리들이 MT-safe 하도록 수정하는 과정을 거쳐왔다.

 

지금부터 우리가 다뤄 볼 자료 구조들에서 Race Condition 뿐만 아니라

Performance에도 신경을 쓰면서 어떻게 MT-safe 하게 만들 수 있는지 살펴보자.

Concurrent Counters

그동안 counter를 가지고 Race Condition에 대해서 설명을 했다.

여기에 더해서 Scalable(확장성) 한지 여부를 좀 살펴보려고 하는데,

지금부터 말하는 확장성이란 CPU가 여러 개 인 경우, 그에 비례해서 성능이 좋아지는지에 대한 이슈를 말한다.

 

이 코드에서는 Race Condition이 해결이 안된 상태이다.

만약 경쟁적으로 value 값을 바꾸려고 시도 하면 문제가 발생할 수 있다.

따라서 필요한 부분에는 Lock을 걸고 Lock을 풀면서 값을 바꿔야 할 것이다.

그래서 그 Lock을 사용한 코드가 위에 나온 코드라고 볼 수 있다.

그런데 이 경우 새로운 문제점이 있는데, 그것은 Bottle neck(병목 현상)이 걸릴 수 있다는 것이다.

특히 value 값을 바꾸기 위해서 Lock을 걸고 푸는 과정에서 Bottle neck이 생길 수 있다.

 

따라서 이 병목 현상을 피하기 위해서 확장성 있게 counter를 만들어보자.

하나씩 나눠서 보면 처음에는 Lock을 global 하게 하나로 사용을 했었는데,

이제부터는 local lock을 각각 하나씩 갖도록 한다.

global count와 global lock이 존재하고 각 CPU(또는 각 Thread) 마다 local 하게 증가시키는 count가 존재한다.

이러한 counter 구조체는 각 Thread에서 공유하는 상태에 대한 정보이다.

동작 방식은 각 Thread에서 local count를 열심히 증가시키는데, local count는 자기만 사용하기 때문에 경쟁이 없다.

그리고 이 local count가 일정 수준(S or threshold)에 도달하면 global count에 값을 전달을 하는 방식이다.

이 때문에 아주 정교한 counting은 살짝 포기를 했다고 보기도 한다. (전달 전까지 텀이 존재하기 때문)

이 표에서는 5(threshold)가 됐을 때 local count의 한계로 지정하고 global count에 반영을 한다.

즉 local count가 5가 되는 순간, local count는 다시 0이 되고 global count에 +5를 해준다.

그 내용과 관련된 update함수를 보면 threshold에 도달하면 global lock을 걸고

global count에 자신이 쌓아놓은 local count 만큼 증가를 시키고 local count는 다시 0으로 reset 한다.

threshold에 도달하지 않았다면, local lock만 건 상태에서 자신의 count (local count)를 증가 시키는 일만 한다.

따라서 global count를 증가시킬 때 Race Condition이 발생할 여지가 있었고 이를 global lock을 통해서 제거했다.

global count에 접근하는 주기 역시 매번 접근하는 것이 아니라 S(threshold, 예제에서는 5) 만큼의 주기로

접근을 했기 때문에 Bottle neck 현상이 많이 완화가 될 수 있다.

다만 앞에서 말한 것처럼 정교한 방식이라기 보다는 Approximate 한 방식에 가깝다.

 

아래는 이러한 방식을 기반으로한 결과를 실험을 통해 살펴본 그래프이다.

S = 1024, Core: 4

 

이 그래프는 Thread를 1개부터 4개 까지 만들어서 각 Thread 별로 실행할 때 걸리는 시간에 대한 결과이고

Precise 라고 적혀있는 그래프가 처음에 Lock으로 Race Condition 문제만 해결했던

이 코드이고 그 밑에 Approximate라고 적혀있는 것이 마지막으로 살펴본 병목 현상을 해결한 코드이다.

성능을 보면 둘의 차이가 상당한 것을 볼 수 있다.

특히 Precise의 경우 Single Thread로 돌릴 때 보다 Thread를 4개로 돌리면 시간이 줄어야하는데

오히려 늘어난 것을 볼 수 있다.

늘어난 이유는 물론 Bottle neck 때문이다.

반면에 Approximate Counter는 병목 현상을 해결하여 굉장히 좋은 성능을 보이고 있다.

 

그러면 S 값은 얼마로 정하는 것이 바람직 할까?

 

S 값이 클 수록 global count에 덜 접근을 할 것이고, 자주 접근할 수록 Bottle neck 때문에 시간은 오래걸릴 것이다.

또한 S 값이 크면 정교함은 떨어질 것이고, 이로 인해 중간 값들의 사이에서 차이가 많이 날 수 있다.

하지만 S 값이 커질 수록 확실히 성능은 좋아지는 것을 알 수 있다.

 

여기까지 Race Condition을 제거하면서 Bottle neck도 제거하여 코어를 투입할 수록

점점 빨라지는 (최소한 느려지지는 않는) 방식에 대해서 살펴보았다.

 

Concurrent Linked Lists

Linked List는 공유 자료구조인데, 각 Thread에서 Linked List에 접근을 해서 연산을 할 때

포인터 값을 읽어다가 판단을 하거나 값을 수정 할 수 있도록 하는 방식이다.

초기 상태는 Linked List 특성과 같이 head가 NULL이다.

또한 여러 개의 Key가 있을 때는 이들이 Link로 연결이 되어있다.

여러 Thread에서 접근하는 자료구조이기 때문에 Linked List에서 작업을 하기 위해선 Lock이 필요하다.

 

insert 할 때 부터 살펴보면 new를 malloc을 통해서 Linked List와 같은 타입으로 Heap 공간으로부터 가져온다.

이 가져온 new가 NULL이라면 malloc에서 에러가 발생한 것이기 때문에 error handling을 한다.

제대로 할당을 받았다면 새로운 new 라는 node에 key 값을 넣고 new의 next는 들어온 L의 head를 가리키도록 한다.

그리고 나서 L의 head로 new를 연결시킨다.

 

그런데 여기서 짚고 넘어가야할 점은 malloc이 현재 코드상 Critical Section 안에 들어가 있는데

malloc은 시간이 굉장히 오래 걸리는 일이다.

하지만 다행인 점은 malloc이 라이브러리로 제공이 되며 MT-safe 하다는 것이다.

따라서 Lock을 걸지 않아도 자유롭게 사용할 수 있기 때문에 굳이 critical section 안에 들어갈 이유가 없다.

또한 우리는 Critical Section을 줄이는 노력도 해야하기 때문에 이 부분이 개선사항이 될 수 있다.

게다가 Lookup 함수는 unlock을 특정 조건에서 푸는 일도 있기 때문에 코드가 좀 복잡하다. 

 

이러한 점들을 개선해서 다시 작성한 코드가 아래와 같다.

Insert의 critical section 부분을 보면 코드가 확연히 줄어든 것을 볼 수 있는데, 

이렇게 코드를 작성하면 Thread가 여러 개가 서로 경쟁을 하더라도 critical section을 금방 빠져나올 수 있다.

그리고 Lookup에서도 rv 변수를 사용해서 -1이면 실패, 0이면 성공(뭔가 찾았다)해서 break로 빠져나오고

unlock으로 lock을 풀어주는 코드로 바꾸었다. 이 경우도 지적했던 문제인 조건에 따른 unlock을 제거했다.

결과적으로 더 나은 코드가 되었다.

 

결국에 Linked List는 공유 하는 상태이다.

따라서 여기서 상태에 변화를 준다는 것은 Link에 변화를 주는 것이다.

그런데 혹시라도 Link에서 Bottle neck이 걸리면 성능이 저하가 되고 확장성에 문제가 생길테니까

Lock을 분산해서 병렬성을 더 주자 라는 아이디어가 있다.

그것이 Scaling Linked Lists이다.

 

Scaling Linked Lists

Scaling Linked Lists는 각 node에 key와 자신의 lock이 별도로 존재한다.

이렇게 할 경우 여러 개의 Thread가 여러 node에 동시에 접근을 해서 상태를 바꾸려고 할 때,

기존에는 lock이 하나였기 때문에 한 곳으로 집중 됐지만

Scaling Linked Lists에서는 처리하고자 하는 node의 lock을 별도로 얻을 수 있다.

이렇게 할 경우 Lock을 거는 것이 분산될 수 있어서 병렬성이 좋아진다.

이 방식을 hand over hand locking 이라고도 하는데, 자신의 lock을 얻고 unlock 하기 전에

다른 쪽의 lock을 또 얻고 이후에 자신이 unlock 하고 이런 식으로 크로스 하면서 동작할 수 있기 때문이다.

 

다만 여기서 알아야 할 점은 이렇게 lock을 분산시키면 병렬성은 좋아지지만 성능이 꼭 좋아지는 것은 아니다.

오히려 복잡성이 올라가기 때문에 에러를 발생시킬 수 있고 lock을 얻으려는 시도에서 라이브러리를 호출 하는 비용이

존재하기 때문에 single lock 보다 성능이 안좋을 수도 있다.