동시 컴퓨팅

Concurrent computing

동시컴퓨팅이란컴퓨팅의일종으로여러연산이순차적으로실행되는것이아니라중복기간에동시에실행되어하나의연산이다음시작전에완료됩니다.

이것은 프로그램, 컴퓨터, 네트워크에 관계없이 각 프로세스에 대해 별도의 실행 지점 또는 "제어 스레드"가 있는 시스템의 속성입니다.동시 시스템은 다른 모든 [1]연산이 완료될 때까지 기다리지 않고 연산이 진행될 수 있는 시스템입니다.

동시 컴퓨팅은 모듈러 프로그래밍의 한 형태입니다. 패러다임에서 전체적인 계산은 동시에 실행될 수 있는 서브컴퓨터에 반영된다.동시 컴퓨팅 분야의 선구자에는 Edsger Dijkstra, Per Brinch Hansen, C.A.R. Hoare [2]등이 있습니다.

서론

병행 컴퓨팅의 개념은 관련성이 있지만 서로 다른 [3][4]병행 컴퓨팅의 개념과 혼동되는 경우가 많습니다.다만, 양쪽 모두 「같은 기간에 실행되는 복수의 프로세스」라고 말할 수 있습니다.병렬 컴퓨팅에서는 계산 속도를 높이기 위해 멀티프로세서 머신의 개별 프로세서에서와 같은 물리적인 순간에 실행이 이루어집니다.단일 클럭 [a]사이클 동안 한 번에 한 번만 계산되므로 병렬 컴퓨팅은 (1코어) 단일 프로세서에서는 불가능합니다.반면 동시 컴퓨팅은 프로세스 수명이 겹치는 것으로 구성되지만 동시에 실행할 필요는 없습니다.여기서의 목적은, 복수의 클라이언트가 동시에 서버에 액세스 하는 등, 동시에 발생하는 외부 세계의 프로세스를 모델화하는 것입니다.소프트웨어 시스템을 복수의 동시 통신 부품으로 구성함으로써 부품을 [5]: 1 병렬로 실행할 수 있는지 여부에 관계없이 복잡성에 대처하는 데 도움이 될 수 있다.

예를 들어 동시 프로세스는 시분할 슬라이스를 통해 각 프로세스의 실행 단계를 인터리빙함으로써 하나의 코어로 실행할 수 있습니다.한 번에 1개의 프로세스만 실행되며 타임 슬라이스 중에 프로세스가 완료되지 않으면 일시 중지되고 다른 프로세스가 시작 또는 재개되며 나중에 원래 프로세스가 재개됩니다.이와 같이 여러 프로세스가 한 번에 실행되는 중간 단계이지만,[citation needed] 그 순간에는 하나의 프로세스만 실행됩니다.

동시연산은 예를 들어 각 프로세스를 별도의 프로세서 또는 프로세서 코어에 할당하거나 네트워크 전체에 연산을 분배함으로써 [3][6]병렬로 실행할 수 있다.그러나 일반적으로 병렬 프로그래밍을 위한 언어, 도구 및 기술은 동시 프로그래밍에 적합하지 않을 수 있으며, [citation needed]그 반대의 경우도 마찬가지입니다.

동시 시스템의 작업이 실행되는 정확한 타이밍은 예약에 따라 다르며 작업을 항상 동시에 실행할 필요는 없습니다.예를 들어 T1과 T2의 [citation needed]2가지 태스크가 있습니다.

  • T1은 T2 이전 또는 그 반대(시리얼 및 시퀀셜)에 실행 및 종료할 수 있습니다.
  • T1과 T2를 번갈아 실행할 수 있습니다(시리얼과 동시).
  • T1과 T2를 동시에 실행할 수 있습니다(병렬 및 동시).

"순차적"이라는 단어는 "동시적"과 "병렬적" 모두에 대한 반의어로 사용됩니다. 이 두 단어가 명시적으로 구별될 경우, 동시/순차적병렬/직렬이 반대 [7]쌍으로 사용됩니다.작업이 인터리빙 없이 한 번에 하나씩(시리얼로 병렬 처리 없음) 실행되는 스케줄을 시리얼 스케줄이라고 합니다.연속적으로 스케줄링할 수 있는 일련의 태스크는 직렬화할 수 있으므로 동시성 제어가 [citation needed]단순해집니다.

공유 리소스에 대한 액세스 조정

