동시성 제어 - by 직렬화(serialization)

여러 스레드가 동시에 실행되는 프로그램을 만들 때는 공유변수에 대한 할당(assignment) 연산을 조심해서 사용해야 한다.
서로 다른 스레드들이 수행하는 할당 연산들의 순서를 제어할 수 없기때문이다.
다수의 할당 연산이 동시에 진행되는 상황이 발생할 수 있다면 시스템이 올바르게 행동하게 만드는 수단을 마련해야 한다.
다시 말해, 동시적 프로그램이 올바르게 행동하게 만들기 위한 약간의 제약이 필요하다.

동시성 제어를 위해 사용할 수 있는 전략

1. 하나의 공유 변수에 대해 둘 이상의 연산이 동시에 적용될 수 없게 만든다.
   즉, 한 번에 하나의 트랜잭션만 진행되게 한다.
2. 스레드들이 프로그램을 동시에 실행할 때 그 실행순서가 어떻든 동일한 결과가 나오게 설계한다.
3. 많은 수의 스레드가 부분 영역을 담당하게 하며, 각 스레드는 주기적으로 자신의 값 주변 스레드 값들을 이용하여 갱신(보정)한다.
   (값이 정확하게 떨어지지 않는 연속적인 물리량.. 이런 거 시뮬레이션 할 때 쓸법한 방법이다)

동시성 제어 메커니즘

(a, b, c)를 실행하는 스레드 1과 (x, y, z)를 실행하는 스레드 2가 있다고 가정해 보자.
이때 발생가능한 순서의 가짓수는 20가지이다.

(a b c x y z) (a b x c y z) (a b x y c z) (a b x y z c) (a x b c y z)
(a x b y c z) (a x b y z c) (a x y b c z) (a x y b z c) (a x y z b c)
(x a b c y z) (x a b y c z) (x a b y z c) (x a y b c z) (x a y b z c)
(x a y z b c) (x y a b c z) (x y a b z c) (x y a z b c) (x y z a b c)

cf. 같은 것이 있는 순열문제로 생각하면 쉽게 경우의 수를 구할 수 있다. (₆P₆ ÷ ₃P₃ ÷ ₃P₃ = 20)

 

스레드수와 사건수가 늘어날수록 이런 시스템을 설계할 때 프로그래머가 이 모든 케이스를 고려해서 행동을 점검하는 건 사실상 불가능하다.
보다 현실적인 접근 방식은 스레드들의 교대 실행에 제약을 가해서 프로그램이 올바르게 작동하게 하는 일반적인 메커니즘을 적용하는 것이다.

그런 메커니즘 중 하나로, 공유 상태에 대한 접근의 직렬화(serialization)에 대해 알아보자.

공유 상태에 대한 접근의 직렬화(serialization)

여러 스레드가 동시에 실행할 수 없는 함수의 집합을 설정하는 메커니즘을 통해 동시성 제어를 실현하는 방법을 말한다.

직렬화기(serializer)

직렬화를 실제로 구현하는 직렬화기(serializer)는 하나의 함수를 받고 그 함수와 동일하게 행동하되 접근이 직렬화된 함수를 return 하는 함수이다.

직렬화기 예시를 살펴보기 전에 우선 concurrent_execute라는 함수를 가정하자.
이 함수는 매개변수로 받는 각 f들에 대해 분리된 스레드를 생성하며 스레드들은 모두 동시적으로 실행된다.

// f1, f2, ... 를 각자 실행하는 분리된 여러개의 스레드를 생성 및 실행하는 함수
function concurrent_execute(f1, f2, ...) {}

공유자원 x에 대해 다음 연산을 수행하는 스레드 T1, T2가 있다고 하자.

T1 : x = x * x
T2 : x = x + 1

두 스레드를 동시적으로 생성 및 실행하는 코드는 다음과 같이 작성할 것이다.

let x = 10; 
concurrent_execute(() => { x = x * x; }, () => { x = x + 1; });

