06.06-과제백업용

RCU(Read-Copy-Update)는 무엇인가 RCU는 어떻게 동작하는가? RCU를 사용한 자료구조 예제 및 프로그램 샘플 RCU의 장점 및 단점? RCU는 어떤 상황에서 다른 기법보다 우수한 성능을 보이는가? 그 이유는 무엇인가? RCU의 개선점은? [ read 연산이 압도적으로 많은 경우? ]

RCU란 무엇인가? RCU(Read-Copy Update)란 여러 개의 실행 흐름 또는 스레드가 동시에 실행되는 동시성 프로그래밍(Concurrent Programming) 패러다임 상에서 자원을 공유하는 상황에서 공유자원에 안전하게 접근하기 위해 사용하는 동기화 매커니즘이다. RCU는 동기화 매커니즘 중 Reader-Writer 동기화 매커니즘을 따르며, read 연산과 write 연산의 동기화 오버헤드가 가진 비대칭성을 고려해서 그에 따른 오버헤드의 비대칭 분배를 극대화하여 read 연산이 임계구역(Critical Region)에 접근할 때 발생가능한 락(lock), 원자적인 명령처리, (메모리 배리어 명령)과 같은 오버헤드의 발생을 없앤 동기화 매커니즘이다. reader의 동기화 오버헤드를 최소화하여 read-only 작업에 대해선 거의 이상적인 성능을 보여주지만 임계구역을 접근하는 오버헤드가 절대적으로 감소했다고 단언하긴 힘들다. reader가 가질 수 있는 오버헤드를 Writer에 비대칭적으로 분배했기 때문에 Write 작업에 대해선 상당한 동기화 오버헤드를 감수해야 한다. 따라서 read 연산 작업의 비율이 큰 운영체제 환경에서는 큰 성능향상을 기대할 수 있지만 write 연산 작업의 비율이 큰 환경에서는 오히려 성능이 떨어질 수 있다. RCU는 DYNIX/ptx 운영 체제 커널에서 구현되어 지연 해제(deferred-destruction)기반 동기화 메커니즘을 사용하여 대형 데이터베이스 서버를 실행하는 상황 등의 mission-critical 데이터 센터 환경에서 사용되었다. 이후 확장되어 Linux 2.5.43 커널에도 통합되어 사용되고 있고 RCU의 변형 또한 K42와 Tornado 연구 운영 체제 및 IBM의 메인프레임 VM/XA 가상 머신 모니터에서 독립적으로 구현되어 사용되었다. RCU는 동기화 매커니즘의 맥락에서 독점적인 락(exclusive locking)에서 Reader-Writer 락(Reader-Writer locking)을 거쳐서 발전해 온 결과다. 독점적인 락은 Reader와 Writer의 구분 없이 임계구역에 대한 연산 요청이 철저하게 순서대로 처리(orderign)되어야 한다. 따라서 임계구역에 접근하는 특정 연산은 이전 연산의 처리가 완료된 이후에, 이후 처리될 연산의 시작 이전에 한 번에 한 개씩 처리된다. 따라서 read 연산 동기화를 위해서 다른 read 연산과 write 연산의 처리에 대해서는 해당 연산들의 수행이 blocking 된 후 처리하고 있는 연산이 끝났을 때 다음 연산이 실행된다. Reader-Writer 락은 독점적인 락과 같이 임계구역에 대한 write 연산 사이의 처리 요청은 철저하게 ordering 되어있지만 read 연산의 처리 요청은 ordering 되어있지 않고 동시에 처리를 할 수 있다. 이는 앞서 얘기한 Reader-Writer의 동기화 오버헤드 비대칭성을 고려해서 오버헤드를 비대칭적으로 분배한 것으로, 임계구역의 공유자원 데이터가 변하지 않는 상황에서만 read 연산 처리를 할 수 있다. 따라서 데이터의 일관성(consistency)을 유지하기 위해 쓰기 read 작업에 대한 락은 필요 하므로 read 연산과 write 연산은 처리과정에서 철저히 ordering 되어야한다. RCU는 일반적인 Reader-Writer 락과 달리 read 연산과 write 연산의 처리요청에 대한 ordering도 필요 없게 설계된 것이다. 이 경우 Reader가 요청하는 연산은 다른 Reader의 연산과 Writer의 연산을 생각할 필요가 없기 때문에 ordering으로 부터 자유롭고 이에 따라 read 연산의 동기화 오버헤드를 크게 줄임으로써 동시성을 극대화해서 read 연산의 효율성을 높인 매커니즘이다.
RCU는 어떻게 동작하는가? RCU에 쓰이는 용어정리 스레드(Thread): 스레드는 작업 실행의 단위이다. 여기서 스레드는 프로세스, 인터럽트 핸들러, 이벤트 핸들러, 코루틴, 트랜잭션 등과 같은 것들을 포함하는 일반적인 의미로 사용한다.

