오퍼레이팅 시스템

[OS] 동기화

유승혁 2022. 9. 19. 19:39

0. 동기화의 필요성

사용하기 쉽고 편한 스레드의 등장 대신 그 만큼의 책임이 생겼다. stack 영역을 제외한 메모리 영역은 공유를 하기 때문에 조심해야 한다. 예를 들어 어떤 스레드는 값을 5를 넣고 어떤 연산 이후 그 값에 10을 더하는 연산을 해야하는 와중에 context switch가 발생하여 다른 스레드가 3으로 바꿔 버리면 원래 스레드가 그 값을 읽고 10을 더하면 13을 도출하게 된다. 이러한 문제를 race condition(동시성 문제)이라 고 한다. 다시말해 같은 실행과정을 거쳐도 리턴 값이 일정하지 않고 예측할 수 없다는 문제이다. 이를 해결하기 위해 여러 동기화 기법이 등장하였다.

 

1. 동시성 문제는 왜 발생하는가

 동시성 문제가 발생하면 무작위 게임을 하는 것과 같다. context switch, 즉 실행 순서에 의해 같은 코드에도 다른 결과가 도출 될 수 있고 실행 순서는 os가 kernel 레벨에서 정해지는 것이기에 우리는 예측 불가하다. 아래와 같은 예시를 들어보자.

 두 스레드 둘 다 counter++; 라는 코드라고 가정하자. 그럼 아래와 같이 어셈블리어로 해석된다. counter는 초기 0 이다.

Thread A
(1) Load counter
(2) Add counter
(3) store counter		 Thread B
(1) Load counter
(2) Add counter
(3) store counter

 두 스레드가 모두 돌고 나면 counter는 2가 되어야 한다. 과연 그럴까?

 예를 들어 A(1)을 하고 나서 context switch가 발생하여 B의 (1)-(2)-(3) 지나서 counter 는 1이 되었다. 하지만 A의 register에는 0이 저장 되어 있고 A(2)-(3)을 지나고 나면 counter에는 1이 저장 된다. 두 스레드가 지나가도 1이라는 뜻.. 만약 단일 프로세스가 아닌 multicore라고 하더라도 A가 (1)-(2)-(3)하기 전에 B가 (1) 해버리면 counter에는 1이 저장 된다.

 

2. Critical Resource/Section, Mutual Exclusion

 우리가 지켜야 하는 자원에 대해 정의한 것이다. 중요 자원의 종류 중에는 Critical Resource라는 것이 있는데 전부 다 이다. 즉, 한번에 하나의 프로세서만 접근해야 하는 경우를 뜻한다(프로세스의 공유 자원 범위). 그 보다 작은 범위는 Sharing resource. 스레드 단위의 공유 자원 범위를 의미한다. 정적 데이터, heap, files, I/O 장치들을 의미한다.

 이러한 Critical Resource를 사용하는 코드 부분을 Critical Section이라고 말한다. 두 스레드가 동시에 해당 코드에 접근하면 위험함.. 단지 읽기라면 괜찮겠지만..

 그래서 이러한 접근을 방지해 주는 것이 Mutual Exclusion이다.

 

3. 동기화 알고리즘

 다른 말로는 mutual exclusion(상호 배제)이다. 어떤 알고리즘이 동기화를 해준다는 건 다음 3가지 특징을 모두 만족할 경우를 의미한다.

(1) 상호배제: 어떤 프로세서(스레드)가 cirtical section에 접근 하였을 때 그 어떠한 프로세서도 접근하지 못함.

(2) 진행: 어떠한 프로세서도 critical section에 접근하지 않은 상태에서 어떠한 프로세서가 들어가고 싶어 하면 들어 오게 해야 한다.

(3) 한정 대기: critical section에 들어가고 싶어하는 프로세서가 있다면 일정시간 안에 진입 시켜야 한다.

 이제 동기화 알고리즘을 하나씩 살펴보자. 

 동기화 알고리즘은 크게 SW 방식과 HW 방식 둘로 나뉜다. 먼저 SW 방식부터 알아보자.

 

3.0 Naive

 정말 단순하게 생각하면 다음과 같이 생각할 수 있다.

