교착 상태

Deadlock
데스록이나 드레드록과 혼동하지 말 것.
이 기사는 컴퓨터 과학 개념에 관한 것이다.다른 용도는 교착 상태(동음이의)를 참조하십시오.
두 프로세스 모두 실행을 계속하려면 리소스가 필요합니다.P1은 추가 자원 R1을 필요로 하고 리소스 R2를 소유하고 있으며 P2는 추가 자원 R2를 필요로 하며 R1을 소유하고 있습니다.어느 프로세스도 속행할 수 없습니다.
오른쪽-왼쪽 정책에 따라 네 개의 프로세스(파란색 선)가 하나의 리소스(회색 원)를 위해 경쟁합니다.교착 상태는 모든 프로세스가 리소스를 동시에 잠글 때 발생합니다(검은색 선).교착상태는 대칭을 깨면 해결될 수 있다.

동시 컴퓨팅에서 데드록이란 자신을 포함한 다른 멤버가 메시지를 보내거나 [1]더 일반적으로 잠금을 해제하는 등의 조치를 취할 때까지 대기하기 때문에 일부 엔티티 그룹의 멤버가 진행할 수 없는 상황을 말합니다.교착상태는 다중처리 시스템, 병렬컴퓨팅 및 분산시스템에서 흔히 볼 수 있는 문제입니다.이러한 상황에서 시스템은 소프트웨어 또는 하드웨어 잠금을 사용하여 공유 자원을 조정하고 프로세스 [2]동기화를 구현하기 때문입니다.

운영체제에서 요청된 시스템자원이 다른 대기프로세스에 의해 유지되고 다시 다른 [3]대기프로세스에 의해 유지되는 다른 자원을 대기하기 때문에 프로세스 또는 스레드가 대기상태가 되었을 때 교착상태가 발생합니다.프로세스가 요청한 리소스가 대기 중인 다른 프로세스에서 사용되고 있기 때문에 프로세스가 상태를 무한정 변경할 수 없는 경우 시스템은 [4]교착 상태에 있다고 합니다.

통신 시스템에서 교착상태는 [5]주로 자원의 경합보다는 신호의 손실이나 파손에 의해 발생합니다.

두 프로세스가 두 리소스를 놓고 서로 반대 순서로 경쟁합니다.
  1. 단일 프로세스가 진행됩니다.
  2. 이후 프로세스는 대기해야 합니다.
  3. 교착 상태는 첫 번째 프로세스가 첫 번째 리소스를 잠그는 동시에 두 번째 프로세스가 두 번째 리소스를 잠글 때 발생합니다.
  4. 교착 상태는 첫 번째 프로세스를 취소하고 다시 시작하여 해결할 수 있습니다.

필요조건

리소스 교착 상태는 시스템에서 [6]다음 조건이 모두 동시에 발생하는 경우에만 발생할 수 있습니다.

  1. 상호 제외:하나 이상의 리소스가 공유 불가능 모드로 유지되어야 합니다. 즉,[7] 리소스를 사용할 수 있는 프로세스는 한 번에 1개뿐입니다.그렇지 않으면 프로세스가 필요할 때 리소스를 사용할 수 없게 됩니다.한 [8]번에 하나의 프로세스만 리소스를 사용할 수 있습니다.
  2. 보류 및 대기 또는 리소스 보류: 프로세스가 현재 하나 이상의 리소스를 보유하고 있으며 다른 프로세스가 보유하고 있는 추가 리소스를 요구하고 있습니다.
  3. 프리엠프션 없음: 자원을 보유하는 프로세스에 의해서만 자원을 자발적으로 해방할 수 있습니다.
  4. 순환 대기: 각 프로세스는 다른 프로세스가 보유하고 있는 리소스를 대기하고 있어야 하며, 이 리소스는 첫 번째 프로세스가 리소스를 해제하기를 대기하고 있습니다.일반적으로 대기 프로세스인 P = {P1, P2, …, P}가N P가2 보유한 리소스를 대기하고2 P가 [4][9]P가 보유한1 리소스를 대기할 때까지N P가 P가 보유한3 리소스를 대기하는 프로세스가1 있습니다.

이 네 가지 조건은 1971년 에드워드 G. 코프만 [9]주니어가 쓴 기사에서 처음 기술한 것부터 코프만 조건이라고 알려져 있다.

이러한 조건은 단일 인스턴스 리소스 시스템에서 교착 상태를 발생시키기에 충분하지만 여러 [10]리소스 인스턴스가 있는 시스템에서 교착 상태가 발생할 가능성을 나타낼 뿐입니다.

