상호 배타

2개의

(

i+1

displaystyle

i

)

와

i

i

i+1

1

(displaystyle

i+

1

)

을 동시에 삭제하면

i+1

i

(\displaystyle i+

1)이

i+1

삭제되지 않습니다.

컴퓨터 공학에서 상호 배제는 동시성 제어의 속성으로, 인종 조건을 방지하기 위해 제정됩니다.동시 실행 스레드가 이미 크리티컬 섹션에 액세스하고 있는 동안 실행 스레드 하나가 크리티컬 섹션에 들어가지 않아야 합니다.이 섹션은 실행 스레드가 공유 리소스 또는 공유 메모리에 액세스하는 시간 간격을 의미합니다.

공유 리소스는 두 개 이상의 동시 스레드가 수정하려고 하는 데이터 개체입니다(동시 읽기 작업 2개는 허용되지만 데이터 불일치로 이어지므로 동시 쓰기 작업 2개 또는 읽기 및 쓰기 1개는 허용되지 않습니다).상호 제외 알고리즘은 프로세스가 이미 데이터 객체(중요 섹션)에 쓰기 작업을 수행하고 있는 경우 첫 번째 프로세스가 데이터 객체(중요 섹션)에 쓰기를 완료하고 다른 프로세스가 읽고 쓸 수 있도록 개체를 해방할 때까지 다른 프로세스/스레드가 동일한 개체에 액세스/수정할 수 없음을 보증합니다.

상호 배제의 요건은 동시 알고리즘 ^[3]연구의 첫 번째 주제로 인정된 1965년 논문 "동시 프로그래밍 ^[1]^[2]제어의 문제 해결"에서 Edsger W. Dijkstra에 의해 처음 확인되고 해결되었다.