While(1){
    if(bOccupied == 0){
         bOccupied = 1;
         break;
    }
}
/*critical section*/

bOccupied = 0;		 While(1){
    if(bOccupied == 0){
         bOccupied = 1;
         break;
    }
}
/*critical section*/

bOccupied = 0;

 bOccupied 를 통해 누군가가 사용 하고 있는지 아닌지 표시한다. 하지만 이런 생각은 쉽게 반박 된다. bOccupied에 1을 넣는 과정에서 context switch가 일어나면.. 둘이 동시에 접근하니 안된다. 즉 (1)을 만족하지 않는다.

 

3.1 SW approach

  이번엔 두 개의 flag와 while 문으로 해결해보자.

flag[0] = true;

while(flag[1]);

/*critical section*/

flag[0] = false;		 flag[1] = true;

while(flag[0]);

/*critical section*/

flag[1] = false;

 이 경우의 문제는 다음과 같다. (1)은 잘 만족할 수 있지만 flag[0]=true 하고 context switch, flag[1]=true 하고 context swtich 일어나면 둘 다 while 에서 무한 루프를 돌게 된다. 즉, (2)가 성립하지 않기에 탈락!

 

3.2 Peterson's

 이 알고리즘 또한 SW 방식이다.

flag[0] = true;
turn = 1;
while(flag[1] && turn == 1);

/*critical section*/

flag[0] = false;		 flag[1] = true;
turn = 0;
while(flag[0] && turn == 0);

/*critical section*/

flag[1] = false;

 위 방식은 (1),(2),(3) 모두 만족한다. 왜냐하면 왼쪽 스레드는 flag[1]을 통해 상대방이 쓰려고 하는 구나, 근데 내가 turn == 1을 보고 내가 뺏을 뻔 했네! 하고 기다린다. 그럼 이제 두 오른쪽스레드가 turn = 0을 하고 while문을 돌지 않는다. 만약 오른쪽 스레드가 turn = 0 에서 뺏기면 오른쪽 스레드가 while문을 돌지 않게 된다. 이런 식으로 (1),(2),(3) 모두 만족하지만, compiler가 임의로 flag와 turn 부분의 코드의 순서를 자기 마음대로 바꾸어 버리면(최적화를 위해 이런 일이 종종 일어난다.) 꼬이게 된다.

 

3.3 Disabling Interrupts

 에휴, 이제 SW방식은 못해먹겠으니 HW 방식으로 가자꾸나. 아래에 코드가 나오는데 SW 코드가 아니라 이러한 동작을 하는 코드를 system call로 제공해준다는 의미이다.

 가장 초기에 나온 생각은, context switch가 일어나기 전에는 system call을 통한 mode switch가 발생한다. 이때는 interrupt가 발생하기 마련. 그래서 아래와 같은 두 함수를 제공한다.

void lock(){
   DisableInterrupts();
}

void unlock(){
   EnableInterrupts();
}

 즉 인터럽트를 잠갔다 풀기를 반복해서 뺏기지 않는다. 간단하다는 장점이 있지만, interrupt가 정말 필요할 때도 무시해 버린다는 문제와 이러한 특권은 악성 코드에도 응용되기 쉽고 multi processor일때는 적용이 안된다. 한쪽 프로세서에 신나게 잠가 봤자 다른 프로세서는 별 상관 없다. 뿐만 아니라 중첩 lock을 적용하기도 어렵고 cost가 든다.

 

3.4 TAS/CAS

 Spin Locks로 불리는 TAS와 CAS이다. 둘의 큰 차이는 잠금 값을 설정할 수 있는 것일 뿐, 큰 차이는 없다. 시스템은 이와 같다. TAS또는 CAS가 반환하는 리턴값을 확인하여 lock을 걸거나 lock을 걸지 않거나 이다. 아래 코드 처럼.

void lock(lock_t *lock){
	while(TAS(&lock->flag,1) == 1);
}

