[운영체제] 5. Race Conditions(1)

2022.03.26 - [컴퓨터 공학/0 +운영체제] - [운영체제] 4. Processes and Threads(프로세스와 스레드)

[운영체제] 4. Processes and Threads(프로세스와 스레드)

 

 

 

멀티 프로세스, 멀티 스레드 개발환경에서 공유자원을 사용하지 않는 경우는 없을 것이다.

이에 따라 여러가지 문제점들이 나오기 시작했고, 사람들은 이러한 상태(Race Conditions)을 해결하기 위해 여러가지 연구를 진행한다..!

 

 

---

https://suintodev.tistory.com/4

병행 프로세스와 상호배제 - 데커와 피터슨의 알고리즘

 

Race Conditions

2개 이상의 프로세스 또는 2개 이상의 스레드가 하나의 공유자원(Critical Regions)에 접근하는 상태를 말한다.(경쟁상태)

따라서 어떤 프로세스/스레드가 먼저 실행되는지에 따라 결과가 달라질 수 있는 상황이다.

race Condition이 있는 코드를 예측하는 것은 거의 불가능에 가깝기 때문에, 최대한 경쟁조건을 피해야한다. 즉, 동시에 공유메모리, 공유 파일, 기타 공유와 관련된 문제를 피할수 있도록 조치해야 한다.

 

다음과 같은 조건을 만족하면 Race Condition을 피할 수 있다...!!!😍

1. Mutal Exclusion(상호 배제)
   • 하나의 프로세스/스레드가 임계영역에 들어가 있으면 다른 프로세스/스레드는 들어갈 수 없다.
2. Progress(진행)
   • 임계 영역에 들어간 프로세스가 있지 않는 이상 임계 영역에 들어가려는 프로세스가 있으면 들어가게 해줘야한다.(Avoid deadlock)
     • Deadlock(교착상태)
       
       • 둘 이상의 프로세스/스레드가 다른 프로세스/스레드가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황
       • 자원을 얻지 못해 다음 처리를 못하는 상황(주로 동일 자원을 점유할때 자주 발생)
3. Bounded Waiting(한정 대기)
   • 상호배제로 유한 시간 내에는 반드시 임계영역에 들어갈 수 있어야 한다.(Avoid Starvation)
     • Starvation
       • 특정 프로세스/스레드가 자원을 독점하고 있어 다른 프로세스/스레드가 원하는 자원을 계속 할당받지 못하는 상태(부족한 자원을 점유하기 위해 경쟁 할때 자주 발생)
4. 프로세스의 상대적인 속도에 대해서 어떤 가정도 해서는 안된다. 😤
   • CPU의 성능과 속도에 영향 받아서는 안됨

 

 

Deadlock과 Starvation 똑같이 자원을 할당받지 못해서 기다리는 상태이다.

Deadlock은 신영이와 세웅이가 필기를 하기위해서 공책과 연필이 필요한데
필기를 하기위해 세웅이는 연필을 갖고있고, 신영이는 책을 갖고 있는 상황에서 서로 책내놔!, 연필내놔! 하는 상태이다.

Starvation은 세웅이가 연필과 책을 계속 갖고있어서 신영이가 필기를 하지 못하는 상황이다.

 

---

 

상호배제는 한 프로세스가 공유자원을 사용하고 있을 때 다른 프로세스들이 사용하지 못하게 배제시키는 제어 기법이다.

Mutual Exclusion with Busy Waiting

• Disabling interrupt
• Lock variables
• Strict alternation
• Perterson's Algorithm
• The TSL instruction

 

2개 프로세스의 상호 배제

Strict alternation

/***
* 프로세서 A
*/
while(true) {
    while(turn != A); //turn이 A이면 break
    V++; //critical section
    turn = B;
    saveData(V);
}

/***
* 프로세서 B
*/
while(true) {
    while(turn != B); //turn이 B이면 break
    V++; //critical section
    turn = A;
    saveData(V);
}

turn 변수를 이용하여 프로세스A와 프로세스B 중 하나에 순서를 준다.

turn이 A일때 프로세스B는 대기하고 프로세스 A는 임계영역에 들어가고 turn을 B로 변경한다.

