이 중 메모리 같은 자원은 공유 영역으로써 모든 프로세스가 동시에 공유한다. 즉, 이 메모리 자원은 공유 영역으로서 병렬(parallel) 로 사용된다. 반면 입출력 장치 일부나 프로세서는 한 번에 프로세스 하나만 사용할 수 있는 공유 자원이다.
메모리의 공유 영역
프로세서 하나는 한 번에 프로세스 하나만 실행할 수 있다. 하지만 OS가 프로세서를 빠르게 전환하여 프로세서 시간을 마치 프로세스 여러 개를 동시에 실행하는 것처럼 보이게 하는 것을 병행 프로세스라고 한다.
병행 프로세스는 단일 처리 시스템에서 서로 독립적으로 작업을 수행하는 독립 프로세스, 다른 프로세스와 협력하면서 특정 기능을 수행하는 비동기적 병행 프로세스인 협력 프로세스로 구분된다.
독립 프로세스
독립 프로세스는 단일 처리 시스템에서 수행하는 병행 프로세스로, 다른 프로세스에 영향을 주고받지 않으면서 독립적으로 실행한다. 그래서 다른 프로세스, 데이터와 상태를 공유하지 않고 동작도 재현할 수 있다. 또 주어진 초깃값에 따라 항상 동일한 결과를 보여주고, 중지했다가 변동 사항 없이 다시 시작할 수 있다.
단일 프로그래밍 : 프로세서를 사용 중이던 프로세스를 완료한 후 다른 프로세스를 실행
다중 프로그래밍 : 프로세스 여러 개가 프로세서 하나를 공유한다. 공유하지 않는 상태일 때 디스패치 순서는 상관없다.
다중 처리 : 프로세서를 2개 이상 사용하여 동시에 프로그램 여러 개를 병렬로 실행한다. 프로세스는 한번에 프로세서 하나에서 실행하지만, 동일한 시스템에서는 서로 다른 시간에 서로 다른 프로세서에서 실행할 수 있다.
협력 프로세스
협력 프로세스는 다른 프로세스에 영향을 주고받으며, 즉 상호작용하여 특정 기능을 수행하는 비동기적 프로세스이다.
대개 제한된 컴퓨터 자원의 효율성을 증대하고, 계산 속도를 향상시키고, 모듈적 구성을 강화하고, 개별 사용자가 여러 작업을 동시에 수행할 수 있는 평의성을 제공하는데 사용한다.
예를 들어 두 프로세스가 동일한 파일을 사용할 때 하나의 프로세스가 파일에서 읽기를 수행하는 동안 다른 프로세스가 해당 파일에 쓰기를 하면 서로 영향을 받는다.
프로세스 상호작용 방식
병행 프로세스들이 입출력 장치, 메모리, 프로세서, 클록 같은 자원을 서로 사용하려고 하면 충돌이 발생한다. 그런데 이런 자원들은 다른 프로세스에 영향을 받거나 상태가 변하면 안 되므로 프로세스는 다음 세가지 형태로 상호작용한다.
프로세스는 서로 인식하지 못하는 경쟁 관계를 유지한다. 다중 프로그래밍 환경이 대표적이 예로, OS가 자원 경쟁을 고려하여 동일한 디스크나 프린터로 접근을 조절한다.
프로세스는 입출력 버스를 비롯한 개체를 공유하는 단계에서 간접적으로 서로의 관계를 인식한다. 이때 다른 프로세스에서 얻은 정보에 의존할 수 있고, 프로세스의 타이밍에 영향을 받을 수 있다. 그러므로 프로세스들은 개체 공유에 따른 협력이 필요하다.
프로세스에서는 서로를 인식하고 프로세스끼리 통신할 수 있는 기본 함수가 있다. 프로세스가 서로 협력 관계에 있으면 직접 통신이 가능하고 병행해서 함꼐 동작할 수 있다.
특히 경쟁 관계에 잇는 프로세스들은 서로 정보를 교환하지 않지만, 한 프로세스의 수행이 나머지 프로세스의 수행에 영향을 미칠 수 있어 상호배제가 필요하다.
병행성과 병렬성
병행성과 병렬성은 둘 다 대략적으로 "동일한 시간 동안 여러 프로세스를 동시 실행"이라는 의미를 담고 있다. 하지만 둘은 전혀 다른 개념이다.
병렬성(Parallelism)
실제로 동시에 작업이 처리가 되는 것.
병렬성을 기반으로 한 병렬 컴퓨팅은 다중 프로세서 시스템에서 동일한 시간에 별도의 프로세서에서 실행하는 것이다.
Physical(Machine) Level에 속한다.
오직 Multi Core에서만 가능하다.
Case
OpenMP, MPI, CUDA
병행성(Concurrency)
동시에 실행되는 것처럼 보이는 것.
병행성을 기반으로 한 동시 컴퓨팅은 프로세스 수명이 겹치는 것이지 모두 동일한 시간에 실행할 필요는 없다.
Logical Level에 속한다.
Single Core
물리적으로 병렬이 아닌 순차적으로 동작할 수 있다.
실제로는Time-sharing으로 CPU를 나눠 사용함으로써 사용자가 Concurrency를 느낄 수 있도록 한다.
Multi Core
물리적으로 병렬로 동작할 수 있다.
예를 들어, 병행 프로세스는 시분할로 각 프로세스의 실행 단계를 전환하여 어느 한순간에는 프로세스 하나를 실행하도록 하는 방법으로, 단일 프로세서 시스템에서도 가능하다.
병행 프로세스의 해결 과제
병행성
여러 프로세스를 이용하여 작업을 수행하는 것으로, 다중 처리 시스템, 분산 처리 시스템뿐만 아니라 단일 프로세서로 운영하는 다중 프로그래밍 시스템에서도 매우 중요하다.
시스템의 신뢰도를 높이고 처리 속도를 개선하여 처리 능력을 높이는데 매우 중요함.
다중 처리 시스템
각 프로세서가 갖는 오버헤드를 감소시키면서 프로세서의 유효성을 증대시킴
명령어 여러 개를 세분화하여 동시에 처리하려면 프로세서들을 연결하고 상호작용을 제어
다중 프로세싱 시스템의 성공적인 구현을 위한 문제 해결
공유 자원을 상호 배타적으로 사용해야 한다. 예를 들어, 프린터, 통신망 등은 한순간에 프로세스 하나만 사용해야 한다.
병행 프로세스 간에는 협력이나 동기화가 되어야 한다. 상호배제도 동기화의 한 형태이다.
두 프로세스 사이에서는 데이터를 교환할 수 있도록 통신이 되어야 한다.
프로세스는 동시에 수행하는 다른 프로세스의 실행 속도와 관계없이 항상 일정한 실행 결과를 보장하도록 결정성(determinacy) 을 확보해야 한다.
교착 상태를 해결하고 병행 프로세스들의 병렬 처리 능력을 극대화해야 한다.
실행 검증 문제를 해결해야 한다.
병행 프로세스 수행 과정에서 발생하는 상호 배제를 보장해야 한다. 어떤 프로세스가 작업을 실행 중일 때 나머지 프로세스들이 그 작업에 관련된 작업을 수행할 수 없음.
다중 처리 시스템에서는 프로세서들이 모든 입출력 장치와 메모리를 참조할 수 잇어 동시에 동일한 자원에 접근할 때 충돌이 발생할 수 있다. 따라서 프로세서 간의 충돌을 해결하는 방법이 필요하다.
여기서는 선행 그래프를 이용하여 프로세스들이 OS의 지원 없이 상호배제를 책임지는 SW 적인 방법을 알아볼 것이다. 상호배제를 시도한 미완성된 형태부터 시작하여 점차 완성된 순으로 상호배제의 개념을 이해해보자.
선행 그래프와 병행 프로그램
프로세스들이 선행 그래프를 이용하여 상호배제를 보장하는 방법을 살펴보기 전에 프로그램밍 언어에서 문장 간의 선행 관계를 그래프로 표현하는 선행 그래프의 개념과 종류를 먼저 살펴보자.
선행 그래프
프로세스는 프로세스 집합과 이것의 선행 제약(precedence constraint) 두 가지 요소로 정의할 수 있다.
선행 제약
선행 제약은 프로세스를 순서대로 다른 상태로 옮기는 것이다.
프로세스 P1, P2 ...., Pn이 있고 선행 제약이 Pi < Pj 이면, 프로세스 상태는 Pi 에서 Pj 로 옮겨 감.
따라서 Pi < Pj 이고 Pj < Pk 이면, Pi < Pk
두 프로세스에 선행 제약이 없으면 이 둘은 독립적이라서 병행 실행이 가능하다.
선행 그래프(precedence graph)
선행 그래프(precedence graph) 는 선행 제약을 논리적으로 표현한 것이다. 노드 i 에서 노드 j 로 활동 j 를 시작하기 전에 활동 i 를 완료해야 한다는 순차적 활동을 표현하는 방향성 비순환 그래프이다. 선행 그래프에서 노드는 SW 작업이거나 동시에 실행할 수 있는 프로그램 명령일 수 있다.
다음은 간단한 산술 연산을 수행하는 알고리즘과 이것의 선행 그래프이다.
알고리즘 일부를 병행 수행하려면, 프로세서 안에 기능을 여러 개 두거나 프로세서를 여러개 사용해야 한다.
특히, 프로세서를 여러 개 사용 시 여러 문장이 동시에 수행되어 총 수행 시간을 줄일 수 있다.
선행 그래프는 각 문장에 대응하는 노드를 비순환 그래프로 나타낸다.
노드 Si 에서 노드 Sj 로 가는 연결선(Edge)은 문장 Si 를 완전히 수행한 후 문자 Sj 를 수행했음을 의미함.
프로그램의 여러 문장의 선행 관계 명시를 위해 두 가지 언어 구조를 제시했다.
fork와 join 구조
선행 그래프는 연산 부분의 선행 제약을 정의하는데 유용하지만, 2차원이라 프로그램에는 사용하기 어렵다.
