동시성(컴퓨터 과학)

Concurrency (computer science)
보다 실용적인 설명은 동시 컴퓨팅을 참조하십시오.
다른 의미는 동시성을 참조하십시오.
동시성과 자원 공유에 관한 고전적인 문제인 "식사 철학자들"

컴퓨터 과학에서 동시성은 프로그램, 알고리즘 또는 문제의 다른 부분이나 단위가 최종 결과에 영향을 미치지 않고 순서나 부분 순서로 실행될 수 있는 능력입니다.이를 통해 동시 유닛을 병렬로 실행할 수 있으므로 멀티프로세서 및 멀티코어 시스템에서 전체적인 실행 속도를 크게 향상시킬 수 있습니다.좀 더 기술적인 용어로 동시성은 프로그램, 알고리즘 또는 문제를 순서에 구애받지 않거나 부분적으로 정렬된 구성 요소 또는 [1]계산 단위로 분해하는 것을 말합니다.

Rob Pike에 따르면 동시성은 독립적으로 [2]연산을 실행하는 구성이며 동시성은 병렬화가 아닙니다. 동시성은 많은 일을 한꺼번에 처리하는 것이지만 병렬화는 많은 일을 한꺼번에 수행하는 것입니다.동시성은 구조에 관한 것이고 병렬성은 실행에 관한 것입니다. 동시성은 병렬화할 수 있는([3]필수는 아니지만) 문제를 해결하기 위한 솔루션을 구성하는 방법을 제공합니다.

Petri nets, process calci, 병렬 랜덤 액세스 머신 모델, 액터 모델 및 Reo Coordination Language를 포함한 다수의 수학 모델이 일반 동시 연산을 위해 개발되었습니다.

역사

Leslie Lamport(2015)가 언급했듯이, "동시 프로그램의 동시 실행은 수년간 고려되어 왔지만 동시 실행의 컴퓨터 과학은 상호 배제 문제를 도입한 1965년 에즈거 다이크스트라의 논문에서 시작되었다.이후 수십 년 동안 동시성, 특히 분산 시스템에 대한 관심이 크게 증가했습니다.이 분야의 기원을 돌이켜보면, 눈에 띄는 것은 에즈거 다이크스트라가 맡은 근본적인 역할이다.[4]

문제들

동시 시스템에서의 연산은 실행 중에 서로 상호작용할 수 있기 때문에 시스템 내에서 가능한 실행 경로의 수가 매우 클 수 있으며 결과도 불확실할 수 있다.공유 자원의 동시 사용은 교착 상태나 자원 [5]부족 등의 문제를 야기하는 불확실성의 원인이 될 수 있습니다.

동시 시스템 설계에서는 대부분의 경우 응답 시간을 최소화하고 [6]스루풋을 최대화하기 위해 실행, 데이터 교환, 메모리 할당 및 실행 일정을 조정하는 신뢰할 수 있는 기술을 찾아야 합니다.

이론.

동시성 이론은 이론 컴퓨터 과학에서 활발한 연구 분야였다.첫 번째 제안 중 하나는 1960년대 초 칼 아담 페트리의 페트리 그물에 대한 중요한 연구였다.이후 수년간 동시성에 대한 모델링과 추론을 위해 다양한 형식주의가 개발되었습니다.

모델

동시 시스템을 모델링하고 이해하기 위한 다음과 [7]같은 다양한 형식이 개발되었습니다.

이러한 동시성 모델 중 일부는 주로 추론 및 사양을 지원하기 위한 것이며, 다른 모델들은 동시 시스템의 설계, 구현, 입증, 테스트 및 시뮬레이션을 포함한 전체 개발 주기 동안 사용될 수 있습니다.이들 중 일부는 메시지 전달에 기반하고 있는 반면 다른 일부는 동시 전달에 대한 메커니즘이 있습니다.

다른 동시성 모델의 확산은 일부 연구자들이 이러한 다른 이론 모델을 통합하는 방법을 개발하도록 동기를 부여했다.예를 들어 이 대통령과 Sangiovanni-Vincentelli은 소위"tagged-signal"모델, 닐센, Sassone, Winskel 그 범주 이론도 비슷한 unifie을 제공하는 데 사용할 수 있다는 것을 보여 준다 concurrency,[9]의 다른 모델의denotational 의미를 정의하는 공동 이해의 틀을 제공하는 데 사용할 수 있다는 것을 입증하였다.d다양한 [10]모델에 대한 이해

액터 모델의 동시성 표현 정리는 외부로부터 통신을 수신하지 않는다는 의미에서 닫힌 동시 시스템을 표현하는 매우 일반적인 방법을 제공합니다.(다른 동시성 시스템, 예를 들어 프로세스 계산은 2단계 커밋 프로토콜을 사용하여 액터 모델에서 모델링할 수 있습니다.)[11]닫힌 체계에 의해 나타나는 수학적 표현S는 다음과 같이 [12]S에 대한 표현(의미)을 구성하기 위해 동작 근사 함수 진행을S 사용하여 Sθ라고 불리는 초기 동작에서 점점 더 나은 근사치를 구성합니다.

≡i∈ω의Si 진행())S을 나타냅니다S.

이러한 방법으로 S는 가능한 모든 동작의 관점에서 수학적으로 특징지을 수 있습니다.

로직스

동시 시스템에 대한 추론을 돕기 위해 다양한 유형의 시간[13] 논리를 사용할 수 있습니다.선형 시간 논리 및 계산 트리 논리와 같은 이러한 로직 중 일부는 동시 시스템이 통과할 수 있는 상태의 시퀀스에 대한 주장을 할 수 있도록 합니다.작용 계산 나무 논리, 헤네시-밀너 논리 및 Lamport의 시간적 작용 논리와 같은 다른 것들은 작용의 순서(상태의 변화)로부터 주장을 구축한다.이러한 로직의 주된 적용은 동시 시스템의 [5]사양서 작성에 있습니다.