turn이 B일때 프로세스A는 대기하고 프로세스 B가 임계영역에 들어가고 turn A로 변경.

따라서 상호배제를 만족한다.

 

하지만, turn이 A로 시작해서 프로세스A가 임계영역에 들어간 후 turn을 B로 바꾸고 saveData(V)를 실행 중인 상태이고 곧바로 프로세스B가 turn이 B가 되어 임계영역에 들어간 후 turn를 A로 바꾸고 saveData(V) 실행을 마친 상태라면...

둘 다 임계영역에 들어가지 못하므로 Progress를 만족하지 못하고, 프로세스B가 무한정 대기인 상태이므로 Bounded Waiting도 만족하지 못한다....

 

 

---

 

 

Using array

/***
* A 프로세스의 구조
*/
while(true){
    flag[A] = true;
    while(flag[B] == true); //flag[B]가 false이면 break
    V++; //critical section
    flag[A] = false;
}

/***
* B 프로세스의 구조
*/
while(true){
    flag[B] = true;
    while(flag[A] == true); //flag[A]가 false이면 break
    V++; //critical section    
    flag[B] = false;
}

 

초기에 flag[A], flag[B]는 false로 초기화 되어있다.

얼핏 보면 문제가 없어 보이지만, 두 프로세스가 동시에 진입한다고 가정했을때 두 프로세스는 영원히 while문을 돌게 된다.

Progress를 충족하지 못하며, 두 프로세스 서로 flag[A], flag[B] false가 되기를 기다리는 이러한 상태를 DeadLock(교착상태)라고 한다.

 

 

---

 

 

Dekker's Algorithm

/***
* A 프로세스의 구조
*/
while(true){
    flag[A] = true; 
    while(flag[B]){ //falg[B] false이면 탈출
    	if(turn == B){     
            flag[A] = false; // 프로세스B의 while(flag[A])에서 탈출해 임계영역에 들어가게 해줌            
            while(turn == B); //turn A이면 탈출            
            flag[A] = true; // 프로세스B가 2번 임계영역에 못들어가게 해줌.            
        }        
    }    
        V++; //critical section        
        flag[A] = false; // 프로세스B의 while(flag[A])에서 탈출해 임계영역에 들어가게 해줌   
        turn = B; // 프로세스B가 while(turn == A)에서 탈출해 임계영역에 들어가게 해줌
}

/***
* B 프로세스의 구조
*/
while(true){
    flag[B] = true; 
    while(flag[A]){ //falg[A] false이면 탈출
    	if(turn == A){     
            flag[B] = false;            
            while(turn == A); //turn B이면 탈출             
            flag[B] = true;            
        }        
    }    
        V++; //critical section        
        flag[B] = false;        
        turn = A;
}

2개의 프로세스를 위한 최초의 정확한 상호배제 알고리즘이다.

flag[A], flag[B]의 초기값 false이고, turn 초기값 A라고 하자.

프로세스A, B 동시에 진입한다고 했을 때 flag[A], flag[B]가 true로 변하면서 첫 번째 while문에 들어간다.

프로세스A는 turn 조건에 의해서 대기 상태로 변하고 (while(flag[B]))

프로세스B는 flag[B]를 false로 변화시킨다. 그리고 두 번째 turn조건에 의하여 대기 상태로 변한다.

그때 프로세스A는 flag[B]가 false이기 때문에 탈출하여 임계영역에 들어가게 된다.

이때, flag[A]를 false로 turn을 B로 바꾼다.

그러면 프로세스 B는 while(turn == A)를 탈출하고 flag[B]를 true로 바꾼다. 또한 이때 flag[A]가 false이므로 while(flag[A])를 탈출하고 임계영역에 들어가게 된다.

즉, turn값이 A이면 프로세스 A가 임계영역에 진입하고, turn값이 B이면 프로세스 B가 임계영역에 진입한다.

하지만, 이는 너무 복잡하다.... ㅠ0ㅠ

 

 

---

 

 

Perterson's Algorithm

/*
* A 프로세스의 구조
*/
while(true){
    flag[A] = true;    
    turn = B;    
    while(flag[B] && turn == B);    
    V++; //critical section    
    flag[A] = false;
}

