[운영체제] 프로세스 동기화 문제와 해결 방법 - 경쟁상태, 임계구역, 뮤텍스, 세마포어 + 예시 코드

무엇이든지 하나일 때는 문제가 없다가, 둘 이상 혹은 n개 이상부터 모든 문제가 시작된다...! 운영체제의 프로세스 동기화에 대해 습득한 지식을 내가 이해한대로 정리해보았다.

1. Race condition(경쟁 상태)

공유하는 데이터에 동시에 접근하여 연산을 할 경우, 순서에 따라 상황별로 연산의 결과가 다르게 나올 수 있는 상태를 Race condition이라고 한다.

위 그림처럼 공유 변수인 sum을 두고 값을 1 증가시키는 프로세스 두 개가 동시에 실행된다면 순서에 따라 올바르지 않은 결과를 얻을 수 있다.

2. Critical Section(임계 영역)

race condition을 방지하기 위해 공유 데이터에 대한 연산 과정은 반드시 하나의 프로세스/스레드에 의해서만 실행이 되어야 하는데 그 영역을 Critical Section이라고 한다.

임계 영역 문제(critical section problem)를 해결하기 위한 필요 조건은 다음 세 가지이다.

Mutual exclusion 상호 배제 : 하나의 프로세스가 임계 영역에서 실행 중이라면, 다른 프로세스는 그 임계 영역에서 실행 중일 수 없다.
Progress : 현재 임계 영역에서 실행중인 프로세스가 없는 상태에서, 임계 영역을 실행하려는 프로세스가 있을 경우 이 프로세스가 실행될 수 있다.
Bounded waiting 한정된 대기 : 프로세스가 임계 영역을 실행하기 위해 무한정 대기하지 않는다.

3. Peterson's solution

critical section problem을 해결하기 위한 가장 고전적인 방법이다. 차례를 나타내는 변수 turn, 준비 상태를 나타내는 flag 배열을 공유 변수로 사용한다.

Peterson's solution의 pseudo code는 다음과 같다.

//공유 변수
int turn;
boolean flag[2];

while(true) {
	/* entry section */
    flag[i] = true;
    turn = j; //상대 프로세스에 먼저 양보 
    while(flag[j] && turn == j) 
        ; 
        /* critical section */
    
    /* exit section */
    flag[i] = false; 
    /* remainder section */
}

하지만 이 방법은 현대 컴퓨터 아키텍처에서 보장되지 않는데, 시스템 성능을 위해 프로세서나 컴파일러가 읽기/쓰기 명령을 재정렬하기 때문이다. 공유변수를 가진 멀티 스레드 어플리케이션이라면 명령을 재정렬하는 과정에서 예상치 못한 결과(=race condition)가 나올 수 있다. 코드로 직접 확인하면 아래와 같다.

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

//공유변수
int sum = 0;

//Peterson's solution의 공유변수
int turn;
int flag[2];

//sum값을 증가시키는 함수
void *producer(void *param) {
    int k;
    for(k=0; k < 100000; k++) {
        /* entry section */
        flag[0] = true;
        turn = 1;
        while (flag[1] && turn == 1)
            ;

        /* critical section */
        sum++;

        /* exit section */
        flag[0] = false;

        /* remainder section */
    }
    pthread_exit(0);
}

//sum값을 감소시키는 함수
void *consumer (void *param) {
    int k;
    for(k=0; k < 100000; k++) {
        /* entry section */
        flag[1] = true;
        turn = 0;
        while (flag[0] && turn == 0)
            ;

        /* critical section */
        sum--;

        /* exit section */
        flag[1] = false;

        /* remainder section */
    }
    pthread_exit(0);
}


int main()
{
    pthread_t tid1, tid2;
    pthread_create(&tid1, NULL, producer, NULL);
    pthread_create(&tid2, NULL, consumer, NULL);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    //동일한 횟수만큼 증가, 감소 시켰으니 출력 예상값은 0일 것이다.
    printf("sum = %d\n", sum);
    //하지만 결과가 0이 아닌 -2, -10, 2.. 등등 실행할 때마다 값이 바뀐다!
}

스레드를 두 개 생성하여 공유변수인 sum을 각각 produce와 consumer라는 함수를 통해 같은 횟수만큼 증감시켰으니 sum의 최종값은 0일 것이라 예상할 수 있다. 하지만 위 코드를 실행시켜보면 매번 다른 결과가 나오는 것을 확인할 수 있다. race condition이 발생했기 때문이다. 파일이 컴파일되고 기계어로 번환되는 과정에서 임계 영역에 대한 접근이 atomic하게 이루어 지지 않은 것이다.

