4-1. 병행 프로세스
병행 프로세스의 개념
- 독립 프로세스
- 단일 처리 시스템
- 독립적임
- 협력 프로세스
- 다른 프로세스와 영향을 주고받는 비동기적 프로세스
- OS가 자원 경쟁을 고려하여 디스크/프린터로의 접근 조절
- 한 프로세스의 수행이 다른 프로세스에 영향을 줄 수 있어 상호배제가 필요
병행 프로세스의 해결 과제
- 공유 자원을 상호 배타적으로 사용해야 함
- 병행 프로세스 간에는 협력이나 동기화(ex 상호배제)가 필요
- 두 프로세스 사이에서 데이터 교환이 가능해야 함
- determinancy확보 필요
- 결정성: 실행 속도와 관계 없이 항상 일정한 실행 결과 보장
- 교착 상태 해결 + 병행 프로세스들의 병렬 처리 능력 극대화 필요
- 상호배제를 보장해야 함
- 상호배제: 어떤 프로세스가 작업을 실행 중일 때, 나머지 프로세스는 그것과 관련된 작업을 할 수 없도록 하는 것
선행 그래프와 병행 프로그램
- 선행 그래프
- 선행 제약(precedence constraint)은 프로세스를 순서대로 다른 상태로 옮기는 것
- 두 프로세스 사이에 선행 제약이 없으면 이 둘은 독립적인 것
- 순차적 활동을 제약하는 방향성 비순환 그래프
- fork와 join 구조
fork L;: 병행 프로세서 2개 생성(레이블이 L인 문장 / fork 명령어 바로 다음)jon v;: 병행 연산 2개를 결합
- 병행 문장
- parbegin/parend 사이의 모든 문장은 병행 수행이 가능
4-2. 상호배제와 동기화
상호배제(mutual exclusion)의 개념
- 병행 프로세스에서 프로세스 하나가 공유 자원을 사용할 때, 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법
- 동기화: 공유 자원을 동시에 사용하지 못하게 실행을 제어하는 방법
- 동기화로 상호배제를 보장하면 교착과 기아 상태 발생 가능 (Chapter 5)
- critical resources(임계 자원): 두 프로세스가 동시에 사용할 수 없는 공유 자원
- critical section(임계 영역): critical resources에 접근하고 실행하는 program code 부분
- 동일한 critical section에 들어가면 뒤에 들어온 프로세스 차단
- 수정 가능한 공유 자원에서만 차단이 필요
- 단, 단순 읽기 작업은 허가
임계 영역
- 한 순간에는 하나의 프로세스만 사용 가능
- 진행: 임계 영역에 프로세스가 없는 상태에서 여러 프로세스가 진입을 원하면 적절히 결정해야 함
- 한정 대기: 프로세스가 무한정 기다리는 것을 방지하기 위해, 임계 영역에 한 번 들어간 프로세스는 재진입 제한을 둠
생산자/소비자 문제와 상호배제를 해결하는 초기의 시도
- 운영체제에서 비동기적으로 수행하는 모델
- 생산자 프로세스가 생산한 정보를 소비자 프로세스가 소비
- 버퍼 (임시 기억장소)
- 생산자는 소비자가 받을 준비가 될 때까지 대기하는 문제를 해결
- 생산자는 버퍼로 데이터를 전송
- 소비자는 버퍼에서 데이터를 받음
- 동기화가 필요: 생산자는 버퍼가 가득 차면 생산 X + 소비자는 버퍼가 비면 소비 X
- race condition(경쟁 상태)
- 여러 프로세스가 동시에 공유 데이터에 접근할 때, 접근 순서에 따라 실행 결과가 달라지는 상황에 놓인 프로세스
- 상호배제를 이용해 병행 프로세스들을 동기화하여 예방
4-3. 상호배제 방법들
데커의 알고리즘 (Dekker’s algorithm)
- 소프트웨어로 해결
- 다익스트라(dijkstra)로 임계 영역 문제에 적용함
- 최초로 상호배제를 소프트웨어로 해결
- 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법
- 가장 짧은 평균 대기시간
- 진입 순서에 따라 허용
- 진입을 원하면 플래그 설정 후 대기
- 장점
- 하드웨어 제어 X, 프로세스가 무한정 기다리지 않게 됨
- 기타 유용한 상호배제 알고리즘
- knuth(크누스) : 이전 알고리즘 관계 분석 후, 패턴을 찾아 반복을 줄여, 프로세스에 프로세서 할당
- lamport(램포트) : 우선순위를 부여하여 차례로 진입 허용
- brinch hansen(핸슨) : 대기시간과 실행시간을 이용하는 모니터 방법
Test And Set (테스)
- 하드웨어로 해결
- 메모리 영역의 값에 대해 검사와 수정을 원자적으로 수행할 수 있는 하드웨어 명령어
- atomic operation (원자적 연산)은 중단 없이, 중간에 다른 사람이 수정할 수 없는 최소 단위 연산
- 장점
- 다중 임계 영역을 지원
- 프로세서, 프로세스 수에 관계 없음
- 단점
- 프로세서 시간 소모가 큼
- 바쁜 대기를 하게 됨
- 대기 프로세스는 비생산적
- 기아/교착 발생
semaphore (세마포)
- 소프트웨어로 제공
- 진입 조건 반복 조사의 비효율을 해결
- 정수의 플래그 변수
- Proberen(검사), Verhogen(증가) 연산과 관련
- P: wait
- V: signal, 준비 큐에서 프로세스를 껀 그 프로세스 시작
- 동기화에도 사용이 가능
- 종류
- 계수(counting) 세마포: 상호배제와 조건부 동기화를 해결하기 위함
- 이진(binary) 세마포: 임계 영역처럼 상호배제를 해결하려기 위함
- 구현
- 제어를 넘겨받은 프로세서는 준비 큐에서 다른 프로세스를 선택
- 그 프로세스를 실행하도록 프로세서 스케줄러에 전송
- 중단된 프로세스는 다른 프로세스가 V(signal)연산을 실행해야 재시작 가능
- 프로세스는 wakeup 연산으로 대기에서 준비 상태로 변하며, 준비 큐에 놓임
- 단점
- wait 연산에 의한 교착 상태 발생
monitor (모니터)
- 소프트웨어로 제공
- 공유 자원과 그의 임계 영역 관리
- 공유 데이터, 임계 영역이 코딩된 프로시저, 초기화 코드로 구성된 모듈
- 프로세스는 모니터의 프로시저를 호출하여 모니터(하나만)에 진입, 원하는 공유 데이터에 접근 가능
- 모니터에서 하나 이상의 프로세스 실행 X
- 모니터 VS 세마포
- x.wait x.signal 은 P V 연산과 비슷함
- wait은 프로세스를 반드시 차단하고 P는 계숙 세마포에 따라 다름
- signal은 호출 시 대기 작업이 없으면 아무 기능X, V는 반드시 counter를 증가시킴
- 구현
- 1로 초기화된 세마포 mutex 사용
x.wait(c);signal 연산을 실행할 때, 우선순위 c를 통해서 다음 프로세스 결정
- 단점
- 프로그래밍 언어로 일부 구현되어 있기 때문에 컴파일러가 코드를 생성해야 함
- 병행성을 지원하는 언어만 모니터를 지원
