[운영체제] 경쟁 조건(Race Condition)과 임계 구역(Critical Section)

프로세스 간 메시지를 전송하거나, 공유메모리를 통해 공유된 자원에 여러 개의 프로세스가 동시에 접근하면 임계 구역(Critical Section) 안에서 경쟁 조건(Race Condition)이 생길 수 있다. 

이를 해결하기 위해 데이터를 한번에 하나의 프로세스만 접근할 수 있도록 제한을 두는 동기화 방식을 취해야 한다.

동기화 도구에는 대표적으로 뮤텍스(Mutex)와 세마포어(Semaphore)가 있다. 

이들은 모두 공유된 자원의 데이터를 여러 스레드/프로세스가 접근하는 것을 막는 역할을 한다.

경쟁 조건 (Race Condition)

경쟁 조건(race condition)은 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 말하며, 공유 자원 접근 순서에 따라 실행 결과가 달라지는 상황을 말한다. 즉, 타이밍이나 순서 등이 결괏값에 영향을 줄 수 있는 상태를 말하는 것이다.(동시성 문제라고도 한다.)

위의 그림과 같이, 사람A와 사람B가 계좌에 동시에 1만원을 넣으려고 한다.

하지만 B와 A는 동시에 17이라는 값을 가져와서 1만원을 더해 Write하기 때문에 은행에 19만원이 저장되어야 하지만

18만원이 저장되는 문제가 생겨버린다.

---

임계 구역(Critical Section)

임계 구역이란 둘 이상의 스레드가 동시에 실행될 경우 생길 수 있는 경쟁 조건(Race Condition)을 발생시킬 수 있는 코드 블록을 임계 구역이라고 한다.

 

임계 구역 해결 조건

critical section 문제를 해결할 수 있는 방법은 다음 3가지 조건을 만족해야 한다.

1. 상호 배제(mutual exclusion)
   • 한 프로세스가 임계구역에 들어가 있으면 다른 프로세스는 들어갈 수 없다.
2. 한정 대기(bounded wating)
   • 상호 배제 때문에 기다리게 되는 프로세스가 무한 대기하지 않아야 한다. 즉, 특정 프로세스가 임계구역에 진입하지 못하면 안 된다.
3. 진행의 융통성(progress flexibility, progress)
   • 임계구역에 프로세스가 없다면 어떠한 프로세스라도 들어가서 자원을 활용할 수 있다. 즉, 두 프로세스가 자원을 번갈아 쓴다고 가정할 때 한쪽에서 자원을 안쓰고 있다고 해서 다른 한 쪽 프로세스가 자원을 쓰고 싶어도 자신의 turn이 아니라고 기다리는 것은 효율적이지 못하다는 것이다.

임계 구역 해결 방법

critical section 문제를 해결하는 단순한 방법은 Lock을 사용하는 것이다. 즉, 한 프로세스가 critical section에 들어간다면 lock을 걸어놓아 다른 프로세스가 들어오지 못하게 하는 것이다.

그리고 프로세스가 critical section에서 빠져나오게 되면 lock을 해제하고 동시에 동기화 신호를 보내는 것이다.

동기화 신호는 다음 프로세스에게 critical section을 사용해도 좋다는 신호를 주는 것이다.

예제 코드

#include <stdio.h>
typedef enum { false , true} boolean;
extern boolean lock = false;
extern int balance;

int main(){
    while(lock == true);
    lock = true;
    balance = balance + 10;
    lock = false;
}

c언어에서는 boolean 변수가 없기 때문에 다음과 같이 typedef로 정의했다.

critical section에 문제가 되는 들어갈 변수는 balance이고, 잠금은 lock으로 걸어놓는다.

false이면 프로세스가 들어가 balance를 쓸 수 있고, true이면 기다리도록 한다.

---

상호 배제(mutual exclusion)

위의 예제는 IPC 방법으로 shared memory를 사용하는 것과 같다.

공유 변수 boolean lock은 shared memory에 있는 변수인 것이다.

프로세스 p1과 p2는 임계구역에 진입하기 전에 코드를 통해 임계구역에 잠금이 걸려 있는지 확인한다.

만약 lock이 true라서 잠겨져 있다면 다른 프로세스가 임계구역에서 작업을 하고 있다는 뜻이므로 잠금이 해제될 때까지 무한 루프를 돌면서 기다리게 된다.

임계구역에 있는 프로세스가 작업을 마치고 잠금을 해제하면 lock = false로 만들어주기 때문에 기다리고 있던 프로세스는 무한루프에 빠져나와 작업을 한다.

 

즉, lock = false는 임계구역을 사용해도 좋다고 다른 프로세스에 보내는 동기화 신호이다.

잠금이 풀려서 새로 임계구역에 진입하는 프로세스는 다른 프로세스가 진입하지 못하도록 잠금을 걸고 (lock = true) 작업을 하며, 작업을 마치면 다른 프로세스가 사용할 수 있도록 잠금을 해제한다.(lock = false)

 

이는 문제없이 작동할 것 같지만 일부 문제가 존재한다. 다음의 상황을 살펴보자.

위 그림에서 임계구역에 진입한 프로세스가 없다고 하자, 이런 상황에서 아래 순서대로 실행된다고 하면

