예시

공유 데이터 구조는 멤버인지 아닌지, 삽입 그리고 삭제에 대한 명령들이 int로 정렬된 Linked List라고 가정하자.

그리고, 멤버가 존재하는 지의 여부를 알려주는 소스코드가 있다.

삽입 오퍼레이션이다. 저장하고자하는 요소를 임시 노드에서 값을 가져와, 중간에 연결고리를 끊고 새로 만든 노드를 5의 next로 저장하고, 새로 만들어진 7의 next를 8에 저장한다.

위 과정을 소스코드로 나타낼 수 있다.

마찬가지로, 노드를 삭제하는 과정이다. curr_p를 왼쪽으로 이동시키면서, 삭제하고자 하는 Value를 찾는다. 찾았다면, 이전 노드의 next를 끊고 curr_p의 next를 끊는다. 그 후, 끊었던 curr_p의 next 노드를 prev_node의 next로 지정하면 된다.

삭제 소스코드는 다음과 같다.

멀티스레드 도입?

이걸 pthread로 구현해보자. linked list를 제어하기 위해 header_p를 전역변수로 접근해야 한다. 이러한 헤더 함수들을 단순화할 필요가 있다. 여기서 말하는 헤더 함수들은 Member, Insert, Delete를 말한다.

2개의 스레드로 단순화한 버전이다. 만약 동시에 2개의 노드에 접근한다면, 충돌이 일어날 것이다.

해결책 1

하나의 스레드만 리스트에 접근할 수 있도록 Lock을 건다. 각 3개의 함수들은 동시성으로부터 보호받을 수 있다.

이렇게 보면 해결된 것 같지만, 아니다.
이러면 병렬화가 되었다고 할 수 없다. 자주 사용되는 Member 함수를 하나의 스레드만 접근할 수 있기 때문이다.

해결책 2

전체 리스트를 Lock하는 대신, 각각의 노드에 대해 Lock을 걸어본다.

노드 전체가 아닌 각 노드마다 mutex를 둔다. header_p를 temp_p에 두고 접근한다. 만약 다음 노드로 넘어갈 경우, 다음 노드에 Lock을 걸고, head_p는 UnLock을 한다. 이것을 반복하면서 header_p와 temp_p가 같아질 경우 모두 Unlock해주고 1을 반환한다.

아직 다 해결된 것은 아니다. 여러 개의 스레드가 접근할 수 있는 장점이 있지만,
Member함수가 이전보다 더 복잡해지고 하나의 노드에 접근할 때마다 Lock&UnLock을 하기 때문에 더 느려진다.

해결하지 못한 문제들..

위에서 2가지의 해결책을 살펴보았다. 첫번째 방법은 하나의 스레드만 전체 리스트를 조회할 수 있고, 두번째 방법은 하나의 스레드가 하나의 노드만 접근할 수 있다. 2가지 모두 효율적이라고 볼 수 없다. 이 문제를 해결하기 위해 Read-Write Lock
을 사용한다.

Read-Write Lock

첫번째 Lock은 Read, 두번째 Lock은 Write할 때 사용되는 방식이다. 여러 개의 스레드가 Lock을 잡을 수 있다. 단, write-lock 함수는 하나의 스레드만 접근할 수 있다. 어떤 스레드가 Read하고자 한다면, write을 Block시킬 수 있다. 마찬가지로, 어떤 스레드가 Write한다고 하면, Read 혹은 Write 모두 Block시킬 수 있다.

어쨌든, 지금까지 솔루션 3가지를 알아보았는데, 이에 대한 간단하게 정리된 퍼포먼스가 있다.

다른 솔루션들은 오버헤드의 영향이 크지만, Write-Read Lock방식은 좀 더 나은 성능을 보여주고 있다. 하지만 항상 좋은 것은 아니다. List의 수정이 많이 일어날 경우, 성능이 확 떨어질 수도 있다.