동기화 문제를 해결하는 법
이번 포스팅에서는 동기화 문제, 즉 임계영역에 쓰레드 또는 프로세스가 동시에 접근할 경우 이를 해결하는 방법론에 대해서 알아보겠습니다.
우선 본격적으로 들어가기전에 Lock과 Mutex와의 관계에 대해 정리해보겠습니다.사실상 이 둘은 같은 개념이라고 보셔도 되고,이러한 Lock(Mutex)를 구현하는 방법 중 두가지를 소개시켜 드리겠습니다.
Lock 구현 1)Spin-Lock 방식(Busy-Waiting)
우선 간단한 의사코드를 통해 Lock의 동작 방식을 알아봅니다.
volatile int lock = 0;//global
void critical(){
while(test_and_set(&lock) == 1);
...critical section
lock = 0;
}
int test_and_set(int* lockPtr){
int oldLock = *lockPtr;
*lockPtr = 1;
return oldLock;
}
우선 글로변 변수로 lock을 선언을 한뒤, 임계영역에 접근하려는 쓰레드들은 critical()이라는 함수를 호출하여 lock을 획득한 뒤 진입해야합니다.
예를 들어 T1이라는 쓰레드가 lock변수가 0일 때,critical()함수를 호출합니다.
그러면 현재 상태의 현재의 lock값은 0이기 때문에 test_and_set() 함수의 반환값은 0이 될것이고 이는 While문을 탈출하는 조건이기에 T1은 무난하게 임계영역에 진입할 수 있습니다.이후 T2라는 쓰레드가 임계영역에 접근하기 위해 critical()함수를 호출합니다.하지만 이전 경우와 달리 전역변수인 lock의 값은 이미 1로 변경 되어있어서test_and_set()의 반환값이 1이므로 while을 탈출하지 못하고 계속 무한 반복을 진행합니다.이러던 와중 임계영역에서의 로직을 끝낸 T1이 lock값을 다시 0으로 변경 시키면 T2 쓰레드는 while문을 탈출할수 있고 임계영역에서의 작업을 시작합니다.
우선 위와 같이 Lock을 끊임없이 기다려면서 while문을 끝없이 돌리는 방식을 Lock-Spin방식이라고 합니다.이 방식 또한 동기화 문제를 해결할 수는 있지만 while문의 명령어를 CPU에게 기약없이 실행시키기에 비효율적이라는 큰 단점이 있습니다.
마지막으로 위와 같은 방식의 코드가 멀티 프로세서에서는 정상적을 작동할지 한번 생각해보겠습니다.주어진 코드만 본다는 가정하에서 T1과 T2가 각각 서로다른 코어에 들어가서 critical()함수를 호출합니다.그러면 어떤 쓰레드가 while문을 먼저 탈출하고 임계영역에서 작업을 진행할 수 있을까요? 코드만 본다면 도저히 답이 나오질 않습니다.
이러한 문제는 사실 이미 해결되어진 채로 위의 Lock-spin 방식은 작동합니다.즉,하드웨어의 도움을 받아 이를 해결합니다.CPU가 test_and_set()이라는 함수를 관리를 하고,이 함수를 동시에 접근하는 경우가 발생하면 함수가 원자적으로(하나하나씩) 실행될 수 있게 처리해줍니다.
추가적으로 위와 같은 스핀락 방식을 사용하려면 OS는 선점형 스케쥴러를 사용해야합니다.만약 비선점형을 사용하게 될 경우,Lock을 얻기 위해 CPU를 무한정 사용할수 있기 때문입니다.
Lock 구현2)Sleep-Wake 방식
스핀락의 근본적인 단점을 생각해보자면 Lock을 얻는 시점이 운에 맡겨진다는것입니다.즉, Lock을 얻으려는 쓰레드가 CPU를 점유한채로 while문을 돌다가 스케쥴러에 의해 yield되면 또 다음번 실행까지 기다려야하고, 심지어 다음번 실행에서도 Lock이 사용가능한지 아닌지에 대해 알수 없습니다.
이러한 비효율을 개선하기 위해 생긴 아이디어가 바로 스핀 대신 잠자기(block)을 사용하는 방식입니다.
간단한 코드로 이를 알아봅시다.다만 해당 코드는 Lock이라는 표현 대신 Mutex라는 이름으로 구조체를 사용했습니다.
typedef struct mutex_type{
int value;
int guard;
queue_t *q;
}mutex;
void mutex_init(mutex *m){
m->value = 1;
m->guard = 0;
queue_init(m->q);
}
void lock(mutex *m){
while(test_and_set(&m->guard) == 1);
if(m->value == 0){
//현재 스레드를 큐에 넣음
queue_add(m->q,gettid());
m->guard = 0;
}else{
value = 0;
m->guard = 0;
}
}
void unlock(mutex *m){
while(test_and_set(&m->guard) == 1);
if(queue_empty(m->q)){
m->value = 1;
}else{
//큐에서 대기하는 특정 쓰레드를 하나 깨움
}
m->guard = 0;
}
스핀락과 비교하여 크게 달라진점은 없습니다.다만,value라는 공유변수에 접근하기 위해서는 필요한 장치인 guard가 존재합니다.즉,value라는 임계영역을 보호하는 장치라고 생각하셔도 됩니다.
위와 마찬가지로 예를 들어 설명하겠습니다.
T1이라는 쓰레드가 가장 첫번째로 임계영역에 접근하려 합니다.즉,mutex라는 구조체는init이 된 상태입니다.즉,guard와 value가 각각 0과 1인 상태입니다.여기서 lock()함수를 호출을 하면 guard값이 0이기 때문에 while문을 탈출하고 value에 접근할 수 있는 권한이 생깁니다.이후 value값이 1이기 때문에 T1 쓰레드는 임계영역에 진입하여 로직을 수행할 수 있습니다.곧 이어 T2라는 쓰레드가 해당 임계영역에 동일하게 접근합니다.다만,이때는 mutex 구조체의 value값이 0이기 때문에 T2 쓰레드는 큐에 들어가게 됩니다.즉,대기하는 큐에서 Lock의 value값이 1이되어 자신을 깨울때까지 기다리는것입니다.
뮤텍스가 스핀락보다 무조건 좋을까?
만약 싱글 코어의 상황이라고 가정해봅시다.뮤텍스의 경우 기본적으로 락을 얻으려는 쓰레드가 block 상태로 변경되는기에 항상 context-switching이 발생합니다.그리고 스핀락의 경우에도 선점형 스케쥴러를 이용해서 while문을 돌고 있는 스레드와 대기하는 스레드간의 컨텍스트 스위칭이 일어나야하기에 둘 다 비슷한 상황에 놓여있다고 볼 수 있습니다.
다만 멀티 코어환경에서는 임계영역에서의 작업이 컨텍스트 스위칭보다 더 빨리 끝난다면 스핀락이 뮤텍스보다 더욱 유리합니다.
예를 들어 설명해보겠습니다.스핀락을 사용하는 환경에서 코어 1에는 락을 가진 스레드가 돌아가고 있고,코어2에는 해당 락을 기다리는 스레드가 돌아간다고 가정합시다.이러한 경우에는 코어1의 스레드의 임계영역에서의 작업이 컨테스트 스위칭보다 빨리 끝나면 스핀락을 사용하는 방식이 더 유리합니다.
Semaphore(세마포어)
세마포어의 경우 앞서 말씀드린 Lock과는 조금은 다른 패러다임을 가지고 있습니다.이들의 목적은 Mutual Exclusion이 아닌 공유 자원에 대한 관리입니다.사실 방금 전의 문장이 이 둘을 이해하는것에 있어 가장 중요한 부분입니다.차근차근 세마포어에 대해 알아봅시다.
우선 sema_down()과 sema_up()함수에 대해 먼저 설명드리겠습니다.간단히 설명하면 각각 Lock의 lock()과 unlock()의 역할을 수행한다고 생각하시면 됩니다.
다음으로 아래와 같이 세마포어는 두가지 종류가 있습니다.
- Binary Semaphore : mutex와 동일하게 value를 1을 가지는 세마포어
- Counting Semaphore : value값이 1보다 큰 세마포어
사실 카운팅 세마포어의 경우,모니터의 개념을 아시는 분들이라면 공유자원의 스케쥴링을 위해 카운팅 세마포어를 사용한다고 쉽게 이해할수 있습니다.간단히 요약하면 value가 1보다 큰 세마포어를 사용하면 임계영역에는 여러개의 쓰레드가 들어가서 작업이 가능합니다.즉,해당 세마포어는 임계영역에 몇개의 쓰레드가 들어가는지를 관리한다고 생각하시면 됩니다.
그러면 이진 세마포어는 임계영역에 들어갈 수 있는 쓰레드의 갯수가 1개입니다.즉,앞서 배운 락과 다를바 없어보입니다.하지만 여기서 가장 큰 차이점을 락은 locking을 한 쓰레드 본인이 스스로 unlock을 통해 자신의 락을 반납해야한다는 것이고 이진 세마포어의 경우 sema_down을 한 쓰레드를 다른 쓰레드가 sema_up을 하여 임계영역으로의 접근 권한을 막아 버릴수 있다는 것입니다.그래서 실제로 위키피디아의 문서를 보면 이진 세마포어의 단점 중 하나인 Accidental release,즉 아직 임계영역에서 작업을 끝내지 않은 쓰레드의 접근 권한을 다른 쓰레드가 풀어버리는 문제를 Lock 방식의 설계에서는 해결한다고 얘기합니다.(제가 앞서 올린 Lock의 코드는 sleep-awake를 알려주기 위한 코드이며 위와 같은 설계는 되어있지 않습니다)
결론적으로 Lock(Mutex)과 세마포어는 그 목적 자체가 다른 동기화 도구라는 생각을 하고 접근하시면 조금 더 쉽게 개념을 정립할수 있을것입니다.