교착 처리

대부분의 현재 운영 체제에서는 [11]교착 상태를 방지할 수 없습니다.교착 상태가 발생하면 운영 체제마다 다른 비표준 방식으로 대응합니다.대부분의 접근방식은 4가지 공통 조건 중 하나(특히 4가지)[12]가 발생하지 않도록 하는 것으로 동작합니다.주요 접근법은 다음과 같습니다.

교착 상태 무시

이 방법에서는 교착 상태가 발생하지 않는 것으로 가정합니다.이것도 Tajo [12][13]알고리즘의 응용 프로그램입니다.이 접근방식은 처음에 MINIX와 [9]UNIX에서 사용되었습니다.교착 상태가 발생하는 시간 간격이 크고 매번 발생하는 데이터 손실이 허용 가능한 경우 사용합니다.

데드록이 발생하지 않는 것이 공식적으로 증명되면 데드록은 안전하게 무시될 수 있습니다.예를 들어 RTIC [14]프레임워크가 있습니다.

검출

데드록 검출에서는 데드록이 발생할 수 있습니다.그런 다음 시스템 상태를 검사하여 교착 상태가 발생한 것을 감지하고 나중에 수정됩니다.리소스 할당 및 프로세스 상태를 추적하는 알고리즘이 사용되며, 탐지된 교착 상태를 제거하기 위해 하나 이상의 프로세스를 롤백하고 재시작합니다.각 프로세스가 잠겨 있거나 현재 요청된 리소스가 운영 [13]체제의 리소스 스케줄러에 알려져 있기 때문에 이미 발생한 교착 상태를 쉽게 탐지할 수 있습니다.

데드록이 검출되면 다음 방법 [citation needed]중 하나를 사용하여 수정할 수 있습니다.

  1. 프로세스 종료: 교착 상태에 관련된 하나 이상의 프로세스가 중단될 수 있습니다.교착 상태에 관련된 모든 경쟁 프로세스를 중단할 수도 있습니다.이것에 의해, 데드록은 확실성과 [citation needed]스피드로 해결됩니다.하지만 부분적인 계산이 손실되기 때문에 비용이 많이 듭니다.또는 교착 상태가 해결될 때까지 한 번에 하나씩 프로세스를 중단하도록 선택할 수도 있습니다.이 접근방식은 각 중단 후 알고리즘이 시스템이 아직 [citation needed]교착 상태에 있는지 여부를 판단해야 하기 때문에 오버헤드가 높아집니다.종료 후보를 선택할 때 [citation needed]공정의 우선 순위 및 연령과 같은 몇 가지 요인을 고려해야 합니다.
  2. 자원 프리엠프션: 다양한 프로세스에 할당된 자원을 연속적으로 프리엠프션하여 교착 상태가 [15][failed verification]해소될 때까지 다른 프로세스에 할당할 수 있습니다.

예방

주요 기사:교착 방지 알고리즘
(가) 선착순 정책에 따라 하나의 자원을 두고 경합하는 2개의 프로세스. (나) 양쪽 프로세스가 동시에 자원을 잠글 때 데드록이 발생하며 (다) 잠금 메커니즘의 대칭을 깨면 데드록이 해소된다.(라) 잠금 메커니즘의 대칭을 깨면 데드록이 방지된다.

