[OS] Process Synchronization(2) - 프로세스 동기화

동기화 하드웨어

---

• 단일 프로세서 시스템의 경우 공유된 변수를 변경하는 동안에 인터럽트를 발생할 수 없도록 하면 위와 같은 문제를 보다 쉽게 해결할 수 있다.
• 인터럽트 억제 방법을 이용한 임계 구역 문제의 해결책

do{
	disable interrupt
    critical section
    enable interrupt
    remainder section
 }while(1);

• 다중 프로그래밍에 큰 영향을 주므로 효율적인 해결책은 아니다.
• 다중 프로세서 시스템에서는 인터럽트가 발생할 수 없도록 하더라도 여전히 두 프로세서에서 두 프로세스가 동시에 실행될 수 있어 임계 구역 문제를 해결할 수 없다.
• 이 때문에 인터럽트를 억제하는 방법 대신 대부분의 시스템은 이런 문제를 해결할 때 사용할 수 있는 특수한 하드웨어 명령어를 제공한다. 이 명령어는 원자적으로(이 명령어를 수행하는 동안에는 인터럽트되지 않음)
• 한 워드를 검사하고 수정할 수 있도록 해주거나 두 워드의 값을 교환할 수 있도록 해준다.

 

 

 

TestAndSet 명령어

boolean TestAndSet(boolean &target){
	boolean rv = target;
    target = true;
    return rv;
}

이 명령어는 원자적으로 실행되므로 두 프로세스가 이 명령어를 병행으로 수행하더라도(두 프로세서에서 동시에 수행되더라도) 임의 순서로 순차적으로 수행된다. 시스템이 TestAndSet 명령을 제공하면 lock이라는 boolean형 변수를 선언하고, 이것을 false로 초기화하여 상호 배제를 다음과 같이 쉽게 구현할 수 있다.

do{
	while(TestAndSet(lock));
    critical section
    lock = false;
    remainder section
}while(1);

 

 

 

Swap 명령어

void Swap(boolean &a, boolean &b){
	boolean temp = a;
    a = b;
    b = temp;
}

시스템이 Swap 명령을 제공하면 lock이라는 광역 불형 변수(공유 변수)와 프로세스마다 key라는 지역 변수를 선언하여 상호 배제를 다음과 같이 구현할 수 있다. 이 때 lock은 false로 초기화한다.

 

 

do{
	key = true;
    while(key==true) swap(lock key);
    critical section
    lock = false;
    remainder section
} while(1);

그러나 TestAndSet과 Swap을 이용하는 두 알고리즘은 모두 상호배제만 충복할 뿐 한계 대기는 충족되지 않는다. 이 두 명령이 실행되는 순서에 따라 한 프로세스는 영구적으로 임계 구역에 진입을 못할 수 있다.

 

 

 

• TestAndSet을 이용한 임계 구역 문제의 모든 요구사항을 충족하는 Algorithm

do{
	waiting[i] = true;
    key = true;
    while(waiting[i] && key)
    	key = TestAndSet(lock);
    waiting[i] = false;

    critical section

    j = (i+1) % n;
    while((j != i) && !waiting[j])
    	j = (j+1) % n;

    if(j==i) lock = false;
    else waiting[j] = false;

    remainder section
}while(1);

• 상호배제 : lock은 false로 초기화된다. 따라서 TestAndSet을 제일 먼저 실행한 프로세스는 자신의 지역 변수 key값이 false가 되어 진입한다. 다른 프로세스들은 진입한 프로세스가 임계 구역을 끝내고 출구 지역에서 lock을 false로 하거나 waiting[j]를 false로 변경해 줄 때까지 진입할 수 없으므로 상호 배제가 충족된다.
• 진행 : 임계 구역을 끝낸 프로세스는 출구 지역에서 다른 프로세스가 진입할 수 있도록 lock을 false로 하거나 waiting[j]를 false로 변경해주므로 다른 프로세스는 결국에는 진입할 수 있다.
• 한계 대기 : 임계 구역을 끝낸 프로세스는 출구 지역에서 i+1부터 i-1까지 순환 순서로 다른 프로세스의 waiting을 조사한다. 이 때 첫 번째로 waiting 값이 true인 것을 false로 변경해준다. 또한 기다리고 있는 프로세스가 없으면 lock을 false로 변경해준다. 따라서 최대 다른 프로세스가 한 번씩 진입한 후에는 임계구역에 진입할 수 있다.
• 동기화 하드웨어나 소프트웨어 접근 방식의 공통된 문제점 : 모두 어느 한 프로세스가 임계 구역에 있으면 진입하고자 하는 다른 프로세스는 "busy waiting"을 해야 한다.

 

 

