병행 프로세스

병행 프로세스

• 운영체제가 프로세서를 빠르게 전환하여 두 개 이상의 프로세스가 동시에 수행
• 프로세서에게 시간을 나눠 마치 프로세스 여러 개를 동시에 실행하는 것처럼 보이게 함
• 서로 관련 없이 독립적으로 수행될 수 있음
• 다른 프로세스들과의 협력을 통해 기능을 수행하는 비동기적 수행 가능
• 제한된 자원을 공유하기 위해 상호 작용 필요
• 상호 작용하는 프로세스를 동기화하지 않으면 교착 상태, 임계 구역 문제, 결과를 예측할 수 없는 상황 등 여러 문제 발생

병행 처리의 문제점

• 한 순간에 하나의 프로세스가 공유 자원을 상호 배타적으로 사용 가능
• 한 함수를 공유해 수행하는 두 프로세스 간의 동기화 문제(synchronization)
• 자료 교환을 위한 메시지 전달 방식 등의 통신 문제(communication)
• 교착 상태(deadlock) 문제
• 프로그래밍 언어를 통한 병행 처리 문제
• 올바른 실행을 검증하는 문제(verification)

임계 구역

• Critical Section
• 병행 처리에서 둘 이상의 프로세스가 동시에 접근해서는 안 되는 공유 자원을 접근하는 코드의 일부
• 어떤 프로세스가 공유 자원을 접근하는 동안 임계 구역에 있는 공유 자원만을 접근하도록 함
• 임계 구역에 접근한 프로세스는 상호배제를 보장받아야 함
• 하나의 프로세스만 공유 데이터에 대해 배타적으로 접근하고 나머지 프로세스들은 공유 데이터에 접근할 필요가 있더라도 기다려야 함
  • 임계 구역은 가능한 한 빨리 수행되어야 함
  • 프로세스가 임계 구역에 들어간 후 프로세스가 블록 상태로 되지 않아야 함
  • 무한 루프 상태가 되지 않아야 함

병행 프로세스의 종류

독립 프로세스

• 단일 처리 시스템에서 수행하는 병행 프로세스
• 다른 프로세스에 영향을 주고받지 않으면서 독립 실행
• 다른 프로세스와 데이터 공유 없이 동작 가능
• 주어진 초기값에 따라 항상 동일한 결과
• 중지 후 변동 없이 다시 시작 가능
• 단일 프로그래밍 시스템: 프로세서를 사용 중이던 프로세스 완료 후 다른 프로세스 실행
• 다중 프로그래밍 시스템: 프로세스 여러 개가 프로세서 하나를 공유
• 다중 처리 시스템: 프로세서 2개 이상 사용, 동시에 프로그램 여러 개를 병렬 실행, 동일한 시스템에서는 서로 다른 시간에 서로 다른 프로세서에서 실행 가능

협력 프로세스

• 충돌을 피하기 위한 프로세스의 상호작용 형태
• 프로세스는 서로 인식하지 못하는 경쟁 관계 유지
  • 다중 프로그래밍 환경이 대표적인 예, OS가 자원 경쟁 고려하여 동일한 디스크나 프린터로 접근 조절
• 프로세스는 입출력 버스를 비롯한 개체를 공유하는 단계에서 간접적으로 서로 관계 인식
  • 이때 다른 프로세스에서 얻은 정보에 의존하여 프로세스의 타이밍에 영향
  • 프로세스들은 개체 공유에 따른 협력 필요
• 프로세스에는 서로 인식하고 프로세스끼리 통신할 수 있는 기본 함수가 있음
  • 프로세스가 서로 협력 관계에 있으면 직접 통신 및 병행하여 함께 동작 가능

---

선행 그래프

• Precedence Graph
• 순차적 활동을 표현하는 방향성 비순환 그래프
• 선행 그래프에서 노드는 소프트웨어 작업이거나 동시에 실행할 수 있는 프로그램 명령
• 프로세스: 프로세스 집합과 이것의 선행 제약 두 가지 요소로 정의
  • 두 프로세스에 선행 제약이 없으면 이 둘은 독립적이므로 병행 실행 가능
• 선행 제약: 프로세스를 순서대로 다른 상태로 옮기는 것

fork & join

• 선행 그래프는 연산의 선행 제약 정의에 유용하지만, 2차원이라 프로그램에는 사용 곤란
• 선행 관계 명시 위해 fork(분기)와 join(결합) 구조, 병행 문장 등 다른 방법 필요

병행 문장

• 하나의 프로세스가 여러 병렬 프로세스로 퍼졌다가 다시 하나로 뭉쳐지는 것을 나타냄
• 대표적인 예: 다익스트라(1965)가 제안한 parbegin/parend

---

상호배제

• 병행 프로세스에서 프로세스 하나가 공유 자원 사용 시 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법
• 읽기 연산은 공유 데이터에 동시에 접근해도 문제 발생 X

동기화

