[운영체제 4] 프로세스 동기화(Synchronization)

2024-04-07 6 분 소요

동기화(Synchronization)란?

각 프로세스와 스레드들은 동시다발적으로 실행되기 때문에, OS는 프로세스/스레드의 실행 순서와 자원의 일관성을 보장해야한다.

이 절차를 동기화(synchronization)라 하며, 크게 프로세스/스레드의 순서를 올바르게 제어하는 ‘실행 순서 제어’와 동시에 접근해서는 안 되는 자원에는 하나의 프로세스만 접근 시키는 ‘상호 배제’로 나뉜다.

공유 자원(Shared Resource)과 임계 구역(Critical Section)

그럼 그 ‘동시에 접근해서는 안 되는 자원’은 무엇일까? 눈치껏 “공유 자원”이라고 답하겠는가? 땡~

한 작업에서 공동으로 사용되는 자원을 공유 자원(shared resource)이라고 부르는 것은 맞다. 다만 이 공유 자원이 항상 동시에 접근해서는 안 되는 것은 아닌가보다?

공유 자원으로는 전역 변수를 포함해 상황 별로 파일, 입출력장치, 보조기억장치가 다 들어맞을 수도 있다. 이중에서 동시에 접근해서는 안되는 전역 변수를 살펴보자.

다음 도식을 보면 전역 변수 Y에 대해서 스레드 1은 Y + 1을, 스레드 2는 Y * 2를 계산한다. 만약 스레드 1과 2가 순차적(sequential)으로 계산이 됐다면 답은 (5 + 1) * 2 = 12가 돼야 할 것이다. 그러나 저장된 값은 스레드 1의 계산 결과인 6에 불과하다. 왜 이렇게 된 걸까?

스레드 1이 Y에서 값을 불러온 뒤 스레드 2가 실행되기 위하여 문맥 교환이 일어났는데, 스레드 2가 먼저 답을 저장해버리면서 다시 문맥 교환이 일어나 스레드 1로 돌아갔을 때, 바뀐 값을 인지하지 못하고 그대로 덮어버리게 된 것이다.

이렇듯 동시에 실행하면 안 되는 공유자원에 접근하는 코드 영역을 임계 구역(critical section)이라 하고, 위처럼 여러 프로세스나 스레드가 동시에 임계 구역의 코드를 실행하여 문제가 발생한 것을 레이스 컨디션(race condition; 경쟁 상태)이라고 한다.

레이스 컨디션은 데이터의 일관성을 깨는데, 특히 고급 언어가 저급 언어로 변환되면서 여러 줄로 프로세스를 실행하게 되고, 이 과정의 문맥 교환에서 레이스 컨디션이 발생할 수 있는 것이다.

이와 관련한 문제를 살펴보자.

생산자-소비자 문제(Producer-Consumer Problem)

#include <iostream>
#include <queue>
#include <thread>

void produce();
void consume();

//std::queue<int> q;
int sum = 0;

int main() {

    std::cout << "초기 합계: " <<  sum << std::endl;
    std::thread producer(produce);
    std::thread consumer(consume);

    producer.join();
    consumer.join();
    
    std::cout << "producer, consumer 스레드 실행 이후 합계: " <<  sum << std::endl;
    
    return 0;
}

void produce() {
    for(int i = 0; i < 100000; i++) {
        // q.push(1);
        sum++;
    }
}

void consume() {
    for(int i = 0; i < 100000; i++) {
        // q.pop();
        sum--;
    }
}

/* [실행 결과]
초기 합계: 0
producer, consumer 스레드 실행 이후 합계: 25845 */

분명 원래라면 생산도 10만 번, 소비도 10만 번 이뤄져서 sum은 여전히 0이어야 하지만, 무슨 이유인지 25845라는 값이 나왔다. 이는 두 스레드가 결합된 상태에서(임계 구역 침범) 레이스 컨디션이 생겨 당초 예상한 값과 다른 결과가 나온 것이다. 즉 동시 접근해서는 안되는 공유 자원에 동시에 접근한 것이 원인이다.

상호 배제(Mutual Exclusion)

OS는 이런 임계 구역 문제를 해결하기 위해 3가지 원칙을 세웠다.

Three Principles for Synchronization