라이브 변수(Live Variable): 현재 값이 향후 실행 상태에서 영향을 줄 가능성이 있는 변수로 변수값의 수정 이전에 액세스될 수 있는 변수

Dead 변수(Dead Variable): 라이브 변수와는 반대로 다음 액세스 이전에 수정될 변수로, 따라서 현재 값이 향후 실행 상태에 어떠한 영향도 미칠 수 없는 변수.

임계구역(Critical Section): 공유 메모리에 대한 액세스가 스핀락, RCU와 같은 동기화 메커니즘을 통해 외부의 영향으로부터 보호되는 코드 영역

read-side 임계구역(Read-Side Critical Section): 마찬가지로 임계구역이므로 공유 메모리에 대한 액세스가 다른 스레드로부터의 간섭으로부터 보호되는 코드 영역으로, 여러 개의 Reader의 임계구역 사용을 허용하기 위한 동기화 메커니즘을 사용한 임계구역. RCU의 경우, RCU read-side 임계구역에서 참조하는 데이터는 해제되어 반납되는 것으로부터 보호된다.

임시 변수(Temporary Variable): 임계구역 내에서만 사용되는 변수.

영속적 변수(Persistent Variable): 임계구역 외부에서 사용되는 변수.

휴식 상태(Quiescent State): 어떤 RCU-protected 데이터 구조에 대한 참조가 없는 스레드의 실행 상태. 후보 휴식 상태(candidate quiescent state)와 관찰된 휴식 상태(observed quiescent state)라는 두 가지 유형의 휴식 상태가 있다. 이 보고서에서는 일반적으로 관찰된 휴식 상태의 의미로 휴식 상태라는 용어를 사용한다.

후보 휴식 상태(Candidate Quiescent State): 임계구역에서 사용되는 임시 변수들이 모두 더 이상 사용되지 않는 특정 코드 지점. 모든 RCU read-side 임계구역 외부에 위치한 지점은 후보 휴식 상태가 될 수 있습니다. 후보 휴식 상태는 선택된 데이터 구조에 대해 휴식 상태이므로 사용되지 않는다는 점을 주목한다. 관찰된 휴식 상태(Observed Quiescent State): 모든 후보 휴식 상태를 고려하는 것은 심각한 오버헤드를 초래하거나 특수한 하드웨어 지원을 필요로 할 수 있다. 그러나 일부 후보 휴식 상태는 특히 비용이 적게 드는 관찰 가능한 상태일 수 있다. 이는 영속적인 운영 체제 상태 변경과 관련이 있다. 이런 상태를 관찰된 휴식 상태라고 한다. 예를 들어, 비선점형 Linux 커널에서는 문맥교환이 관찰된 휴식 상태다. 각 문맥교환 발생시마다 카운터가 증가하기 때문이다.

