[운영체제] Process Synchronization (2) - test_and_set () & compare_and_swap ()

바로 앞의 글에서 확인할 수 있듯이 Peterson's Solution과 같이 코드적으로 완벽해보이는 소프트웨어적인 알고리즘들도 결국 컴파일러의 동작 순서 등의 이유와 맞물려 예상치 못하게 잘 못 동작할 수 있다는 것을 알 수 있었습니다. 사실 프로세서가 하나 뿐인 시스템 (single-processor system)에서는 어떤 공유 변수가 변경되는 동안은 interrupt 발생을 허용하지 않는 방법을 사용하여 쉽게 처리할 수 있기는 합니다. CPU 스케쥴링을 멈춤으로써 아예 Race condition 문제를 발생하지 않게 하는 것입니다.

 

하지만 이것은 multiprocessor system에서는 사용이 불가능하며, 또 실시간 처리가 필요한 시스템에서는 사용이 불가능합니다. Multiprocessor system에서 모든 프로세서에게 지금은 interrupt를 사용할 수 없다고 메세지를 보내는 것은 굉장히 많은 시간을 필요로 하기 때문입니다. 

 

이러한 이유 때문에 특별한 하드웨어 instruction을 이용하여 이 문제를 해결합니다. 오늘은 이 하드웨어 insturction에 대해서 알아보도록 하겠습니다.

 

1. Synchronization Hardware (동기화 하드웨어)

앞에서도 말했듯이 소프트웨어적으로 Race condition을 해결하는 것에는 명확한 한계점이 존재합니다. 그래서 원자적인 (atomic) 명령어를 지원합니다. 바로 test_and_set (TS)와 compare_and_swap (CAS)라는 instruction들 입니다. 이 명령어들은 말 그대로 원자적인 명령어입니다. 원자적이란 말은 더 이상 나눌 수 없다는 뜻이죠. 우리가 생각하듯이 코드로 구현되어 있는 것이 아니고 정말 말 그대로 하나의 명령어로 수행이 되게 됩니다. 만일 두 개의 CPU들이 test_and_set이나 compare_and_swap을 각각 동시에 실행하여 같은 메모리 주소의 값을 변경하게 되면, 하드웨어는 알아서 하나의 CPU만 실행을 하도록 허용해 줍니다. 

 

test_and_set 명령어는 다음과 같이 정의됩니다.

 

앞에서도 말했듯이 실제로 이렇게 구현이 되어 있는 것은 아닙니다. 마치 CPU가 add 연산을 실행하듯이 하나의 명령어를 실행하는 것 뿐이고 굳이 이것을 소프트웨어적으로 표현하자면 위의 식 처럼 표현이 된다는 것입니다. 

 

비슷한 원리로 compare_and_swap은 다음과 같이 정의됩니다.

 

compare_and_swap은 test_and_set의 확장된 버전이라고 할 수 있겠습니다. 이들에 대해 조금 더 자세하게 알아보겠습니다.

 

2. test_and_set ( )

test_and_set은 말 그대로 lock의 값이 true인지 false인지 확인해 보고 true이면 누군가 Critical Section에 들어가 있다는 뜻이므로 false를 리턴해주고 lock의 값이 false면 lock의 값을 true로 바꾼 뒤에 true를 리턴해주는 명령어입니다. test_and_set을 소프트웨어적으로 구현해보면 다음과 같이 코드를 작성해 볼 수 있습니다.

 

그런데 이렇게 소프트웨어적으로 구현하여 함수를 호출하는 식으로 사용하면 만일 어떤 프로세스가 lock = true;까지 실행하고 context switching을 당하는 경우가 발생할 수 있습니다. 이러한 경우에 lock이 true가 된 상태여서 아무도 Critical section에 접근할 수 없기 때문에 다른 프로세스들이 Critical section을 실행하지 못하는 문제가 생기게 됩니다. 

 

test_and_set() 명령어는 다음과 같이 사용될 수 있습니다. 

 

아마 test_and_set의 작동 원리를 올바르게 이해하셨다면 위의 예시도 쉽게 이해할 수 있을 것이라고 생각합니다.

 

3. compare_and_swap ( )

compare_and_swap 명령어는 우선 세 개의 피연산자를 인자로 전달받기 때문에, test_and_set 보다는 조금 복잡한 형태를 가집니다. 세 개의 인자 중 첫번째 인자인 *value는 lock의 현재 상태를 뜻하며, 0이면 현재 아무도 Critical section에 들어가 있지 않다는 뜻이고, 1이면 현재 사용이 불가능하다는 뜻입니다. expected 값은 말 그대로 기대하는 값으로 당연히 들어가기를 기대하기 때문에 0을 일반적으로 사용하겠죠? new_value는 내가 Critical section에 들어가면 lock의 값을 바꿔줄 값이기 때문에 1을 인자로 넣어줍니다. 사용의 예시는 다음과 같습니다.

 

그러면 lock의 값에 따라 0이면 lock의 값을 new_value인 1로 바꿔주고 0을 리턴해주기 때문에 while문을 탈출할 수 있고, lock의 값이 1이라면 그대로 원래 lock 값인 1을 리턴해 주는 형태입니다.

 

4. 문제점

하지만 이 test_and_set과 compare_and_swap을 이용하는 것은 또 한가지 문제점이 존재합니다. 이는 앞에서 알아봤던 세 가지의 조건, Mutual exclusion, Progress, Bounded waiting 중 Bounded waiting을 만족하지 않는다는 것입니다. lock이라는 변수를 여러 Process가 공유하며 경쟁하므로 Bounded waiting을 만족하지 못하는 상황이 발생할 수 있습니다. 즉 얼마나 오랜 시간을 기다렸는지와는 전혀 상관없이 while문을 계속 돌며 경쟁적으로 lock을 가지려고 하기 때문입니다.

 

물론 waiting[] 과 같은 배열을 사용하여 Bounded waiting 문제를 해결하도록 구현할 수 있지만 이러한 해결책은 복잡할 뿐 아니라 하나의 instruction으로 구현되기 때문에 응용 프로그래머는 사용할 수가 없습니다. 이러한 점을 해결하기 위해 등장한 방법들이 또 존재하는데 이 부분들에 대해서는 다음 글에서 알아보도록 하겠습니다.

 

 

 

 

 

읽어주셔서 감사합니다.