병행 프로세스

병행 프로세스는 독립적으로 작업을 수행하기도 하고, 다른 프로세스와 협력해 특정 기능을 수행하기도 한다. 이 협력 과정에서는 프로세스 간 통신이 필요하다.

비동기적 병행 프로세스

여러 프로세스가 통신할 때 서로 동기화되어야 하는 프로세스를 비동기적 병행 프로세스라 부른다.

상호작용

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

병행성

병행성은 다수의 프로세서를 이용해 작업을 수행하는 방식으로, 다중 처리 시스템, 분산 처리 환경, 다중 프로그래밍 운영체제에서 특히 중요하다. 시스템의 신뢰도를 높이고 처리 속도를 개선해 전체 처리 능력을 끌어올리는 데 핵심적인 역할을 한다. 다중 처리 시스템에서는 각 프로세서가 갖는 오버헤드를 줄이면서 프로세서의 유효성을 높이는 것이 목표이며, 이를 위해 여러 개의 명령어를 세분화해 동시에 처리할 수 있도록 프로세서들을 연결하고 그 상호작용을 제어한다.

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

다중 처리 시스템을 제대로 구현하려면 다음 여덟 가지 문제를 해결해야 한다.

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

선행 제약

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

선행 그래프

선행 그래프는 이러한 제약을 규칙적(논리적)으로 표현한 것으로, 각 문장에 대응하는 노드로 이루어진 비순환 그래프를 이용한다.

산술 연산 수행 알고리즘

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

Fork-Join

선행 그래프는 연산 부분의 선행 제약을 정의하는 데 유용하지만, 2차원 구조이기 때문에 프로그래밍 언어에서 그대로 쓰기는 어렵다. 병행성을 언어적 표현으로 처음 명시한 것은 콘웨이(Conway, 1963), 데니스(Dennis, 1966), 반혼(Van Horn, 1966)이었다.

병행 문장

병행 문장은 프로세스 하나가 여러 가닥의 병렬 프로세스로 퍼졌다가 다시 한 가닥으로 뭉쳐지는 것을 나타내는 고급 언어 구조다. 예를 들어 다익스트라(Dijkstra, 1965)가 이러한 구조를 제시했다.

상호배제, 동기화

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

진입 상호배제

진입 상호배제는 프로세스 하나가 임계영역에 있을 때 다른 프로세스가 임계영역에 들어가지 못하게 하는 것이다. 임계영역에 들어가려는 프로세스는 반드시 이 진입 상호배제를 수행해야 한다.

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

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

test-and-set

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

모니터

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

x.wait 연산

어떤 프로세스가 x.signal을 호출할 때까지, x.wait을 호출한 프로세스는 연기(중단)된다. 프로세스 p가 x.signal 연산을 호출할 때 조건 x와 연관되어 중단된 프로세스 q가 있다고 가정하면 두 가지 선택지가 있다. 호어(Hoare)는 p가 이미 모니터 안에서 실행 중이기 때문에, q보다 p를 계속 실행하는 것이 합리적이라고 주장했다. 반면 핸슨은 병행 파스칼 언어에서 두 선택지를 절충해 적용했다. 프로세스 p가 signal 연산을 실행하며 즉시 모니터를 떠나고 q가 즉시 재실행되는 방식을 ‘신호 후 종료 기법’이라 부르며, 이 기법은 경쟁하는 프로세스들 사이에서 단일 자원 할당을 제어하는 데 쓰인다.