공유 자원과 임계구역

공유 자원(shared resource)

공유 자원(shared resource)은 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다.공동으로 쓰기 때문에 프로세스들의 공유 자원 접근 순서를 정하여 예상치 못한 문제가 발생하지 않도록 해야 한다.

Race Condition

만약 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 경쟁조건(race condition)이 발생했다고 한다.

즉 자바로 말하면 하나의 객체를 두 개 이상의 쓰레드가 동시에 읽거나 쓰는 상황을 말한다. 예를들어 state++ 연산을 두 개 이상의 쓰레드에서 동시에 접근했다고 하자. 이 때 코어는 싱글코어이다. 그러면 멀티태스킹 방식으로 처리를 하게 되는데 어셈블리어로 state ++ 는 3가지 과정을 거친다.
1. 레지스터에 state 싣기
2. 레지스터 +1해주기
3. 레지스터를 state에 저장하기

만약 T1(Thread1)이 2번까지 하고 컨텍스트 스위칭이 일어나서 T2로 넘어갔다고 하자. 그리고 다시 T2도 2번까지 수행하고 T1으로 다시 컨텍스트 스위치잉이 일어나면 1번에서 3번이 끝나면 state는 1이된다. 그리고 다시 T2도 3번까지 수행하면 1이되기 때문에 원래 2가 되어야 하지만 state가 2번의 ++를 거쳤음에도 1이 되는 현상을 볼 수 있다.

멀티코어는 애초에 컨텍스트 스위칭이 둘이 동시에 발생하기 때문에 더 발생하기 쉽다.

이처럼 여러 프로세스/스레드가 동시에 같은 데이터를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황을 race condition라고 한다.

임계 구역

공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영억을 임계구역(critical section)라고 한다. 전역변수와 같은 것이 예시이다. 임계구역이라는 의미의 영어 단어(critical section)에서 critical은 (앞으로의 상황에 영양을 미친다는 점에서) 대단히 중요한 이라는 뜻으로, 프로세스 실행 상황에서 공유할 수 없는 자원이 이러한 자원이다. 임계구역에서는 프로세스들이 동시에 작업하면 안 된다. 어떤 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역 밖에서 기다려야 하며, 임계구역의 프로세스가 나와야 들어갈 수 있다.

임계구역 해결 조건

임계구역 문제를 해결하는 방법은 여러 가지가 있다. 특히 중요한 것은 상호 배제이다.

상호 배제(mutual exlusion)

뮤텍스(Mutex)라고도 불리며 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다. 이것이 지켜지지 않으면 임계구역을 설정한 의미가 없다. 두 요리사가 한 믹서에 각자 사용할 재료를 한 번에 넣고 갈면 안되는 것 처럼 임계구역 내에는 한 번에 하나의 프로세스만 있어야 한다.

한정 대기(bounded waiting)

어떤 프로세스가 무한 대기 (infinite postpone)하지 않아야 한다. 즉 특정 프로세스가 임계구역에 진입하지 못하면 안된다.

진행의 융통성 (progress flexibility)

한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다. 즉 비어있는 자원이 있으면 언제든 사용할 수 있어야 한다.

임계구역 해결 방법

가장 단순한 방법은 잠금(lock)을 이용하는 것이다. 예를 들어 임계구역이 화장실이라면 사용자는 문을 잠그고 사용한 후 나올 때 잠금을 해제한다. 그리고 기다리는 사람이 있다면 사용해도 좋다는 신호를 보낸다. 잠금 해제와 동시에 동기화 신호를 보내는 것이다.

상호 배제 문제

while(lock==true);
lock = true;
~~~
lock = false;

이렇게 상호 배제를 할 수 있다. 하지만 제대로 작동히지 않을 때가 있다. 만약 P1이 lock이 false여서 while문을 통과했다고 하자. 아래에 lock = true;를 진행하기 전에 CPU 시간을 다 써서 타임아웃이 일어나 문맥교환을 하게 된다면 lock은 그대로 false이다. 여기서 P2도 while문을 통과하게 되어 동시 진입 상황(상호 배제 조건을 충족하지 않음)이 일어난다.
또한 while문으로 busy wait를 하게 된다는 단점이 있다.
둘 다 임계구역으로 들어온다.

한정 대기 문제

위를 보안하여 작성한 코드가 있다.

lock1 = true;
while(lock2 == true);
lock1 = false;

lock2 = true;
while(lock1==true);
lock2=false;

