산타캅의 샌드박스

UVa Online Judge

결론부터 말하자면
 
1. 링크드 리스트 당 하나의 동기화 객체를 사용할 것.

2. 성능을 위해 Read Write Lock(또는 Shared Exclusive Lock이라고도 함)을 사용할 것.
 (동시에 여러명이 Read 가능, 한명만 Write 가능)

3. 리스트가 길어져서 탐색 시간과 대기 시간이 증가할 것 같으면 해시 테이블을 사용하고, 각 버킷별로 하나의 동기화 객체를 사용할 것.



멀티스레드 프로그래밍에서 링크드 리스트(Linked List)를 다루다 보면 마주치는 문제가 있다. 바로 동기화이다.

이게 접근할 수 있는 스레드가 한개면 상관이 없는데, 여러개일 경우에는 push와 pop이 동시에 진행되면서 잘못된 메모리 참조를 하고 프로그램이 죽어버리는 상황이 발생할 수 있다. 실제로 이 점을 전혀 염두하지 않고 프로그램을 만들었다가 프로그램이 피를 토하며 죽고 나서야 실수를 깨달았던 경우가 있었다. 그 후부터는 항상 리스트를 만들 때 동기화가 필요한지에 대해 생각한다.

대개 이런 상황에서는 리스트 한개당 하나의 크리티컬 섹션을 사용해서 동기화하는 방법을 사용했다. 그런데 리스트가 길어지다 보면 탐색 시간이 오래 걸리기 마련인데, 만약 여러 스레드가 하나의 리스트를 '읽으려' 할 때 동시에 읽어도 되지만 크리티컬 섹션에 막혀서 하나씩 대기를 타고 있는 비효율적인 상황이 발생한 적이 있다.


이 문제를 해결하기 위해서 처음에 생각해 낸 방법은 '각 노드마다 동기화 객체 사용'이었다. 리스트 전체를 잠그는 대신 하나의 노드만 잠그고 읽거나 쓰면, 잠기지 않은 다른 노드는 다른 스레드가 접근할 수 있기 때문이다.

그런데 생각하다보니 문제가 하나 생겼는데, 일단 노드들이 주루룩 있는 상태에서는 각 노드를 잠가서 읽거나 쓰는(노드의 내용을 수정하는)데는 문제가 없었다. 하지만 링크를 끊거나 연결하는 과정에서 문제가 발생할 것이 분명했다.

동기화라는 것은 원자적(아토믹, Atomic)이지 않은 여러 개의 명령을 원자성을 가지도록 해주는 것이다. 원자적인 명령 단위는 멀티스레드 환경에서도 안전하다. 자세한 내용은 생략.

위에서 말한 그 문제는, 링크드 리스트에서 노드를 추가하거나 삭제할 때 연결을 맺고 끊는 과정이 원자적이지 않아서 발생한 것이다. 앞 노드의 연결을 수정하고, 뒤 노드의 연결을 수정하는 두개의 과정이 있기 때문이다. 그럼 락 걸고 앞뒤로 수정한 다음에 언락하면 되는거 아냐? 말은 쉽지만 1번 노드에 락 건다고 2번 노드까지 잠기는게 아니니까.

고민하던 끝에... 그래! 그냥 락 앞뒤로 걸어버리자! 하고 생각했다.

이론적으로 될 거라고 생각했다. 하지만 데드락과의 사투 끝에... 결국 내린 결론은 리스트 통째로 락 거는게 가장 낫다는 것이었다. 동기화 로직에 들어가는 코드의 양이 비대해지고 복잡해지면서 과연 다른 사람이 이 코드를 보고 이해할까 하는 생각이 드는 것은 물론이었다. 어찌어찌 해서 사실 완성은 했지만, 결국 이 코드를 버렸다.

쓰기를 할 때 뿐만이 아니라 읽기를 할 때도 필요한 노드를 포함해서 앞뒤 3개의 노드에 락을 걸어야 했다. 물론 데드락이 생기지 않게 왼쪽 오른쪽 자신 순서로 걸도록 했지만...

이제 여러 개의 스레드가 읽는다고 쳐보자. 락과 언락에 걸리는 시간때문에 오히려 퍼포먼스가 떨어질 지경이다.

그래서 버렸다. 사실 성능 측정으로 비교해보지는 않았다. 하지만 그렇게 직감이 들었다.


그 대안으로 해시 테이블을 선택했다. 말하자면 리스트를 쪼개서 분산 처리하는 것이다. 테이블의 각 버킷을 링크드 리스트로 만들면 된다. 그리고 각 버킷별로 동기화 객체를 사용하면 된다. 동시에 읽을 수 있게 Read Write Lock을 사용하면 더 좋다(Read Write Lock은 Interlock을 사용해서 직접 구현했다).

말은 마치 해시 테이블을 교묘하게 이용한 링크드 리스트처럼 했지만, 그냥 해시 테이블을 쓰는거다. 충돌이 발생하면 링크드 리스트로 이어가는 것일 뿐이지.

해시 테이블은 링크드 리스트보다 조금 더 메모리를 소모한다. 하지만 많은 데이터가 있어도 검색과 삽입, 삭제가 빠르므로 현업에서 자주 사용하고 있다.