동시 프로그램을 설계할 때 가장 중요한 과제는 동시성 제어입니다. 즉, 서로 다른 계산 실행 간의 상호 작용 또는 통신의 올바른 시퀀스를 [6]보장하고 실행 간에 공유되는 리소스에 대한 액세스를 조정하는 것입니다.잠재적인 문제에는 경쟁 조건, 교착 상태 및 자원 부족포함됩니다.예를 들어 공유 리소스로 표시되는 당좌예금 계정에서 인출하려면 다음 알고리즘을 고려하십시오.balance:

부울 철수하다(인트 철수) {     한다면 (균형. >= 철수)     {         균형. -= 철수;         돌아가다 진실의;     }      돌아가다 거짓의; } 

가정하다balance = 5002개의 동시 스레드가 콜을 발신한다.withdraw(300)그리고.withdraw(350)양쪽 동작의 3번 회선이 5번 회선보다 먼저 실행되면 양쪽 동작은balance >= withdrawal까지 평가하다.true인출금액을 차감하는 작업이 진행됩니다.그러나 두 과정 모두 인출이 이루어지기 때문에 인출된 총액은 원래 잔액보다 많아지게 됩니다.이러한 공유 자원의 문제는 동시성 제어 또는 논블로킹알고리즘을 사용하면 편리합니다.

이점

동시 컴퓨팅의 장점은 다음과 같습니다.

  • 프로그램 throughput 향상—동시 프로그램의 병렬 실행으로 주어진 시간 내에 완료된 작업 수가 Gustafson의 법칙에 따라 프로세서 수에 비례하여 증가할 수 있습니다.
  • 입력/출력에 대한 높은 응답성—입력/출력을 많이 사용하는 프로그램은 대부분 입력 또는 출력 작업이 완료될 때까지 기다립니다.동시 프로그래밍을 사용하면 다른 [citation needed]작업에 사용할 대기 시간을 확보할 수 있습니다.
  • 보다 적절한 프로그램 구조—일부 문제와 문제 영역은 동시 작업 또는 [citation needed]프로세스로 표현하기에 적합합니다.

모델

1962년에 도입된 Petri nets는 동시 실행 규칙을 코드화하기 위한 초기 시도였다.데이터 플로우 이론은 나중에 이를 기반으로 구축되었으며, 데이터 플로우 아키텍처는 데이터 플로우 이론의 아이디어를 물리적으로 구현하기 위해 만들어졌습니다.1970년대 후반부터, 통신 시스템 미적분(CCS)과 통신 순차 프로세스(CSP)와 같은 과정 계산은 상호작용하는 구성요소로 구성된 시스템에 대한 대수적 추론을 가능하게 하기 위해 개발되었다.θ-calculus는 동적 토폴로지에 대한 추론 기능을 추가했다.

입출력 오토마타는 1987년에 도입되었습니다.

Lamport의 TLA+와 같은 로직과 트레이스나 Actor 이벤트 다이어그램과 같은 수학적 모델도 동시 시스템의 동작을 기술하기 위해 개발되었습니다.

소프트웨어 트랜잭션 메모리는 데이터베이스 이론에서 원자 트랜잭션의 개념을 차용하여 메모리 액세스에 적용합니다.

일관성 모델

동시 프로그래밍 언어와 멀티프로세서 프로그램에는 일관성 모델(메모리 모델이라고도 함)이 있어야 합니다.일관성 모델은 컴퓨터 메모리에서 작업이 발생하는 방법과 결과가 생성되는 방법에 대한 규칙을 정의합니다.

최초의 일관성 모델 중 하나는 Leslie Lamport의 순차적 일관성 모델입니다.순차적 일관성은 순차적 프로그램과 동일한 결과를 생성하는 프로그램의 속성입니다.구체적으로는, 「모든 프로세서의 조작이 순서적으로 실행된 것과 같은 실행 결과가 되어,[8] 각각의 프로세서의 조작이 그 프로그램에 의해 지정된 순서로 이 순서로 나타나는 경우」의 경우, 프로그램은 순차적으로 정합성이 있다.

실행

각 연산처리를 운영체제 프로세스로 구현하거나 단일 운영체제 프로세스 에서 스레드 세트로 구현하거나 여러 가지 다른 방법을 사용하여 동시 프로그램을 구현할 수 있습니다.

상호작용과 커뮤니케이션

일부 동시 컴퓨팅 시스템에서는 동시 컴포넌트 간의 통신이 프로그래머로부터 숨겨져 있는 반면(예를 들어 미래를 사용하여), 다른 시스템에서는 명시적으로 처리되어야 합니다.명시적 통신은 두 가지 클래스로 나눌 수 있습니다.

