읽기-복사-업데이트

Read-copy-update

컴퓨터 과학에서 RCU(Read-Copy-Update)는 포인터를 통해 링크되고 공유 데이터 구조(예: 링크 목록, 트리, 해시 테이블)[1]에 속하는 요소를 여러 스레드가 동시에 읽고 업데이트하는 동안 잠금 프리미티브의 사용을 피하는 동기화 메커니즘입니다.

스레드가 공유 메모리에 데이터 구조의 요소를 삽입 또는 삭제할 때마다 모든 리더가 이전 구조 또는 새 구조 중 하나를 확인하고 통과할 수 있으므로 불일치(예: 참조 늘 포인터)[1]를 방지할 수 있습니다.

읽기 성능이 중요한 경우에 사용되며 공간 대 시간 균형을 유지하는 한 예로서, 더 많은 공간을 희생하면서 빠른 운영을 가능하게 합니다.이것에 의해, 모든 리더는 동기화가 필요 없는 것처럼 처리되기 때문에, 고속이 됩니다만, 갱신은 한층 더 어려워집니다.

이름 및 개요

이 이름은 RCU를 사용하여 링크된 구조를 업데이트하는 방식에서 유래했습니다.이 작업을 수행하는 스레드는 다음 단계를 사용합니다.

  • 새로운 구조를 만듭니다.
  • 이전 구조에서 새 구조로 데이터를 복사하고 이전 구조로의 포인터를 저장합니다.
  • 새, 복사, 구조 수정,
  • 새 구조를 참조하도록 글로벌 포인터를 업데이트합니다.
  • sleeve는 운영체제 커널이 예를 들어 Linux 커널에서 를 사용하여 오래된 구조를 사용하는 리더가 남아 있지 않다고 판단할 때까지 실행됩니다.synchronize_rcugs
  • 커널에 의해 웨이크업되면 오래된 구조의 할당을 해제합니다.

따라서 업데이트를 수행하기 위해 스레드 복사와 동시에 구조가 읽히므로 "read-copy update"라는 이름이 붙습니다."RCU"라는 약어는 Linux 커뮤니티에 의한 많은 공헌 중 하나였습니다.VM/XA 프로그래머에 의한 패시브시리얼라이제이션과 MP 지연, K42 및 Toenado 프로그래머에 의한 세대 등이 유사한 기술에 해당합니다.

상세설명

Read-copy-update 삽입 순서.스레드는 3개의 필드로 구조를 할당한 후 이 구조를 가리키도록 글로벌 포인터 gptr을 설정합니다.

RCU의 주요 속성은 데이터 구조가 갱신 중인 경우에도 리더가 데이터 구조에 액세스할 수 있다는 것입니다.RCU 업데이트 프로그램은 리더를 차단하거나 강제로 접근을 재시도할 수 없습니다.이 개요는 동시 판독기에도 불구하고 링크된 구조에 데이터를 안전하게 삽입하고 삭제할 수 있는 방법을 보여 주는 것으로 시작합니다.오른쪽 첫 번째 그림은 시간이 왼쪽에서 오른쪽으로 진행되는 4가지 상태 삽입 절차를 보여 줍니다.

첫 번째 상태에는 gptr이라는 이름의 글로벌포인터가 표시됩니다.이 포인터는 처음에는 NULL이며, 빨간색으로 표시되어 리더가 언제든지 액세스할 수 있음을 나타냅니다.따라서 업데이트 프로그램의 주의가 필요합니다.새로운 구조에 메모리를 할당하면, 제2의 상태로 이행합니다.이 구조체는 미확정 상태(물음표로 표시)를 가지지만, 판독자가 액세스할 수 없습니다(녹색으로 표시).이 구조는 독자가 접근할 수 없기 때문에 업데이트 프로그램은 동시 독자를 방해하지 않고 원하는 작업을 수행할 수 있습니다.이 새 구조체를 초기화하면 구조체 필드의 초기화된 값을 보여주는 세 번째 상태로 전환됩니다.이 새로운 구조에 대한 참조를 gptr에 할당하면 네 번째 및 마지막 상태로 이행합니다.이 상태에서는, 독자가 구조에 액세스 할 수 있기 때문에, 빨간색으로 표시됩니다.rcu_assign_pointer 프리미티브는 이 할당을 실행하기 위해 사용되며 동시 판독기는 NULL 포인터 또는 새로운 구조에 대한 유효한 포인터를 볼 수 있지만 두 값의 일부 매시업은 볼 수 없다는 점에서 할당이 원자성이라는 것을 보증합니다.rcu_assign_pointer의 추가 속성에 대해서는 이 문서의 뒷부분에서 설명합니다.

읽기-복사-업데이트 삭제 절차

이 절차에서는 리더가 삽입 전, 삽입 중 및 삽입 후에 동시에 데이터 구조를 통과하는 경우에도 링크된 데이터 구조에 새로운 데이터를 삽입하는 방법을 보여 줍니다.오른쪽의 두 번째 그림은 시간이 왼쪽에서 오른쪽으로 이동하는 4가지 상태 삭제 절차를 보여 줍니다.

