동기화(Synchronization)

Goal

• 동기화가 무엇이고 왜 필요한지 설명할 수 있다.
• 임계 구역(critical section)에 대해 설명할 수 있다.
• 임계 구역 문제를 해결하기 위한 동기화 방법(semapohre, monitor 등)에 대한 이해

관련 용어

• 공유 자원(shared resource)
• 임계 구역(critical section)
• 경쟁 상태(race condition)
• 상호 배제(mutual exclusion)
• 세마포어(semaphore), 뮤텍스(mutex), 모니터(monitor)

---

동기화(Synchronization)란?

시스템을 동시에 작동시키기 위해 여러 사건들을 조화시키는 것을 의미

 

작업들 사이의 수행 시기를 조절하여 사건이 동시에 일어나거나, 일정한간격을 두고 일어날 수 있도록 한다.

 

스레드(또는 프로세스) 동기화라고 하면 멀티 스레드 환경에서 스레드들의 수행시점을 조절하는 것을 의미한다.

클라우드 환경에서 사용되는 '동기화'란 용어 역시 같은 의미로 사용되는데, 기기와 원격 저장소의 데이터가 일치할 수 있도록 제어하는 것을 의미한다.

동기(同期) : 같은 시기. 또는 같은 기간

동기화(同期化) : 작업들 사이의 수행 시기를 맞추는 것

 

스레드 동기화(thread synchronization) 필요성

멀티 스레드 환경에서 두 개 이상의 스레드가 공유 자원(shared resource)에 접근하는 상황이 발생할 수 있다.

이때, 누가, 언제 데이터를 읽고 쓰는지에 따라 그 실행 결과가 달라질 수 있다. (경쟁 상태가 발생할 수 있다)

따라서, 동기화를 통해 예상치 못한 문제가 발생하지 않도록 공유 자원에 대한 접근 순서를 제어해야 한다.

 

*경쟁 상태(race condition)

경쟁 상태란 공유 자원에 대해 여러 개의 프로세스(또는 스레드)가 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다.

 

임계 구역(크리티컬 섹션, Critical Section)

critical section이란 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부를 의미한다. 

(= race condition이 발생할 수 있는 코드의 일부)

 

임계 구역 문제(critical section problem)

임계 구역 문제란 임계 구역으로 지정되어야 할 코드 영역이 임계 구역으로 지정되지 않았을 때 발생할 수 있는 문제를 말한다. (race condition이 발생할 수 있는 코드 부분)

 

따라서 임계 구역 문제가 발생하지 않기 위해서는 임계 구역을 지정해야 한다.

임계 구역을 코드로 지정하면 다음과 같이 지정할 수 있다.

• 입장 구역(entry section) : 임계 구역에 진입하기 위해 진입 허가를 요청하는 부분
• 임계 영역(critical section)
• 퇴장 구역(exit section) : 임계 구역을 빠져 나왔음을 알리는 구역

 

임계 구역 문제 해결 조건

임계 구역 문제를 해결하기 위해서는 다음 3가지 조건을 모두 충족해야 한다.

• 상호 배제(Mutual exclusion) : 임계 구역에 특정 시점에 하나의 스레드만 진입할 수 있다. (다른 스레드는 진입 불가)
• 진행(Progress) : 임계 구역에 진입한 스레드가 없다면, 그 다음 진입할 스레드를 적절히 선택해줘야 한다.
• 한정 대기(Bounded waiting) : 다른 프로세스(또는 스레드)의 기아(Starvation)를 방지하기 위해, 한 번 임계 구역에 들어간 스레드는 다음 번 임계 구역에 들어갈 때 제한을 두어야 한다.

 

임계 구역 해결 방법

가장 일반적인 방법으로는 잠금(Lock)을 통해 임계구역에 특정 스레드(프로세스)만 진입할 수 있도록 허용 하는 것이다.

(Lock을 통해 상호 배제를 보장)

 

Lock의 기능을 제대로 구현하기 위해서는 원자성(atomicity)이 보장 되어야 한다.

 

*atomic operation이란?

분리되어 실행되지 않고 완전히 실행됨이 보장되는 연산을 의미한다.

따라서, atomic operation은 공유 자원에 대한 연산 실행 도중에 다른 스레드의 연산이 끼어들지 않기 때문에 경쟁 상태(race condition)를 피할 수 있다.

 

 <참고> Atomicity(원자성)이란?

