독서자-작성자 잠금

Readers–writer lock
작가들이 가끔 겪는 심리적 어려움은 작가 블록을 참고하십시오.

컴퓨터 과학에서, 독자-작가-작가(단독자 잠금,[1] 다중 판독자 잠금,[2][3] 푸시 잠금 또는 MISSW 잠금)는 독자-작가 문제를 해결하는 동기화 원시적이다.RW 잠금 장치는 읽기 전용 작업에 대한 동시 액세스를 허용하는 반면 쓰기 작업에는 전용 액세스가 필요하다.이는 여러 개의 스레드가 병렬로 데이터를 읽을 수 있지만 데이터를 쓰거나 수정하기 위해서는 독점적인 잠금이 필요하다는 것을 의미한다.작가가 자료를 쓰고 있을 때, 다른 모든 작가나 독자들은 작가가 글을 다 쓸 때까지 차단될 것이다.일반적으로는 원자적으로 업데이트할 수 없고 업데이트가 완료될 때까지 유효하지 않은(그리고 다른 스레드로 읽을 수 없는) 메모리의 데이터 구조에 대한 액세스를 제어하는 것일 수 있다.

독서자-작성자 잠금은 보통 뮤텍스와 조건 변수 위 또는 세마포어 위에 구성된다.

업그레이드 가능한 RW 잠금

일부 RW 잠금장치는 잠금장치를 읽기-모드에서 쓰기-모드로 잠그는 것뿐만 아니라 쓰기-모드에서 읽기-모드로 다운그레이드하는 것을 원자적으로 허용한다.[1] 리더를 고정하는 두 개의 스레드가 모두 쓰기기 잠금으로 업그레이드하려고 할 때마다, 리더 잠금을 해제하는 하나의 스레드에 의해서만 중단이 발생하기 때문에 업그레이드 가능한 RW 잠금 장치는 안전하게 사용하기 어려울 수 있다.쓰기 모드에는 스레드가 없고 읽기 모드에는 0이 아닐 수 있는 스레드가 없는 상태에서 "쓰기로 업그레이드하려는 읽기 모드"에서 하나의 스레드만 잠금을 획득하도록 허용함으로써 교착 상태를 피할 수 있다.

우선 순위 정책

RW 잠금장치는 독자와 작성자 접근을 위한 다른 우선순위 정책으로 설계될 수 있다.자물쇠는 항상 독자에게 우선권을 주거나(읽기 선호), 항상 저자에게 우선권을 주거나(쓰기 선호) 우선순위와 관련하여 불특정화되도록 설계될 수 있다.이 정책들은 동시성과 기아에 관한 다른 절충을 초래한다.

  • 읽기 우선 RW 잠금은 최대 동시성을 허용하지만 경합이 높을 경우 쓰기 별고로 이어질 수 있다.적어도 한 개의 읽기용 나사산이 잠금을 쥐고 있는 한 쓰기용 나사산이 잠금을 획득할 수 없기 때문이다.여러 개의 판독기 스레드가 동시에 잠금을 고정할 수 있기 때문에, 이는 새로운 판독기 스레드가 잠금을 획득할 수 있는 동안에도, 심지어 처음 잠금을 획득하려고 시도할 때 잠금을 잡고 있던 모든 독자들이 잠금을 해제한 후에도 작가가 여전히 기다리고 있을 수 있는 지점까지 작가 스레드가 잠금을 계속 기다릴 수 있다는 것을 의미한다.독자에 대한 우선 순위는 방금 설명한 것처럼 약하거나 강할 수 있는데, 작가가 자물쇠를 열 때마다 차단 독자는 항상 다음에 자물쇠를 얻는다.[4]: 76
  • 쓰기 선호 RW 잠금 장치는 대기 중인 작가가 있을 경우 새로운 독자들이 자물쇠를 획득하지 못하도록 함으로써 작가 기아 문제를 피한다. 작가는 이미 자물쇠를 잡고 있던 모든 독자들이 그 자물쇠를 완성하는 즉시 그 자물쇠를 획득할 것이다.[5]단점은 쓰기 선호 잠금 장치는 읽기 선호 RW 잠금에 비해 쓰기 선호 잠금 장치(writer srad)가 있는 상태에서 동시성을 덜 허용한다는 것이다.또한 읽기 또는 쓰기를 위해 잠금을 취하거나 해제하는 각 조작이 더 복잡하여 내부적으로 한 개 대신 두 개의 뮤텍스를 취하여 해제해야 하기 때문에 잠금 장치의 성능이 떨어진다.[citation needed]이 변형은 때때로 "쓰기 편향된" 독자-작성자 잠금이라고도 알려져 있다.[6]
  • 지정되지 않은 우선 순위 RW 잠금 장치는 읽기 대 쓰기 액세스에 관한 보증을 제공하지 않는다.지정되지 않은 우선 순위는 더 효율적인 구현을 허용한다면 일부 상황에서 선호될 수 있다.[citation needed]

