[전공생이 설명하는 OS] 동기화 - (2) 상호배제 전략 (Mutex)

지난 포스팅(동기화 - (1) 용어 및 개념정리)에서 정리했듯이,

 

동기화는 Critical Section 에 대한 접근 제어를 적절하게 잘 한다는 것이고,

 

구체적으로 MutualExclusion / Progress / BoundedWaiting 3가지의 requirement를 만족시켜야한다고 언급했다.

 

이런 특성을 만족시키는 동기화 전략은 (1)상호배제, (2)조건부 동기화 전략이 있는데,

 

이번 포스팅에서는 상호배제의 측면에서 동기화 기법을 살펴보도록 한다.

 

상호배제 차원의 동기화 전략은 SW의 방식과 HW의 방식으로 나눌 수 있다.

 

---

1. SW approach

크게 1) Peterson의 알고리즘, 2) Interrupt 차단방식 두가지를 예로 들 수 있다. 결론부터 이야기하자면, SW 방식의 동기화 전략은 효과적이지 못하다. HW의 도움을 받아야한다.

---

1) Peterson's Algorithm

 바로 Peterson 의 알고리즘을 보면, 이해하기가 쉽지 않기 때문에, 3단계로 빌드업하면서 설명한다. 

(1) Naive approach 

  가장 빨리 떠올릴 수 있는 간단한 방법은, flag 변수를 선언하는 방법이다.  아래와 같이 critical section 에 진입할 때 flag를 활성화 시키고, 빠져나올 때 비활성화하는 방법이다. critical section에 진입하기 위해 flag 변수를 busy-waiting 방식으로 계속 확인한다.

while(1) /* critical section start */
{
    if (!occupied)
    {
        occupied = true;
        break;
    }	
}

//access shared resource here !!

occupied = false; /* critical section end */

  하지만 이 방법은 옳은 방법이 아니다. occupied 라는 flag 변수도 공유변수이기 때문에, 상호배제 시켜야한다. 구체적으로 문제가 되는 예는 (if 블럭에 진입한 후) ~ (occupied 가 true 로 변하기 전) 에 스케줄링 되는 상황이다. 

1. Process A 가 if 블럭에 진입, 즉시 스케줄링 되어 occupied가 true 로 변경되지 않고, false 임.
2. Process B 가 critical section 에 진입하여 공유자원에 write 작업을 수행하던 중 스케줄링
3. Process A 가 if 문 내부에서 재실행되면서 공유자원에 접근! (원래 의도는 Process B 가 임계영역에 있기 때문에 occupied 가 true 인 것을 확인하고 block 되어야한다. 공유자원의 변경값이 메모리에 적용되기 전에 다중쓰기되므로 동기화 실패!) 

(2) Better approach

  위의 상황에서의 문제는 flag 변수 또한 공유변수라는 점이다. 그러면 flag 변수를 공유변수가 아닌, 프로세스마다 개별적으로 사용하게끔 해서 좀 더 나은 방법을 만들 수 있다.

  아래의 예는 두개의 프로세스(0번 프로세스, 1번 프로세스)가 있을 때, flag 변수를 프로세스 하나당 할당하는 예제이다.

/* 0번 Process */
do {
    accupied[0] = true;
    while (accupied[1]); // 1번 Process 가 점유중이면 기다림.
    
        /* Critical Section */
        
    accupied[0] = false;
    
// Remainder Section
    
} while(1)

/* 1번 Process */
do {
    accupied[1] = true;
    while (accupied[0]); // 0번 Process 가 점유중이면 기다림.
    
        /* Critical Section */
        
    accupied[1] = false;
    
// Remainder Section
    
} while(1)

  하지만 아직도 문제가 존재하는데, 0번 프로세스가 임계영역 밖에 존재하고, 1번 프로세스가 flag[1] = true; 를 수행한 뒤 while 전에 스케줄링 되는 상황을 생각해보자.

