프로세스 동기화 (Process Synchronization)

Cooperating Process 즉, 서로 협력하고 있는 프로세스 간의 동기화를 의미한다.

현대 운영체제에서는 쓰레드 동기화 (Thread Synchronization) 방식을 대부분 사용한다.

Cooperating Process

Independant Processes

다른 프로세스와 분리되어있는 독립적인 프로세스

Cooperting Processes

다른 프로세스에게 영향을 미치거나 영향을 받는 프로세스

프로세스는 보통 전자우편이나 파일 전송 등을 통해 서로 통신하며 메모리 상의 자료들, 데이터베이스 등의 자원을 공유한다.

대표적인 예시로는 명절 기차표 예약, 대학 온라인 수강신청, 실시간 주식 거래 등이 있다.

Process Synchronization

현대 운영체제들은 대부분 Cooperating Processes 들로 이루어져 있기 때문에 이 프로세스들 간의 데이터 동기화 (Synchronization)가 무척 중요하다.

많은 사람들이 명절 기차표를 예약한다고 하자.
한 사람이 이미 A2 좌석을 예약했는데 기차표 시스템에 반영이 되지 않는다면? ( = 동기화가 이루어지지 않는다면?)
다른 사람이 A2 좌석을 또 예약하게 되는 불상사가 발생할 수 있다.

이처럼 프로세스 동기화의 주요 목적은 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것이다. 여러 프로세스가 동시에 하나의 공유된 자원에 접근하려고 할 때 이 프로세스들의 순서를 정하여 데이터의 일관성을 유지해야 한다.

은행 계좌 문제 (BankAccount Problem)

하나의 은행 계좌가 있고 부모님은 이 계좌에 입금을, 자녀는 출금을 하려고 한다. 이때 입금(Deposit)과 출금(Withdraw)은 서로 독립적으로 일어난다.

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

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

1000원을 100번 입금하고 다시 1000원을 100번 출금하므로 결과값으로 balance = 0이 출력된다.

매우 간단한 과정이므로 2개의 쓰레드가 동작하고 있지만 동기화 오류가 발생하지 않는다.

여기서 입금 과정에서 "+"를 출력하고 출금 과정에서 "-"를 출력해서 시간을 지연시켜 보도록 하자. 또한 입출금 횟수를 100회에서 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;
	}
}

그리고나서 결과값을 살펴보면

++++++++++++++++++++++++++++++++++----------------------------------------------
--------------------------------------------------------------------------++++++
+++----------------------------------------------+++++++++++++++++++++++++++++++
+----+++++++-+++++----+++-------------------------------------------------------
-+++++++-++++-+++++++++-------++++++++++++++++++++++++++++++++++++++++++++++++++
++++++---------------+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+-++++++++++++-------------------++++++++++++++++++++-++++++++++++++++++++++++++
++++++-+------------------------------------------------------------------------
-+++++++++++-+++++++----------------------------------------+-------+-----------
-+------+-----------------------------------------------------------------------
-+------------------------------------------------------------------------------
-+------------------------------------------------------------------------------
-------------------+-------+----------------------------------------------------
------------------------------+-------------------------------------------------
------------------------------------------------------+-------------------------
-+------------------------------------------------------------------------------
-++---------------------------------------++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

balance = 1000000

이와 같이 balance = 1000000로 잘못된 결과값이 출력된다.

이렇게 동작이 복잡해지고 시간 지연이 발생하면 곧바로 동기화 오류가 발생한다.

원인은 바로 서로 다른 쓰레드가 balance라는 공통 변수에 접근함으로써 동기화 오류가 발생하는 것이다. 이를 공통 변수 (Common Variable)에 대한 동시 업데이트 (Concurrent Update) 라고 한다.

이러한 오류는 한번에 하나의 쓰레드만 업데이트하도록 설정하는 임계구역 문제를 통해 해결할 수 있다.

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

임계구역 (Critical Section)

각각의 쓰레드들은 공통 변수를 변경하거나 테이블을 업데이트 하거나 파일을 작성하는 등의 작업을 담당하는 임계구역 (Critical Section)이라는 코드 뭉치를 갖고 있으며, 이로 인해 임계 구역 문제 (The Critical-Section Problem)가 발생할 수 있다.

임계 구역 문제를 해결하기 위해서는 다음의 조건을 만족해야 한다.

• 상호 배타 (Mutual Exclusion) : 한 쓰레드가 임계 구역에서 작업 중이라면 다른 쓰레드들은 절대로 이 구역에 접근할 수 없다.
• 진행 (Progress) : 어떠한 임계 구역에 접근할 지 여부는 반드시 유한 시간 내에 결정되어야 한다.
• 유한대기 (Bounded Waiting) : 어떠한 임계 구역에 접근하기 위해 대기하는 모든 쓰레드들은 유한 시간 내에 해당 구역으로 접근할 수 있어야한다.

프로세스/쓰레드 동기화 목적

프로세스 또는 쓰레드의 동기화는 다음과 같은 목적을 갖고 있다.

• 잘못된 결과값이 나오지 않도록 임계 구역 문제 해결 (3가지 조건 필수 만족)
• 프로세스의 실행 순서를 원하는대로 제어
• 효율적인 작업 실행

동기화 도구 (Synchronization Tools)

프로세스/쓰레드를 동기화하는 도구는 세마포 (Semaphores), 모니터 (Monitors) 등이 있다.

세마포 (Semaphores)

Semaphores
n. (철도의) 까치발 신호기, 시그널; U (군대의) 수기(手旗) 신호

