임계구역과 교착 상태

동기화 문제

◎ 임계 구역

멀티 스레드에서 발생할 수 있는 동기화 문제에 대해 설명하려면 먼저 임계구역에 대해 공부해야 한다.

 

임계 구역이란 여러 개의 스레드가 수행되는 멀티 스레드 시스템에서 각 스레드들이 공유하는 데이터를 변경하는 코드 영역을 말한다.

 

이전에 설명했듯 스레드의 경우 프로세스 내에서 Stack 영역을 제외한 Data, Code, Heap 영역을 공유하고 있다.

이 중 static 변수와 전역 변수는 특정 상황에서 무조건 1개 스레드만 활용한다고 확정할 수 없다.

즉, 스레드끼리 공유하는 Code, Heap 영역의 데이터를 변경하는 코드 영역을 "임계 구역"이라고 하는 것이다.

 

임계 구역에 대한 문제를 확인할 수 있는 대표적인 코드는 아래와 같다.

static int cnt = 0;

void funcA(){
	cnt++;
}

void funcB(){
	cnt--;
}

이러한 프로그램에서 만약 A 스레드는 funcA만, B 스레드는 funcB만 수행한다고 가정하자.

이 경우 만약 funcA와 funcB가 동시에 실행된다고 가정하자. 이 경우 funcA는 cnt 값을 0에서 1로 변환시킬 텐데 문제는 funcB가 실행될 때도 cnt 값이 0이라는 의미이다.

이 경우 funcA를 통해 cnt 값이 1로 변환되었는데 funcB를 통해서는 cnt 값이 -1로 변환될 것이다. 이 경우 나중에 종료되는 함수가 도출한 상태로 설정되기 때문에 funcA와 funcB가 동시에 수행되었다면 원래 0이 나와야겠으나 -1이나 1이라는 이상한 값이 도출될 수 있는 것이다.

 

그리고 이러한 임계 구역 때문에 발생하는 문제를 동기화 문제라고 부르는 것이다.

 

◎ 동기화

동기화의 정의는 여러 프로세스나 스레드가 어떠한 데이터에 대하여 동시 작업을 수행할 경우 작업에 순서를 정해주어 공유하는 데이터의 일관성을 유지하는 것이다.

 

하나의 자원을 한 순간에 한 프로세스만 이용하도록 제어하는 "프로세스 동기화", 하나의 코드블록이나 메서드를 한 순가에 하나의 스레드만 이용하도록 보장하는 "스레드 동기화"가 존재한다.

 

동기화 작업은 어떠한 데이터에 대하여 동시 작업이 일어날 경우 작업 순서에 관계없이 원하는 결괏값을 얻기 위하여 수행하는 과정이다.

이를 깊게 생각해 보자면 임계 구역이 존재하여 공유된 자원에 여러 스레드가 접근할 경우 동기화 작업을 통해 스레드 작업 간 순서를 정할 수 있기 때문에 공유된 자원의 일관성을 유지할 수 있다는 것이다.

 

위 예시를 보자면 funcA를 먼저 수행시키고 funcB를 수행시키는 설정으로 "0 → 1 → 0" 과정을 통해 정상적으로 자원의 일관성을 유지할 수 있는 것이다.

 

동기화의 가장 큰 목적은 데이터의 일관성을 보장하기 위함이다.

동기화를 통해 임계구역 문제를 해결하고 공유되는 데이터를 관리해 줌으로써 원하는 결괏값이 도출될 수 있는 것이다.

 

또한 프로세스의 실행 순서를 원하는 대로 제어하거나 Busy wait 같은 비효율성을 제거하기 위해 동기화를 사용하기도 한다. 여기서 Busy wait이란 의미 없는 코드를 반복 수행하며 기다리는 것을 말한다.

 

◎ 임계구역 문제(동기화 문제) 해결의 3가지 조건

임계구역과 그에 따라 발생하는 문제, 그리고 동기화에 대해서도 알아봤으니 멀티스레드 시스템에서 발생할 수 있는 동기화 문제를 해결할 방법에 대해서 알아보자.

 

