병행 프로세스

병행 프로세스

독립적으로 작업을 수행하거나, 다른 프로세스와 협력하여 특정기능을 수행한다.
프로세스간 통신이 필요하다.

비동기적 병행 프로세스

프로세스간 통신 시 동기화 되어야 하는 프로세스

상호 작용

제한된 자원을 공유하기 위함이며, 상호 작용하는 프로세스는 순서에 맞게 실행되도록 동기화 되어야 한다.

병행성

다수의 프로세서를 이용한 작업을 수행하며, 다중 처리 시스템, 분산 처리 환경, 다중 프로그래밍 운영체제에서 매우 중요하다.
시스템의 신뢰도 향상과 처리 속도 개선을 통한 처리 능력 증대에 매우 중요하다.
다중 처리 시스템: 각 프로세서가 갖는 오버 헤드를 감소시키면서 프로세서의 유효성을 증대시킨다. 
여러개의 명령어를 세분화하여 동시에 처리하기 위해 프로세서들을 연결 상호 작용을 제어한다.

다중 처리 시스템의 성공적인 구현을 위한 해결문제

1. 공유자원을 상호 배타적으로 사용해야 한다.
2. 병행 프로세서들 사이는 협력, 동기화되어야 한다.
3. 두 프로세스 사이에 데이터 교환을 위한 통신이 이루어져야 한다.
4. 프로세서는 결정성을 확보해야 한다.
5. 교착 상태를 해결하고 병행 프로세서들의 병렬 처리 능력 극대화
6. 실행 검증 문제 해결
7. 병행 프로세서 수행 과정에서 발생하는 상호 배제를 보장해야 한다.
8. 동기화 알고리즘이 필요하다.

선행 제약

프로세스가 순서대로 다른 상태로 옮겨간다.
두 프로세스간에 선행 관계가 없으면 이들은 독립적이라 병행 실행이 가능하다.

선행 그래프

제약을 규칙적(논리적)으로 표현한 것
각 문장에 대응되는 노드가 비순환 그래프를 이용한다.

산술 연산 수행 알고리즘

병행 수행을 하기 위해 프로세서 안의 기능 단위를 여러개 두거나 프로세서를 여러개 사용해야 한다.
프로세서를 여러개 사용 시 여러 문장이 동시에 수행되어 총 수행시간을 줄일 수 있다.

Fork-Join

선행 그래프는 연산 부분의 선행 제약을 정의하는데 유용하나, 2차원 이므로 프로그래밍 언어에서 사용하기 어렵다.
병행을 최초로 언어적 표현으로 명시: 콘웨이(Conway 1963), 데니스(Denis 1966), 호른(Van Horn 1966)

병행 문장

프로세스 하나가 여러 가닥의 병렬 프로세스로 퍼졌다가 다시 한 가닥으로 뭉쳐지는 것을 나타내는 고급언어 구조
예) 다익스크라(Dijkstra, 1965)

상호배제, 동기화

둘 이상의 프로세스가 공유할 수 없는 자원을 임계자원이라 하여, 프로그램에서 이를 이용하는 부분
공유 메모리가 참조되는 프로그램의 부분(데이터, 데이터 구조)으로 다수의 프로세스가 접근 가능한 영역이면서 한 순간에 하나의 프로세스만 사용할 수 있는 영역을 의미
프로세스들이 공유 데이터를 통해 협력 시 한 프로세스가 임계영역에 들어가면 다른 모든 프로세스는 임계영역으로의 진입을 금지한다.
다중 처리 시스템과 단일 처리 시스템(시분할) 환경에서 적용되는 하나의 실행단위, 실행 구간을 의미한다.
임계영역 내에서 빠른 속도로 작업을 수행, 한 프로세스가 오랫동안 머무르면 안된다.
프로세스가 무한 루프 등에 빠지지 않도록 관리해야 한다.

진입 상호배제

프로세스 하나가 임계영역에 있으면 다른 프로세스가 임계영역에 들어가지 못하게 하는 것.
임계영역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야 한다.

임계영역을 해결하기 위한 세가지 요구사항

• 상호배제: 프로세스 p^i가 임계영역에서 수행 중일 때 다른 프로세서는 임계영역에서 수행할 수 없다.
• 진행: 임계영역에서 수행하는 프로세스가 없고 여러개의 프로세스가 임계영역으로 들어가려고 하면 프로세스 선정 알고리즘에 따라 다음 임계영역으로 들어가려고 하면 프로세스 선정 알고리즘에 따라 다음 임계영역에서 수행할 대상을 선정한다.
• 제한된 대기: 한 프로세스가 임계영역을 요청한 후 요청이 수락되기까지 다른 프로세스가 임계영역에 진입할 수 있는 횟수를 제한해야 한다.

test, dest

testandest(a,b); # 논리변수 b 를 읽어 a 에 복사하고 b 를 참으로 하는 명령
단일 프로세서, 메모리를 공유하는 다중 처리 환경과 관계없이 적용되며, 간단하여 쉽게 적용된다는 장점을 가진다.
임계영역에 진입하려는 프로세스에 바쁜 대기가 발생한다.
무한 연기 가능성이 발생할 수 있지만 프로세스 수가 많으면 거의 발생하지 않는다.

모니터

하나 이상의 프로시저, 초기화 코드, 공유 데이터로 구성된 소프트웨어 모듈로 이루어진 객체
모니터 안에 정의된 프로시저는 모니터 내에서 지역적으로 정의된 변수의 형식 매개변수들만 접근이 가능하다.
모니터 경계에서 한 번에 한 프로세스만 진입하도록 제어되므로 상호배제 원칙을 지킨다.
자원 반납 시 모니터 진입 루틴 호출

x.wait 연산

어떤 프로세스가 x.signal 을 호출할 때 까지 x.wait 을 호출한 프로세스는 연기/중단된다는 의미
프로세스 p 가 x-signal 연산 호출 시 조건 x 와 연관되고 중단된 프로세스 q 가 있다고 가정 시 두 가지 가능성이 존재한다.
호(Hoare)는 p 가 이미 모니터 안에서 실행되기 때문에 후자를 선택하는 것이 합리적이라 주장한다.
핸슨은 병행 파스칼 언어에서 이 두 가지 선택사항을 절충하여 적용하였다.
프로세스 p 가 signal 연산을 실행하며 즉시 모니터를 떠나고 q 가 즉시 재실행된다.(신호 후 종료 기법)
새로운 기법은 경쟁하는 프로세서 사이에서 단일 자원 할당을 제어한다.