데드록 방지는 4가지 코프만 조건 중 하나가 발생하는 것을 방지함으로써 작동합니다.

  • 상호 제외 조건을 제거하면 어떤 프로세스도 리소스에 독점적으로 액세스할 수 없습니다.이는 스풀링할 수 없는 리소스에서는 불가능한 것으로 판명되었습니다.그러나 스풀된 리소스를 사용하더라도 교착 상태가 발생할 수 있습니다.상호 배제를 방지하는 알고리즘을 논블로킹 동기화 알고리즘이라고 합니다.
  • 보류 및 대기 또는 리소스 보류 조건은 프로세스가 시작 전(또는 특정 작업 세트를 시작하기 전에) 필요한 모든 리소스를 요구하도록 요구함으로써 제거할 수 있습니다.이러한 고급 지식은 종종 충족시키기 어렵고, 어떤 경우에도 자원의 비효율적인 사용입니다.또 다른 방법은 프로세스가 리소스가 없는 경우에만 리소스를 요구하도록 하는 것입니다.첫 번째로 현재 보유하고 있는 리소스를 모두 해제한 후 필요한 리소스를 모두 처음부터 요청해야 합니다.이것 또한 종종 비현실적이다.자원이 할당되어 장기간 사용되지 않을 수 있기 때문입니다.또, 인기 있는 자원을 필요로 하는 프로세스는 무기한 대기할 필요가 있는 경우가 있습니다.이러한 자원은 항상 일부 프로세스에 할당되어 자원 [16]부족을 초래할 수 있기 때문입니다.(토큰의 시리얼화등의 알고리즘은, all-or-none 알고리즘이라고 불립니다).
  • 또한 프로세스가 일정 시간 동안 리소스를 보유할 수 있어야 하거나 처리 결과가 일관되지 않거나 슬래싱이 발생할 수 있으므로 프리엠프션 조건이 까다롭거나 회피하기 어려울 수 있습니다.단, 프리엠프션을 강제할 수 없는 경우 priority 알고리즘에 방해가 될 수 있습니다."잠금된" 자원의 프리엠프션은 일반적으로 롤백을 의미하며 오버헤드가 매우 높기 때문에 피해야 합니다.프리엠프션을 가능하게 하는 알고리즘에는 록프리 및 대기프리 알고리즘과 낙관적인 동시성 제어가 있습니다.일부 리소스를 보유하고 있는 프로세스와 즉시 할당할 수 없는 다른 리소스에 대한 요구가 있을 경우 해당 프로세스의 현재 보유하고 있는 리소스를 모두 해제하여 이 조건을 제거할 수 있습니다.
  • 마지막 조건은 순환 대기 조건입니다.순환 대기를 회피하는 방법으로는 중요한 섹션에서의 인터럽트를 무효로 하거나 계층을 사용하여 자원의 부분 순서를 결정하는 방법이 있습니다.명확한 계층이 존재하지 않는 경우 자원의 메모리 주소까지 사용하여 순서를 결정하고 [4]열거의 증가 순서로 자원을 요구한다.Dijkstra의 솔루션을 사용할 수도 있습니다.

교착 상태 회피

데드록 방지와 마찬가지로 데드록 회피 접근법은 시스템에서 데드록이 발생하지 않도록 합니다.'데드록 회피'라는 용어는 언어적 맥락에서 '데드록 방지'에 매우 가까운 것으로 보이지만 교착 처리의 맥락에서는 매우 다르다.데드록 회피는 예방에서 볼 수 있는 어떤 조건도 부과하지 않지만, 여기서는 각 자원 요구를 신중하게 분석하여 데드록의 원인이 되지 않고 안전하게 이행할 수 있는지 확인합니다.

교착 상태 회피는 프로세스가 수명 동안 요구하고 사용하는 리소스에 대한 추가 정보를 운영 체제에 미리 제공해야 합니다.데드록 회피 알고리즘은 요청된 리소스가 할당될 경우 향후 데드록이 발생할 가능성이 없음을 조사하여 모든 요청을 분석합니다.이 접근법의 단점은 향후 자원 요구 방법에 대한 정보를 사전에 요구하는 것입니다.가장 많이 사용되는 교착 방지 알고리즘 중 하나는 Banker [17]알고리즘입니다.

라이브록

"Livelock"은 여기서 리다이렉트 됩니다.비디오 게임에 대해서는 Livelock(비디오 게임)을 참조하십시오.

라이브록은 교착상태와 비슷하지만 라이브록에 관련된 프로세스의 상태는 서로에 대해 끊임없이 변화하며 진행되지 않습니다.

이 용어는 에드워드 A에 의해 만들어졌다. Ashcroft는 1975년[18] 항공 예약 [19]시스템 검사에 관한 논문을 발표했다.Livelock은 자원 부족의 특수한 경우입니다.일반적인 정의에서는 특정 프로세스가 [20]진행되지 않고 있다고만 기술되어 있습니다.

Livelock은 교착 상태를 감지하고 복구하는 일부 알고리즘의 위험입니다.여러 프로세스가 액션을 실행하는 경우 교착 상태 검출 알고리즘이 반복적으로 트리거될 수 있습니다.이것은, 1개의 프로세스(임의 또는 우선순위에 의해서 선택)만이 [21]액션을 실행하도록 하는 것으로 회피할 수 있습니다.

분산 교착 상태

분산 트랜잭션 또는 동시성 제어가 사용되는 경우 분산 시스템에서 분산 교착 상태가 발생할 수 있습니다.

분산 교착 상태는 교착 상태 디텍터의 로컬 대기 그래프에서 글로벌 대기 그래프를 구성하거나 에지 추적과 같은 분산 알고리즘을 통해 탐지할 수 있습니다.

