운영체제 기본/Linux/RCU/Tree RCU와 유예 기간: 두 판 사이의 차이
잔글 Linux 각론 경로 변경에 따른 본문·목차·틀 링크 갱신 |
반복 대조 및 강조 표현 정리, ASCII 도표 통일 |
||
| 1번째 줄: | 1번째 줄: | ||
{{이전 다음 문서 | {{이전 다음 문서 | ||
|이전= | |이전=<- 이전 문서<br>[[운영체제 기본/Linux/RCU/갱신과 메모리 회수|갱신과 메모리 회수]] | ||
|목차=[[운영체제 기본/Linux/RCU|RCU 목차]] | |목차=[[운영체제 기본/Linux/RCU|RCU 목차]] | ||
|다음=마지막 문서 | |다음=마지막 문서 | ||
}} | }} | ||
Tree RCU는 | Tree RCU는 태스크와 CPU별로 상태를 기록하고 트리에서 유예 기간의 완료를 모은다. 독자에게 가벼운 경로를 제공하는 대가로 갱신, 회수 측의 상태 추적이 복잡해진다. Linux v6.12의 <code>CONFIG_PREEMPT_RCU=y</code>, 다중 CPU, 일반 유예 기간을 기준으로 내부 연결을 살펴본다. | ||
== 읽기 구간의 태스크별 기록 == | == 읽기 구간의 태스크별 기록 == | ||
<code>rcu_read_lock()</code> 아래의 <code>__rcu_read_lock()</code>은 현재 태스크의 <code>rcu_read_lock_nesting</code>을 증가시킨다. 대응하는 unlock은 감소시키고, 가장 바깥 읽기 구간이 끝났을 때 미뤄둔 특별 처리가 있으면 <code>rcu_read_unlock_special()</code>을 실행한다. | <code>rcu_read_lock()</code> 아래의 <code>__rcu_read_lock()</code>은 현재 태스크의 <code>rcu_read_lock_nesting</code>을 증가시킨다. 대응하는 unlock은 감소시키고, 가장 바깥 읽기 구간이 끝났을 때 미뤄둔 특별 처리가 있으면 <code>rcu_read_unlock_special()</code>을 실행한다. 태스크별 기록을 사용하여 읽기 측의 전역 원자 연산 비용을 줄인다.<ref name="plugin">[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/rcu/tree_plugin.h?h=v6.12 Linux v6.12, kernel/rcu/tree_plugin.h], __rcu_read_lock, __rcu_read_unlock, rcu_note_context_switch와 rcu_read_unlock_special.</ref> | ||
<pre> | <pre> | ||
태스크의 읽기 구간 | 태스크의 읽기 구간 | ||
read_lock nesting 0 | read_lock nesting 0 -> 1 | ||
read_lock nesting 1 | read_lock nesting 1 -> 2 | ||
read_unlock nesting 2 | read_unlock nesting 2 -> 1 | ||
read_unlock nesting 1 | read_unlock nesting 1 -> 0 : 바깥 구간 종료 | ||
</pre> | </pre> | ||
읽기 도중 태스크가 선점되면 CPU는 다른 일을 시작해도 그 태스크는 이전 객체의 포인터를 가지고 있다 | 읽기 도중 태스크가 선점되면 CPU는 다른 일을 시작해도 그 태스크는 이전 객체의 포인터를 가지고 있다. <code>rcu_note_context_switch()</code>는 선점된 독자를 해당 <code>rcu_node</code>의 <code>blkd_tasks</code> 목록으로 연결한다. 현재 유예 기간을 막는 독자는 <code>gp_tasks</code> 등으로 추적하며, 태스크가 다시 실행되어 바깥 읽기 구간을 끝내야 이 조건을 해소할 수 있다.<ref name="plugin" /> | ||
이 기록 덕분에 읽기 구간 전체에서 선점을 금지하지 않아도 수명을 지킬 수 있다. <code>CONFIG_PREEMPT_RCU=n</code>에서는 읽기 구간과 선점 제어의 관계가 다르므로 위 태스크 목록 경로를 그대로 적용하지 않는다. | 이 기록 덕분에 읽기 구간 전체에서 선점을 금지하지 않아도 수명을 지킬 수 있다. <code>CONFIG_PREEMPT_RCU=n</code>에서는 읽기 구간과 선점 제어의 관계가 다르므로 위 태스크 목록 경로를 그대로 적용하지 않는다. | ||
| 37번째 줄: | 37번째 줄: | ||
</pre> | </pre> | ||
정지 상태(Quiescent State)는 여기서 추적하는 이전 RCU 읽기를 CPU가 계속 수행하고 있지 않음을 보고할 수 있는 상태다. 문맥에 맞는 컨텍스트 스위치나 | 정지 상태(Quiescent State)는 여기서 추적하는 이전 RCU 읽기를 CPU가 계속 수행하고 있지 않음을 보고할 수 있는 상태다. 문맥에 맞는 컨텍스트 스위치나 idle, 사용자 모드 상태의 관찰 등이 이 판단에 쓰인다. 선점된 독자가 다른 곳에 남아 있을 수 있으므로 CPU의 보고와 앞 절의 태스크 목록을 함께 확인한다. | ||
각 노드의 <code>qsmask</code>는 이번 유예 기간에 아직 보고를 기다리는 CPU 또는 하위 노드를 비트로 나타낸다. <code>rcu_report_qs_rnp()</code>는 보고된 비트를 지우고, 그 노드의 비트가 모두 지워졌으며 해당 유예 기간을 막는 선점 독자도 없을 때 상위 노드로 완료를 전달한다. 마지막 보고만 위로 올라가므로 모든 CPU가 매번 루트의 락에 몰리지 않는다.<ref name="tree">[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/rcu/tree.c?h=v6.12 Linux v6.12, kernel/rcu/tree.c], rcu_gp_init, rcu_gp_kthread, rcu_report_qs_rnp, rcu_gp_cleanup, rcu_do_batch.</ref> | 각 노드의 <code>qsmask</code>는 이번 유예 기간에 아직 보고를 기다리는 CPU 또는 하위 노드를 비트로 나타낸다. <code>rcu_report_qs_rnp()</code>는 보고된 비트를 지우고, 그 노드의 비트가 모두 지워졌으며 해당 유예 기간을 막는 선점 독자도 없을 때 상위 노드로 완료를 전달한다. 마지막 보고만 위로 올라가므로 모든 CPU가 매번 루트의 락에 몰리지 않는다.<ref name="tree">[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/rcu/tree.c?h=v6.12 Linux v6.12, kernel/rcu/tree.c], rcu_gp_init, rcu_gp_kthread, rcu_report_qs_rnp, rcu_gp_cleanup, rcu_do_batch.</ref> | ||
| 46번째 줄: | 46번째 줄: | ||
<pre> | <pre> | ||
회수 요청 | 회수 요청 | ||
v | |||
필요한 유예 기간 순서 결정 | 필요한 유예 기간 순서 결정 | ||
v | |||
CPU별 정지 상태 보고 | CPU별 정지 상태 보고 --- 선점된 기존 독자의 읽기 종료 | ||
+------------+-----------------+ | |||
v | |||
rcu_node 트리에서 완료 집계 | rcu_node 트리에서 완료 집계 | ||
v | |||
유예 기간 완료 기록 | 유예 기간 완료 기록 | ||
v | |||
해당 기간을 기다린 콜백 실행 가능 | 해당 기간을 기다린 콜백 실행 가능 | ||
</pre> | </pre> | ||
| 61번째 줄: | 61번째 줄: | ||
<code>gp_seq</code>는 단순한 시각 대신 유예 기간의 진행 순서를 표시한다. 회수 요청이 어느 완료 시점 이후 안전한지를 구분해야, 요청보다 앞서 시작되어 충분한 보장을 주지 못하는 기간을 잘못 사용하지 않는다. 여러 요청은 같은 유예 기간을 함께 기다릴 수 있다. 각 객체의 참조를 세는 대신 기존 읽기 구간들이 지나갔음을 묶어서 확인하는 방식이다. | <code>gp_seq</code>는 단순한 시각 대신 유예 기간의 진행 순서를 표시한다. 회수 요청이 어느 완료 시점 이후 안전한지를 구분해야, 요청보다 앞서 시작되어 충분한 보장을 주지 못하는 기간을 잘못 사용하지 않는다. 여러 요청은 같은 유예 기간을 함께 기다릴 수 있다. 각 객체의 참조를 세는 대신 기존 읽기 구간들이 지나갔음을 묶어서 확인하는 방식이다. | ||
CPU가 오래 보고하지 않으면 RCU는 상태를 다시 관찰하거나 스케줄링을 촉진하는 등 진행을 요구한다 | CPU가 오래 보고하지 않으면 RCU는 상태를 다시 관찰하거나 스케줄링을 촉진하는 등 진행을 요구한다. 종료하지 않는 독자가 있으면 유예 기간이 지연되고, 콜백과 메모리 회수도 밀린다.<ref name="tree" /> | ||
== 콜백 대기열과 실행 == | == 콜백 대기열과 실행 == | ||
<code>call_rcu()</code>는 <code>__call_rcu_common()</code>으로 이어져 <code>rcu_head</code>에 콜백을 기록하고 CPU별 콜백 경로에 넣는다. 기본 비오프로딩 경로에서 콜백은 <code>rcu_data</code>의 <code>rcu_segcblist</code>에 연결된다. 이 목록은 실행 가능한 콜백과 유예 기간을 기다리는 콜백을 구분한다. <code>rcu_accelerate_cbs()</code>는 필요한 기간과 연결하고, 완료가 관찰되면 <code>rcu_advance_cbs()</code>가 실행 가능한 부분을 앞으로 진행시킨다. | <code>call_rcu()</code>는 <code>__call_rcu_common()</code>으로 이어져 <code>rcu_head</code>에 콜백을 기록하고 CPU별 콜백 경로에 넣는다. 기본 비오프로딩 경로에서 콜백은 <code>rcu_data</code>의 <code>rcu_segcblist</code>에 연결된다. 이 목록은 실행 가능한 콜백과 유예 기간을 기다리는 콜백을 구분한다. <code>rcu_accelerate_cbs()</code>는 필요한 기간과 연결하고, 완료가 관찰되면 <code>rcu_advance_cbs()</code>가 실행 가능한 부분을 앞으로 진행시킨다. | ||
<code>rcu_core()</code> 경로의 <code>rcu_do_batch()</code>가 준비된 콜백들을 꺼내 실행한다. | <code>rcu_core()</code> 경로의 <code>rcu_do_batch()</code>가 준비된 콜백들을 꺼내 실행한다. 유예 기간이 완료되면 콜백을 안전하게 실행할 수 있고, 실제 실행은 콜백 처리 경로가 담당한다. 콜백 오프로딩이나 지연 회수 설정은 실행 주체와 시점을 바꿀 수 있지만, 안전한 유예 기간 이후라는 조건은 유지한다.<ref name="tree" /> | ||
<code>synchronize_rcu()</code>는 같은 완료 보장을 동기적으로 기다리는 인터페이스다. v6.12의 일반 경로 <code>synchronize_rcu_normal()</code>에는 유예 기간 완료 요청을 등록하고 completion을 기다리는 경로와 <code>wait_rcu_gp(call_rcu_hurry)</code> 경로가 있다. | <code>synchronize_rcu()</code>는 같은 완료 보장을 동기적으로 기다리는 인터페이스다. v6.12의 일반 경로 <code>synchronize_rcu_normal()</code>에는 유예 기간 완료 요청을 등록하고 completion을 기다리는 경로와 <code>wait_rcu_gp(call_rcu_hurry)</code> 경로가 있다. 두 경로 모두 호출자가 돌아왔을 때 기존 읽기 구간이 끝났음을 보장한다.<ref name="tree" /> | ||
== 비용과 적용 범위 == | == 비용과 적용 범위 == | ||
Tree RCU가 줄이는 것은 읽는 쪽의 공유 락 경쟁이다. 쓰기 측의 직렬화, 새 객체 복사, 유예 기간 추적, 이전 객체를 보관하는 메모리 비용은 남는다. 읽기가 많고 일정 시간 이전 버전을 관찰해도 되는 구조에 특히 잘 맞는다. 쓰기가 잦거나 읽기 구간이 길면 회수 지연이 커지므로 | Tree RCU가 줄이는 것은 읽는 쪽의 공유 락 경쟁이다. 쓰기 측의 직렬화, 새 객체 복사, 유예 기간 추적, 이전 객체를 보관하는 메모리 비용은 남는다. 읽기가 많고 일정 시간 이전 버전을 관찰해도 되는 구조에 특히 잘 맞는다. 쓰기가 잦거나 읽기 구간이 길면 회수 지연이 커지므로 뮤텍스 방식과 비용을 비교해야 한다. | ||
x86-64와 RISC-V RV64에서 이 트리와 태스크 추적의 의미는 같다. 아키텍처별 원자 | x86-64와 RISC-V RV64에서 이 트리와 태스크 추적의 의미는 같다. 아키텍처별 원자 연산, 장벽이 그 아래의 순서를 구현한다. 사용자 공간 RCU는 별도의 라이브러리와 실행 환경을 사용한다. | ||
== 참고 문헌 == | == 참고 문헌 == | ||
| 79번째 줄: | 79번째 줄: | ||
{{이전 다음 문서 | {{이전 다음 문서 | ||
|이전= | |이전=<- 이전 문서<br>[[운영체제 기본/Linux/RCU/갱신과 메모리 회수|갱신과 메모리 회수]] | ||
|목차=[[운영체제 기본/Linux/RCU|RCU 목차]] | |목차=[[운영체제 기본/Linux/RCU|RCU 목차]] | ||
|다음=마지막 문서 | |다음=마지막 문서 | ||