동기화와 교착 상태

동기화

프로세스 혹은 스레드는 실행하기 위해선 자원이 필요하다. 하지만 모든 자원을 독점할 수는 없는 법. 프로세스 혹은 스레드가 공유하는 자원 또한 독점할 수 없이 공유한다. 이 공유 자원은 메모리 혹은 파일이 될 수 있고, 전역 변수나 입출력 장치일 수도 있다. 공유 자원을 두고 동시 다발적으로 여러 프로세스와 스레드가 동시에 접근한다면, melee 전과 마찬가지로 그냥 서로가 서로를 죽이자는 것과 같을 수 있다.

공유 자원에 접근하는 코드 중 동시에 접근하게 된다면 문제가 생길 만한 구역이 생기는데 이를 임계 구역이라고 한다. 즉, 동시에 실행되는 프로세스나 스레드가 동시에 이 구역에 진입하게 되면, 공유 자원을 선점하는 것에 문제가 발생할 수 있다. 이러한 문제를 레이스 컨디션이라고 한다.

따라서 실행되는 모든 프로세스 혹은 스레드는 이 임계 구역을 동시에 접근하지 않도록 유의해야 한다. 레이스 컨디션이 발생되면 자원의 일관성이 손상될 수 있다. 그렇기 때문에 2개 이상의 프로세스 혹은 스레드가 임계 영역에 진입하고자 한다면, 하나는 대기 상태에 있어야 한다.

레이스 컨디션을 방지하면서 임계 구역을 관리하기 위해서는 프로세스와 스레드가 동기화 되어야 한다. 동기화는 쉽게 프로세스와 스레드가 서로 sync를 맞추어 임계 구역에 접근하지 않고 차례를 맞추어 이용하게 되어야 한다는 뜻이다.

동기화는 두가지 실행 방식이 있다. 올바른 순서로 레이스 컨디션을 피해 사용하는 방법과 하나만 접근하게 하는 방법이다. 각각은 실행 순서 제어, 상호 배제 라고 한다. 당연하게도, 레이스 컨디션은 이 두 조건 중 하나라도 만족하지 못해 생기는 오류다.

• 실행 순서 제어: 프로세스 및 스레드를 올바른 순서로 실행
• 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스 & 스레드만 접근

동기화 기법 1: 뮤텍스 락

뮤텍스 락은 동시에 접근해서는 안 되는 자원에 동시 접근이 불가능하도록 상호 배제를 보장하는 동기화 도구다. 즉, 뮤텍스, MUTEX (mutual Exclustion), 상호 배제 를 위한 Lock의 뜻이다. 이를 다시 해석해보면

임계 구역에 접근하고자 한다면, 반드시 lock을 acquire해야 하고 , 임계 구역에서의 작업이 끝났다면 release를 해야한다.

전형적인 뮤텍스 락은 프로세스 및 스레드가 공유하는 변수인 Lock과 2개의 함수 (acquire, release)로 구현된다. 위의 설명의 순서에 따르면, lock.acquire()을 호출하여 임계 구역에 접근하고, 작업이 끝난 후 lock.release()로 임계 구역에서 빠져 나온다.

뮤텍스 락은 여러 프로그램 언어에 포함되어 있기도, 구현해야 하기도 한다. python의 경우 뮤텍스 락을 지원한다. (처음 알았다)

동기화 기법2: 세마포

공유 자원이 늘 하나만 있는 것이 아니다. 한 번에 하나의 프로세스 및 스레드 만 공유 자원을 이용할 수 있는 상황도 있지만, 한 번에 3~4개의 프로세스 및 스레드까지 특정 자원을 이용할 수 있는 상황도 있다. 한 번에 하나의 프로세스 및 스레드 만 공유 자원을 사용한다면 뮤텍스 락을 사용하면 되지만, 그 이상은 세마포, semaphore를 사용하는 것이 좋다.

세마포의 경우 뮤텍스 락과 비슷하지만, 조금 더 일반적인데, 세마포는 그 말과 동일하게 신호기의 특징을 지닌다. 멈춤 신호와 가도 좋다신호를 토대로 임계 구역을 관리한다. 프로세스 및 스레드가 임계 구역 앞에서 멈추라는 신호라면 기다리고, 가도 좋다 라는 신호라면 접근하면 되게 한다.

세마포 또한 변수와 함수로 구성되어 있다.

• 변수 S: 사용 가능한 공유 자원의 개수를 나타내는 변수
• wait() 함수: 임계 구역 진입 전 호출하는 함수
• signal() 함수: 임계 구역 진입 후 호출하는 함수

변수 S, 사용 가능한 공유 자원의 개수는, 임계 구역에 진입할 수 있는 프로세스의 개수와 같다. 공유 자원의 개수가 S개 일 경우, 임계 구역에 진입하여 동시에 실행 가능한 프로세스 혹은 스레드 또한 S개로 구성된다.

원리는 다음과 같다.

1. 사용 가능한 공유 자원의 개수를 나타내는 변수 S에 1을 증가시키고
2. 변수 S의 값이 0 이하인지를 확인한다. S를 1 증가 시킬 때 S가 0보다 크다는 것은 사용 가능한 공유 자원의 개수가 1개 이상을 의미하며, 0 이하는 임계 구역에 진입하기 위해 대기하는 프로세스가 존재함을 의미한다.
3. 대기 상태로 접어든 프로세스 중 하나를 준비 상태로 전환한다.

쉽게, 공유 자원의 개수와 프로세스를 동일하게 맞추어 임계 구역에 진입하게 하고, 이외는 대기하게 하며 동기화를 진행하는 것이다.