첫 번째 상태에는 A, B 및 C 요소를 포함하는 링크 목록이 표시됩니다.3가지 요소는 모두 빨간색으로 표시되어 있어 RCU 리더가 언제든지 참조할 수 있습니다.list_del_rcu를 사용하여 이 목록에서 요소 B를 삭제하면 두 번째 상태로 이행합니다.요소 B에서 C로의 링크는 현재 참조하고 있는 요소 B가 목록의 나머지 부분을 통과할 수 있도록 그대로 유지됩니다.요소 A에서 링크에 액세스하는 리더는 요소 B 또는 요소 C에 대한 참조를 얻지만, 어느 쪽이든 각 리더는 유효한 올바른 형식의 링크 목록을 볼 수 있습니다.요소 B는 기존 리더가 요소 B에 대한 참조가 있을 수 있지만 새 리더는 참조를 얻을 방법이 없음을 나타내기 위해 노란색으로 표시됩니다.판독기 대기 조작은 세 번째 상태로 이행합니다.이 판독기 대기 작업은 기존 판독기를 대기하기만 하면 되고 새 판독기는 대기하지 않아야 합니다.요소 B는 이제 녹색으로 표시되어 독자가 참조할 수 없음을 나타냅니다.따라서 이제 업데이트 프로그램은 요소 B를 해방시켜 네 번째 및 마지막 상태로 이행하는 것이 안전합니다.

두 번째 상태에서는 요소 B의 유무에 관계없이 서로 다른 독자들이 목록의 두 가지 다른 버전을 볼 수 있다는 것을 반복하는 것이 중요합니다.즉, RCU는 공간(목록의 다른 버전)과 시간(삭제 절차의 다른 상태)에서의 조정을 제공합니다.이는 공간이 아닌 시간에 조정되는 잠금이나 트랜잭션과 같은 기존 동기화 기본 요소와 크게 대조됩니다.

이 절차에서는 리더가 삭제 전, 삭제 중 및 삭제 후에 동시에 데이터 구조를 통과하는 경우에도 링크된 데이터 구조에서 오래된 데이터를 얼마나 제거할 수 있는지를 보여 줍니다.삽입 및 삭제 시 RCU를 사용하여 다양한 데이터 구조를 구현할 수 있습니다.

RCU의 리더는 보통 rcu_read_lock과 rcu_read_unlock으로 구분되는 읽기측 크리티컬섹션 내에서 실행됩니다.RCU 읽기 측 임계 섹션 내에 없는 문은 대기 상태라고 하며, 이러한 문장은 RCU로 보호된 데이터 구조에 대한 참조를 유지하는 것이 허용되지 않으며, 대기 상태의 스레드를 대기하기 위해 판독기 대기 동작도 필요하지 않습니다.각 스레드가 적어도 한 번 대기 상태에 있는 기간을 유예 기간이라고 합니다.정의상 소정의 유예기간 시작 시에 존재하는 RCU 읽기측 크리티컬섹션은 유예기간 종료 전에 완료해야 합니다.이는 RCU가 제공하는 기본적인 보증이 됩니다.또, 판독기 대기 동작은 적어도1개의 유예기간이 경과할 때까지 대기해야 합니다.이 보증은 극히 적은 읽기 측 오버헤드로 실현될 수 있습니다.실제로 서버 클래스의 Linux 커널 빌드에 의해 실현되는 제한적인 경우 읽기 측 오버헤드는 정확히 [2]제로입니다.

RCU의 기본 보증은 업데이트를 제거 및 회수 단계로 분할하여 사용할 수 있습니다.삭제 단계에서는 데이터 구조 내의 데이터 항목에 대한 참조를 제거하고(이러한 데이터 항목의 새 버전에 대한 참조로 대체하여), RCU 읽기 측 중요 섹션과 동시에 실행할 수 있습니다.삭제 단계를 RCU 리더와 동시에 실행하는 것이 안전한 이유는 최신 CPU의 의미론에서 리더가 부분적으로 갱신된 참조가 아닌 데이터 구조의 이전 버전 또는 새 버전을 볼 수 있음을 보증하기 때문입니다.유예기간이 경과하면 이전 버전을 참조하는 리더가 없어지므로 회수 단계에서는 이전 [3]버전을 구성하는 데이터 항목을 해방(재청구)하는 것이 안전합니다.

업데이트를 제거 및 회수 단계로 분할하면 업데이트 프로그램이 즉시 제거 단계를 수행하고 제거 단계에서 활성 상태인 모든 판독기가 완료될 때까지, 즉 유예 기간이 [note 1]경과할 때까지 회수 단계를 연기할 수 있습니다.

