[혼공컴운] 5주차 프로세스 동기화, 교착상태

혼공학습단13기 5주차 활동의 일환으로 혼자공부하는 컴퓨터구조 + 운영체제 학습 내용을 정리해보는 포스팅입니다.

오늘은 챕터12 프로세스 동기화, 챕터13 교착상태에 대해 학습해보려고 합니다.

 

 

[목차]

1. 프로세스 동기화
2. 교착 상태
3. 마무리

---

 

1. 프로세스 동기화

 

1) 동기화란

 

프로세스 동기화란 프로세스가 아무렇게나

동시에 실행되지 않도록 올바른 순서대로 실행되도록

맞추는 것을 의미합니다.

 

그리고 동시에 접근해서 안 되는 자원에 하나의 프로세스만

접근하도록 제어하는 것도 의미합니다.

 

즉, 프로세스 동기화란 실행순서 제어와 상호 배제

두가지 측면을 갖고 있습니다.

 

참고로 쓰레드도 동기화 대상입니다.

여러 쓰레드가 동시에 하나의 자원에 접근하면

원하는 결과를 얻지 못할 수 있습니다.

개발하면서 자주 듣게 되는 동시성이라는 키워드도 

이와 관련이 있습니다.

 

프로세스 동기화 중, 상호 배제를 위한 동기화와

관련된 대표 문제가 생산자와 소비자 문제입니다.

 

하나의 전역변수(총합)와 2개의 함수(생산자, 소비자)가 

있다고 가정했을 때, 생산자는 총합 변수를 1증가시키고,

소비자는 총합 변수를 1감소시킨다고 가정해봅시다.

(총합변수는 최초값 1로 가정)

 

이때 생산자가 10,000번 소비자가 10,000번 실행되면

총합변수는 1이 될까요?

 

실제로 실행해보면 1이 아니라 이상한 값들로 나오게 됩니다.

생산자가 소비자 작업이 끝나기도 전에 총합을 수정,

소비자가 생산자 작업이 끝나기도 전에 총합을 수정했기 

때문입니다.

 

여기서 총합이 바로 동시에 접근해서는 안 되는 자원입니다.

이를 공유자원이라고 합니다.

 

공유자원은 전역변수뿐만 아니라 입출력장치, 보조기억장치 등도

될 수 있습니다.

 

동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을

임계구역(critical section)이라고 합니다.

 

두 개 이상 프로세스(혹은 스레드)가 입계 구역에 진입하려고 하면

하나는 대기를 해야 합니다. 

 

그러나 두 개 이상의 프로세스(혹은 스레드)가 동시에 실행되면

문제가 발생하며 이를 레이스 컨디션(race condition)이라고 합니다.

 

임계 구역 문제를 해결하기 위해 3가지 원칙하에 해결합니다.

한 프로세스가 임계구역에 진입했으면 다른 프로세스는 임계구역에 

들어올 수 없다는 상호배제 원칙과 임계구역에 어떤 프로세스도 

진입하지 않았다면 임계구역에 프로세스가 진입할 수 있다는 진행 원칙,

한 프로세스가 임계구역에 진입하기 위해 무한정 대기하면 안 되고 언젠가

들어갈 수 있어야 한다는 유한 대기 원칙이 있습니다.

 

2) 동기화 기법

 

앞서 설명한 동기화를 하기 위한 도구 3가지를 소개합니다.

 

우선 뮤텍스 락이 있습니다. 상호배제를 위한 동기화 도구중 하나이며

자물쇠를 생각하면 됩니다. 탈의실(자원)에 들어갈 사람 2명(프로세스)이

있다고 가정하면 한명이 들어가서 자물쇠를 걸고, 나올때 자물쇠를 풀어서

다른 사람이 들어갈 수 있게 합니다.

 

자물쇠는 전역변수 lock, 임계구역을 잠구는 역할은 acquire(), 임계구역

잠금을 해제하는 역할은 release()로 구현할 수 있습니다.

 

임계구역에 진입하기 전에 acquire()를 호출하는데, 이는 임계구역이 열릴 떄까지

반복 확인하고 열리면 임계구역을 잠구는 함수(lock=true)입니다.

 

release는 임계구역에서의 작업이 끝나고 호출하는 함수입니다.(lock=false) 

 

아래와 같은 수도 코드로 생각해볼 수 있습니다.

acquire() {
	while(lock == true); //임계구역 잠겨있으면 반복 확인
	lock = true; //임계구역 잠겨 있지 않으면 잠금
}