(+자바에서는 java.util.concurrent.atomic 패키지의 AtomicBoolean클래스를 사용하면 동시성을 보장할 수 있다)

따라서 하드웨어 레벨에서 공유 변수에 접근했을 때 단 하나의 작업만 수행될 수 있도록, 즉 동기화가 될 수 있도록 보장이 되어야 한다. 하드웨어 단에서의 동기화 명령어로는 test_and_set, compare_and_swap 등이 있다. 하드웨어에서 동기화를 보장하는 방법을 이용해 소프트웨어 단에서도 동기화를 할 수 있는 여러 가지 장치가 있는데, 대표적으로 뮤텍스와 세마포어가 있다.

4. Mutex 뮤텍스

race condition을 방지하는 가장 대표적이고 간단한 동기화 도구이다. 락을 얻은 프로세스만 임계 영역을 수행할 수 있으며, 임계 영역을 수행한 후 락을 반환한다.

뮤텍스는 boolean 형태의 공유변수를 두고 락을 얻고(acquire), 락을 해제하는(release) 방식으로 구현된다. acquire, release는 하드웨어에서 atomic하게 실행되므로, race condition이 발생하지 않는다.

//공유 변수
bool available;

acquire() {
    while(avaliable==false) 
        ; /* busy wait */
    available = false;
}

release() {
    available = true; 
}

뮤텍스를 사용한 코드 예시는 아래와 같다. (c언어)

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

//공유변수
int sum = 0;

//뮤텍스
pthread_mutex_t mutex;

//sum값을 증가시키는 함수
void *add(void *param) {
    int k;
    for(k=0; k < 100000; k++) {
        /* entry section */
        pthread_mutex_lock(&mutex);

        /* critical section */
        sum++;

        /* exit section */
        pthread_mutex_unlock(&mutex);

        /* remainder section */
    }
    pthread_exit(0);
}


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

두 스레드가 동시에 공유 변수에 접근하여 값을 증가시킨다. 뮤텍스를 사용하여 lock을 관리한 결과, 예상한 결과값이 일정하게 나오는 것을 확인할 수 있다.

한편, 뮤텍스는 락을 얻기까지 락이 avaliable한지 while문 안에서 계속 체크하는 특징이 있다. 이러한 방법을 '스핀락'이라고 한다. 프로세스가 락을 얻기 전까지는 락을 얻을 수 있는지 확인하는 데에만 cpu 자원을 사용하기 때문에, spin lock이 걸려있는 동안 실질적으로 수행되는 작업은 없다. 그림을 통해 좀더 구체화 시켜보자면 아래와 같다.

싱글 코어에서 critical section에 진입하려는 두 프로세스가 있을 경우, 락을 획득한 첫번째 프로세스의 critical section의 작업이 context-switching이 일어나기 전에 끝나지 않는다면 락을 얻지 못한 두번째 프로세스는 아무런 작업도 하지 못하고 spinlock을 도는 데에만 시간을 보내야 할 것이다.

그러면, 스핀락은 무조건 나쁜걸까? - 그렇지 않다!

같은 상황에서 락을 획득한 첫번째 프로세스의 critical section의 작업이 context-switching이 일어나기 전에 완료된다면, 두번째 프로세스는 spinlock에 낭비하는 시간이 없어진다. 따라서 cpu 자원을 더욱 효율적으로 사용할 수 있다.

멀티코어를 사용할 경우에는 첫번째 프로세스에서 critical section을 수행을 완료한 후 context switching을 하지 않고 다른 코어에서 lock을 획득할 수 있어 context-switching으로 인한 오버헤드를 줄일 수 있다.

정리하자면, 스핀락은 프로세스간 컨텍스트 스위칭이 필요하지 않을 경우 cpu 자원 활용 부분에서 이점이 있다.

5. Semaphore 세마포어

뮤텍스는 boolean 변수를 사용하여 lock을 관리하였으므로 최대 2개의 프로세스만 뮤텍스 락을 사용할 수 있었다. 또한 뮤텍스는 spinlock이 발생하였기 때문에 cpu자원을 낭비할 수 있는 문제점이 있었다.

