1. 프로세스 동기화

현대 운영체제에서는 보통 스위칭이 스레드 단위로 일어나기 때문에 정확히는 Thread synchronization이라고 할 수 있다.

프로세스는 일반적으로 두 부류로 나눌 수 있는데 하나는 Independent 프로세스이다. 프로세스 간에 아무런 관계가 없다면 independent하다고 볼 수 있다. 반면 어떤 형태로든 두 프로세스가 영향을 주고 받는다면 Cooperating 프로세스이다.

대부분의 프로세스는 사실 협력 관계에 해당되는데, 예를 들어 명절 기차표 예약, 수강신청을 생각해 보면 여러 사용자가 같은 데이터에 접근을 해 서로 간에 영향을 준다.

이처럼 공유된 데이터에 동시 접근이 발생할 때, 데이터에는 inconsistency가 야기될 수 있는데, 이를 경쟁 상태(Race Condition)라고 한다. 프로세스 동기화는 협력 관계에 놓인 프로세스에 순서를 정해 실행하여, 데이터 consistency를 유지하는 것이다.

1.1. BankAccount Problem

부모님이 은행 계좌에 입금을 하고, 자녀는 출금하는 상황을 생각해 보자.
입금(deposit)과 출금(withdraw)은 독립적으로 일어난다.

class BankAccount {
    int balance;

    void deposit(int amount) {
        balance += amount;
    }

    void withdraw(int amount) {
        balance -= amount;
    }

    int getBalance() {
        return balance;
    }
}

class Parent extends Thread {
    BankAccount b;

    Parent(BankAccount b) {
        this.b = b;
    }

    public void run() {
        for (int i = 0; i < 100; i++) {
            b.deposit(1000);
        }
    }
}

class Child extends Thread {
    BankAccount b;

    Child(BankAccount b) {
        this.b = b;
    }

    public void run() {
        for (int i = 0; i < 100; i++) {
            b.withdraw(1000);
        }
    }
}

class Test {
    public static void main(String[] args) 
        throws InterruptedException {
        BankAccount b = new BankAccount();
        Parent p = new Parent(b);
        Child c = new Child(b);
        p.start();
        c.start();
        p.join();
        c.join();
        System.out.println("Balance = " + b.getBalance());
    }
}

위의 파일을 실행해 보면 balance는 0원으로 출력이 된다.

Balance = 0

여기에 시간 지연을 주면 어떻게 될까?

class BankAccount {
    int balance;

    void deposit(int amount) {
        int temp = balance + amount;
        System.out.println("+");
        balance = temp;
    }

    void withdraw(int amount) {
        int temp = balance - amount;
        System.out.println("-");
        balance = amount;
    }

    int getBalance() {
        return balance;
    }
}

deposit, withdraw 함수에 temp 변수를 따로 선언하여 balance 값을 업데이트 하도록 하고, “+”, “-”를 출력하도록 하여 입출금 동작에 시간 지연을 추가했다.

++--+++++++++++++++++++++++++-------------------------++++++++++-----++
-------+++++++-----------------++++++++--------------------------+-----
...
...Balance = 1000000

실행 결과는 실행할 때마다 다르다. 0원보다 많게 나올 때도 있고, 0원보다 적게 나올 때도 있다. 상식적으로는 똑같이 1000원을 100번 입금하고, 100번 출금했는데 왜 0원이 나오지 않을까?

우리는 balance라는 공통 변수를 이용하는데 이를 동시에 업데이트 하려고 해서 문제가 생긴 것이다. High level language로는 한 줄이지만 low level language로는 여러 줄인데, 공통 변수가 업데이트되는 도중에 스위칭이 일어난 것이다.

LDR r0, [balance]
LDR r1, [amount]
ADD r0, r0, r1
STR r0, [balance]

이를 해결하기 위해서는 위 네 개의 명령이 atomic하게, 즉 분해되지 않고 한 번에 처리되어야 한다. 만약 3번째의 ADD 명령어를 수행하다가 문맥 전환이 일어나서 balance의 값이 원래 값과 달라지면 위에서 설명한 상황처럼 데이터의 일관성이 깨지게 된다.

이처럼 둘 이상의 스레드가 동시에 접근해서는 안 되는 공유 자원(예제에서는 balance)을 접근하는 코드의 일부를 임계구역이라고 한다.

2. 임계구역 문제(The Critical-Section Problem)

의미 그대로는 이 구간에서 무언가 치명적인(critical) 오류가 일어날 수 있다는 의미이다.

여러 개의 스레드로 이루어진 시스템에서, 각각의 스레드는 어떤 코드의 영역을 가지고 있는데 이를 critical section이라고 한다. 이 안에서 여러 스레드들은 공통 변수, 테이블, 파일을 수정한다.
1.1의 예시에서는 balance라는 공통 변수를 업데이트하는 부분을 임계구역이라고 한다.

우리가 만들어야 하는 임계구역 문제의 해결은 아래 세 가지가 전부 만족되어야 한다.

• Mutual exclusion(상호배타): 공통 변수에 대한 업데이트는 상호배타적이어야 한다.
  • e.g. Parent가 critical section 안에 들어가면, 즉 balance라는 공통 변수를 업데이트하면 Child는 이를 업데이트해서는 안 된다. 그 반대도 마찬가지다.
• Progress(진행): 임계구역에 어떤 스레드가 먼저 들어갈 것인지 결정하는 것은 유한 시간 내에 결정되어야 한다.
• Bounded waiting(유한대기): 어느 스레드라도 기다리고 다른 스레드가 기다리고 있다면 그 스레드는 유한 시간 내에 임계구역에 들어갈 수 있다.

Reference

• KOCW 양희재 운영체제