공유자원 x에 접근 혹은 할당하는 사건에 a~e의 기호를 부여했다.

T1 : a. 왼쪽 피연산자 x에 접근, b. 오른쪽 피연산자 x에 접근, c. x에 연산된 값을 할당
T2 : d. 왼쪽 피연산자 x에 접근, e. x에 연산된 값을 할당

이때 a-b-c, d-e의 순서가 고정된 a, b, c, d, e의 순서쌍의 가짓수는 10가지(₅P₅ ÷ ₃P₃ ÷ ₂P₂)이다.
x의 최종값은 5가지로 귀결된다.

• 101: (a b c d e)
• 121: (d e a b c)
• 110: (a d e b c), (d a e b c)
• 11: (a b d c e), (a d b c e), (d a b c e)
• 100 : (a b d e c), (a d b e c), (d a b e c)

여기서 직렬화기를 이용하여 T1, T2가 실행하는 각 함수가 동시 실행되지 않도록 제한하면 어떻게 동작할까?

let x = 10; 
// 직렬화기 s를 생성
const s = make_serializer();
concurrent_execute(s(() => { x = x * x; }), s(() => { x = x + 1; }));

같은 직렬화기에 의해 직렬화된 함수끼리는 한 번에 한 가지 함수만 실행가능하다. 따라서 동작중에 다른 함수가 침범할 수 없다.

앞에서 a~e 부호를 부여하는 방법과 같은 방식으로 접근해 보자면, 직렬화된 함수 본문 전체에 기호 a, b를 부여하는 셈이 된다.

이때 x의 최종값은 2가지로 축소된다.

• 101: (a b)
  = T1 실행 후 T2를 실행
• 121: (b a)
  = T2 실행 후 T1을 실행

여러 개의 공유 자원에 대한 동시성 제어

위에서 살펴보았듯 직렬화기는 동시 실행프로그램을 제어하는 데에 직관적이면서도 강력한 도구가 된다.

그런데 만약 동시적으로 제어해야 할 공유자원이 여러 개가 되면 어떻게 해야 할까?

 

예를 들어 두 계좌의 잔액을 서로 교환하는 함수 exchange가 있다고 해보자.

이 함수에서 접근하는 공유자원은 account1의 잔액과, account2의 잔액이다.

만일 여러 개의 스레드에서 exchange를 동시 실행한다면 한 개의 직렬화기로는 exchange 함수의 직렬화를 보장할 수 없다.

function exchange(account1, account2) {
    const difference = account1("balance") - account2("balance");
    account1("withdraw")(difference);
    account2("deposit")(difference);
}

 

해결책은 간단하다. 두 공유자원의 직렬화기를 모두 사용하여 총 두 번 직렬화하면 된다.

