[OS] 경쟁상태, 교착상태, 라이브락 (Race Condition, Deadlock, Livelock)

경쟁상태 (Race Condition)

둘 이상의 입력이나 조작이 동시에 일어나 의도하지 않은 결과를 가져오는 경우를 말합니다.

- 파일 또는 변수와 같은 공유 자원을 접근하는 하나 또는 그 이상의 프로세스들의 다중 접근이 제대로 제어되지 않은 것을 말합니다.

- 프로세스들 끼리 하나의 자원을 갖기 위해 싸우는 것, 하나의 자원을 동시에 요청

라이브락 (Livelock)

한 프로세스가 이미 자원을 점유한 상태에서 다른 프로세스가 그 자원을 사용하기 위해 무한정 대기상태에 빠지는 것을 라이브락이라 합니다.

- 지극히 정상적인 동작이지만 분명 문제가 있는 동작입니다.

교착상태 (DeadLock)

프로세스들이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태로, 시스템 자원에 대한 경쟁 도중에 발생할 수도 있고 프로세스간의 통신 과정에서도 발생할 수 있습니다.

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로는 아무것도 완료되지 못하는 상태를 말합니다.

- A프로세스가 A자원을 점유하고 B프로세스가 B자원을 점유한 상태에서 A프로세스의 다음 작업으로 B자원이 필요하고 B프로세스의 다음 자원으로 A자원이 필요할 경우, 서로의 작업이 끝나기만을 기다리며 아무것도 실행되지 않는 상태라고 할 수 있습니다.

- 경쟁상태도 교착상태(DeadLock)의 종류 중 하나입니다.

교착상태 조건

- 상호배제 (Mutual Exclusion) : 한 순간에 한 프로세스만이 자원을 사용할 수 있다. 즉, 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수 없다.

- 점유대기 (Hold and Wait) : 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다리고 있다.

- 비선점 (No preemption) : 프로세스에 의해 점유된 자원을 다른 프로세스가 강제적으로 빼앗을 수 없다.

- 환형대기 (Circular Wait) : 프로세스간에 닫힌 연결이 존재할 경우입니다. 블록된 프로세스가 자원을 점유하고 있는데 이 자원을 다른 프로세스가 원하며 대기하고 있는 상태입니다.

교착상태를 발생시킨다고해서 이 조건들이 잘못된 조건은 아닙니다.

예를 들면, 상호배제는 수행 결과의 일관성과 데이터베이스의 무결성을 위해 반드시 필요합니다. 

선점 또한 임의대로 수행되어서는 안됩니다. 특히, 데이터 자원이 연관되어 있는 경우 선점은 롤백 복구 기법의 지원이 있어야만 가능합니다.

- 프로세스가 다시 재수행 될 수 있도록 프로세스의 상태와 사용하던 자원의 상태를 안정적인 이전의 상태로 복원할 수 있어야 함을 의미.

- 환형대기의 경우 조건 1 ~ 3의 결과에 의해 발생하게 된다.

교착상태 예방, 회피, 발견

접근 방법	자원 할당 정책	구체적인 기법	장점	단점
예방	보수적 - 자원할당이 가능하더라도 조건에 따라 할당하지 않을 수 있다.	모든 자원을 한꺼번에 요구 - 점유대기 배제	- 순간적으로 많은 일을 하는 프로세스에 적합 - 선점이 불필요	- 효율이 나쁨 - 프로세스 시작을 지연시킬 가능성 있음 - 프로세스는 사용할 모든 자원을 미리 알고 있어야 함
		선점 가능 - 비선점 배제	- 자원 상태의 저장과 복구가 간단한 자원에는 적용하기 쉬움	- 선점이 필요보다 자주 일어남
		자원할당 순서 - 환형대기 배제	- 컴파일 시점에 강제할 수 있음 - 시스템의 설계 시점에 문제를 해결했기 때문에 동적 부하가 없음	- 점진적인 자원 할당이 안됨
회피	예방과 발견의 중간 정도	교착 상태가 발생하지 않는 안전한 경로를 최소한 하나는 유지	- 선점이 불필요	- 운영체제는 자원에 대한 미래 요구량을 미리 알고 있어야 함 - 오랜 기간 지연 발생의 가능성 있음
발견	적극적 - 자원 할당이 가능하면 즉시 할당한다.	주기적으로 교착상태 발생 여부 파악	- 프로세스 시작을 지연시키지 않음 - 온라인 처리 가능	- 선점에 의한 손실 발생

교착상태 예방 기법

교착상태 예방 전략은 운영체제를 설계할 때 교착상태가 발생할 가능성을 없애는 것입니다.

위에서 설명한 교착상태 발생 조건 중 하나를 설계 단계에서 배제하는 것입니다. 교착상태 예방 방법은 크게 간접적인 방법과 직접적인 방법으로 구분할 수 있습니다.

- 간접적 방법 : 1 ~ 3의 조건 중 하나를 허용하지 않는 것

- 직접적 방법 : 4. 환형대기를 허용하지 않는 것

상호배제 조건은 공유 자원의 일관성을 유지하기 위해 반드시 필요하기 때문에, 자원 접근에서 상호 배제가 필요하면 이를 운영체제가 지원해주어야 합니다.

