[OS] 5. Synchronization(동기화)

Synchronization

Synchronization은 여러 작업이나 프로세스가 존재하는 경우 수행 시점을 조절하여 예상하지 못한 결과가 일어나는 현상을 방지하는 것을 말한다.

 

한 번에 하나의 process, 하나의 thread만이 존재한다면 synchronization은 필요가 없을 것이다.

 

하지만 우리가 컴퓨터로 작업을 하는데 단 하나의 process,  thread만 사용할 수 있다면?

 

웹 서핑을 하다가 문서 작업을 하고 싶으면 인터넷을 닫아야하는 등의 매우 불편한 상황들이 연출 될 것이다.

 

따라서 필연적으로 multi-thread를 도입할 수 밖에 없고, 이와 관련하여 발생하는 문제들을 해결하는 테크닉이 `synchronization` 인 것이다.

 

 

Race Condition

우리가 multi thread 환경에서 synchronization을 고려해야 하는 이유가 바로 `Race Condition`이다.

 

Race Condition이란 여러 thread들이 공유하는 데이터가 존재할 때, 접근하는 순서에 따라 예상하지 못한 결과가 발생하는 문제를 말한다. 

말 그대로, 공유 자원을 두고 thread들이 서로 경쟁하는 상황을 의미하는 것이다.

 

예를 들어, `Thread A` 와 `Thread B` 가 존재한다고 가정하자.

이들은 공유 자원 X를 가지고 있으며, 공유자원 X의 값은 10이다.

 

`Thread A`는 공유 자원 X를 두배로 만드는 작업을 진행하고,

`Thread B`는 공유 자원 X를 절반으로 만드는 작업을 수행한다고 가정하자.

 

이 경우, 다음과 같은 상황이 발생할 수 있다.

 

1. Thread A가 공유 자원 X에 접근한다. (Thread A가 공유자원 X를 읽는 순간, X의 값은 10이다)

2. Thread B가 공유 자원 X에 접근한다. (Thread B가 공유자원 X를 읽는 순간, X의 값은 10이다)

3. Thread A가 공유 자원 X를 두배로 만든다 (Thread A가 공유자원을 이미 10으로 읽었었기 때문에, 20이 된다)

4. Thread B가 공유 자원 X를 절반으로 만든다 (Thread B가 공유자원을 이미 10으로 읽었었기 때문에, 5가 된다)

 

우리는 Thread A와 Thread B가 각각 작동하여, 결과적으로 10이 나오기를 예상했지만, 결국 얻은 값은 5가 되며,

이는 예상하지 못한 결과가 발생한 예시이다.

 

따라서 이러한 문제를 해결하기 위해 다양한 기법들이 도입되었다.

 

Synchronization의 구현

위에서 살펴본 예상하지 못한 프로그램 결과를 방지하기 위하여

 