유예기간(Grace Period): 모든 스레드가 적어도 하나의 휴식 상태를 거치는 시간 간격. 유예기간의 핵심 특성은 해당 유예기간의 시작 시점에서 RCU read-side 임계구역에서 사용되는 모든 임시 변수가 해당 유예기간 동안 적어도 한 번은 휴식 상태이다. 따라서 이러한 변수들은 유예기간이 끝난 후에는 어떠한 직접적인 영향도 미칠 수 없으며, 유예기간 시작 전에 어떤 시점에서든 데이터 구조에서 제거된 요소를 참조하지 않는다. 또한 유예기간을 포함하는 시간간격도 유예기간이라 할 수 있다. 메모리 배리어(memory barrier): CPU나 컴파일러에게 특정 연산의 순서를 강제하도록 하는 기능. CPU에서는 파이프라이닝과 같이 비순차적 명령어 처리 기법을 통해 연산 결과에 영향이 가지 않도록 연산의 순서를 뒤바꿀 수 있으며, 컴파일러도 비슷한 최적화를 수행한다. 하지만, 이러한 기능은 다중 스레드가 동시에 돌아가는 환경에서 코드의 실행 순서가 바뀌어 실행되는 동안 다른 스레드에서 그 부분에 대한 메모리를 접근하여 잘못된 결과를 내놓을 수 있다. 따라서 이런 문제를 해결하기 위해서 특정 부분에 대해 실행 순서를 강제하는 메모리 배리어를 놓아야 한다.

RCU 동작원리 RCU가 read 측면에서 동기화 매커니즘의 높은 성능을 보이는 동작원리를 요약해서 정리하면 ‘Reader-Writer 락의 read와 write의 동기화 오버헤드가 비대칭성을 가진다는 점을 이용해서 read 연산의 오버헤드를 최소화하고 write 연산에 오버헤드의 부담을 더하는 동기화 오버헤드의 비대칭적 분배’라고 할 수 있다. 이러한 오버헤드의 비대칭적 분배를 최적화한 RCU의 동작을 위해선 아래의 기능이 보장되어야한다. Readers와 Writers 지원 다중 버전 관리 Writer-Writer 동기화 Reader-Writer 동기화 weak memory-consistency semantics와의 상호작용 Readers, Writers 읽기(read)는 임계구역의 공유자원에 대해서 공유자원의 상태를 거의 바꾸지 않는 데이터 접근 연산방식을 말한다. Reader는 데이터의 통계적 상태나 CPU 상태에 대한 정보를 바꿀 수 있지만 Writer와 같은 다른 참여자가 접근할 수 있는 정보에 대해서는 업데이트는 하지 않는다. 쓰기(write)는 임계구역의 공유자원에 대해서 공유자원의 상태를 업데이트하는 데이터 접근 연산방식을 말한다. read가 임계구역에서 중요한 데이터를 바꾸지 않기 때문에 read-side에서 read는 다른 read 연산에 영향을 미치지 않는다. write에 의한 업데이트가 발생하지 않는 이상 read는 데이터를 변화시키지 않기 때문에 read 연산끼리는 read 요청의 수행 순서에 상관 없이 동일한 데이터값에 접근하므로 read 연산의 결과에 영향을 미치지 않는다. write 연산 또한 덮어쓰기 과정만 한다면 write 연산끼리는 요청 처리 순서가 영향을 미치지 못하겠지만 데이터의 read와 write가 같이 쓰여야 하는 상황에서 write의 순서가 바뀌는 것은 read 연산이 서로 다른 데이터값을 읽게되어 read 연산의 결과값을 바꿀 수 있으므로 write의 순서는 ordering 되어있어야 한다. 이처럼 동기화 매커니즘에서 읽기 연산은 그 순서가 다른 연산들의 결과값에 영향을 미치지 못하고, 쓰기 연산은 그 순서가 다른 연산들의 결과값에 영향을 미친다는 점에서 동기화 매커니즘에서 읽기와 쓰기의 오버헤드가 비대칭성을 가진다. RCU는 공유자원의 버전이라는 개념을 도입해서 위의 일반적인 Reader-Writer 락방법 비대칭성에서 한 번 더 나아가 read 연산이 모든 연산(다른 read 연산, write 연산)과의 ordering을 필요없게 만들었다. 따라서 동기화 매커니즘을 구현할 때 Reader는 동기화를 위한 어떠한 연산도 할 필요가 없게 만들어준다. 버전은 RCU Reader가 임계구역에서 동기화를 위한 어떤 명령어도 실행하지 않게 만들기 위해서 Writer가 공유자원의 데이터 구조에서 여러 버전을 유지한다. read-side 실패(failure)에 대한 명령어 또한 버전을 통해서 방지하게 된다.

