동기화(Synchronization)

다수의 프로세스 혹은 스레드가 같은 공유 자원에 접근할 때, 일관된 순서가 정해지지 않으면 데이터의 일관성이 깨지게 된다. 이때 공유 자원에 대한 접근 순서를 보장해주는 과정이 동기화이다. 동기화는 프로그램의 안정성을 위해 필요하다.

프로세스들이 서로 동작을 맞추는 것
프로세스들이 서로 정보를 공유하는 것

경쟁 상태(Race Condition)

여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라지는 상황을 말함
- 이러한 공유 데이터의 동시 접근(Concurrent access)은 데이터 불일치 문제를 발생시킬 수 있음
따라서 경쟁상태를 막고 데이터의 일관성을 유지하기 위해서 프로세스 간의 실행 순서를 정해주는 매커니즘인 동기화(Synchronization)가 필요함

임계 영역(Critical Section)

개념
- 코드 상에서 경쟁 상태(Race Condition)가 발생할 수 있는 특정 부분
- 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분
임계 영역 문제
- 여러 프로세스가 공유자원에 동시에 접근하면 문제가 발생할 수 있음
- 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한해야 함
임계 영역 문제 해결을 위한 기본 조건
- 상호배제(Mutual Exclusion)
  - 한 프로세스가 임계 영역에서 수행 중이라면, 다른 프로세스가 임계 영역에 들어가지 못하게 해야 함
  - 이러한 상호 배제로 deadlock(교착 상태)과 starvation(기아 현상)이 발생하게 됨
- 진행(Progress - avoid deadlock)
  - 임계 영역에 있는 프로세스 외에는 다른 프로세스가 임계 영역에 진입하는 것을 방해하면 안됨
  - 현재 기다리고 있는 스레드가 있다면, 누가 먼저 들어갈 것인지에 대한 결정이 유한 시간 내에 일어나야 함
- 한정된 대기(Bounded Waiting - avoid starvation)
  - 임계구역으로 진입하기 위해 대기하는 모든 스레드는 유한 시간 이내에 해당 임계구역으로 진입할 수 있어야 함
  - 다른 프로세스의 기아를 방지하기 위해, 한 번 임계 영역에 들어간 프로세스는 다음 임계 영역에 들어갈 때 제한을 두어야 함

교착 상태(Deadlock): 무한대기 기아 상태(Starvation): 우선순위가 낮아 자원을 계속 할당 받지 못하는 상태 바쁜 대기(Busy waiting): 공유자원의 권한을 얻을 때까지 계속 대기하고 있는 상태

상호배제(Mutex, Mutual Exclusion)

개념
- 두 개 이상의 스레드가 공유 자원을 사용할 때, 하나의 스레드가 공유 자원을 사용하고 있으면 다른 스레드는 접근할 수 없도록 막는 것
- 하나의 프로세스만 임계 영역을 사용할 수 있도록 다른 프로세스의 접근을 차단하는 것
기본 연산
- enterCS() : 임계영역 집입 전 검사 및 다른 프로세스 존재여부 검사
- exitCS() : 임계영역에서 벗어날 때의 후처리 과정 및 임계영역 벗어남을 알림
상호배제 기본 연산을 만들기 위해 필요한 조건
- 상호배제(Mutual Exclusion), 진행(Progress), 한정된 대기(Bounded Waiting)

상호배제를 위한 해결 방법

수준	방법	종류
고급	SW solutions	- 데커 알고리즘 - 피터슨 알고리즘 - 다익스트라 알고리즘
고급	OS supported SW solution : 프로그래밍 언어와 운영체제 수준에서 제공	- 세마포어 - 뮤텍스 - Spinlock - Eventcount / Sequencer - 모니터
저급	HW solution	- TestAndSet(TAS) - CompareAndSwap(CAS)

수준

방법

종류

고급

SW solutions

- 데커 알고리즘 - 피터슨 알고리즘 - 다익스트라 알고리즘

고급

OS supported SW solution : 프로그래밍 언어와 운영체제 수준에서 제공

- 세마포어 - 뮤텍스 - Spinlock - Eventcount / Sequencer - 모니터

저급