/*
* B 프로세스의 구조
*/
while(true){
    flag[B] = true;    
    turn = A;    
    while(flag[A] && turn == A);    
    V++; //critical section    
    flag[B] = false;
}

flag[A], flag[B] 의 초기값은 false이고, turn의 초기값은 A라고 하자.(A, B 상관 없다.)

프로세스A를 임계영역에 들어가고 싶다는 의미로 flag[A]를 ture로 만든다.

turn을 B로 설정하고 while(flag[B] && turn == B);을 수행한다. 이때 프로세스B가 임계영역에 들어간다는 의사표현을 하지 않는다면 flag[B]가 false이므로 while(flag[B] && turn == B);를 탈출하고 프로세스 A는 바로 임계영역에 들어간다.

그러나 만약 두 프로세스가 동시에 시작한다고 한다면, 그중에서라도 늦게 시작한 프로세스가 turn 값을 정할 수 있기 때문에 turn변수를 늦게 수행된 프로세스가 내부 while문을 돌면서 대기한다.

임계영역에 들어갔던 프로세스는 나오면서 자신의 flag를 false로 만들면서 다른 프로세스가 임계영역에 들어가게 해준다.

turn이 A이면 B프로세스가, turn이 B이면 A 프로세스가 먼저 임계영역을 수행한다.

Dekker's Algorithm보다 쉽군..!😍

 

 

---

 

 

Bakery Algorithm

n개의 프로세서에서 race condition을 해결하기 위해 개발

빵집을 비유로 고객들에게 번호표를 부여하여, 번호표를 기준으로 먼저 처리해야할 일들의 우선순위를 부여하는 알고리즘.

모든 고객들은 맨 처음 번호표를 부여 받는다. 그리고 자기 순서가 올때까지 대기한다. 이러한 방법으로 프로세스들이 공유자원에 동시에 접근하지 못하도록 한다.

일단 이것을 기억하자..!

(a, c) < (c, d)
process ID가 작은 값이 먼저 임계영역에 들어간다.
if( (a < c) || ( (a == c) && (b < d) ) )

 

process Pi {
    choosing[i] = true; //번호표를 받기 시작함.
    number[i] = max(number[0], number[1], 
                    .... , number[n-1])+1; //자신의 번호표가 제일 나중이라는 것을 알려주기 위해 +1을 한다.
    choosing[i] = false; //번호표 받음.
    for(t = 0; t < n; t++) { //프로세스 갯수만큼 for문 실행
        if(t == i) continue; //내 차례면 아래 while(choosing[t])을 건너뛴다.
        while(choosing[t]); //다른 프로세스가 번호표를 받았다고 할때 까지 대기
        while((number[t] != 0) && (number[t], t) < (number[i], i))); //번호표 비교해서 내번호표가 더 작은 숫자면 탈출!
    }
    v++; //critical section
    number[i] = 0; //임계영역을 실행한 후 초기화.
}

 

 

 

---

 

 

 

위에서 알아 본 것처럼 임계구역에서 해야할 일은 단순한데

Race Condition을 피하기 위해서는 복잡한 코드를 구현해야한다... ㅠ0ㅠ

그래서 사람들은 H/W의 도움을 받는 것을 생각했다..😊

https://ko.wikipedia.org/wiki/%EA%B2%80%EC%82%AC%EC%99%80_%EC%A7%80%EC%A0%95

검사와 지정 - 위키백과, 우리 모두의 백과사전

 

---

 

The TSL Instruction

 

Lock Signal을 보낸 CPU만 접근

 

검사와 지정(test-and-set) 명령어는 동시성을 제어하기 위한 동기화 명령어 중 하나로서, 하드웨어의 도움을 받아 수행된다. 이것을 활용하면 상호 배제 등을 편리하게 구현할 수 있다.

이 명령어는 원자성을 가져 명령어가 실행되는 도중에 인터럽트될 수 없으며,

명령어 내에서 수행되는 두 명령어 "boolean initial = lock" 과 "lock = true"는 동시에 실행되어 둘 다 실행되거나

