운영체제, lock에 관해 알아보자 2편 - lock의 구현 방식과 Condition Variables
[ Lock의 구현 방식 ]
앞의 글에서는 쓰레드를 사용하는 이유, 멀티 쓰레드 환경에서 공유 자원이 있을 때 생기는 문제점, 공유자원 문제를 해결하기 위해서 Lock을 사용한다는 얘기를 했었다. 여기서 생각해봐야 할 점은 Lock을 도입해서 원자성을 얻었는데 Lock의 구현에 따라 잃는게 있지 않을까에 대한 고민을 해보아야 한다. Lock을 도입하면 공유자원에 관한 보호를 얻지만 Lock 구현 자체로 인해서 CPU 자원 손해를 봐야한다. 이에 관해 알아보자.
Spin Lock 구현 방식
정말 단순하게 구현 방법을 생각해보자. 특정한 변수하나를 추가로 두고 그 이름을 flag라고 해보자. 그러면 flag 값이 1이면 lock이고 flag 값이 0이면 unlock이다. 그리고 임계 영역에 접근할 때 만약 flag 값이 1이라면 계속 flag 값이 0인지 확인하다가 0이 되면 본인이 flag를 1로 만들고 접근한다.
하드웨어 지원을 받은 Lock 구현 방식
그럴싸 해보인다. 그런데 생각을 해보면 이전 글에서 2개의 쓰레드로 100만 더하기를 했었는데, 그 100만 더하기 상황에서 컴퓨터 구조적 한계가 있다는 이야기를 했었다. 그게 기억이 났다면 flag = 1과 flag = 0도 똑같으니 문제가 있는게 아니냐고 할 수 있다. 결론만 이야기하면 이 문제는 하드웨어적인 도움을 통해서 해결한다. 아래의 코드는 C언어 스타일로 적혀있지만 한 instruction에서 일어나는 일이다. 그러니 컴퓨터 구조적 한계라는 문제가 없다. 이 외에도 여러 방법이 있지만 여기까지만 하도록 하겠다.
하드웨어의 도움을 받으면 진짜로 문제가 없는걸까? 위의 lock 방식에서의 문제점은 아래의 코드 한 줄이 문제이다.
whlle(TestAndSet(&lock->flag, 1) == 1);
일상 생활로 따져보자. 공중화장실을 사용하고 싶은데 안에 사람이 있는지 확인을 하고 싶은 경우 문을 두들길 수 있다. 그리고 반응이 없으면 들어가서 사용하고 아니면 사용이 끝날 때까지 기다려야 한다. 그런데 위의 코드 한 줄은 이 상황으로 비유하면 본인이 화장실을 쓰겠다고 앞에 화장실 쓰고 있는 사람이 있는데 그 사람이 나올 때까지 두들기고 있는 상황이다. 문을 안 두드리고 기다리면 스마트폰을 스마트폰을 할 수도 있는데 참 안타까운 순간이다. 컴퓨터에서도 똑같다 지금 위의 상황은 CPU 자원을 그 시간 동안 다른 처리를 해줄 수도 있는데 flag 확인하는데 무한루프를 돌면서 낭비하고 있는 상황이다.
OS의 지원을 받은 Lock 구현 방식
CPU 자원 낭비 문제를 해결하려면 OS의 도움을 받아야 한다. 아래처럼 lock함수를 사용할 때에 내부 조건을 검사할 때 yield() 시스템 콜로 CPU 자원을 미리 포기하고 컨텍스트 스위칭을 해버리면 된다. 그런데, 무슨 말인지는 알겠는데 컨텍스트 스위칭도 결국 spin처럼 자원낭비이다. 계속 저 조건문 검사하고 컨텍스트 스위칭이 일어나면 결과적으로 똑같다. 이런 문제는 자원은 1개인데 접근하는 쓰레드가 100개면 그 1개 쓰레드가 컨텍스트 스위칭돼서 본인 차례가 되고 일을 다 끝내기 전까지 계속 일어난다. 그리고 무슨 쓰레드로 넘어갈지 모르는 스케쥴러의 특징상, 특정 쓰레드가 기아 현상이 일어나지 못한다는 것을 보장하지 않는다.
그래서 큐와 함께 사용해서 이 문제를 해결하는 OS(Solaris)도 있는데, 계속 생각해봐도 일반 개발자가 알려고 하기에는 너무 과한 것 같다. 결과적으로 정리하면 다음과 같다. 멀티 쓰레드에서 공유자원 문제를 해결하기 위한 Lock이 있는데 최대한 CPU를 Lock에 덜 쓰도록 하드웨어와 OS의 도움을 받아 해결하고 있으며 기아 문제도 최대한 안 일어나게 큐 같은 자료형을 같이 사용해서 문제를 해결한 것이 우리가 일반적으로 쓰고 있는 mutex Lock의 형태라는 것이다.
[ Condition Variables ]
조건변수(Condition Variables)는 간단하게 쓰레드 간 순서를 정리해주는 역할을 한다고 생각하면 된다. 순서를 정리하는 방법으로는 대기와 신호를 사용한다. 이전에 race condition을 만들었을 때 사용했던 pthread_join 함수가 그 예시이다.
아래는 pthread_join()함수를 통해서 어떻게 부모 쓰레드가 자식 쓰레드를 기다릴 수 있었는지를 확인하게 해준다.
int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
void thr_exit() {
Pthread_mutex_lock(&m);
done = 1;
Pthread_cond_signal(&c);
Pthread_mutex_unlock(&m);
}
void* child(void* arg) {
printf("child\n");
thr_exit();
return NULL;
}
void thr_join() {
Phtread_mutex_lock(&m);
while (done == 0)
Pthread_cond_wait(&c, &m);
Pthread_mutex_unlock(&m);
}
int main(int argc, char* argv[]) {
printf("parent: begin\n");
pthread_t p;
Pthread_create(&p, NULL, child, NULL);
thr_join();
printf("parent: end\n");
return 0;
}
여기서 Pthread_cond_wait함수는 쓰레드를 sleep 상태로, Pthread_cond_signal은 쓰레드를 ready 상태로 바꾸어주는 역할을 한다. 참고로 OS에서 sleep 상태에 있는 프로세스는 누가 깨워주지 않으면 계속 sleep 상태 큐에서 대기한다.
그런데 왜 이렇게 구현이 되어있을지도 생각을 해보아야 한다. 우선 while 같은 조건문이 없다면 어떻게 될 지를 생각해보자. 조건문 내의 변수 하나와 조건문의 중요성은 다음과 같다. 만약에 쓰레드 부모가 wait까지가고 컨텍스트 스위칭이 됐다면 자식이 부모를 제대로 깨워줬을 것이다. 아쉽게도 쓰레드 부모가 자식을 만들자마자 자식이 작업을 다 마치고 다시 컨텍스트 스위칭이 일어나 부모가 sleep상태로 들어가면 부모는 영원히 일어나지 못한다.
순서를 어떻게 구현하는지는 알았는데, 왜 이렇게 condition Variables가 필요한지도 고민을 해보아야 한다. 지금 위의 상황은 쓰레드 부모와 자식이 1대1인 상황이다. 그런데 1대1 관계가 아니라 다대다의 관계인 경우 lock만으로 과연 해당 정보를 보호할 수 있을까? 이를 고민해볼 수 있는 상황이 생산자 소비자 문제이다.
이전 글에서 보았던 락을 통해 값을 경쟁적으로 올렸던 단순한 케이스에선 쓰레드가 2개가 아니라 3개가 되어도 문제가 없었을 것이다. 하지만 생산자 소비자 문제는 값을 올리는 것 뿐만 아니라 내리는 것도 있다. 또한 값이 0미만의 음수로 내려가면 안된다. 그래서 아래에는 Lock과 Condition Variables를 사용해서 아래처럼 이 상황을 해결하기 위해 시도한다.
int buffer;
int count = 0
void put(int value) {
assert(count == 0);
count = 1;
buffer = value;
}
int get() {
assert(count == 1);
count = 0;
return buffer;
}
cond_t cond;
mutex_t mutex;
void* producer(void* arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // p1
if (count == 1) // p2
Pthread_cond_wait(&cond, &mutex); // p3
put(i); // p4
Pthread_cond_signal(&cond); // p5
Pthread_mutex_unlock(&mutex); // p6
}
}
void* consumer(void* arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // c1
if (count == 0) // c2
Pthread_cond_wait(&cond, &mutex); // c3
int tmp = get(); // c4
Pthread_cond_signal(&cond); // c5
Pthread_mutex_unlock(&mutex); // c6
printf("%d\n", tmp);
}
}
하지만 이 문제는 생산자가 1명, 소비자가 2명인 상황으로 가면 문제가 발생한다. 아래는 그 예시이다. 우선 소비자1이 필요한 값이 아직 없음을 깨닫고 생산자에게 값을 넘겼다. 그리고 생산자는 값을 생산을 할 때 소비자 1을 깨웠고 값이 있으니 제어권을 넘겼다. 그런데 소비자2도 OS 상의 Ready 큐에 있었고 스케쥴러가 소비자 2에게 먼저 주었다. 이 때 값이 있으니 가져가고 생산자를 깨웠다. 생산자와 소비자1이 Ready큐에 있는데 소비자 1이 가져가야 할 값이 없다. 지금 0과 1로 바꾸는 코드로 짜서 그렇지 만약에 각각을 +1, -1로 짰었다면 음수로 넘어갈 수도 있었던 상황이다. 따라서 이런 상황을 방지하기 위해서는 Pthread_con_wait에서 count 조건문을 if가 아니라 while로 설정해놓아야 한다.
그래서 이번에는 기존처럼 while로 바꾸었다.
void* producer(void* arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // p1
while (count == 1) // p2
Pthread_cond_wait(&cond, &mutex); // p3
put(i); // p4
Pthread_cond_signal(&cond); // p5
Pthread_mutex_unlock(&mutex); // p6
}
}
void* consumer(void* arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // c1
while (count == 0) // c2
Pthread_cond_wait(&cond, &mutex); // c3
int tmp = get(); // c4
Pthread_cond_signal(&cond); // c5
Pthread_mutex_unlock(&mutex); // c6
printf("%d\n", tmp);
}
}
그럼 이제는 더이상 문제가 발생하지 않을까? 아니다. 다음에는 여러 소비자와 한 명의 생산자가 한 개의 Condition Variables에만 본인의 상태를 의존하는게 문제가 된다. 이 문제는 아래의 예시에서 발견할 수 있다. 아래의 예시에서 드러난 문제는 소비자 1,2가 모두 소비할 게 없어 잠들고 생산자가 생산할 때까지 기다리고 있다. 그리고 생산자는 생산을 하고 소비자 1을 깨웠는데, 소비자 1이 소비하고 생산자를 깨우는 게 아니라 소비자 2를 깨워버렸고 본인도 소비할 게 없으니 잠들었다. 그러다가 소비자 2도 소비할 게 없어 잠들었는데, 결국엔 모두가 서로가 깨워주기를 기대하다가 시스템이 멈춰버린 것이다.
이 문제를 해결하려면 생산자는 소비자만을 소비자는 생산자만을 깨울 수 있도록 2개의 condition variables을 두면 된다. 아래처럼 말이다. 그러면 위에서 생기는 문제를 해결할 수 있다.
cond_t empty, fill;
mutex_t mutex;
void* producer(void* arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
if (count == 1)
Pthread_cond_wait(&empty, &mutex);
put(i);
Pthread_cond_signal(&fill);
Pthread_mutex_unlock(&mutex);
}
}
void* consumer(void* arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
if (count == 0)
Pthread_cond_wait(&fill, &mutex);
int tmp = get();
Pthread_cond_signal(&empty);
Pthread_mutex_unlock(&mutex);
printf("%d\n", tmp);
}
}
코드도 많이 들어갔고 최적화에 관한 내용은 뺐다. 그래서 이 때까지의 내용을 정리해보고 마치려고 한다. 역할을 나누거나 동시에 여러 처리를 위해 멀티 프로세스 환경이 필요해졌다. 그런데 프로세스 간 통신은 복잡하고 비용이 크니 중간에 본인만의 스택을 제외한 공유 영역을 가진 쓰레드로 경량화를 했다. 경량화를 했는데 공유 자원이다보니 경쟁적 상황이 벌어졌다. 경쟁적 상황이 벌어지는 문제를 막기 위해서 Lock을 도입했다. Lock에서 불필요한 자원을 낭비하는 걸 막기 위해 OS의 도움을 받아 본인이 기다리는게 끝날 때까지 sleep 상태로 대기하다가 깨워주는 방식이 필요했다. 그래서 condition variables를 도입했고 이를 통해서 순서 제어가 가능했다. 순서 제어가 가능해지니 이전에 Lock만으로는 구현이 불가능했던 생산자 소비자 문제를 해결할 수 있게 됐다. 순서 제어로 생산자가 생산한 값이 있을 때만 소비자가 값을 가져갈 수 있게 때문이다.
[ 참고 자료 ]
운영체제 - 서의성 강의