[OS - 7] 프로세스 동기화

프로세스 동기화

프로세스(또는 스레드)는 동시에 그리고 병렬로 실행된다. CPU 코어는 각 프로세스를 빠르게 전환해 실행함으로써 프로세스는 동시에 실행된다. 또한 각 CPU 코어는 하나의 프로세스를 실행함으로써 프로세스는 병렬로 실행된다. 이 같은 동작 방식은 CPU 사용률을 높이지만 한 가지 문제가 있다.

 

두 개 이상의 프로세스가 공유 데이터에 동시 접근할경우 데이터의 일관성이 깨질 수 있다. 이와 같은 상황은 매우 빈번하게 발생한다. 아래는 예시 상황이다.

• 두 개 이상의 스레드가 힙 영역, 데이터 영역의 데이터에 동시 접근
• 두 개 이상의 프로세스가 파일, 메모리, 소켓, 외부 장치 등 컴퓨터 자원 또는 OS의 자원에 동시 접근 
• 두 개 이상의 커널 모드 프로세스가 커널 자료구조(열린 파일 목록 리스트, 메모리 할당 관리 자료구조, 프로세스 리스트 자료구조 등)에 동시 접근

데이터 일관성이 깨지는 걸 직접 확인해 보자. 아래는 두 개의 스레드가 데이터 영역의 데이터에 동시 접근하는 C 코드이다.

#include <stdio.h>
#include <pthread.h>

int count;

void *run(void *param)
{
	int i;
    for(int i = 0; i < 10000; i++)
    	count++;
    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", count);
}

출력되는 count의 값은 항상 20000이 되어야 한다. 하지만 실행해 보면 20000이 출력되지 않는 경우가 있다. 데이터 일관성이 깨진 것이다. 왜 다른 값이 나올까? 위 run 함수의 count++는 아래의 어셈블리어로 변환되어 실행된다. (고급 언어는 컴파일러에 의해 어셈블리어 또는 기계어로 번역 된다.)

여기서 스레드는 동시에 그리고 병행 수행된다. thread 1의 하나의 명령어 실행 이후 컨텍스트 스위칭이 발생해 thread 2가 수행될 수 있으며 thread1와 thread2가 서로 다른 CPU 코어에서 병행 수행될 수 있다. 따라서 thread1와 thread2가 수행될 경우 명령어 실행 순서는 아래와 같이 여러 경우의 수가 발생한다. (각 스레드의 명령어 실행 순서는 변하지 않는다.)

만약 두 번째, 세 번째 경우의 수가 발생한다면 count의 값은 정상적으로 20000이 나올 수 없다. count의 값이 스레드의 접근 순서에 따라 달라지는 것이다. 이렇듯 여러 프로세스가 공유 데이터에 접근해 조작하고 공유 데이터의 값이 프로세스의 접근 순서에 의해 결정되는 상황을 경쟁 상황(race condition)이라 한다. 경쟁 상황이 발생하면 공유 데이터의 값은 접근 순서에 결정되므로 값이 일관적이지 않아 데이터 일관성이 깨진다. 따라서 우리는 한순간에 한 프로세스만이 공유 데이터에 접근하도록 프로세스들을 동기화해줄 필요가 있다.

임계 구역 문제

공유 데이터에 대한 프로세스 동기화는 임계 영역 문제로부터 시작한다. 임계 영역은 다른 프로세스와 공유하는 데이터에 접근(acessing or updating)하는 코드 영역을 말하며 임계 영역 문제는 한 프로세스가 자신의 임계 영역을 실행하는 동안 다른 프로세스가 자신의 임계 영역에 들어가지 못하도록 만드는 문제를 말한다. 임계 영역 문제를 해결하면 한 순간에 오직 한 프로세스만이 임계 영역을 수행하여 경쟁 상황을 방지할 수 있게된다.

 

프로세스의 코드 영역은 아래와 같이 나눌 수 있다.

• 진입 영역(entry section) : 임계 영역 진입 시 진입 허가를 요청하는 코드 영역
• 임계 영역(critical section) : 다른 프로세스와 공유하는 데이터에 접근하는 코드 영역
• 퇴출 영역(exit section) : 임계 영역에서 퇴출하는 코드 영역
• 나머지 영역(remainder section) : 임계 영역이 아닌 나머지 코드 영역

임계 영역 문제에 대한 해결안은 아래의 세 가지 조건을 충족해야 한다.

• 상호 배제(mutual exclusion) : 한 프로세스가 임계 구역을 실행하고 있으면 다른 프로세스는 임계 구역에 진입할 수 없다.
• 진행(progress) : 임계 영역을 실행하고 있는 프로세스가 없고 다른 프로세스들이 임계 영역 진입을 원할 때, 임계 영역에 진입할 프로세스 선택은 무한정 연기될 수 없다. (데드락 방지)
• 한정된 대기(bounded waiting) : 임계 영역 진입을 위한 대기 시간은 한정된 시간이어야 한다. (기아 방지)

하지만 위 세가지 조건을 충족시키는 해결안은 현실적으로 불가능하기에 데드락 또는 기아는 최대한 회피하는 식으로 해결한다.

소프트웨어 해결안

임계영역 문제를 해결하는 고전적인 알고리즘으로 Peterson's Algorithm이 있다. 피터슨 알고리즘은 두 개의 프로세스를 동기화한다. (N개의 프로세스로 확장할 수 있다.) 동작 방식은 간단하다. 두 개의 프로세스가 번갈아가면서 임계영역을 실행하는 식이다. 피터슨 알고리즘을 적용할 두 개의 프로세스 P𝑖, P𝑗가 있고 두개의 데이터 항목을 공유한다.

int turn;
boolean flag[2];

P𝑖의 코드는 아래와 같다.

Peterson 해결안에서 프로세스 P𝑖의 구조

피터슨 알고리즘은 상호 배제, 진행, 한정된 대기 조건을 모두 충족한다.

• 상호 배제 : 두 개의 프로세스가 임계 영역에 진입 요청 시 turn 변수로 인해 무조건 한 프로세스만이 임계영역에 진입한다. 또한 한 프로세스가 임계 영역을 실행하고 있으면 다른 프로세스는 임계 영역에 진입할 수 없다. 그로 인해 상호 배제 조건이 충족된다.
• 진행, 한정된 대기 : 하나의 프로세스가 임계 영역을 실행했으면 무조건 그 다음에는 다른 프로세스가 임계 영역을 수행한다. 이로 인해 진행과 한정된 대기 조건이 충족된다.

하지만 피터슨 알고리즘이 올바르게 수행된다고 보장할 수 없다.