Synchronization Tools[2]

이번 글에서는 저번에 다뤘던 synchronization tools[1] 에 이어서 Mutex Locks, Semaphore 등의 critical section solution에 대해서 다룰 예정이다.

Mutex Locks

mutex lock은 critical sectoin을 해결하는 가장 간단한 방법이다. boolean 변수인 lock을 이용해서 critical section을 잠그고 풀 수 있다.

mutex lock 에서는 두 가지의 함수가 존재한다. 바로 acquire()와 release()이다.

• acquire()

  acquire()는 lock을 걸어 잠그는 함수로서, 프로세스가 critical section에 진입할 때, acquire()를 호출해 lock을 잠그게 된다.

• release()

  release()는 acquire()와 반대의 동작을 수행하는 함수로서, lock을 푸는 동작을 수행하게 되는데, 프로세스가 critical section에서 작업을 마치고 나갈 때, exit section에서 호출하게 된다.
  따라서 acquire()와 release()는 반드시 atomic 하게 수행되어야만 한다. interrupt가 발생할 수 없다는 뜻이다.

• Busy Waiting

  하지만 mutex lock은 필연적으로 busy waiting이라는 동작을 할 수 밖에 없다. busy waiting을 그대로 직역하면 "바쁜 대기"인데, 이는 OS에서 원하는 자원을 얻을 때까지 기다리는 것이 아니라, 권한을 얻기 위해 대기함을 의미한다. 즉, entry section에서 프로세스는 permission을 얻기 위해 계속해서 대기해야 한다는 것이다.

그림에서 볼 수 있듯이 acquire()에서는 while(!avaiable) 을 통해 avaiable이 false일 경우 true가 될 때까지 계속 체크하면서 대기해야 한다.

Semphore

semaphore는 mutex lock과는 다르게 semaphore라는 integer variable을 활용한다.

그림에서는 semaphore가 S로 정의되어 있다. S를 critical section에 진입하기 위한 일종의 자원이라고 생각하면 쉽다. critical section에 진입할 때는 자원을 하나 가져가고, critical section을 나갈 때 다 쓴 자원을 반납하는 것이다. 따라서 자원이 0보다 작다면 이미 하나의 프로세스가 critical section에 진입해 있는 것이므로 entry section에서 대기해야 한다.

• wait(S)

  mutex lock에서의 acquire()와 같은 동작을 수행한다. S의 값이 0보다 작다면 busy wait을 하게 되고, S 자원이 있을 때 하나의 자원을 가져가면서 critical section에 진입하게 된다.

• signal(S)

  critical section에서 작업을 마친 프로세스가 exit section에서 자원을 반납하고 나가는 동작을 수행한다.

semaphore를 정의하는 두 가지 방법

• Counting Semaphore

  위에서 설명한 것처럼 integer value를 통해 S를 설정하며, 이때 자원의 수는 제한이 없다. 즉 처음에 초기화 된 S의 값이 자원을 이용할 수 있는 프로세스의 숫자라고 생각하면 된다.

• Binary Semaphore

  S는 0 ~ 1의 값을 가질 수 있도록 초기화 되며, 이때는 자원의 숫자가 1개이기 때문에 동작 방식이 mutex lock과 같다고 볼 수 있다.

Incorrect use of semaphore operations :

• signal(mutex) ... wait(mutex)

• wait(mutex) ... wait(mutex)

• Omitting of wait(mutex) and/or signal(mutex)

semaphore를 사용하는 것은 전적으로 프로그래머의 몫이기 때문의 wait()와 signal()을 적절히 사용하여야 한다. 위에 제시된 예시처럼 signal()과 wait()의 순서가 바뀌거나 wait()을 두번 호출하는 경우, 혹은 어느 하나를 호출하지 않는 경우에는 문제가 발생할 수 있다.

Semaphore - Usage

	wait(mutex);
	/* critical section */
    signal(mutex);

	P1: S1;
    	signal(synch);
    
    P2: wait(synch);
    	S2;

두 번째 그림을 보면 semaphore를 통해 두 프로세스 간의 실행 순서를 결정할 때 사용할 수 있음을 알 수 있다. S2보다 S1이 먼저 실행되길 원할 경우 synch를 0으로 초기화하고 S2 전에 wait(synch)를 걸어주게 되면 S1이 작업을 마치고 signal(synch) 를 통해 자원을 할당하지 않으면 S2는 실행 될 수 없다. 따라서 S1은 어떤 경우에도 S2보다 먼저 실행될 수 있는 것이다.