따라서 일반적인 RCU 업데이트시퀀스는 다음과 같습니다.[4]

  1. RCU로 보호된 데이터 구조에 액세스하는 모든 판독기가 RCU 읽기 측 중요 섹션 내에서 참조를 수행하는지 확인하십시오.
  2. 데이터 구조에 대한 포인터를 제거하여 이후 독서자가 데이터 구조에 대한 참조를 얻을 수 없도록 합니다.
  3. 모든 이전 리더(이전 단계에서 제거된 데이터 구조에 대한 포인터가 있을 수 있음)가 RCU 읽기 측 중요 섹션을 완료하도록 유예 기간이 경과할 때까지 기다립니다.
  4. 이 시점에서는 데이터 구조에 대한 참조를 보유하고 있는 판독기가 있을 수 없으므로, 이제 데이터 구조를 안전하게 회수할 수 있습니다(예: 자유).[note 2]

위의 절차(이전 다이어그램과 일치)에서는 업데이트 프로그램이 제거 및 회수 단계를 모두 수행하지만 완전히 다른 스레드가 회수하는 데 도움이 되는 경우가 많습니다.참조 카운트를 사용하여 리더가 제거를 수행할 수 있으므로 동일한 스레드가 업데이트 단계(상기 (2))와 회수 단계(4)를 모두 수행하더라도 종종 이들을 별도로 생각하는 것이 도움이 됩니다.

RCU는 공유 데이터 구조에서 가장 일반적인 논블로킹 알고리즘입니다.RCU는 모든 수의 리더에 대해 완전히 대기하고 있지 않습니다.싱글 라이터의 실장 RCU도,[5] 라이터에게는 록 프리입니다.RCU의 일부 멀티 라이터 실장은 잠금 프리입니다.[6]RCU 의 다른 멀티 라이터 실장에서는,[7] 록을 사용해 라이터를 시리얼화합니다.

사용하다

2008년 초까지 Linux 커널[8] 내에서 네트워킹 프로토콜[9] 스택과 메모리 관리 [10]시스템을 포함하여 거의 2,000개의 RCU API가 사용되었습니다.2014년 3월 현재 9,000회 이상 [11]사용되었습니다.2006년 이후 연구자들은 동적 [12]분석에 사용되는 메타데이터 관리, 클러스터된 [13]객체의 수명 관리, K42 연구 운영 [14][15]체제에서의 객체 수명 관리, 소프트웨어 트랜잭션 메모리 [16][17]구현 최적화 등 많은 문제에 RCU와 유사한 기술을 적용했습니다.Dragonfly BSD는 Linux의 Sleepable RCU(SRCU) 구현과 가장 유사한 기술을 사용합니다.

장점과 단점

모든 리더가 완료될 때까지 기다릴 수 있기 때문에 RCU 리더는 훨씬 가벼운 동기화를 사용할 수 있습니다.경우에 따라서는 동기화가 전혀 이루어지지 않을 수도 있습니다.이와는 대조적으로 기존의 잠금 기반 방식에서는 업데이트 프로그램이 데이터 구조를 삭제하지 않도록 읽기 프로그램이 중량 동기화를 사용해야 합니다.그 이유는 잠금 기반 업데이트 프로그램은 일반적으로 제자리에 있는 데이터를 업데이트하므로 판독기를 제외해야 하기 때문입니다.이와는 대조적으로 RCU 기반 업데이트 프로그램에서는 일반적으로 단일 정렬 포인터에 대한 쓰기가 최신 CPU에서 원자적으로 이루어지기 때문에 판독기를 중단하지 않고 링크된 구조에서 데이터를 원자적으로 삽입, 제거 및 교체할 수 있습니다.동시 RCU 리더는 이전 버전에 계속 액세스할 수 있으며, 잠금 [18][19]경합이 없는 경우에도 최신 SMP 컴퓨터 시스템에서 매우 비싼 원자적인 읽기-수정-쓰기 명령, 메모리 장벽 및 캐시 누락이 필요하지 않습니다.RCU의 읽기측 프리미티브의 경량성은 뛰어난 퍼포먼스, 확장성, 실시간 응답성을 넘어 추가적인 이점을 제공합니다.예를 들어, 대부분의 교착 상태 및 라이브 잠금 [note 3]상태에 대한 내성을 제공합니다.

물론 RCU에도 단점이 있습니다.예를 들어 RCU는 대부분 읽기와 업데이트가 적은 상황에서 가장 잘 작동하지만 업데이트 전용 워크로드에는 적용되지 않는 경우가 많습니다.예를 들어, RCU 리더와 업데이트 프로그램이 동시에 실행될 수 있다는 사실이 RCU의 읽기 측 프리미티브의 경량성을 가능하게 하지만, 일부 알고리즘은 읽기/업데이트 동시성을 수용할 수 없을 수 있습니다.

RCU에 대한 10년 이상의 경험에도 불구하고, RCU의 정확한 적용 범위는 여전히 연구 주제입니다.

특허

이 기술은 1995년 8월 15일 발행된 미국 소프트웨어 특허 5,442,758 및 Sequent Computer Systems에 할당되어 있으며 미국 특허 5,608,893(2009-03-30 만료), 미국 특허 5,727,205-209(2010 만료)에도 적용됩니다.현재 만료된 미국 특허 4,809,168은 밀접하게 관련된 기술을 다루고 있습니다.RCU는 또한 SCO 대 IBM 소송의 한 가지 주장의 주제이기도 합니다.