원자단위 연산(Atomic Operation)은 실행중에 중단(inturruption)하지 않는, 하나 이상의 순차적인 기계어 명령(machine instruction)으로 이루어져있다. 대개 2개이상의 기계어 명령으로 이루어진 경우에는 원자단위 연산이라 하지 않는다. 명령 실행 도중에 운영체제가 다른 작업을 위해, 현재 진행중인 명령을 중지(suspend)시킬 수 있기 때문이다. 만약 여러 명령들이 원자성을 가지게 하고싶다면, locking등의 동기화 방법을 사용해야 한다. 단, 하나의 기계어 명령은 항상 원자성을 갖는다는 점을 기억하자(CPU는 하나의 기계어 명령을 수행하는 도중 멈추지 않는다). 이로서 알수있는 것은, 어떤 C++ 구문이 하나의 기계어 명령으로 표현되어진다면 그것은 자연적으로 원자성을 갖는다(naturally atomic)는 것이며, 이러한 경우, 굳이 명시적인 동기화 방법을 사용하지 않아도 된다는 것이다.

 

기계어 명령(machine instruction)의 특성

• Atomicity(원자성), Indivisible(분리 불가능)
• 한 기계어 명령의 실행 도중에 인터럽트 받지 않음

 

DB 에서 말하는 ACID 트랜젝션 중 하나인 Atomic 역시 이와 같은 의미로 사용된다.

 

atomic operation 보장되지 않으면 어떤 문제가 발생할까?

상호 배제(mutual exclusion) 문제가 발생할 수 있다.

즉, 임계 구역에 둘 이상의 스레드가 진입하는 문제가 생긴다.

 

예시)

위 두 프로세스가 sdata(shared data)에 1을 더하는 연산을 실행한다고 했을 때, 그 결과가 항상 2가 될까?

결론부터 말하자면, 위 연산의 경우 atomic operation이 아니기 때문에 항상 2라는 결과값을 보장하지 못한다.

 

위 연산은 다음과 같은 기계어 명령어로 분리될 수 있다.

위 명령어 수행 도중 context switching이 발생할 수 있기 때문에 위 연산 실행 결과는 명령어 실행 순서에 따라 달라질 수 있다.

 

상호 배제 문제를 해결하는 방법

<참고> velog.io/@monsterkos/TIL2020.09.05

 

위 방법들은 모두 상호 배제(mutual exclusion)을 해결하기 위한 방법이다.

이 중 가장 많이 사용되는 세마포어(semaphore)에 대해 알아보자.

 

세마포어(semaphore)

세마포어(Semaphore)는 Dijkstra가 고안한, 1)두 개의 원자적 함수로 조작되는 2)정수 변수로서, 멀티프로그래밍 환경에서 3)공유 자원에 대한 접근을 제한하는 방법으로 사용된다.

 

세마포어는 다음과 같은 형태로 정의된다.

int S; // 정수 변수(공유 자원) - 원자적 함수에 의해 조작됨

P() // 임계 구역 진입 전 실행
{
    if (0 < S) S = S - 1;
    else block();
}

V() // 임계 구역에서 나갈 때 실행
{
    S = S + 1;
    wake_up();
}

 

세마포어 사용 형태

P(); // entry section

//임계 구역(Critical Section)

V(); // exit section

 

<설명>

세마포어 S는 정수값을 가지는 변수이며, 다음과 같이 P와 V라는 명령에 의해서만 접근할 수 있다.

(P와 V는 각각 try와 increment를 뜻하는 네덜란드어 Proberen과 Verhogen의 머릿글자를 딴 것이다.)

 

• P() : 임계 구역에 진입 전 수행
• V() : 임계 구역 나올 때 수행

P와 V 모두 원자성을 만족해야 한다. 다시 말해, 한 프로세스(또는 스레드)에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다.

 

Semaphore 종류

• counting semaphore : 임의의 자원 개수를 허용하는 세마포어 (n개의 자원의 허용)
• binary semaphore : '잠김/해제' 와 같이 0 또는 1만을 가질 수 있도록 자원 개수를 1개로 제한하는 세마포어

 

- counting semaphore

semaphore가 동기화 방법 중 하나이지만, 다수의 자원을 허용하는 counting semaphore의 경우 임계 구역(critical section)에서 발생하는 경쟁 상태(race condition)를 완전히 해소하지는 못한다. (mutex 는 해결 가능)

 

사용 예시

• 로그인 인원 수 제한
• 한정 버퍼 문제(bounded-buffer problem) - 생산자-소비자 문제(producer-consumer problem)라고도 함
  • 세마포어로 자원의 개수를 한정하고, 버퍼를 동기화 시켜 정상 동작할 수 있도록 한다.

 

- binary semaphore (mutex)

특별히 1개의 자원만 허용하는 binary semaphore를 mutex(또는 lock)라고도 한다.

binary semaphore와 mutex의 차이를 구분짓는 경우도 있는데, 이 경우 mutex는 잠금/해제를 하는 주체가 동일 해야 한다는 제한이 있다. 이런 제한 때문에 mutex가 안전한 동기화 방법이라고 한다.

 

