운영체제 Ch6 - 프로세서 동기화(1)

배경

공유 데이터에 접근할 때 생기는 문제에는 data inconsistency가 있다. 데이터를 동시에 접근할 때 문맥 교환으로 인해 생기는 문제인데 예시를 통해 살펴보도록 하자.

int sum;

void run void param)
{
  int i;
  for (i = 0; i < 10000; i++)
      sum++;    
  pthread_exit(0);
}

int main()
{
  pthread_t tid1, tid2;
  pthread_create(&tid1, NULL, run, NULL);
  pthread_create(&tid2, NULL, run, NULL);
  pthread_join(tid1, NULL);
  pthread_join(tid2, NULL);
  printf("%d\n", sum);
}

위의 코드에서 두 개의 스레드는 sum이라는 전역변수를 공유한다. 둘 모두 10000이 나와서 전역변수가 20000이 되어야 할 것 같지만 매번 올바른 값이 나오지는 않는다. 이유는 sum++이라는 코드를 실제 기계어로 본다면 하나의 코드가 아닌 여러 개의 코드로 이루어져 있기 때문에 이 코드가 실행되다가 중간에 문맥 교환이 일어날 수 있기 때문이다. 

명령어 수행 중 문맥 교환

이러한 상태를 Race Condition 즉, 경쟁상태라고 한다. 같은 데이터에 동시에(concurrent) 접근하면서 접근하는 순서에 따라 데이터가 일치하지 않을 수 있는 것이다. 경쟁 상태를 막기 위해서는 공유 자원에 접근할 때 한 번에 하나의 프로세스만 접근하게끔 하여 데이터 불일치 문제를 막아야 하는데 이를 process(or thread) synchronization(프로세스 동기화)라고 한다.

임계 구역 문제

앞서 살펴본 것처럼 우리는 한 번에 한 스레드만 업데이트하는 동기화를 고려해야 한다. 이러한 문제를 임계 구역 문제라고 한다. 여러 개의 스레드로 이루어진 시스템에서 각각의 스레드는 코드 영역을 가지고 있는데 이를 임계구역이라고 한다. 여기서는 공통으로 사용하는 데이터를 가진다. 임계구역에서 가장 중요한 것은 임계 구역 내에서는 반드시 하나의 프로세스만 실행되어야 한다는 것이다.

 

코드 영역은 크게 4가지로 나뉜다. 먼저 임계 구역으로 진입하는 entry section, 문맥 교환이 일어나지 않아야 하는 critical section, 임계 구역에서 빠져나온 exit section, 그 외의 영역인 remainder section으로 나뉜다. 

 

코드 영역

임계구역 문제 해결 조건

임계 구역 문제를 해결하기 위해서는 3가지의 조건이 필요하다. 먼저 상호배타(Mutual Exclusion)은 가장 기본이 되는 조건으로 반드시 지켜져야 하는데, 한 프로세스가 임계구역으로 들어왔을 때 다른 프로세스가 접근하지 못하게 하는 것이다. 그리고 프로세스가 임계구역에 접근하지 못하게 되는 데드락을 피하기 위한 진행(Progress)이 필요하다. 마지막으로 기아 문제를 해결하기 위해 프로세스가 무한정으로 대기하는 것을 막기 위한 유한 대기(Bounded Waiting) 또한 필요하다. 하지만 이 3가지를 모두 충족하기란 쉽지 않기 때문에 현대 운영체제에서는 진행과 유한 대기는 발생할 때 해결하는 회피 방법을 사용한다,

싱글 코어와 멀티 코어

싱글 코어에서는 프로세스가 실행되는 동안에는 인터럽트를 발생하지 않게 함으로써 임계 구역 문제를 해결할 수 있다. 하지만 현대의 컴퓨터는 대부분 멀티 코어이고 코어가 여러 개 있을 때는 모든 코어에 인터럽트를 걸어주어야 하기 때문에 굉장히 비효율적이다.

선점과 비선점

임계 구역은 크게 두 가지 접근법으로 살펴볼 수 있다. 비선점 커널은 프로세스가 자동으로 exit될 때까지 기다리는 형태이기 때문에 경쟁 상태를 걱정하지 않아도 된다. 하지만 현대의 대부분의 운영체제들은 모두 선점형으로 구현되어 있기 때문에 우리는 선점형일 때를 고려해보아야 한다. 

피터슨 해결책

이러한 임계 구역 문제를 해결하는 알고리즘에는 다양한 방법이 있지만 피터슨 알고리즘은 가장 전통적인 소프트웨어 해결방법이다. 이 알고리즘이 방법은 간단한데, 두 개의 프로세스가 임계 구역과 나머지 구역 사이를 왔다갔다하며 상호배타성을 지키는 것이다. 

피터슨 알고리즘

위의 코드에서 볼 수 있다시피 flag와 turn을 이용하여 임계 구역에 들어갈 때 표시를 하는 것이다. 예시를 들어보자. 강아지와 산책을 나가야 하는데, 산책을 하다가 옆집 강아지를 만나기만 하면 싸운다. 이를 해결하기 위해 옆집과 의논하여 한 사람이 산책을 나가면 flag를 통해 산책하고 있다는 것을 알리고, 그 동안 다른 사람은 산책을 나가지 않는 것이다. 

 

하지만 피터슨 알고리즘 또한 올바르게 동작할 것이라는 것을 보장해주지 못한다는 점에서 완벽하지 않다. 이는 기계어 레벨에서 while (flag[j] && turn == j) 명령어를 분석해보면 이 또한 하나의 명령어가 아니라 여러 명령어의 집합으로 실행되는 것을 알 수 있다. 이 때문에 앞서 살펴보았던 경쟁 상태가 완벽히 보완되지 않는 것이다.

 

피터슨 알고리즘은 비록 실제로는 완벽하게 임계 구역 문제를 보장해주지는 못하지만 3가지의 조건을 모두 만족하는 이론적으로 가장 올바른 알고리즘이라는 것을 알아두자.

동기화를 위한 하드웨어 기반 해결

피터슨 알고리즘을 통해 소프트웨어 단에서는 임계 구역 문제를 완벽하게 해결할 수 없다는 것을 알게되었다. 따라서 이를 해결하기 위해서는 하드웨어 단에서 동기화를 고려해보아야 한다.

원자성(Atomicity)

원자성이란 더이상 쪼갤 수 없는 즉 더 이상 인터럽트를 걸 수 없는 명령어의 단위이다. test_and_set()이나 compare_and_swap()과 같은 인스트럭션이 있다.