int TAS(int *old_ptr, int new){
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

 즉, 어떤 스레드가 먼저 lock()을 호출하면 lock이 가리키는 메모리의 값이 1로 변하고 0을 리턴 받아 while 문을 돌지 않는다. 해당 스레드가 unlock으로 lock 변수를 바꾸어 주지 않는다면 다른 스레드는 TAS의 리턴 값이 계속 1일 테니 while 문에서 잠든다.. 어? 이거 어디서 본 패턴!

 그렇다 Naive approach인데 이걸 system call로서 제공하는 것이다. 그 덕에 context switch가 나던 multi processor이건 동시성 문제가 발생하지 않는다. context switch 자체가 발생하지 않기도 하고 같은 메모리 주소를 통해 공유 하기 때문에 발생하지 않는 것이다.

 이러한 방식에는 단점이 존재하는데, 스레드간 우선순위를 제공하여 접근하게 하는 것이 어렵고(fairness 문제) lock 걸린다면 while 문을 계속 돌면서 '내 차례인가?' 계속 확인하기 때문에 cpu bound 작업이 된다. 만약 I/O bound 처럼 재워버리고 자리가 나면 일어나는 방식이라면 얼마나 좋을까?

 

4. Semaphore

 그렇게 semaphore가 등장하게 되었다. 위 처럼 계속 확인하는 컨셉을 busy waiting이라 하고 이제 등장할 방식을 sleep awake라고 한다. 오해하면 안되는게 busy waiting이 항상 나쁜건 아니다. lock 시간이 짧다면 busy waiting이 훨씬 유리하다. 그 이유는 말 그대로 재우고 깨우고를 반복 -> 인터럽트 이기 때문에 busy waiting에 비해 cost가 굉장히 클 수 있다.

 요녀석은 굉장히 자세히 다루어야 한다. 세마포어라는 하나로 두 가지의 것을 할 수 있다. 지금 까지 다루는 상호배제와 조건동기. 주구장창 상호배제에 대해서만 이야기했으니 조건 동기는 조금 미루겠다.

 semaphore는 두 가지 함수를 총칭하는데 다양한 이름이 있다.

 - semWait() = P() = sleep()

 - semPost() = V() = awake()

 P를 불러서 누군가가 작업을 하고 있다면 해당 스레드는 잠들고, 기존에 critical section 에서 작업 중이던 녀석은 처리가 끝나면 V를 호출하여 P에서 자고있던 녀석들을 깨운다.

 semaphore에는 binary semaphore와 counting semaphore 둘로 나뉘는데, counting 만 코드로서 보여주자면,

struct semaphore{
	int count;
    queueType queue;
};

void semWait(semaphore s){
	s.count--;
    if(s.count<0){
    	//해당 프로세스 또는 스레드 queue에 넣기
        //이 프로세스 또는 스레드 block시키기
    }
}

void semSignal(semaphore s){
	s.count++;
    if(s.count <= 0){
    	//누군가가 자고 있으므로 queue에서 프로세스를 꺼냄/
        //꺼내진 프로세스는 ready queue에 들어감
    }
}

 binary semaphore의 경우는 count가 0 아니면 1일 뿐이고 조건문은 qeueu가 비어있는 지를 기준으로 판단한다.

 또한 semaphore의 count 변수를 2이상의 정수로 할 수 있는데 그러면 한번에 두 개 이상의 프로세서가 접근 가능 한 것이다.

 

5. DeadLocks

 semaphore 덕에 정말 단순한 방식으로 상호 배제를 걸 수 있게 되었지만 전적으로 프로그래머에게 맡겨 졌으니 컴파일러는 어떠한 문제 제기를 하지 못한다. 그러한 문제 중 하나를 deadlock 이라고 한다.

 예를 들어 S와 Q라는 자원이 있어서 이에 대해 아래와 같은 코드가 있다고 보자.

P1: wait(S); wait(Q); ...  signal(S); signal(Q);
P2: wait(Q); wait(S); ...  signal(Q); signal(S);

 만약 P1이 wait(S)하고 context switch 걸려서 P2의 wait(Q) 지나게 되면 S,Q 둘 다 하나의 자원이 선점 되어 있기 때문에 둘 다 진행이 되지 않는다. 이러한 경우를 dead lock. 간단하게는, 절대로 일어나지 않을 일을 기다리는 경우를 의미한다.

 deadlock 에 대한 자세한 정의와 피할 수 있는 방법은 다음 글에서 자세히 다루겠다.

 

6. Condition Variables (CV)

 조건 동기화를 영어로 해봤당 헤헤. 조건 동기화는 마치 프로세스 간 접근 순서를 걸거나 진행 순서를 바꾸거나 할 수 있다. 예를 들어 부모가 자식 프로세스 만들고 자식이 어떠한 작업을 하고 끝나야지만 부모가 다음 코드를 진행 할 수 있다고 할 때, 부모는 lock에 걸려있다가 자식이 나 끝났어~ 하면 그제서야 일어나서 자신의 코드를 진행하게끔 하는게 조건 동기화이다. 물론 여기서 while loop를 통해 할 수 있겠지만, 자식 프로세스의 task가 시간 좀 걸리는 작업이라면, block 되어 있는게 훨 낫다.

 이를 semaphore를 통해서도 진행 할 수 있다. semaphore의 변수 S를 0으로 설정하자. 그 후 부모에는 wait(S); 자식에서는 signal(S);와 같이 코드를 배치해 두면 위 예시를 쉽게 해결할 수 있다.

 

6.1 CV 구현체

 C언어에서는 semaphore가 아닌 다른 함수를 제공해 준다.

 pthread_cond_wait()과 pthread_cond_signal() 쌍과 mutex lock을 제공해주는 pthread_mutex_lock()과 pthread_mutex_unlock()이 존재한다.

 구현한 방식을 대략적인 코드로 살펴보자.

[Thread - 1]
int main()
{
    pthread_t c;
    pthread_create(&c, NULL, child, NULL;
    thr_join();

    return 0;
}
void thr_join(){
    pthread_mutex_lock(&m);
    while(done == 0)
        pthread_cond_wait(&c,&m);
    pthread_mutex_unlock(&m);
}		 [Thread - 2]
void *child(void* arg){
     thr_exit();
     return NULL;
}
void thr_exit(){
    pthread_mutex_lock(&m);
    done=1;
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

 자 이제 하나씩 살펴보자. 1에서 스레드를 만들고 실행한다. 이후 thread 1과 2는 동시에 진행된다. 만약 1이 먼저 thr_join을 통해 m을 걸어 잠궜다 가정하자. 그러면 2는 thr_exit에서 1이 thr_join을 하는 동안 코드를 진행하지 못한다. 1에서 while의 조건이 참이기 때문에 pthread_cond_wait이 돌게 된다. 이와 동시에 c를 잡고 잠에 들고 m을 깨운다. 그러면 2에서 m이 풀렸으니 코드가 진행 되면서 m을 걸어 잠그고 done을 1로 만들어 버린다. 그다음 signal로 c를 깨우고 m 을 풀고 종료 된다. 그럼 1은 pthread_cond_wait()을 벗어남과 동시에 m을 다시 걸어 잠그고 done이 1인 것을 확인하여 loop를 나오게 되고 m을 unlock을 통해 다시 풀어낸다.

 반대로 2가 먼저 m을 먼저 잡아버린다고 하면, 2가 m 잠갔으니 1은 아무것도 하지 못하고 2만 진행 된다. done을 1로 만들고 signal을 보내지만 허공에 내던져져 버리고 m을 풀고 종료한다. 그러면 1이 m 걸어 잠그고 while 조건문 안맞으니깐 loop 안돌고 m 풀고 종료된다.

즉 이처럼 자식이 끝나야 부모가 끝날 수 있도록 CV를 적용 시켰다.

 

6.2 CV의 조건

 위 코드에서 의아할 수 있는 부분들이 많다. 예를 들어 done이라던지 while문 같은 녀석들. 그러한 녀석들을 하나씩 정의해보자.

 - State variable: done과 같이 상태 변수가 필요하다.

 - Lock for the state variable: done의 mutex를 보장해줄 lock이 필요하다.

 - Loop checking a condition using state variable: 상태 변수의 값을 확인해줄 loop가 필요하다.

 하나씩 그 예시를 들어보자.

 만약 lock이 없다면? 1이 done을 확인하자 마자 2로 가서 done을 1로 만들고 signal 보내 봤자 signal은 허공에 날라가고 종료되면 1을 pthread_cond_wait에 걸려 영원히 자게 된다.

 만약 state variable이 없다면? loop checking도 자연스레 없어진다. 그러면서 thr_exit() 다 하고 thr_join 해버리면 1은 계속 자게 된다.

 만약 loop checking이 아닌 if로 체크한다면? 해당 부분에 대해서는 생산자/소비자 문제를 통해 확인해보자.

 

7. 생산자/소비자

 생산자가 생산을 해야 소비를 하는 것 같은 경우이다. 생산자는 하나씩 생산하고 소비자도 하나씩 소비한다. count 값은 남은 량이고 최소 0 최대 MAX 만큼 유지할 수 있다. 

void producer(){
     while(1){
          pthread_mutex_lock(&m);
          if(count == MAX)
               pthread_cond_wait(&c,&m);
          put(value);
          pthread_cond_signal(&c);
          pthread_mutex_unlock(&m);
     } 
}		 void consumer(){
     while(1){
          pthread_mutex_lock(&m);
          if(count == 0)
            pthread_cond_wait(&c,&m);
          get();
          pthread_cond_signal(&c);
          pthread_mutex_unlock(&m);
     } 
}

 요 코드를 보면 count가 state variable이 되고 while 문이 아닌 if문으로 state variable의 조건을 체크한다. 

 MAX는 1이라 가정하고 count = 0이 초기 값, 생산자 하나 두 명의 소비자라고 가정하자. 이때 put은 count를 1로 만들어주고 get은 count를 1 감소 시킨다.

 count가 0인상태에서 소비자1이 count가 0이라서 잠들었다. 이때 생산자가 count를 1로 만들고 signal을 보내 자고 있던 소비자1 이 깨어났다. 그리고 생산자는 count가 MAX 가 되어 wait을 통해 잠들었다. 이때 소비자 2가 코드를 실행하며 count가 1이니깐 소비하여 count를 0으로 만들고 잠들었다. 이후 소비자 1은 ready 상태 였으니 get()를 한다. 즉 count 값을 -1로 만들어 버렸다.

 만약 while로 체크를 했다면 1번 소비자는 '아 잘잤다. 일어나야지?' 하고 딱 봤는데 while 조건에서 count == 0이 성립하니 다시 잠들어 버린다. 그러하기에 state variable의 조건을 체크할때는 if가 아닌 while로 체크를 해야함을 알 수 있다.

 

7.1 하지만...

 아래 코드는 완전하지 않다. 다음 예를 들어보자.

void producer(){
     while(1){
          pthread_mutex_lock(&m);
          while(count == MAX)
               pthread_cond_wait(&c,&m);
          put(value);
          pthread_cond_signal(&c);
          pthread_mutex_unlock(&m);
     } 
}		 void consumer(){
     while(1){
          pthread_mutex_lock(&m);
          while(count == 0)
            pthread_cond_wait(&c,&m);
          get();
          pthread_cond_signal(&c);
          pthread_mutex_unlock(&m);
     } 
}

 소비자 1이 시작하면서 잠들어 버리고, 소비자 2도 진행하다 잠들어 버린다. 이때 생산자가 put을 하여 signal을 보내 소비자 1을 깨우고 잠든다. 그럼 소비자 1이 count를 0으로 만들고 signal을 보냈는데, 이때 signal이 생산자가 아닌 소비자 2를 깨워 버리게 된다. 그럼 소비자 1은 count 값을 확인하고 다시 자버리게 되어 모든 생산자와 소비자가 잠들어 버린다. 즉, dead lock (교착상태)

문제가 어디서 발생한 것이냐면, 생산자를 깨우거나 소비자를 깨우는 semaphore가 동일해서 발생하는 문제인 거다! 생산자를 깨워야 하는데 그 신호가 다른 소비자에게 가버린 것이다. 그렇다면! semaphore의 값을 각각 전용으로 만들어 주면 되는 것!

 아래와 같은 코드가 만들어 진다.

void producer(){
     while(1){
          pthread_mutex_lock(&m);
          while(count == MAX)
               pthread_cond_wait(&empty,&m);
          put(value);
          pthread_cond_signal(&fill);
          pthread_mutex_unlock(&m);
     } 
}		 void consumer(){
     while(1){
          pthread_mutex_lock(&m);
          while(count == 0)
              pthread_cond_wait(&fill, &m);
          get(value);
          pthread_cond_signal();
          pthread_mutex_unlock(&m);
     } 
}

 

7.2 semaphore as CV

 지금껏 CV를 C에서 제공하는 pthread_cond_wait/signal 을 통해 확인할 수 있었다. 놀라운 것은 이 역할을 semaphore 로도 가능 하다!!

 맨 처음에 든 예시(부모 자식) 에 semaphore를 적용한 코드는 아래와 같다.

sem_t s;

void* child(void* args){
    printf("child\n");
    sem_post(&s);
    return NULL;
}

int main()
{
    sem_init(&s,0,0);
    printf("parent: begin\n");
    pthread_t c;
    pthread_create(c,NULL,child,NULL);
    sem_wait(&s);
    printf("parent: end\n");

    return 0;
}

 이처럼 sem_init을 통해 s를 0으로 설정하여 자식이 post로 s를 1로 만들어 주면 부모 프로세스가 깨어나면서 종료된다.

 만약 생산자 소비자를 semaphore로 하고자 한다면 아래와 같다.

void producer(){
     while(1){
         sem_wait(&empty);
         sem_wait(&m);
          put(value);
          sem_post(&m);
          sem_post(&fill);
     } 
}		 void consumer(){
     while(1){
         sem_wait(&fill);
         sem_wait(&m);
          get();
          sem_post(&m);
          sem_post(&empty);
     } 
}

 mutex와 cv의 코드의 순서가 바뀐 이유는 만약 소비자가 먼저 실행 되면서 sem_wait(&m) 으로 m에 대해 lock 걸고 count 초기 값이 0이니깐 sem_wait(&fill) 을 통해 잠든 뒤에 생산자가 m에 대해 lock이 걸려 버리면 deadlock이 될 수 있기 때문이다.

 정말 semaphore는 사용하기 쉽지만 그만큼 리스크가 있는 것 같다.

 

8. Readers-Writers 문제

 이 경우는 어떤 값을 수정하는 Writers와 다수의 Readers가 있는 상황이다. readers는 제한 없이 한번에 여러 reader가 정보에 대해 접근 하능 하지만 writer가 데이터를 수정 하는 동안에는 접근하면 안된다. 마치 DB의 serializable 격리 상태 처럼. 뿐만 아니라 writer는 한번에 한명 씩만 존재 해야 한다. 

 readcount가 이번엔 state variable이고 초기 값은 0, semaphore x = 1, wsem = 1 로 설정 되어 있다.

void writer(){
    while(true){
        semWait(wsem);
        WRITE();
        semSignal(wsem);
     }
}		 void reader(){
   while(true){
      semWait(x);
      readCount++;
      if(readCount == 1) semWait(wsem);
       semSignal(x);
       READ();
       semWait(x);
       readCount--;
       if(readCount ==0 ) semSignal(wsem);
       semSignal(x);
    }
}

 만약 writer가 먼저 실행 되면 wsem 잠그고 쓰고 신호 보낸다.  만약 잠갔을 때 reader가 접근하게 된다면, 첫 reader는 x 잠그고 readCount를 1로 만든 다음에 semWait(wsem)에서 자버린다. 이후 writer가 쓰기를 완료하고 wsem을 1로 만들고 종료하면 reader는 일어나서 x 잠근 걸 풀고 read를 한다. 

 지금 아마 CV이외의 코드 부분이 혼란 스러울 수 있는데, 정리하자면 read는 다같이 접근 가능하니깐 READ()에 대해 mutex 를 할 필요 없지만 readCount는 state variable이므로 이에 대한 mutex는 필요하다. 그렇기에 readCount를 조작하거나 확인하기 위해서는 x를 통해 mutex를 보장 받는 것이다. 

 또한 reader가 많은데 writer가 작업중이면 한명만 if(readCount==1)에 걸려있고 나머지는 쭈루룩 semWait(x)에 걸려있다. 그러다가 reader의 차례가 되면 주루루루룩 미친듯이 내려가면서 readCount를 증가시키고 다시 감소시키다가 마지막에 read가 끝나는 녀석이 if(readCount==0) semSignal(wsem);을 통해 writer가 대기중이라면 깨워준다.