독자-라이터 문제
Readers–writers problem |
컴퓨터 과학에서, 독자-작가 문제는 [1]동시성에서의 일반적인 컴퓨팅 문제의 예입니다.여러 동시 실행 스레드가 동시에 동일한 공유 리소스에 액세스하려고 하는 상황을 다루는 문제에는 적어도 세 가지 종류가 있습니다.
일부 스레드는 읽거나 쓸 수 있지만, 다른 스레드가 쓰기 작업을 하는 동안에는 어떤 스레드도 공유 리소스에 액세스할 수 없습니다(특히, 여러 스레드가 공유 리소스를 동시에 수정하는 것을 방지하고 두 개 이상의 리더가 공유 리소스에 액세스할 수 있도록 합니다).use를 동시에 사용합니다).리더 라이터 잠금이란 하나 이상의 리더 라이터 문제를 해결하는 데이터 구조입니다.
기본적인 독자-작가 문제는 Courtois [2][3]등에 의해 처음 공식화되고 해결되었다.
첫 번째 독자-라이터 문제
위에서 설명한 기본 제약 조건을 가진 공유 메모리 영역(중요 섹션)이 있다고 가정합니다.상호 제외 뮤텍스 뒤에서 공유 데이터를 보호할 수 있습니다. 이 경우 두 개의 스레드가 동시에 데이터에 액세스할 수 없습니다.단1, 리더 R이 잠금을 가지고 다른 리더2 R이 액세스를 요구할 가능성이 있기 때문에 이 솔루션은 최적이라고 할 수 없습니다.R이2 자체 읽기 작업을 시작하기 전에 R이 완료될 때까지1 기다리는 것은 어리석은 일입니다. 대신 읽기는 데이터를 수정하지 않으므로 R이 R과 함께1 리소스를 읽을 수 있도록 허용해야2 합니다. 따라서 동시 읽기는 안전합니다.이것이 첫 번째 독자-작가 문제에 대한 동기이며, 여기서 공유가 현재 열람을 위해 열려 있는 경우 독자를 계속 기다릴 수 없다는 제약이 추가된다.이것은, 독자 프리퍼런스라고도 불리며, 그 솔루션은 다음과 같습니다.
세마포 자원=1; 세마포 rmutex=1; 재카운트=0; /* 자원입니다.P()는 wait(리소스)와 동일합니다. 자원입니다.V()는 신호(리소스)와 동일합니다. rmutex.P()는 wait(rmutex)와 동일합니다. rmutex.V()는 signal(rmutex)과 동일합니다. */ 작가.() { 자원.P(); //라이터 공유 파일 잠금 < >중요. 부분> // 쓰기가 완료되었습니다. < >퇴장 부분> 자원.V(); //다른 리더가 사용할 수 있도록 공유 파일을 해제합니다.요청하는 독자가 없는 경우 필자가 허용됩니다. } 독자() { rmutex.P(); //<엔트리> 섹션을 실행하는 동안 다른 리더가 없는지 확인합니다. < >중요. 부분> 재카운트++; //Critical 섹션에 들어가려고 하는 독자임을 나타냅니다. 한다면 (재카운트 == 1) //당신이 CS에 들어가려고 하는 첫 번째 리더인지 확인합니다. 자원.P(); //첫 번째 리더인 경우, 라이터로부터 자원을 잠급니다.리소스는 후속 리더를 위해 예약된 상태로 유지됩니다. < >퇴장 중요. 부분> rmutex.V(); //릴리스 // 판독을 수행합니다. rmutex.P(); //다른 리더가 <종료> 섹션을 실행할 수 없도록 합니다. < >중요. 부분> 재카운트--; //공유 리소스가 더 이상 필요하지 않음을 나타냅니다.리더 1대 감소 한다면 (재카운트 == 0) //공유 파일을 읽고 있는 마지막 (유일한) 리더인지 확인합니다. 자원.V(); //마지막 리더인 경우 리소스 잠금을 해제할 수 있습니다.이것은 작가들이 그것을 이용할 수 있게 한다. < >퇴장 중요. 부분> rmutex.V(); //릴리스 } 이 리더/라이터 문제의 해결 방법에서는 자원(공유 파일)을 사용할 수 있는 경우 첫 번째 리더가 잠글 필요가 있습니다.파일이 라이터로부터 잠기면, 그 후 많은 리더가 파일을 다시 잠그지 않고 사용할 수 있습니다.
중요한 섹션에 들어가기 전에 모든 새 리더는 입력 섹션을 검토해야 합니다.단, 엔트리 섹션에는 한 번에 1개의 리더만 있을 수 있습니다.이는 리더의 레이스 조건을 피하기 위해 이루어집니다(이 문맥에서 레이스 조건은 2개 이상의 스레드가 동시에 웨이크업하여 크리티컬섹션에 들어가려고 하는 상태입니다.더 이상의 제약 없이 동작은 비결정적입니다).예를 들어, 두 개의 리더가 동시에 읽기 카운트를 증가시키고, 둘 다 리소스를 잠그려고 시도하여 한 개의 리더가 차단됩니다).이를 위해 <ENTY Section>에 들어가는 모든 리더는 완료될 때까지 스스로 <ENTY Section>을 잠급니다.이 시점에서 리더는 리소스를 잠그지 않습니다.입력 섹션만 잠그고 있기 때문에 다른 판독기는 입력 섹션에 들어갈 수 없습니다.판독기는 엔트리 섹션의 실행을 완료하면 뮤텍스에 신호를 보내 잠금을 해제합니다.시그널링은 mutex와 동일합니다.위 코드의 V().<EX>도 마찬가지입니다.[ IT Section > ]를 클릭합니다.종료 섹션에는 한 번에 1개 이상의 판독기를 설치할 수 없습니다.따라서 모든 판독기는 사용하기 전에 자신의 종료 섹션을 요청하고 잠가야 합니다.
첫 번째 리더가 엔트리 섹션에 있으면 리소스가 잠깁니다.이렇게 하면 작성자가 액세스할 수 없습니다.후속 독자는 잠긴 (라이터의) 리소스만 사용할 수 있습니다.마지막으로 끝낼 판독기(readcount 변수에 의해 표시됨)는 리소스의 잠금을 해제해야 하므로 기록자가 리소스를 사용할 수 있습니다.
이 솔루션에서는 모든 라이터가 개별적으로 자원을 청구해야 합니다.이것은 일련의 독자들이 이후에 모든 잠재적 작가들을 가두고 굶길 수 있다는 것을 의미한다.이는 첫 번째 리더가 리소스를 잠근 후에는 리소스가 해제되기 전에 기록자가 리소스를 잠글 수 없기 때문입니다.그리고 마지막 독자가 발표할 것이다.따라서 이 솔루션은 공정성을 만족시키지 못합니다.
두 번째 독자: 라이터 문제
리더1 R이 잠금을 가지고 있고, 라이터 W가 잠금을 기다리고 있을 가능성이 있으며, 리더2 R이 액세스를 요구할 수 있기 때문에 첫 번째 솔루션은 차선책입니다.R이2 W보다 먼저 뛰어드는 것은 불공평하다.그 일이 자주 일어나면 W는 굶을 것이다.대신 W는 가능한 한 빨리 시작해야 합니다.이것이 두 번째 독자-작가 문제에 대한 동기부여입니다.이 문제에서는 큐에 한 번 추가된 라이터는 절대 필요 이상으로 오랫동안 대기해서는 안 된다는 제약이 추가됩니다.이것은 작가 선호라고도 불립니다.
라이터 프리퍼런스시나리오에 대한 해결책은 다음과 같습니다.[2]
인트 재카운트, 기입 카운트; //(초기값 = 0) 세마포 rmutex, 뮤텍스, 재시도, 자원; //(초기값 = 1) //판독기 독자() { < >엔트리 부분> 재시도.P(); //독자가 입력하려고 함을 나타냅니다. rmutex.P(); //다른 리더와의 레이스 상태를 피하기 위해 엔트리 섹션을 잠급니다. 재카운트++; //본인을 독자로 보고합니다. 한다면 (재카운트 == 1) //첫 번째 독자일 경우 표시 자원.P(); //첫 번째 리더인 경우 리소스를 잠급니다. rmutex.V(); //다른 리더를 위해 항목 섹션 해제 재시도.V(); //리소스에 대한 접근이 종료되었습니다. < >중요. 부분> //읽기가 실행됩니다. < >퇴장 부분> rmutex.P(); //종료 섹션 삭제 - 리더와의 레이스 조건을 회피합니다. 재카운트--; //떠나야 할 것 같아 한다면 (재카운트 == 0) //마지막 리더가 떠나는 경우 표시 자원.V(); //마지막인 경우 잠긴 리소스를 해제해야 합니다. rmutex.V(); //다른 리더를 위해 종료 섹션 해제 } //라이터 작가.() { < >엔트리 부분> 뮤텍스.P(); //작성자를 위한 엔트리 섹션 삭제 - 레이스 조건 회피 기입 카운트++; //작가로써 자신을 신고합니다. 한다면 (기입 카운트 == 1) //첫 번째 라이터인 경우 변경 재시도.P(); //처음에는 독자를 차단해야 합니다.CS에 들어가지 않도록 하다 뮤텍스.V(); //release 엔트리 섹션 자원.P(); //스스로 리소스 편집 - 다른 작성자가 공유 리소스를 동시에 편집하지 못하도록 합니다. < >중요. 부분> //기입이 실행됩니다. 자원.V(); //파일 릴리스 < >퇴장 부분> 뮤텍스.P(); //종료 섹션 삭제 기입 카운트--; //떠나야 할 것 같아 한다면 (기입 카운트 == 0) //마지막 작성자일 경우 변경 재시도.V(); //마지막 작성자라면 독자의 잠금을 해제해야 합니다.읽기 위해 CS를 입력할 수 있습니다. 뮤텍스.V(); //종료 섹션 해제 } 이 솔루션에서는 작가에게 우선권이 주어집니다.이는 모든 리더가 읽기 시도 세마포어를 개별적으로 잠그고 해제하도록 함으로써 실현됩니다.반면 작가들은 개별적으로 잠글 필요가 없습니다.첫 번째 라이터만 읽기 시도를 잠그고 이후 모든 라이터는 이전 라이터에 의해 리소스가 해방되면 리소스를 사용할 수 있습니다.맨 마지막 작가는 읽기 힘든 세마포어를 풀어 독자들이 읽을 수 있는 문을 열어야 한다.
읽기 시도 세마포어가 이전에 라이터에 의해 설정되어 있는 경우, 판독자는 엔트리 섹션에 참여할 수 없습니다.리더는 마지막 기록자가 리소스를 잠금 해제하고 세마포어를 다시 시도할 때까지 기다려야 합니다.한편, 특정 리더가 읽기 시도 세마포어를 잠근 경우, 이는 엔트리 섹션에 리더가 있음을 모든 동시 작성자에게 나타냅니다.그래서 작가는 독자가 재시도문을 발표하기를 기다렸다가 그 자신과 그 이후의 모든 작가들을 위해 즉시 잠글 것이다.그러나 현재 리더가 리소스를 해제할 때까지 작성자는 리소스에 액세스할 수 없습니다. 이 작업은 리더가 중요한 섹션의 리소스를 모두 사용한 후에만 발생합니다.
자원 세마포어는 기입 섹션의 작성자와 판독자 모두에 의해 잠길 수 있습니다.먼저 읽기 시도 세마포어를 잠근 후에만 실행할 수 있습니다.한 번에 1개만 잠글 수 있습니다.
읽기 시도 세마포의 상태에 따라 독자에게 표시된 리소스에 액세스하려는 기록기가 없는 경우, 독자는 리소스를 잠그지 않습니다.이는 현재 리더가 읽기를 마치자마자 라이터가 리소스를 즉시 제어할 수 있도록 하기 위한 것입니다.그렇지 않으면, 라이터는 마지막 사용자가 읽기 시도 세마포어를 잠금 해제하기 전에 리더 대기열이 완료될 때까지 기다려야 합니다.라이터가 나타나자마자 리트라이 설정을 시도하고 현재 리더가 리트라이를 해제하기를 기다리며 전화를 끊습니다.그런 다음 현재 리더가 읽기를 마치자마자 리소스를 제어하고 미래의 모든 리더를 잠급니다.이후 모든 리더는 읽기 시도 세마포에서 전화를 끊고 라이터가 리소스를 다 사용하고 readtry를 해제하여 게이트를 열기를 기다립니다.
rmutex 및 wmutex는 첫 번째 솔루션과 동일한 방법으로 사용됩니다.그들의 유일한 목적은 독자들과 작가들이 그들의 출입 구역에 있는 동안 그들이 경쟁하는 상황을 피하는 것이다.
제3의 독자: 라이터 문제
실제로 두 문제 문장이 암시하는 해결책은 기아로 이어질 수 있습니다.첫 번째 문제 문장은 큐에 있는 라이터를 굶길 수 있고 두 번째 문제 문장은 독자를 굶길 수 있습니다.따라서, 때때로 세 번째 독자-작가 문제가 제안되는데, 이는 어떤 스레드도 부족하게 해서는 안 된다는 제약 조건을 추가한다. 즉, 공유 데이터에 대한 잠금을 얻는 작업은 항상 제한된 시간 내에 종료된다.독자와 작가 모두에게 공평한 해결책은 다음과 같습니다.
인트 재카운트; // 0으로 초기화, 현재 리소스에 액세스하는 리더 수 // 모든 세마포어가 1로 초기화됨 세마포 자원; // 리소스에 대한 액세스(읽기/쓰기)를 제어합니다.바이너리 세마포어 세마포 rmutex; // 공유 변수 readcount 변경 동기화 세마포 서비스 큐; // 공정성: 요청 순서를 유지합니다(신호는 FIFO여야 함). //판독기 독자() { < >엔트리 부분> 서비스 큐.P(); // 서비스를 받기 위해 줄을 서서 대기합니다. rmutex.P(); // readcount에 대한 배타적 액세스 요청 재카운트++; // 활성 리더의 업데이트 수 한다면 (재카운트 == 1) // 내가 첫 번째 독자일 경우 자원.P(); // 리더에 대한 리소스 액세스 요청(라이터 차단됨) 서비스 큐.V(); // next in line 서비스 제공 rmutex.V(); // readcount에 대한 액세스 해제 < >중요. 부분> //읽기가 실행됩니다. < >퇴장 부분> rmutex.P(); // readcount에 대한 배타적 액세스 요청 재카운트--; // 활성 리더의 업데이트 수 한다면 (재카운트 == 0) // 리더가 남아 있지 않은 경우 자원.V(); // 모든 사용자에 대한 리소스 액세스 해제 rmutex.V(); // readcount에 대한 액세스 해제 } //라이터 작가.() { < >엔트리 부분> 서비스 큐.P(); // 서비스를 받기 위해 줄을 서서 대기합니다. 자원.P(); // 리소스에 대한 배타적 액세스 요청 서비스 큐.V(); // next in line 서비스 제공 < >중요. 부분> // 쓰기가 수행됩니다. < >퇴장 부분> 자원.V(); // 다음 리더/라이터용 리소스 액세스 해제 } 이 솔루션은 세마포어가 스레드를 차단 및 해제할 때 선입선출 순서를 유지하는 경우에만 "어떤 스레드도 굶주리지 않아야 한다"는 조건을 충족할 수 있습니다.그렇지 않으면 차단된 라이터는 예를 들어 다른 라이터가 세마포어를 감소시키는 사이클과 함께 무기한 차단 상태를 유지할 수 있습니다.
가장 간단한 리더 라이터 문제
두 개의 세마포만 사용하고 버퍼에 있는 데이터를 읽기 위해 리더 배열이 필요하지 않은 가장 단순한 리더 라이터 문제입니다.
이 솔루션은 Bounded buffer 문제와 동등하게 만들어졌기 때문에 일반적인 경우보다 간단하다는 점에 유의하십시오.N독자는 병렬로 입장할 수 있습니다.N버퍼의 크기입니다.
독자
하다 { 잠깐만요.(읽어주세요) ............ 읽고 있어 데이터. ............ 신호.(쓰다) } 하는 동안에 (진실의); 작가.
하다 { 잠깐만요.(쓰다) ............. 쓰기 데이터. ............. 신호.(읽어주세요) } 하는 동안에 (진실의); 알고리즘.
- 읽기 세마포어로 인해 Writer 뒤에 Reader가 실행됩니다.
- 쓰기 세마포어가 0에 도달하면 쓰기 작업이 중지됩니다.
- 판독 세마포가 0에 도달하면 판독기가 판독을 중지합니다.
라이터에서는 읽기 세마포에 쓰기 세마포의 값을 부여하고, 리더에서는 루프 완료 시에 쓰기 세마포의 값을 부여한다.
「 」를 참조해 주세요.
레퍼런스
- ^ Tanenbaum, Andrew S. (2006), Operating Systems - Design and Implementation, 3rd edition [Chapter: 2.3.2 The Readers and Writers Problem], Pearson Education, Inc.
- ^ a b Courtois, P. J.; Heymans, F.; Parnas, D. L. (1971). "Concurrent Control with "Readers" and "Writers"" (PDF). Communications of the ACM. 14 (10): 667–668. doi:10.1145/362759.362813. S2CID 7540747.
- ^ Taubenfeld, Gadi (2006). Synchronization Algorithms and Concurrent Programming. Pearson Education. p. 301.
- Morris JM(1979년).상호 배타적 문제에 대한 기아 없는 해결책.Inf 프로세스 Let 8:76 ~80
- Reader-Writer에 대한 공정한 해결책-세마포만의 문제.H. 발하우젠, 2003 arXiv:cs/0303005
- Reader-Writer 문제에 대한 보다 빠른 공정한 솔루션.V. Popov, O. Mazonka 2013 arXiv: 1309.4507
