경쟁상태 / 교착상태 / 기아상태

niireymik·2024년 5월 13일

💡
운영체제의 3가지 핵심 개념은 가상화(virtualization), 병행성(concurrency), 영속성(persistency)이다. 이중에서 병행성은 Concurrent processing ( ↔ Serial processing ) 방식으로써 보장되는데, 이때 발생할 수 있는 대표적인 문제들이 바로 경쟁상태, 교착상태, 기아상태이다. 하나씩 알아보자.

Concurrent processing?

Interleaving 방식 : 한 CPU에서 여러 작업을 번갈아가며 실행

overlapping 방식 (진정한 의미의 Parallel processing : 병렬 처리) : CPU가 두 개

→ 이 둘을 합쳐 Concurrent Processing이라고한다!

⚡ 경쟁상태, Race condition

경쟁상태의 정의

| 공유 자원에 여러 프로세스가 동시에 접근을 시도할 때, 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태

경쟁상태 예시 상황

x=100으로 설정되어있고, 두 스레드는 다음과 같다.
Thread1 x+10;
Thread2 x-10;

여기서 Thread1과 Thread2가 모두 실행되면, 결론적으로는 100으로 돌아와야 하는 것이 맞다. 그러나 실제로는 이 'X'라는 공유자원 때문에 문제가 발생한다. 두 스레드를 명령어로 나누어 보자.

< Thread1 >
| LOAD X, R1
ADD R1, 10
STORE R1, X

< Thread2 >
| LOAD X, R2
SUB R2, 10
STORE R2, X

-> LOAD X, R1과 LOAD X, R2가 먼저 실행된 뒤 각각 ADD/SUB와 STORE이 실행되면, 저장된 값으로부터 다음 계산이 반영되는 것이 아니라 계산된 값은 무시되고 새로운 값이 저장되어, 90, 110과 같은 값이 나오는 경우가 생기는 것이다! (이 확률은 정말 희박하지만 그래도 문제임은 확실하다.)

이렇게 공유 자원에 대해 접근, 즉 경쟁하는 상황을 경쟁상태라고 한다.

발생 조건 및 해결 방안

커널 작업 중 인터럽트가 발생하여 동일한 데이터를 조작할 경우
-> 커널 모드 작업 중에는 인터럽트를 disable로 설정, CPU 제어권을 가져가지 못하게 한다.
프로세스가 (시스템 콜 하여) 커널 모드로 작업 수행 중, 시간이 초과되어 CPU 제어권이 다른 프로세스로 넘어가며 문맥 교환이 발생할 때
-> 시간이 초과되어도 CPU 제어권이 넘어가지 않도록 한다.
멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 경우
-> 커널 내부에 있는 각 공유 데이터에 접근할 떄마다 그 데이터에 대해 lock/unlock 한다.

🔒 교착상태, DeadLock

교착상태의 정의

| 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 아무것도 완료되지 못하는 상태

교착상태 배경과 예시 상황

위의 경쟁상태 예시에서, Thread1은 x+10;, Thread2는 x-10;의 작업을 한다. 여기서, 경쟁 상태에 놓인 두 스레드가 서로 영향을 주게 되는 것을 방지하기 위한 방법으로 lock, unlock이 있었다.

스레드가 특정 자원을 사용하고 있으면, 그동안 다른 스레드가 해당 자원을 사용하지 못하게 하는 것이다. (해당 코드를 Serial하게 실행되게 한다.) = Lock을 걸고서 작업하고, 빠져나올 때 Unlock한다!

각 스레드의 작업에 lock, unlock을 추가하면 다음과 같이 된다.

Thread1

lock(a);
x = x + 10;
unloxk(a);

Thread2

lock(a);
x = x - 10;
unlock(a);

-> 이렇게 두면, Thread1이 사용을 시작하고 Thread2가 접근하려 하면 거부될 것이다.

자, 경쟁상태의 문제를 lock/unlock으로 해결한 바로 이 지점에서 교착상태의 문제가 생겨난다. 이는 두 동일한 자원 a, b에 접근하는 것을 예시로 들 수 있다.

Thread1

lock(a);
lock(b);

Thread2

lock(b);
lock(a);

이렇게 두 자원 a, b에 접근하는 경우 문제가 발생한다. 아주 적은 확률로, Thread1의 lock(a);가 실행되고 Thread2의 lock(b)가 실행되는 경우이다! 이때 두 스레드 모두 각각 b와 a에 접근을 거부당하면서 어떠한 작업도 종료되지 못한다. a, b의 자원에는 다른 어떠한 스레드도 접근하지 못하게 된다. 이러한 상태를 바로 교착 상태, DeadLock이라 한다.

발생 조건 및 해결 방안

교착 상태는 아래의 4가지 조건을 모두 충족해야 발생한다.

상호 배제 : 하나의 프로세스가 자원을 사용중일 때 다른 프로세스는 그를 사용할 수 없다.
점유 대기 : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
비선점 : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
순환 대기 : 프로세스의 집합에서 순환형태로 자원을 대기하고 있어야 한다.

이에 따른 해결 방안은 다음의 방법들이 있다.

예방 : 교착 상태 발생 조건 중 하나를 제거하면서 해결 👉 자원 낭비가 가장 심하다.
회피 : 교착 상태 발생 시 피해나가는 방법 👉 은행원 알고리즘 : 자원을 할당하면 문제가 발생하지 않는지 확인 후 할당함 : 예측의 어려움과 복잡함, 큰 오버헤드 때문에 현재 채택되는 방식은 X
탐지 및 회복 : 자원 할당 그래프 혹은 알고리즘을 통해 교착 상태를 탐지 -> 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시킴

교착상태의 회복

교착상태를 일으킨 프로세스 자체를 종료
- 교착 상태의 프로세스를 모두 중지하는 방법
- 교착 상태가 제거될 때까지 하나씩 프로세스를 중지하는 방법

할당된 자원을 회수해 회복
- 교착상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당해주는 방법
- 우선 순위가 낮거나 수행 횟수가 적은 프로세스 위주로 프로세스 자원