프로세스 동기화, 데드락(교착 상태)

공유 자원, 임계 영역(Critical Section), 경쟁 상태(Race Condition)

• 공유 자원: 여러 스레드가 동시에 접근할 수 있는 자원을 공유 자원이라고 한다.
• 임계 영역: 공유 자원 중 여러 스레드가 동시에 접근했을 때 문제가 생길 수 있는 부분을 임계 영역이라고 한다.
• 경쟁 상태: 둘 이상의 스레드가 공유 자원에 동시 접근했을 때 실행 순서에 따라 결과 값이 달라지는 상황을 의미한다.

따라서 경쟁 상태를 방지하고 데이터 일관성을 보장하기 위해 임계 영역에 하나의 스레드만 접근할 수 있도록 제어해야 한다.

* Race Condition은 CPU 코어가 1개일 때도 발생할까?

결론은 Race Condition은 CPU 코어가 1개일 때도 발생한다. CPU 코어가 1개인 경우에는 동시에 하나의 프로세스만 실행할 수 있고, 또 각각의 프로세스는 자신의 주소 공간에만 접근할 수 있는데 경쟁 상태가 발생하는 이유는 뭘까?

 

예를 들어 다음과 같은 상황이 있다.

1. 프로세스 A는 특권 명령을 수행하려는데, 자신이 직접 수행할 수 없으므로 운영체제에게 부탁하기 위해 시스템 콜을 발생시킨다.
2. CPU 제어권이 운영체제로 넘어오고, 운영체제 커널에서 특정 데이터를 읽어서 연산을 한다. (1을 읽어서 +1을 하는 연산)
3. 그러던 중 프로세스 A의 CPU 할당 시간이 다 되어 타이머 인터럽트가 발생한다. 따라서 CPU 제어권이 프로세스 B에게 넘어간다. (A ➡️ B)
4. 프로세스 B도 특권 명령을 수행하기 위해 시스템 콜을 발생시킨다.
5. CPU 제어권이 운영체제로 넘어오고, 운영체제 커널에서 특정 데이터를 읽어서 연산을 한다. (1을 읽어서 +1을 하는 연산)
6. 그리고 연산 결과를 커널에 반영한다. (커널의 데이터가 1에서 2로 변경됨)
7. 다시 문맥 교환이 발생하여 (B ➡️ A) 프로세스 A의 작업이 수행되고, 프로세스 A도 연산 결과(2)를 커널에 반영한다.
8. 즉, 커널의 데이터 1을 +1하는 연산이 두 번 일어났지만, race condition으로 인해 결과 값이 3이 아닌 2가 되었다.

즉, 운영체제 커널과 같은 공유 자원은 여러 프로세스가 접근할 수 있기 때문에 경쟁 상태가 발생할 수 있다. 그리고 문맥 교환 시 기존에 실행하던 프로세스의 레지스터 값을 PCB에 저장하여, 나중에 해당 프로세스가 다시 CPU를 사용할 때 마저 연산을 수행하기 때문에 CPU가 하나여도 경쟁 상태가 발생할 수 있다.

---

프로세스 동기화 방법

Race Condition을 방지하기 위한 해결법의 조건

프로세스 동기화 방법은 다음 3가지 조건을 모두 만족시켜야 한다.

• 상호 배제(Mutual Exclusion): 하나의 프로세스가 임계 영역에 들어가 있으면 다른 프로세스는 들어갈 수 없다.
• 진행(Progress): 아무도 임계 영역에 들어가 있지 않은 상태에서, 임계 영역에 들어가려는 프로세스가 있으면 들어갈 수 있어야 한다. 
• 한정 대기(Bounded Waiting): 한 프로세스가 임계 영역에 들어가기 위해 무한히 대기하는 기아 문제가 발생하지 않아야 한다.

대표적인 동기화 방법으로 뮤텍스, 세마포어 등이 있다. 이 방법들은 운영체제에서 동기화 기법을 구현하는 추상적인 개념으로, 실제 운영체제에 따라 세부적인 구현 방법은 다를 수 있다. 