만약 lock1이 true로 바뀌고 타임아웃 그리고, lock2도 true로 바뀌고 타임아웃되면 다시 무한루프에 빠지게 된다. 이는 한정 대기 조건을 보장하지 못하는 상황으로 교착 상태(deadlock)라고 한다.
임계구역으로 들어오면 안되는데 둘 다 들어와 버린다.

진행의 융통성 문제

임계구역 문제를 해결 하기 위한 세 번째 코드이다. lock 값이 1이면 프로세스 P1이 임계구역을 사용하고, lock 값이 2면 프로세스 P2가 임계구역을 사용한다.

int lock=1;
while(lock==2);
//임계
lock=2;

while(lock==1);
//임계
lock = 1;

공유 변수 lock의 값을 통해 다른 프로세스가 임계구역에 있는지 확인하고, 없으면 진입한다. 상호 배제는 하나의 공유 변수를 true,false로 해놓고 둘 다 true일 때 집입하도록 하였다.
하지만 이번엔 lock으로 임계구역으로 들어오는 조건이 다르다. 잠금을 확인하는 문장이 하나이므로 상호 배제와 한정 대기를 보장한다. 하지만 서로 번갈아가면서 실행해야 하는 문제가 있다. 한 프로세스가 두 번 연달아 임계구역에 진입하고 싶어도 그럴 수 없다.
이를 경직된 동기화 (lockstep synchronization)라고 한다.

피터슨 알고리즘

//공유변수
boolean lock1 = false;
boolean lock2 = false;
int turn = 1;

lock1 = true;
turn = 2;
while(lock2 == true && turn == 2)
//임계 구역
lock1 = false;

lock2 = true;
turn = 1;
while(lock1 == true && turn == 1);
lock2 = false;

게리 피터슨씨가 제안한 알고리즘이다.한정 대기 문제 코드와 유사한데 turn이라는 공유 변수를 더 사용한다.
프로세스 P1은 임계구역에 진입하기 전에 먼저 잠금을 한(lock1 = true;) 후 turn을 2로 설정한다. 변수 turn은 두 프로세스가 동시에 lock을 설정하여 임계구역에 못 들어가는 상화에 대비하기 위한 장치이다.
즉 두 프로세스가 동시에 lock을 설정했더라도 turn을 사용하여 다른 프로세스에 양보한다. 이어서 While(lock2 == true && turn == 2);문을 실행한다. 만약 프로세스 P2가 잠금을 설정하지 않았거나 잠금을 설정했더라도 곧바로 turn = 1 로 바꾸면 프로세스 P1은 임계구역에 진입하여 작업을 마친 후 잠금을 해제하고 임계구역을 빠져나온다. 프로세스 P2도 같은 방식으로 임계구역에 진입한다.

피터슨 알고리즘은 임계구역 해결의 세 가지 조건을 모두 만족하지만 2개의 프로세스만 사용 가능하다는 한계가 있다. 여러 공유변수가 있어야 가능하다.

데커 알고리즘

데커가 제안한 데커 알고리즘도 임계구역 해결의 세 가지 조건을 모두 만족하는 알고리즘이다. 하지만 피터슨 알고리즘 처럼 변수도 많고 매우 복잡하다.

뮤텍스

class Mutex {
	int value = 1;
    int guard = 0;
}

Mutex::lock() {
	while (test_and_set(&guard));
    if (value == 0) {
    	...현재 스레드를 큐에 넣음
        guard = 0; & go to sleep
    } else {
    	value = 0;
        guard = 0;
    }
}

Mutex::unlock() {
	while (test_and_set(&guard));
    if(큐에 하나이상 대기중) {
    	하나를 깨움
    } else {
    	value = 1;
    }
    guard = 0;
}

muext -> lock();
..critical section
mutex -> unlock();

위를 보면 먼저 guard를 통해 1차적으로 대기를 한 뒤 value를 통해 다시 검증을 한다. 또한 스핀락 방식과 달리 나중에 unlock이 발생했을때 큐에 대기중인 것을 깨우는 방식을 쓰기 때문에 락을 가질 수 있을 때 까지 휴식을 취하게 된다.

