졍's 기술 블로그

0. 용어 정리

• Race Condition(경쟁 조건)
  : 여러 Process/Thread가 동시에 같은 Data를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황
• Synchronization(동기화)
  : 여러 Process/Thread를 동시에 실행해도 공유 Data의 일관성을 유지하는 것
• Critical Section(임계 영역)
  : 공유 Data의 일관성을 보장하기 위해 한 번에 하나의 Precess/Thread만 진입해 실행가능한 영역
• Mutual Exclusion(상호 배제)
  : 공유 Data의 일관성을 보장하기 위해 한 번에 하나의 Process/Thread만 진입해 실행할 수 있도록 하는 Algorithm

1. Mutual Exclusion을 보장할 수 있는 방법

: Lock을 사용한다.

// 실제 동작 Code가 아닌 개념 이해를 돕기위한 Code 입니다.

do{
	acquire lock // 여러 Process/Thread가 Lock을 획득하기 위해 경합
    	critical section // Lock을 획득한 단 하나의 Process/Thread만이 Critical Section에 들어가 실행
    release lock // Critical Section에서의 실행을 마치면 Critical Section을 빠져나오며 Lock 반환
    	reminder section
} while(TRUE)

Mutual Exclusion을 보장하는 상호 배제 기법으로는 Spin Lock, Mutex, Semaphore가 있다.

2. Spin Lock

: Lock을 획득할 수 있을 때까지 Lock 획득을 반복해서 시도하는 방식

☞ Lock을 획득하기 전까지 Lock이 다른 Process/Thread에 의해 선점되었는지 확인하는 것 자체가 CPU Cycle을 잡아먹는 일이기 때문에 CPU를 낭비한다.

Single Core, Multi Core에서의 Spin Lock

더보기

Single Core에서는 Spin Lock으로 Lock이 반환되기를 계속 기다리더라도 Lock을 획득하기 위해서는 이미 누군가 획득한 상태인 Lock을 반환해야하는데 이는 결국 Context Switching이 필요하다.
☞ Single Core에서의 Spin Lock은 이점이 없다.

Multi Core에서는 Spin Lock으로 Lock이 반환되기를 기다리다가 Thread 1이 Lock을 반환하자마자 Thread 2가 Lock을 획득하므로 Context Switching이 일어나지 않는다.

2.1. 동작 예제

// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.

volatile in lock = 0; // global -> 여러 Thread가 동시에 Lock에 접근 가능

// 여러 Thread가 호출할 함수
void critical(){
	
    while(test_and_set(&lock) == 1); // 여러 Thread가 while loop를 통해 Lock을 획득하려 시도
    ... critical section // Lock 획득에 성공한 하나의 Thread가 Critical Section에 들어와 실행
    lock = 0 // Critical Setcion에서 수행 완료 후 Lock 반환
    
}

// 실제 TestAndSet()의 동작 원리를 간단히 구현한 함수
// 공유되는 Lock에 대해 Lock의 원래 저장값을 반환하고 Lock 값은 1로 변경
int test_and_set(int* lockPtr){
	
    int oldLock = *lockPtr; // 원래 가지고 있던 Lock 값 가져오기
    *lockPtr = 1; // Lock 값을 1로 변경
    
    return oldLock; // 원래 가지고 있던 Lock 값을 반환
}

2.2. 동작 과정

Thread 1이 먼저 수행된 후 Thread 2가 수행되는 경우

1. Thread 1의 test_and_set()의 반환값 = 0 (원래 Lock은 0으로 초기화 되어있었기 때문) 이므로 while loop 탈출해 Critical Section에서 작업을 수행한다.

    ☞ test_and_set()을 호출했으므로 Lock은 1로 변경된다.

2. Thread 2의 test_and_set()의 반환값 = 1 (1번 과정에서 Thread 1에 의해 Lock이 1로 변경되었기 때문) 이므로 while loop에 갇힌다.

    ☞ test_and_set()을 호출했으므로 Lock은 계속 1로 갱신된다.

3. Thread 1이 Critical Section에서 작업을 마치고 Lock을 반환한다.

    ☞ Lock이 0이 된다.

4. Thread 1이 Lock을 반환함과 동시에 Thread 2의 test_and_set() 반환값 = 0 (3번 과정에서 Thread 1에 의해 Lock이 0으로 변경되었기 때문) 이 되므로 while loop 탈출해 Critical Section에서 작업을 수행한다.

    ☞ test_and_set()을 실행했기 때문에 Lock은 1로 변경된다.

5. Thread 2가 Critical Section에서 작업을 마치고 Lock을 반환한다.

    ☞ Lock이 0이 된다.

∴ test_and_set()을 통해 Thread 1과 Thread 2가 Critical Section 안에서 동시에 작업을 수행할 수 없다. (= 상호 배제)

TestAndSet()

Atomic 명령어의 특징

3. Mutex

: Lock이 다른 Process/Thread에 의해 획득된 상태라면 Lock이 반환될 때까지 Queue에서 대기하는 방식

☞ CPU Cycle을 불필요하게 낭비하는 것을 최소화한다.

3.1. 동작 예제

// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.
Class Mutex{
	int value = 1; // 이 값을 획득해야 Lock을 획득할 수 있다. (공유되는 Data)
    		       // value를 변경할 때 Critical Section 안에서 변경하지 않으면 Race Condition이 발생할 수 있다.
    int guard = 0; // Critical Section에 포함되어있는 value를 변경하기 위해 사용되는 변수
}

