동기화란

동기화의 의미

• 프로세스 동기화(synchronization)
  • 프로세스들 사이의 수행 시기를 맞추는 것
  • 동시다발적으로 실행되는 많은 프로세스는 서로 데이터를 주고받으며 협력하며 실행될 수 있음
    • 이들은 각기 독립적인 프로세스들이지만 공동의 목표를 위해 서로 협력하는 존재임
    • 협력적으로 실행되는 프로세스들은 아무렇게나 마구 동시에 실행되어서는 안 되며, 이를 위해 동기화가 필수임

프로세스들 사이의 수행 시기를 맞추는 것 즉, 프로세스 동기화란 크게 아래 두 가지를 일컫는다.

• 실행 순서 제어를 위한 동기화
  • 동시에 실행되는 프로세스를 올바른 순서대로 실행하는 것
• 상호 배제를 위한 동기화
  • 동시에 접근해서는 안 되는 자원에 동시에 접근하지 못하게 하는 것
  • 상호 배제(mutual exclusion) : 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

생산자와 소비자 문제

상호 배제를 위한 동기화와 관련된 고전적이고 유명한 문제로, 생산자와 소비자 문제가 있다.물건을 계속해서 생산하는 프로세스인 생산자와 물건을 계속해서 소비하는 프로세스인 소비자로 이루어져 있다.

#include <iostream>
#include <queue>
#include <thread>

void produce();
void consume();

int sum = 0;

int main() {

    std::cout << "초기 합계: " <<  sum << std::endl;
    std::thread producer(produce);
    std::thread consumer(consume);

    producer.join();
    consumer.join();
    
    std::cout << "producer, consumer 스레드 실행 이후 합계: " <<  sum << std::endl;
    
    return 0;
}

void produce() {
    for(int i = 0; i < 100000; i++) {
        sum++;
    }
}

void consume() {
    for(int i = 0; i < 100000; i++) {
        sum--;
    }
}

위 코드를 실행했을 때 결과는 아래와 같다.

초기 합계: 0
producer, consumer 스레드 실행 이후 합계: 63078

초기 합계: 0
producer, consumer 스레드 실행 이후 합계: -13750

매번 실행 결과가 다르게 나오는 것은 생산자 프로세스와 소비자 프로세스가 제대로 동기화되지 않았기 때문이다. 즉, 동시에 접근해서는 안 되는 자원에 동시에 접근했기에 발생한 문제다.

공유 자원과 임계 구역

• 공유 자원(shared resource)

  • 동시에 실행되는 프로세스들이 공동으로 사용하는 자원
  • 전역 변수, 파일, 입출력장치, 보조기억장치 등이 공유 자원이 될 수 있음

• 임계 구역(critical section)

  • 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
  • 먼저 진입한 프로세스의 작업이 마무리되면 그제서야 기다렸던 프로세스가 임계 구역에 진입해야 함

• 레이스 컨디션(race condition)

  • 병렬 프로그래밍에서 발생하는 문제로, 여러 프로세스 또는 스레드가 동시에 같은 자원을 수정하려고 할 때 예상치 못한 결과가 발생하는 상황
  • 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우
  • 데이터의 일관성이 깨짐

• 상호 배제를 위한 동기화

  • 레이스 컨디션과 같은 상황이 발생하지 않도록 두 개 이상의 프로세스가 임계 구역에 동시에 접근하지 못하도록 관리하는 것
  • 원칙
    • 상호 배제(mutual exclusion) : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없음
    • 진행(progress) : 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 함
    • 유한 대기(bonuded waiting) : 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 함 (임계 구역에 들어오기 위해 무한정 대기해서는 안 됨)

동기화 기법

뮤텍스 락

• 뮤텍스 락(Mutex lock; MUTual Exclusion Lock)
• 동시에 접근해서는 안 되는 자원에 동시에 접근하지 않도록 만드는 도구 즉, 상호 배제를 위한 동기화 도구
• 구현
  • 전역 변수 lock
    • 프로세스들이 공유하는 변수
    • lock이 true이면 프로세스가 자원을 사용 중이고, false이면 사용하지 않는 상태임
  • acquire 함수
    • 프로세스가 임계 구역에 진입하기 전에 호출하는 함수
    • 임계 구역이 잠겨있다면 lock이 false가 될 때까지 반복해서 확인 및 대기
    • 임계 구역이 열려 있다면 lock을 true로 바꿈
  • release 함수
    • 임계 구역에서의 작업이 끝나고 호출하는 함수
    • lock을 false로 바꿔줌