샘플 RCU 인터페이스

RCU는 많은 운영 체제에서 사용할 수 있으며 2002년 10월에 Linux 커널에 추가되었습니다.liburcu와 같은 사용자 수준의 구현도 사용할 [20]수 있습니다.

Linux 커널 버전 2.6에서의 RCU 실장은 잘 알려진 RCU 실장 중 하나입니다.이 문서의 후반부에서 RCU API의 힌트로 사용됩니다.핵심 API(Application Programming Interface)는 매우 [21]작습니다.

  • rcu_read_lock(): 중요한 섹션의 전체 기간 동안 회수되지 않도록 RCU로 보호된 데이터 구조를 표시합니다.
  • rcu_read_unlock(): 리더가 RCU 읽기 측 크리티컬섹션을 종료하고 있음을 리더가 회수자에게 통지하기 위해 사용합니다.RCU 판독측 크리티컬섹션은 중첩되거나 중복될 수 있습니다.
  • synchronize_rcu(): 모든 CPU의 기존 RCU 읽기 측 크리티컬섹션이 모두 완료될 때까지 차단합니다.주의:synchronize_rcu는, 다음의 RCU 판독측의 중요한 섹션이 완료될 때까지 기다릴 필요는 없습니다.예를 들어, 다음과 같은 일련의 이벤트를 생각해 보겠습니다.
CPU 0 CPU 1 CPU 2 ----------------------------------------------------------------------------------------------------------------------------------------------------- 1. rcu_read_lock() 2. synchrcu() 3. rcu_read_lock()를 입력합니다. rcu_lock() 4. rcu_unlock().rcu_read_model()
부터synchronize_rcu는 리더가 언제 완료되었는지 파악해야 하는 API이며, 그 실장은 RCU의 핵심입니다.RCU가 가장 읽기 집약적인 상황을 제외한 모든 상황에서 유용하게 쓰이려면synchronize_rcu님의 오버헤드도 꽤 작아야 합니다.
또는 synchronize_rcu는 블로킹 대신 진행 중인 모든 RCU 읽기 측 크리티컬섹션이 완료된 후에 호출되는 콜백을 등록할 수 있습니다.이 콜백 배리언트는call_rcuLinux 커널에 있습니다.
  • rcu_syslog_syslog():업데이트 프로그램은 이 기능을 사용하여 업데이트 프로그램의 값 변화를 판독기에 안전하게 전달하기 위해 RCU로 보호된 포인터에 새 값을 할당합니다.이 함수는 새로운 값을 반환하고 지정된 CPU 아키텍처에 필요한 메모리 장벽 명령도 실행합니다.아마도 더 중요한 것은 어떤 포인터가 RCU에 의해 보호되고 있는지를 문서화하는 것입니다.
  • rcu_dereference():독자는 다음을 사용합니다.rcu_dereferenceRCU로 보호된 포인터를 가져오면 안전하게 참조될 수 있는 값이 반환됩니다.또한 컴파일러 또는 CPU가 요구하는 명령어(gcc의 휘발성 캐스트, C/C++11의 memory_order_consume 부하, 오래된 DEC Alpha CPU가 요구하는 메모리 장벽 명령 등)도 실행합니다.에 의해 반환된 값rcu_dereference는 동봉된 RCU 읽기 측 크리티컬섹션 내에서만 유효합니다.와 마찬가지로rcu_assign_pointer, 의 중요한 기능rcu_dereference는 RCU에 의해 보호되는 포인터를 문서화하는 것입니다.
판독기, 업데이트 프로그램 및 회수기 간의 RCU API 통신

오른쪽 그림은 각 API가 판독기, 업데이트 프로그램 및 회수기 간에 통신하는 방법을 보여 줍니다.

RCU 인프라스트럭처는, 다음의 타임 시퀀스를 감시합니다.rcu_read_lock,rcu_read_unlock,synchronize_rcu,그리고.call_rcu(1)의 타이밍을 결정하기 위한 호출synchronize_rcu호출은 발신자에게 반환될 수 있으며 (2)call_rcu콜백이 호출될 수 있습니다.RCU 인프라스트럭처를 효율적으로 구현하면 대응하는 API의 많은 사용에서 오버헤드를 상각하기 위해 배치 처리가 많이 사용됩니다.

심플한 구현

RCU에는 RCU에 대한 이해를 돕기 위한 매우 단순한 '장난감' 구현이 있습니다.이 섹션에서는 비선제적인 [22]환경에서 작동하는 그런 '장난감' 구현 중 하나를 설명합니다. 

