동시성의 두 가지 모델 - 공유메모리 vs 메시지 전달

참고: https://web.mit.edu/6.005/www/fa14/classes/17-concurrency/#two_models_for_concurrent_programming

동시성

동시성은 여러 개의 계산이 동시에 일어나는 것을 의미한다. 동시성은 현대적 프로그래밍의 모든 곳에서 발생한다.

• 네트워크 상의 여러 컴퓨터들
• 하나의 컴퓨터에서 동작하는 여러 개의 어플리케이션
• 여러 개 프로세서를 가진 컴퓨터

실제로 현대적 프로그래밍에서 동시성은 필수적이다.

• 여러 명의 사용자를 동시에 처리해야 하는 웹 사이트
• 서버에서 여러 개의 모바일 앱에 필요한 작업을 수행하는 경우(클라우드)
• GUI 환경에서 사용자가 보는 UI 부분과 동시에 백그라운드 작업이 수행됨 (예를 들어 브라우저는 애니메이션을 보여주면서도 사용자의 입력을 받을 수 있음)

프로그램이 동시성을 가지고 동작하는 것은 미래에는 더욱 중요해 질 것이다. 프로세서의 계산 속도는 더이상 빨라지기 어렵다. 대신 우리는 미래의 칩 기술을 이용해서 점점 더 많은 코어를 가진 컴퓨터를 사용하게 될 것 이다. 그러므로 미래에는 계산이 빠르게 수행되려면 계산을 여러 개로 나누어 동시에 실행하는 수 밖에 없다.

동시 프로그래밍의 두 가지 모델

동시 프로그래밍에는 두 가지 모델이 있다. 공유메모리와 메시지 전달

공유메모리. 공유메모리 모델에서는 동시에 수행되는 모듈들이 메모리의 공유 객체를 읽고 쓰면서 상호작용한다.

두 프로세스가 공유 문서를 동시에 편집하는 것이 공유메모리 사용의 사례로 볼 수 있다.

• 하나의 문서를 메모장과 비쥬얼스튜디오가 동시에 열었을 때 두 프로세스는 하나의 공유메모리(파일)을 이용하고 있다.
• 두 사람은 각자 다른 프로세서에서 편집을 수행하고 있지만 구글에 있는 하나의 파일을 사용하고 있다.

메시지 전달. 메시지 전달 모델에서는 동시에 수행되는 모듈이 서로에게 메시지를 주고받으면서 수행한다. 모듈은 메시지를 보내거나 들어오는 메시지는 큐의 형태로 쌓이게 된다. 이것의 예는 다음과 같다.

• 두 개의 컴퓨터에 있는 프로그램이 네트워크로 통신하고 있다.
• 웹브라우저와 웹 서버라면 브라우저가 메시지로 요청을 보내고 서버가 결과를 메시지로 회신한다.
• 두 프로그램이 인스턴트 메시징 클라이언트와 서버라면 메시지 기반으로 통신할 것이다.

Processes, Threads, Time-slicing

메시지 전달과 공유메모리 모델은 동시수행 모듈들이 어떻게 통신하는가에 관한 것이다. 동시수행 모듈들은 프로세스와 스레드로 나누어진다.

프로세스. 프로세스란 실행되는 프로그램의 단위를 일컫는 말인데, 같은 기계에서도 독립적인 실행 단위가 된다. 특히 독자적인 메모리 부분을 가진다.

프로세스를 추상화한 것이 가상기계다. 가상기계는 흔히 그 자체가 컴퓨터 전체를 혼자 사용하는 것처럼 보인다. 마치 새로운 컴퓨터가 하나 생성되어서 새로운 메모리로 그 프로그램 하나만 실행하는 것처럼 해준다.

네트워크로 연결된 컴퓨터들처럼 프로세스들도 그들간에 메모리를 공유하지는 않는다. 프로세스는 다른 프로세스의 메모리나 객체를 절대 접근할 수 없다. 프로세스 간에 메모리를 공유하는 것은 대부분 OS의 특별한 지원에 의해 가능하다. 반면에 새로운 프로세스는 메시지 전달에 대해서는 자동으로 준비되어 있다. 왜냐하면 모든 프로세스는 기본적인 표준 입력과 출력 스트림을 가지는데 대부분의 프로그래밍 언어에서 이것을 Syste.out 과 System.in 스트림으로 사용 가능하기 때문이다. 

스레드. 스레드는 실행되는 프로그램 내부에서 제어에 핵샘이 되는 구조다. 그것을 실행되는 프로그램이 있는 곳이라고 생각해도 된다. 추가로 메소드 호출 스택을 가지는 구조라고 보면 된다.