• 바쁜 대기(busy wait) : acquire 함수에서 lock 변수를 확인하는 작업을 반복해서 확인 및 대기하는 상태

세마포

• 세마포(semaphore)
• 철도 신호기에서 유래한 단어
• 공유 자원이 여러 개 있는 상황에서도 적용이 가능한 동기화 도구
  • 뮤텍스 락은 하나의 공유 자원에 접근하는 프로세스를 상정한 방식임
  • 공유 자원이 여러 개 있을 경우 여러 개의 프로세스가 각각 공유 자원에 접근이 가능해야 함
• 세마포에는 이진 세마포(binary semaphore)와 카운팅 세마포(counting semaphore)가 있지만, 이진 세마포는 뮤텍스 락과 비슷한 개념이므로 아래 내용은 카운팅 세마포에 관한 것임
• 구현
  • 전역 변수 S : 임계 구역에 진입할 수 있는 프로세스의 개수를 나타냄
  • wait 함수 : 임계 구역에 들어가도 좋은지, 기다려야 할지 알려주는 함수
  • signal 함수 : 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋다'고 신호를 주는 함수
• 바쁜 대기
  • 뮤텍스 락과 마찬가지로, 사용할 수 있는 공유 자원이 없는 경우 프로세스는 무작정 무한히 반복하며 S를 확인해야 함
  • CPU 주기를 낭비하므로 손해임
• 바쁜 대기 문제 방안
  • wait 함수
    • 만일 사용할 수 있는 자원이 없을 경우 해당 프로세스를 대기 상태로 만듦
    • 대기 상태의 프로세스 PCB를 세마포를 위한 대기 큐에 집어넣음
  • signal 함수
    • 대기 중인 프로세스를 대기 큐에서 제거
    • 프로세스 상태를 준비 상태로 변경한 뒤 준비 큐로 옮김

모니터

• 모니터(monitor)
• 세마포에 비해 사용자가 사용하기 훨씬 편리한 도구
• 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리함
  • 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근하도록 함
  • 모니터를 통해 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입하고, 큐에 삽입된 순서대로 하나씩 공유 자원을 이용하도록 함
• 조건 변수(condition variable)
  • 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수
  • 특정 조건을 바탕으로 프로세스를 실행하고 일시 중단하기 위해 사용
  • wait와 signal 연산을 수행할 수 있음
  • wait
    • 호출한 프로세스의 상태를 대기 상태로 전환하고 일시적으로 조건 변수에 대한 대기 큐에 삽입하는 연산
    • 상호 배제를 위한 큐 : 모니터에 한 번에 하나의 프로세스만 진입하도록 하기 위해 만들어진 큐
    • 조건 변수에 대한 큐 : 모니터에 이미 진입한 프로세스의 실행 조건이 만족될 때까지 잠시 실행이 중단되어 기다리기 위해 만들어진 큐
  • signal
    • wait를 호출하여 큐에 삽입된 프로세스의 실행을 재개하는 연산
  • 특정 프로세스가 아직 실행될 조건이 되지 않았을 때 : wait를 통해 실행을 중단
  • 특정 프로세스가 실행될 조건이 충족되었을 때 : signal을 통해 실행을 재개

Q&A

레이스 컨디션(race condition)이 발생하는 이유와 그로 인해 발생하는 문제 (Ch12-1)

레이스 컨디션 (Race Condition)은 병렬 프로그래밍에서 발생하는 문제로, 여러 프로세스 또는 스레드가 동시에 같은 자원을 수정하려고 할 때 예상치 못한 결과가 발생하는 상황이다. 이로 인해 다음과 같은 문제가 발생할 수 있다.

데이터 불일치 (Data Inconsistency)

여러 스레드가 동시에 같은 변수를 수정하는 경우, 변수의 값이 일관성 없이 변경될 수 있다. 예를 들어 은행 계좌 잔액을 동시에 감소시키는 경우, 잔액이 정확하지 않게 갱신될 수 있다.

쓰기-읽기 충돌 (Write-Read Conflict)

