[운영체제/OS] 동기화 문제 - test_and_set(), TAS

test_and_set()은 원자성을 보장하는 명령어이다

 

세마포어의 wait(), signal() 연산이 원자성을 보장해야 한다는 것을 지난 포스팅에 언급했다.

(https://highlaw00-dev.tistory.com/63)

 

싱글 프로세서 환경에서는 단순히 인터럽트를 방지하면 됐지만 멀티 프로세서 환경에서는 모든 코어의 인터럽트를 방지하는 것이 매우 비효율적이기 때문에 test_and_set() 명령어 혹은 compare_and_swap() 명령어 혹은 스핀락을 통해 해결해야 한다.

 

싱글 프로세서 환경

 

싱글 프로세서 환경에서 단순히 인터럽트만 방지하였을 때 wait(), signal() 연산이 원자성을 보장받는다. (그림 참조)

서울대학교 홍성수 교수 - 운영체제의 기초 강의 자료

 

 

멀티 프로세서 환경

 

만약, 멀티 프로세서 환경에서 wait(), signal()을 수행할 때 원자성을 보장하기 위해 해당 명령을 수행한 프로세서의 코어만 인터럽트 방지를 수행한다면 어떻게 될까?

 

해당 코어에서는 인터럽트가 방지되어 다른 프로세스가 원자성을 해치지 않겠지만, 다른 코어에서 동작하는 프로세스가 원자성을 해칠 가능성이 존재한다.

 

이를 해결하기 위해 공유 리소스를 읽고 수정하고 갱신하는 연산을 atomic하게 지원하는 명령어를 사용한다.

 

서울대학교 홍성수 교수 - 운영체제의 기초 강의 자료

 

리소스를 읽고 수정하고 갱신하는 연산을 test_and_set()이라고 한다. test_and_set()이 어떻게 atomic한 연산을 지원할까? 그 비밀은 컴퓨터 구조에 있다.

 

CPU에서 메모리에 존재하는 리소스를 읽고 쓰기 위해선 버스를 통해 명령을 주고 받아야 한다. 이 원리를 이용해 test_and_set() 명령이 수행될 때 버스를 lock 하여 다른 프로세스가 잠시 접근하지 못하도록 한다.

 

test_and_set()의 구현

// 이 함수가 atomic하게 동작하는 것을 하드웨어 계층에서 보장한다!!

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true; // target을 true로 변환
    
    return rv; // 기존 값 반환
}

 

test_and_set() 함수는 초기값이 false인 target을 매개변수로 하는 함수다. target의 값을 true로 바꾸고, 기존 target의 값을 그대로 반환한다. 

 

test_and_set()을 활용해 Mutual exclusion을 구현하면 다음과 같아진다!

 

do {
    while (test_and_set(&lock));
    // do nothing ...
    
    /* critical section */
    
    lock = false;
    // lock을 해제해준다.
    
    /* remainder section */
} while (true);

 

위 코드를 수행하는 프로세스 2개가 있다고 가정해보면 다음과 같이 동작한다.

 

스레드1
- lock: false임으로 while 루프 통과 후 임계 구역 진입
- test_and_set()이 atomic하기 때문에 중간에 문맥 교환이 일어나 경쟁 상황이 되지 않는다.

스레드 2
- 스레드1이 lock을 true로 만들었기 때문에 while 루프를 계속 반복하게 된다.

스레드 1
- 임계 구역에서 빠져나와 lock을 false로 변경해준다.

스레드 2
- busy waiting 하던 중 lock이 false로 변경되어 while 루프를 빠져나온다.

 

 

세마포어에 적용하기

 

tas 명령어로 세마포어의 wait()과 signal()을 atomic하게 구현해보자.

 

wait()

wait(semaphore *S) {
    disableInterrupts(); // 같은 프로세서 내에서 인터럽트가 발생하지 않게 방지한다.
    while (test_and_set(&lock)) continue; // lock 여부를 확인한다.
    S->value--;
    enableInterrupts(); // 인터럽트 허용
    
    // 리소스가 없다면 대기
    if (S->value < 0) {
        add this process to S->list; // list에 현재 프로세스 삽입
        sleep(); // 현재 프로세스 대기
    }
}

 

signal()

signal(semaphore *S) {
    disableInterrupts(); // 인터럽트 금지
    while (test_and_set(&lock)) continue; // lock 여부를 확인한다.
    S->value++;
    lock = false; // lock 해제
    enableInterrupts(); // 인터럽트 허용
    
    // 대기 프로세스가 있으면 wake
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

 

임계구역 전체 코드

 

변경된 wait() 와 signal()을 사용하여 임계구역을 구현해보면 다음과 같아진다.

 

while (true) {
    // init section
    
    
    /* entry section */
    wait(semaphore);
    
    /* critical section */
    
    /* leaving section */
    signal(semaphore);
    
    
    // remainder section
}