[운영체제] 은행 계좌 문제 (세마포어)

세마포어를 사용해 임계구역 문제를 상호 배타 방식으로 해결하고, 프로세스 실행 순서를 제어한다. 

 

---

1. Critical Section 임계 구역 문제 

1) 임계 구역 문제란?

임계 구역 : 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역으로 중요한 부분이다. 

 

2) 예제

아래는 부모님(Parent)은 입금, 자녀(Child)는 출금하는 예제이다.

Thread를 상속받아 Parent와 Child 클래스를 만들어 BankAccount에 입금입, 출금을 100번씩 실행한다.

(입금 deposit,  출금 withdraw는 독립적으로 일어난다.)

입, 출금을 같은 횟수를 실행했으니 결과는 0이 나와야한다. 

public class Main {

	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();
        	// wait until thread is finished
		p.join(); 
		c.join();
		System.out.println("\nBalance = " + b.getBalance());
	}

}

class BankAccount {
	int balance;
	void deposit(int amount) {
    		//temp : time delay
		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;
	}
}

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);
		}
	}
}

Output:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------------------------------------------------------------------------------------
 Balance : -100000

3) 문제점

입금, 출금 각각 100번씩 실행했는데 잔액이 0원이 아니라 -100000원이 나온다.

(실행할 때마다 0으로 맞게 나올 때도 있지만, -69000, -99000 등 잘못된 값이 나오기도 한다)

공통 변수 balace에 두 쓰레드가 동시에 업데이트했기 때문이다.

 

4) 해결 방법 : Mutual Exclusion 상호 배타

세마포어를 사용해 공통변수 balace에 한 쓰레드만 업데이트하도록 한다. 

import java.util.concurrent.Semaphore;

public class Main {
    /* 생략. 위와 동일*/
}


class BankAccount {
    int balance;
    Semaphore sem;

    BankAccount() {
        // Semaphore(n): allow n simultaneous access as many threads
        sem = new Semaphore(1);
    }

    void deposit(int amount) {
        try {
            // add thread to semaphore queue
            sem.acquire();
        } catch (InterruptedException e) {}
        int temp = balance + amount;
        System.out.print("+");
        balance = temp;
        // remove from semaphore queue
        sem.release();
    }
    void withdraw(int amount) {
        try {
            sem.acquire();
        } catch (InterruptedException e) {}
        int temp = balance - amount;
        System.out.print("-");
        balance = temp;
        sem.release();
    }
    int getBalance() {
        return balance;
    }
}



class Parent extends Thread {
    /* 생략. 위와 동일*/
}

class Child extends Thread {
    /* 생략. 위와 동일*/
}

Output:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------------------------------------------------------------------------------------
 Balance : 0

여러번 실행해도 정상 값 0 이 출력된다.

 

 

---

2. Ordering : 프로세스 실행 순서 제어

1) 항상 입금(+) 먼저

sem2를 사용해 withdraw가 먼저 실행되면 세마포어 큐에 잡아놓고, deposit이 실행된후 withdraw를 깨운다.

반대로 하려면 sem2위치를 바꾸면 된다.

class BankAccount {
	int balance;
	Semaphore sem, sem2;
	
	BankAccount() {
		sem = new Semaphore(1);
		sem2 = new Semaphore(0);
	}
	
	void deposit(int amount) {
		try {
			sem.acquire(); 
		} catch (InterruptedException e) {}
		int temp = balance + amount;
		System.out.print("+");
		balance = temp;
		sem.release();
		sem2.release();
	}
	void withdraw(int amount) {
		try {
			sem2.acquire();
			sem.acquire();
		} catch (InterruptedException e) {}
		int temp = balance - amount;
		System.out.print("-");
		balance = temp;
		sem.release();
	}
	int getBalance() {
		return balance;
	}	
}

Output:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------------------------------------------------------------------------------------
 Balance : 0

 

2) 번갈아가면서

세마포어 dsem, wsem 를 사용해 번갈아가며 실행되도록한다. 

deposit 에서는 입금 후 wsem을 release하고, dsem을 acquire해서 deposit 후에 withdraw가 실행되도록 한다.

withdraw에서는 반대로 wsem을 aquire하고, 출금 후, dsem을 release해서 withdraw후에 deposit이 실행되도록 한다. 

class BankAccount {
	int balance;
	Semaphore sem, dsem, wsem;
	
	BankAccount() {
		sem = new Semaphore(1);
		dsem = new Semaphore(0);
		wsem = new Semaphore(0);
	}
	
	void deposit(int amount) {
		try {
			sem.acquire(); 
		
		int temp = balance + amount;
		System.out.print("+");
		balance = temp;
		sem.release(); 
		
		wsem.release();
		dsem.acquire();
		} catch (InterruptedException e) {}
	}
	void withdraw(int amount) {
		try {
			wsem.acquire();
			
			sem.acquire();
		} catch (InterruptedException e) {}
		int temp = balance - amount;
		System.out.print("-");
		balance = temp;
		sem.release();
		
		dsem.release();
	}
	int getBalance() {
		return balance;
	}
}

Output:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
 Balance : 0