동기화(Synchronization)

동기화의 목표는 스레드의 협업이 올바르게 운영된다는것을 보증하기 위함임.

 

Race Condition

공유 리소스에 스레드가 접근하게 된다면, Incorrect error 및 Reproducible이 발생한다.

실행 시기에 따라 다르지만,

MultiThreading - 실행은 CPU 스케줄러에 의해 interleaved 될 수 있음. (예측할 수 없는 요인)

MultiProcessor - 멀티프로세서 안에서의 실행 시기는 다양함. (프로세서가 얼마나 busy한지에 의존)

스레드 문제

- atomic 작업에서 공유 리소스에 접근하기 어려움.

- Atomic operation : 전체 또는 전혀 인터럽트가 불가능하다.

- 단일 연산자를 여러 개의 명령으로 컴파일 할 수 있음 ( ++ 연산자는 로드/추가/저장의 세가지 단계를 포함함)

- multi-word 작업이 원자성을 띈다는 보장을 할 수 없음.

 

Critical Resource

- 한 번에 최대 한 프로세스에서만 사용할 수 있는 리소스

- 프린터와 같은 리소스에 접근하기 위해선 두개 또는 그 이상의 프로세스가 요구된다고 가정함.

각 스레드에는 자체 스택과 CPU 레지스터의 복사본이 있음.

리소스 공유

- 정적 데이터, 힙 메모리, 파일 , IO장치와 같은 기타 리소스는 프로세스의 모든 스레드에서 공유됨.

- critical resource에 속하는 하드웨어에는 프린터와 테이프 드라이브가 있고, 소프트웨어에는 메세지 버퍼 대기열, 변수 , 배열 및 버퍼가 포함됨.

 

Critical Section & Mutual Exclusion ( 중요 섹션 및 상호 배제 )

Critical Section( or Critical Region)

- 중요한 리소스에 접근하는 코드 조각

- 공유된 변수 또는 데이터 구조를 점검

- 스레드가 동시에 엑세스할 수 있는지 여부를 검사

 

Mutual Exclusion(상호 배제)

- critical section에서 한 번에 하나의 스레드만 실행되도록 함.

- ciritical section을 상호 배타적으로 만듦.

 

동기화 용어

Process/thread synchronization - 공유 리소스 또는 실행을 사용하여 올바른 프로세스/스레드 조정 방법

Race Condition - 여러 프로세스/스레드가 동시에 공유 데이터에 접근하고, 조작하는 상황

Critical Section - 공유 리소스에 접근하는 코드 조각

Mutual Exclusion - critical section 안에서 동시에 하나의 프로세스/스레드만 존재해야 한다.

Condition Synchronization - 프로세스가 특정 작업이 발생할때 까지 대기하도록 허용.

 

Critical section의 문제점

크리티컬 섹션은 반드시 다음 세가지 조건을 만족해야 한다.

1. Mutual Exclusion (상호 배제)

- 만약 프로세스 P가 크리티컬 섹션 안에서 실행중이라면, 다른 프로세스들은 그 크리티컬 섹션 안에서 실행할 수 없다.

2. Progress (진행)

- 크리티컬 섹션에 실행 중인 프로세스가 없고, 해당 크리티컬 섹션에 진입하려는 일부 프로세스가 있는 경우 다음으로 크리티컬 섹션에 진입할 프로세스의 선택을 계속 미룰 수 없다.

3. Bounded Wating (한정 대기)

- 프로세스가 임계 섹션 진입 요청을 한 후, 다른 프로세스가 임계 섹션 진입을 허용하는 횟수에 제한 또는 제약이 있다.

 

Disabling Interrupts

- 가장 쉬운 해결책 중 하나로, 크리티컬 섹션에서의 인터럽트를 불가능 하게 만드는 것이다.

장점 : 간단하다.

단점 : 장시간 인터럽트를 차단하면, 인터럽트가 손실될 수 있음, 이러한 권한 있는 작업은 일부 악성 프로그램에 의해 악용될 수 있음, 이 접근 방식은 멀티프로세서에 적합할 수 없음.

 

HW Support

몇몇 시스템은 lock 메커니즘을 구현하기 위해 추가적은 명령을 제공함.

1. Test-And-Set operation (called TAS)

Test(load)와 Set(store)를 하나의 atomic 명령으로 만듦.

Test - old lock value를 체크한다.

Set - lock을 새 value로 설정한다.

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; // fetch old value
    *old_ptr = new; // store ‘new’ value
    return old; // return the old value
}

 

2. Compare And Swap 

Lock을 위한 또 다른 HW Primitive.

- 메모리 위치의 내용을 지정된 값과 비교하고, 동일한 경우에만 해당 메모리 위치의 내용을 새로운 지정된 값으로 수정함.

Test-And-Set과 유사한 lock 구현 방식.

int CompareAndSwap(int *ptr, int expected, int new) {
     int actual = *ptr; 
     if (actual == expected) 
     *ptr = new; // update the memory location
     return actual; // return the actual value
}

Spin lock

- Spin lock은 한 번에 하나의 스레드만 크리티컬 섹션에 들어갈 수 있도록 함. (상호 배제)

- 싱글 프로세서 사용 시 lock을 유지하는 스레드를 제외한 다른 모든 스레드는 spinning 동안 CPU 사이클을 낭비해야 함.

- 멀티 프로세서 사용 시 다른 프로세서에 lock이 될 때 까지 spinning을 대기하면 많은 사이클이 낭비되지 않음.

- 그러나 spin lock은 공평성을 보장하지 않기 때문에 starvation으로 이어질 수 있음.

 

Semaphore

동시 시스템에서 엑세스를 제어하는 보다 일반적인 동기화 방법.

세마포어 S - 정수 값을 가진 객체 ( value는 현재 사용 가능한 리소스의 단위 수 )

2개의 수정 표준 연산. semWait() / semSignal()

semWait() - value값 감소 연산

semSignal() - value값 증가 연산

 

- 오랜 대기 시간을 피하기 위해, 세마포어는 세마포어에서 대기중인 관련 프로세스 대기열을 사용할 수 있음.

- 세마포어를 사용하여 n-process 크리티컬 섹션의 문제점을 해결.

 

Binary Semaphore

- 정수 값은 lock의 사용을 위해 0과 1사이의 범위만 사용할 수 있음. ( 뮤텍스 lock 이라고도 함 )

Counting Semaphore

- 정수 값은 제한되지 않는 도메인에 걸쳐 있을 수 있음.