세마포어

---

세마포어(semaphore) S는 정수 변수로서 초기화를 제외하고는 두 가지 연산 wait와 signal을 통해서만 접근할 수 있다. 이 두 연산은 원자적이다.

• wait 연산

wait(S){
	while(S <= 0);
    S--;
}

• signal 연산

signal(S) {
	S++;
}

 

사용법

• 세마포어를 이용한 n 프로세스 임계 구역 문제에 대한 해결책

do{
	wait(mutex);
    critical section
    signal(mutex);
    remainder section
}while(1);

모든 프로세스는 mutex라는 세마포어를 공유하며, mutex는 1로 초기화된다.

• wait 연산을 제일 먼저 실행하는 프로세스는 mutex 값이 1이므로 이 값을 0으로 바꾸고 임계 구역에 진입할 수 있다. 이 프로세스가 출구 지역에서 mutex값을 1로 다시 바꾸어주면 다른 프로세스가 진입을 할 수 있다.
• 이 방법도 앞서 본 TestAndSet과 Swap명령어를 이용한 방법과 마찬가지로 한계 대기는 충족하지 못한다.

 

 

병행으로 수행되는 두 개의 프로세스 P[1]과 P[2]는 각각 S(1)과 S(2) 프로그래밍 문장을 가지고 있다고 하자. 또한 S(1)이 실행된 다음에 S(2)가 실행되어야 한다. 이런 동기화 문제는 세마포어를 이용하여 쉽게 해결할 수 있다. 두 프로세스는 0으로 초기화된 synch라는 세마포어를 공유한다.

- P[1]
  S[1];
  signal(synch);
- P[2]
  wait(synch);
  S[2];

 

 

구현

• busy waiting을 하는 세마포어를 spinlock이라 한다. spinlock은 문맥 전환이 필요없어 오래 동안 busy waiting을 하지 않는다면 효과적인 방법이다.
• busy waiting을 제거하기 위해서는 wait 연산을 수행하였을 때 세마포어 값이 양수가 아니면 스스로 블록하도록 해야 한다.
• busy waiting이 없는 세마포어 구조

typedef struct{
	int value;
    struct process *L;
} semaphore;

• busy waiting이 없는 wait 연산

void wait(semaphore S){
	S.value--;
    if(S.value < 0){
    	add this process to S.L;
        block();
    }
}

여기서 큐는 FIFO 방식

• busy waiting이 없는 signal 연산

void signal(semaphore S){
	S.value++;
    if(S.value <= 0){
    	remove a process P from S.L;
        wakeup(S.L);
    }
}

• busy waiting이 있는 세마포어의 경우에는 세마포어 값이 음수가 되지 않는다. 그러나 busy waiting이 없는 세마포어의 경우에는 세마포어 값이 음수가 될 수 있으며, 음수이면 이것은 세마포어를 기다리는 프로세스의 수를 나타낸다.
• 세마포어가 올바르게 동작하기 위해서는 wait와 signal 연산은 반드시 원자적으로 수행되어야 한다. 이를 위해 단일 프로세서 시스템에서는 인터럽트 억제 방법을 사용할 수 있다. 그러나 다중 프로세서 시스템에서는 이 방법이 가능하지 않다. 따라서 특수한 하드웨어 명령을 제공하지 않으면 소프트웨어 해결법을 사용해야 한다.

 

 

이진 세마포어

---

• 지금까지 사용한 세마포어는 가질 수 있는 값의 범위가 정해져 있지 않은 카운팅 세마포어이다.
• 세마포어가 가질 수 있는 값의 범위가 0 또는 1로 제한되어 있으면 이진 세마포어라 한다.
• busy waiting이 없는 이진 wait 연산

void wait(semaphore S){
	if(S.value == 1)
    	S.value = 0;
    else{
    	add this process to S.L;
        block();
    }
}

• busy waiting이 없는 이진 signal 연산

void signal(semaphore S){
	if(S.L is empty)
    	S.value = 1;
    else{
    	remove a process P from S.L;
        wakeup(S.L);
    }
}

• 카운팅 세마포어는 두 개의 이진 세마포어 S[1]과 S[2]를 이용하여 구현할 수 있다. 이 때 추가로 카운팅 세마포어의 초기값으로 초기화된 정수 변수 C를 사용한다.
• wait 연산

void wait(semaphore S){
	wait(S1);
    C--;
    if(C < 0){
    	signal(S1);
        wait(S2);
    }
    signal(S1);
}

• signal 연산

void signal(semaphore S){
	wait(S1);
    C++;
    if(C<=0) signal(S2);
    else signal(S1);
}