임계구역 문제를 해결하기 위해선 3가지 조건이 필요하다.

1. 상호배제(Mutual Exclusion)
   • 임계구역에는 오직 1개의 스레드만 진입 가능함
   • 1개 스레드가 임계구역에서 실행 중이라면 다른 스레드는 해당 임계구역에 접근할 수 없음
2. 진행(Progress)
   • 임계구역에 프로세스가 존재하지 않을 경우 다른 프로세스가 접근 가능해야 함
   • 임계구역에 들어간 프로세스가 없는 상태에서 한 순간에 다수의 프로세스가 임계 구역에 들어가려 할 때 어떤 프로세스가 임계 구역에 들어갈지 유한 시간 내에 결정돼야 함
3. 유한 대기(Bounded Waiting)
   • 임계구역으로 진입하기 위해 대기하는 모든 스레드는 유한 시간 내에 해당 임계구역으로 진입 가능해야 함
   • 진행은 임계구역 해결을 위해 계속해서 스레드가 임계 구역 코드를 실행시키도록 하는 것을 말하며 유한대기는 이미 임계구역 코드를 실행하고 있는 스레드 외의 나머지 스레드들이 기아 현상이 나타나지 않도록 실행되고 있는 스레드를 제한하는 것을 의미함
     • 기아 : 프로세스나 스레드가 임계 영역 코드를 실행시키기 위하여 무한정으로 기다리는 현상

 

◎ 임계구역 문제 해결방법

Lock

하나의 스레드가 프로세스나 자원을 활용하고 있다면 이를 잠가 다른 스레드가 접근을 못하게 하는 방식이다.

 

하지만 Lock 방식은 특정 상황에서 제대로 동작하지 않는다는 단점이 존재한다.

예를 들어 A 함수가 임계 구역 코드에 Lock을 걸기 전 다른 스레드가 임계 구역 함수에 들어오게 된다면 두 개의 스레드가 임계 영역에 동시접근하는 상황이 발생할 수 있다.

 

 

Semaphore & Mutex

임계구역 문제 해결방법으로 가장 유명한 방법이자 위에서 설명한 동기화 방법을 통해 문제를 해결하는 방법이다.

 

세마포어란 동시에 자원을 접근할 수 있도록 허용한 공유 자원의 수를 나타내는 것으로 P, V라고 불리는 2개의 Atomic(분해되지 않는) 함수로 제어되는 정수 변수를 이용한 교착 상태 방법이다.

 

사실 세마포어와 뮤텍스에 대해서까지 공부하면 리눅스를 공부하기 위해 간단히 OS를 공부한다는 측면과는 달라지는 것 같아 간단히만 설명하고 넘어가겠다.

나중에 네트워크처럼 OS도 필요성을 느낀다면 그때 자세히 다루지 않을까 싶다. 학부생 때도 배웠지만 이 부분이 정말 생각보다 매우 복잡한 과정 및 이론을 가지고 있는데 1학기 중 중간 ~ 기말 내내 다뤘던 부분이라는 것을 알아두면 어느 정도 난이도와 양인지 알 수 있을 것이다.

 

간단히만 설명하자면 세마포어는 접근제어를 위한 정수형 변수 S값을 감소시키는 P함수(Wait 함수)와 S값을 증가시키는 V함수(Signal)가 존재한다.

이 중 Semaphore는 정수형 변수 상태가 0부터 지정한 정수값 n까지의 값 중 하나를 가질 수 있지만 뮤텍스는 S 상태가 9과 1 두 개뿐인 이진형 세마포어이다.

이 때문에 "세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다"라는 면접관들이 좋아하는 1개 문장이 나오는 것이다.

 

이렇게 차이가 나는 것은 세마포어는 "여러 프로세스가" 공유된 데이터에 접근하는 것을 막는 것이고 뮤텍스는 "여러 스레드가" 공유된 데이터에 접근하는 것을 막는 것이다.

