5. 병행 프로세스와 동기화

이희제·2021년 1월 4일

OS Operating System 운영체제

Operating System

목록 보기

5/12

오늘은 병행 프로세스와 동기화에 대해서 알아보겠습니다.

각 내용에 들어가기 전 병행(Concurrent)의 의미에 대해서 정확히 알고 가야합니다.

병행은 말 그래도 같이 존재하고 있다는 뜻으로 메모리에 다수의 프로세스가 같이 존재한다는 것과 같습니다.

1. 병행 프로세스

✅ 프로세스 여러 개가 동시에 실행되는 것을 의미합니다.

문제점

공유 자원의 상호 배타적인 사용
하나의 기능을 공통적으로 사용하는 두 프로세스 간의 동기화 문제
자료 교환을 위한 통신 문제
교착상태 문제(deadlock)

2. 상호배제(Mutual Exclusion)

프로세스들이 공유 데이터에 대해 서로 접근을 시도하는 상황을 경쟁 상태(Race Codition)라고 합니다.

이런 경쟁 상태 속에서 상호배제, 교착상태(Deadlock), 기아(Starvation)와 같은 문제들이 발생합니다.

<출처: http://sqlmvp.tistory.com/176>

➡️ 두 개 이상의 프로세스가 동시에 사용할 수 없는 자원을 임계자원(Critical Resource)라고 합니다. 그리고 이에 대해 접근하고 실행하는 프로그램 내의 코드 부분을 임계영역(Critical Section)이라고 합니다.

임계영역의 성공적인 실행을 위해서는 우선적으로 상호배제가 지켜져야 합니다.

3. 상호배제를 위한 소프트웨어 기법

✅ 우선 parbegin/parend 구조부터 살펴보겠습니다.

1: parbegin
2:    statement_1
3:    statement_2 
4:    ...
5:    statement_n
6: parend

➡️ parbegin 과 parend 사이에 존재하는 n 개의 문장들이 동시에 수행될 수 있다는 것을 뜻합니다.

단일 처리기 시스템의 경우면 각 문장의 수행 순서를 임의로 해도 되고 다중 처리기의 경우에는 각 문장을 병렬적으로 실행하겠다는 뜻이 됩니다.

Peterson 알고리즘

✅ 두 프로세스 간의 상호배제를 해결한 알고리즘입니다.

전역변수 flag[0]과 flag[1]의 초기값은 false 입니다.

Bakery 알고리즘

✅ n개의 프로세스들을 대상으로 하는 상호배제 알고리즘입니다.

임계 영역을 빠져 나왔을 때 자신의 값을 0으로 해줌으로써 다른 프로세스가 임계영역에 진입할 수 있도록 해줍니다.

임계영역의 진입을 막기 위해서 while문을 계속해서 돌리는 것을 확인할 수 있습니다. 이는 CPU가 가동 중이지만 유용한 곳에 사용되지 못하는 것입니다.

이런 현상을 바쁜 대기(Busy Wait) 또는 스핀락(Spinlock)이라고 합니다.

4. 상호배제를 위한 하드웨어 기법

인터럽트 금지를 사용한 기법


while(true) do
    	.
	.
    
	Interrupt Disable;
    	<critical section>
    	Interrupt Enable;
        
    	.
	.

endwhile;

임계영역 처리 동안 모든 종류의 인터럽트를 금지시킵니다.

하드웨어 명령어를 사용한 기법

기계명령어인 testandset과 exchange 명령어에 대해서 먼저 살펴봅니다.

[testandset]

[exchange]

➡️ 기계명령어로서 원자적으로 실행 도중 끊김 없이 완료되는 연산입니다.(Indivisable)

<testandset과 exchange를 사용한 상호배제>

1. testandset

2. exchange

5. 세마포어(Semaphore)

✅ 세마포어는 세 개의 특수한 명령들만 접근할 수 있게 허용되는 보호된 변수입니다.

0과 1읠 이진 값만을 가진다면 이진(Binary) 세마포어라고 합니다.
음이 아닌 모든 정수가 될 수 있으면 계수(Counting) 또는 정수(Integer) 세마포어라고 합니다.

[Block and wakeup 방식]

P(S): if (S>0) then S = S-1;
	       else S > 0 조건이 만족될 때까지 큐에서 대기; 

V(S): if(큐에서 대기 중인 프로세스들이 존재)
		then 그 중의 한 프로세스를 준비 또는 실행 상태로 만듦;
		else S=S+1;

[Busy-Wait 방식]

P(S){

    while(S<=0); // Busy-wait //	
    S--;

}

V(S){

    S++;
    
}

세마포어를 사용한 상호배제

const int n = /* 프로세스 개수 */;
semaphore s = 1;  // 이진 세마포어

void process(int i) {
	while (true) {
    	P(s);
        
        /* 임계 영역(Critical Section)*/
        
        V(s);
        
        /* 임계 영역 이후 코드 */
    }
}

void main() {
	parbegin (P(1), P(2), ..., P(n));
}