[7] 프로세스 동기화

KOCW - 양희재 교수님 강의를 기반으로 운영체제 정리

프로세스라는 것은 일반적으로 Independent와 Cooperating으로 나눌 수 있습니다.

• Independent process : 프로세스들 끼리 서로 영향을 주지 않는 경우

• Cooperating process : 프로세스들 끼리 영향을 주는 경우 (영향을 주든지, 영향을 받든지)

프로세스간 통신을 하거나 프로세스간 자원을 공유하는 상황이 빈번하기 때문에 일반적으로 프로세스는 Cooperating인 경우가 훨씬 많습니다. Cooperationg 같은 환경에서는 자원에 접근하거나 통신을 하는 상황에서 발생할 수 있는 문제들을 막기 위해 프로세스(쓰레드) 동기화는 매우 중요합니다.

Process(Thread) synchronization

• Concurrent access to shared data may result in data inconsistency

• Orderly execution of cooperating processes so that data consistency is maintained

위의 문장처럼 공유 자원에 동시에 접근하는 경우 데이터의 일관성이 유지되지 못하기 때문에 cooperating process를 특정 순서로 실행하여 일관성을 유지하도록 하는게 동기화입니다.

대표적인 문제로 BankAccount Problem이 있습니다.

class Test {
	public static void main(String[] args) throws InterruptedException {
    
    BankAccount b = new BankAccout();
    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;
    
    Parent(BankAccount b) {
    	this.b = b;
    }
    
    public void run() {
    	for (int i=0; i < 100; i++)
        	b.withdraw(1000);
    }
	
}

위의 코드는 부모와 자식 쓰레드가 하나의 계좌에 접근하여 입금과 출금을 반복하는 상황입니다. 위의 쓰레드가 종료되고 계좌의 잔액은 0으로 나옵니다. 상황을 조금 더 현실 상황에 맞게 바꿔 보겠습니다. 입금과 출금이 이루어질때 시간 지연이 일어나는 상황을 구현하면 아래와 같습니다.

class BankAccount {
	int balance;
    void deposit(int amount) {
    	// 시간 지연을 위한 temp와 print 추가
    	temp = balance + amount;
        System.out.println("+")
    	balance = temp;
    }
    
    void withdraw(int amount) {
   		temp = balance - amount;
        System.out.println("-")
    	balance = temp;
    }
    
