동기화

JeongSeulho

2023년 02월 06일

경쟁 조건

여러 프로세스/스레드가 동시에 같은 데이터를 조작할 때, 접근 순서에 따라 결과가 달라지는 상황

DB의 트랙잭션과 같은 원리
두 스레드에서 어떤 변수의 값을 +=1 하는 경우

copy

public class Counter {
    private int count = 0;

    public void increment() {
        count++;
    }
}

for(int i = 0; i < 10; i++) {
    counter.increment(); // 각 루프문의 다른 스레드에서 실행된다면?
}

동기화

여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것

임계영역(Critical Section)

공유 데이터 일관성을 위해 하나의 프로세스/스레드만 진입하여 실행 가능한 영역

copy

   // 이 메소드를 임계영역으로 설정하여 해결
   public void increment() {
        count++;
    }

임계 영역 동작 과정

copy

do {
    entry section // 진입 전 가능한지 확인
    critical section // 임계영역 실행
    exit section // 나가기
    remainder section // 나머지 코드
} while(true);

임계영역을 해결책이 되기 위한 조건

상호 배제(Mutual Exclusion) : 한번의 하나의 프로세스/스레드만 임계영역에 진입 가능
진행(Progress) : 임계영역에 진입을 원하는 프로세스/스레드가 있고 임계영역이 비워져있다면 진입 가능
한정된 대기(Bounded Waiting) : 프로세스/스레드가 임계영역에 진입하기 위해 대기하는 시간이 한정되어야 함

Thread-unsafe

언어에서 기본적으로 제공하는 메소드나 API가 모두 동기화를 지원하지 않음
공식문서를 확인하여 지원 여부 확인 및 필요시 직접 구현

상호 배제 구현 방법

spin lock

임계영역 진입을 위해 lock을 획득하고 임계영역 종료 후 해제

copy

volatile int lock = 0; // global variable

// 임계영역 진입 전 임계영역이 사용중인지 확인
// 임계영역이 사용중이면 1, 사용중이지 않으면 0
int testAndSet(int *lockPtr) {
    int oldLock = *lockPtr;
    *lockPtr = 1;
    return oldLock;
}

void criticalSection() {
    while(testAndSet(&lock) == 1); // 임계영역 진입 전 임계영역이 사용중인지 확인
    ...critical section... // 임계영역 실행
    lock = 0; // 임계영역 종료
}

testAndSet은 CPU atomic 명령어
- 실행 중간에 간섭받거나 중단되지 않음
- 동시에 실행 못하게 함, 두개의 스레드가 멀티 코어로 동시에 실행하려해도 하나가 먼지 실행되며 끝나고 다음 실행
lock을 계속 확인하며 비효율적

mutex

lock이 준비되면 다음 스레드에게 알림

copy

volatile int value = 1; // 0: 임계영역 사용중, 1: 임계영역 사용 가능
volatile int guard = 0; // value에 대한 동기화 보장

void lock() {
    while(testAndSet(&guard) == 1);
    if(value == 0) {
        ... 접근한 현재 스레드를 큐에 넣음
    } else {
        value = 0;
    }
    guard = 0;
}

void unlock() {
    while(testAndSet(&guard) == 1);
    if(큐에 대기중인 스레드가 있으면) {
        ... 큐에서 스레드를 꺼내 임계영역에 진입
    } else {
        value = 1;
    }
    guard = 0;
}

// 사용
lock();
...critical section...
unlock();

spin lock vs mutex

mutex는 큐에서 대기하고 호출하는 Context Switching이 발생
critical section 작업이 Context Switching 보다 빨리 끝나면 => 굳이 큐에서 대기하는 Context Switching이 더 안좋음
즉, critical section 작업이 빠르면 spin lock이 더 좋음

위 조건은 멀티코어 환경에서 성립
싱글코어라면 한번에 하나의 스레드만 실행됨
즉, spin lock에서 while로 cpu time동안 lock을 확인해도 처음에 lock을 획득 못했다면 해당 cpu time 동안 계속 획득 못함
mutex는 끝나면 알려주므로 불필요한 Context Switching이 발생하지 않으므로 싱글 코어에서는 mutex가 더 좋음

semaphore

하나 이상의 프로세스/스레드가 critical section에 진입할 수 있도록 함
mutex에서 value가 0 또는 1이었다면, semaphore에서는 0 이상의 값을 가짐

copy

volatile int value = 1; // 임계영역에 접근 가능한 스레드 수수
volatile int guard = 0; // value에 대한 동기화 보장

void wait() {
    while(testAndSet(&guard) == 1);
    if(value == 0) {
        ... 접근한 현재 스레드를 큐에 넣음
    } else {
        value -= 1; // 임계영역에 접근 했으므로 -1
    }
    guard = 0;
}

void signal() {
    while(testAndSet(&guard) == 1);
    if(큐에 대기중인 스레드가 있으면) {
        ... 큐에서 스레드를 꺼내 임계영역에 진입
    } else {
        value += 1; // 임계영역에 접근 해제 했으므로 +1
    }
    guard = 0;
}

// 사용
wait();
...critical section...
signal();

// 순서 제어 사용
// thread1이 먼저 실행되어야 하는 경우
...thread1 work... // wait() 없이 실행
signal(); // thread1 종료

wait(); // thread2 대기
...thread2 work... // thread2 실행

semaphore 예시

task1가 끝나고 task3가 시작되어야 하는 경우

semaphore는 순서를 정하는데에도 사용용
- 위 그림처럼 P1에서는 wait() 없이 task1을 실행, signal() 실행행
- P2에서는 wait()를 하고 task3를 실행
- 멀티코어에서 각 P1과 P2가 동시에 실행될 때 항상 task1이 task3보다 먼저 실행됨
즉, semaphore의 wait()과 signal()이 각 다른 프로세스/스레드에서 실행될 수 있으며 이를 통하여 순서 제어 가능

mutex vs binary semaphore

mutex는 lock을 가진 스레드만 해제 가능
mutex는 priority inheritance 속성이 존재

priority inheritance란
High priority 프로세스(HPP)와 Low priority 프로세스(LPP)가 있을 때
LPP가 임계영역에 차지하고 있는 상황
HPP가 LPP가 임계영역을 빠져나올 때까지 대기 => HPP가 LPP의 의존성을 가짐
이 경우 LPP의 우선순위를 HPP만큼 높이는 것(mutex는 lock을 가진 프로세스만 해제 가능하므로)