다중 버전 관리 공유자원의 데이터 구조에 여러 버전을 유지하게 되며, Writer가 버전을 만들고 Reader가 버전을 읽어들인다. 버전의 생성: Writer가 데이터를 업데이트하는 과정을 마쳤을 때 새로운 버전이 생긴다. 버전의 삭제: Writer로 새로운 버전이 만들어진 시점에서 동시에 특정 옛 버전에 대한 read 연산을 진행중이던 모든 Readers가 임계구역에 대한 작업을 끝냈을 때 해당 버전을 반납하며 그 버전이 논리적으로 삭제된다. <사진 1. multiple version handling>

사진1은 이러한 다중 버전이 어떻게 구현될 수 있는지 보여주는 예시다. 동적으로 할당된 데이터 항목에 대해서 데이터 주소를 가리키는 헤드 포인터(head pointer)를 사용하여 설명되었다. 1단계는 초기상태의 리스트를 보여주며, 헤드 포인터는 동적으로 할당된 구조의 버전 1을 참조하는 모습이다. 2단계는 Writer에 의해 첫 번째 업데이트가 진행된 이후의 리스트를 보여준다. 업데이트에 따라서 구조의 버전 2가 만들어진 모습을 볼 수 있다. 파란 화살표는 업데이트가 됐지만 여전히 구조의 버전 1을 참조하는 Reader가 read 연산을 수행하고 있을 수 있음을 나타낸다. 3단계는 Writer에 의한 두 번째 업데이트 이후의 리스트를 보여준다. 이때 구조의 버전 3이 만들어졌으며, 파란 화살표는 여전히 Readers가 버전 1과 버전 2의 구조에 대해 연산을 수행하고 있어 헤드 포인터가 해당 버전의 구조를 참조할 수 있다는 것을 나타낸다. 4단계는 버전 1을 참조하는 모든 Reader가 read 연산을 마쳐 read-side RCU 임계구역에서 빠져나간 후의 리스트를 보여준다. 이 때, 해당 버전에 대한 주어진 구조를 참조하는 모든 Readers가 read-side RCU 임계구역에서 빠져나갔는지 확인하기 위한 메커니즘이 필요하다. 5단계는 구조에서 더이상 어떤 Readers도 참조하지 않는 버전 1의 구조가 반납된 후의 리스트를 보여준다. 6단계는 Writer에 의한 세 번째 업데이트 이후의 리스트를 보여준다. 이때 데이터 구조의 버전 4가 만들어졌으며, 파란 화살표는 여전히 구조의 버전 2를 참조하는 Readers가 있고, 버전 3에 대한 모든 Readers의 read 연산이 종료되어 참조하는 헤더 포인터가 없음을 확인할 수 있다. 이 단계에서 Reader는 read-side 임계구역에서의 read 연산이 순서대로 종료하지 않을 수 있다는 것을 볼 수 있다. 7단계는 구조의 버전 2와 3을 참조하는 모든 Reader가 read-side RCU 임계구역에서 빠져나간 후의 리스트를 보여준다. 8단계는 더이상 참조하는 헤더 포인터가 없는 구조의 버전 2와 3이 반납된 이후의 리스트를 보여준다. 다중 버전 관리를 통해 RCU Reader가 read-side에서 동기화 없이 진행할 수 있는 메커니즘으로, 각 버전은 업데이트 과정에 해당한다. 위의 로직에 따라서 각 업데이트는 Writer로 인해 요소의 새 버전 생성하는 작업(removal)과 Readers의 작업 및 참조 종료에 의해 해당 요소의 이전 버전 삭제하는 작업(reclaimation)으로 나눌 수 있다. 첫 번째 작업은 Reader를 연관시키지 않고 원자적으로 수행될 수 있으며, 두 번째 작업은 Reader의 정확성에 영향을 미치지 않고 무기한으로 연기될 수 있습니다. 그러나 Writer는 서로 동기화되어야함을 확인할 수 있다.

