[OS] Synchronization

Terminology

Synchronization = 동기화 (≠ 병렬)

:  멀티스레드 환경에서 공유 데이터에 접근할 때 발생하는 문제를 해결하기 위한 메커니즘으로, atomic (indivisible) operation을 사용하여 쓰레드 간의 협력을 보장한다.

왜 필요한가? (Policy)

OS의 최종 목적은 Multiprogramming이다. 이를 통해 하드웨어 리소스를 최대한 효율적으로 사용함으로써 사용자가 무한대의 자원을 사용하고 있다고 느끼게끔 돕는다. 그러면 더욱이 처리 속도를 높이기 위해 동시에 여러 작업을 실행할 수 있도록 작업이 완료되기 전에 다른 작업을 수행할 수 있도록 비동기 처리하여야하는게 아닐까? 생각이 든다. 아주 타당한 생각이다. 다만, 동기화를 수행해야 하는 특수한 상황이 존재한다. 바로, 프로세스간 영향을 주고 받는 협력적 프로세스를 사용할 때이다. 프로세스가 서로 영향을 주고 받기 위해서는 논리주소 공간을 공유한다거나 공유 메모리 메모리를 사용해야 한다. 이때, 여러개의 프로세스가 동일 리소스에 접근하면 어떻게 될까? 질서 있는 실행이 이루어지지 않아 데이터 일관성에 문제(producer consumer problem)가 생기지 않을까? 이러한 여러 프로세스가 동일 리소스에 접근하기 위해 경쟁하는 상황을 race condition(경쟁 상황)이라고 한다. 해당 상황을 타개하기 위해 오직 하나의 프로세스만이 해당 데이터에 접근/조작하도록 보장하는데, 이를 동기화(Synchronize)라하며, Mutex Locks나 Semaphore를 통해 이뤄질 수 있다

.

잠깐 생산자 소비자 문제를 언급했는데, 이는 producer가 생산하는 동안, context switching에 의해 consumer가 실행될 수 있다면, race condition이 발생하여 interleaving(데이터 불일치)가 발생하는 문제이다. 이를 해결하기 위해 “Atomic operation(원자성 연산)”을 사용한다. 이는 context switch가 일어나지 않게 timer interrupt를 disable하여 producer와 consumer가 동시에 병렬적으로 실행되지 않도록 막는 것이다.

 

어떠한 혜택이 있나?

Atomic operation을 사용하면 Synchronize를 통한 쓰레드 실행 순서를 보장할 수 있으며, Mutual exclusion을 통해 한번에 한 쓰레드만 임계구역에 들어갈 수 있도록 보장할 수 있다. 이때, starvation과 deadlock은 피해야 하는데, 이는 접근 시도한 프로세스는 언젠가 접근 성공해야 하고, 항상 접근 시도한 프로세스들 중 하나는 접근 성공해야 한다는 의미이다.

임계구역(Critical Section)을 언급했는데, 이는 한번에 하나의 쓰레드만 실행할 수 있는 코드영역이다. 즉, 적어도 하나 이상의 다른 쓰레드와 함께 접근과 갱신이 가능하도록 공유하는 영역으로, 한번에 하나의 쓰레드만 접근할 수 있어야 한다.

 

위 사진 처럼 공유 메모리가 아닌 곳에서는 map을 통해 동시병렬로 실행되다가 critical section을 만나면 reduce를 통해서 하나의 쓰레드만 임계 구역에 들어가도록 하여 데이터의 무결성도 지키며 리소스도 최대한 효율적으로 사용한다. 즉, seralization을 통하여 반 병렬화를 시키는 것이다.

*reduce하는 곳을 entry라고 하며, map하는 곳을 exit이라고 한다.

 

임계 구역의 조건은 다음과 같다. 싱글 쓰레드 시스템의 경우에는, interrupt를 막아서 context switching이 일어나지 않도록 한다. 다만, multi 쓰레드 시스템의 경우에는 1. mutual exclusion 2. process 3. bounded waiting이 지켜져야 한다. 이러한 3가지 조건을 모두 지키도록 설계된 솔루션이 있다. 바로 Peterson’s Solution이다.

 

Peterson’s Solution에서는 누구의 “turn”인지 추적하는 referee를 사용한다. 또한, “flag”을 사용해서 c.s에 들어갈 준비가 되었음을 표시한다. 스레드들은 flag을 들어 turn을 부여받는다. 그 상태로 기다리다가 타 쓰레드의 flag들이 모두 내려가 있거나 나의 turn이면, c.s에 들어간다.

 