사용 예시

• 상호 배제를 보장해야 하는 경우
  • ex) 공유 변수를 두 개 이상의 스레드에서 증가 또는 감소 시키는 경우 : 회복과 피격이 동시에 되는 경우

 

세마포어를 구현하는 방법

원자적 연산을 보장하기 위해 사용되는 방법

• 하나의 기계어 명령어로 이루어진 연산 사용 (단일 명령어는 중간에 인터럽트 되지 않으므로 동기화가 필요 없음)
• 두 개 이상의 명령어로 구성된 연산일 경우 인터럽트를 무시하여 하나의 연산 처럼 동작하게 한다.
  • 모든 가능한 하드웨어, 소프트웨어의 인터럽트를 불가능하게 인터럽트 레벨을 증가시켜 원자적 동기화를 구현한다.

 

어쩃든, 프로그래머 입장에서 보면 운영체제나 언어적 차원에서 원자적으로 동작하게 하는 연산 및 함수를 이용해서 원자성(Atomicity)을 보장 받아야 한다.

 

동기화 사용 방식(spin lock, semaphore, monitor)

Spin Lock이란?

스핀락(spinlock)은 임계 구역(critical section)에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락을 가리킨다. 스핀락이라는 이름은 락을 획득할 때까지 해당 스레드가 빙빙 돌고 있다(spinning)는 것을 의미한다. 스핀락은 바쁜 대기(busy waiting)의 한 종류이다.

= busy waiting + Locking

 

바쁜 대기(busy waiting) 방식이기 때문에 CPU 자원을 계속해서 사용한다. (단점)

 

그렇다면 어떤 상황에서 사용 될 수 있을까?

• 자원을 점유하는데 까지 많은 시간이 소요되지 않는 상황인 경우 (짧은 시간 이내에 자원을 점유할 수 있는 경우)
• Context Switching 비용보다 성능적으로 더 우수한 상황인 경우

또한, 다음과 같은 형태로도 사용될 수 있다.

Spin Lock으로 짧은 시간 동안 대기하고 오래 걸릴 경우 Semaphore 방식 사용

 

Semaphore (or mutex)

일반적으로 Semaphore나 mutex는 busy waiting 방식이 아닌 sleeping(blocking) 방식을 사용한다.

즉, 커널 기능을 이용해 스레드(프로세스)를 재우고(sleep), 깨우는(wake up) 방식으로 동기화한다.

 

Sleeping 방식은 운영체제에서 다음과 같은 형태로 동작한다.

1. sleep : 자원을 점유하기 위해 기다리는 스레드들을 대기 큐(wait queue)에 넣는다.
2. wake up : 자원을 점유하고 있던 스레드가 자원을 반납한 경우 신호(signal)를 보내 대기큐에 있는 스레드 중 하나에게 자원을 점유할 수 있도록 한다.

 

Sleeping은 어떤 상황에서 쓸까?

• busy wating 없이 자원을 점유하고 싶은 경우

 

Sleeping방식의 경우 Context Switching에 의한 Overhead가 발생할 수 있다.

 

Monitor

세마포어에서 사용되는 두 원자적 함수(P, V)가 인터페이스 형태로 제공되는 동기화 방법이다.

즉, 개발자의 잘못된 사용을 방지하기 위해서 제공되는 안전한 형태의 동기화 기법이다.

(흔히 객체지향 언어에서 말하는 캡슐화를 사용한 방법)

 

예시)

다음과 같은 형태로 공유 자원을 내부적으로 숨기고 공유 자원에 접근할 수 있도록 인터페이스를 제공할 수 있다.

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

 

 

<참고> 동기, 비동기 방식

*동기(synchronous : 동시에 일어나는)

• 시스템을 동시에 동작시키기 위해 실행 순서의 제어가 필요함
• (자원 등) 요청 후 응답을 받기 까지 대기 상태가 발생
• 웹 - 요청(request)후 응답(response)을 받아야지만 다음 동작 수행이 가능
• DB - A노드 B노드 사이의 트랜젝션(transaction) 처리

*비동기(Asynchronous : 동시에 일어나지 않는)

• 실행 순서 제어가 필요 없음 (공유 되는 자원이 없는 경우)
• 요청 후 응답을 기다리지 않아도 됨

 

프로세스간 통신에서 동기화 기능이 있는지 없는지에 따라

동기화(synchronous) 통신, 비동기화(asynchronous) 통신으로 구분할 수 있다.

(blocking / non-blocking 통신으로 구분하기도 한다)

 

References

동기와 비동기의 개념과 차이

critical section problem - tutorialspoint

velog.io/@monsterkos/TIL2020.09.05

C++에서의 원자성에 대한 설명