실행

독자-작성자 잠금을 위한 몇 가지 구현 전략이 존재하며, 사전 존재한다고 가정하는 동기화 원시 요소들로 감소한다.

두 개의 음소거 사용

Raynal은 두 개의 뮤텍스와 하나의 정수 카운터를 사용하여 R/W 잠금을 구현하는 방법을 보여준다.카운터 b는 차단 독자 수를 추적한다.하나의 뮤텍스, r, 는 b를 보호하고 독자에 의해서만 사용되며, 다른 하나의 g ("글로벌"의 경우)는 작가들의 상호 배제를 보장한다.이를 위해서는 한 나사산에 의해 획득된 뮤텍스가 다른 나사산에 의해 방출될 수 있어야 한다.다음은 작업에 대한 유사점이다.

초기화

  • b를 0으로 설정한다.
  • r이 잠겨 있지 않다.
  • g가 잠겨 있지 않다.

읽기 시작

  • 자물쇠 r.
  • 증분 b.
  • b = 1이면 g를 잠근다.
  • 잠금 해제 r.

읽기 종료

  • 자물쇠 r.
  • 노쇠 b.
  • b = 0이면 g를 잠금 해제한다.
  • 잠금 해제 r.

쓰기 시작

  • 자물쇠 g.

쓰기 종료

  • 잠금 해제 g.

이 구현은 읽기 선호한다.[4]: 76

조건 변수 및 뮤텍스 사용