1. 1번 프로세스가 accupied[1] = true; 를 수행한 뒤 while 전에 스케줄링
2. 0번 프소세스가 accupied[0] = true; 를 수행함. while(accupied[1]); 에서 block
3. 1번 프로세스도 while(accupied[0]); 에서 block 
4. 둘 다 block -> deadlock

  두 프로세스 모두 공유자원에 접근할 수 없는 deadlock이 발생한다. Progress requirement 를 만족시키지 못하는 상황이다.

  즉, 공유자원인 flag 변수를 분리함으로써 mutual exclusion requirement를 위배하는 상황을 해결했지만, Progress requirement 를 만족시키지 못함으로써, critical section 에 대한 접근제어를 적절히 잘 했다고 평가할 수 없다.

(3) Peterson's solution

  위에서의 progress requirement 를 해결하기 위해, 공통된 flag를 하나 더 도입한다. 정리하자면, (분리된 flag 2개) + (공유 flag) 를 사용한다. 

/* 0번 Process */
do {
    accupied[0] = true;
    turn = 1;  // 1번 프로세스가 실행할 의사가 있으면 양보.
    while (accupied[1] && turn==1); // 1번 Process 가 점유중이면 기다림.
    
        /* Critical Section */
        
    accupied[0] = false;
    
// Remainder Section
    
} while(1)

/* 1번 Process */
do {
    accupied[1] = true;
    turn = 0; // 0번 프로세스가 실행할 의사가 있으면 양보.
    while (accupied[0] && turn==0); // 0번 Process 가 점유중이면 기다림.
    
        /* Critical Section */
        
    accupied[1] = false;
    
// Remainder Section
    
} while(1)

  아까와 비슷하게 1번 프로세스가 accupied[1] = true 를 실행하고 스케줄링 되었다고 생각해보자

1. 1번 프로세스가 accupied[1] = true 를 실행하고 스케줄링 
2. 0번 프로세스가  accupied[0] = true; turn=1; 하고 while 에서 기다림.
3. 1번 프로세스가 turn=0; 수행하고 while 에서 기다림
4. 0번 프로세스가 while 을 지나치고 실행됨

  이 방법은 두 프로세스(또는 스레드)에서의 동기화 문제를 잘 해결했지만, 너무 복잡하다는 문제가 있다. 프로세스 개수가 3개 이상부터는 기하급수적으로 복잡해진다.

  또 현대 OS에서는 적용할 수 없는데, compiler 에 의해 instruction reordering 이 발생하기 때문이다. low level 에서의 instruction 순서가 바뀔 수 있다. 결국 accupied[i] = true; turn = i; 의 실행 순서가 보장되지 않아서, 적용할 수 없다.

---

2) Disabling Interrupts

  초창기 OS에서 사용하던 방식. single-processor system 에서 고안되었다. Critical Section 에 진입하면 모든 인터럽트를 끄는 방식이다. 이는 (1) 인터럽트 신호를 잃어버릴 수 있고, (2) 악의적으로 cpu를 독점할 수 있으며, (3) 멀티 프로세서 시스템에서는 더더욱 비효율적이라는 단점이 존재한다. 횡단보도 하나 건너기 위해 전국의 횡단보도를 끄는 셈이다. system timer interrupt, io interrupt 등을 다 비활성화 시키기 때문에, 스케줄링이 원천적으로 금지된다.

(=순차처리 방식, = concurrency 가 극단적으로 낮아짐) 

---

2. HW support

++ 연산은 machine-level 에서 3개의 명령어로 구성된다.

 

위에서 충분히 봤듯이, 소프트웨어의 구현만으로는 동기화 문제를 처리할 수 없다. 조금만 생각해봐도 이는 당연한데, 왜냐하면 동기화 문제는 근본적으로 하드웨어의 구조적 문제로 발생하기 때문이다.

• (main 메모리와 캐시메모리의 분리)
• => (데이터 수정할 때, 하드웨어에서는 여러 단계의 작업이 필요)
• => (중간 단계에서 갑자기 스케줄링!)
• => race condition!