프로세스와 마찬가지로 가상의 컴퓨터를 표현하는데 스레드는 가상 프로세서라고 볼 수 있다. 새로운 스레드를 만드는 것은 프로세스로 표현되는 가상 컴퓨터 내부에 새로운 프로세서를 만드는 것으로 생각해 볼 수 있다. 이 새로운 가상 프로세서는 동일한 프로그램의 일부이고 프로세스 내부의 다른 스레드와 메모리를 공유한다.

스레드는 자동적으로 공유 메모리를 이용할 수 있다. 스레드들은 프로세스 내부의 모든 메모리를 공유한다. 이것은 오히려 하나의 스레드에서만 사용할 수 있는 "스레드 전용" 메모리를 이용하려면 추가적인 노력이 든다는 의미다. 또한 스레드는 메시지 전달을 위해서도 명시적으로 큐 자료구조를 생성해 사용해야 한다. 이에 대해서는 뒤에서 살펴볼 것이다.

그럼 프로세서가 하나밖에 없는 컴퓨터에서 어떻게 여러 개의 동시 실행 스레드를 가질 수 있을까? 프로세서 수보다 더 많은 스레드가 있으면 동시성을 위해 시분할(time slicing)을 사용하게 된다. 그것은 프로세서가 스레드들을 바꿔가며 실행해 주는 것이다. 그림에서 오른쪽은 세 개의 스레드 T1, T2, T3가 두 개의 프로세서를 가진 기계에서 시분할 되는 것을 보여준다. 이 그림에서 시간은 아래 방향으로 흘러가는데, 첫 번째 프로세서는 T1을 실행하다가 T2 스레드를 실행한다. 또한 두번째 프로세서는 T2를 실행하다가 T3로 바꾸어 실행한다. 스래드 T2는 정지되고 다음에 어느 프로세서든 자기를 실행해줄 시분할 순서가 올 때까지 기다린다.

대부분의 시스템에서 시분할에 의한 전환은 예상할 수 없고 비결정적으로 일어난다. 즉 스레드는 언제든 정지되고 다시 실행될 수 있다는 의미이다.

공유메모리 예제

그럼 공유메모리 시스템의 예제를 살펴보자. 이 예제는 동시실행 프로그래밍이 교묘한 버그로 인해 다루기 어렵다는 것을 보여주기 위한 것이다.

은행에서 ATM 기계가 공유메모리 모델을 쓰고 있다고 가정해 보자. 그럼 모든 ATM 기계는 메모리의 동일한 계좌를 읽고 쓸 수 있다.

무슨 문제가 생기는지 보기 위해 은행에 계좌가 하나 밖에 없다고 가정하고 잔액은 balance 변수에 저장되어 있고 입금(deposit)과 출금(withdraw) 연산만 있다고 가정하자.

// suppose all the cash machines share a single bank account
private static int balance = 0;

private static void deposit() {
    balance = balance + 1;
}
private static void withdraw() {
    balance = balance - 1;
}

고객은 ATM기에서 다음과 같은 연산을 하려고 한다.

deposit(); // put a dollar in
withdraw(); // take it back out

이 간단한 예제에서 모든 거래는 항상 1달러 입금이거나 1달러 출금이다. 그러므로 이 연산을 수행한 후 balance 변수의 잔액은 변함이 없다. 하루 동안 네트워크 상의 여러 ATM 기계가 이러한 입금/출금 거래를 계속했다고 가정해 보자.

// each ATM does a bunch of transactions that
// modify balance, but leave it unchanged afterward
private static void cashMachine() {
    for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {
        deposit(); // put a dollar in
        withdraw(); // take it back out
    }
}

그럼 그날 자정에 몇개의 ATM기가 있든 관계없이 또 얼마나 많은 거래가 있었든지 관계없이 잔액은 0이어야 할 것이다.

그러나 이 코드를 실행하면, 우리는 그날 자정에 잔액이 0이 아닌 경우를 자주 보게 된다. 하나 이상의 cashMachine() 호출이 동시에 일어나면 - 즉 동일 컴퓨터의 다른 프로세서라고 생각해 보자 - 자정의 잔액은 0이 아닐 수 있다. 왜 그럴까?

인터리빙(Interleaving)

어떤 일이 일어날 수 있는지 한번 살펴보자. 두 ATM 기 A, B가 있다고 하자. 두 기계가 모두 동시에 입금을 하려고 한다. 다음 코드는 어떻게 deposit()  단계가 프로세서의 명령문 수준에서 나누어 질 수 있는지 보여준다.

get balance (balance=0)
add 1                 
write back the result (balance=1)

A와 B가 동시에 수행될 때 이들 낮은 수준의 명령문들은 서로 교차로 수행된다. (동시라고 할 수도 있으나 여기서는 일단 교차를 고려해 보자.)