• 변수나 파일은 프로세스 별로 하나씩 차례로 읽거나 쓰도록 해야 하는데, 공유 자원을 동시에 사용하지 못하게 실행을 제어하는 방법
• 순차적으로 재사용 가능한 자원을 공유하려고 상호작용하는 프로세스 사이에서 나타남
• 동기화로 상호배제를 보장할 수 있지만, 이 과정에서 교착 상태와 기아 상태가 발생할 수 있음

상호배제의 조건

1. 두 프로세스는 동시에 공유 자원에 진입 불가
2. 프로세스의 속도나 프로세서 수에 영향받지 않음
3. 공유 자원을 사용하는 프로세스만 다른 프로세스 차단 가능
4. 프로세스가 공유자원을 사용하려고 너무 오래 기다려서는 안 됨

임계 영역을 이용한 상호배제

• 임계 영역: 다수의 프로세스 접근 가능하지만 어느 한순간에는 프로세스 하나만 사용 가능
• 자물쇠와 열쇠 관계, 프로세스가 진입하지 못하는 임계 영역이 자물쇠로 잠근 상태
• 어떤 프로세스가 열쇠를 사용할 수 있는지 확인하려고 검사하는 동작과 다른 프로세스 사용을 금지하는 동작으로 분류

임계 영역의 조건

• 상호배제: 어떤 프로세스가 임계 영역에서 작업 중이면 다른 프로세스 임계 영역 진입 불가
• 진행: 임계 영역에 프로세스가 없는 상태에서 어떤 프로세스가 들어갈지 결정 가능
• 한정 대기: 다른 프로세스가 임계 영역을 무한정 기다리는 상황을 방지하기 위해 임계 영역에 한 번 들어갔던 프로세스는 다음에 임계 영역에 다시 들어갈 때 제한

---

생산자 · 소비자 문제

• OS에서 비동기적으로 수행하는 모델
• 생산자 프로세스가 생산한 정보를 소비자 프로세스가 소비하는 형태
• 소비자가 데이터를 받을 준비를 마칠 때까지 생산자는 버퍼로 데이터 전송

생산자와 소비자의 공유 버퍼

• 생산자는 버퍼가 꽉 차면 더 이상 생산 불가
• 소비자는 버퍼가 비면 데이터 소비 불가

무한 버퍼

• 생산자와 소비자가 독립적으로 알고리즘 수행
• 생산자: 버퍼가 가득 차면 중단, 아닐 경우 버퍼에 데이터를 저장하고 버퍼의 다음에 보낼 위치로 포인터 이동
• 소비자: 버퍼가 비면 중단, 아닐 경우 버퍼에서 데이터를 받고 버퍼의 다음에 받을 위치로 포인터 이동

유한 버퍼

• 논리적 포인터 in과 out 2개로 버퍼 순환 배열

버퍼 구조 프로그램 예시

