[Operating System] 동시성 제어 2
이전 포스팅에서 동시성 문제를 어떻게 해결할 수 있는가? 에 대한 소프트웨어적인 해결책에 대해 알아보았습니다. 이번 포스팅에서는 하드웨어의 Support 을 받아 동시성 문제를 해결하는 방법에 대해 알아봅시다.
먼저, 동시성 문제를 어떻게 해결할 수 있었는지 복습해봅시다. 동시성 문제의 해결책으로 두가지 방법이 있었습니다.
1. Critical Section 의 Code 를 실행할 때 Interrupt 를 Disable 해서 Atomic 하게 처리한다.
2. Critical Section 의 위/아래로 Entry Section/End Section 을 만들어 Critical Section 을 Fence 안에 두어 Mutual Exclusion 을 보장한다.
그리고 이 두가지 방법 중 2번째, Fence 를 만드는 방법이 더 우수한 방법이라 하였습니다. Critical Section 의 정의에 대해 다시 한 번 살펴봅시다.
- Critical Section : A section of code within a process that requires access to shared resources and that may not be executed while another process is in a corresponding section of code. Only one program at a time is allowed in its critical section.
이처럼 Critical Section 은 A Section of Code 입니다. 즉 유저 코드의 영역인데 Interrupt 를 강제로 disable 해버린다면 누군가 악의적인 코드를 넣는 순간 이것을 Interrupt 를 통해 막을 수 없는 보안 문제가 발생할 수 있습니다. 따라서 2번의 방식으로 구현하는 것이 좋습니다.
하지만 지난 포스팅의 결론에서 그랬듯이, 소프트웨어적인 방식으로 Fence 를 구현하는 것은 Busy Waiting 을 한다는 점, Overhead 가 너무 크다는 단점이 있었습니다. 이 문제를 하드웨어의 support 을 받아 해결할 수 있습니다.
하드웨어의 도움을 받아 동시성 문제를 해결하는 방법 1. Testset 이용
testset 함수를 살펴보면 알겠지만 굉장히 간단하다. i 는 binary 상태로 존재하고 previous 값과 반대의 값을 return 한다. 그리고 이 모든 과정은 atomic 하게 수행된다. 여기서 atomic 하게 수행할 수 있는 방법이 궁금해서 stdatomic.h 에 있는 test_and_set 을 찾아보았다.
https://en.cppreference.com/w/cpp/atomic/atomic_flag_test_and_set
std::atomic_flag_test_and_set, std::atomic_flag_test_and_set_explicit - cppreference.com
(1) (since C++11) (2) (since C++11) bool atomic_flag_test_and_set_explicit( volatile std::atomic_flag* p, std::memory_order order ) noexcept; Atomically changes the state of a std::atomic_flag poi
en.cppreference.com
atomic_flag 라는 타입의 변수를 사용하여 test_and_set 을 구현하는데 이 atomic_flag 라는 타입은 다음과 같은 특성을 가지고 있다고 한다.
std::atomic_flag does not provide load or store operations.
이전 포스팅에서 Producer/Consumer 문제에서도 LDA, STA 인스트럭션에서 문제가 발생했는데 이 변수는 오직 toggle 만 가능하다고 한다. 이것이 가능한 이유는 현대 CPU 는 아예 하드웨어 적으로 test_and_set 을 implement 하는 instruction 이 있다고 한다. 결국 문제가 되는 것이 shared resource 에 접근할 때인데, CPU 가 특정 메모리 주소에 저장된 atomic_flag 을 보고 test 를 거쳐 set 이 가능한지 안한지를 확인할 수 있는 것을 하드웨어적으로 지원을 하니까, Critical Section 에 대한 lock 이 지원이 되는 것 같다.
다시 본론으로 돌아와서 testset 함수로 Critical Section 을 보호하는 Fence 를 만드는 예제를 살펴보자
testset 함수를 while 로 감싼 Entry Section 으로 Fence 를 만들어 Critical Section 을 보호하고 있다. parbegin 함수를 통해서 Producer 쓰레드를 여러개 만들었는데, 어떤 쓰레드가 testset 으로 들어가 전역변수 bolt 점유하고 Critical Section 의 코드의 연산을 수행하고 있다면 다른 쓰레드는 testset 에서 bolt 를 점유하지 못해 critical section 으로 들어갈 수 없을 것이다. 즉 Mutual Exclusion 이 형성된다.
주의해야할 것은 이것은 Critical Section 을 Atomic 하게 수행하는 것이 아니라 testset 이라는 아주 짧은 함수만이 Atomic 하다. 따라서 아주 긴 유저코드가 될 수 있는 critical section 을 atomic 하게 수행하는 것과는 완전히 다르고 훨씬 유용하다.
다만 이렇게 testset 으로 구현한 fence 에도 단점이 있다. 일단 bolt 를 점유하지 못한 쓰레드는 while 문을 반복하다 다른 쓰레드로 CPU 자원을 넘겨주어야 한다. 즉, Busy Waiting 이 발생하여 CPU Utilization 이 낮아진다. 그리고 Bounded Waiting 을 만족시키지 못해 Starvation 과 Deadlock 도 발생할 수 있다. 하지만, Deadlock 의 경우 너무 드문 경우라 현대 OS 에서도 딱히 이것을 처리하지는 않는다고 한다. 알고리즘을 짜는 노력에 비해 효용이 별로 없나보다.
하드웨어의 도움을 받아 동시성 문제를 해결하는 방법 2. Semaphore 이용
testset 은 Bold 처리 안했는데, 세마포어에는 Bold 체로 처리했다. 왜냐면 끝판왕이기 때문이다. 결론부터 말하면 세마포어는 mutual exclusion 은 물론이고 bounded waiting, progress 까지 모두 충족하는 방법이다.
세마포어는 자바로 치면 클래스, C/C++ 로치면 구조체인데 정수값 하나와 Queue 를 가지고 있다.
세마포어는 다음과 같은 함수들로부터 호출된다.
세마포어의 동작은 testset 에서 bolt 를 쓰레드가 점유하는 것과 아주 유사하다. Semaphore 는 철도의 까치발 신호기 또는 해군의 수기 신호라는 뜻이다. 이게 중요한건 아니다.
위 함수 정의를 보면 알겠지만, semWait 은 testset 에서 bolt 를 점유하는 것과 유사하고 semSignal 은 testset 에서 bolt 를 release 하는 것과 유사하다. semWait과 semSignal 은 testset 과 마찬가지로 atomic 하게 수행된다.
이제, 세마포어를 사용하는 예제를 보자. Semaphore 는 정수값을 가지므로 1이 아닌 값을 가질 수도 있다. 하지만 1을 사용하면 아 이건 Mutual Exclusion 을 보장하려고 하는구나 예측할 수 있다.
구조가 testset 으로 fence 를 만들었던 것과 거의 유사하다. 하지만 결정적인 차이가 있다.
semWait 은 이미 critical section 에 들어가지 못하는 쓰레드는 바로 Wait Status 가 된다는 것이다. (Process-five state model 의 그 wait 이 맞다.) 즉, busy waiting 을 하지 않으므로 불필요한 CPU 낭비가 없다.
멀티 쓰레드 (혹은 멀티 프로세스) 에서 Semaphore 를 이용하여 Critical Section 을 보호하는 예시를 보자.
Semaphore 를 사용할 때는 semWait 의 호출횟수와 semSignal 의 호출횟수를 Pairing 시켜야한다. 그렇지 않으면 count 가 무한이 증가/감소하거나 적어도 제대로 동작하지 않을 것임을 예상할 수 있다.
세마포어의 또 다른 usage 로는 서로 다른 프로세스(혹은 쓰레드) 에 있는 코드의 실행 순서를 보장할 수 있다는 것이다. 다음의 예제를 살펴보자.
세마포어의 initial value 를 0 으로 주면 B in Pk 의 경우는 다음 Code 를 실행할 수가 없다. 오직 A in Pi 의 작업이 끝나고 semSignal(flag) 에 의해 semaphore 의 value 가 0이 되서야 B 가 실행될 수 있다. 이렇게 세마포어는 서로 다른 프로세스에 있는 Code 들의 실행 순서를 보장하는 방법으로도 사용할 수 있다. (같은 프로세스라면 어차피 순차적으로 실행될 것이니 세마포어가 필요가 없다.)
또 세마포어의 Special Case 로 Binary Semaphore 라는 것이 있는데 알아두면 좋을 것 같다.