A get balance (balance=0)
A add 1        
A write back the result (balance=1)
                                    B get balance (balance=1)
                                    B add 1     
                                    B write back the result (balance=2)

This interleaving is fine – we end up with balance 2, so both A and B successfully put in a dollar. But what if the interleaving looked like this:

A get balance (balance=0)
                                    B get balance (balance=0)
A add 1         
                                    B add 1     
A write back the result (balance=1)
                                    B write back the result (balance=1)

이 경우 잔액은 1이 된다. - A의 1달러가 없어졌다. A와 B는 동시에 잔액을 읽었고 따로 각자의 잔액을 계산했는데, 그 결과 새로운 잔액을 변수에 저장하기 위해 경쟁한다 - 그 결과로 계좌에 다른 ATM의 입금이 기록되지 못한다.

경쟁 조건(Race Condition)

이것이 경쟁조건의 예다. 경쟁조건은 프로그램의 동작(수행 결과)이 동시에 수행되는 A와 B의 상대적인 순서나 시간에 따라 달라지게 됨을 의미한다. 이런 일이 생기면 "A는 B와 경쟁한다"라고 말한다.

어떤 이벤트들은 교차되어도 문제가 없다. 즉 하나의 순차 프로세스가 수행한 결과와 동일한 결과를 낸다면... 그러나 다른 교차는 잘못된 결과를 낼 수가 있다.

코드를 복잡하게 꼬아도 문제가 해결될 수 없다

아래의 다양한 은행 거래 코드는 동일한 경쟁조건을 가지게 된다.

// version 1
private static void deposit() {
    balance = balance + 1;
}
private static void withdraw() {
    balance = balance - 1;
}

// version 2
private static void deposit() {
    balance += 1;
}
private static void withdraw() {
    balance -= 1;
}

// version 3
private static void deposit() {
    ++balance;
}
private static void withdraw() {
    --balance;
}

자바 코드를 보고 이들이 어떻게 실행될지 알 수가 없다. 개별 연산의 단위(아토믹 연산, 인터리빙되지 않고 실행되는 연산 단위)이 뭐가 될지 알 수 없다. 자바 코드의 한 줄이라고 해서 아토믹은 아니다. 잔액 변수가 코드에 한번 나온다고 그 변수를 한번만 접근하는 것이 아니다. 자바 컴파일러는 컴파일 결과 생성되는 저수준의 연산이 무엇인지에 대해 확실하게 알려주지 않는다. 사실 대부분의 자바 컴파일러가 만든 코드는 동일한 자바 프로그램에 대해 여러 가지 경우의 순서로 실행될 수 있다. 

그러므로 가장 중요한 점은 자바 프로그램이나 수식을 보고 이것이 경쟁조건에서 안전한가를 말할 수가 없다는 점이다.

재순서화 (Reordering)

사실 위에서 설명한 것보다 더 나빠질 수도 있다. 경쟁조건은 은행계좌 잔액에 저장하려는 서로 다른 프로세스들의 연산이 교차되는 방식으로 설명될 수 있다. 그러나 사실 여러 개의 변수와 여러 개의 프로세서를 쓰는 경우 같은 순서로 일어나는 변수 값의 변경을 따라가기도 어렵다.

다음 예제를 보자.

private boolean ready = false;
private int answer = 0;

// computeAnswer runs in one thread
private void computeAnswer() {
    answer = 42;
    ready = true;
}

// useAnswer runs in a different thread
private void useAnswer() {
    while (!ready) {
        Thread.yield();
    }
    if (answer == 0) throw new RuntimeException("answer wasn't ready!");
}

다른 스레드에서 실행되는 두 개의 메소드를 가지고 있다. computeAnswer는 긴 계산을 해서 42라는 값을 얻었는데, 그것을 answer 변수에 저장한다. 그리고 ready 변수를 참으로 바꾸어서 다른 스레드에서 동작하는 useAnswer() 메소드에게 그 값이 준비되었음을 알리려고 한다. 코드를 보면 answer는 ready가 set 되기 전에 설정되었고 useAnswer 는 ready가 참인 것을 보고 접근했으므로 answer가 42가 될 것으로 예상할 수 있다.

문제는 현대의 컴파일러와 프로세서들은 코드를 빠르게 실행하기 위해 많은 일을 한다는 점이다. 그런 일 중에는 ready나 answer 같은 변수의 값을 임시로 복사해서 지정된 변수의 메모리에 저장(store)하기 전에 사용한다는 점이다. storeback 연산은 당신의 자바 코드에서 처리하는 순서로 실행되지 않는다. 실제 일어날 수 있는 상황은 다음과 같다. (좀더 잘 알아보기 위해 그것을 자바 코드로 표현해 보았다) 프로세서는 tmpr과 tmpa라는 두 개의 임시 변수를 만들어서 ready와 answer 값을 다루게 된다.