상호 배제(mutual exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어갈 수 없다.
진행(progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
유한 대기(bounded waiting): 한 프로세스 임계 구역에 들어오기 위해 무한정 대기해서는 안 된다.

상호 배제가 특히 핵심인데, 관련해서 데이크스트라(다익스트라)가 고안한 문제를 살펴보자.

최단 경로 문제(shortest path problem)의 해결책인 다익스트라 알고리즘을 고안한 그 아저씨.. 후술할 ‘세마포어’에 대해서 처음으로 연구한 학자이기도 하다.. 무친 사람..

식사하는 철학자 문제(Dining Philosophers Problem)

“다음과 같이 철학자 다섯 명이 원탁에 둘러앉아 스파게티를 먹으려 하는데, 하필 포크가 각 사람들 사이에 하나씩 놓여 있다. 스파게티를 먹으려면 포크가 두 개 있어야만 하고, 각 철학자는 서로 대화를 할 수 없다. 즉 철학자들은 혼자 생각을 하거나 옆의 포크를 집어야 하는 두 가지 행동밖에 취하지 못한다. 각 철학자는 일정 시간 스파게티를 먹고 나면 반드시 포크를 내려둬야 한다. 이때 다섯 명이 모두 스파게티를 먹으려면 어떻게 해야겠는가?”

뭐 이런 건데 각자 왼쪽의 포크를 들게끔 알고리즘을 짜면 아무 것도 못하는 교착(deadlock) 상태가, 누군가가 스파게티를 먹다보면 다른 사람은 기아(starvation) 상태에 빠지게 된다. 어떻게 해결할 수 있을까? 여러 해결책이 있지만 동기화의 관점으로 찾아보자!

동기화 기법

뮤텍스 락(Mutex Lock; MUTual EXclusion)

먼저 상호 배제 잠금, 즉 뮤텍스 락(mutex lock)이다. mutex는 상호 배제의 약어다.

자물쇠 하나를 두고 해당 자물쇠를 잠그는 acquire(lock) 함수와 해제하는 release(unlock) 함수의 구현으로 이뤄진다.

acquire 함수는 프로세스의 진입 전에 임계 구역이 열릴 때까지 임계 구역을 반복적으로 확인(busy waiting: 바쁜 대기)하고, 임계 구역이 열려 있다면 임계 구역을 잠근다. 즉 lock이 false가 되면 기회를 틈타 true로 바꾼다.

release 함수는 임계 구역에서의 스레드가 끝나면 호출이 되는 함수로, lock을 true에서 false로 바꾼다.

즉 프로세스는 락을 획득할 수 있다면(임계 구역에 진입할 수 있다면) 임계 구역을 잠근 뒤 임계 구역에서의 작업을 진행하고, 락을 획득할 수 없다면(임계 구역에 진입할 수 없다면) 유한한 시간만큼 기다리다가 락이 풀리면 다시 진입을 시도한다. 위의 goroutine 2와 3이 attempt를 했으나 진입하지 못하고 일정 시간 기다리는 것을 보라. 코드 구현은 다음과 같이 하면 된다.

#include <stdio.h>
#include <pthread.h>
#define NUM_THREADS 4
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int shared = 0;

void *foo()
{
    pthread_mutex_lock(&mutex); // 뮤텍스 락
    for (int i = 0; i < 10000; ++i) {
        shared += 1;
    }
    pthread_mutex_unlock(&mutex); // 뮤텍스 언락
    return NULL;
}

int main()
{
    pthread_t threads[NUM_THREADS];
    for (int i = 0; i < NUM_THREADS; ++i) {
        pthread_create(&threads[i], NULL, foo, NULL);
    }
    for (int i = 0; i < NUM_THREADS; ++i) {
        pthread_join(threads[i], NULL);
    }
    printf("final result is %d\n", shared);
    return 0;
}

카운팅 세마포(Counting Semaphore)

앞서 짚은 뮤텍스 락은 크게 두 가지 문제가 있다. 첫째, 공유 자원이 여러 개인 상황은 상정하지 못한다. 둘째, 바쁜 대기로 인해 CPU의 효율이 떨어진다. 이를 해결하기 위해 등장한 것이 (카운팅) 세마포(semaphore: 수기(手旗))이다.

이제 우리는 뮤텍스 락의 전역 변수 lock이 아닌, 새로이 전역 변수 S를 살펴볼 것이다. S는 임계 구역에 진입할 수 있는 프로세스의 개수(사용 가능한 공유 자원의 개수)를 의미한다. S가 0 이하이면 프로세스는 임계 구역에 진입하지 못한다.

위의 acquire/release와 달리 이번엔 wait와 signal 함수로 대체할 것이다. wait 함수는 임계 구역에 진입 전, 진입이 가능한지를 판단하는 함수이고, signal 함수는 기다리는 프로세스들에게 진입을 허가하는 함수이다.

wait는 자신이 호출될 때마다 S를 1씩 감소시키는데, 만약 감소된 S가 음수로 떨어진다면 진입이 불가능한 것이므로 해당 요청을 한 프로세스는 스스로를 대기 상태로 block한다. 해당 프로세스의 PCB는 세마포를 위한 대기 큐에 삽입되고, 이후 signal 함수가 S를 1씩 증가하며 호출이 되면 해당 대기 큐에서 제거되어(=wake up) 준비 상태로 변경되는 것이다. 마치 스케줄링 큐의 인터럽트와 같다!

이 방법의 장점은 바쁜 대기(busy waiting)가 없다는 것, 그리고 wait()를 통해 각 프로세스의 진입 순서를 제어할 수 있다는 것이다. 코드 구현은 다음과 같다.

from threading import Thread, Semaphore
num = 0
sem = Semaphore(1)

def foo(sem):
    global num
    sem.acquire()
    for _ in range(100000):
        num += 1
    sem.release()

if __name__ == '__main__':
    t1 = Thread(target=foo, args=(sem,))
    t2 = Thread(target=foo, args=(sem,))
    t1.start()
    t2.start()
    t1.join()
    t2.join()
    print(num)

모니터(Monitor)

그런데 이처럼 항상 wait와 signal 함수를 사용하다가 보면 코드가 방대해지고 꼬이는 경우도 있을 수 있다. 이를 위해 이를 묶어 하나의 인터페이스(통로)로 관리하는 동기화 도구가 탄생했는데, 바로 모니터(monitor)다.

다음과 같이 진입 큐(entry queue)를 만들어 임계 구역으로의 진입을 상호 배제하고, 조건 변수(CV)(Conditional Variable)라는 큐를 만들어 앞선 wait와 signal 연산을 수행하는 것이다. 즉 두 번 기다려야하는 것이다.

wait가 호출되면 waiting list에 들어가 대기 상태(blocked)로 있다가, signal이 호출되어야 비로소 공유 자원으로의 접근이 가능해지는 시스템. 이때 signal은 모니터 안에 실행되는 프로세스가 호출하는데, 호출 뒤 호출한 프로세스는 일시 중단하고 대기 상태로 있던 프로세스가 동작하는 경우를 Signal & Wait 방식, 호출한 프로세스가 일단 끝까지 수행되는 경우를 Signal & Continue 방식이라고 부른다.

public class BoundedBuffer<E>
{
    private static final int BUFFER_SIZE = 5;
    private E[] buffer;
    public BoundedBuffer() {
        count = 0;
        in = 0;
        out = 0;
        buffer = (E[]) new Object[BUFFER_SIZE];
    }
    /* 생산자가 호출하는 코드 */
    public synchronized void insert(E item) {
        while (count == BUFFER_SIZE) {
            try {
                wait();
            }
            catch (InterruptedException ie) {}
        }
        buffer[in] = item;
        in = (in + 1) % BUFFER_SIZE;
        count++;
        notify();
    }
    /* 소비자가 호출하는 코드 */
    public synchronized E remove() {
        E item;
        while (count == 0) {
            try {
                wait();
            }
            catch (InterruptedException ie){}
        }
        item = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        count--;
        notify();
        return item;
    }
}

(이외에도 대키 큐의 모든 프로세스를 깨우는 broadcast()가 있다고 한다. 자세한 건 나도 지금 잘 이해가 안돼서.. 아래 영상에 설명이 잘 나와 있으니 다시 와서 복습하는 걸로 하자.)

출처: [혼자 공부하는 컴퓨터구조+운영체제 Chapter 12]

Twitter Facebook LinkedIn