HW solution

- TestAndSet(TAS) - CompareAndSwap(CAS)

SW solutions

Dekker's Algorithm
- 프로세스 2개일때 상호배제를 보장하는 최초의 알고리즘
- flag와 turn의 개념을 혼합해서 사용하여 조건 3가지를 부합시킴
  - flag: 누가 CS(Critical Section)에 진입할 것인지 알리는 변수
  - turn: 누가 CS에 들어갈 차례인지 알리는 변수
Peterson's Algorithm
- Dekker's Algorithm의 업데이트 버전으로 보다 간단하게 구현함(간소화)
  - 다른 점은 서로 양보하는 것
- 스레드의 순서를 결정하는 turn 변수를 추가한 알고리즘
- 단점
  - 속도가 느림
  - 프로세스가 두 개인 경우에만 적용 가능
  - 자원을 많이 소모한다(Bush Waiting)
  - 현대 컴퓨터에서 정상 작동 하지 않음
Dijkstra's Algorithm
- 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
- 실행 시간이 가장 짧은 프로세스에 프로세서를 할당하는 세마포어 방법
- 가장 짧은 평균 대기시간 제공

소프트웨어 기반 알고리즘의 문제점

속도가 느리고 구현이 복잡함
수행 도중에 선점(preemption)이 발생할 수 있음
- 운영체제가 인터럽트를 막아준다고 하더라도 오버헤드가 발생함
Busy waiting 발생 ➜ 비효율적
- CPU의 자원을 낭비하면서 무한루프에 빠질 수 있음

OS supported SW solution

SW solution과 HW solution의 busy waiting 문제를 해결하기 위해 OS의 도움을 받는 문제 해결 방식으로, 가장 대중적으로 사용함

spinlock
- 락을 획득하려는 스레드가 락을 얻을 때까지 계속해서 반복(확인 및 기다림)하는 방식
  - lock을 얻을 수 없다면 계속해서 lock을 확인하고 얻을 때까지 기다림(spin) ➜ Busy waiting
- 정수형 변수이며 OS가 보장함
- Context Switching이 발생하지 않아 그에 따른 부하를 줄일 수 있음
- 여전한 Busy waiting 문제와 기다리는 동안 CPU 리소스 낭비의 문제가 존재함
Semaphore
- Busy waiting 문제 해결
- 상호배제, 프로세스 동기화 등 다양한 동기화 문제 해결 가능
Eventcount/sequencer
- 스레드나 프로세스 간의 통신과 순서를 관리하기 위해 사용
- 세마포어에서 Busy waiting을 해결했지만, 대기하고 있는 프로세스 중 어떤 것을 깨울지 정해진 순서가 없기 때문에 이를 정형화하기 위해 등장함
  1. Event Count(이벤트 카운트)
    어떤 이벤트가 발생했음을 나타내는 카운터로 이벤트 발생 시 마다 카운터 증가
    다른 스레드나 프로세스는 이벤트 카운터의 값 체크로 원하는 이벤트 발생 확인 및 대기
  2. Sequencer(시퀀서)
    각 작업에 고유한 번호나 시퀀스를 부여해 작업들이 시퀀스에 따라 순서대로 실행될 수 있도록 보장
- Busy waiting과 Starvation 문제 해결
- 세마포어보다 더 low-level 컨트롤이 가능함(더 세세한 컨트롤이 가능)

HW solution

하드웨어가 한 번에 수행되는 것을 보장해주기 때문에 SW solution에 비해 구현이 간단하지만, 여전히 Busy waiting 발생함

`TestAndSet (TAS) instruction`