하나의 스레드가 데이터를 수정하는 동안 다른 스레드가 같은 데이터를 읽으려고 할 때 충돌이 발생합니다. 이로 인해 잘못된 데이터를 읽을 수 있다.

쓰기-쓰기 충돌 (Write-Write Conflict)

두 개 이상의 스레드가 동시에 같은 데이터를 수정하려고 할 때 충돌이 발생한다. 이로 인해 데이터가 무효화될 수 있다.

교착 상태 (Deadlock)

두 개 이상의 스레드가 서로의 작업이 끝나기를 기다리며 멈춰있는 상태다. 데드락이 발생하면 프로그램이 더 이상 진행되지 않는다. 교착 상태가 발생할 수 있는 조건은 다음과 같다.

1. 상호 배제

레이스 컨디션의 문제를 해결하고자 상호 배제 조건을 두어 동시에 공유 자원에 접근할 수 없도록 하여 한 자원에 한 스레드만 접근 할 수 있게 하는 것을 의미한다.

스레드가 자원을 독점적으로 사용하고 있어 다른 스레드가 자원에 접근하려고 락을 획득하기 위해 무한 대기할 수 있는 상황이 발생할 수 있다.

2. 점유 상태로 대기

공유 자원에 락을 획득하여 점유하고 있는 상태인데 다른 자원의 락을 획득하기 위해 대기하고 있는 상황을 의미한다.

조금 더 이해하기 쉽게 풀어서 말해본다면, 발생할 수 있는 상황이 여러 개의 자원을 동시에 써야하는 경우 락을 획득한 자원에 대한 처리는 끝났는데 남은 자원의 락을 다른 스레드가 가지고 해제를 하지 않아 무한정 대기하는 상태다.

또한 자신이 점유하고 있는 락도 해제를 해주어야 그 락을 획득하기 위해 대기하고 있는 다른 스레드들도 자원에 접근하여 처리를 할 수 있는데 락을 획득할 수 없어 다른 스레드 마저 무한정 대기할 수 밖에 없는 상황이 발생한다.

3. 선점 불가

다른 스레드가 자원을 선점하고 있어서 자원을 뺏어올 방법이 없는 것을 의미한다. 만일 어느 스레드가 공유 자원의 락을 획득하여 선점하고 있다면 그 공유 자원에 접근해야 하는 다른 스레드들은 아무리 잠깐 처리하면 끝나는 상황이라도 락을 빼앗을 방법이 없기 때문에 무한 대기할 상황이 발생할 수 있다.

4. 순환성 대기

프로세스가 어느 자원을 점유하고 있고 다른 자원을 요청하여 대기하고 있는데 순환적인 구조를 가지는 경우를 순환성 대기라고 한다.

즉, 점유 상태로 대기가 순환적으로 발생한 상황으로 볼 수 있다. 락을 해제하고 락을 획득하는게 순차적으로 잘 돌아가면 좋겠지만, 어느 순간 모든 프로세스가 락을 획득하려고 대기하여 모든 프로세스가 무한 대기에 놓인 상황이 발생할 수 있다.

레이스 컨디션 공격

리눅스 환경에서 레이스 컨디션 상태를 이용해 root 권한을 얻어내는 공격 방식이다.

사용자가 프로그램을 실행했을 때 SETUID를 통한 권한 상승으로 관리자 권한의 임시 파일이 생성된다. 공격자는 이 임시 파일의 이름을 파악해놓고, 임시 파일이 생성되면 이 파일의 심볼릭 링크를 생성한다.

다음 프로그램 실행 시 기존의 임시 파일이 삭제되고 재생성되면 공격자는 심볼릭 링크를 이용해 파일의 내용을 변경한다. 이후 시스템은 변경된 파일을 자신이 생성한 임시 파일이라 인식해 프로세스를 진행시키고, 공격자는 관리자 권한으로 실행되는 프로그램에서 자신이 원하는 동작을 실행할 수 있게 된다.

이를 위한 필요조건은 다음과 같다.
1. 공격자는 생성되는 임시 파일의 이름을 사전에 알고 있어야 한다.
2. 파일의 소유자가 root이며 SETUID 비트를 가져야 한다.

참고

• [OS] 스레드 동기화 문제
• 레이스 컨디션 그게 뭐야?
• [시스템해킹] 레이스 컨디션 공격 기법 (Race Condition)
• 레이스 컨디션(Race Condition) 공격