Mechanism

이러한 c.s영역에서의 동시성 제어(동기화)를 위해 사용하는 기법에는 크게 두가지가 있다. 첫째, SpinLock(특정한 유형의 Mutual Locks)이며, 둘째로는 Semaphore가 있다.

Spin Lock

acquire()를 통해 Lock을 획득하고, release()를 통해 Lock을 반환한다. 이를 통해 어떠한 스레드가 critical section(CS)에 들어가 있을 동안에는 Lock을 통해 다른 스레드가 CS에 들어가지 못하게 한다. 그러나 해당 CS에 들어가고자 하는 다른 스레드들은 busy waiting하며 CS에 들어갈 준비를 계속하고 있어야 한다. Spinlock은 짧은 시간 동안 CS를 이용하는 경우에 유리할 수 있다. 이는 Lock이 풀리기를 기다리는 동안 비용이 높은 context switch를 피할 수 있기 때문이다. Context switch를 할 때는 CPU의 모든 레지스터 값을 PCB에 저장하고, 페이지 테이블을 갱신하며, 스케줄링을 통해 다음에 실행될 스레드를 선택하고 CPU를 할당하는 등 많은 작업이 필요하다. 따라서 Spinlock은 이러한 context switch의 비용을 줄이면서 동시성 제어를 할 수 있는 유용한 방법이다.

Semaphore

Semaphore는 spinlock에 비해 CPU 사용이 더욱 효율적이며, 우선순위 역전을 방지할 수 있다. 특히 멀티태스킹 환경에서 효율적인데, semaphore는 대기하는 동안 스레드를 대기 상태로 전환하여 자원을 보다 예측 가능하게 하며 스케줄링이 가능하여 자원을 보다 효율적으로 사용할 수 있게 한다. 또한 spinlock에서는 우선순위가 높은 스레드가 대기하면서 priority inversion이 발생할 수 있는데, semaphore에서는 우선순위 상속과 같은 기법을 사용하여 해당 문제를 방지할 수 있다.

Semaphore의 실행 순서는 다음과 같다:

1. 임계영역에 허용되는 수로 초기화
2. 사용하고자 하면 wait(p)으로 semaphore 감소
3. 다 쓰고 자원 방출 시 signal(v)로 semaphore 값 증가와 sleep하고 있던 스레드가 있다면 wake up을 하는 단계로 이루어진다.

만일, critical section(CS)에 들어갈 때 acquire()를 통해 lock을 획득하고, CS에서 나갈 때 release()를 통해 lock을 푼다면, lock을 하고 sleep해야 하는 특정 상황에 대처하지 못한다. 그런 상황이 발생하면 다른 스레드가 해당 리소스에 접근/제어를 못하게 되어 lock을 풀지도 못한다. 그래서 위와 같이 condition variables(wait, signal)을 사용해서 lock을 풀고 CS 안에서 sleep할 수 있는 환경을 조성한다. Condition variable에는 두 가지의 스타일이 있다:

1. Hoare-style: signal()이 실행되면 lock을 포기하여 ready queue의 다음 순이 실행된다.
2. Mesa-style: signal()이 실행되면 lock을 유지하며 대기 중인 스레드가 큐에 추가되지만, ready queue의 다음 순이 실행된다는 보장은 없다.

정리하면, 프로그램이 데이터 구조에 대한 작업을 수행하기 전에 lock을 획득하고, 다른 작업이 데이터 구조를 적절한 상태로 만들 때까지 기다려야 하는 경우, condition variable을 통해 기다린다.

 

Condition variable의 wait()을 통해 busy wait 대신 자신을 일시중지 시킬 수도 있다. wait()를 실행할 때 semaphore 값이 0보다 작다면, sleep mode로 가는데, signal()을 통해 wake up이 되면 ready queue로 들어가 CPU 할당을 기다리게 된다. 이처럼 wait()과 signal()까지의 코드 영역을 임계영역으로 묶어 중간에 context switch가 일어나지 않도록 interrupt를 disable한다. 하지만, 멀티코어를 가진 경우, 자신 이외에 다른 CPU에는 interrupt disable이 불가능하다. 그래서 이때는 Test&Set instruction을 통해 하드웨어적인 제한을 두어 다른 CPU에서도 CS 접근을 막는다.