private void computeAnswer() {
    boolean tmpr = ready;
    int tmpa = answer;

    tmpa = 42;
    tmpr = true;

    ready = tmpr;
                   // <-- what happens if useAnswer() interleaves here?
                   // ready is set, but answer isn't.
    answer = tmpa;
}

메시지 전달 예 (Message Passing Example)

다음은 은행 계좌 프로그램의 메시지 전달 방식을 살펴보자.

여기서는 ATM 기 뿐 아니라 계좌도 모듈이다. 여러 개의 모듈들이 메시지를 주고 받는다. 요청이 들어오면 큐에 들어가서 요청을 한개씩 처리한다. 송신자는 요청에 대한 답이 올 때까지 기다리지 않는다. 대신 자신의 큐에서 다른 요청을 처리하느라 바쁘게 움직인다. 자신이 보낸 요청에 대한 답은 또다른 메시지의 형태로 돌아온다.

그런데, 메시지 전달이 경쟁조건을 없애주는 것은 아니다. 각 계좌가 get-balance(잔액조회)와 withdraw(출금) 연산을 가진다고 가정해 보자. 두 사용자는 각각 A와 B라는 ATM 기계를 이용하는데 동시에 동일한 계좌에서 1달러를 출금하려고 한다. 그들은 잔액을 먼저 조회하고 출금을 하려고 한다. (마이너스 통장이 마이너스가 되는 걸 원치 않아서^^)

get-balance
if balance >= 1 then withdraw 1

이 문제는 여전히 교차로 실행되고 이번에는 두 계좌에서 실행되는 명령문이 교차되기 보다는 계좌로 보내는 메시지 순서가 교차될 수가 있다. 각 계좌가 1달러로 시작했다면 메시지의 순서가 얽히면서 A와 B가 동시에 그 계좌에서 1달러를 출금할 수 있게 된다.

여기서 알 수 있느느 것은 메시지 전달 모델의 연산을 신중하게 골라야 한다는 것이다. "withdraw-if-sufficient-funds" (잔액이 있으면 출금하라)라는 이벤트가 문제를 해결할 수 있을 것이다.

동시성은 테스트하고 디버그하기가 어렵다

여기까지 읽고도 동시성이 어렵다는 것이 실감나지 않는다면 여기 더 나쁜 문제가 있다. 경쟁 조건은 테스트를 통해서 발견되기 어렵다는 점이다. 그리고 설사 한번 그 버그가 발견되었다 해도 그 원인이 어디인지를 찾는 것은 더 어려운 문제다.

동시성 오류는 잘 재현되지 않는다. 동일한 방식으로 두번 발생되게 하는 것은 어려운 일이다. 명령문이나 메시지의 교차는 환경에 강한 영향을 받는 사건들의 상대적인 순서에 따라 달라지기 때문이다. OS의 스케쥴링 결정에 따라 다른 실행 프로그램이 좀더 오래 돌 수도 있다. 그러므로 결국 경쟁조건이 들어있는 프로그램은 실행할 때마다 다른 동작을 보여줄 것이다.

이런 종류의 버그를 "하이젠버그(heisenbugs)"라고 한다. 불확정성의 원리를 발견한 하이젠베르크와 버그의 합성어다. 반대로 "보어버그"는 실행할 때마다 반드시 나타나는 버그를 말한다. 순차 프로그래밍의 버그는 거의 대부분이 보어버그다.

하이젠버그는 출력이나 디버거를 통해 확인하고자 할 때는 사라져 보린다. 이유는 출력이나 디버깅이 원래 연산의 실행에 비해 너무 느리기 때문에 연산의 순서나 교차되는 방식을 완전히 바꾸어버린다. 그러므로 간단한 출력문을 cashMachine()에 넣어보면:

private static void cashMachine() {
    for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {
        deposit(); // put a dollar in
        withdraw(); // take it back out
        System.out.println(balance); // makes the bug disappear!
    }
}

… 갑자기 잔액이 0이 되고 버그는 사라져 버린 것처럼 보인다. 그러나 그것은 단순히 가려진 것 뿐이지 고쳐진 것이 아니다. 다른 곳에서의 시간 변경으로 인해 또 갑자기 버그가 나타나기도 한다.

동시성은 수정하기도 어렵다. 이 글의 목적은 어쨌든 이러한 문제를 경고하는 것이다. 이를 피하기 위해 어떻게 해야 하는가는 컴퓨터과학 전공의 주요한 관심사다.