점유대기 조건 배제 : 프로세스는 자신이 사용 할 모든 자원을 한 순간에 요청합니다. 만약 모든 자원을 할당받을 수 있으면 계속 수행하고 하나의 자원이라도 할당받을 수 없으면 어떠한 자원도 할당받지 않고 대기합니다.

- 점유대기를 배제할 경우 비효율적입니다.

- 프로세스들은 모든 자원을 할당받기 위해 오랜 시간 대기상태에 있게 됩니다.

- 한꺼번에 할당받은 자원 중 일부는 실제 수행이 끝날 때 쯤 사용될 수 있습니다. 이용되지도 않는 자원이 점유된 상태가 됩니다.

- 프로세스가 미래에 사용할 자원이 무엇인지 모두 알기는 어렵습니다.

비선점 조건 배제 : 두 가지 조건으로 없앨 수 있습니다.

1. 자원을 점유한 프로세스가 다른 자원을 요청했을 때 할당받을 수 없다면 자신이 점유한 자원을 반납하고 이후 프로세스는 원래 자원과 새로 원하는 자원을 함께 요청합니다.

2. 한 프로세스에서 다른 프로세스가 점유한 자원을 원하면 운영체제는 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스에 할당할 수 있습니다. (프로세스들이 서로 다른 우선순위를 갖고 있을 때 교착상태를 예방할 수 있습니다.)

- 상태를 저장하고 복구시키기 쉬운 자원에 적용할 수 있습니다.

환형대기 조건 배제 : 자원들의 할당 순서를 정하면 없앨 수 있습니다.

- 만일 프로세스가 자원 R을 할당받았으면 이후 이 프로세스는 자원 R의 다음 순서를 갖는 자원들을 요청할 수 있는 것입니다.

- 결국, 자원들의 할당 순서를 정하면 교착상태가 발생하지 않게 됩니다.

- 환형대기를 없애는 것은 프로세스의 수행 지연과 불필요한 자원의 할당 거부 문제가 일어날 수 있습니다.

교착상태 회피 기법

교착상태를 해결할 수 있는 또 다른 기법은 회피입니다.

- 교착상태 예방은 교착상태 발생을 위해 필요한 네가지 조건 중 하나를 배제하는 방법으로 자원 사용과 프로세스 수행에 비효율성을 이야기할 수 있습니다.

- 반면, 교착상태 회피는 교착상태 발생 조건 중 1~3은 허용합니다. 그리고 자원 할당 순서를 미리 정하지도 않습니다.

- 대신, 자원을 할당할 때 교착상태가 발생 가능한 상황으로 진행하지 않도록 고려합니다.

- 때문에, 회피 방법은 예방 방법에 비해 더 많은 병행성을 제공합니다. (자원 사용의 효율성이 높다)

- 하지만, 회피 방법은 현재 자원의 가용 개수와 프로세스의 자원 요구량을 미리 알고 있어야 가능합니다.

프로세스가 시작하려고 할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있으면 프로세스를 시작시키지 않습니다.

수행 중인 프로세스가 요구하는 추가적인 자원 할당이 교착상태 발생의 가능성이 있으면 자원을 할당하지 않습니다.

교착상태 발견 기법

교착상태 발견은 자원 할당이 요구될 때마다 매번 수행될 수도 있고 주기적으로 가끔 수행 될 수도 있습니다.

자원 할당이 요구될 때마다 매번 수행되면 교착상태를 빠른 시점에 발견할 수 있으며, 또한 시스템의 상태가 점진적으로 변하기 때문에 발견 알고리즘도 간단해진다는 장점이 있습니다. 하지만, 매번 시도될 때마다 발생하는 처리 비용이 커진다는 단점이 있습니다.

- 발견 기법에 해당하는 알고리즘, 자원 할당 그래프, 시간의 상한값 등 여러가지 방법이 있습니다. 

교착상태를 발견하게 되면 이를 회복하기 위한 기법이 필요합니다.

교착상태 회복 기법에는 아래와 같은 것이 있습니다.

- 교착상태에 포함되어 있는 모든 프로세스를 중지시킨다. 

 + 실제로, 많은 운영체제에서 사용되는 방법 중 하나이다.

- 교착상태에 포함되어 있는 각 프로세스의 수행을 롤백시킨다.

 + 미리 정의된 특정 체크포인트 시점까지 되돌린 후 다시 수행시킨다. 또 다시 교착상태에 빠질 수 있음.

- 교착상태가 없어질 때까지 교착상태에 포함되어있는 프로세스를 하나씩 종료시킨다.

 + 종료시킬 프로세스는 가장 비용이 작은 것으로 한다.

- 교착상태가 없어질 때까지 교착 상태에 포함되어 있는 자원을 하나씩 선점시킨다.

 + 비용이 가장 작은 자원부터 선택하고 하나씩 선점한 후 교착상태 발견 알고리즘을 수행시켜 아직 교착상태가 존재하는지 확인한다.

 + 이 때, 자원을 선점당한 프로세스는 자원을 할당받기 전 시점으로 롤백하고, 그 시점부터 다시 수행한다.

출처 : http://wonjayk.tistory.com/251