무효 rcu_read_lock(무효) { }  무효 rcu_read_module(무효) { }  무효 call_rcu(무효 (*콜백) (무효 *), 무효 *arg) {     // 목록에 콜백/콜백 쌍 추가 }  무효 synchronize_rcu(무효) {     인트 CPU, ncpus = 0;      위해서 각_cpu(CPU)         schedule_current_task_to(CPU);      위해서 각각 엔트리 에 그 call_rcu 목록.         엔트리->콜백 (엔트리->arg); }

코드 샘플에서는rcu_assign_pointer그리고.rcu_dereference크게 놓치지 않고 무시할 수 있습니다.단, 유해한 컴파일러 최적화를 억제하고 CPU의 액세스 순서를 변경하지 않도록 하기 위해 필요합니다. 

#syslog rcu_syslog_syslog(p, v)({\) smp_wmb();/* 이전 글을 주문합니다.*/\ ACCESS_ONCE(p) = (v); \ })  #syslog rcu_dereference(p) type of(p) _value = ACCESS_ONCE(p); \ smp_read_smp_smp();/* 대부분의 아키텍처에서 제외 */\ (_값); \ })

주의:rcu_read_lock그리고.rcu_read_unlock아무것도 하지 않다이것이 비선점 커널에서의 클래식 RCU의 큰 장점입니다.읽기측 오버헤드는 정확하게 제로입니다.smp_read_barrier_depends()는 DEC Alpha CPU를 [23][failed verification]제외한 모든 CPU에서 빈 매크로이며 최신 CPU에서는 이러한 메모리 장벽이 필요하지 않습니다.그ACCESS_ONCE()매크로란 대부분의 경우 추가 코드를 생성하지 않는 휘발성 캐스트입니다.그리고 절대 그럴 리가 없다.rcu_read_lock는 교착 사이클에 참여하거나 실시간프로세스가 스케줄링 마감을 놓치거나 priority 반전을 촉진하거나 높은 잠금컨텐션을 일으킬 수 있습니다.그러나 이 완구 RCU 구현에서 RCU 읽기 측 임계 섹션 내에서 차단하는 것은 순수한 스핀록을 유지하는 동안 차단하는 것과 마찬가지로 불법입니다.

의 실장synchronize_rcu는 synchronize_cpu의 발신자를 각 CPU로 이동시켜 모든 CPU가 컨텍스트스위치를 실행할 수 있을 때까지 차단합니다.이것은 비선제적인 환경이며, RCU 읽기측 크리티컬섹션 내의 블로킹은 불법입니다.이는 RCU 읽기측 크리티컬섹션 내에 프리엠프션포인트가 존재하지 않음을 의미합니다.따라서 특정 CPU가 컨텍스트스위치를 실행하고 있는 경우(다른 프로세스를 스케줄 할 경우), 이 CPU는 이전의 모든 RCU 읽기 측 크리티컬섹션을 완료해야 합니다.모든 CPU가 콘텍스트스위치를 실행하면 앞의 모든 RCU 읽기측 크리티컬섹션이 완료됩니다.

리더-라이터 잠금과 유사

RCU는 다양한 방법으로 사용할 수 있지만, 매우 일반적인 용도는 리더 라이터 잠금과 유사합니다.다음 코드 나란히 표시는 리더 라이터 잠금과 RCU가 얼마나 [24]밀접하게 관련되어 있는지를 보여줍니다. 

   /* 리더 라이터 잠금 */              /* RCU */   1 구조 엘 {                            1 구조 엘 {  2   구조 list_head lp;                 2   구조 list_head lp;  3   긴 열쇠;                            3   긴 열쇠;  4   스핀록 뮤텍스;                    4   스핀록 뮤텍스;  5   인트 데이터.;                            5   인트 데이터.;  6   /* 기타 데이터 필드 */              6   /* 기타 데이터 필드 */  7 };                                     7 };  8 정의_RWLOCK(리스트 뮤텍스);              8 정의_SPINLOCK(리스트 뮤텍스);  9 리스트_헤드(머리);                       9 리스트_헤드(머리);   1 인트 서치(긴 열쇠, 인트 *결과)      1 인트 서치(긴 열쇠, 인트 *결과)  2 {                                      2 {  3   구조 엘 *p;                        3   구조 엘 *p;  4                                        4  5   읽기_잠금(&리스트 뮤텍스);               5   rcu_read_lock();  6   목록_각 엔트리(p, &머리, lp) {  6   list_for_each_entry_rcu(p, &머리, lp) {  7     한다면 (p->열쇠 == 열쇠) {               7     한다면 (p->열쇠 == 열쇠) {  8       *결과 = p->데이터.;               8       *결과 = p->데이터.;  9       읽기_실행(&리스트 뮤텍스);         9       rcu_read_module(); 10       돌아가다 1;                       10       돌아가다 1; 11     }                                 11     } 12   }                                   12   } 13   읽기_실행(&리스트 뮤텍스);            13   rcu_read_module(); 14   돌아가다 0;                           14   돌아가다 0; 15 }                                     15 }   1 인트 삭제하다(긴 열쇠)                   1 인트 삭제하다(긴 열쇠)  2 {                                      2 {  3   구조 엘 *p;                        3   구조 엘 *p;  4                                        4  5   write_lock(&리스트 뮤텍스);              5   spin_lock(&리스트 뮤텍스);  6   목록_각 엔트리(p, &머리, lp) {  6   목록_각 엔트리(p, &머리, lp) {  7     한다면 (p->열쇠 == 열쇠) {               7     한다면 (p->열쇠 == 열쇠) {  8       list_del(&p->lp);                8       list_del_rcu(&p->lp);  9       write_filename(쓰기)_filename(필수)(&리스트 뮤텍스);        9       spin_interface(&리스트 뮤텍스);                                          10       synchronize_rcu(); 10       kfree(p);                       11       kfree(p); 11       돌아가다 1;                       12       돌아가다 1; 12     }                                 13     } 13   }                                   14   } 14   write_filename(쓰기)_filename(필수)(&리스트 뮤텍스);           15   spin_interface(&리스트 뮤텍스); 15   돌아가다 0;                           16   돌아가다 0; 16 }                                     17 }

두 접근법 간의 차이는 매우 작습니다.읽기 측 잠금 이동 위치rcu_read_lock그리고.rcu_read_unlock업데이트 측 잠금이 리더 라이터 잠금에서 단순한 스핀 잠금으로 이동하며,synchronize_rcu의 선두에 있습니다.kfree.

단, 잠재적인 단점이 하나 있습니다.읽기 측과 업데이트 측 중요 섹션을 동시에 실행할 수 있습니다.많은 경우, 이것은 문제가 되지 않습니다만, 어쨌든 주의 깊게 확인할 필요가 있습니다.예를 들어, 복수의 독립된 리스트업데이트를 1개의 아토믹업데이트로 간주할 필요가 있는 경우, RCU 로의 변환에는 특별한 주의가 필요합니다.

또, 의 존재는synchronize_rcu의 RCU 버전이delete차단할 수 있게 되었습니다.이게 문제라면call_rcu와 같이 사용할 수 있다call_rcu (kfree, p)대신해서synchronize_rcu이는 참조 카운트와 조합하여 특히 유용합니다.

역사

RCU와 유사한 기술과 메커니즘은 여러 번 독립적으로 [25]개발되었습니다.

  1. H.T. 쿵과 Q.리먼은 2진수 검색 트리에 [26]대한 RCU와 같은 접근을 구현하기 위해 가비지 컬렉터를 사용하는 것에 대해 설명했다.
  2. Udi Manber와 Richard Ladner는 제거 시 실행되는 모든 스레드가 종료될 때까지 매립을 연기함으로써 Kung과 Lehman의 작업을 쓰레기가 수집되지 않은 환경으로 확장했습니다. 이 스레드는 수명이 긴 [27]스레드가 없는 환경에서 작동합니다.
  3. Richard Rashid 등에서는 모든 CPU가 TLB를 플래시할 때까지 가상 주소 공간의 재확보를 지연시키는 저속한 TLB(Translation Lookaside Buffer) 구현에 대해 설명했습니다.이것은 일부 RCU [28]구현과 같은 정신입니다.
  4. 제임스 P.헤네시, 데미안 L.Osisek, 및 Joseph W. Seigh, II는 1989년에 미국 특허 4,809,168을 취득했습니다(실패한 이후).이 특허는 IBM 메인프레임의 [29]VM/XA에서 사용된 것으로 보이는 RCU와 유사한 메커니즘을 설명합니다.
  5. William Pugh는 RCU와 같은 메커니즘을 설명했는데,[30] 이는 독자의 명시적인 플래그 설정에 의존했습니다.
  6. Aju John은 RCU와 같은 구현을 제안했습니다.업데이트는 단순히 정해진 시간 동안 대기하며, 이는 독자들이 모두 정해진 시간 내에 완료한다는 가정 하에, 어려운 실시간 [31]시스템에서 적절할 수 있습니다.밴 제이콥슨은 1993년에 비슷한 계획을 제안했다.
  7. J. Slingwine과 P. E. McKenney는 1995년 8월에 미국 특허 5,442,758을 취득했습니다.이것에 의해, RCU는 DYNIX/ptx에 실장되어 나중에 Linux [32]커널에 실장되어 있는 것을 기술하고 있습니다.
  8. B. Gamsa, O. Krieger, J. Appavoo, M.Stumm은 토론토 대학 토네이도 연구 운영 체제와 밀접하게 관련된 IBM Research K42 연구 운영 [33]체제에서 사용되는 RCU와 유사한 메커니즘을 설명했습니다.
  9. Rusty Russell과 Phil Rumpf는 Linux 커널 [34][35]모듈의 언로드 처리를 위한 RCU와 같은 기술을 설명했습니다.
  10. D. Sarma는 2002년 10월에 Linux 커널 버전 2.5.43에 RCU를 추가했습니다.
  11. Robert Colvin 등은 RCU와 [36]유사한 게으른 동시 목록 기반 집합 알고리즘을 공식적으로 검증했다.
  12. M. Desnoyers 등은 사용자 공간 [37][38]RCU에 대한 설명을 발표했다.
  13. A. Gotsman 등은 분리 [39]논리에 기초한 RCU의 형식적 의미론을 도출했다.
  14. Ilan Frenkel, Roman Geller, Yoram Ramberg, Yoram Snir는 2006년에 미국 특허 709만9932건을 취득했습니다.이 특허는 읽기/쓰기 일관성을 강화하고 읽기/쓰기 [40]동시성을 가능하게 하는 디렉토리 서비스를 사용하여 서비스 품질 정책 관리 정보를 검색 및 저장하기 위한 RCU와 같은 메커니즘에 대해 설명합니다.

「 」를 참조해 주세요.

메모들

  1. ^ 제거 단계 이후에 시작하는 판독기는 제거된 데이터 항목에 대한 참조를 얻을 수 없기 때문에 제거 단계 중에 활성 상태인 판독기만 고려하면 됩니다.
  2. ^ 가능한 경우 가비지 컬렉터를 사용하여 이 단계를 수행할 수 있습니다.
  3. ^ 예를 들어 RCU 읽기 측 크리티컬섹션 내에서 유예기간이 완료될 때까지 차단하는 스테이트먼트를 실행함으로써 RCU 기반의 데드록도 가능합니다.

레퍼런스

  1. ^ a b Tanenbaum, Andrew (2015). Modern Operating Systems (4th ed.). USA: Pearson. p. 148. ISBN 9781292061429.
  2. ^ Guniguntala, Dinakar; McKenney, Paul E.; Triplett, Joshua; Walpole, Jonathan (April–June 2008). "The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with Linux". IBM Systems Journal. 47 (2): 221–236. doi:10.1147/sj.472.0221.
  3. ^ McKenney, Paul E.; Walpole, Jonathan (December 17, 2007). "What is RCU, Fundamentally?". Linux Weekly News. Retrieved September 24, 2010.
  4. ^ McKenney, Paul E.; Slingwine, John D. (October 1998). Read-Copy Update: Using Execution History to Solve Concurrency Problems (PDF). Parallel and Distributed Computing and Systems. pp. 509–518. {{cite conference}}:외부 링크 journal=(도움말)
  5. ^ Naama Ben-David, Guy E. Belloch, Yihan Sun, Yuanhao Wei."효율적인 싱글 라이터 동시성"
  6. ^ "원자 연산을 통한 잠금 없는 멀티스레딩"
  7. ^ 에디 콜러."Read-Copy Update 관련 참고사항"을 참조하십시오.인용: "기입과 기입의 경합을 관리하기 위해 대부분의 RCU 데이터 구조에서는 일반 잠금을 사용합니다."
  8. ^ McKenney, Paul E.; Walpole, Jonathan (July 2008). "Introducing technology into the Linux kernel: a case study". SIGOPS Oper. Syst. Rev. 42 (5): 4–17. doi:10.1145/1400097.1400099.
  9. ^ Olsson, Robert; Nilsson, Stefan (May 2007). TRASH: A dynamic LC-trie and hash table structure. Workshop on High Performance Switching and Routing (HPSR'07). doi:10.1109/HPSR.2007.4281239.
  10. ^ Piggin, Nick (July 2006). A Lockless Pagecache in Linux---Introduction, Progress, Performance. Ottawa Linux Symposium.
  11. ^ "Paul E. McKenney: RCU Linux Usage".
  12. ^ Kannan, Hari (2009). "Ordering decoupled metadata accesses in multiprocessors". Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture - Micro-42. p. 381. doi:10.1145/1669112.1669161. ISBN 978-1-60558-798-1.
  13. ^ Matthews, Chris; Coady, Yvonne; Appavoo, Jonathan (2009). Portability events: a programming model for scalable system infrastructures. PLOS '06: Proceedings of the 3rd Workshop on Programming Languages and Operating Systems. San Jose, CA, USA. doi:10.1145/1215995.1216006. ISBN 978-1-59593-577-9.
  14. ^ Da Silva, Dilma; Krieger, Orran; Wisniewski, Robert W.; Waterland, Amos; Tam, David; Baumann, Andrew (April 2006). "K42: an infrastructure for operating system research". SIGOPS Oper. Syst. Rev. 40 (2): 34–42. doi:10.1145/1131322.1131333.
  15. ^ Appavoo, Jonathan; Da Silva, Dilma; Krieger, Orran; Auslander, Mark; Ostrowski, Michal; Rosenburg, Bryan; Waterland, Amos; Wisniewski, Robert W.; Xenidis, Jimi (August 2007). "Experience distributing objects in an SMMP OS". ACM Transactions on Computer Systems. 25 (3): 6/1–6/52. doi:10.1145/1275517.1275518.
  16. ^ Fraser, Keir; Harris, Tim (2007). "Concurrent programming without locks". ACM Transactions on Computer Systems. 25 (2): 34–42. CiteSeerX 10.1.1.532.5050. doi:10.1145/1233307.1233309.
  17. ^ Porter, Donald E.; Hofmann, Owen S.; Rossbach, Christopher J.; Benn, Alexander; Witchel, Emmett (2009). "Operating systems transactions". Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles - SOSP '09. p. 161. doi:10.1145/1629575.1629591. ISBN 978-1-60558-752-3.
  18. ^ Hart, Thomas E.; McKenney, Paul E.; Demke Brown, Angela; Walpole, Jonathan (December 2007). "Performance of memory reclamation for lockless synchronization". J. Parallel Distrib. Comput. 67 (12): 1270–1285. doi:10.1016/j.jpdc.2007.04.010.
  19. ^ McKenney, Paul E. (January 4, 2008). "RCU part 2: Usage". Linux Weekly News. Retrieved September 24, 2010.
  20. ^ Desnoyers, Mathieu (December 2009). Low-Impact Operating System Tracing (PDF). École Polytechnique de Montreal (Thesis).
  21. ^ McKenney, Paul E. (January 17, 2008). "RCU part 3: the RCU API". Linux Weekly News. Retrieved September 24, 2010.
  22. ^ McKenney, Paul E.; Appavoo, Jonathan; Kleen, Andi; Krieger, Orran; Russell, Rusty; Sarma, Dipankar; Soni, Maneesh (July 2001). Read-Copy Update (PDF). Ottawa Linux Symposium.
  23. ^ Wizard, The (August 2001). "Shared Memory, Threads, Interprocess Communication". Hewlett-Packard. Retrieved December 26, 2010.
  24. ^ McKenney, Paul E. (October 2003). "Using {RCU} in the {Linux} 2.5 Kernel". Linux Journal. Retrieved September 24, 2010.
  25. ^ McKenney, Paul E. (July 2004). Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques (PDF). OGI School of Science and Engineering at Oregon Health and Sciences University (Thesis).
  26. ^ Kung, H. T.; Lehman, Q. (September 1980). "Concurrent Maintenance of Binary Search Trees". ACM Transactions on Database Systems. 5 (3): 354. CiteSeerX 10.1.1.639.8357. doi:10.1145/320613.320619.
  27. ^ Manber, Udi; Ladner, Richard E. (September 1984). "Concurrency Control in a Dynamic Search Structure". ACM Transactions on Database Systems. 9 (3).
  28. ^ Rashid, Richard; Tevanian, Avadis; Young, Michael; Golub, David; Baron, Robert; Bolosky, William; Chew, Jonathan (October 1987). Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures (PDF). Second Symposium on Architectural Support for Programming Languages and Operating Systems. Association for Computing Machinery.
  29. ^ US 4809168, 헤네시, 제임스 P.Osisek, Damian L. & Seigh II, Joseph W., "멀티태스킹 환경에서 패시브 시리얼라이제이션" 1989년 2월 발행
  30. ^ Pugh, William (June 1990). Concurrent Maintenance of Skip Lists (Technical report). Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland. CS-TR-2222.1.
  31. ^ John, Aju (January 1995). Dynamic vnodes — design and implementation. USENIX Winter 1995.
  32. ^ US 5442758, Slingwine, John D. & McKenney, Paul E., "멀티프로세서 시스템에서의 오버헤드 상호 배제 감소 및 일관성 유지를 위한 부속서 및 방법" 1995년 8월 발행
  33. ^ Gamsa, Ben; Krieger, Orran; Appavoo, Jonathan; Stumm, Michael (February 1999). Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System (PDF). Proceedings of the Third Symposium on Operating System Design and Implementation.
  34. ^ Russell, Rusty (June 2000). "Re: modular net drivers".
  35. ^ Russell, Rusty (June 2000). "Re: modular net drivers".
  36. ^ Colvin, Robert; Groves, Lindsay; Luchangco, Victor; Moir, Mark (August 2006). Formal Verification of a Lazy Concurrent List-Based Set Algorithm (PDF). Computer Aided Verification. Archived from the original (PDF) on 2009-07-17.
  37. ^ Desnoyers, Mathieu; McKenney, Paul E.; Stern, Alan; Dagenais, Michel R.; Walpole, Jonathan (February 2012). User-Level Implementations of Read-Copy Update (PDF). IEEE Transactions on Parallel and Distributed Systems. doi:10.1109/TPDS.2011.159.
  38. ^ McKenney, Paul E.; Desnoyers, Mathieu; Jiangshan, Lai (November 13, 2013). "User-space RCU". Linux Weekly News. Retrieved November 17, 2013.
  39. ^ Gotsman, Alexey; Rinetzky, Noam; Yang, Hongseok (March 16–24, 2013). Verifying concurrent memory reclamation algorithms with grace (PDF). ESOP'13: European Symposium on Programming.
  40. ^ US 709932, Frenkel, Ilan; Geller, Roman & Ramberg, Yoram 등, 「서비스 품질 정책 관리 시스템의 디렉토리에서 네트워크 서비스 품질 정책 정보를 취득하는 방법 및 장치」(2006-08-29)는, Cisco Tech Inc.에 할당되어 있습니다.

Bauer, R.T., (2009년 6월), "상대론적 프로그램의 운용 검증" PSU 기술 보고서 TR-09-04 (http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/tr0904.pdf)

외부 링크