1. 프로세스 P1은 while(lock == true) 문을 실행한다. 임계 구역에 프로세스가 없기 때문에 무한 루프를 빠져나온다. 그런데 이어서 다음 문장을 실행하려는 순간 자신에게 주어진 CPU 시간을 다해(timeout) ready 상태로 옮겨진다. context switching이 발생하고 프로세스 p2가 running 상태로 바뀐다.
2. 프로세스 P2는 while(lock == true) 문을 실행한다. 아직 프로세스 P1이 잠금을 걸지 않았기 때문에 lock은 여전히 false이며 프로세스 P2는 임계구역에 진입할 수 있다.
3. 프로세스 P1은 lock = true 문을 실행하여 임계구역에 잠금을 걸고 진입한다.
4. 프로세스 P2는 lock = true문을 실행하여 임계구역에 잠금을 걸고 진입한다. 결국 둘 다 임계구역 안에 진입하게 된다.

프로세스 P1은 while(lock == true) 문을 실행하고 나서 곧바로 lock = true 문을 실행해야 다른 프로세스가 임계구역에 들어오는 것을 막을 수 있다. 그러나 프로세스 P1이 lock = true; 문을 실행하기 전에 프로세스 P2가 while(lock == true) 문을 실행하면 둘다 임계구역에 진입하게 된다.

결국 위 그림과 같은 상황은 상호 배제 조건(Mutual Exclusion)을 보장하지 못한다.

 

또 다른 문제는 잠금이 해제되기 전까지 busy waiting이 발생한다는 것이다.

바로 while(lock == true) 문 부분인데, 작업을 할 필요가 없는 시간에도 계속 무한 루프를 돌면서 시스템 자원을 낭비한다.

---

한정 대기 문제( bounded waiting )

mutual exclusion 문제를 해결하기 위해서 lock을 하나만 두지 말고 두 개를 두기로 하자.

이전에는 lock을 두 프로세스가 공유하였기 때문에 문제였던 것이었다. 그러면 각 프로세스가 자신들만의 lock을 가지고 있도록 하는 것이다.

프로세스 P1은 임계구역에 진입하기 전에 먼저 잠금을 설정하고(lock1 = true) 프로세스 P2가 잠금을 설정했는지 확인한다(while(lock2 == true)) 만약 잠금을 설정하지 않았다면 임계구역에 진입하여 작업을 마친 후 잠금을 해제한다.(lock1 = false) 프로세스 P2도 같은 방식으로 임계구역에 진입한다.

 

위 코드는 일단 잠금을 하고 다른 프로세스가 잠겼는지 확인하므로 두 프로세스가 상호 배제가 보장된다.

그런데, 두 프로세스가 모두 임계구역에 진입하지 못하는 무한 대기 현상이 일어난다. 

1. 프로세스 P1은 lock1=true 문을 실행한 후 주어진 CPU 시간을 다 써버려 ready 상태로 돌아간다. context switching이 발생하고 프로세스 P2가 running 상태로 바뀐다.
2. 프로세스 P2도 lock2=true문을 실행한 후 자신의 CPU 시간을 다 써버려 ready 상태로 돌아간다. context switching이 발생하고 프로세스 P1이 running 상태로 바뀐다.
3. 프로세스 P2가 lock2=true문을 실행했기 때문에 프로세스 P1은 while(lock2 == true) 문에서 무한 루프에 빠진다.
4. 프로세스 P1이 lock1=true문을 실행했기 때문에 프로세스 P2도 while(lock1 == true) 문에서 무한 루프에 빠진다.

결국 P1, P2 둘 다 while 문을 빠져나오지 못하고 무한 루프에 빠져서 critical section에 진입하지 못한다.

이는 bounded waiting 조건을 보장하지 못하고 데드락(교착상태, deadlock)에 빠진다.

또한, 위의 코드는 확장성의 문제 또한 있다. 만약 process p3가 추가된다면 또 lock3를 추가해주어야 하고 점점 더 코드가 복잡해진다.

---

진행의 융통성 문제(Progress)

critical section 문제를 해결하기 위해 lock 값이 1이면 P1이 critical section에 들어갈 수 있고, lock이 2이면 P2가 critical section에 사용한다.

공유 변수 lock의 값을 통해 다른 프로세스가 critical section에 있는지 확인하고, 없으면 진입한다.

프로세스 P1은 while(lock == 2) 문을 실행하고 프로세스 P2가 잠금을 걸었으면 기다린다.

lock = 1이면 프로세스 P1이 critical section에 진입하고, critical section에 빠져나올 때 lock을 2로 바꾼다.

 

잠금을 확인하는 문장은 하나이므로 mutual exclusion고 bounded waiting을 보장한다. 그러나 서로 번갈아가면서 실행된다는 것이 문제이다. 한 프로세스가 두 번 연달아 임계구역에 진입하고 싶어도 그럴 수 없다.

 

P1는 P2가 critical section에 진입하고 나서야 critical section에 진입할 수 있다.

이렇게 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화(lockstep synchronization)라고 한다.

따라서 위 예시는 progress를 보장하지 못한다.

 

 

---

 

참고 자료

https://velog.io/@chappi/OS%EB%8A%94-%ED%95%A0%EA%BB%80%EB%8D%B0-%ED%95%B5%EC%8B%AC%EB%A7%8C-%ED%95%A9%EB%8B%88%EB%8B%A4.-8%ED%8E%B8-Critical-section-%EC%9E%84%EA%B3%84-%EA%B5%AC%EC%97%AD

OS는 할껀데 핵심만 합니다. 8편 Critical section (임계 구역)

https://cloudxlab.com/blog/race-condition-and-deadlock/

Race Condition and Deadlock | CloudxLab Blog