Writer-Writer 동기화 RCU는 어떤 유형의 Writer-Writer 동기화를 사용해야 하는지를 명시하지 않는다. 대부분의 경우, Writer를 동기화하기 위해 락이 사용되며, 가장 빈도가 높게 사용되는 것은 코드 락 또는 데이터 락이다.

Reader-Writer 동기화 RCU에서 Reader는 동기화 명령문을 실행할 필요가 없다. 그러나 Reader가 여전히 참조하고 있는 데이터 구조를 Writer가 없애버리는 것을 방지하기 위한 동기화가 필요하다. Reader가 동기화 명령에 대한 생각을 안하지만 Writer와의 동기화가 필요해보이는 역설적인 상황은 아래에서 설명하는 바와 같이 RCU Reader와 Writer 간의 동기화가 간접적으로 이루어진다는 사실로 해결된다. Reader측 신호는 일괄적으로 처리될 수 있으므로 이전의 여러 RCU Reader 사이의 하나의 신호가 사용될 수 있다.

RCU와 Reader-Writer 락의 임계구역은 동일한 규칙을 따르지만, RCU는 Reader-Writer 락과 달리 모든 read-side 임계구역 쪽에서 Writer에게 직접 동기화 신호를 보내야 하는 것이 아니며 동기화 신호의 전송을 지연시킬 수 있다. 이로써 단일 신호가 임의로 많은 read-side 임계구역 사용의 완료를 Writer에게 알릴 수 있다. RCU의 read-side 신호의 지연은 Reader에게 발생하는 동기화 오버헤드를 크게 감소시킵니다. RCU에서 Reader와 Writer 간의 지연 동기화는 아래와 같이 동작한다.

비선점(non-preemptive) 방식의 경우 RCU read-side 임계구역에서 문맥교환이 발생할 수 없으므로, 차단된 스레드 또한 이전의 모든 RCU read-side 임계구역 사용을 완료한 상태여야 한다.
RCU read-side 임계구역 사용을 완료할 때 RCU-protected 데이터 구조에 대해 모든 참조를 반납해야하므로, RCU read-side 임계구역에서 실행 중이지 않은 스레드는 RCU-protected 데이터 구조에 대한 어떠한 참조도 보유할 수 없습니다.
차단된 스레드는 RCU 임계구역에서 실행 중일 수 없으며, RCU 임계구역에서 실행 중이지 않은 스레드는 RCU-protected 데이터 구조에 대한 참조를 보유할 수 없으므로, 차단된 스레드는 RCU-protected 데이터 구조에 대한 참조를 가질 수 없다.
RCU-protected 데이터 구조에서 참조가 반납된 경우 해당 구조의 경로가 더 이상 존재하지 않으며, 스레드는 그에 대한 새로운 참조를 얻을 수 없다. 모든 RCU Read-side 임계구역에서 해당 구조에 대한 참조를 반납한 후에야 해당 데이터(버전)가 사라진 상태가 되며, 그 값은 이후의 RCU Read-side 임계구역에 더 이상 영향을 줄 수 없다.
차단된 스레드는 RCU-protected 데이터 구조에 대한 참조를 보유할 수 없으며, 이전에 RCU-protected 데이터 구조에서 제거된 데이터에 대한 새로운 참조를 얻을 수 없으므로, RCU-protected 데이터 구조가 반납된 후에 차단된 스레드는 해당 데이터에 대한 참조를 보유할 수 없다.
주어진 데이터가 차단된 후에 모든 스레드가 차단된 상태를 보이면 RCU-protected 데이터 구조에서 제거되며 RCU read-side의 임계구역에 있는 어떤 스레드도 해당 요소에 대한 참조를 유지하고 있을 수 없다.

