[운영체제] 임계구역(Critical section) 문제 해결 (조건, 방법)

Critical section이란?

공유 자원 접근 순서에 따라 실행 결과가 달리지는 프로그램 영역

(출처: 쉽게 배우는 운영체제)

 

여러 프로세스가 변수, 메모리, 파일 등을 공유하면서, 접근 순서에 따라 실행 결과가 달라, 예상이 불가능한 구역을 critical section이라고 한다.

 

가장 간단한 예로 만약 money=5000이 있고, 프로세스가 2개가 있다고 가정해보자.

process1은 money-=1000을 하고

process2는 money+=500을 한다고 해보자

 

process1은 money가 5000원인 것을 확인하고 1000을 빼려는 작업을 시작하고,

process2도 money가 5000원인 것을 확인하고 500을 더하려는 작업을 시작한다.

 

이렇게 되면 process1이 먼저 작업을 끝내면 money는 process2가 바꿔놓은 5500이 되어 있고,

process2가 먼저 작업을 끝내면 money는 process1이 바꿔놓은 4000이 되어 있다.

 

공유자원인 money을 사용할 때, 프로세스들 간의 서로의 작업을 무시하고 덮어쓰기 해버렸기 때문에 이러한 문제가 발생한 것이다.

따라서 공유자원을 사용할 때는 규칙이 필요하다.

 

---

Critical section 문제 해결 조건

critical section의 문제를 해결할 수 있는 조건 3가지가 있다.

이 3가지를 지켜야 critical section 문제를 완벽히 해결 수 있다.

 

1. 상호 배제 (Mutual exclusion)

ciritical section 내에서는 한번에 하나의 프로세스만 접근 가능하다.

 

2. 한정 대기 (Bounded waiting)

어떤 프로세스도 ciritical section에 접근하지 못해 무한정 대기해서는 안된다.

언젠간 접근할 수 있어야 한다.

 

3. 진행 (progress)

한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.

 

---

Critical section 해결 알고리즘

 

1. 피터슨 알고리즘

// 공유변수 
boolean lock1 = false
boolean lock2 = false
int turn = 1


// process 1
lock1 = true
turn = 2
while (lock2==true and turn==2) {}
(critical section 접근)
lock1 = false


// process 2
lock2 = true
turn = 1
while (lock1==true and turn==1) {}
(critical section 접근)
lock2 = false

lock1, lock2, turn이라는 변수를 사용해서 임계구역 문제를 해결했다.

변수의 사용의 의미를 직관적으로 분석해보자면

 

lock1 -> prcess1이 임계구역 접근 시도를 표현

lock2 -> process2가 임계구역 접근 시도를 표현

turn ->   먼저 양보하는 변수 겸 무한정 대기를 방지하는 변수

 

process1의 관점에서 보자면 먼저 lock1을 true로 바꿈으로서 임계구역의 진입하고 싶다는 의사를 표하고, turn을 2로 설정했다.

그리고 만약 process2도 임계구역에 진입하고 싶었다면 (lock2==true) 양보해서 (turn==2) process2가 임계구역을 사용할 때 까지 기다린다. (while문)

process2가 임계구역 사용이 끝나서 lock2=false로 바꿨음으로 process1도 while문을 빠져나와 lock1을 false로 바꿔준다.

 

조건	조건 충족 여부	근거
상호 배제	O	lock변수를 통해 다른 프로세스가 접근하고자 할 때는 while문에서 대기한다.
무한정 대기	O	turn변수을 사용하기 때문에 각 프로세스의 맨첫 줄 lock1=true, lock2=true을 수행 후 타임아웃이 걸려도 turn변수가 1이냐 2이냐에 따라 어느 한 프로세스는 while문에서 빠져나오게 된다.
진행	O	만약 process2가 임계구역에 접근하려고 하지 않더라도 process1은 이에 영향을 받지 않고 임계구역을 진입할 수 있다. 왜냐하면 lock2가 false이기 때문에 바로 while문을 빠져나오기 때문이다.

 

 

2. 데커 알고리즘

위의 피터슨 알고리즘보다 코드가 조금 더 복잡하다.

 

// 공유변수
boolean lock1=false
boolean lock2=false
int turn=1


// process1
lock1=true
while (lock2 == true) {
	if (turn==2) {
    	lock1=false
        while (turn==2)
        lock1=true
    }
}
(임계구역 진입)
turn=2
lock1=false


// process2
lock2=true
while (lock1 == true) {
	if (turn==1) {
    	lock2=false
        while (turn==1)
        lock2=true
    }
}
(임계구역 진입)
turn=1
lock2=false

