[OS] 병행프로세스와 동기화

병행 프로세스와 동기화

개인적으로 공부하면서 정리하는 글입니다. 내용에 오류가 있는 경우 댓글 달아주시면 수정하도록 하겠습니다.

병행 프로세스

'병행'이라는 말은 같이 존재하고 있다는 뜻이며, 메모리에 다수의 프로세스가 같이 존재한다는 것과 같은 의미입니다. 한 개의 CPU가 있는 단일처리 시스템에서 병행 프로세스 중 한 개의 프로세스만 실행되지만, CPU의 처리 시간을 효과적으로 나눔으로써 사람이 봤을 때는 동시에 처리되는 것 처럼 보이게 됩니다.

병행 프로세스들은 서로 간에 비동기적인데요. 다른 프로세스들이 어떤 상태에 있는지, 어떤 자원을 가지고 있는지, 어디까지 실행됐는지 등에 대해 모른 체 실행되고 있음을 의미합니다. 공유하는 자원이나 데이터가 있는 병행 프로세스들이 각자 비동기적으로 실행되는 것을 제대로 관리하지 못하면 큰 문제가 발생할 수 있으므로, 이러한 것들을 잘 관리하는 것이 중요합니다.

상호배제

공유하는 자원이 있는 병행 프로세스들은 다른 프로세스의 상태를 알지 못합니다. 그렇기 때문에 공유 데이터에 대해 서로 접근을 시도하는 경쟁 상태(Race Condition)이 될 수 있으며, 이 때 다수의 프로세스가 하나의 공유 데이터에 접근하는 것을 제어하지 않는다면 큰 문제가 발생할 수 있습니다.

var라는 데이터의 현재 값은 10이고, var의 값을 1 증가시키는 프로세스 A와 1 감소시키는 프로세스 B가 존재합니다. 두 프로세스의 순서에 상관없이 한 번씩 실행되었을 경우 var라는 데이터의 값은 10이 되어야 합니다. 하지만 공유 데이터에 대한 접근 제어를 하지 않게 되면, var라는 값은 11 또는 9가되는 상황이 발생할 수 있습니다.

두 개 이상의 프로세스가 동시에 사용할 수 없는 자원을 임계 자원(Critical Resource)라고 말하는데요. 이런 임계 자원에 접근하고 실행하는 프로그램 코드 부분을 임계 영역(Critical Section)이라고 합니다. 이러한 임계영역에 한 번에 하나의 프로세스만이 들어가도록 제어하는 것을 상호배제(Mutual Exclusion)이라고 합니다.

임계영역의 성공적인 실행을 위해서는 가장 먼저 상호배제가 지켜져야 하고, 임계영역에 있지 않는 프로세스가 다른 프로세스의 진입을 막아서도 안 되고, 비어있는 임계영역에 대한 진입은 바로 허용하되 특정 프로세스의 진입 시도가 계속 무산되어 기아를 겪지 않도록 해야 합니다.

Peterson 알고리즘

Peterson 알고리즘은 flag와 turn 변수로 두 프로세스 사이의 상호배제를 구현한 알고리즘입니다.

flag 값은 프로세스 중 '누가 임계영역에 진입할 것'인지를 나타내는 변수이고,

turn 값은 '누가 임계영역에 들어갈 차례'인지 나타내는 변수입니다.

void P0()
{
    while(true)
    {
        flag[0] = true;
        turn = 1;
        while(flag[1] && turn == 1);
        <critical section>
        flag[0] = false;

        ...
    }
}

P0 프로세스는 임계영역에 진입하기 전에 flag[0]을 true로 설정하여 진입할 것이라는 표시를 합니다. 그리고 turn 변수를 1로 설정하여 P1(다른 병행 프로세스)에게 차례를 양보하게 됩니다. 그 후 P1 프로세스가 작업을 끝냈거나, 임계영역이 비어있었다면 P0은 임계영역으로 들어가 작업을 수행하고, 작업이 끝나면 flag[0]을 다시 false로 바꾸어 P1이 접근하는데 문제가 없도록 해줍니다.

P1에 대한 코드는 P0의 코드에서 0을 1로, 1을 0으로 바꾸어주면 됩니다.

세마포어

세마포어는 3개의 특수한 명령들만 접근할 수 있게 허용되는 보호된 변수로서, 프로그래밍 언어와 운영체제 수준에서 병행성을 위해 제공되는 기법입니다.

세마포어를 위한 특수한 명령

• 초기화 명령 : 세마포어 변수 값 초기화
• P 명령 : 임계영역 진입 전 대기, 세마포어 값 -1 후 진입
• V 명령 : 임계영역 수행 후 세마포어 값 +1

P(S) {
    while(S <= 0);
    S--;
}
V(S) {
    S++;
}

식사하는 철학자 문제

5명의 식사하는 철학자가 있습니다. 이들은 각각 접시를 갖고 있고, 양 손에 들 포크가 있는데... 잘 보면 포크도 다섯개입니. 모두가 같이 식사를 할 수 없습니다.

철학자(프로세스)는 아래의 과정을 반복합니다. (철학자 간 비동기적으로)

1. 생각한다.
2. 자신의 왼쪽에 있는 포크를 집는다.
3. 자신의 오른쪽에 있는 포크를 집는다.
4. 식사한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.

여기서 공유 자원은 포크입니다. 만약 모든 철학자가 동시에 왼쪽 포크를 집는다면, 그 이후 아무도 오른쪽 포크를 집을 수 없어서 교착 상태에 빠지게 됩니다.

해결 방법 1

양 쪽 포크를 한 번에 집고, 한 번에 내려놓도록 합니다. 철학자는 왼쪽, 오른쪽 포크를 동시에 집게 됩니다. 이러면 교착상태가 생기지 않게 할 수 있긴 한데, 위 그림에서 P4와 P1이 너무 빨라서 계속 포크를 집고 먹고 내려놓고 반복하게 되면 P0는 식사를 계속 못하게 되는 기아상태에 빠질 수 있습니다.

해결 방법 2

짝수 번호의 철학자는 왼쪽 포크부터 집게 하고, 홀수 번호의 철학자는 오른쪽 포크부터 집게합니다. 이러면 교착상태나 기아 없이 식사가 가능합니다.