이를 보완하여 세마포어 개념이 등장하였는데, 세마포어는 integer값으로 여러 개의 프로세스 동기화를 관리할 수 있다. 또한 lock을 얻지 못하는 상황일 경우에는 프로세스 자기 자신을 waiting queue에 넣고 대기한다. lock을 얻을 수 있는 상황일 경우 waiting queue에 있는 프로세스를 깨워서 lock을 얻을 수 있게끔 한다. 기존의 스핀락과 다른점은, 락을 얻기 까지 계속해서 확인하는 것이 아니라 waiting queue에 자신의 프로세스를 넣고, 대신 다른 프로세스가 cpu에서 수행될 수 있게끔 한다는 것이다.

semaphore값을 1로 설정하면 0과 1로만 동작하므로 뮤텍스 락과 비슷하게 동작한다. 이를 binary semaphore라고도 한다.

세마포어의 내부 코드 구조는 아래와 같다. 뮤텍스와 마찬가지로 wait와 signal은 atomic하게 수행된다.

typedef struct
{
    int value;
    struct process *list; /* waiting queue */
}semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        //락을 획득할 수 없다면 자기 자신을 웨이팅 큐에 넣고 sleep
        add this process to S -> list;
        sleep();
    }
}

signal(semaphore *S) {
    S->value++;
    if(S->value <= 0) {
        //락을 획득할 수 있다면 웨이팅 큐에 있는 프로세스를 깨운다
        remove a process P from S -> list;
        wakeup(P);
    }
}

세마포어를 사용한 예시 코드는 다음과 같다.

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

//공유변수
int sum = 0;

//세마포어
sem_t sem;

//sum값을 증가시키는 함수
void *add(void *param) {
    int k;
    for(k=0; k < 10000; k++) {
        /* entry section */
        sem_wait(&sem);

        /* critical section */
        sum++;

        /* exit section */
        sem_post(&sem);

        /* remainder section */
    }
    pthread_exit(0);
}


int main()
{
    pthread_t tid[5]; int i;
    sem_init(&sem, 0, 5);
    //다섯 개의 스레드를 생성하여 공유변수에 진입
    for(i=0; i<5; i++) pthread_create(&tid[i], NULL, add, NULL);
    for(i=0; i<5; i++) pthread_join(tid[i], NULL);
    printf("sum = %d\n", sum);
}

위 코드를 직접 실행하면 공유변수에 대한 동기화가 잘 될 것이라는 예상을 깨고 결과값이 매번 다르게 나온다. 그 이유는 세마포어가 1보다 큰 정수일 경우 n개의 프로세스가 critical section에 동시에 진입이 가능하기 때문이다. 결국 다시 race condition이 발생하게 된다.

6. 마무리

race condition과 critical section에 대해 알아보고, 이를 해결하기 위한 장치에 대해 살펴보았다. 책에서 pseudo 코드만 봤을 때는 이해가 좀 어려웠는데, 실제로 스레드를 만들어 동작하는 코드를 이해했을 때 한층 더 깊이있게 이해하게 된 것 같다. 동시성 문제는 스레드, 프로세스, 데이터베이스 트랜잭션 등 거의 모든 영역에서 중요한 문제이므로 원리를 이해하면 다른 분야에도 더 쉽게 적용할 수 있을 것 같다. 다음에는 모니터와 동시성 문제 실제 경험 사례들을 정리해보고 싶다.

참고자료

Operating System Concepts(10th Edition), Abraham silberschatz

https://www.youtube.com/watch?v=gTkvX2Awj6g&t=987s - 쉬운코드 유튜브 영상

https://inf.run/ANmi - 인프런 운영체제 공룡책 강의

저작자표시

'운영체제' 카테고리의 다른 글

[운영체제] 프로세스와 스레드 (0)	2023.03.26
운영체제 목차 (0)	2023.03.20

레나의 개발 노트

[운영체제] 프로세스 동기화 문제와 해결 방법 - 경쟁상태, 임계구역, 뮤텍스, 세마포어 + 예시 코드

1. Race condition(경쟁 상태)

2. Critical Section(임계 영역)

3. Peterson's solution

4. Mutex 뮤텍스

5. Semaphore 세마포어

6. 마무리

'운영체제' 카테고리의 다른 글

티스토리툴바

[운영체제] 프로세스 동기화 문제와 해결 방법 - 경쟁상태, 임계구역, 뮤텍스, 세마포어 + 예시 코드

1. Race condition(경쟁 상태)

2. Critical Section(임계 영역)

3. Peterson's solution

4. Mutex 뮤텍스

5. Semaphore 세마포어

6. 마무리

'운영체제' 카테고리의 다른 글

관련글

티스토리툴바