Semaphore w/o Busy Waiting

	typedef struct { 
    	int value; 
        struct process *list; 
    } semaphore;

semaphore가 waiting queue를 가지게 함으로써 busy waiting을 해결할 수 있다. waiting queue에는 critical section에 진입하기 위해 기다리는 프로세스들이 할당된다.

두 개의 함수가 새롭게 추가되었다.

• block()

  더 이상 프로세스는 자원이 할당될 때까지 busy waiting을 하지 않는다. 자원이 있지 않다면, 프로세스는 block()을 호출해 waiting queue에 들어간다. 따라서 계속해서 자원의 값을 확인하지 않고 waiting queue에서 자신을 때울 때까지 대기하게 된다.

• wakeup()

  signal 함수에 정의된 wakeup()은 critical section에서 작업을 마치고 나온 프로세스가 다 쓴 자원을 반납하고, waiting queue에 있던 프로세스를 깨우는 동작을 실행한다. wakeup()이 호출되면 waiting queue에 있던 프로세스 중 하나가 깨어나 자원을 할당받고 critical section에 진입할 수 있는 permission을 얻게 된다.

New Critical Section Issue

wait()와 signal()은 자원의 값을 조절하고 waiting queue를 관리하는 능력을 얻었기 때문에, 두 개의 프로세스가 동시에 같은 semaphore를 가지고 접근해서는 안된다. 즉, wait()와 signal()이 새로운 critical section이 되어버린 것이다..!

따라서 이제는 wait()와 signal()을 다른 wait()와 signal()로 감싸줘야 하는 것이다.

	wait(sem_mutex)
    [wait(mutex)]
    signal(sem_mutex)
    
    // critical section
    
    wait(sem_mutex)
    [signal(mutex)]
    signal(sem_mutex)

wait(mutex)와 signal(mutex)를 한번 더 semaphore로 감싸서 자원이 두 개 이상의 프로세스들로부터 수정되는 것을 막았다.

busy waiting을 막기 위해 block()과 wakeup()을 추가한 거 아닌가??

wait(mutex)와 signal(mutex)은 굉장히 짧은 코드이고 critical section의 사용 시간과 빈도가 많지 않다면 wait(mutex)와 signal(mutex)을 감싸는 busy waiting 정도는 큰 문제가 없다.

하지만 critical section을 사용하는 시간이 많다면 이는 별로 좋은 솔루션이 될 수는 없다.

Monitor

monitor는 프로세스가 자원을 안전하게 공유할 수 있도록 도와주는 SW 구조체이다. monitor에서는 한번에 오직 하나의 하나의 프로세스만이 활동할 수 있다.

	monitor monitor-name
    {
    	// shared variable declarations
        procedure P1 (...) { ... }
        procedure P2 (...) { ... }
        procedure Pn(...) { ... }
        initialization code (...) { ... }
    }

P1 ... Pn은 모두 동기화되며, monitor 타입의 구조체를 선언함으로써 구현할 수 있다.

monitor 구조체 내부에서 동작하고 있는 것이 process 1이라면 그동안에는 나머지 process들은 진입하지 못하고 entry queue에서 대기해야 한다.

Condition Variables

condition variable은 shared data 사용에 있어서 프로세스들을 대기 상태로 전환하고 깨울 때 사용할 수 있다.

condition x,y;

두 개의 조건을 생성하고 하나의 프로세스가 x.wait()을 통해 대기 리스트로 들어갔다면 이 프로세스는 다른 프로세스의 x.signal()을 통해서 깨어날 수 있다.

x, y 조건에 따른 두 개의 리스트가 있으며 process 1이 x.wait()을 통해 잠들어 있다면, 다른 프로세스의 x.signal()을 통해서만 깨어날 수 있다. x, y는 독립적인 조건으로 분리되어 작용한다.

	F1: S1;
    	done = true;
        x.signal();
    
    F2: if (done == false)
    	x.wait();
        S2;

done 이라는 boolean 변수와 조건변수 x를 통해 S1과 S2에서 프로세스들의 대기 상태와 호출을 관리하는 코드이다.