스레드는 공유된 자원이라면 1개 프로세스 전체에서 공유되고 있는 자원이기 때문에 무조건 2개 이상의 스레드가 동시에 접근하면 안 된다.

하지만 프로세스 같은 경우 다른 프로세스와 독립된 메모리 공간을 가지고 있기 때문에 공유된 자원이라 할지라도 다수의 프로세스에서 동시 접근 가능한 상태도 존재하며 이런 상황에선 2개 이상의 스레드가 들어와도 데이터 안정성을 해치지 않을 수 있기 때문에 꼭 0,1 값만 가지지 않아도 되는 것이다.

 

단지 Semaphore는 P나 V 연산 중 하나가 생략된다면 상호배제 문제와 대기하는 프로세스들이 교착상태에 빠질 수 있다는 문제가 존재한다.

P 연산이 일단 시작되면 프로세스는 다른 경로를 선택할 수 없기 때문에 만약 S값이 1인 상태로 V 연산이 생략된다면 S는 영원히 1일 것이며 이진 세마포어일 경우 P 연산을 이미 실행하여 기다리고 있는 스레드들은 영구적으로 임계구역에 접근할 수 없을 것이다.

 

Monitor

한 프로세스 내에 있는 하나의 스레드만 자원에 접근이 가능한 방법으로 하나의 프로세스 내에서 다른 스레드 간 동기화를 할 때 사용한다.

 

모니터는 개념적으로 이진 세마포어만 가능한데 세마포어와 유사하지만 객체 지향 개념을 넣었기 때문에 제어하기가 더욱 쉽다.

 

이 부분도 자세히 공부하자면 너무 복잡하기 때문에 이 정도로만 알고 넘어가자.

---

교착상태(Deadlock)

출처 : https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/

◎ 교착상태란?

교착상태는 "프로세스의 무한 대기 상태"라고 이해하면 편하다.

2개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 다음 단계를 진행하지 못하는 상황을 말한다.

 

위 이미지가 교착상태를 가장 잘 표현한 이미지이다.

Process1(P1)과 Process2(P2)는 실행되기 위해 Resource1(R1)과 Resource2(R2)가 필요하며 P1은 R1만을 가지고 있고 P2는 R2만을 가지고 있는 상황인 것이다.

P1의 경우 P2가 종료되면 R2를 반납할 것이니 이를 가져가 실행하면 되기 때문에 R2 반환을 기다릴 것이다. 하지만 P2 입장에서도 R2를 가지고 있는 현 상태에서 P1이 종료되어 R1이 반납되면 이를 가져가야 실행할 수 있으므로 P1이 종료되기를 기다리는 것이다.

즉, P1은 P2가 종료되기를, P2는 P1이 종료되기를 한없이 기다리며 2개 프로세스 모두 실행되지 못하는 상태가 되는 것이다.

 

이런 교착 상태는 제한된 자원을 최대한 효율적으로 사용하려다 그 부작용으로 인해 발생하는 문제이다.

이런 교착 상태가 지속된다면 다른 프로세스에도 영향을 끼치기 때문에 1개 프로세스만 고통을 받는 기아(무한 대기) 상태보다 더욱 심각한 문제라고 볼 수 있다.

예를 들어 P3라는 프로세스가 R1, R2, R3 자원을 필요로 한다면 P3까지 이 교착 상태에 추가될 것이기 때문이다.

 

◎ 교착상태의 4가지 필요조건

교착 상태가 발생하기 위해선 꼭 4가지 필요조건이 성립되어야 한다.

여기에서 중요한 것은 "필요조건"이라는 것이다. 4가지 조건이 충족된다고 해서 무조건 교착 상태가 발생한다고 단정 지을 수는 없으나 만약 교착 상태가 발생했다면 무조건 이 4가지 조건이 충족된 것이다.

1. 상호 배제(Mutual Exclusion)
   • 1개 프로세스가 자원을 사용하고 있다면 다른 프로세스는 사용할 수 없음
   • 즉, 자원에 대한 공유가 안 되는 것이다.