Test와 Set을 한 번에 수행하는 기계어(machine instruction)
- 기계어 명령의 특성: 원자성, 분리 불가능, 한 기계어 명령의 실행 도중에 인터럽트를 받지 않음
- 따라서 TAS는 기계어이기 때문에 명령어 수행 중 선점이 되지 않음
TAS를 이용한 상호배제 구현
```
// target을 검사하고, target 값을 true로 변경
boolean TestAndSet (boolean *target) { // <- 한번에 수행(machine instruction)
    boolean temp = *target;  // 이전 값 기록
    *target = true;          // true로 설정
    return temp;             // 값 반환
}
```
```
boolean lock = false;
do {
    while(TestAndSet(&lock));
    // critical section
    lock = false;
} while(true);
```
1. 가장 먼저 TestAndSet()을 실행하는 프로세스가 while(TestAndSet(&lock)); 루프에서 lock = true로 바꾸고, false를 반환받음
2. 이후 while문을 빠져나와서 임계 영역에 진입함
3. 다른 프로세스는 lock = false가 될 때까지 while 루프를 빠져나오지 못하고 계속 대기함
4. 임계 영역에 진입했던 프로세스가 임계 구역을 빠져나오면서 lock = false를 수행하고 lock을 풀어주면, 대기하던 다른 프로세스가 임계 영역에 진입함

`CompareAndSwap(CAS)`

두 워드의 내용 교환에 기반을 둔 두개의 워드에 대해 원자적인 연산을 수행함
CPU가 메인 메모리의 자원을 CPU 캐시 메모리로 가져와 연산을 수행하는 동안, 다른 스레드에서 연산이 수행되어 메인 메모리의 자원 값이 바뀌었을 경우, 기존 연산을 실패처리하고 새로 바뀐 메인 메모리 값으로 재수행하는 방식
- 메인 메모리와 캐시 메모리의 값이 일치하면 새로운 값으로 교체하고, 그렇지 않다면 기존 교체를 실패시키고 계속 재시도함
CAS를 이용한 상호배제 구현
```
int CompareAndSwap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected) {
        *value = new_value;
    } 
    return temp;
}
```
```
do {
  while(CompareAndSwap(&lock, 0, 1) != 0);
  // critical section
  lock = 0;
} while(true);
```
- TestAndSet()과 유사하지만, TAS는 메모리 값의 변경 여부에 상관없이 항상 값을 변경했더라면 CAS는 기대값과 메모리 값이 같을 때만 값을 변경함
- 보통 value에는 lock 변수의 주소, expected는 가용 상태를 나타내는 0, new_value는 해당 변수를 사용하겠다는 의미로 1을 넣음

멀티코어 환경에서 동기화 기법

멀티코어 프로세서에선 여러 코어가 동시에 공유 메모리에 접근할 수 있으므로 공유자원에 대한 동시 접근을 제어하고 일관성 유지를 위한 동기화 기법이 필요함

락(Locking)
- 락은 공유 자원에 대한 접근을 제어하는 기본적인 동기화 매커니즘
- 뮤텍스, 세마포어 등의 락 기법을 사용하여 공유자원을 보호하고, 한 번에 하나의 코어만 자원에 접근할 수 있도록 한다.
원자적 연산(Atomic Operations)
- 원자적 연산은 중간 단계를 거치지 않고 한 번에 수행되는 연산
- 멀티코어 프로세서에서 원자적 연산을 사용하면 여러 코어가 동시에 수행하는 연산 간에 데이터 경쟁이 발생하지 않도록 할 수 있다.
- TAS, CAS 등의 원자적 연산을 사용하여 공유 자원의 동시 접근을 제어할 수 있다.
메모리 배리어(Memory Barrier)
- 메모리 배리어는 프로세서 최적화를 제한하여 명령어 순서를 보장하는 기법
- 멀테코어 프로세서에서 메모리 배리어를 사용하면 코어 간에 일관된 메모리 순서를 유지할 수 있다.
락 프리 알고리즘 및 자료구조(Lock-Free)
- 락 프리 알고리즘 및 자료구조는 락 없이 동시성 문제를 해결하기 위한 기법이다.
- 락 프리 기법은 원자적 연산, 메모리 베리어 등을 활용하여 동시에 여러 코어가 공유 자원에 접근하면서도 동시성 문제를 제어할 수 있다.
병렬 프로그래밍 라이브러리 및 프레임워크
- 병렬 프로그래밍을 지원하는 라이브러리와 프레임워크를 사용하여 멀티코어 프로세서에서 동기화를 구현할 수 있다.

Ref

Previous동기/비동기 & 블로킹/논블록킹 Next메모리 할당과 단편화

Last updated 5 months ago