팬텀 데드록은 시스템 내부 지연으로 인해 분산 시스템에서 잘못 감지되었지만 실제로 존재하지 않는 데드록입니다.

예를 들어 프로세스가 리소스 R1을 해제하고 R2에 대한 요구를 발행했을 때 첫 번째 메시지가 손실되거나 지연된 경우 코디네이터(데드록 검출기)가 데드록(R1이 있는 동안 R2에 대한 요구가 데드록의 원인이 되는 경우)을 잘못 결론지을 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. p. 716. ISBN 978-0-273-76059-7.
  2. ^ Padua, David (2011). Encyclopedia of Parallel Computing. Springer. p. 524. ISBN 9780387097657. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  3. ^ Falsafi, Babak; Midkiff, Samuel; Dennis, JackB; Dennis, JackB; Ghoting, Amol; Campbell, Roy H; Klausecker, Christof; Kranzlmüller, Dieter; Emer, Joel; Fossum, Tryggve; Smith, Burton; Philippe, Bernard; Sameh, Ahmed; Irigoin, François; Feautrier, Paul; Praun, Christoph von; Bocchino, Robert L.; Snir, Marc; George, Thomas; Sarin, Vivek; Jann, Joefon (2011). "Deadlocks". Encyclopedia of Parallel Computing. Boston, MA: Springer US. pp. 524–527. doi:10.1007/978-0-387-09766-4_282. ISBN 978-0-387-09765-7. A deadlock is a condition that may happen in a system composed of multiple processes that can access shared resources. A deadlock is said to occur when two or more processes are waiting for each other to release a resource. None of the processes can make any progress.
  4. ^ a b c Silberschatz, Abraham (2006). Operating System Principles (7th ed.). Wiley-India. p. 237. ISBN 9788126509621. Archived from the original on 25 January 2022. Retrieved 16 October 2020.
  5. ^ Schneider, G. Michael (2009). Invitation to Computer Science. Cengage Learning. p. 271. ISBN 978-0324788594. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  6. ^ Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 239. ISBN 9788126509621. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  7. ^ Operating System Concepts. Wiley. 2012. p. 319. ISBN 978-1-118-06333-0.
  8. ^ "ECS 150 Spring 1999: Four Necessary and Sufficient Conditions for Deadlock". nob.cs.ucdavis.edu. Archived from the original on 29 April 2018. Retrieved 29 April 2018.
  9. ^ a b c Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill Education. p. 446. ISBN 9780070145894. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  10. ^ "Operating Systems: Deadlocks". www.cs.uic.edu. Archived from the original on 28 May 2020. Retrieved 25 April 2020. If a resource category contains more than one instance then the presence of a cycle in the resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one. Consider, for example, Figures 7.3 and 7.4 below:
  11. ^ Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 237. ISBN 9788126509621. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  12. ^ a b Stuart, Brian L. (2008). Principles of operating systems (1st ed.). Cengage Learning. p. 446. ISBN 9781418837693. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  13. ^ a b Tanenbaum, Andrew S. (1995). Distributed Operating Systems (1st ed.). Pearson Education. p. 117. ISBN 9788177581799. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  14. ^ "Preface - Real-Time Interrupt-driven Concurrency". Archived from the original on 18 September 2020. Retrieved 1 October 2020.
  15. ^ "IBM Knowledge Center". www.ibm.com. Archived from the original on 19 March 2017. Retrieved 29 April 2018.
  16. ^ Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 244. ISBN 9788126509621. Archived from the original on 18 April 2021. Retrieved 16 October 2020.
  17. ^ "Deadlock Avoidance Algorithms in Operating System (OS)". Electronics Mind. 26 January 2022.
  18. ^ Ashcroft, E.A. (1975). "Proving assertions about parallel programs". Journal of Computer and System Sciences. 10: 110–135. doi:10.1016/S0022-0000(75)80018-3.
  19. ^ Kwong, Y. S. (1979). "On the absence of livelocks in parallel programs". Semantics of Concurrent Computation. Lecture Notes in Computer Science. Vol. 70. pp. 172–190. doi:10.1007/BFb0022469. ISBN 3-540-09511-X.
  20. ^ Anderson, James H.; Yong-jik Kim (2001). "Shared-memory mutual exclusion: Major research trends since 1986". Archived from the original on 25 May 2006.
  21. ^ Zöbel, Dieter (October 1983). "The Deadlock problem: a classifying bibliography". ACM SIGOPS Operating Systems Review. 17 (4): 6–15. doi:10.1145/850752.850753. ISSN 0163-5980. S2CID 38901737.

추가 정보

외부 링크