1. 들어가기 전에 … 🔗

앞으로 기술하는 내용은 http://jake.dothome.co.kr/rcu/#comment-214230 에서 발췌하여 정리하는 내용이므로 원본 내용 확인을 위해서는 링크에서 직접 보길 권한다. RCU 내용 뿐만 아니라, 리눅스 커널 전반적인 내용에 대해 정말 자세하게 정리가 잘 되어있다.

RCU(Read, Copy, Update)란 리눅스 커널 내에서 주로 읽기 연산만 일어나고 쓰기 연산의 비중은 매우 작은 객체에 주로 쓰이는 동기화 기법이다. Reader-Writer 락과 비슷한 동기화 기법인데, RW 락에 대해 RCU가 가지는 상대적인 강점으로는 읽기 연산이 wait-free(읽기 연산에 대해 Block이 일어나지 않음)이며 그 오버헤드가 극도로 작다는 점 등이 있다. 대신 쓰기 연산의 오버헤드가 상당하고 쓰기에 필요한 동기화의 시간 복잡도가 최소한 RCU로 보호되는 객체의 크기에 비례한다.

2. RCU란? 🔗

• 불변 객체(Immutable Object)에 대한 쓰레드는 안전하다. 즉, 어떤 코드 영역을 수행하는 동안 공유되는 메모리 구간이 불변인 경우라면, 코드로 인한 상태의 변화는 항상 예측 가능하므로 코드 수행의 결과가 항상 결정적(Deterministic)이다.

• 메모리 배리어 등을 통해 가시성이 확보된 경우 단일 워드에 대한 쓰기 연산은 대개 원자적이다.

• 어떤 객체의 상태를 변경하는 코드를 수행할 때 그 변경이 다른 쓰레드의 입장에서 한 순간에 원자적으로 이루어지는 것처럼 보인다면, 연관된 코드들의 수행 내역은 단일 쓰레드로 재현 가능하다. 쓰레드 간 코드 수행 순서에 대한 구체적인 합의가 필요한 경우는 드물기 때문에 대부분 이 정도만 보장되어도 동기화로서 충분한 역할을 할 수 있다.

GC(Garbage Collector)를 지원하는 요즘 언어들은 객체를 직접 변경하는 대신 불변 객체를 새로 만들어서 사용한다. 예를 들어, 자바의 경우는 문자열을 변경할 경우, 변경된 결과의 불변 문자열을 가져와 새로운 인스턴스를 할당하여 사용한다(String Internalization). 즉, 기존의 객체를 변경하는 대신 새로운 불변 객체를 만들어 쓰레드의 안전성을 쉽게 확보하는 것이 RCU의 기본 개념이다.

RCU로 보호되는 객체에 대한 읽기를 하려고 하는 경우, 평소처럼 포인터를 가져와 읽기 전용으로 해당 객체를 다루면 된다. 하지만 RCU로 보호되는 객체를 변경하려는 경우, 객체를 직접 변경하는 대신 새로 할당한 메모리 영역에 객체를 복사한 뒤 새로 만든 객체를 변경한다. 기존의 객체는 불변이므로 이 과정은 안전하다.

하지만 실제로 GC와 달리 직접 관련된 자원을 해제해 관리해줘야 하는 경우 Reader 입장에서 더 이상 접근할 방도가 없는 객체인 경우만 해제해주면 되지만 이를 위해서는 레퍼런스 카운팅이 필요하다. 즉, 읽기 영역에 진입/이탈 시에 원자적인 정수 연산이 적어도 한 번씩은 일어나는데 리눅스 커널에서는 이를 간단하게 해결한다.

RCU는 커널 코드 내에서만 사용되며 커널 모드에서 수행이 끝나면 RCU의 읽기 구간 역시 끝나게 된다. 선점형 커널을 사용하고 있는 경우 문맥 교환이 한번씩 이루어지고 비선점형 커널인 경우 읽기가 끝나면 모든 동작들이 종료된 것이므로 메모리를 안전하게 해제할 수 있다.

3. RCU의 장/단점 🔗

RCU는 read-side overhead를 최소화하는데 목적이 있기 때문에 동기화 로직이 읽기 동작에 더 많은 비율로 사용되는 경우만 사용한다. 수정 동작이 10% 이상인 경우에는 오히려 성능이 떨어지므로 RCU 대신 다른 동기화 기법을 선택해야 한다.

3-1. 장점 🔗

1. read-side overhead가 거의 없다. (zero wait, zero overhead)
2. Deadlock 이슈 없음
3. Priority Inversion 이슈 없음
4. Unbounded Latency 이슈 없음
5. Memory Leak Hazard 이슈 없음

3-2. 단점 🔗

1. 사용이 복잡하다.
2. 쓰기 동작에서 다른 동기화 기법보다 느리다.

4. 기본 요소 및 개념들 🔗

커널 문서를 읽기에 앞서 기본 요소에 대해서 미리 알고 읽는 것이 훨씬 낫다. 이름이 낯설기 때문에 관련 용어들에 대해 미리 알아야 한다. RCU는 아래와 같이 3가지 기본 요소와 특징이 있다.

4-1. Reader 🔗

Reader는 rcu_read_lock()과 rcu_read_unlock() 코드 범위의 Read-side critical section이다.