function make_account_and_serializer(balance) {
    function withdraw(amount) {
        if (balance > amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const balance_serializer = make_serializer();
    return m => m === "withdraw"
                ? withdraw
                : m === "deposit"
                ? deposit
                : m === "balance"
                ? balance
                : m === "serializer"
                ? balance_serializer
                : error(m, "unknown request -- make_account");
}

const a1 = make_account_and_serializer(100);
const a2 = make_account_and_serializer(200);
const a3 = make_account_and_serializer(300);

function serialized_exchange(account1, account2) {
    const serializer1 = account1("serializer");
    const serializer2 = account2("serializer");
    // 두 account의 직렬화기를 모두 이용하여 직렬화를 2번 수행한다.
    serializer1(serializer2(exchange))(account1, account2);
}

concurrent_execute(() => serialized_exchange(a1, a2), () => serialized_exchange(a1, a3));

교착(deadlock)

그런데 위의 방법으로 여러 개의 공유자원에 대한 동시성 문제를 다룰 때 발생할 수 있는 문제가 있다.

a1, a2를 공유자원으로써 사용하는 두 스레드 T1, T2가 있다고 가정해 보자.

 

T1 : a1에 접근 후 a2에 접근

T2 : a2에 접근 후 a1에 접근

 

만일 T1이 a1에 접근한 상태로 T2가 a2에 접근했다면, 두 스레드는 서로의 종료를 영원히 기다리게 된다.

 

이렇게 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태 상황을 교착(deadlock)이라고 부른다.

그리고 여러 스레드가 여러 개의 공유 자원에 접근할 수 있는 시스템에서는 항상 이런 교착의 위험이 있다.

여기서 교착을 회피하기 위해 사용할 수 있는 한 가지 방법으로는 각 공유자원에 고유식별번호를 부여한 뒤 일관된 접근 우선순위를 정하는 것이다.

직렬화기 구현 by 뮤텍스(mutex)

직렬화기는 뮤텍스(mutex)라는 객체를 이용하여 구현한다.

뮤텍스는 획득(aquire), 해제(release) 두 가지 연산을 지원하며, true / false로 구분되는 상태를 가진다.

function make_serializer() {
    const mutex = make_mutex();
    return f => {
               function serialized_f() {
                   mutex("acquire");
                   const val = f();
                   mutex("release");
                   return val;
               }
               return serialized_f;          
           };
}

 

위의 코드를 살펴보면, 직렬화기는 mutex라는 내부 변수를 가지며
함수 f를 매개변수로 받아 뮤텍스를 얻은(acquire) 후 함수 f를 실행하고, 다시 뮤텍스를 반환(release)하는 함수를 리턴하여 직렬화를 달성한다.

뮤텍스의 연산

• 획득(acquire) : 뮤텍스를 획득한다.
• 해제(release) : 뮤텍스를 반납한다.

뮤텍스의 상태

뮤텍스의 상태(아래 예시에서는 cell) 값은 뮤텍스의 점유상태를 나타낸다.

• true : 현재 공유자원을 사용 중인 스레드가 존재하여 뮤텍스 획득 불가능한 상태.
• false : 현재 공유자원을 사용중인 스레드가 없어 뮤텍스 획득 가능한 상태.

function make_mutex() {
    const cell = list(false);
    function the_mutex(m) {
        return m === "acquire"
               ? test_and_set(cell)
                 ? the_mutex("acquire") // 뮤텍스를 얻을 수 있을 때까지 retry
                 : true
               : m === "release"
               ? clear(cell)
               : error(m, "unknown request -- mutex");
    }
    return the_mutex;
}

function clear(cell) {
    set_head(cell, false);
}

function test_and_set(cell) {
    if (head(cell)) {
        return true;
    } else {
        set_head(cell, true);
        return false;
    }
}

test_and_set(TAS)

acquire 연산 시 test_and_set 함수를 실행한다. 이 함수는 뮤텍스의 상태에 따라 동작이 다르다.

• 뮤텍스의 상태가 true일 때 : true를 반환한다.
• 뮤텍스의 상태가 false일 때 : 뮤택스를 true로 설정한 후 false를 반환한다.

여기서 주의할 점은 test_and_set은 원자성을 가져야 한다는 것이다.
원자성이란 더 작은 단위로 쪼갤 수 없다는 뜻으로, 여기서는 실행단위가 여러단계로 나눠지지 않고 한 번의 명령줄로 실행된다는 것을 의미한다.
위의 JavaScript코드에서의 test_and_set 원자성을 가지지 않는다. 조건문 - 변수 접근 - 할당 등... 여러 단계를 거쳐 실행될 것인데, 이런 상황에서는 멀티스레드 환경에서 각 스레드의 실행순서가 보장되지 않는 문제로 인해 또 똑같은 동시성 문제가 발생할 수 있다.

 

따라서, 운영체제가 test_and_set(TAS)을 안전하게 수행하기 위해서는 하드웨어 차원에서 원자성을 보장하는 test_and_set 명령어를 지원해야 한다.