공유 메모리 통신
동시 컴포넌트는 공유 메모리 위치(Java 및 C#에 의해 예시)의 내용을 변경하여 통신합니다.이러한 동시 프로그래밍 스타일에서는 일반적으로 스레드 간에 조정하기 위해 어떤 형태의 잠금(: 뮤텍스, 세마포어 또는 모니터)을 사용해야 합니다.이들 중 하나를 적절히 구현하는 프로그램은 스레드 세이프라고 불립니다.
메시지 전달 통신
동시 컴포넌트는 메시지를 교환함으로써 통신합니다(MPI, Go, Scala, Erlang 및 occam).메시지 교환은 비동기적으로 수행되거나 메시지가 수신될 때까지 발신인이 차단하는 동기식 "rendezvous" 스타일을 사용할 수 있습니다.비동기 메시지 전달은 신뢰할 수도 있고 신뢰할 수도 없습니다('보내고 기도'라고도 함).메시지 전달 동시성은 공유 메모리 동시성보다 훨씬 쉽게 추론할 수 있는 경향이 있으며 일반적으로 더 강력한 동시 프로그래밍 [citation needed]형태로 간주됩니다.메시지 전달 시스템을 이해하고 분석하기 위한 다양한 수학적 이론이 제공되며, 여기에는 액터 모델, 다양한 프로세스 계산 등이 포함됩니다.메시지 전달은 공유 메모리 캐시 일관성의 유무에 관계없이 대칭형 멀티프로세싱을 통해 효율적으로 구현할 수 있습니다.

공유 메모리와 메시지 전달 동시성은 성능 특성이 다릅니다.일반적으로 (항상 그렇지는 않지만) 메시지 전달 시스템에서는 프로세스별 메모리 오버헤드와 태스크스위칭 오버헤드는 낮지만 메시지 전달 오버헤드는 프로시저 콜보다 커집니다.이러한 차이는 종종 다른 성능 요소에 의해 압도됩니다.

역사

동시 컴퓨팅은 19세기부터 20세기 초반까지 철도 및 전신에 관한 초기 작업에서 발전했으며, 세마포어 등 일부 용어는 이 시대로 거슬러 올라갑니다.이는 동일한 철도 시스템에서 여러 열차를 처리하는 방법 (충돌을 피하고 효율성을 극대화하는 방법)과 주어진 와이어 세트를 통한 다중 전송 (효율성 향상)에 대한 문제를 해결하기 위해 제기되었습니다 (1870년대).

동시 알고리즘에 대한 학술적 연구는 1960년대에 시작되었으며, Dijkstra(1965)상호 [9]배제를 식별하고 해결하는 이 분야의 첫 번째 논문으로 인정받았다.

유병률

동시성은 컴퓨팅에 널리 퍼져 있으며, 단일 칩 상의 낮은 수준의 하드웨어에서 전세계 네트워크에 이르기까지 발생합니다.예를 들면 다음과 같습니다.

프로그래밍 언어 수준:

운영 체제 수준:

네트워크 레벨에서는, 네트워크 시스템은 다른 디바이스로 구성되어 있기 때문에, 그 성질상, 일반적으로 동시입니다.

동시 프로그래밍을 지원하는 언어

동시 프로그래밍 언어는 동시성을 위해 언어 구조를 사용하는 프로그래밍 언어입니다.이러한 구성에는 멀티스레딩, 분산 컴퓨팅 지원, 메시지 전달, 공유 리소스(공유 메모리 포함) 또는 미래와 약속이 포함됩니다.이러한 언어는 동시성 지향 언어 또는 동시성 지향 프로그래밍 언어(COPL)[10]로 설명되기도 합니다.

현재 동시성을 위한 특정 구조를 가진 가장 일반적으로 사용되는 프로그래밍 언어는 Java와 C#입니다.이들 언어 모두 기본적으로 공유 메모리 동시성 모델을 사용하며 모니터에 의해 잠금이 제공됩니다(단, 메시지 전달 모델은 기본 공유 메모리 모델 위에 구현될 수 있고 구현될 수도 있습니다).메시지 전달 동시성 모델을 사용하는 언어 중 Erlang은 아마도 [citation needed]현재 업계에서 가장 널리 사용되는 언어일 것입니다.

많은 동시 프로그래밍 언어는 실제 사용 언어라기보다는 연구 언어(Pict )로 개발되어 왔습니다.하지만, 얼랑, 림보, 오캄같은 언어들은 지난 20년 동안 다양한 시기에 산업적으로 사용되어 왔다.동시 프로그래밍 기능을 사용하거나 제공하는 언어 목록:

  • Ada: 메시지 전달 및 모니터 기반 동시성을 기본적으로 지원하는 범용
  • Alef - 스레드 및 메시지 전달과 동시에 Bell Labs의 Plan 9 이전 버전에서 시스템 프로그래밍을 수행합니다.
  • Alice: 표준 ML로 확장되어 미래를 통한 동시성 지원 추가
  • Ateji PX - --calculus에서 영감을 얻은 병렬 프리미티브를 사용하여 Java로 확장
  • Axum: 액터모델과 를 기반으로 한 도메인 고유의 동시.C-like 구문을 사용하는 NET 공통 언어 런타임
  • BMDFM: 바이너리 모듈러형 DataFlow 머신
  • C++: 표준:: 개요
  • C' (C omega) : 조사를 위해 C#을 확장하고 비동기 통신을 사용합니다.
  • C#: 버전 5.0의 비동기 및 wait 키워드가 도입된 이후 lock, yield를 사용한 동시 컴퓨팅 지원
  • Clojure - Java 플랫폼Lisp의 현대적인 기능적 방언
  • Concurrent Clean - Haskell과 유사한 기능 프로그래밍
  • Concurrent Collections(CnC) - 데이터 흐름과 제어 흐름을 명시적으로 정의함으로써 메모리 모델에 의존하지 않는 암묵적인 병렬 처리를 실현합니다.
  • Concurrent Haskell - 공유 메모리에서 동시 프로세스를 실행하는 느리고 순수한 기능성 언어
  • 동시 ML - 표준 ML 동시 확장
  • 동시 파스칼 - Per Brinch Hansen
  • 카레시
  • D: 동시 프로그래밍을 명시적으로 지원하는 다중 패러다임 시스템 프로그래밍 언어(배우 모델)
  • E: 약속을 사용하여 교착 상태를 방지합니다.
  • ECMAScript: 비동기 조작에 대한 약속을 사용합니다.
  • Eiffel – 계약에 의한 설계 개념을 기반으로 한 SPOCK 메커니즘을 통해 구현
  • Elixir: Erlang VM에서 실행되는 동적 및 기능적 메타 프로그래밍 지원 언어.
  • Erlang: 공유되지 않은 비동기 메시지 전달을 사용합니다.
  • FAUST - 신호 처리를 위해 컴파일러는 OpenMP 또는 특정 워크스틸링 스케줄러를 통한 자동 병렬화를 제공합니다.
  • Fortran동시동시 실행은 Fortran 2008 표준의 일부입니다.
  • Go: CSP를 기반으로 한 동시 프로그래밍 모델을 사용하는 시스템 프로그래밍용
  • Haskell - 동시 및 병렬 기능 프로그래밍[11] 언어
  • Hume - 자동 데이터 프로세스가 동기 채널 패턴 및 메시지 전달에 의해 기술되는 한정된 공간과 시간 환경에 동시에 기능합니다.
  • Io: 배우 기반 동시성
  • Janus: 논리변수, 백채널에 대한 개별 애스커와 텔러를 특징으로 합니다.순전히 선언형입니다.
  • Java: 스레드클래스 또는 Runnable 인터페이스
  • Julia—"동시 프로그래밍 기본 요소:작업, 비동기 대기, 채널"[12]
  • JavaScript: 워커를 통한 브라우저 환경에서의 약속 및 콜백.
  • JoCaml: 동시 및 분산채널 기반의 OCaml 확장으로 프로세스의 Join-Calculus를 구현합니다.
  • Join Java - Java 언어에 기반한 동시 참여
  • Joule: 데이터 플로우 기반, 메시지 전달에 의해 통신합니다.
  • Joyce - Per Brinch Hansen의 CSP 기능을 탑재한 Concurrent Pascal을 기반으로 한 동시, 교육
  • LabVIEW—그래픽, 데이터 흐름, 함수는 그래프 내의 노드, 데이터는 노드 간의 배선, 객체 지향 언어 포함
  • 림보 - Alef와 관련된 Inferno(운영 체제)에서의 시스템 프로그래밍용
  • MultiLisp: 병렬 처리를 지원하도록 확장한 스키마 바리안트
  • 모듈라-2: 시스템프로그래밍용, N별.Pascal의 후속 제품으로 Coroutine에 대한 네이티브 지원
  • Modula-3 - 스레드, 뮤텍스, 조건 변수를 폭넓게 지원하는 Algol 패밀리의 최신 멤버
  • 뉴스큐크 - 채널을 퍼스트 클래스 값으로 하는 조사용, Alef의 전신
  • occam: communication sequential process(CSP; 시퀀셜프로세스)의 영향을 크게 받습니다.
  • Orc크린 대수에 기초한 매우 동시적이고 비결정적
  • Oz-Mozart: 멀티패러다임, 공유 스테이트 및 메시지 전달 동시성 및 미래 지원
  • ParaSail: 객체 지향, 병렬, 포인터 없음, 레이스 조건
  • Pict - 기본적으로 Milner의 µ-calculus 실행 가능 구현
  • Raku는 기본적으로[13] 스레드, 약속 및 채널 클래스를 포함합니다.
  • Python — 스레드 기반 병렬 처리 및 프로세스 기반 병렬 처리 사용
  • Reia: shared-nothing 객체 간에 전달되는 비동기 메시지를 사용합니다.
  • 빨간색/시스템Rebol 기반 시스템 프로그래밍용
  • [Rust] : 시스템프로그래밍용 메시지 패싱과 이동 시멘틱스, 공유 불변 메모리 및 공유 [15]가변 메모리.
  • Scala - 일반적인 프로그래밍 패턴을 간결하고 우아하며 안전한 방법으로 표현하도록 설계된 범용 기능
  • Sequence L - 범용 기능, 주요 설계 목표는 프로그래밍의 용이성, 코드의 명확성, 멀티코어 하드웨어에서의 퍼포먼스를 위한 자동 병렬화이며 레이스 조건으로부터 자유롭습니다.
  • SR: 조사용
  • SuperPascal - Per Brinch HansenConcurrent Pascal과 Joyce를 기반으로 구축한 동시 교육용
  • Unicon: 조사용
  • TNSDL: 전기통신 교환 개발을 위해 비동기 메시지 전달을 사용합니다.
  • VHSIC 하드웨어 기술 언어(VHDL) - IEEE STD-1076
  • XC - XMOS가 개발한 C언어의 일관성 확장 서브셋으로, 프로그램 가능한 I/O용 임베디드 구성체 통신 시퀀셜 프로세스를 기반으로 합니다.

다른 많은 언어들은 위 목록과 거의 비슷한 수준으로 라이브러리 형태의 동시성을 지원합니다.

「 」를 참조해 주세요.

메모들

  1. ^ 이는 파이프라이닝이나 벡터화 명령 등 프로세서코어의 내부 병렬화를 경시하는 것입니다.1코어의 1프로세서 머신은 코프로세서와 같은 병렬 처리를 할 수 있지만 프로세서만으로는 할 수 없습니다.

레퍼런스

  1. ^ 운영체제 개념 제9판, 에이브러햄 실버샤츠."제4장: 스레드"
  2. ^ The Origin of Concurrent Programming. doi:10.1007/978-1-4757-3472-0.
  3. ^ a b Pike, Rob(2012-01-11)"통화는 평행주의가 아니다."Waza 회의, 2012년 1월 11일.http://talks.golang.org/2012/waza.slide(비디오) 및 http://vimeo.com/49718712(비디오)에서 취득.
  4. ^ "Parallelism vs. Concurrency". Haskell Wiki.
  5. ^ Schneider, Fred B. (1997-05-06). On Concurrent Programming. Springer. ISBN 9780387949420.
  6. ^ a b Ben-Ari, Mordechai (2006). Principles of Concurrent and Distributed Programming (2nd ed.). Addison-Wesley. ISBN 978-0-321-31283-9.
  7. ^ 패터슨 & 헤네시 2013, 페이지 503.
  8. ^ Lamport, Leslie (1 September 1979). "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs". IEEE Transactions on Computers. C-28 (9): 690–691. doi:10.1109/TC.1979.1675439. S2CID 5679366.
  9. ^ "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing, retrieved 2009-08-24
  10. ^ Armstrong, Joe (2003). "Making reliable distributed systems in the presence of software errors" (PDF).
  11. ^ 말로, 사이먼 (2013) 해스켈 병렬 및 동시 프로그래밍 : 멀티코어 및 멀티스레드 프로그래밍 ISBN 9781449335946 기술
  12. ^ https://juliacon.talkfunnel.com/2015/21-concurrent-and-parallel-programming-in-julia Julia 동시 및 병렬 프로그래밍
  13. ^ "Concurrency". docs.perl6.org. Retrieved 2017-12-24.
  14. ^ 문서 the Python 표준 라이브러리 document 동시 실행
  15. ^ Blum, Ben (2012). "Typesafe Shared Mutable State". Retrieved 2012-11-14.

원천

  • Patterson, David A.; Hennessy, John L. (2013). Computer Organization and Design: The Hardware/Software Interface. The Morgan Kaufmann Series in Computer Architecture and Design (5 ed.). Morgan Kaufmann. ISBN 978-0-12407886-4.

추가 정보

외부 링크