RCU에서 보호해야 하는 데이터에 접근할 때 항상 이 영역 내에서만 접근해야 한다는 점이다. 이 영역을 벗어난 사용은 RCU 규칙을 벗어난 것이며 존재하지 않는 데이터 또는 잘못된 데이터로의 접근이 될 수 있다. 그리고 반드시 보호해야 할 데이터에 접근하기 전, 메모리 배리어를 사용한 후에 참조해야 한다.

4-2. Updater 🔗

기존의 여러가지 락 중 하나를 사용하여 데이터를 보호하고 수정한다.

4-3. Reclaimer 🔗

Updater에서 최종 수정한 객체가 아닌 사용이 완료된 객체들에 대해 메모리 해제하는 작업을 한다. 이 때, 안전하게 메모리 해제가 되도록 삭제할 데이터에 접근하는 Reader들이 없음을 보장하기 위해 반드시 Grace Period가 지난 후에 Reclaimer가 동작하도록 한다.

4-4. Grace Period (GP) 🔗

Grace Period를 사전에서 찾아보니 유예기간이라는 의미로 해석되었다. 한 마디로 정리하면, 동기화를 위해 업데이트 해야 할 내용을 곧바로 반영하지 않고 기존 Reader들이 읽기를 모두 완료할 때까지 기다리는 시간이다.

사용자는 특정 자료의 동기화를 위해 두 가지의 관점에서 처리한다.

• 읽기 처리만 수행하는 read-side critical section이 있고 이를 Reader라고 부른다.
• 변경 처리가 포함된 write-side critical section이 있고 이를 Writer 또는 Updater라고 부른다.

이 때, RCU에서는 업데이트가 발생하는 시점부터 각 처리 과정을 아래와 같이 세 가지 단계(Removal, Grace Period, Reclamation)로 구분한다.

1단계. Removal 🔗

write-side critical section 구간에서는 데이터를 읽은 뒤 사본을 만들고 해당 사본을 변경한다. Removal(Read-Copy-Update)이 진행되는 동안 해당 데이터에 접근하고 있는 Reader들을 보호하기 위해 기존에 접근하고 있는 자료는 곧바로 수정하지 않고 이를 Copy한 후 Update하여 사용한다. 즉, Reader들을 원본 자료에만 접근하므로 데이터에 안전하게 접근할 수 있다.

2단계. Grace Period 🔗

Removal 단계의 데이터에 관련된 Reader가 완료됨을 보장할 수 있도록 대기하는 단계이다. 앞서 설명한 1단계(Removal)에서 생성된 사본을 원본에 반영해야 하는데, 곧바로 반영하면 각 cpu가 동시에 처리하고 있는 Reader에 문제가 생긴다. 따라서, Removal 기간 동안 같은 자료에 접근한 Reader의 처리가 모두 완료될 때까지 기다려야 하는데 이 구간을 GP(Grace Period)라고 한다.

3단계. Reclamation 🔗

사본을 원본에 적용하는 구간이다. 2단계 GP의 완료를 인지하면 사본을 원본에 반영하고 필요 없어진 기존 데이터는 폐기하는 Reclamation 구간이 시작된다. 이러한 처리들은 RCU의 후 CB(Call-Back) 함수를 리스트에 보관해 두었다가 Reclamation 구간에서 호출하여 처리한다.

그렇다면, Reader의 모든 처리가 완료되는 시점을 어떻게 알 수 있을까? 출처에 따르면, Grace Period 자체는 개념적인 의미이고 실제로는 Min Grace Period라고 불린다고 한다. Removal 기간 중 관련된 Reader 들의 끝 부분이 곧바로 인식되지 않으므로 Grace Period가 끝나는 시점을 감지하는 방법을 사용한다는데, 사실 직감적으로는 이해가 되지 않는다.

4-5. QS(Quiescent State) 🔗

QS(Quiescent State)의 quiescent는 ‘진행이 중단된, 조용한, 잠잠한’이라는 뜻을 가지고 있다. 이 상태는 Reader 간의 사이 시간 상태로 GP 구간 전에 이미 진행되고 있었던 Reader 의 구간이 끝난 것을 인지할 목적으로 사용된다. QS 상태가 지났는지 여부는 아래와 같은 방법들을 사용한다.

1. rcu_sched: 각 CPU에서 태스트 간 호출되는 스케쥴 틱을 이용하여 인터럽트 구간을 이용하는 방법
   

   • Context Switch
   • 유저 모드 실행 후 스케쥴 틱 진입
   • Dynticks or Idle

2. rcu_bh: softirq를 사용하는 방법

   • 커널에서 실행되는 Reader가 Idle 태스크를 수행한다는 것은 이미 문맥교환(Context Switch)를 완료했다는 의미이므로 해당 CPU에서 Reader의 완료를 보장한다.

개념 수준에서 QS(Quiescent State)는 Reader 간의 시간으로 기존 Reader의 처리가 완료되었음을 보장하는 기간이다.

출처 🔗

• https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt
• https://summerlight.tistory.com/entry/%EB%8F%99%EA%B8%B0%ED%99%94-%EA%B8%B0%EB%B2%95-Read-Copy-Update
• http://jake.dothome.co.kr/rcu/#comment-214230