레이스와 동기화

레이스 (Race Conditions)

레이스 조건이란?

• 레이스 조건은 두 개 이상의 이벤트가 서로 의존하며, 일부 이벤트가 다양한 순서로 발생하거나 동시에 발생할 수 있는 상황을 의미합니다.
• 이벤트의 잘못된 순서가 존재할 수 있습니다.
• 예시:
  • 여러 번 업데이트되는 상태
  • 상태를 기반으로 생성되는 출력
• 업데이트의 순서가 잘못되어 잘못된 출력이 발생하는 경우가 레이스 조건입니다.

동기화 (Synchronization)

동기화의 개념

• 동기화는 프로그램 내에서 이벤트의 의도적인 순서를 설정하는 것입니다.
• 다양한 방식으로 작동하는 많은 동기화 메커니즘이 존재합니다.
• 동기화 메커니즘은 이벤트를 직접적으로 순서화하거나, 동시에 발생하지 않도록 보장할 수 있습니다.
• 동기화를 통해 레이스를 피할 수 있습니다.

데이터 레이스

데이터 레이스란?

• 데이터 레이스는 다음 조건이 모두 충족될 때 발생합니다:
  • 두 개 이상의 동시 실행 흐름이 공유 상태에 접근합니다.
  • 하나 이상의 흐름이 상태를 수정합니다.
  • 접근/수정의 순서가 중요합니다.
  • 사용 중인 동기화가 필요한 순서를 유지하기에 불충분합니다.

예시 레이스

예시 코드

• 두 개의 스레드가 다음 코드를 실행한다고 가정합니다:

void setstring(char **strings, char *s, int index) {
    if (strings[index] == NULL) {
        strings[index] = s;
        nstrings++;
    }
}

• 초기 상태: nstrings = 0, strings 배열은 모두 NULL
• 스레드 1과 스레드 2가 동시에 setstring(strings, "T1", 0) 및 setstring(strings, "T2", 0)를 실행할 때 발생할 수 있는 문제

단계별 실행

• 스레드 1과 스레드 2가 동시에 index 0을 확인하고, strings[0]이 NULL임을 확인합니다.
• 스레드 1과 스레드 2가 각각 "T1"과 "T2"를 strings[0]에 설정합니다.
• nstrings는 두 번 증가하여 nstrings = 2가 됩니다.
• 결과: strings[0]에는 "T1"이 남고 nstrings는 2가 됩니다. 이는 의도한 결과가 아닙니다.

임계 구역 (Critical Sections)

임계 구역이란?

• 임계 구역은 한 번에 하나의 제어 흐름만 접근할 수 있는 코드 영역입니다.
• 주로 공유 상태에 접근하는 코드를 포함합니다.
• 대부분의 경우, 공유 상태에 대한 쓰기는 임계 구역입니다.
• 읽기는 상태가 불변이거나 자주 변하지 않는 경우 임계 구역이 아닐 수 있습니다.
• 임계 구역을 신중하고 완전히 정의하는 것이 중요합니다.

진행 그래프 (Progress Graphs)

진행 그래프의 개념

• 진행 그래프는 동시 실행 흐름과 임계 구역을 모델링하는 도구입니다.
• 그래프의 각 차원은 동시 실행 흐름을 나타냅니다.
• 흐름이 진행됨에 따라 해당 차원에서 이동합니다.
• 임계 구역은 진행 그래프에서 n차원 영역으로 표시됩니다.

예시

• T1의 진행은 오른쪽으로 이동하고, T2의 진행은 위로 이동합니다.
• 프로그램 실행은 어떤 경로를 따릅니다.
• 임계 구역은 그래프에서 특정 영역으로 표시됩니다. 이 영역 내의 모든 점은 잘못된 실행을 나타냅니다.

동기화 방법1: 원자적 연산 (Atomic Operations)

원자적 연산이란?

• 한번 실행한 이상 반드시 실행을 끝내야하는. 아무도 간섭못해.
• 원자적 연산은 중단될 수 없으며, 다른 연산이 동시에 실행되지 않는 것처럼 보입니다.
• 항상 완전히 성공하거나 아무런 효과 없이 실패합니다.
• 모든 원자적 연산은 '하드웨어 지원'이 필요합니다. 모든 기계 명령이 원자적이지는 않습니다.

C 언어에서의 원자적 연산

• C는 보장된 원자적 연산을 '제공하지 않습니다.'
• C에서 동기화를 위한 원자적 연산은 다음을 필요로 할 수 있습니다:
  • 인라인 어셈블리 코드
  • 라이브러리 함수
  • 컴파일러 구현에 대한 지식
  • 커널 지원

동기화 방법2 :상호 배제 (Mutual Exclusion)

상호 배제의 개념

• 상호 배제는 하나의 논리적 제어 흐름만이 리소스에 접근하도록 보장하는 도구입니다.
• 임계 구역과 거의 직접적으로 매핑됩니다: 임계 구역의 코드는 리소스입니다.

뮤텍스 (Mutex)

• 상호 배제를 제공하는 소프트웨어 도구는 뮤텍스입니다.
• 뮤텍스는 두 가지 작업을 제공합니다:
  • 잠금 (Lock)
  • 잠금 해제 (Unlock)

뮤텍스 사용

• 일반적으로 뮤텍스는 임계 구역을 보호하기 위해 사용됩니다.
• 모든 동시 실행 흐름은 다음을 수행합니다:
  1. 뮤텍스를 잠급니다.
  2. 임계 구역을 실행합니다.
  3. 뮤텍스를 잠금 해제합니다.
• 이렇게 하면 한 번에 하나의 흐름만이 뮤텍스를 잠글 수 있어 임계 구역에서 상호 배제가 보장됩니다.

다음 학습 내용

• 세마포어 (Semaphores)

• 조건 변수 (Condition Variables)

• 교착 상태 (Deadlock)

• Progress Graphs로 ciritcal section 알아내기.

• critical section ㅇ