경쟁 상태(Race Condition), 프로세스 동기화, 데드락

경쟁 상태(Race Condition)

Race Condition이란, 여러 개의 프로세스가 동시에 공유 데이터에 접근할 때 실행 순서에 따라 결과 값이 달라지는 현상이다. 따라서 이런 경쟁 상태에서는 각 프로세스가 공유 데이터에 동시에 접근하지 못하도록 접근 순서를 제어하는 동기화가 필요하다.

 

경쟁 상태은 CPU가 하나인 경우에도 발생하는데, CPU가 하나인 경우에는 동시에 하나의 프로세스만 실행할 수 있고, 또 각각의 프로세스는 자신의 주소 공간에만 접근할 수 있는데 경쟁 상태가 발생하는 이유는 뭘까?

 

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

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

즉, 운영체제 커널의 데이터는 여러 프로세스가 접근할 수 있기 때문에 경쟁 상태가 발생할 수 있다. 즉, 운영체제 커널의 데이터는 공유 자원이라고 볼 수 있다.

 

그리고 문맥 교환 시 기존에 실행하던 프로세스의 레지스터 값을 PCB에 저장하여, 나중에 해당 프로세스가 다시 CPU를 사용할 때 마저 연산을 수행하기 때문에 CPU가 하나여도 경쟁 상태가 발생할 수 있다.

임계 영역(Critical Section)

임계 영역은 경쟁 상태에서 공유 데이터의 일관성을 보장하기 위해 특정 프로세스만 접근할 수 있도록(상호 배제) 해야 하는 코드 영역이다. 임계 영역은 다음과 같이 입장 영역(entry section)과 퇴장 영역(exit section)을 기준으로 구분된다. 따라서 각 프로세스는 임계 영역에 접근하기 위해 입장 영역 ➡️ 임계 영역 처리 ➡️ 퇴장 영역의 순으로 이뤄진다.

프로세스 동기화

임계 영역의 동시 접근 문제를 해결하기 위한 조건

임계 영역의 동시 접근 문제를 해결하기 위해서는 다음 3가지 조건을 모두 만족해야 한다. 

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

피터슨의 알고리즘

• 임계 영역에 들어가기 전에
  • flag[i]를 true로 만들어, 임계 영역에 접근하려는 의사를 표시한다. 
  • turn을 상대의 값으로 변경한다. 
  • 상대방이 임계 영역에 접근하려고 하며 차례가 상대방 차례이면 기다리고, 그렇지 않으면 현재 프로세스가 임계 영역에 들어간다.
• 임계 영역을 빠져 나온 후에는 flag[i]를 false로 만든다. 
• 상호 배제, 진행, 한정 대기 조건을 모두 만족하는 알고리즘이다.
  • 상호 배제: turn의 값이 i 또는 j 중 하나의 값만 가질 수 있기 때문에 하나의 프로세스만 임계 영역에 접근할 수 있다.
  • 진행: 프로세스 i가 임계 영역 처리 후에 flag[i]를 false로 만들기 때문에 임계 영역에 접근하고자 하는 다른 프로세스가 접근할 수 있다.
  • 한정 대기: 두 개의 프로세스가 동시에 flag의 값을 ture로 설정한 경우(동시에 임계 영역 접근 의사를 표현한 경우), turn 값을 확인하여 해당 프로세스가 임계 영역에 들어갈지 말지를 결정한다. 만약 상대의 flag가 true이면서 turn 값이 상대 차례이면 while 문을 빠져 나온다.
• 문제점 - Busy Waiting(Spin Lock)
  • 그러나 임계 영역에 접근할 수 있을 때까지 while 문을 도는 비효율적인 상황이 발생한다.
  • 현재 프로세스가 임계 영역에 접근하지 못하고 while문을 도는 상황일 때, 그 다음 프로세스가 CPU를 획득하여 임계 영역에 접근하여 작업을 완료해야 현재 프로세스가 임계 영역에 접근할 수 있다.
  • 즉, 임계 영역에 접근하지 못하는 프로세스는 CPU를 획득했으나 CPU 획득 시간 내내 while 문만 계속 돌며 CPU를 제대로 활용하지 못한다. 

뮤텍스(Mutex)

• 뮤텍스는 mutual exclusion(상호 배제)의 약자로, 임계 영역에 하나의 스레드만 접근하도록 한다. 그리고 이를 제어하기 위해 락이라는 개념을 사용한다.
• 임계 영역에 대한 접근은 동시에 하나의 스레드만 가능하다. 즉, 뮤텍스의 동기화 대상은 하나이다.
• 다른 스레드들은 락을 갖기 위해 대기한다. 

세마포어(Semaphore)

• 세마포어는 카운터를 이용하여 임계 영역에 접근할 수 있는 프로세스를 제한한다.
• 세마포어에서는 사용 가능한 자원의 개수를 S라는 정수형 오브젝트로 표현한다. 
• S에 대한 연산은 다음 두 가지이다.
  • P(S): 공유 데이터 획득(락을 거는 과정)
  • V(S): 공유 데이터 반납(락을 반납하는 과정)
• 이때 P 연산과 V 연산의 구현 내용은 알 수 없으며, P 연산과 V 연산이 수행될 때 각각 원자적으로 수행된다고 가정한다. 즉, 이어서 설명하는 내용은 원자적으로 수행되는 P 연산과 V 연산이 지원된다는 가정 하에 프로그래머가 지원되는 연산자들을 활용하여 어떻게 동기화를 구현할 것인지에 대한 내용이다.

세마포어의 구현 방식

• Busy Waiting 방식
  • 세마포어 S의 값을 1로 설정한다. 즉, 공유 자원이 하나의 프로세스만 접근할 수 있다.
  • 프로세스가 임계 영역에 접근하려고 할 때, S가 0 이하이면 자원이 없으므로 대기한다. 반면 S가 양수이면 자원을 획득한다. 
  • 문제점 
    • 만약 다른 프로세스가 이미 임계 영역에 접근한 상태여서 S의 값이 0이라면, 현재 프로세스는 CPU를 획득한 채로 while 문을 돌기만 한다(다음 프로세스가 임계 영역 수행을 마치고 V 연산을 하여 공유 데이터를 반납해야 해결되는 상황). 즉, CPU를 획득한 채로 대기만 하는 Busy Waiting 문제가 발생한다.

• 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

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