실무에서 상호 배제가 중요한 이유에 대한 간단한 예는 두 번째와 세 번째 항목을 제거하는 네 가지 항목의 단일 링크 목록을 사용하여 시각화할 수 있다.다른 2개의 노드 사이에 있는 노드를 삭제하려면 이전 노드의 다음 포인터를 다음 노드를 가리키도록 변경합니다(즉, $노드$ i ${\displaystyle$ i}가 $i$ 삭제되면 $i-1$ - $i-1$ 1 {displaystyle $i-1}$ 의 $i-1$ 다음 포인터는 노드 i $i+1$ + $i+1$ { $displaystyle$ i $+1$ 을 가리키도록 변경됩니다). $링크$ 목록에서 노드i(\ $displaystyle$ i $)$ 에 대한 참조를 삭제합니다.이러한 링크 목록이 여러 실행 스레드 간에 공유되는 경우 두 개의 실행 스레드가 동시에 두 개의 다른 노드를 삭제하려고 할 수 있습니다.한 실행 스레드는 $i-1$ i - $1$ 의 $i-1$ 다음 포인터를 $i+1$ i + $1$ 을 가리키도록 변경하고 다른 실행 스레드는 $노드$ i + $1$ 을 가리키도록 변경합니다. $노드$ $i의$ 다음 $i$ 포인터가 $i+2$ i $+ 2$ 를 가리킵니다 $i+2$ 두 제거 작업이 모두 성공적으로 완료되었지만 링크된 목록의 원하는 상태에 도달하지 못했습니다. $i-1$ i $i+1$ + 1 $({$ displaystyle i-1 $})$ 은 $i-1$ $i+1$ i - 1({ $displaystyle$ $i-1$ $i+1$ 의 $i-1$ 다음 포인터가 $i+1$ i + $i+1$ ({ $displaystyle$ i+ $1)$ 을 $i+1$ 가리키기 때문에 목록에 남아 있습니다.

이 문제(레이스 조건이라고 불린다)는 리스트의 같은 부분에 대한 동시 갱신이 발생하지 않도록 상호 제외 요건을 사용함으로써 회피할 수 있습니다.

상호배제라는 용어는 앞서 언급한 메모리 주소가 하나 이상의 다른 스레드에 의해 조작되거나 읽혀지는 동안 하나의 스레드에 의해 메모리 주소가 동시에 쓰여지는 것에 대해서도 사용된다.

문제 설명

상호 배제의 문제는 자원 공유의 문제입니다.각 프로세스가 작업을 수행하는 동안 해당 자원에 대한 배타적 제어가 필요한 상황에서 소프트웨어 시스템이 공유 자원에 대한 여러 프로세스의 액세스를 어떻게 제어할 수 있습니까?이에 대한 상호 제외 솔루션은 프로세스가 중요한 섹션이라는 특정 코드 세그먼트에 있을 때만 공유 리소스를 사용할 수 있도록 합니다.리소스가 사용될 프로그램의 각 부분 상호 실행을 제어하여 공유 리소스에 대한 액세스를 제어합니다.

이 문제를 해결하려면 적어도 다음 두 가지 속성이 있어야 합니다.

상호 배제를 구현해야 합니다.한 번에 하나의 프로세스만 중요 섹션에 포함할 수 있습니다.
데드록이 없어야 합니다.프로세스가 크리티컬섹션에 들어가려고 할 경우 프로세스가 크리티컬섹션에 영속적으로 머무르지 않는 한 프로세스 중 하나가 정상적으로 이행할 수 있어야 합니다.

데드록의 자유도를 확장하여 다음 속성 중 하나 또는 모두를 구현할 수 있습니다.

Lockout-Freedom은 중요한 섹션에 진입하려는 모든 프로세스가 최종적으로 진입할 수 있음을 보증합니다.이는 일부 대기 프로세스가 크리티컬 섹션에 액세스할 수 있어야 하지만 모든 프로세스가 차례대로 수행되어야 하는 교착 상태 회피와는 다릅니다.두 프로세스가 지속적으로 리소스를 교환할 경우 시스템이 교착 상태에 있지 않더라도 세 번째 프로세스가 잠기고 리소스가 부족해질 수 있습니다.시스템에 록아웃이 없는 경우 모든 프로세스가 미래의 어느 시점에서 턴아웃할 수 있습니다.
k 바운드의 대기 속성은 록아웃프리덤보다 더 정확한 커밋을 제공합니다.Lockout-Freedom을 사용하면 모든 프로세스가 최종적으로 중요한 섹션에 액세스할 수 있습니다. 대기 시간에 대한 보장은 없습니다.실제로는 프로세스가 차례가 되기 전에 우선순위가 높은 다른 프로세스에 의해 임의의 횟수 또는 무제한으로 추월될 수 있습니다.k-바운드의 대기 속성에서는 각 프로세스의 최대 대기 시간은 한정되어 있습니다.이는 다른 프로세스가 ^[4]대기하는 동안 k회 이상 크리티컬 섹션에 들어갈 수 없도록 다른 프로세스가 새치기할 수 있는 횟수에 제한을 설정하는 방식으로 작동합니다.

모든 프로세스의 프로그램은 4개의 섹션으로 분할되어 4개의 상태가 됩니다.프로그램 실행은 다음 4가지 상태를 순서대로 ^[5]순환합니다.

단일 공정의 섹션 주기

중요하지 않은 섹션: 작업이 중요 섹션을 벗어납니다. 프로세스가 공유 리소스를 사용하거나 요청하지 않습니다.

괴로운: 프로세스가 크리티컬섹션으로 들어가려고 합니다.

[ Critical ]섹션: 프로세스는 이 섹션의 공유 리소스에 액세스할 수 있습니다.

퇴장: 이 프로세스는 중요한 섹션을 남겨두고 공유 리소스를 다른 프로세스에서 사용할 수 있도록 합니다.

프로세스가 크리티컬섹션에 들어가려면 먼저 trying섹션을 실행하고 critical섹션에 액세스 할 때까지 대기해야 합니다.프로세스가 중요 섹션을 실행하고 공유 리소스를 완료한 후 종료 섹션을 실행하여 다른 프로세스에서 사용할 수 있도록 해제해야 합니다.그런 다음 프로세스가 중요하지 않은 섹션으로 돌아갑니다.

상호 제외 적용

하드웨어 솔루션

단일 프로세서 시스템에서 상호 배제를 실현하는 가장 간단한 해결책은 프로세스의 중요한 섹션 동안 인터럽트를 비활성화하는 것입니다.이로 인해 인터럽트 서비스 루틴이 실행되지 않게 됩니다(프로세스가 프리엠프트되는 것을 효과적으로 방지합니다).이 솔루션은 효과적이지만 많은 문제로 이어집니다.크리티컬 섹션이 긴 경우 타이머 인터럽트가 처리되지 않기 때문에 크리티컬섹션이 실행될 때마다 시스템클럭이 드리프트되기 때문에 크리티컬섹션 중에는 트래킹 시간이 불가능합니다.또한 프로세스가 중요 섹션 중에 중지되면 제어가 다른 프로세스로 반환되지 않고 시스템 전체가 사실상 중단됩니다.상호 배제를 달성하기 위한 보다 우아한 방법은 busy-wait이다.

비지 웨이팅은 유니프로세서시스템과 멀티프로세서시스템 모두에서 유효합니다.공유 메모리의 사용 및 원자 테스트 및 세트 명령은 상호 배제를 제공합니다.프로세스는 공유 메모리 내의 로케이션에서 테스트 및 설정할 수 있습니다.동작은 원자성이기 때문에 플래그를 설정할 수 있는 것은 한 번에 1개의 프로세스뿐입니다.플래그 설정에 실패한 프로세스는 다른 작업을 계속하고 나중에 다시 시도하거나 프로세서를 다른 프로세스로 릴리스하고 나중에 다시 시도하거나 플래그를 확인하면서 플래그를 정상적으로 취득할 때까지 루프를 계속할 수 있습니다.프리엠프션은 아직 가능하기 때문에 이 방법을 사용하면 잠금 유지 중에 프로세스가 정지되어도 시스템이 계속 작동할 수 있습니다.

데이터 구조의 상호 배제를 제공하기 위해 몇 가지 다른 원자 연산을 사용할 수 있습니다. 그 중 가장 주목할 만한 것은 CAS(Compare-and-SW(Compare-and-Swap)입니다.CAS는 각 노드가 실행하는 원하는 동작을 나타내는 링크 리스트를 작성함으로써 공유 데이터 구조에 대해 대기 없는 상호 배제를 실현하기 위해 사용할 수 있다.그런 다음 CAS를 사용하여 새 노드 삽입 중에 링크 목록^[6] 내의 포인터를 변경합니다.CAS에서 성공할 수 있는 프로세스는 1개뿐입니다.또한 노드를 동시에 추가하려는 다른 모든 프로세스는 재시도해야 합니다.그러면 각 프로세스는 데이터 구조의 로컬 복사본을 유지할 수 있으며 링크된 목록을 통과할 때 로컬 복사본의 목록에서 각 작업을 수행할 수 있습니다.

소프트웨어 솔루션

하드웨어 지원 솔루션 외에 비지 대기 기능을 사용하여 상호 배제를 수행하는 소프트웨어 솔루션도 있습니다.예를 들어 다음과 같습니다.

이러한 알고리즘은 알고리즘을 실행하는 플랫폼에서 순서가 잘못된 실행을 사용하는 경우 작동하지 않습니다.프로그래머는 ^[8]스레드 내의 메모리 동작에 대해 엄밀한 순서를 지정해야 합니다.

대부분의 경우 운영 체제의 멀티스레딩 라이브러리에서 제공되는 동기화 기능을 사용하는 것이 좋습니다. 이 기능은 가능하면 하드웨어 솔루션을 활용하지만 하드웨어 솔루션이 없는 경우 소프트웨어 솔루션을 사용합니다.예를 들어, 운영 체제의 잠금 라이브러리가 사용되고 스레드가 이미 취득한 잠금을 취득하려고 하면 운영 체제는 컨텍스트 스위치를 사용하여 스레드를 일시 중단하고 실행 가능한 다른 스레드와 스왑하거나 실행할 수 있는 다른 스레드가 없는 경우 프로세서를 저전력 상태로 만들 수 있습니다.따라서 대부분의 최신 상호 제외 방식에서는 큐잉과 컨텍스트스위치를 사용하여 지연과 비지 대기 시간을 줄이려고 합니다.단, 스레드를 서스펜드한 후 복원하는 데 걸리는 시간이 특정 상황에서 차단된 후 스레드가 실행 준비가 될 때까지 대기해야 하는 시간보다 항상 긴 것으로 판명될 경우 스핀록은 적절한 솔루션입니다(그 경우에만).^{[citation needed]}

상호 배타적 문제에 얽매이다

하나의 바이너리 테스트 & 세트 레지스터로 상호 배제 문제에 대한 교착 없는 해결책을 제공하기에 충분하다.그러나 테스트 및 세트 레지스터를 사용하여 구축한 솔루션은 일부 프로세스가 고갈될 수 있으며, 이 프로세스는 테스트 ^[4]섹션에 포함될 수 있습니다.실제로 록아웃을 피하기 위해서는 $\Omega ({\sqrt {n}})$ ( $\Omega ({\sqrt {n}})$ $)(\displaystyle$ \Omega $(\sqrt$ {n $})})$ 의 $\Omega ({\sqrt {n}})$ 개별 메모리 상태가 필요합니다.무제한 대기 상태를 방지하려면 n개의 개별 메모리 상태가 필요합니다.^[9]

복구 가능한 상호 배제

대부분의 상호 제외 알고리즘은 프로세스가 중요한 섹션 내에서 실행되는 동안 오류가 발생하지 않는다는 가정 하에 설계되었습니다.그러나 실제로는 이러한 실패가 일반적일 수 있습니다.예를 들어 갑자기 전원이 끊기거나 인터커넥트 장애가 발생하면 중요한 섹션의 프로세스에서 회복 불가능한 오류가 발생하거나 계속할 수 없게 됩니다.이러한 장애가 발생했을 경우 기존의 장애 허용성이 없는 상호 제외 알고리즘이 교착 상태가 되거나 키 활성 속성이 실패할 수 있습니다.이 문제에 대처하기 위해 크래시 리커버리 메커니즘을 사용하는 몇 가지 솔루션이 ^[10]제안되었습니다.

상호 제외 장치 유형

위에서 설명한 솔루션을 사용하여 아래 동기화 프리미티브를 구축할 수 있습니다.

많은 형태의 상호 배제는 부작용을 가지고 있다.예를 들어 기존 세마포어를 사용하면 교착 상태가 허용됩니다. 즉, 한 프로세스는 세마포를 얻고 다른 프로세스는 두 번째 세마포를 얻은 다음 둘 다 다른 세마포가 해제될 때까지 기다립니다.기타 일반적인 부작용으로는 프로세스가 완료까지 실행하기에 충분한 자원을 얻을 수 없는 기아, 우선순위가 높은 스레드가 우선순위가 낮은 스레드를 기다리는 priority 반전, 인터럽트에 대한 응답이 신속하지 않은 높은 지연 등이 있습니다.

많은 연구는 위의 효과를 제거하는 것을 목표로 하며, 종종 논블로킹 진행을 보장하는 것을 목표로 한다.완벽한 계획은 알려져 있지 않다.프로세스 전체의 sleep에 사용되는 시스템콜 차단이러한 콜이 스레드 세이프가 될 때까지 프로세스 내에서 단일 스레드를 sleeve 하는 적절한 메커니즘은 없었습니다(폴링 ^{[citation needed]}참조).

「」를 참조해 주세요.

레퍼런스

^ Dijkstra, E. W. (1965). "Solution of a problem in concurrent programming control". Communications of the ACM. 8 (9): 569. doi:10.1145/365559.365617. S2CID 19357737.
^ ^a ^b 토벤펠트, "흑백 베이커리 알고리즘"인프로그래프분산 컴퓨팅, 제18회 국제회의, DISC 2004.Vol 18, 56-70, 2004
^ "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing, retrieved 24 August 2009
^ ^a ^b Attiya, Hagit; Welch, Jennifer (25 March 2004). Distributed computing: fundamentals, simulations, and advanced topics. John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.
^ Lamport, Leslie (26 June 2000), "The Mutual Exclusion Problem Part II: Statement and Solutions" (PDF), Journal of the Association for Computing Machinery, 33 (2): 313–348, doi:10.1145/5383.5384, S2CID 12012739
^ https://timharris.uk/papers/2001-disc.pdf^{[베어 URL PDF]}
^ Lamport, Leslie (August 1974). "A new solution of Dijkstra's concurrent programming problem". Communications of the ACM. 17 (8): 453–455. doi:10.1145/361082.361093. S2CID 8736023.
^ Holzmann, Gerard J.; Bosnacki, Dragan (1 October 2007). "The Design of a Multicore Extension of the SPIN Model Checker" (PDF). IEEE Transactions on Software Engineering. 33 (10): 659–674. doi:10.1109/TSE.2007.70724. S2CID 9080331.
^ Burns, James E.; Paul Jackson, Nancy A. Lynch (January 1982), "Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable" (PDF), Journal of the Association for Computing Machinery, 33 (2): 313–348
^ Golab, Wojciech; Ramaraju, Aditya (July 2016), "Recoverable Mutual Exclusion", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 65–74, doi:10.1145/2933057.2933087, ISBN 9781450339643, S2CID 8621532

추가 정보

미셸 레이날:상호 배제를 위한 알고리즘, MIT Press, ISBN 0-262-1819-3
선일 알Das, Pradip K.스리마니:분산상호배제알고리즘, IEEE Computer Society, ISBN 0-8186-3380-8
토마스 W.크리스토퍼, 조지 K.티루바투칼:고성능 Java 플랫폼 컴퓨팅, 프렌티스 홀, ISBN 0-13-016164-0
Gadi Taubenfeld, 동기화 알고리즘 및 동시 프로그래밍, Pearson/Prentice Hall, ISBN 0-13-197259-6

외부 링크

공통 스레드: POSIX 스레드 설명– Daniel Robbins의 뮤텍스라고 불리는 작은 것
Wayback Machine 상호 제외 Petri Net(2016-06-02 아카이브)
잠금 기능이 있는 상호 배제 – 개요
Open의 상호 제외 변형MP
흑백 베이커리 알고리즘

[1] Dijkstra, E. W. (1965). "Solution of a problem in concurrent programming control". Communications of the ACM. 8 (9): 569. doi:10.1145/365559.365617. S2CID 19357737.

[Taubenfeld:2004-2] 토벤펠트, "흑백 베이커리 알고리즘"인프로그래프분산 컴퓨팅, 제18회 국제회의, DISC 2004.Vol 18, 56-70, 2004

[3] "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing, retrieved 24 August 2009

[Distributed_computing:_fundamentals,_simulations,_and_advanced_topics-4] Attiya, Hagit; Welch, Jennifer (25 March 2004). Distributed computing: fundamentals, simulations, and advanced topics. John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.

[5] Lamport, Leslie (26 June 2000), "The Mutual Exclusion Problem Part II: Statement and Solutions" (PDF), Journal of the Association for Computing Machinery, 33 (2): 313–348, doi:10.1145/5383.5384, S2CID 12012739

[6] ttps://timharris.uk/papers/2001-disc.pdf^{[베어 URL PDF]}

[7] Lamport, Leslie (August 1974). "A new solution of Dijkstra's concurrent programming problem". Communications of the ACM. 17 (8): 453–455. doi:10.1145/361082.361093. S2CID 8736023.

[8] Holzmann, Gerard J.; Bosnacki, Dragan (1 October 2007). "The Design of a Multicore Extension of the SPIN Model Checker" (PDF). IEEE Transactions on Software Engineering. 33 (10): 659–674. doi:10.1109/TSE.2007.70724. S2CID 9080331.

[9] Burns, James E.; Paul Jackson, Nancy A. Lynch (January 1982), "Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable" (PDF), Journal of the Association for Computing Machinery, 33 (2): 313–348

[10] Golab, Wojciech; Ramaraju, Aditya (July 2016), "Recoverable Mutual Exclusion", Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 65–74, doi:10.1145/2933057.2933087, ISBN 9781450339643, S2CID 8621532

[3]

[1]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search

상호 배타

네임스페이스

더

목차

문제 설명

상호 제외 적용

하드웨어 솔루션

소프트웨어 솔루션

상호 배타적 문제에 얽매이다

복구 가능한 상호 배제

상호 제외 장치 유형

「」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

Search

상호 배타

문제 설명

상호 제외 적용

하드웨어 솔루션

소프트웨어 솔루션

상호 배타적 문제에 얽매이다

복구 가능한 상호 배제

상호 제외 장치 유형

「 」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

「」를 참조해 주세요.