Mutex::lock(){
	while(test_and_set(&guard)); // value 값 변경 전 guard를 획득하기 위해 여러 Process/Thread가 경합
    
    // guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
    if (value == 0){ // 누군가 value를 이미 획득한 상태라면
    	현재 Thread를 Queue에 넣는다; // 작업을 잠시 멈추고 쉬고 있을테니 Lock이 풀리면 깨워달라며 Queue에 들어간다.
        guard = 0; & go to sleep // Process/Thread를 Queue에 넣고 guard 변경(guard 반환)
    }
    else{ // value를 획득할 수 있으면
    	value = 0; // value 획득하고 value를 0으로 갱신(value 획득한 상태를 표시)한다.
        guard = 0; // value 변경 후 guard 0으로 갱신(guard 반환)
    }

Mute::unlock(){
	while(test_and_set(&guard)); // value 변경 전 여러 Process/Thread가 guard를 획득하기 위해 경합
    
    // guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
    if (Queue에 하나라도 대기 중이라면){
    	그 중 하나를 깨운다;
    }
    else{ // 대기중인 Process/Thread가 하나도 없으면
    	value = 1; // value를 1로 갱신(value 반환)
    }
    guard = 0; // value 변경 혹은 Queue에서 Process/Thread 꺼낸 후 guard 0으로 갱신(guard 반환)
}

mutex -> lock(); // 여러 Process/Thread가 Lock을 획득하기 위해 경합
... critical section // Lock을 획득한 하나의 Process/Thread가 Critical Section에 들어가 작업 수행
mutex -> unlock(); // Critical Section에서 작업을 마친 후 Lock 반환

항상 Mutex가 Spin Lock보다 좋을까?

4. Semaphore

: Signal Mechanism을 가지는, 하나 이상의 Process/Thread가 Critical Section에 접근 가능하도록 하는 방법

4.1. 종류

• Binary Semaphore(이진 세마포어)
  : 한 번에 1개의 Process/Thread만 Critical Section에 접근할 수 있다.
  ☞ Mutual Exclusion을 보장한다.
• Counting Semaphore
  : 한 번에 value개의 Process/Thread만 Critical Section에 접근할 수 있다.

4.2. 동작 예제

// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.
Class Semaphore{

    // 한 번에 value개의 Process/Thread가 Critical Section에 접근할 수 있다.
    int value = 1; // value를 획득해야 Lock을 획득할 수 있다. (공유되는 Data)
    			   // value를 변경할 때 Critical Section 안에서 변경하지 않으면 Race Condition이 발생할 수 있다.
    int guard = 0; // Critical Section에 포함되어있는 value를 변경하기 위해 사용되는 변수
}

Semaphore::wait(){
	while(test_and_set(&guard)); // value 변경 전 guard를 획득하기 위해 여러 Process/Thread가 경합
    
    // guard를 취득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
    if (value == 0){ // 이미 누군가 value를 획득한 상태라면
    	현재 Process/Thread를 Queue에 넣는다; // Process/Thread가 일을 잠시 멈추고 쉬고 있을테니 Lock이 풀리면 깨워달라며 Queue에 들어간다.
        
        guard = 0; & go to sleep; // Process/Thread를 Queue에 넣은 후 guard 변경(guard 반환)
    }
    else{ // value를 획득할 수 있다면
    	value -= 1; // value 획득한 후 value를 1 감소(value 획득한 상태를 표시)
        guard = 0; // value 변경 후 guard 0으로 갱신(guard 반환)
    }
}

Semaphore::signal(){
	while(test_and_set(&guard)); // value 변경 전 guard 획득하기 위해 여러 Process/Thread가 경합
    
    // guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행
    if (Queue 안에 하나라도 대기 중이라면){
    	그 중에 하나를 깨워 준비시킨다;
    }
    else{ // 대기중인 Process/Thread가 하나도 없으면
    	value += 1; // value 1 증가(value 반환)
    }
    guard = 0; // value 변경 혹은 Queue에서 Process/Thread 꺼낸 후 guard 0으로 갱신(guard 반환)
}

Semaphore -> wait(); // 여러 Process/Thread가 Lock을 획득하기 위해 경합
... critical section // Lock을 획득한 하나의 Process/Thread가 Critical Section에 들어가 작업 수행
semaphore -> signal(); // Critical Section에서 작업을 마친 후 Lock 반환

Semaphore는 Process/Thread의 동작 순서를 정할 때도 사용할 수 있다.

더보기

Multi Core 환경에서 P1과 P2가 각각 Core를 할당받아 동시에 시작되는 경우

P1: task 1을 수행

P2: task 2를 수행한 후 task 3을 수행

 

Class Semaphore{
    int value = 0;
    int guard = 0;
}

P1이 task 1, P2가 task 2 수행이 동시에 진행되는 경우 task 1이 먼저 끝날지, task 2가 먼저 끝날지는 알 수 없지만 task 3은 task 1이 끝난 뒤에 수행된다는 것은 명확하다.

task 1이 먼저 끝나는 경우

1. P1이 task 1을 끝내고 signal() 호출함으로써 value = 1로 갱신

2. P2가 task 2를 끝내고 wait() 호출하면 value를 1 차감해 value는 0이 되고 wait() 반환되어 task 3 수행

 

task 2가 먼저 끝나는 경우

1. P2가 task 2를 끝내고 wait() 호출하지만 아직 value는 0이므로 자신을 Queue에 넣고 대기

2. P1이 task 1을 끝내고 signal() 호출하면 Queue에 들어있던 P2를 깨움

3. P2가 깨어나 task 3 수행

 

∴ signal()과 wait()가 같은 Process/Thread 안에서 실행될 필요가 없다.

5. Mutex와 Binary Semaphore의 차이점

Priority Inheritance

[참고]

https://youtu.be/gTkvX2Awj6g