이 접근 방식의 문제는 특정 시스템에선 수만 개의 많은 스레드가 실행될 있다는 것이다. 이 때 각 스레드의 상태를 확인하는 것은 많은 오버헤드를 초래하게되며, read-side 임계구역에서 동기화 명령을 제거함으로써 이뤄낸 성능 향상 효과를 무색하게 만들 수 있다. 비선점 시스템에서 이 문제를 해결하는 한 가지 방법은 현재 실행 중인 스레드 만이 read-side 임계구역에 있을 수 있으며, 그 외의 스레드는 blocking된 상태여야 하게 만드는 것이다. 따라서 CPU는 현재 실행 중인 스레드만 확인하며 이런 오버헤드로 부터 벗어날 수 있다. 이 때 당연히 실행 중이지 않은 다른 스레드는 blocking된 상태이다. 대부분의 시스템은 CPU보다 훨씬 많은 스레드를 가지고 있으므로, 모든 read-side 임계구역 이용의 완료를 확인해야하는 오버헤드를 크게 줄일 수 있다. 지연 동기화를 통해 구현된 RCU-protected 데이터 구조의 요소를 안전하게 삭제하기 위해서 아래의 절차를 따른다.

RCU-protected 구조에서 데이터 요소를 제거하되 RCU read-side 임계구역에서 참조하는 필드는 그대로 유지한다.
각 CPU에서 적어도 하나의 문맥교환을 실행할 때까지 기다린다.
요소를 반환하는 등 필요한 반남(destruction) 작업을 수행한다. 이 때, freelist에 구조체를 반납하게 된다.

RCU Reader와 Writer 사이의 간접 동기화는 위의 삭제 절차의 3단게에서 구조체가 반납될 때 Reader가 더이상 해당 구조체를 참조하지 않게 됨을 보장해준다.

Weak memory-consistency semantics 현대의 CPU는 weak memory-consistency semantics을 가지고 있으므로 하드웨어에서 읽기와 쓰기의 순서가 변경될 수 있으며, 서로 다른 CPU들은 읽기와 쓰기 작업의 순서에 대해서 정보를 공유하지 못하여 메모리 일관성이 떨어질 수 있다. 이러한 약한 메모리 일관성은 하드웨어 성능 고려 사항과 개별 CPU가 일반적으로 private한 정보나 락을 보유한 데이터를 처리하기 때문에 다른 CPU가 관찰하는 CPU의 메모리 작업 순서는 보통 중요하지 않다는 점에 기반한다. 따라서 CPU는 소프트웨어가 필요한 경우에만 순서의 일관성을 유지할 수 있게끔 메모리 배리어(memory barrier) 명령을 수행함으로써 락을 획득하거나 해제할 때 임계구역이 주변 코드로 접근되어지지 않게 보장한다. RCU Writer는 RCU-protected 데이터 구조에서 공유자원에 대해 일관된 정보를 RCU Reader가 접근할 수 있도록하려면 필요에 따라 메모리 배리어를 실행해야한다. 예를 들어, RCU-protected 데이터 구조에 새로운 구조체 버전을를추가할 때 RCU Writer는 다음의 절차를 따른다 새로운 구조체를 초기화하여 할당하고, 이 구조체는 이웃하는 구조체를 참조하는 포인터를 포함합니다. 메모리 배리어 명령을 실행한다. RCU-protected 데이터 구조의 기존 구조체가 새 구조체를 가리키도록 포인터를 업데이트한다.

이 절차에서 메모리 배리어는 1단계에서 새 구조체를 초기화하는 모든 데이터의 메모리 작성이 3단계의 포인터 업데이트보다 먼저 다른 CPU에서 볼 수 있도록 보장한다.