연습

동시 프로그래밍은 동시 시스템을 구현하는 데 사용되는 프로그래밍 언어와 알고리즘을 포함합니다.병렬 프로그래밍은 일반적으로 병렬 프로그래밍보다 더 일반적인 것으로 간주되는데, 병렬 시스템은 일반적으로 사전 정의되고 잘 구조화된 통신 패턴을 가지고 있는 반면, 병렬 프로그래밍은 임의적이고 동적인 통신 패턴을 포함할 수 있기 때문입니다.동시 프로그래밍의 기본 목표에는 정확성, 성능 및 견고성이 포함됩니다.운영체제나 데이터베이스 관리시스템과 같은 동시 시스템은 일반적으로 장애로부터의 자동 복구를 포함하여 무기한 작동하도록 설계되어 있으며 예기치 않게 종료되지 않습니다(동시 제어 참조).일부 동시 시스템은 투명한 동시 실행 형태를 구현합니다. 이 경우 동시 계산 엔티티는 단일 리소스를 위해 경쟁하고 공유할 수 있지만, 이 경쟁과 공유의 복잡성은 프로그래머로부터 보호됩니다.

일반적으로 동시 시스템은 공유 리소스를 사용하기 때문에 이러한 리소스에 대한 액세스를 제어하기 위해 구현 어딘가에 아비터를 포함해야 합니다(대개 기본 하드웨어에 포함).중재자의 사용은 정확성과 성능을 포함한 실무에 중요한 영향을 미치는 동시 계산의 불확정 가능성을 야기한다.예를 들어, 조정은 무한 비결정론을 도입하여 상태 공간에서 폭발을 일으키고 모델이 무한히 많은 상태를 가질 수 있기 때문에 모델 확인에 문제를 제기합니다.

일부 동시 프로그래밍 모델에는 코프로세스와 결정론적 동시성이 포함됩니다.이러한 모델에서 제어 스레드는 시스템 또는 다른 프로세스 중 하나에 대해 명시적으로 타임라이스를 양보합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Lamport, Leslie (July 1978). "Time, Clocks, and the Ordering of Events in a Distributed System" (PDF). Communications of the ACM. 21 (7): 558–565. doi:10.1145/359545.359563. S2CID 215822405. Retrieved 4 February 2016.
  2. ^ "Go Concurrency Patterns". talks.golang.org. Retrieved 2021-04-08.
  3. ^ "Concurrency is not Parallelism". talks.golang.org. Retrieved 2021-04-08.
  4. ^ Lamport, Leslie. "Turing Lecture: The Computer Science of Concurrency: The Early Years (Communications of the ACM, Vol. 58 No. 6, June 2015)". ACM. Retrieved 22 Mar 2017.
  5. ^ a b Cleaveland, Rance; Scott Smolka (December 1996). "Strategic Directions in Concurrency Research". ACM Computing Surveys. 28 (4): 607. doi:10.1145/242223.242252. S2CID 13264261.
  6. ^ Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (August 2010). Parallel Programming with Microsoft .NET. Microsoft Press. ISBN 978-0-7356-5159-3.
  7. ^ Filman, Robert; Daniel Friedman (1984). Coordinated Computing - Tools and Techniques for Distributed Software. McGraw-Hill. ISBN 978-0-07-022439-1.
  8. ^ Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons.
  9. ^ Lee, Edward; Alberto Sangiovanni-Vincentelli (December 1998). "A Framework for Comparing Models of Computation" (PDF). IEEE Transactions on CAD. 17 (12): 1217–1229. doi:10.1109/43.736561.
  10. ^ Mogens Nielsen; Vladimiro Sassone; Glynn Winskel (1993). "Relationships Between Models of Concurrency". REX School/Symposium.
  11. ^ 프레데릭 크나베Choice PARLE 1992를 사용한 채널 기반 통신을 위한 분산 프로토콜.
  12. ^ William Clinger (June 1981). "Foundations of Actor Semantics". Mathematics Doctoral Dissertation. MIT. hdl:1721.1/6935. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  13. ^ Roscoe, Colin (2001). Modal and Temporal Properties of Processes. Springer. ISBN 978-0-387-98717-0.

추가 정보

  • Lynch, Nancy A. (1996). Distributed Algorithms. Morgan Kaufmann. ISBN 978-1-55860-348-6.
  • Tanenbaum, Andrew S.; Van Steen, Maarten (2002). Distributed Systems: Principles and Paradigms. Prentice Hall. ISBN 978-0-13-088893-8.
  • Kurki-Suonio, Reino (2005). A Practical Theory of Reactive Systems. Springer. ISBN 978-3-540-23342-8.
  • Garg, Vijay K. (2002). Elements of Distributed Computing. Wiley-IEEE Press. ISBN 978-0-471-03600-5.
  • Magee, Jeff; Kramer, Jeff (2006). Concurrency: State Models and Java Programming. Wiley. ISBN 978-0-470-09355-9.
  • 디스테파노, S, & 브루노, D. (2015년)분산 시스템의 정량적 평가: 방법론 및 기술 (제1판)서머셋: John Wiley & Sons Inc.ISBN 9781119131144
  • 미국 바타차리야(2013;2014;)신호 처리 시스템 핸드북 (제2; 2; 2013년 제2; 제2판)뉴욕, 뉴욕: 스프링어.10.1007/978-1-4614-6859-2 ISBN 9781461468592
  • 월터, K. (2012; 2014;)컴퓨터 시스템의 복원력 평가 및 평가 (1)aufl.;1;ed.)런던베를린: 스프링거.ISBN 9783642290329

외부 링크