Bank Account Problem

2. Bank Account Problem(은행 계좌 문제)

동기화의 필요성을 가장 잘 느낄 수 있는 은행 계좌 문제에 대해 알아본다.

2.1 문제 설명

동기화 문제 중에서 대표적인 은행 계좌 문제를 살펴보자. 은행에는 하나의 계좌에 입금, 출금을 할 수 있다. 여기서 계좌는 공유하는 자원이고, 입금과 출금은 각각 프로세스라고 볼 수 있다. 부모님이 자식에게 입금을 하고, 자식은 출금을 하는 상황을 자바로 구현한 코드는 아래와 같다.

// 계좌
class BankAccount {
	int balance;
	void deposit(int amount) {
		balance = balance + amount;
	}
	void withdraw(int amount) {
		balance = balance - amount;
	}
	int getBalance() {
		return balance;
	}
}

입금, 출금, 잔액조회 함수를 멤버함수로 갖는 클래스를 구현한다.

// 입금 프로세스
class Parent extends Thread {
	BankAccount b;
  // 생성자는 공유하는 계좌를 초기값으로 가진다.
	Parent(BankAccount b) {
		this.b = b;
	}
	public void run() {   // run(): 쓰레드가 실제로 동작하는 부분(치환)
		for (int i = 0; i < 100; i++)
		  b.deposit(1000);
	}
}

멤버 변수로 계좌를 가지고, 이것을 생성할 때 인자로 받는 클래스이다. 해당 클래스에서 run()은 입금을 100번 수행한다.

// 출금 프로세스
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);
	}
}

멤버 변수로 계좌를 가지고, 이것을 생성할 때 인자로 받는 클래스이다. 해당 클래스에서 run()은 출금을 100번 수행한다.

// Test.java
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();   // start(): 쓰레드를 실행하는 메서드
		c.start();
		p.join();    // join(): 쓰레드가 끝나기를 기다리는 메서드
		c.join();
		System.out.println("balance = " + b.getBalance());
	}
}

main 함수에서는 위에서 만든 클래스들을 사용하여, 계좌를 공유하는 두 개의 쓰레드를 만든다. 그리고 부모, 자식 클래스에서 각각 입금과 출금을 100번씩 수행하고, 결과적으로 남은 잔액을 조회한다. 잔액은 0이 나와야 할 것이다.

// Result
balance = 0

이 결과는 정상적이다. 100번 1,000원을 입금하고, 100번 1,000원을 출금하면 잔액은 0원이 남는다. 위 코드는 2개의 쓰레드가 동작하고 있음에도 불구하고 동기화 문제가 발생할 확률은 매우 낮다. 반복이 100번 밖에 안 일어나는 매우 간단한 코드 이기 때문이다.

2.2 동기화 문제 발생

실제 상황에서는, 입금, 출금 명령을 내리고 이 명령이 전달되는데 까지 시간이 소요된다. 그런 상황을 만들기 위해 출금하는 과정에서 temp라는 필요없는 변수를 추가하고, +,-를 출력하고, 반복 횟수를 1000번으로 늘렸다.

// 계좌
class BankAccount {
	int balance;
	void deposit(int amount) {
		int temp = balance + amount;
		System.out.print("+");
		balance = temp;
	}
	void withdraw(int amount) {
		int temp = balance - amount;
		System.out.print("-");
		balance = temp;
	}
	int getBalance() {
		return balance;
	}
}

// Result
++++++++++++++++++++++++++++++++++----------------------------------------------
--------------------------------------------------------------------------++++++
+++----------------------------------------------+++++++++++++++++++++++++++++++
+----+++++++-+++++----+++-------------------------------------------------------
-+++++++-++++-+++++++++-------++++++++++++++++++++++++++++++++++++++++++++++++++
++++++---------------+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+-++++++++++++-------------------++++++++++++++++++++-++++++++++++++++++++++++++
++++++-+------------------------------------------------------------------------
-+++++++++++-+++++++----------------------------------------+-------+-----------
-+------+-----------------------------------------------------------------------
-+------------------------------------------------------------------------------
-+------------------------------------------------------------------------------
-------------------+-------+----------------------------------------------------
------------------------------+-------------------------------------------------
------------------------------------------------------+-------------------------
-+------------------------------------------------------------------------------
-++---------------------------------------++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
balance = 1000000

+는 입금을 한 경우, -는 출금을 한 경우이고, 주목할 점은 balance값이 0이 아닌 1000000이라는 알 수 없는 값이 출력되었다. 또한 여러번 실행할 경우 100000이라는 값이 고정되어 출력되는 것도 아니다. 결과가 불일치하며, 비일관적이다. (비일관적인 이유는 운영체제에서 쓰레드를 스위칭하는 패턴이 매번 다르기 때문이다.)

약간의 시간 지연을 준 것만으로도 여러 쓰레드가 하나의 공유 자원을 사용하는 프로그램은 망가지게 된다.

2.3 왜 발생할까?

이러한 문제가 발생하는 원인은 공통변수(common variable)에 대한 동시 업데이트(concurrent update) 때문이다.

위 예제에서 공통 변수는 계좌의 잔액이다. 이에 접근하는 프로세스의 코드를 보면 다음과 같다.

balance = balance + amount;   // 입금
balance = balance - amount;   // 출금

이는 자바 문법에서는 한 줄이라 문제가 없어 보이지만, 로우 레벨(어셈블리어)로 내려가면 여러 줄로 구현된다. 예를 들어, balance를 업데이트 하는 하이 레벨 코드 1줄이 로우 레벨에서 3줄로 구현된다고 하자.

1. 공유 변수인 현재 잔액을 복사한다.
2. 현재 잔액에서 명령을 수행한다.
3. 나온 결과를 가지고 잔액을 갱신한다.

그런데, parent가 수행하던 도중에 1000번을 다 수행하지 못한 상황에서 interrupt(이 경우에는 시간 지연을 걸었으므로 timer interrupt가 되겠다.)가 걸려 2번 라인에서 멈췄다고 생각해보자. parent가 1000원을 입금했지만, 업데이트가 되지 않아 여전히 현재 잔액은 0이다.

이번에는 child가 부모님이 용돈을 넣은 줄 알고 신나서 돈을 뽑는 상황을 생각해보자. 잔액을 확인했더니, 아직 0이다. 그래서 child는 마이너스 통장을 통해 돈은 인출하고 현재 잔액은 -1000이 된다.

따라서 이 경우, 입금과 인출이라는 행위는 프로세스 입장에서 원자성을 갖는 행위이므로 동기화가 필수적이다. 기억이 안난다면 Introduction을 보자.

Reference

• KOCW 양희재 교수님 - 운영체제
• 양희재 교수님 블로그(시험 기출 문제)
• codemcd 님의 정리글
• Operating System Concepts, 9th Edition - Abraham Silberschatz