[ 운영체제 ] 동기화 방법2 - TestAndSet(), Mutex Locks

저번 시간에는 피터슨 방법에 대해 다뤘었다. 피터슨 방법의 단점 및 문제점을 다시 한번 살펴보자.

 

1. 소프트웨어적 방법 - 속도가 느리다
2. 프로세스가 두 개인 경우에만 적용 가능
3. 자원을 많이 소모한다(Busy Waiting)
4. 현대 컴퓨터에서 정상 작동 하지 않음

 

이번에 소개하는 방법은 피터슨 방법에서 Busy Waiting을 제외한 나머지 단점들을 보완한 방법이다. 소프트웨어적인 방법으로 경쟁 상태를 해결하는 것은 컴퓨터 구조적으로 문제가 발생할 수 있기 때문에 이번에는 하드웨어적인 방법으로 접근한다. 하드웨어적 방법은 원자적 실행 단위를 보장하므로 코드의 순서가 바뀌거나 하는 일은 없다. 

Synchronization Hardware: TestAndSet()

TestAndSet()은 하드웨어적으로 구현되었기 때문에 하나의 명령어로 취급해도 된다. 제목과 같이 동기화 하드웨어고 임계구역의 세 가지 조건 중 상호배제를 만족하는 명령어다. 소프트웨어적으로 풀면 동작 원리는 아래와 같다. 

 

boolean TestAndSet(boolean *target){
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

 

다시 한번 말하지만 위 코드는 하드웨어적으로 구현되어 있다. 다만 소프트웨어적으로 풀어 쓴 것일 뿐이다. 이제 target 값으로 FALSE, TRUE를 받았을 때 어떻게 되는지 살펴보자. 

 

• target = FALSE :  target = TRUE, 반환값은 FALSE
• target = TRUE :  target = TRUE, 반환값은 TRUE

TestAndSet()은 입력값의 상태를 그대로 반환하고, 입력값은 항상 TRUE로 갱신하는 함수로 정리할 수 있다. TestAndSet() 명령어는 아래와 같이 사용된다. lock은 전역 변수다.

 

do{
    while(TestAndSet(&lock)); // do nothing (진입 구역)
    
    CRITICAL SECTION
    
    lock = FALSE; // 퇴출 구역
    
    REMAINDER SECTION
    
} while(TRUE);

 

lock = FALSE 인 경우만 진입 가능하고, 퇴출 구역에서 lock = FALSE 로 갱신해줘야 다른 프로세스가 진입할 수 있다. lock을 획득한 하나의 프로세스만 임계구역에 진입할 수 있다는 점에서 Mutual Exclusive를 만족하고, 퇴출 구역에서 lock을 다시 FALSE로 바꿔준다는 점에서 Progress를 만족한다. 

 

그런데 TestAndSet()만 사용하면 한 가지 문제가 있다. 바로 임계구역의 세 가지 요구사항 중 Bounded Waiting을 만족하지 않는다는 것이다. 그 이유는 프로세스의 도착 순서와 무관하게 임계 구역에 진입할 프로세스가 정해지기 때문이다. 즉, fair 하지 않다! 그렇다면 프로세스의 도착 순서를 고려해준다면? fair하기 때문에 임계구역의 세 가지 조건을 모두 만족하므로 유효한 알고리즘이 된다. Bounded Waiting 조건을 만족시켜주기 위해서는  아래와 같이 코드를 수정하면 된다. 

 

boolean waiting[n]; 
boolean lock;

do{
    waiting[i] = true; // i번째 프로세스가 진입 요청
    key = true; 
    while(waiting[i] && key)
    	key = TestAndSet(&lock); // key = false, lock = true
    waiting[i] = false;
    
    CRITICAL SECTION
    
    j = (i + 1) % n; // j 값으로 자신(i)의 다음 프로세스 값을 선정
    while((j != i) && !waiting[j])
    	j = (j + 1) % n; // 다음 프로세의 존재 탐색
        
    if(j == i) // 기다리는 애가 없어서 다시 자기 차례
    	lock = false;
    else // 가디라는 애가 있기 때문에 진입 구역의 while문 탈출할 수 있게 한다
    	waiting[j] = false;
        
    REMAINDER SECTION
    
} while(1);

 

그런데 이 방법은... 복잡하고 어렵워 보통의 프로그래머는 사용하기 힘들어서 소프트웨어 tool인 Mutex Locks이 만들어졌다. Mutex Locks는 API 형태로 제공된다.

Mutex Locks

이 알고리즘은 acquire()와 release() 함수를 사용하며 available이라는 boolean 변수로 lock의 잠금 여부를 확인할 수 있다. 이 두 함수 또한 하드웨어적으로 구현되어 있으며 원자적으로 실행된다. acquire() 과 release() 함수 형태는 아래와 같다.

 

mutex -> available = 0

void acquire(lock *mutex){
    while(test_and_set(&mutex -> available) != 0); // busy wait
    // available = True, 반환값은 False
    
    return;
}

void release(lock *mutex){
    mutex -> available = 0;
    // available = 0 으로 바꿔줘야 acquire에서 while문 탈출 가능
    
    return;
}


do{
    acquire lock 
    
    CRITICAL SECTION
    
    release lock
    
    REMAINDER SECTION
    
} while(true);

 

 

Mutex Locks는 여전히 busy waiting(spin lock)의 문제점을 가지고 있다. 즉, 쓸데없이 CPU를 점유하고 있는 경우가 발생해 자원을 낭비하게 된다. 이를 해결하기 위해서는 busy waiting 하는 프로세스를 강제로 wait state로 보내면 된다. 이 아이디어가 바로 세마포어다. 다음 시간에는 세마포어를 알아보자.