2. 점유 대기(Hold and wait)
   • 프로세스가 할당된 자원을 가지고 있는 상태에서 필요한 다른 자원을 기다림
3. 비선점(No preemption)
   • 프로세스가 자원 사용을 끝낼 때까지는 다른 프로세스가 그 자원을 빼앗아 사용할 수 없음
4. 순환대기(Circular wait)
   • 프로세스가 요구하는 자원의 방향이 원형을 이룸
   • 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 점유하고 있어야 함

교착 상태를 가장 잘 나타내는 예시는 "식사하는 철학자들 문제"라는 다익스트라가 만든 문제이다.

 

철학자들은 식사를 하는데 한 철학자가 A 젓가락을 사용하고 있다면 다른 사람들은 누구도 A 젓가락을 사용할 수 없다.(상호 배제) 또한 다른 철학자가 들고 있는 젓가락을 뺏을 수도 없다.(비선점)

이때 철학자들의 젓가락은 철학자의 왼쪽과 오른쪽에 1개씩 놓여 있는데 모든 철학자는 왼쪽 젓가락부터 집을 수 있다.(순환 대기)

조건에 의하여 모든 철학자는 왼쪽 젓가락을 집고 있는 상태가 될 것이고 이젠 오른쪽 젓가락을 집어야 할 텐데 오른쪽 철학자가 이미 자신 기준 오른쪽, 오른쪽 철학자 기준 왼쪽 젓가락을 가지고 있기 때문에 오른쪽 철학자가 젓가락을 내려놓을 때까지 기다린다. 이 상황에서 자신은 왼쪽 젓가락을 내려놓지 않는다.(점유 대기)

 

결국 이런 상황에선 모든 철학자가 왼쪽 젓가락만 가진 상태에서 오른쪽 젓가락을 기다리고 있는 상태가 되므로 모든 철학자가 식사를 하지 못할 것이다.

 

◎ 교착상태 처리

1. 교착 상태 방지
   • 필요조건 4가지 중 최소 1가지를 미충족 시키도록 만들어 교착 상태를 일어나지 않게 함
   • 상호 배타 - 독점적으로 사용할 수 있는 자원 없애기
   • 보유 및 대기 - 프로세스 실행에 필요한 자원을 전부 할당하거나 할당하지 않음
   • 비선점 - 모든 자원을 다른 프로세스에서 빼앗을 수 있게 만듦
   • 환형대기 - 프로세스들을 한 줄로 길게 늘어뜨려 한 방향으로 실행되도록 함
2. 교착 상태 회피
   
   • 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고 만약 교착 상태가 발생할 만큼 자원이 할당된다면 대기 시킴
   • 할당된 자원의 수를 기준으로 시스템은 안정 상태와 불안정 상태로 나뉘는데, 자원을 많이 할당할수록 교착 상태가 발생활 확률이 커져 불안정 상태로 변한다.
   • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다는 점에서 현실과는 맞지 않는 처리 방식이며 자원이 낭비된다는 문제점이 존재
3. 교착 상태 검출 및 복구
   • 교착 상태가 발생할 경우 이를 검출하여 복구시키는 방식으로 가장 현실적인 방식
   • OS가 타임아웃을 사용하여 교착 상태 발생 여부를 계속 주시하는 방식
   • 교착상태 발생 시 교착상태를 유발한 프로세스를 강제 종료
     • 교착상태를 유발한 프로세스 동시 종료
     • 교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
       • 우선순위가 낮은 프로세스 > 작업 시간이 짧은 프로세스 > 자원을 많이 사용하는 프로세스 순으로 먼저 종료시킨다.
4. 교착 상태 무시
   
   • 교착 상태는 드물게 발생하는데 이를 예방, 회피, 탐지 및 복구하기 위해선 비용이 많이 들기 때문에 그냥 무시하는 방식
   • 어디까지나 교착 상태 "처리"에 대해 공부하는 것이지 교착 상태 해결법에 대해 공부하는 것이 아님을 기억하자