따라서 하드웨어 수준에서 다음과 같은 조치를 취한다면, race condition을 방지할 수 있다.

• 여러 단계의 하드웨어 작업을 atomic 하게 수행할 수 있도록 묶어서 instruction 을 만든다. -> 하나의 instuction 을 수행하는 도중에는 스케줄링 될 수 없으므로(물리적으로 불가능), race condition이 발생하지 않는다.

 

---

 

HW 의 도움을 받는다는 것을 결국 Single Atomic Operation 을 지원받는 것을 의미한다. 

아래의 예시는 실제 HW 수준에서 제공하는 atomic 한 단일 Instruction 을 c언어 수준에서 설명한다.

 

(1) Test-And-Set (TAS)

  다음 psuedo code 와 같은 instruction 을 HW에서 제공한다.

/**
 * 아래의 TestAndSet 함수는 low-level 에서의 machine code 를 c언어로 표현한 것이다.
 * 하드웨어 수준에서 atomic 한 instruction을 제공한다.
 */
int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

void lock(lock_t *lock) {
    // 공유변수 lock 을 다른 프로세스가 선점하고 있다면, *old_ptr == 1
    // 즉 1을 리턴하고 busy waiting
    // 공유변수 lock 을 아무도 점유하고 있지 않다면, *old_ptr == 0
    // lock 을 점유하고 빠져나감!
    while(TestAndSet(&lock->flag, 1) == 1);
}

 

(2) Compare-And-Swap (CAS)

  : TAS 와 동일한 기능을 제공한다. 다만 TAS는 매번 변수에 new value 를 대입하는데 반해서, CAS는 기존값이 expected value와 동일할 때만 변경해준다. 

/**
 * 아래의 CompareAndSet 함수는 low-level 에서의 machine code 를 c언어로 표현한 것이다.
 * 하드웨어 수준에서 atomic 한 instruction을 제공한다.
 */