뮤텍스(Mutex)

• 뮤텍스는 임계 영역에 하나의 스레드만 접근하도록 한다. (동기화 대상이 하나)
• 그리고 이를 제어하기 위해 락을 사용한다. 임계 영역에 접근한 스레드는 락을 가지고 있으며, 임계 영역을 빠져나온 후에는 락을 반납한다. 다른 스레드들은 락을 갖기 위해 대기한다.

세마포어(Semaphore)

• 세마포어는 카운터를 이용하여 임계 영역에 접근할 수 있는 프로세스를 제한한다.
• 사용 가능한 자원의 개수를 S로 표현하고, S에 대한 연산은 다음과 같다.
  • P(S): 공유 자원 획득
    • S가 0보다 크면 자원을 사용할 수 있다는 의미로, P 연산을 통해 자원을 획득하고 S 값을 1 감소시킨다.
    • S가 0이면 사용 가능한 자원이 없다는 의미로, 자원이 해제될 때까지 대기한다.
  • V(S): 공유 자원 반납
    • 자원을 해제하고 대기 중인 스레드가 자원을 사용하게 된다.
    • S 값이 1 증가한다.
• 세마포어는 카운팅 세마포어와 이진 세마포어로 나뉠 수 있다.
  • 카운팅 세마포어:  S 값이 0 이상의 정수 값을 가진다.
  • 이진 세마포어: S 값이 0 또는 1이다. 즉, 한 번에 하나의 스레드만 임계 영역에 접근할 수 있으며 뮤텍스와 유사하다.
• 세마포어의 구현 방식
  
  • Busy Waiting 방식
    • 다른 프로세스가 이미 임계 영역에 접근한 상태여서 S의 값이 0이라면, 현재 프로세스는 CPU를 획득한 채로 while 문을 돌기만 한다(다음 프로세스가 임계 영역 수행을 마치고 V 연산을 하여 공유 데이터를 반납해야 해결되는 상황). 
    • 즉, 현재 프로세스가 CPU를 획득한 채로 대기만 하는 Busy Waiting 문제가 발생한다. (CPU 낭비)
  • Block & Wakeup 방식
    
    • Busy Waiting이 발생하지 않는 구현 방법으로, 이 구현 방법에서 S는 세마포어 변수 value와 공유 자원을 기다리는 봉쇄 상태의 프로세스들이 저장된 큐를 갖는다.
    • 공유 자원에 접근할 수 없는 프로세스는 CPU를 획득한 내내 대기하는 것이 아니라, 바로 봉쇄 상태가 되어 큐에 줄을 서게 된다.
  •  일반적으로 Busy Waiting이 발생하지 않는 Block & Wakeup 방식이 더 좋다. 그러나 임계 영역의 길이가 짧거나 임계 영역 접근이 자주 발생하지 않으면, Block & Wakeup 방식에서 (큐를 관리하고 프로세스를 봉쇄 상태로 전환하는 등의) 오버헤드가 비효율적이므로 Busy Waiting 방식이 더 좋을 수 있다.

---

데드락(교착 상태)

데드락은 다중 프로세스나 스레드가 서로 필요한 자원을 점유하고 있어서, 다음 단계를 실행하지 못하고 무한히 대기하는 상태를 말한다.

데드락의 발생 조건

데드락이 발생하기 위해선 다음 4가지 조건을 모두 만족해야 한다. 

• 상호 배제(Mutual Exclusion): 매 순간 하나의 프로세스만 자원을 사용할 수 있다.
• 비선점(No Preemption): 프로세스는 자원을 스스로 내려놓을 뿐, 강제로 빼앗을 수 없다.
• 보유 대기(Hold and Wait): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유하고 있는 자원을 놓지 않고 계속 가지고 있다.
• 순환 대기(Circular Wait): 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다. (ex, 프로세스 p0, p1, ..., pn이 있을 때 p0은 p1을 기다리고 p1은 p2를 기다리고..)

---

Reference

• 이화여자대학교출판문화원, 운영체제와 정보기술의 원리, 반효경