//임계구역 코드(총합 변수 접근)

relaese() {
	lock = false;
}

 

위에서 보시다시피 while을 통해 반복확인을 하는데 이를 바쁜 대기라고 합니다.

 

위에서 설명한 뮤텍스락보다 더 일반화된 동기화 도구가 세마포(혹은 세마포어)입니다.

 

뮤텍스락은 탈의실(자원)이 하나일 경우를 가정해 만든 것이고, 

세마포는 탈의실을 여러개 가정합니다. 이 때 여러 개의 프로세스가

공유 자원이 여러 개 있는 상황에서도 접근할 수 있게 도와주는 도구입니다.

 

뮤텍스락과 비슷하지만 세마포는 전역변수 lock대신 임계구역 진입 가능 프로세스 개수를

나타내는 전역변수 S를 사용합니다.

 

그리고 임계구역에 들어가도 좋은지, 기다려야 하는지 알려주는 wait()과

임계구역 앞에서 기다리는 프로세스에 이제 가도 좋다는 신호를 주는 signal()로 구성됩니다.

 

아래와 같은 수도 코드로 구성할 수 있습니다.

 

wait() {
	while(S <= 0);    
    S--;
}

//임계구역

signal() {
	S++;
}

 

 

S가 진입가능 프로세스 개수이기 때문에, 0이하면

진입가능한 프로세스가 없어서 while로 무한 대기,

이후 진입가능하면 S--로 프로세스를 하나 사용중으로 변경하여 진입합니다.

 

임계구역 작업이 끝나면 signal을 호출하여

진입 가능 프로세스를 하나 올려줍니다(S++).

 

실제로 세마포나 뮤텍스락처럼 while로 바쁜 대기를 하면

CPU 자원을 낭비하는 결과를 초래합니다.

 

그래서 세마포는 실제로 아래와 같이 프로세스가

사용가능한 자원이 없을 경우 PCB를 대기큐에 넣고

다른 프로세스가 끝나서 자원을 반납(signal() 호출)하여

프로세스가 진입가능하면 PCB를 대기큐에서 

제거하여 프로세스를 준비상태로 변경하여 준비큐로 옮겨줍니다.

 

세마포는 좋은 동기화 도구지만 임계구역 앞뒤로 wait(), signal()을 호출해야하고

잘못 코드를 작성할 가능성이 있습니다.

 

그래서 최근에는 모니터라는 동기화 도구를 사용합니다.

 

공유자원과 공유자원에 접근하기 위한 인터페이스를 묶어서 관리합니다.

프로세스는 공유자원을 인터페이스를 통해서만 접근 가능합니다.

 

공유자원에 접근하려면 프로세스를 큐에 삽입하고 삽입된 순서대로

공유자원을 이용합니다.

 

그리고 세마포처럼 실행순서 제어를 위한 동기화도 제공하는데,

이때 조건변수를 사용합니다.

 

조건변수로는 wait(), signal()을 호출할수 있습니다.

조건변수가 x라고 할 때, 모니터에 진입한 어떤 프로세스가

x.wait()을 호출하면 조건변수 x에 대한 큐에 삽입됩니다.

이때 모니터는 비게 되고 다른 프로세스가 모니터에 들어올 수 있습니다.

wait()으로 일시중지된 프로세스는 다른 프로세스의 x.signal()로 

실행이 재개될 수 있습니다.

 

모니터는 자바 언어 기준으로 synchronized 키워드로 구현되었다고 합니다.

 

2. 교착 상태

 

1) 교착 상태란

 

교착상태는 프로세스간 자원의 점유로 서로 무한히 자원을 기다리는 현상을

말합니다.

 

게임 프로세스가 자원B가 필요한데 웹브라우저가 자원B를 점유하고 있고,

웹브라우저가 자원A가 필요한데 게임이 자원A를 점유하고 있어서

서로의 자원을 기다리는 상태를 예시로 들 수 있을 것 같습니다.

 

교착상태를 표현할 때 자원 할당 그래프를 사용합니다.

 

 

위의 사진에서 첫번째는 프로세스D가

프린터 자원을 점유하고 있는 것이고,

프로세스E가 프린터 자원을 기다리는 상태를 나타냅니다.

 

SSD 자원은 3개가 있고 프로세스A가 하나의 자원을 점유한 상태이며,

CPU 자원은 2개가 있고 프로세스 B,C가 할당받고 있는 상태입니다.