int CompareAndSet(int *old_ptr, int expected, int new) {
    int old = *old_ptr;
    if (old == expected) // TAS 에 비교해서 추가된 기능
        *old_ptr = new;
    return old;
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

void lock(lock_t *lock) {
    // 공유변수 lock 을 다른 프로세스가 선점하고 있다면, *old_ptr == 1
    // 즉 1을 리턴하고 busy waiting
    // 공유변수 lock 을 아무도 점유하고 있지 않다면, *old_ptr == 0
    // lock 을 점유하고 빠져나감!
    while(CompareAndSet(&lock->flag, 0, 1) == 1);
}

  위와 같은 wait 방식을 busy-waiting 또는 spin-waiting 이라고 한다. 기다리는동안 cpu를 계속 사용하면서 조건을 확인하는 방식이다. 매우 짧은 시간동안만 기다릴 것으로 예측되는 경우에는 효과적이다. (scheduling 시에 타이밍에 기대기 때문에, cpu 점유 관점에서는 fair하지는 않다). 반면 프린트 출력 작업과 같이 오랜시간동안 기다릴 것으로 예상될 때에는 sleep 하고 다른 프로세스를 실행시키는 것이 효과적이다. 이때 사용되는 것이 semaphore 이다. 세마포는 상호배제 측면 뿐만 아니라 조건동기화의 측면에서도 사용될 수 있다.

 

---

[pthread.h 예시]

  pthread 는 UNIX 계열 OS에서 제공하는 스레드 라이브러리다. 전역변수 x를 두개의 child threads가 각각 1000번씩 더하고 빼는 예시이다. 코드를 보면 pthread_mutex_lock, pthread_mutex_unlock 함수가 있는데, 위에서 설명한 것처럼 HW의 도움을 받아서 상호배제 전략의 동기화를 제공한다. (내부적으로는 busy-waiting 이 아니라 시그널을 사용하는 것으로 알고있다.)

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define ITER 1000

void *thread_increment(void *arg); 
void *thread_decrement(void *arg); 
int x;  
pthread_mutex_t m; 

int main() {

    pthread_t tid1, tid2; 
    pthread_mutex_init(&m, NULL); 
    pthread_create(&tid1, NULL, thread_increment, NULL); 
    pthread_create(&tid2, NULL, thread_decrement, NULL); 
    pthread_join(tid1, NULL); 
    pthread_join(tid2, NULL); 
    
    if (x != 0)
    	printf("BOOM! counter=%d\n", x);
    else
    	printf("OK counter=%d\n", x);
        
    pthread_mutex_destroy(&m);
}

void *thread_increment (void *arg) {

    int i, val;
    for (i=0; i< ITER ; i++) {
    	pthread_mutex_lock(&m);
    	val = x;
    	printf("%u:%d\n",(unsigned int) pthread_self(), val);
    	x = val + 1;
    	pthread_mutex_unlock(&m);
    }
    
	pthread_exit(NULL);
}

void *thread_decrement (void *arg) {

    int i, val;
    for (i=0; i< ITER ; i++) {
        pthread_mutex_lock(&m);
        val = x;
        printf("%u: %d\n", (unsigned int) pthread_self(), val);
        x = val - 1;
        pthread_mutex_unlock(&m);
    }
    
	pthread_exit(NULL);
}

 

---

[semaphore.h 예시]

  세마포는 위에서 소개된 동기화 방식의 Generalized 된 버전이다. 상호배제 전략과 조건동기화 전략에 모두 사용될 수 있다. 위에서 설명했던 상호배제에서는 flag = 1 이면 자원이 사용중이라 대기해야하고, flag = 0 이면 바로 사용가능한 상태였다. 즉 Critical Section 에 들어갈 수 있는 실행흐름이 단 한개이다. 근데 세마포는 Critical Section에 들어갈 수 있는 실행흐름의 개수를 여러개로 설정할 수 있다. 상호배제의 측면에서는 자원의 개수로 볼 수 있고, 조건동기화 측면에서는 조건(상태)로 볼 수 있다. 

상호배제 측면에서의 Semaphore

  semWait 함수를 통해서 lock 을 얻을 수 있는지 확인하는데, lock이 1 이상이면 lock을 얻고 critical section으로 진입한다. 이때 lock 습득 유무에 상관없이 semWait 함수 마지막에 lock 값을 1씩 감소시킨다. 위에서 설명했던 spin_wait 방식과 다르게, 자원에 접근하지 못할때는 대기큐에 들어가서 sleep 한다. 

  자원을 다 사용하면 semSignal 함수를 통해서 lock 을 1개 release 한다. 이 때 lock 이 0 이하면, sleep 하고 있는 다른 프로세스가 있다는 의미이므로, signal을 발생시켜서 대기중인 다른 프로세스를 깨운다. 시그널 발생 유무와 상관없이 semSignal 함수 마지막에는 lock 값을 1씩 증가시킨다.

  

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define ITER 1000

void *thread_increment(void *arg);
void *thread_decrement(void *arg);
int x;
sem_t s;

int main() {

    sem_init(&s, 0, 1); // binary semaphore

    pthread_t tid1, tid2;	
    pthread_create(&tid1, NULL, thread_increment, NULL);
    pthread_create(&tid2, NULL, thread_decrement, NULL);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    
    if (x != 0)
    	printf("BOOM! counter=%d\n", x);
    else
        printf("OK counter=%d\n", x);
    sem_destroy (&s);
}

void * thread_increment (void *arg) {

    int i, val;
    for (i=0; i< ITER ; i++) {
        sem_wait(&s);
        val = x;
        printf("%u:%d\n",(unsigned int) pthread_self(), val);
        x = val + 1;
        sem_post(&s);
    }
    pthread_exit(NULL);
}

void * thread_decrement (void *arg) {

    int i, val;
    for (i=0; i< ITER ; i++) {
        sem_wait(&s);
        val = x;
        printf("%u: %d\n", (unsigned int) pthread_self(), val);
        x = val - 1;
        sem_post(&s);
    }
    pthread_exit(NULL);
}