20180219 병렬 프로세스

병렬 프로세스

프로세스 여러 개가 동시에 실행되면 병렬 프로세스라고 한다. 병행 프로세스는 서로 관련 없이 단독으로 작업을 수행하기도 하지만, 종종 다른 프로세스들과 협력 및 통신하면서 작업을 진행해야 할 필요가 있다. 

2개 혹은 그 이상의 프로세스들이 공유 메모리에 읽기/쓰기를 진행하고 그 결과가 어떤 프로세스가 언제 실행하느냐에 따라 결과가 달라질 수 있는 상황을 경쟁 조건(race condition)이라 한다. 

그림을 살펴보면, 두 개의 스레드가 존재하고 Integer 17의 값을 공유 자원으로 이용하고 있다. 두 스레드는 해당 값을 읽어들이고 약간의 시간 차를 두고 공유 자원의 값을 증가시키지만, 나오는 결과가 다르다. 이를 race condition 이라고 칭한다.

경쟁조건(race condition) 을 피하기 위해서는 공유 메모리, 공유 파일, 기타 공유에 관련된 문제를 피하도록 조치해야 한다. 앞서 말했다시피 경쟁조건으로 인해서 어떤 프로세스가 언제 실행하느냐에 따라 결과가 달라질 수 있기 때문. 이와 같은 상황은 이후 심각한 문제를 초래한다.

따라서 2개 혹은 그 이상의 프로세스들이 동시에 읽기/쓰기를 하지 못하도록 상호배제가 필요하다. 상호배제(mutual exclusion : mutex)란 한 프로세스가 공유 메모리 혹은 공유 파일을 사용하고 있을 때, 다른 프로세스들이 사용하지 못하게 배제시키는 제어기법을 의미한다.

프로세스들은 가끔 공유 메모리 혹은 공유 파일을 참조하여 경쟁 조건(race condition)을 일으키는 일을 한다. 이러한 공유 메모리가 참조되는 프로그램의 부분을 임계 영역(critical section) 이라 한다. 

결과적으로 수행순서를 잘 조절하여 두 개 이상의 프로세스가 임계 영역에 동시에 들어가지 않게 한다면 경쟁 조건을 피할 수 있다. 

병렬 프로세스가 효과적으로 수행되려면, 아래와 같은 요구조건이 제시된다.

- 상호배제 조건 : 두 개 이상의 프로세스들이 동시에 임계영역에 있어서는 안된다.

- 진행 조건 : 임계 구역 밖에 있는 프로세스는 다른 프로세스의 임계 구역 진입을 막아서는 안된다.

- 한계 대기 조건 : 어떤 프로세스도 임께 구역으로 들어가는 것이 무한정 연기되어서는 안된다.

- 동일 속도 조건 : 프로세스들의 상대적인 속도에 어떠한 가정도 하지 않는다.

교착상태(DeadLock)

두 개의 프로세스가 공유 메모리 또는 공유 자원을 참조해서 race condition을 일으키는데, 상호배제를 통해서 임계 영역에 들어가는 것을 막는다. 하지만 임계 영역의 진입을 위해서 일어날 수 없는 사건을 무한히 기다리는 상태인 교착상태가 발생하는 경우가 있다. 

교착상태

☞ 다중 프로그래밍 시스템에서 아무도 기다려도 결코 일어나지 않을 사건을 기다리는 하나 또는 그 이상의 프로세스를 교착상태 (Deadlock) 에 빠져있다고 한다. 

☞ 하나 또는 둘 이상의 프로세스가 더 이상 계속할 수 없는 어떤 특정 사건을 기다리는 상태를 말한다. 여기서 특정 사건이란 자원의 할당과 해제를 의미한다.

☞ 둘 이상의 서로 다른 프로세스가 요구한 자원을 할당받아 점유하고 있으면서 상호 간에 상대방 프로세스가 가진 자원을 요구하는 때를 말한다.

시스템 자원을 사용하려고 경쟁하거나 상호 간에 통신하는 프로세스 집합들이 영구적으로 블로킹된 상태

세마포어

세마포어란, 공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것이다. 세마포어 s는 정수값을 갖는 변수로서 초기화 및 2개의 연산(P 와 V 혹은 wait 와 signal) 으로만 접근할 수 있는 특수한 변수이다. 아래는 wait(= P) 그리고 signal(= V)의 정의이다.

s.wait():
    if(s.value > 0) then
        s.value--;
    else
        현재 프로세스를 s.list에서 기다린다.

프로세스를 대기시키는 wait 동작으로 임계영역에 진입하기 위한 연산이다.

s.signal():
    if(1개 이상의 프로세스가 s에서 대기 중이면) then
        그 중 1개 프로세스만 진행
    else
        s.value++;

대기 중인 프로세스를 깨우는 신호를 보내는 signal 동작으로 임계영역에서 나오기 위한 연산이다.

세마포어 s에 의해 블록 또는 대기 중인 프로세스가 signal 연산을 실행해야 재시작할 수 있다. 이때, 프로세스는 wake up 동작에 의해 재시작되며 대기 상태에서 준비상태로 변하면서 준비 큐에 놓이게 된다.

임계영역에 있던 프로세스는 signal 동작을 통해 s를 단순히 1만큼 증가시키고 임계영역을 빠져나온 사실을 스케줄러에게 알린다. 여기서 중요한 사실은 wait와 signal 연산이 세마포어 변수를 수정하는 것이 개별적으로 실행된다는 것이다. 즉 한 프로세스가 세마포어 변수 s를 수정하면 다른 프로세스는 같은 변수 s에 대하여 수정할 수 없다.

세마포어는 프로세스 N개의 임계영역을 다루는데 사용되며 세마포어를 이용한 N개 프로세스의 상호배제 구현은 다음과 같다.

semaphore(1);
 
while(1) {
    ...
    s.wait();
 
    // 임계영역
    ...
    
    s.signal();
    ...
}

세마포어 변수 s에 적용된 wait와 signal연산은 동시에 두 가지 동작이 실행되는 것을 예방한다. 여기서 s는 세마포어 공유 변수이며 초깃값은 1이다.

상호배제(=Mutex) 와 세마포어간의 차이점도 있기에 찾아보고 공부하자.