세마포 또한 2가지로 나뉜다. 이진 세마포 그리고 카운팅 세마포이다. 카운팅 세마포는 공유 자원이 여러개 존재했을 때 사용하는 세마포다. 이진 세마포는 이진법을 사용하기 때문에 뮤텍스 락과 비슷하다. (0과 1만 가질 수 있음 (S)). 따라 세마포라는 용어는 대부분 카운팅 세마포를 의미한다.

뮤텍스 락과 세마포 차이

어찌보면 뮤텍스 락과 세마포 동기화 방법은 순서에 맞추어 임계 구역에 접근해 자원을 사용하는 것은 비슷해 보인다. 하지만, 뮤텍스 락은 한 번에 하나의 스레드만 공유 자원에 접근할 수 있지만, 세마포는 "사용 가능한 공유 자원의 수 = 임계 구역에 진입할 수 있는 프로세스의 개수" 라는 조건이 있다는 점이다.

3개의 공유 자원이 있다면, 서로 순서는 조금씩 다르겠지만 3개의 프로세스나 스레드가 임계 구역에 접근할 수 있다.

동기화 기법3: 조건 변수와 모니터

모니터를 통해 동기화를 할 수 있다. 우선, 조건 변수란 실행 순서 제어를 위한 동기화 도구다. 특정 조건 하에 프로세스를 실행/일시 중단함으로써 프로세스나 스레드의 실행 순서를 제어할 수 있다. 조건 변수에 대해 wait와 signal(재개)하는 함수가 있다.

• 아직 특정 프로세스가 실행될 조건이 되지 않았을 때는 wait
• 특정 프로세스가 실행될 조건이 충족되었을 때는 signal을 통해 실행을 재개한다.

그렇다면 모니터란 무엇일까? 모니터는 공유 자원과 그 공유 자원을 다루는 함수로 구성된 동기화 도구로, 상호 배제를 위한 동기화 뿐 만 아니라, 실행 순서 제어를 위한 동기화까지 가능하다. 프로세스 및 스레드는 공유 자원에 접근하기 위해 반드시 정해진 공유 자원 연산을 통해 모니터 내로 진입하고, 모니터 안에서 실행되는 프로세스 및 스레드는 오직 하나여야 한다. 이미 모니터 내로 진입하여 실행 중인 프로세스 및 스레드가 존재하면 큐에서 대기해야 한다.

항목	Mutex Lock	Semaphore	Monitor
자원 접근 수	1개	1개 이상	1개
해제 주체	잠근 스레드	다른 스레드 가능	내부적으로 자동 해제
대기 기능	X	X	조건 변수 기반 대기/알림
추상화 수준	낮음	중간	높음
예시 언어	C, POSIX	C, Linux	Java Python C# 등 OOP

교착상태

프로세스를 실행하기 위해서는 자원이 필요하다는 것은 이미 우리는 잘 알고 있다. 하지만 2개 이상의 프로세스가 각자 가지고 있는 자원을 기다리기만 한다면 어떠한 일도 일어날 수가 없다. 이러한 경우가 deadlock, 교착 상태를 의미한다. 일어나지 않을 사건을 기다리며 프로세스의 진행이 멈춰 버리는 현상이다.

프로세스 A는 자원 X를 점유 한 채 프로세스 B가 점유하는 자원 Y의 사용을 기다리고, 프로세스 B는 자원 Y를 점유 한 채 프로세스 A가 점유하는 자원 X를 기다리면… 세월이 없이 기다릴 수 밖에 없다.

발생 조건

교차 상태가 발생하는 상황에는 4가지 필요 조건이 있다. 상호 배제, 점유와 대기, 비선점, 원형 대기다. 이중 하나라도 만족하지 않는 다면, 교착 상태는 발생하지 않고, 4개의 조건이 모두 만족할 때 교착 상태의 가능성이 생긴다.

1. 상호 배제

   • 교착 상태가 발생하는 원인 중, 한 번에 하나의 프로세스만 해당 자원을 이용 가능했기 때문
   • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상호 배제 상황에서 발생한다

2. 점유와 대기

   • 한 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다린다면, 교착 상태가 발생

3. 비선점

   • 해당 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 자원을 이용할 수 있다
   • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우 발생한다.

4. 원형 대기

   • 프로세스와 프로세스가 요청한 자원이 원의 형태를 이루는 경우
   • 각각의 프로세스가 서로 점유한 자원을 할당 받기 위해 원의 형태로 대기할 경우 (아까의 예제) 발생한다.

해결 방법

그렇다면 이걸 어떻게 해결할까? 운영체제는 애초에 교착 상태의 발생 조건에 부합하지 않도록 자원을 분배하는 방식으로 교차 상태를 예방할 수 있으며, 조금씩 할당하다가 할당하지 않는 방식으로 회피 하기도 한다. 또한 자원을 제약 없이 할당하다가 검출한 후 회복 시키기도 한다.

1. 교착 상태 예방

   • 교착 상태를 발생시키는 4가지 필요 조건 중 하나를 충족시키지 못하게 막아버리는 방법이 있다.

2. 교착 상태 회피

   • 교착 상태가 발생하지 않을 정도만 자원을 할당하는 방법
   • 기본적으로 교착 상태를 한정된 자원의 무분별한 할당으로 인한 문제로 간주.

3. 검출 후 회복

   • 예방과 회피는 사전 조치라면, 교착 상태를 인정하고 처리하는 사후 조치 방식
   • 운영체제는 프로세스가 자원을 요구할 때 마다 자원을 할당, 주기적으로 교착 상태의 발생 여부를 검사
   • 검출 될 경우 자원 선점을 통해 회복시키거나 강제 종료함으로써 회복한다.
     
     
     

참고자료

※ 이 글은 『이것이 컴퓨터 과학이다』 책을 기반으로, 다양한 자료를 참고해 작성했습니다.