둘 중 하나가 실행되지 않으면 나머지 하나도 실행되지 않는다.

 

function TestAndSet(boolean_ref lock) {
    boolean initial = lock
    lock = true
    return initial
}

do {
    while(TestAndSet(&lock))
        ; // do nothing
        // critical section
    lock = false;
        // remainder section
} while(true);

• lock 값이 true일 때는 initial 값이 항상 true이기 때문에 TestAndSet은 항상 true를 반환한다. 따라서 프로세스는 while(TestAndSet(&lock)); 루프를 빠져나가지 못한다. 이것은 다른 프로세스 하나가 임계구역(Critical Section)에 진입했음을 의미한다.
• 임계구역에 진입했던 프로세스는 임계구역을 빠져나오면서 lock = false;를 수행한다.
• 그때 대기중이던 프로세스 중 가장 먼저 TestAndSet을 실행한 프로세스가 while(TestAndSet(&lock)); 루프에서 false를 반환받고 while문을 빠져나오며 임계구역에 진입한다.
• 이 과정에서 boolean initial = lock; 과 lock = true;는 동시에 실행되므로 다른 프로세스들은 계속 while(TestAndSet(&lock)); 루프를 빠져나오지 못하고 계속 대기한다.
• 임계구역에 진입했던 프로세스는 임계구역을 빠져나오면서 lock = false;를 수행한다.
• 위의 과정이 반복된다.

 

Critical section에 들어가고자 하는 프로세스는 enter_region 을 부른다.

이 루틴에서 lock이 해제될 때까지(lock이 0이 될때까지) busy waiting 상태로 기다리게 된다.(lock이 1이라는 것은 다른 프로세스가 임계영역을 사용중이라는 뜻)

Critical section에서 빠져 나올 때는 leave_region 을 부른다.

 

 

---

 

 

Spin Lock

https://goodgid.github.io/Spin-Lock/

스핀락(Spin Lock)

 

우아한 형제들 채용 인원이 k명인데 n명이 지원 했다. (k < n)
이경우 k명을 제외한 인원(n-k)명은 예비 번호를 받고 기다리게 된다.

아쉽게도 세웅이와 신영이는 k명에 포함되지 않아 예비번호를 받게 되었다.. ㅠㅠ
기다리다 지친 세웅이는 연락이 오기를 기다리다가 잠이 들었고,
신영이는 언제 연락이 올지 모른다는 불안감에 자지 않고 기다렸다.

 

• 락 중에는 이런식으로 접근하는 락이 있다.
• 이게 바로 세마포어 개념이다.
• 세마포어는 보통 자원에 관계된 락이다.
• 그래서 락을 걸때 특정 수 만큼의 카운트(k)로 접근해야한다.
• 이러한 락을 슬립(sleep) 가능한 락이라고 한다.
  • 또한 뮤텍스라는 락이 있는데 이는 우리가 앞서 배운 락이다.
  • 결국 이것도 세마포어긴 한데 세마포어는 다음에 더 알아보도록하자..!

 

신영이는 자지 않고 계속 전화를 기다리고 있는데, 이처럼 자원을 얻기 위해 sleep하지 않고 계속 대기하는 락을 스핀락 이라고 한다.

다시말하면, 스핀락은 다른 프로세스나 스레드가 lock을 소유하고 있다면 sleep하지 않고 lock이 반환 될때 까지 계속 확인하며 기다린다.

세마포어, 뮤텍스는 데이터를 memory에 쓰고 sleep하는 프로세스를 깨워 context switching하는 작업은 비싼 cost가 든다.

그렇기 때문에 작은 작업에서는 스핀락이 세마포어 혹은 뮤텍스보다 효율적이라고 할 수 있다.

 

스핀락에는 2가지 버전이 있다.

void spinLockVersion1(spinlock_t *s) {
	while(test_and_set(s) != 0); //lock변수가 0이 될때 까지 lock signal을 계속 전송 -> 성능저하
}

void spinLockVersion2(spinlock_t *s) {
	while(test_and_set(s) != 0) {
    	while(*s != 0); //lock변수가 0이 될때 까지 memory만 읽음
    }
}