프로세스 동기화

공유된 데이터에 동시에 접근할 때 데이터의 무결성을 고려해야하는 문제이다. A 프로세스와 B 프로세스가 공유된 데이터에 동시에 접근할 경우 원치 않는 결과가 나올 수 있기 때문이다.
따라서 프로세스가 동시에 실행 될 경우 순서를 보장해줌 (프로세스 동기화) 으로써 공유된 데이터의 무결성을 보장 할 수 있다.

여러 프로세스 끼리 공유하는 데이터 불일치 문제 상황

1. 동시 실행 시

현재 CPU를 사용 중인 프로세스가 중단되고, context switch 가 발생할 수 있는데, 이 때 다른 프로세스가 CPU를 점유하면 데이터의 무결성을 보장해줘야 하는 문제 발생

2. 병렬 실행 시

여러개의 프로세스가 분리된 CPU에서 실행될 때 데이터의 무결성을 보장해줘야 하는문제 발생

1. 프로세스 동시 실행 시 문제

동기적으로 실행 되므로, 제대로 데이터의 무결성이 지켜질 것이라고 생각 할 수 있지만 데이터의 불일치성이 발생한다.

왜 ?

A 프로세스와 B 프로세스가 공유된 메모리를 갖고, 동기적으로 실행된다고 가정했을 때, Round-Robin 알고리즘에 따라서 Context Switch 가 A 프로세스 연산 중 처음 혹은 끝에 발생하면 상관없지만, 연산 중간에 Context Switch 가 발생할 수 있다. 그 상태로 B 프로세스를 실행하면 데이터의 불일치성이 발생한다.즉, 각 프로세스 (혹은 쓰레드)가 어떤 순서로 실행되느냐에 따라서 달라진다.

경쟁 상황 (Race Condition)

위의 상황을 일반화 시킨 것으로, 여러개의 프로세스가 하나의 데이터를 공유하고 있을 때, 해당 데이터에 동시적으로 접근/처리 하려고 할 때 실행의 결과는 순서에 따라서 달라진다는 것이다.

경쟁상황 해결 방법 - 프로세스 동기화

특정 시간에 하나의 프로세스만 공유 데이터에 접근/처리 가능 하도록 한다. 즉, 데이터에 대한 접근/처리가 순차적으로 실행될 수 있도록 보장하는 것

• n 개의 프로세스가 있을 때, 각 프로세스의 특정 코드 부분을 임계 영역 (Critical Section)으로 정의
• 해당 임계 영역에서 공유된 데이터에 접근하고 처리한다.
• 따라서, 하나의 프로세스가 임계 영역을 실행 하고 있을 때에는 나머지 프로세스들이 임계 영역을 실행하지 못하도록 함으로써 경쟁 상황을 해결할 수 있고, 자연스럽게 동기화가 된다.

2. 임계 영역 문제

임계 영역을 기준으로 한 코드 영역 분류

1. Entry-Section

임계 영역에 진입하기 위한 허가를 요청하는 영역

2. Critical-Section (임계 영역)

공유된 데이터에 접근/처리하는 영역

3. Exit-Section

임계 영역 진입하기 위한 허가를 반납하는 영역

4. Remainder-Section 나머지 영역

임계 영역 해결방법 시 요구사항

1. 상호 배제 보장 (Mutual Exclusion)

A 프로세스가 임계 영역을 실행 중일 때, 다른 프로세스들은 임계 영역을 실행 할 수 없음을 보장한다.

2. Progress ( 데드락 해결 )

아무 프로세스도 임계 영역을 실행중이지 않을 때, 다른 프로세스들이 임계 영역에 진입하지 못하는 문제를 해결한다. 즉, 모든 프로세스가 무한 대기 하는 것을 해결해야 한다.

3. Bounded Waiting ( 기아현상 해결 )

우선순위나, 실행 순서의 문제 때문이 특정 프로세스들만 계속해서 임계 영역을 실행하지 못하는 문제를 해결해야 한다. 이를 위해서는 프로세스들의 대기 시간을 한정시켜줘야 한다.

프로세스 중단을 막는 방법의 문제점

싱글코어 환경에서는 간단하지만, 멀티 코어(프로세서) 환경에서는 특정 프로세스의 임계영역 실행마다 프로세스 중단을 막아야하므로 시스템 성능이 매우 좋지 못하다.

3. 임계영역 문제 해결 방법

소프트웨어 해결방법 - Peterson's Algorithm

flag 와 turn 이라는 변수를 사용한다. flag[n]이 true일 경우, 프로세스 n 이 임계 영역에 진입해야한다는 것을 의미하고, 이 때 다른 프로세스들은 임계 영역에 진입하지 않고 기다린다. 임계 영역을 종료한 후에는 flag 값을 변경한다.

하지만, 해당 알고리즘에서 임계 영역에 가기 전, 즉 변수 turn과 flag[n] 만 변경해놓고 Context Switch가 일어나는 경우는 데이터의 무결성을 보장할 수 없다.

그럼에도 불구하고, 이론적으로 상호배재 / Progress / Bounded Waiting 조건을 모두 만족하는 소프트웨어 해결방법이다.

bool flag[2] = {false, false};
int turn;

P0:      flag[0] = true;
P0_gate: turn = 1;
         while (flag[1] == true && turn == 1)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[0] = false;


P1:      flag[1] = true;
P1_gate: turn = 0;
         while (flag[0] == true && turn == 0)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[1] = false;

하드웨어 해결 방법

코드의 명령문이 기계어로 변환 되어 각 코드 영역 내부의 원자성을 보존해주지 못하는 문제가 발견되기 때문에 하드웨어를 제어해줘야 한다.

• 원자성(Atomicity)이란 ? 중단 할 수 없는 가장 작은 운영의 단위
• 원자성을 보존해주기 위해 컴퓨터 자체에서 하드웨어의 명령어를 제공해준다.
• 해당 명령어는 test-and-set과 compare-and-swap으로 나뉜다.

Test-and-Set

bool test_and_set (bool *target){
    bool rv = *target;
    *target = true;
    
    return rv;
}

Compare-and-Swap

int compare_and_swap(int *value, int expected, int new_value){
    int temp = *value;
    if(*value == expected) {
        *value = new_value;
    }
    return temp;
}

위와 같은 명령어를 하나의 원자적인 명령어 로 만든다. 따라서 test_and_set 혹은 Compare-and-Swap 자체가 쪼갤 수 없는 가장 작은 단위이므로 해당 명령어 내부에서 중단될 일이 없다. 따라서 상호배재성을 확실히 보장해준다.

따라서 소프트웨어에서 위의 Atomic Variable 을 사용하여 상호배재성을 보장할 수 있다.

참고

• Peterson's algorithm

• 인프런 운영체제 공룡책 강의