세마포란 동기화 문제를 해결하기 위한 대표적인 소프트웨어 도구이다. 다익스트라 알고리즘으로 유명한 네덜란드의 Edsger Dijkstra가 제안했다.

세마포는 정수형 변수와 두 개의 동작 (P, V)로 이루어져있다.

Edsger Dijkstra는 네덜란드 사람이기 때문에 용어가 네덜란드어로 되어있다.

P : Problem (Test)을 의미하며 acquire()로 동작한다.
V : Verhogen (Increment)을 의미하며 release()로 동작한다.

세마포의 구조를 코드로 나타내면 다음과 같다.

class Semaphore {
  int value;	// number of permits
  Semaphore(int value) {
    ...
  }
  void acquire() {
    value--;
    if (value < 0) {
      // add this process/thread to list
      // block
    }
  }
  void release() {
    value++;
    if (value <= 0) {
      // remove a process P from list;
      // wakeup P;
    }
  }
}

acquire()은 value 값을 감소시키며 만약 value가 0 미만이 된다면 해당 임계 구역에는 이미 다른 프로세스가 들어와있다는 것으로 판단해서 다른 프로세스의 접근을 막는다. 들어오지 못한 다른 프로세스들은 list라는 이름의 Queue에 차례로 들어가서 순서를 기다린다.

release()는 value 값을 증가시키며 만약 value가 0 이하가 된다면 해당 임계 구역에 진입하기를 기다리는 프로세스가 남아있다는 것으로 판단해서 그 중 하나를 꺼내어 임계 구역에 진입시켜준다.

acquire()는 자원이 사용가능한지 확인하고, 가능하다면 프로세스/쓰레드를 진입시키고 그렇지 않다면 대기시킨다. release()는 작업이 끝난 프로세스/쓰레드를 임계 구역에서 내보내고, 다음 프로세스/쓰레드를 진입시킨다.

세마포의 사용 목적은 다음과 같다.

• 상호 배제 (Mutual Exclusion) : 여러개의 프로세스/쓰레드가 하나의 공유 자원에 동시에 접근하는 것을 막기 위해 사용.
• Ordering : 프로세스/쓰레드의 실행 순서 결정.

상호 배제 (Mutual Exclusion)

import java.util.concurrent.Semaphore;

class BankAccount {
	int balance;

	Semaphore sem;
	BankAccount() {
		sem = new Semaphore(1);
	}

	void deposit(int amount) {
		try {
			sem.acquire();
		} catch (InterruptedException e) {}

		int temp = balance + amount;
		System.out.print("+");
		balance = temp;

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

deposit(), withdraw() 과정에 세마포를 추가하여, acquire가 성공할 때만 동작하도록 설정했다. (상호 배제)

결과값은 balance = 0 으로 정상 출력된다.

Ordering

만약 2개의 프로세스 P1, P2가 있고 P1=>P2 순서로 실행시키려고 한다면 다음과 같이 할 수 있다.

세마포의 값을 0으로 초기화하고

P1	P2
	sem.acquire()
S1	S2
sem.release()

와 같이 설정한다.

1. P1이 먼저 실행된 경우

• S1이 실행된다.
• sem.release()가 실행되어 value값이 1 증가되고 (value = 1), 세마포 큐 안에 대기 중인 프로세스를 실행시킨다. (지금의 경우 대기 중인 프로세스가 없으므로 바로 종료된다.)
• P2가 실행된다.
• P2의 sem.acquire()가 실행되고 현재 value값은 1이므로 이를 1감소시켜서 0이 된다. value = 0이라서 block 되지 않으므로, 무사히 S2가 실행된다.

2. P2가 먼저 실행된 경우

• S2가 실행되기 전에 sem.acquire() 가 먼저 실행된다. 그런데 현재 value값은 0이고 이를 1 감소 시키면 -1 이 된다. 따라서 해당 P2는 block되고 세마포 큐에 삽입되어 순서를 기다린다.
• P1이 실행되고 S1이 실행된다.
• sem.release()가 실행되어 value값이 1 증가되고 (value = 0), 세마포 큐에 있는 P2 프로세스가 진입한다.
• P2의 S2가 수행된다.

결과적으로 P1, P2 둘 중 어느 것을 먼저 실행하여도 결과적으로 P1 -> P2 순서로 수행된다.

class BankAccount {
	int balance;

	Semaphore sem, semOrder;
	BankAccount() {
		sem = new Semaphore(1);
		semOrder = new Semaphore(0);
	}

	void deposit(int amount) {
		try {
			sem.acquire();
		} catch (InterruptedException e) {}
		int temp = balance + amount;
		System.out.print("+");
		balance = temp;
		sem.release();
		semOrder.release();
	}
    
	void withdraw(int amount) {
		try {
			semOrder.acquire();
			sem.acquire();
		} catch (InterruptedException e) {}
		int temp = balance - amount;
		System.out.print("-");
		balance = temp;
		sem.release();
	}
    
	int getBalance() {
		return balance;
	}
}

semOrder 변수를 선언하여 Ordering 작업을 담당하도록 한다.

계좌가 비어있는데 출금을 할 수는 없으므로 무조건 입금 => 출금 순으로 동작해야한다.

따라서 deposit() 마지막에서 semOrder의 release()가 실행되고, withdraw() 실행 전에 semOrder의 acquire()가 실행된다.

만일 입금 전에 출금이 먼저 실행되려한다면 Ordering에 의해 block된다.