그렇다고 뮤텍스가 스핀락보다 항상 좋진 않고 멀티 코어 환경이고 ciritical section에서의 작업이 컨텍스트 스위칭보다 더 빨리 끝난다면 스핀락이 뮤텍스보다 더 이점을 가지게 된다. 멀티 코어 환경인 이유는 하나의 코어에서 다른 하나의 코어를 계속 확인하기 때문에 락을 해제하면 바로 시작할 수 있기 때문이다. 코어가 하나면 컨텍스트 스위칭이 일어나기 때문에 이점이 없다.

세마 포어

이러한 단점을 해결하기 위해 다익스트라는 세마포어(semaphore)라는 알고리즘을 제안했다. 세마포어는 앞의 알고리즘과 비교하면 간단하고 사용하기도 쉽다.

세마포어는 임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다.
이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 세마포어는 앞의 단점들인 잠겼는지 직접 점검, 바쁜 대기, 동기화 메세지 보내기 등을 할 필요가 없다.

Semaphore(n) -> n만큼 공유자원을 가지고 있다.

P(); -> if RS>0 then RS=RS-1; else block();
//임계구역
V() -> RS += 1,wake_up();

하지만 세마포어도 단점은 있다. 세마포어의 가장 큰 문제는 잘못된 사용으로 인해 임계구역이 보호받지 못한다는 것이다. 사용자가 고의로 세마포어를 사용하지 않거나 사용 중에 실수를 해서 문제가 생긴 경우이다.
1. 프로세스가 세마포어를 사용하지 않고 바로 임계구역에 들어간 경우는 당연히 보호 불가이다.
2. P()를 두 번 사용하여 wake_up신호가 발생하지 않은 경우 프로세스 간의 동기화가 이루어지지 않아 세마포어 큐에서 대기하고 있는 프로세스들이 무한 대기에 빠진다.
3. P()와 V()를 반대로 사용하여 상호 배제가 보장되지 않은 경우로 임계구역을 보호할 수 없다.

공유 자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P()와 V()를 사용할 필요 없이 자동으로 처리하면 된다. 이를 실제로 구현한것이 모니터(monitor)이다.
모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킨다.

모니터는 시스템 호출과 같은 개념이다. 보호할 자원을 임계구역으로 숨기고 임계구역에서 작업할 수 있는 인터페이스만 제공하여 자원을 보호한다.
작동원리는
1. 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
2. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.

increase(10), increase(5)와 같이 필요한 숫자를 넣어서 사용하면 된다. 모니터는 임계구역 보호와 동기화를 위해 내부적으로 상태 변수(condition variable)을 사용한다.

monitor shared_balance
{
    private:
        int balance = 10;
        boolean busy = false;
        condition mon;
    
    public:
        increase(int amount)
        {
            if(busy==true) mon.wait();
            busy = true;
            balance = balance + amount;
            mon.signal();
        }
}

위에서 10만 원이 들어 있는 예금 balance, 잠금 역할을 하는 busy, 잠금 해제 역할을 하는 mon 변수는 private로 선언되어 있다. 이 변수들은 public 영역에 있는 increase()를 통해서만 값을 변경할 수 있다. 다시 말해 입금하려는 프로세스 increase()만 사용하여 예금 데이터에 접근할 수 있다.
이 상황에서 프로세스 P1은 increase(10)을 , 프로세스 P2는 increase(5)를 사용하면 입금이 끝난다. increase는 임계구역이 잠겼는지(busy) 확인하고 다른 프로세스가 사용하지 않으면 잠금을 건 후 예금액을 증가시킨다.
모니터는 세마포어의 P()와 V()를 사용할 필요가 없다. 임계구역의 보호나 프로세스의 동기화가 모니터 내부에서 처리되므로 사용자는 increase()를 호출하기만 하면 된다.

모니터는 임계구역 보호화 동기화를 위해 내부적으로 상태 변수를 사용한다. 상태변수에는 wait()과 signal()기능이 있다.

-wait() : 모니터 큐에서 자신의 차례가 올 때까지 기다린다. 세마포어의 P()에 해당한다.
-signal() : 모니터 큐에서 기다리는 다음 프로세스에 순서를 넘겨준다. 세마포어의 V()에 해당한다.

불필요한 정보를 숨기고 공유 자원에 대한 인터페이스만 제공하는 모니터는 오늘날의 객체지향 언어와 매우 유사하다.

정리

뮤텍스는 priority inheritacne 속성을 가지며 세마포어는 이러한 속성이 없다. 따라서 상호 배제만 필요하다면 뮤텍스를, 작업 간의 순서 동기화가 필요하다면 세마포어를 사용하는 것이 좋다.