또는 RW 잠금은 조건 변수, 콘드, 일반 (뮤텍스) 잠금, g 및 현재 활성화되거나 대기 중인 스레드를 설명하는 다양한 카운터 및 플래그 측면에서 구현될 수 있다.[7][8][9]쓰기 우선 RW 잠금의 경우 두 개의 정수 카운터와 하나의 부울 플래그를 사용할 수 있다.

  • num_message_active: 잠금을 획득한 판독기 수(수)
  • num_message_messages: 액세스를 기다리는 작가 수(messager 수(integer)
  • writer_active: 작가가 잠금(부울)을 획득했는지 여부.

처음에 num_readers_active 및 num_waitinger_waiting은 0이고 writer_active는 false이다.

다음과 같이 잠금 및 해제 작업을 구현할 수 있다.

읽기 시작

  • 잠금 g
  • num_writers_waiting > 0 또는 writer_active 중:
    • 기다림 콘드, g[a]
  • 증가 num_readers_active
  • 잠금 해제 g.

읽기 종료

  • 잠금 g
  • 감소 num_readers_active
  • num_readers_active = 0인 경우:
    • 콘드(방송) 알림
  • 잠금 해제 g.

쓰기 시작

  • 잠금 g
  • num_writer_waiting 증분
  • num_readers_active > 0 또는 writer_active가 참인 경우:
    • 기다림 콘드, g
  • 감소 num_writers_waiting
  • writer_active를 true로 설정
  • 잠금 해제 g.

쓰기 종료

  • 잠금 g
  • writer_active를 false로 설정
  • 콘드(방송) 알림
  • 잠금 해제 g.

프로그래밍 언어 지원

  • POSIX 표준pthread_rwlock_t및 관련 작업[10]
  • Java 버전 5 이상에서 ReadWriteLock[11] 인터페이스 및 ReentrantReadWriteLock[6] 잠김
  • 마이크로소프트System.Threading.ReaderWriterLockSlimC#와 다른 것을 위하여 자물쇠를 잠근다.NET 언어[12]
  • std::shared_mutexC++17의[13] 읽기/쓰기 잠금
  • boost::shared_mutex그리고boost::upgrade_mutexBoost C++ 라이브러리의[14] 잠금
  • SRWLock, 윈도우즈 비스타의 윈도우즈 운영 체제 API에 추가됨.[15]
  • sync.RWMutex바둑서[16]
  • 독자와 작가가[17] 번갈아 가며 사용하는 공정 공정 독서자-작성자 잠금
  • std::sync::RwLock러스트에서[18] 잠금 장치를 읽다/쓰기
  • Poco::POCO C++ 라이브러리의 RWLock
  • mse::recursive_shared_timed_mutexSafetyCPlusPlus 라이브러리는 의 반복적 소유권 의미 체계를 지원하는 버전의 입니다.
  • txrwlock.ReadersWriterDeferredLock독서자/쓰기자 뒤틀림[19] 잠금

대안

RCU(읽기-복사-업데이트) 알고리즘은 독자-작성자 문제에 대한 하나의 해결책이다.RCU는 독자들에게는 무료다.리눅스 커널은 seqlock이라고 불리는 소수의 작가들을 위한 특별한 솔루션을 구현한다.

참고 항목

메모들

  1. ^ 이것은 조건 변수에 대한 표준 "대기" 연산으로, 다른 동작 중에서도 뮤텍스 g를 해제한다.

참조

  1. ^ Hamilton, Doug (21 April 1995). "Suggestions for multiple-reader/single-writer lock?". Newsgroup: comp.os.ms-windows.nt.misc. Usenet: hamilton.798430053@BIX.com. Retrieved 8 October 2010.
  2. ^ 키어 프레이저 2004의 "실용적 잠금 자유"
  3. ^ "Push Locks – What are they?". Ntdebugging Blog. MSDN Blogs. 2 September 2009. Retrieved 11 May 2017.
  4. ^ a b Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer.
  5. ^ Stevens, W. Richard; Rago, Stephen A. (2013). Advanced Programming in the UNIX Environment. Addison-Wesley. p. 409.
  6. ^ a b java.util.concurrent.locks.ReentrantReadWriteLockJava 리더-작성자 잠금 구현은 "공정한" 모드 제공
  7. ^ Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. pp. 184–185.
  8. ^ Nichols, Bradford; Buttlar, Dick; Farrell, Jacqueline (1996). PThreads Programming: A POSIX Standard for Better Multiprocessing. O'Reilly. pp. 84–89.
  9. ^ Butenhof, David R. (1997). Programming with POSIX Threads. Addison-Wesley. pp. 253–266.
  10. ^ "The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy". The IEEE and The Open Group. Retrieved 14 May 2011.
  11. ^ java.util.concurrent.locks.ReadWriteLock
  12. ^ "ReaderWriteLockSlim Class (System.Threading)". Microsoft Corporation. Retrieved 14 May 2011.
  13. ^ "New adopted paper: N3659, Shared Locking in C++—Howard Hinnant, Detlef Vollmann, Hans Boehm". Standard C++ Foundation.
  14. ^ Anthony Williams. "Synchronization – Boost 1.52.0". Retrieved 31 January 2012.
  15. ^ Alessandrini, Victor (2015). Shared Memory Application Programming: Concepts and Strategies in Multicore Application Programming. Morgan Kaufmann.
  16. ^ "The Go Programming language - Package sync". Retrieved 30 May 2015.
  17. ^ "Reader–Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems" (PDF).
  18. ^ "std::sync::RwLock - Rust". Retrieved 26 October 2019.
  19. ^ "Readers/Writer Lock for Twisted". Retrieved 28 September 2016.