#define BUFFER_SIZE 100
typedef struct{
    DATA data;
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;

생산자 프로세스 예시

item nextProduced;

while (true) {
    // 버퍼가 가득 차 아무 일도 하지 않음
    while (counter == BUFFER_SIZE);
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

• 생산자 프로세스는 생산하는 새로운 원소를 지역변수 nextProduced에 저장

소비자 프로세스 예시

item nextConsumed;

while (true) {
    // 버퍼가 비어 아무 일도 하지 않음
    while (counter == 0);
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}

• 소비자 프로세스는 소비하는 원소를 지역변수 nextConsumed에 저장

경쟁 상태

• Race Condition
• 여러 프로세스가 동시에 공유 데이터에 접근 시, 접근 순서에 따라 실행 결과가 달라지는 상황
• 공유 데이터에 마지막으로 남는 데이터의 결과를 보장할 수 없는 상황
• 장치나 시스템이 둘 이상의 연산 동시 실행 시, 어느 프로세스를 마지막으로 수행한 후 결과를 저장했느냐에 따라 오류가 발생하므로 적절한 순서에 따라 수행해야 함
• 읽기와 쓰기 명령을 거의 동시에 실행해야 한다면, 기본적으로 읽기 명령을 먼저 수행 후 쓰기 명령을 수행하는 접근

경쟁 상태의 예방

• 병행 프로세스들을 동기화해야 함 (임계 영역을 이용한 상호배제로 구현)
• 즉, 공유 변수 counter를 한 순간에 프로세스 하나만 조작할 수 있도록 해야 하는 임계 영역과 counter 연산하는 부분을 임계 영역으로 설정하여 상호배제하는 방법으로 해결

---

상호배제 방법

수준	방법	종류
고급	소프트웨어로 해결	데커의 알고리즘
		램포트의 베이커리 알고리즘
		크누스 알고리즘
		핸슨의 알고리즘
		다익스트라 알고리즘
	소프트웨어가 제공 : 프로그래밍 언어와 운영체제 수준	세마포어
		모니터
저급	하드웨어로 해결 : 저급 수준의 원자 연산	TestAndSet

데커의 알고리즘

• 두 프로세스가 서로 통신하려고 공유 메모리를 사용하여 충돌 없이 단일 자원을 공유할 수 있도록 허용하는 것
• 다익스트라로 임계 영역 문제에 적용
• 병행 프로그래밍 상호배제 문제의 첫 번째 해결책
• 각 프로세스 플래그 설정 가능, 다른 프로세스 확인 후 플래그 재설정 가능
• 프로세스가 임계 영역에 진입하고 싶으면 플래그 설정하고 대기
• 특별한 하드웨어 명령문 필요 없음
• 임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계 영역 진입 막지 않음
• 임계 영역에 들어가기를 우너하는 프로세서를 무한정 기다리게 하지 않음

다익스트라 알고리즘

• 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
• 실행 시간이 가장 짧은 프로세스에 프로세서를 할당하는 세마포어 방법
• 가장 짧은 평균 대기시간

크누스 알고리즘

• 이전 알고리즘 관계 분석 후, 일치하는 패턴을 찾아 패턴의 반복을 줄여 프로세스에 프로세서 할당
• 무한정 연기할 가능성을 배제하는 해결책을 제시
• 프로세스들이 아주 오래 기다려야 함

램포트의 베이커리 알고리즘

• 사람들로 붐비는 빵집에서 번호표 뽑아 빵을 사려고 기다리는 사람들에 비유해서 만든 알고리즘
• 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당

세마포어

• Semaphore
• 다익스트라가 테스 명령어의 문제 해결을 위해 제안
• 상호배제 및 다양한 연산의 순서도 제공
• 세마포어 값은 true나 false로, P(Proberen, 검사)와 V(Verhogen, 증가) 연산과 관련
  • P: 프로세스를 대기하게 하는 wait 동작, 임계 영역에 진입하는 연산
  • V: 대기 중인 프로세스를 깨우려고 신호를 보내는 signal 동작, 임계 영역에서 나오는 연산
• 음이 아닌 정수 플래그 변수
• 문제점: 두 프로세스가 동시에 동일한 세마포어에서 wait과 signal 연산을 할 수 없도록 해야 함

단일 프로세서에서 문제점 해결

• wait과 signal 연산 수행 중 인터럽트 금지
• 중간에 다른 프로세서의 명령어 실행이 끼어들지 않으므로 단일 프로세서 환경으로 활용 가능

다중 프로세서에서 문제점 해결

• 인터럽트를 금지할 수 없어 다른 프로세스의 명령어가 임의의 방법으로 끼어들 수 있음
• 모든 프로세서에서 인터럽트 비활성화 곤란 → 심각한 성능 저하로 이어질 수 있음
• 하드웨어가 임계 영역 문제에 특별한 명령을 제공하지 않으면 이를 소프트웨어적으로 해결해야 함
• wait과 signal 연산으로는 바쁜 대기를 완전히 제거할 수 없음
• 따라서 응용 프로그램의 진입 영역에서 임계 영역까지 바쁜 대기를 제거해야 함
• 바쁜 대기는 아주 짧은 기간 동안만 일어나지만, 어떤 응용 프로그램에서는 임계 영역이 아주 길거나 항상 점유되어 있는 상황이 발생할 수 있음

모니터

• 세마포어의 오용으로 여러 가지 오류가 쉽게 발생하면 프로그램 작성 곤란 → 이러한 단점 극복 위해 등장
• Hansen이 제안하고 Hoare가 수정한 공유 자원과 이것의 임계 영역 관리 소프트웨어 구성체
• 사용자 사이에서 통신하려고 동기화하고, 자원에 배타적으로 접근할 수 있도록 프로세스가 사용하는 병행 프로그래밍 구조

조건 변수가 있는 모니터의 구조

• 프로세스 실행 동안 상호배제와 동기화 제공
• 강력함은 떨어져 동기화 방법을 추가 정의해야 함
• 모니터 외부에 있는 프로세스가 모니터에 있는 프로세스를 수행할 때까지 외부에서 기다려야 할 때는 특정 조건에 따라 실행 재개 결정
• 모니터는 조건 변수와 프로세스를 대기할 수 있는 상황을 연관시킴
• 하나 이상의 모니터 조건 변수를 정의하여 모니터 안에서 작업 동기화

세마포어를 이용한 모니터의 구현

• 모니터 진입의 상호배제 실현하려고 각 모니터마다 1로 초기화된 세마포어 mutex 사용
• 프로세스는 모니터에 진입하기 전에 P(mutex) 연산, 모니터를 떠날 때 V(mutex) 연산 실행
• signal을 보내는 프로세스는 재개된 프로세스가 떠나거나 대기할 때까지 대기
• 초기값이 0인 세마포어 next 추가 도입, next에서 signal을 보내는 프로세스는 자기 자신 연기
• 초기값이 0인 정수형 변수 next_count는 next에서 중단된 프로세스 수 계산
• 각 외부 프로시저 F는 다음 루틴으로 치환하여 모니터 안에서 상호배제 보완