1일 1커밋 !

동기화, Synchronization

스레드, 프로세스들이 어떤 리소스를 공유할 때 실행 순서를 잘 조정하는 것이다. 실제 많은 스레드들이 Shared Data 에 접근할 때 서로 협력하며 접근한다.

예를 들어 스레드 A 가 작업 완료한 것을 스레드 B 가 가져다 사용해야한다면 당연하게도 실행 순서는 A -> B 이다. 이때 B -> A 가 일어나지 않도록 조정하는 것이 동기화라고 할 수 있다.

흔한 예시로 은행에서 각자 A, B 가 같은 통장에서 돈을 출금한다고 생각해보자. 100만원이 들어있는 통장에서 A가 출금하려 할 때 B 도 통장을 읽힌다면 B 의 눈앞에는 100만원이 든 통장이 존재한다. 이때 A 가 출금을 했지만 이미 B 는 이미 통장을 읽히고 출금하려하기 때문에 출금에 성공할 수 있는 문제가 있다.

Producer Consumer Example

image

동기화에서의 고전적인 문제이다. 데이터를 생성하지 않았을 때 컨슈머는 데이터를 가져갈 수 없기 때문에 데이터가 없다면 항상 프로듀서가 실행되어야한다.

이때 두 가지 문제가 존재한다.

  1. Synchronization 이 이루어지지 않는다. 즉 Critical Section 이 보호되지 않는다.
  2. CPU 가 낭비되면서 동작하고 있다. (Busy wait) 무한 루프를 돌다가 스레드의 타임퀀텀이 끝나야 다음 스레드로 넘어간다.

Requirements

먼저 첫 번째 문제에 대해서 살펴보도록 하자.

  • Race Condition : 두 개 이상의 Concurrent 한 스레드가 하나의 공유 자원을 사용하려고 경쟁하는 상황, 조건을 말한다.
  • Critical Section : Race Condition 이 발생했을 때 서로 사용하려고 하는 부분으로 문제가 생길 수 있는 범위이다. 이 섹션에는 한 번에 하나의 스레드만 들어갈 수 있다.
    • 위의 예시에서 buffer 에 데이터 쓰거나 읽고 count 를 변경하는 부분을 통틀어서 Critical Section 으로 볼 수 있다. 따라서 프로듀서가 해당 섹션에 진입한다면 컨슈머는 자신의 섹션에 진입할 수 없다!

동기화를 하기 위한 세 가지 조건이 존재한다.

  1. Mutual Exclusion
    • Shared Data 는 한 곳에서만 사용되어야한다.
  2. Progress
    • Shared Data 를 쓰려고 하는 데, 아무도 쓰고 있지 않으면 바로 사용해야한다. 다른 스레드가 사용할까봐 잠시 기다려주면 안된다.
  3. Bounded Waiting
    • 어떤 스레드가 Shared Data 를 사용하고 있으면 다 사용할 때까지 기다려야한다.

Synchronization Tools

동기화를 위한 총 네 가지 방법에 대해서 알아보도록 하자.

  1. Locks

    low level 에서 이루어지는 동기화이다. OS가 아래 다른 메커니즘을 만들기 위해 사용한다. spin lock / block 을 사용한다. 무한 루프를 돌면서 Busy wait 하는 것이다.

    Critical Section 중에 Interrupt가 걸리면 문제가 발생할 수 있기 때문에 한번에 수행해야한다. 이를 더 이상 쪼갤 수 없다는 뜻으로Atomic Operation 이라 한다. 예시로는 TestAndSet, CompareAndSwap 이 존재한다.

    하지만 낭비가 심해 OS가 아주 짧은 ciritical section에 사용하는 방법이다. 어플리케이션은 프로세스를 wait상태에서 기다리도록 구현한다. 이를 구현할 때 spin lock 이 사용될 수 있다.

    image Disabling Interrupt : OS만 Interrupt할 수 있다. 당연히 막는 것도 OS만 가능하다. CPU가 한개 있을 때만 사용할 수 있다. 두개 이상이면 모든 CPU를 제어해야하기에 비효율적이다.

  2. Mutex lock

    High-level 에서 이루어지는 동기화이다. 내부에서 lock을 거는 메커니즘은 atomic instruction으로 이루어진다.

  3. Semaphores

    사용 가능한 Shared Data의 개수를 알려주는 Integer Counter 이다. wait, signal 두 가지 함수를 가지고 있다. Shared Data를 사용할 때 wait을 하면 -1, 다 사용 후 반납하면 signal 하면 +1 이다.

    0/1만 가능하면 Binary Semaphore 라 부르며 사실상 mutex lock과 동일하다. 개수가 2 이상 가능하면 Counting Semaphore라 한다.

    현재 Semaphore = 0 일 때 wait이면 할당할 Shared Data가 없으므로 할당할 수 없어 Wait한다.

    A 실행 후에 B가 실행되어야하면 semaphore를 0으로 두고 A 완료 후 signal, B 시작 전 wait으로 coordinate 할 수 있다.

    Semaphore를 구현할 때는 int 변수와 wait 상태인 프로세스들을 정리할 리스트가 필요하다. wait, signal 함수의 내부에서 ++, - - 를 할 때도 한 줄이지만 instruction으로는 3개의 명령어가 존재하므로 ciritical section이므로 보호해야한다. 여기서 사용하는 Lock, unlock은 low-level이며 OS에서 수행되는 lock/unlock이다.

    하지만 Semaphore 자체가 전역변수이면서 Shared Data이다. 따라서 유지보수가 어려워지는 소프트웨어 엔지니어링 이슈가 발생할 수 있다.

  4. Monitors

    image

    프로그래밍 언어에서 Critical section을 보호하는 기능을 지원한다.

    Critical Section에 하나의 스레드만 들어가도록 모니터링한다. 클래스-함수처럼 사용히며, 하나의 함수에는 하나의 스레드만 사용할 수 있다. 모니터 안에 하나의 스레드가 들어와 펑션을 사용 후 빠져 나가면 다음 스레드가 와서 사용한다. 펑션 사용 중에 뭔가를 기다려야하는 상황이면 조건을 기다리는 que로 이동해서 비켜줘야한다.

    x라는 컨디션이 발생하기를 기다린다면, x가 발생했을 때 알려주는 오퍼레이션 필요하다. 이를 Condition Variable 이라 하고, wait이면 일어나고 signal이면 꺠운다. signal이 오고 wait이 오면 다른 signal이 올 때까지 기다려야함.

업데이트:

댓글남기기

참고