[운영체제] 병행 프로세스와 상호배제(1)
병행프로세스
병행 프로세스 개념
프로세스 여러 개가 동시에 실행되는 것
- 독립적으로 작업을 수행, 다른 프로세스와 협력하며 특정 기능 수행
- 프로세스 간 교신이 필요
비동기적 병행 프로세스
- 프로세스 간 교신 시 동기화되어야 하는 프로세스
상호 작용
- 제한된 자원을 공유하기 위함이며, 상호 작용하는 프로세스는 순서에 맞게 실행되도록 동기화되어야 함
병행 프로세스의 과제
병행성
- 다수의 프로세서를 이용하여 작업을 수행하며, 다중 프로세싱 시스템, 분산 처리 환경, 다중 프로그래밍 운영체제에서 매우 중요함
- 시스템의 신뢰도 향상과 처리 속도 개선을 통한 처리 능력 증대에 매우 중요함
- 다중 프로세싱 시스탬
- 각 프로세서가 갖는 오버헤드를 감소시키면서 프로세서의 유효성을 증대시킴
- 여러 개의 명령어를 세분화하여 동시에 처리하기 위해 프로세서들을 연결, 상호작용을 제어
다중 프로세싱 시스템의 성공적인 구현을 위한 해결 문제
공유 자원을 상호 배터적으로 사용해야 함
- 프린터, 통신망 등은 한 순간에 한 프로세스만 사용해야 함
병행 프로세서들 사이는 협력 또는 동기화되어야 함
- 상호 배제도 동기화의 형태임
두 프로세스 사이에 데이터 교환을 위한 통신이 이루어져야 함
프로세서는 결정성(Determinacy)을 확보해야 함
- 동시에 수행되는 다른 프로세스들의 실행 속도와 관계 없이 항상 일정한 실행 결과 보장
교착 상태를 해결하고 병행 프로세스들의 병렬 처리 능력 극대화
실행 검증 문제 해결
병행 프로세스 수행 과정에서 발생하는 상호 배제를 보장해야 함
- 어떤 프로세스가 작업을 실행 중일 때 나머지 프로세스들이 그 작업에 관련된 작업을 수행할 수 없음
다중 프로세싱 시스템은 프로세스 동기화 알고리즘이 필요
- 프로세서들이 모든 입출력 장치와 메모리를 참조 가능
- 동시에 동일한 자원에 접근할 경우 충돌이 발생하므로 이를 해결
</br>
선행 그래프
프로세스는 프로세스 집합과 이들의 선행 제약(Precedence Constraint)의 두 가지 요소로 정의
선행 제약
- 프로세스가 순서대로 다른 상태로 옮겨감
- 프로세스 ‘P1, P2, …, P3’가 있을 때, 선행 순서는 Pi < Pj 로 표시, 상태는 Pi 에서 Pj로 옮겨감
- 따라서 Pi < Pj 이고 Pj < Pk 이면 Pi < Pk
- 두 프로세스 간에 선행 관계가 없으면 이들은 독립적이라 병행 실행이 가능함
선행 그래프(Precedence Graph)
- 제약을 규칙적(논리적)으로 표현한 것
- 각 문장에 대응되는 노드가 비순환 그래프를 이룸
- 노드 Si에서 노드 Sj로 가는 연결선(Edge)은 문장 Si가 완전히 수행된 다음에 문자 Sj가 수행됨을 의미함
언어적 표현과 병행 문장
프로그램의 여러 문장의 선행 관계 명시를 위해 두 가지 언어구조 제시
fork와 join구조
- 선행 그래프는 연산 부분의 선행 제약을 정의하는데 유용하나, 2차원이므로 프로그래밍 언어에서 사용하기에 어려움
- 콘웨이(Conway, 1963년)와 데니스(Dennis, 1966년), 호른(Van Horn, 1966년)이 소개
- 병행을 최초로 언어적 표현으로 명시
- fork L 명령
- 프로그램에서 두 개의 병행 수행을 만듦
- 단일 연산을 두 개의 독립적인 연산으로 분할
- 레이블이 L인 문장에서 수행을 시작
- fork 명령 바로 다음 문장에서 시작
- join 명령
- 여러 개의 병행 연산을 하나로 결함하는 방법을 제공하며, 단위적으로 수행하야 함
- 합칠 연산의 수를 명시하는 매개변수를 가짐
- 연산들은 서로 다른 속도로 진행되므로 둘 중 하나가 join을 먼저 수행하게 됨
- join 연산 수행 후 다른 연산 수행
- 세 개의 연산을 합칠 경우 두 개의 연산이 끝나고 join 연산을 수행한 다음 이들의 결과와 나머지 연산을 join함
병행 문장
- 프로세스 하나가 여러 가닥의 병렬 프로세스로 퍼졌다가 다시 한 가닥으로 뭉쳐지는 것을 나타내는 고급언어 구조
- 대표적인 예 : 다익스트라(Dijkstra, 1965년)가 제안한 ‘parbegin/parend’
상호배제와 동기화
상호배제(Mutual Exclusion)
특정 공유 자원을 한 순간에 한 개의 프로세스만 사용할 수 있을 때, 프로세스 하나가 공유 데이터에 접근하는 동안 다른 프로세스가 해당 데이터를 접근할 수 없게 하는 것
프로세스 간 동기화
공유 자원을 동시에 사용하지 못하게 실행을 제어하는 기법
순차적으로 재사용 가능한 자원을 공유하기 위해 상호작용하는 프로세스 사이에서 나타남
병행 프로세스 간 상호작용
프로세스는 아래 세 가지 형태로 상호작용 함
- 프로세스들이 서로 인식하지 못하는 경쟁관계 유지
- 다중 프로그래밍 환경에서 운영체제는 자원에 대한 경쟁을 고려, 동일한 디스크나 프린터로의 접근 조절
- 프로세스들은 입출력 버스를 비롯한 개체를 공유하는 단계에서 간접적으로 서로의 관계를 인식함
- 프로세스들은 공동 개체를 공유하는데 따른 협력이 필요함
- 프로세스들은 서로를 인식하고 프로세스끼리 통신할 수 있는 기본 함수를 가짐
- 프로세스들이 협력관계일 때, 프로세스 간 직접 통신이 가능, 병행해서 함께 동작할 수 있음
생상자/소비자 프로세스
생산자/소비자, 판독자/기록자(입력기/출력기) 문제
- 여러 프로세스가 공통 작업 수행을 위해 서로 협동하고, 병행 처리되는 대표적인 예
- 상호배제와 동기화가 필요하며 세마포어를 이용해 구현
- 운영체제에서 비동기적으로 수행하는 모델로 생산자 프로세스는 소비자 프로세스가 소비하는 정보를 생산
생산자와 소비자 프로세서들을 병행 실행하기 위해 공유 버퍼가 필요함
- 생산자의 데이터 생산 속도와 소비자의 데이터 소비 속도는 서로 독립적이므로 버퍼가 필요함
- 생산자와 소비자는 같은 버퍼에 접근하므로 동시에 사용할 수 없음
- 생산자가 이미 채워진 버퍼에 더 채우거나, 소비자가 빈 버퍼에서 데이터를 꺼낼 때 문제 발생
- 속도가 다른 생산자와 소비자가 데이터를 일시 저장할 수 있는 버퍼 사용 시 버퍼는 세 가지 상태 중 하나
프로세스 간 통신의 예
- 생산자/소비자 관계에서 한 프로세스가 정보를 생산하면 다른 프로세스는 그 정보를 소비함
- 버퍼가 비었거나 꽉 차 있을 때 버퍼에 접근하는 것을 막기 위해 생산자와 소비자가 동기화 되어 있어야 함
무한 버퍼 생산자/소비자 문제
- 버퍼의 크기에 제한을 두지 않으며 항상 빈자리가 존재함
유한 버퍼 생산자/소비자 문제
- 크기가 고정된 버퍼를 사용, 버퍼가 비었을 시 소비자가 대기, 버퍼가 가득차면 생산자가 대기함
- 공유 버퍼의 저장소를 두 개의 논리적 포인터 in과 out을 사용한 순환 배열로 해결 가능
- in과 out은 0으로 초기화
- 변수 in은 비어있는 다음 버퍼를 기리킴
- 변수 out은 채워진 버퍼의 맨 처음을 가리킴
- 소비자는 버퍼에서 데이터를 읽기 전 생산자가 앞서 가는 지, 즉 in>out 인지 확인함
경쟁 상태(Race Condition)
- 공유 데이터에 최종적으로 남는 데이터의 결과를 보장할 수 없는 상황을 의미
- 여러 프로세스가 공유 데이터를 동시에(병행적으로) 접근(읽기나 쓰기)할 때 공유 데이터에 대한 접근 순서에 따라 실행 결과가 달라지는 상황
- 장치나 시스템이 둘 이상의 연산을 동시에 수행하려 할 때, 어느 프로세서가 제일 마지막에 수행된 후 결과를 저장했느냐에 따라 발생 하는 오류
- 접근 순서화가 필요
- 이를 방지하기 위해 병행 프로세서들은 반드시 동기화되어 실행되어야 함
동기화 실행 방법
- 임계 영역
- 공유 변수를 어느 한 순간에 한 프로세스만 조작할 수 있도록 함
- 상호 배제
- 예에서 counter를 조작하는 부분을 임계영역으로 설정, 상호 배제 함