    int getBalance() {
    	return balance
    }
	
}

위와 같이 시간 지연이 추가된 코드로 결과를 확인하면 계좌의 잔액은 0이 아니게 됩니다. 시간 지연이 추가 되지 않은 한줄의 코드도 어셈블리어로 변환하면 여러개의 명령어를 수행해야하기 때문에 시간 지연이 없는 코드더라도 무한대로 돌려보면 이런 오류가 날 수 있습니다.

이런 오류가 나는 이유는 공통 변수(common variable)에 대한 동시 업데이트 때문입니다. 이 문제를 해결 하기 위해 한번에 하나의 쓰레드만 업데이트(Atomic) 하도록 해야합니다.

임계구역(Critical Section) 문제

다중 쓰레드로 이루어진 시스템에서 각각의 쓰레드가 가지고 있는 코드에서 공통 변수(파일, 데이터베이스, 변수 등)를 변경하려는 부분을 임계구역이라고 합니다.

이 문제를 해결하기 위해 3가지 조건이 만족해야 합니다.

• Mutual exclusion(상호배타) : 임계구역에 오직 하나의 쓰레드만 진입

• Progress(진행) : 임계구역에 접근하는 쓰레드를 결정하는 것은 유한 시간 이내에 이루어져야함

• Bounded waiting(유한대기) : 어느 쓰레드라도 유한 시간 내에 해당 임계구역으로 진입해야함

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

• 임계구역 문제 해결

• 프로세스 실행 순서를 원하는대로 제어

• Busy wait같은 비효율성 제거

동기화 도구

세마포어(Semaphores)

세마포어는 동기화 문제 해결을 위한 스프트웨어 도구입니다. 세마포어의 구조는 정수형 변수와 두 개의 P(Proberen, acquire) 동작과 V(Verhogen, release) 동작으로 이루어져 있습니다.

P 동작

void acquire() {
	value --;
    if (value < 0) {
    	add this process/thread to list;
        block;
    }
}

정수값이 1 감소하고 이 값이 0보다 작은 경우 acquire를 호출한 프로세스나 쓰레드를 queue(list)에 추가합니다. 그 후 block을 걸어 누군가가 꺼내지 않는 이상 아무것도 하지 못하는 상황이 됩니다.

V 동작

void release() {
	value ++;
    if (value <= 0) {
    	remove a process P from list;
        wakeup P;
    }
}

정수값을 1 증가하고 이 값이 0보다 작거나 같다면 어떤 프로세스나 쓰레드가 queue안에 있다는 뜻입니다. 이때 queue로 부터 프로세스/쓰레드를 빼내고 wakeup시켜줍니다.

세마포어에 의해 queue로 들어간 프로세스/쓰레드는 release될 때까지 ready queue로 들어가지 못하게 됩니다.

세마포어의 Mutual exclustion

초기 value를 1로 설정한 경우에 acquire 동작을 실행한 프로세스/쓰레드는 임계구역으로 접근하게 됩니다. 이 프로세스/쓰레드가 끝나기 전에 다른 프로세스/쓰레드가 acquire 동작을 실행하면 queue에 block되고 이전 프로세스/쓰레드가 끝나면 release를 실행하면 임계구역으로 접근할 수 있도록 합니다. 여기서 알 수 있듯이 value는 임계구역에 접근할 수 있는 프로세스/쓰레드의 개수를 의미합니다.

세마포어의 Ordering

세마포어는 프로세스의 순서를 원하는대로 제어하는 Ordering을 할 수 있습니다.
두 개의 프로세스/쓰레드가 있을때 무조건 P1이 먼저 실행되게끔 설정하려면 위의 사진과 같이 설정할 수 있습니다.

세마포어의 value를 0으로 설정하여 어떤 프로세스도 임계구역에 입장할 수 없게 설정합니다.

• P1이 먼저 실행되는 경우

이 경우는 acquire 동작을 하지 않기 때문에 우리가 원하는대로 P1이 먼저 임계구역에 접근할 수 있습니다. 이 프로세스가 동작하고 있는 중 P2가 실행된다면 acquire 동작으로 인해 임계구역에 접근할 수 없고 세마포어의 queue로 들어가게 됩니다. 결과적으로 P1의 프로세스/쓰레드가 완료되고 release 동작을 통해 value를 증가시켜 P2를 세마포어 queue에서 빼내어 ready queue로 이동시킬 수 있습니다.

• P2가 먼저 실행되는 경우

P2가 먼저 실행이 되면 acquire 동작으로 인해 세마포어 queue에 block이 되고 P1은 임계구역으로 접근할 수 있습니다.

import java.util.concurrent.Semaphore;

class BankAccount {
	int balance;
    
    Semaphore sem, sem2;
    
    BankAccount() {
    	// 상호배타 목적
    	sem = new Semaphore(1);
        // Ordering 목적
        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
    }
	
}

• P1과 P2가 교대로 나오게 하려면?

세마포어를 2개(출금 세마포어, 입금 세마포어) 사용하여 제어할 수 있다.

import java.util.concurrent.Semaphore;

class BankAccount {
	int balance;
    
    Semaphore sem, wsem, dsem;
    
    BankAccount() {
    	// 상호배타 목적
    	sem = new Semaphore(1);
        // Ordering 목적
        wsem = new Semaphore(0);
        dsem = new Semaphore(0);
    }
    
    void deposit(int amount) {
    	try {
        	sem.acquire();
        } catch (InterruptedException e) {}
        int temp = balance + amount;
        System.out.print("+");
    	balance = temp;
        sem.release();
        // 입금을 위한 acquire
        dsem.acquire();
        // 출금을 위한 release
        wsem.release();
    }
    
    void withdraw(int amount) {
    	try {
        	sem.acquire();
            wsem.acquire();
        } catch (InterruptedException e) {}
        int temp = balance - amount;
        System.out.print("-");
    	balance = temp;
        sem.release()
        // 입금을 위한 release()
        dsem.release();
    }
    
    int getBalance() {
    	return balance
    }
	
}