병행성
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
병행성은 여러 계산 또는 프로세스가 동시에 실행되는 시스템의 특성을 의미한다. 병행 시스템은 불확정성, 교착 상태, 자원 기아와 같은 문제를 야기할 수 있으며, 응답 시간을 최소화하고 처리량을 극대화하기 위해 설계 및 구현된다. 병행성 이론은 페트리 망과 같은 초기 연구를 시작으로 다양한 모델과 논리를 개발해왔으며, 액터 모델, 시간 논리 등이 활용된다. 병렬 컴퓨팅, 멀티스레딩, 동기화 등 여러 관련 개념을 포함하며, 병행 프로그래밍은 정확성, 성능, 강건성을 목표로 한다.
더 읽어볼만한 페이지
- 병행성 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다. - 병행성 - 기아 상태
기아 상태는 컴퓨터 과학에서 프로세스가 필요한 자원을 할당받지 못해 무한정 대기하는 현상으로, 단순한 스케줄링 알고리즘, 우선순위 역전, 교착 상태 등으로 인해 발생하며 시스템 효율성을 저하시키고 작업 완료를 지연시키지만, 에이징 기법과 같은 공정한 스케줄링 알고리즘이나 우선순위 조정으로 해결할 수 있다. - 에츠허르 데이크스트라 - 교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다. - 에츠허르 데이크스트라 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다.
| 병행성 | |
|---|---|
| 개요 | |
| 정의 | 컴퓨터 과학에서, 병행성은 프로그램의 여러 부분이 순서에 관계없이 실행될 수 있음을 의미한다. |
| 목표 | 병렬 시스템을 위한 정확하고 효율적인 계산 모델과 상호 작용 기술을 제공하는 것이다. |
| 특징 | 계산은 여러 개의 동시적인 단계로 나눌 수 있다. 동시적 단계는 병렬로 실행될 수 있다. 여러 에이전트가 계산을 수행하는 경우, 상호 작용은 동기화 및 통신으로 구성된다. |
| 병행성의 형태 | |
| 스레드 | 프로그램의 실행 흐름을 나타내는 기본적인 단위 단일 프로세스 내에서 여러 스레드가 동시에 실행될 수 있다. |
| 프로세스 | 운영 체제로부터 자원을 할당받아 실행되는 독립적인 실행 단위 여러 프로세스가 동시에 실행될 수 있다. |
| 분산 컴퓨팅 | 여러 대의 컴퓨터가 네트워크를 통해 연결되어 작업을 분산 처리하는 방식 각 컴퓨터는 독립적으로 작업을 수행하며, 필요에 따라 서로 통신한다. |
| 병행성 모델 | |
| 액터 모델 | 액터라는 독립적인 객체들 간의 메시지 전달을 통해 병행성을 구현하는 모델 각 액터는 상태, 행동, 메일 주소를 가지며, 메시지를 받으면 자신의 상태를 변경하고 다른 액터에게 메시지를 보낼 수 있다. |
| 프로세스 계산 | 프로세스 간의 상호 작용을 수학적으로 모델링하는 방법 CCS, CSP, π-calculus 등 다양한 종류가 존재한다. |
| 공유 메모리 | 여러 스레드나 프로세스가 공유된 메모리 공간에 접근하여 데이터를 공유하고 상호 작용하는 방식 동기화 메커니즘 (뮤텍스, 세마포어 등)을 사용하여 데이터 경쟁을 방지해야 한다. |
| 데이터 흐름 | 데이터의 흐름에 따라 계산을 수행하는 모델 각 연산은 입력 데이터가 준비되면 실행되고, 결과를 다음 연산으로 전달한다. |
| 페트리 네트 | 시스템의 상태와 상태 변화를 그래프 형태로 표현하는 모델 병행 시스템의 모델링, 검증, 분석에 사용된다. |
| 병행성 제어 | |
| 목적 | 여러 프로세스나 스레드가 공유 자원에 동시에 접근할 때 발생할 수 있는 문제를 해결하고, 데이터의 일관성과 무결성을 유지하는 것 |
| 방법 | 뮤텍스: 상호 배제를 위한 잠금 메커니즘 세마포어: 여러 프로세스나 스레드가 공유 자원에 접근할 수 있는 횟수를 제한하는 메커니즘 모니터: 공유 자원에 대한 접근을 제어하는 추상적인 데이터 타입 배리어: 여러 프로세스나 스레드가 특정 지점에 도달할 때까지 기다리도록 하는 동기화 메커니즘 퓨처와 프라미스: 비동기 연산의 결과를 나중에 얻을 수 있도록 하는 메커니즘 |
| 병행성과 병렬성의 관계 | |
| 병행성 | 프로그램의 논리적인 구조를 나타내는 개념으로, 여러 작업이 동시에 진행될 수 있도록 설계하는 것을 의미한다. |
| 병렬성 | 실제로 여러 작업을 동시에 실행하여 성능을 향상시키는 것을 의미한다. |
| 관계 | 병행성은 병렬성을 구현하기 위한 필요조건이지만, 충분조건은 아니다. 즉, 병행적으로 설계된 프로그램이 반드시 병렬적으로 실행되는 것은 아니다. |
| 병행성 관련 문제 | |
| 데드락 | 여러 프로세스나 스레드가 서로가 점유하고 있는 자원을 기다리면서 무한정 대기하는 상태 데드락은 자원 할당 그래프를 통해 감지하고, 예방, 회피, 탐지 및 복구 등의 방법으로 해결할 수 있다. |
| 레이스 컨디션 | 여러 프로세스나 스레드가 공유 자원에 동시에 접근하여 데이터의 일관성이 깨지는 현상 레이스 컨디션은 동기화 메커니즘을 사용하여 방지할 수 있다. |
| 기아 현상 | 특정 프로세스나 스레드가 자원을 할당받지 못하여 계속해서 대기하는 상태 기아 현상은 공정한 자원 할당 정책을 통해 해결할 수 있다. |
2. 문제
병행 시스템은 여러 계산이 동시에 실행되면서 상호 작용할 수 있기 때문에, 실행 경로가 매우 다양하고 결과 예측이 어려워 불확정성을 띨 수 있다. 공유 자원을 동시에 사용하면 교착 상태, 기아 상태 등의 문제가 발생할 수 있다.[25][7][16]
병행성 이론은 이론 전산학의 주요 연구 분야이다. 1960년대 카를 아담 페트리의 페트리 넷 연구가 이 분야의 초기 제안 중 하나였다. 그 이후 병행성을 모델링하고 추론하기 위한 다양한 형식론이 개발되었다.
병행 시스템 설계 시 응답 시간을 최소화하고 처리량을 최대화하기 위해 실행, 데이터 교환, 메모리 할당, 실행 스케줄링 등을 조정하는 신뢰성 있는 기술이 필요하다.[26][8][17]
3. 이론
3. 1. 모델
병행 시스템을 모델링하고 이해하기 위한 다양한 형식 기법이 개발되었다.[27]
이러한 병행성 모델의 일부는 주로 추론 및 명세 기술을 목적으로 한다. 반면 다른 모델은 개발 주기 전체(병렬 시스템의 설계, 구현, 증명, 테스트, 시뮬레이션)를 지원하는 것을 목적으로 한다.
병행성 모델이 다양하게 등장함에 따라, 일부 연구자들은 이러한 이론 모델들을 통합하는 방법을 모색했다. 예를 들어 Lee와 Sangiovanni-Vincentelli는 다양한 병행성 모델의 지시적 의미론을 정의하는 공통 프레임워크를 제공하고자 "태그된 신호" 모델을 제안했다.[20] 한편, Nielsen, Sassone, Winskel은 범주론이 다양한 모델을 통합적으로 이해하는 데 유효하다고 주장했다.[21]
액터 모델의 동시성 표현 정리는 외부로부터의 통신을 받아들이지 않는다는 의미에서 닫힌 병렬 시스템을 범용적으로 표현하는 방법을 제공한다. 프로세스 계산 등 다른 병행성 시스템은 2상 커밋 프로토콜을 사용하여 액터 모델로 모델링할 수 있다.[22] 닫힌 시스템 S는 초기 거동 ⊥S에 대해 거동 근사 함수 '''progression'''S를 적용함으로써 더 나은 근사를 구축할 수 있으며, S의 수학적 기술(의미)은 다음과 같다.[23]
::'''Denote'''S ≡ ⊔i∈ω '''progression'''Si(⊥S)
이와 같이 하면, S는 모든 가능한 거동으로 수학적으로 특징지어질 수 있다.
3. 2. 논리
다양한 시제 논리[24]가 병행 시스템을 이해하는 데 사용된다. 특히 선형 시상 논리나 계산 트리 논리는 병행 시스템의 각 시점 상태를 확인하는 데 사용 가능하다. ACTL(Action Computational Tree Logic)이나 Hennesy-Miller Logic, 레슬리 램포트의 행동 시간 논리 등은 "액션(상태 변화)"의 순서를 확인할 수 있다. 이러한 논리의 주요 용법은 병행 시스템의 사양을 기술하는 것이다.[16]
4. 관련 개념
- 병렬성: 여러 처리 장치에서 동시 실행되는 것을 의미한다. 병렬성은 여러 CPU 코어에서 작업을 독립적으로 실행하는 반면, 병행성은 여러 코어에서 여러 작업을 관리하며 각 작업을 완료하지 않고 스레드 간을 전환하거나 시간 분할을 수행한다. 프로그램은 병렬성만, 병행성만, 병렬성과 병행성 모두, 또는 둘 다 나타내지 않을 수 있다.
병렬성 대 병행성 - 멀티스레딩 및 멀티프로세싱: 공유 시스템 리소스를 활용하는 방식이다.
- 동기화: 공유 리소스에 대한 접근을 조정하는 것을 의미한다.
- 조정: 병행 작업 간의 상호 작용을 관리하는 것을 의미한다.
- 병행 제어: 데이터 일관성 및 무결성을 보장하는 것을 의미한다.
- 프로세스 간 통신 (IPC): 정보 교환을 촉진하는 것을 의미한다.
5. 실제
병행 프로그래밍은 병행 시스템 구현에 사용되는 프로그래밍 언어와 알고리즘을 포괄한다. 병행 프로그래밍은 일반적으로 병렬 프로그래밍보다 더 광범위하며, 다양한 통신 및 상호 작용 패턴을 다룬다. 병행 프로그래밍의 주요 목표는 정확성, 성능, 강건성이다.[16] 운영 체제 및 데이터베이스 관리 시스템과 같은 병행 시스템은 일반적으로 무기한으로 작동하고 예기치 않게 종료되지 않도록 설계된다. ( 병행 제어 참조) 일부 병행 시스템은 투명한 병행성을 구현하여, 공유 리소스 경쟁 및 공유의 복잡성을 프로그래머로부터 숨긴다.[17]
공유 리소스를 사용하기 때문에 일반적으로 병행 시스템은 해당 리소스에 대한 접근을 제어하기 위해 구현 어딘가에( 종종 기본 하드웨어에서) 중재자의 일부 종류를 포함해야 한다. 중재자의 사용은 병행 계산의 비결정성의 가능성을 도입한다. 예를 들어, 중재는 무제한 비결정성을 도입하여 모델 검사와 관련된 문제를 야기한다.
일부 병행 프로그래밍 모델에는 코프로세스 및 결정적 병행성이 포함된다. 이러한 모델에서 제어 스레드는 시스템 또는 다른 프로세스에 명시적으로 타임 슬라이스를 양보한다.
참조
[1]
서적
Operating System Concepts
Wiley
2008-07-29
[2]
서적
Computer Organization and Design: The Hardware/Software Interface
Morgan Kaufmann
2012
[3]
서적
Distributed Systems: Concepts and Design
Pearson
2012
[4]
서적
Parallel Computing: Theory and Practice
McGraw-Hill
1994
[5]
서적
Parallel and Distributed Computing Handbook
[6]
서적
Parallel and Concurrent Programming in Haskell
O'Reilly Media
[7]
간행물
Strategic Directions in Concurrency Research
1996-12
[8]
서적
Parallel Programming with Microsoft .NET
http://msdn.microsof[...]
Microsoft Press
2010-08
[9]
서적
Coordinated Computing - Tools and Techniques for Distributed Software
https://archive.org/[...]
McGraw-Hill
[10]
서적
Practical PRAM Programming
John Wiley and Sons
[11]
간행물
A Framework for Comparing Models of Computation
http://ptolemy.eecs.[...]
1998-12
[12]
컨퍼런스
Relationships Between Models of Concurrency
http://citeseer.ist.[...]
[13]
문서
A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992
[14]
간행물
Foundations of Actor Semantics
MIT
1981-06
[15]
서적
Modal and Temporal Properties of Processes
Springer
[16]
간행물
Strategic Directions in Concurrency Research
https://doi.org/10.1[...]
1996-12
[17]
서적
Parallel Programming with Microsoft .NET
http://msdn.microsof[...]
Microsoft Press
[18]
서적
Coordinated Computing - Tools and Techniques for Distributed Software
http://home.comcast.[...]
McGraw-Hill
[19]
서적
Practical PRAM Programming
John Wiley and Sons
[20]
간행물
A Framework for Comparing Models of Computation
1998-12
[21]
컨퍼런스
Relationships Between Models of Concurrency
http://eprints.soton[...]
[22]
문서
A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992
[23]
간행물
Foundations of Actor Semantics
https://hdl.handle.n[...]
MIT
1981-06
[24]
서적
Modal and Temporal Properties of Processes
Springer
[25]
저널
Strategic Directions in Concurrency Research
http://doi.acm.org/1[...]
1996-12
[26]
서적
Parallel Programming with Microsoft .NET
https://web.archive.[...]
Microsoft Press
2010-08
[27]
서적
Coordinated Computing - Tools and Techniques for Distributed Software
https://web.archive.[...]
McGraw-Hill
[28]
서적
Practical PRAM Programming
John Wiley and Sons
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com