여러 Thread가 공유하는 자원을 사용하게 되는 영역인 Critical Section(임계 영역)`에 대한 접근을 제한하고 컨트롤 하는 테크닉이 필요하다.

Peterson's Algorithm(Spin Lock)

do{
    flag[i] = true;
    turn = j;
    while(flag[j] && turn == j); // wait
    critical section
    flag[i] = false;
}while(true);

공유 자원에 대한 접근을 제어하기 위한 가장 기본적인 알고리즘이다. 

다만 이 방법은 Busy Waiting이라는 치명적인 단점이 존재하는데, 이는 while 문을 계속해서 검사하는 과정에서 CPU 자원이 낭비되는 상황을 의미한다.

계속에서 CPU와 Memory를 사용하면서 wait가 진행되기 때문에, spin lock이라고도 한다.

 

Semaphore

Semaphore는 critical section에 대한 진입을 조절하기 위한 일종의 추상 데이터에 해댕한다.

 

Semaphore 변수 자체는 정수 값을 가지며, P연산과 V연산이라는 두 가지 operation을 가진다.

 

// P연산
while(S<=0) do no-op;
S--


// V 연산
S++;

 

따라서 사용자는 critical section 전에 P연산을, critical section을 빠져나온 후에 V연산을 해주면 Synchronization을 구현할 수 있다.

 

다만 아직까지 busy-waiting 문제가 존재한다는 문제점이 있다.

 

이러한 문제를 해결하기 위해 `Block/Wake up Implementation` 방식을 적용한다.

구현을 위해 Semaphore를 아래와 같이 정의한다.

 

typedef struct{
    int value;
    struct process * L // process waiting queue
} semaphore

value는 이전 구현 방식에서 semaphore의 값에 해당한다.

 

그리고 L은 프로세스의 링크드리스트의 헤드포인터에 해당한다.

 

P와 V연산 또한 다음과 같은 변형이 필요하다.

// P연산

S.value--;
if(S.value <0){
    add this process to S.L;
    block();
}


//V연산
S.value++;
if(S.value <=0){
    remove a process P form S.L;
    wakeup(P);
}

 

Mutex

Mutex는 Mutual Exclusion의 약자로, 상호 배제라는 의미를 가지고 있다.

 

다른 이름으로는 Binay Semaphore라고도 하는데, Semaphore value가 0 또는 1만 가질 수 있는 시나리오와 동일하게 동작하기 때문이다.

 

Lock 또는 Unlock 이라는 두 개의 상태만을 가질 수 있으며, Critical Section에 들어가기 전에 이를 acquire하고, 나올 때 release한다.

 

다만, 순수하게 lock 만을 사용하면 문제가 발생할 수 있다.

 

간단한 수도코드를 살펴보자.

InsertQueue(){
    lock.acquire(); 
    
    put Item on Queue;
    
    lock.release();
}

RemoveQueue(){
    lock.acquire();
    
    if something on Queue
    	remove firstEntry;
    
    lock.release();
}

각각 Queue에 데이터를 넣는 Thread의 동작과, Queue에서 데이터를 꺼내는 Thread의 동작이 설명되어있다.

 

Queue가 비어 있는 상황에서 RemoveQueue가 먼저 실행될 경우,  lock을 획득한 후 아무런 작업도 수행하지 않고 다시 release한다. (마치 spin lock 상황처럼 무의미하게 CPU 자원이 사용됨)

 

따라서 RemoveQueue를 수행하는 Thread는 Queue가 비어 있는 동안에는 실행될 필요가 없으므로 Queue에 데이터가 있는 경우에만 수행되는 것이 효율적일 것이다.

 

그렇다면 RemoveQueue가 실행된 후, Queue에 데이터가 들어올 때 까지 sleep했다가 데이터가 들어오면 깨어나서 작동되는 구조가 가장 이상적일 것이라고 추측할 수 있다.

 

이 구조를 구현하기 위한 방법이 `Condition Variable`이다.

 

이를 활용한 코드는 아래와 같다.

 

InsertQueue(){
    lock.acquire(); 
    
    put Item on Queue;
    condition.signal();
    
    lock.release();
}

RemoveQueue(){
    lock.acquire();
    
    while queue is empty
    	condition.wait(&lock);
    	// 위 코드로 인해 RemoveQueue가 획득했던 lock이 해제되고, sleep 상태에 빠지게 된다.
        
    remove item from Queue
    
    lock.release();
}

RemoveQueue가 실행되면, queue가 비어있는 경우 `condition.wait`를 실행하게 된다.

 

해당 코드를 실행하면 RemoveQueue를 수행하여 lock을 해제하고 Thread는 Sleep 상태에 빠지게 된다.

 

이후 InsertQueue가 해제된 lock을 획득하여 실행되면,  Queue에 item을 넣고 condition.signal() 을 수행하며

sleep 상태에 빠진 RemoveQueue Thread를 깨우고, 깨어난 Thread는 Queue에서 아이템을 제거한다. 

 

condition variable을 사용하여 sleep 중인 Thread를 깨우는 방식에는 signal과 broadcast가 있으며,

signal은 조건에 부합하는 첫 번째 thread를 깨우고, broadcast는 sleep 중인 모든 thread를 깨우는 방식이다.

 

 

Problems of Synchronization

Bounded-Buffer Problem(Producer-Consumber Problem)

대표적인 동기화 관련 문제로, 크기가 유한한 버퍼가 존재하는 환경에서 발생하는 문제를 의미한다.

 

Readers-Writers Problem

Write는 동시에 진행하면 문제가 발생하지만, Read는 동시에 진행해도 큰 문제가 발생하지 않는다.

 

따라서 Read를 수행할 경우에는 Lock을 걸지 않는 방식을 선택하는데, 이 경우 발생하는 문제에 대한 내용이다.

 

// Writer

P(db)
*********************
writring DB is performed
*********************
V(db)


// Reader

P(mutex);
readCount++;
if(readCount == 1) P(db); // Writer의 접근을 차단한다.
V(mutex);
***********
reading 작업 수행
***********
P(mutex);
readCount--;
if(readCount==0) V(db); // Writer의 접근을 허용한다
V(mutex);

위와 같은 코드를 사용하여 문제를 해결할 수 있다.

readCount 변수를 사용하여 Wrtier에 대한 접근을 제어하고 있다.

 

다만, readCount의 변수 또한 공유변수이고, 별 다른 처리를 해 주지 않으면 예상하지 못한 값으로 변할 수 있기 때문에

Semaphore 변수 mutex를 설정하여 해당 값의 변경을 제어해주고 있는 것을 확인할 수 있다.

 

Monitor

Semaphore는 공유 자원에 의해 발생할 수 있는 다양한 Synchronization 문제를 해결하기 위한 매우 훌륭한 해결 방법이다.

 

하지만 몇 천줄의 코드를 작성하는 과정에서 단 한번만 Semaphore 사용에서 실수가 발생해도 전체 시스템에 crash를 발생시킬 수 있다는 치명적인 단점이 있다.

 

이를 해결하기 위한 방법이 Monitor이다.

 

Monitor라고 정의된 class 내부의 procedure를 통해서만 공유데이터에 접근할 수 있도록 하면서, 따로 lock을 걸 필요가 없어지게 한다.

 

대신에 자원이 유무를 파악하기 위해 semaphore 변수와 비슷한 역할을 하는 Condition variable을 필요로한다.

다만 CV는 남은 자원의 개수를 카운터하는 기능은 하지 않고, wait()와 signal() 함수를 통해 프로세스를 잠재우거나 깨우는 역할을 수행한다.