lock1, lock2, turn 변수를 사용해서 임계구역 문제를 해결했다.

(위와 똑같다)

변수의 사용의 의미를 직관적으로 분석해보자면

 

lock1 -> prcess1이 임계구역 접근 시도를 표현

lock2 -> process2가 임계구역 접근 시도를 표현

turn ->   먼저 양보하는 변수 겸 무한정 대기를 방지하는 변수

 

피터슨 알고리즘과 다른 점은 피터슨에서는 while문 조건을 turn과 lock변수를 동시에 확인했지만,

데커 알고리즘에서는 먼저 lock변수로 다른 프로세스도 임계구역에 접근하고자 했는지를 먼저 살피고,

turn변수가 자신이 아니라면 (process1은 turn=1, process2는 turn=2), lock변수를 false로 바꿔 한발 양보하고,

turn변수가 상대방이 아닐때까지 while문에서 대기 하다가 lock변수를 다시 true로 바꾼다.

그리고 임계구역이 끝난 후에는 turn을 상대방으로 바꾸고, lock도 false로 바꾼다.

 

조건	조건 충족 여부	근거
상호 배제	O	lock변수를 통해 다른 프로세스가 접근하고자 할 때는 while문에서 대기한다.
무한정 대기	O	임계구역이 끝나면 turn변수를 상대 프로세스로 바꿈으로써, 상대 프로세스도 임계구역에 진입할 기회를 준다.
진행	O	만약 process2가 임계구역에 접근하려고 하지 않더라도 process1은 이에 영향을 받지 않고 임계구역을 진입할 수 있다. 왜냐하면 lock2가 false이기 때문에 바로 while문을 빠져나오기 때문이다.

 

3. 세마포어

세마포어는 간단하고 사용하기 쉽다!

한 프로세스가 임계구역을 진입하면 다른 프로세스들은 앞의 프로세스가 작업을 마칠 때까지 기다리고, 

앞의 프로세스가 작업이 끝나면 다른 프로세스들에게 동기화 신호를 보낸다.

 

Semaphore(n)

P()
(임계구역 진입)
V()


function Semaphore(n){
    RS = n // n=공유 가능한 자원의 수, RS=전역변수
}
 
function P() {
    if RS>0 then RS-=1
    else block() //wake_up()신호 보낼 때까지 대기
}

function V() {
    RS+=1
    wake_up() // 임계구역에 진입해도 좋다는 신호 보냄
}

조건	조건 충족 여부	근거
상호 배제	O	공유 가능한 자원이 남아 있다면 진입하고, 없다면 block()으로 진입하기를 대기한다.
무한정 대기	O	임계구역이 끝나면 wake_up()을 통해 다른 프로세스가 진입 할 수 있도록 신호를 준다. 그 신호를 받은 프로세는 block()에서 벗어나 임계구역을 진입할 수 있다.
진행	O	다른 프로세스 방해 없이 공유 가능한 자원이 있다면 바로 임계구역 진입가능하다.

 

4. 모니터

공유자원을 내부적을 숨기고 공유 자원에 접근할 수 있는 인터페이스를 제공함으로써 자원을 보호하고 프로세스를 동기화 시킨다.

커널이 하드웨어 접근을 시스템 콜을 통해서만 받아들이는 것과 비슷하다.

세마포어의 경우 단순하도 3가지 조건을 충족하지만, 만약 P(), V()코드를 순서를 바꿔서 실행하거나, 사용하지 않는다면 임계구역을 보호할 수 없다.

따라서 인터페이스로만 접근가능하도록 보호하는 것이 안전한다. 그게 모니터 방식이다.

 

monitor shared_balance {
    private:
    	int balance = 0;  // 공유 자원 
        boolean busy = false;
        condition mon;
        
    public:
    	increase(int amount) {
            if (busy==true) mon.wait(); // 다른 프로세스가 사용 중이라면 대기 
            busy=true; // 공유자원 사용중이라는 것을 알림 
            balance=balance + amount; 
            mon.signal(); // 대기 중인 프로세스에게 신호보냄
        }
}

조건	조건 충족 여부	근거
상호 배제	O	busy변수를 통해 다른 프로세스가 임계구역에 진입했다면 대기한다.
무한정 대기	O	임계구역이 끝나면 mon.signal()을 통해 다른 프로세스가 진입 할 수 있도록 신호를 준다. 그 신호를 받은 프로세는 mon.wait()에서 벗어나 임계구역을 진입할 수 있다.
진행	O	다른 프로세스 방해 없이 busy가 false라면 바로 임계구역 진입가능하다.

 

 

---

ref

쉽게 배우는 운영체제 - 조성호 (한빛아카데미)