그리고 프로세스F는 CPU 할당을 기다리는 상황입니다.

 

두번째는 식사하는 철학자 문제의 그래프로, 철학자들이 왼쪽 포크만 든 채

오른쪽 포크를 기다리고 있기에 교착 상태가 발생한 상황을 나타내고 있습니다.

자원 할당 그래프에서는 그래프가 원의 형태를 띄우고 있으면 교착상태가

일어나는 그래프입니다.

 

교착 상태 발생 조건은 크게 4가지로 정리할 수 있습니다.

 

교착 상태 발생 조건	상세
상호 배제	한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때(상호배제상황) 교착상태 발생
점유와 대기	자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
비선점	어떤 프로세스도 다른 자원을 강제로 빼앗을 수 없기 때문에 교착상태 발생(빼앗는 것이 선점)
원형 대기	프로세스들과 프로세스가 요청 및 할당 받은 자원이 원의 형태를 이루어 교착상태 발생

 

2) 교착 상태 해결 방법

 

교착 상태는 예방, 회피, 검출 후 회복

3가지 해결 방법이 있습니다.

 

교착 상태를 예방하는 방법은

교착 상태 발생 필요 조건 4가지 중

하나를 충족하지 못하게 하는 방법입니다.

 

상호배제, 점유와 대기, 비선점, 원형 대기 중

하나의 조건을 미충족시키면

교착상태는 발생하지 않습니다.

 

상호배제를 미충족시키면 자원을 공유 가능하게 만드는 것을 의미합니다.

그러나 모든 자원의 상호 배제를 없애는 것은 현실적으로 불가능합니다.

프린터는 한번에 하나의 일만 할 수 있는데, 프린터가 공유되어

동시에 두 가지 프린팅은 불가능한 것을 예로 들 수 있습니다.

 

점유와 대기를 미충족시키면 자원 할당의 효율성이 낮아집니다.

특정 프로세스에 자원을 몰아주고, 특정 프로세스는 자원을 쓰지 못하는 

상황이 발생합니다.

특히 많은 자원을 쓰는 프로세스가 불리해집니다.

 

비선점 조건을 없앤다면 프로세스가 자원을 뺏을 수 있습니다.

그러나 모든 자원을 빼앗는 것도 비현실적이기에 범용성이 떨어집니다.

 

원형대기조건을 없애는 것은 모든 자원에 번호를 붙이고

오름차순으로 자원을 할당하는 것입니다.

 

식사하는 철학자 문제에서 탁자를 원형이 아니라 일렬로

만드는 것을 생각하면 될 것 같습니다.

 

그러나 자원에 번호를 붙이는 것은 간단한 일이 아니기 때문에

쉬운 방법은 아닙니다.

 

교착 상태를 회피하는 방법도 있습니다.

프로세스들 간 배분할 수 있는 자원 양을 고려해

교착 상태가 발생 안 할 정도로만 자원을 배분하는 방법입니다.

 

교착상태가 발생하지 않고 모든 프로세스가 정상적으로

자원을 할당받고 종료될 수 있는 상태를 안전 상태라고 합니다.

 

그리고 이 순서를 안전 순서열이라고 합니다.

 

그리고 교착 상태가 발생할 수 있는 상황을 불안전 상태라고 합니다.

 

마지막으로 교착 상태 검출 후 회복은 교착 상태 발생 가능성을

인정하고 이후 처리하는 것입니다.

 

선점을 통해 다른 프로세스로부터 자원을 빼앗아서 교착상태를 해결하거나,

프로세스를 강제 종료하는 등의 방법을 사용합니다.

 

드물게 이를 무시하는 타조 알고리즘도 있습니다.

효율성 측면에서 간간이 사용할 수 있다고 합니다.

 

3. 마무리

 

프로세스의 동기화와 교착 상태에 대해 알아봤습니다.

프로세스는 아니고 자바 언어 공부할 때

멀티 쓰레드 파트에서 배웠던 내용들이 나와서

이해하는데에 조금 더 도움이 되었던 것 같습니다.

 

여행갔다와서 앞에 공부했던게 또 가물가물해서

기억력 왜 이러냐..싶지만 두어번 머리에 스쳐놨기 때문에(?)

분명 안 봤을 때보다 도움이 되고 있다고 믿습니다.

 

마지막 주차까지 꾸준히 해서 유종의 미를 거두고 싶네요!

 

숙제 인증하며 마무리합니다!