[04] 프로세스 교착상태

 

 

교착상태(Deadlock)를 나타내는 그림입니다.

 

1. 병행 프로세스(Concurrent Process) 와 상호배제(Mutual Exclusion)

= 병행 프로세스(Concurrent Process) 란?

두개 이상의 프로세스들이 동시에 존재하며 실행 상태에 있는 것을 의미 합니다. 여러 프로세스들이 독립적으로 실행되는 것을 독립적 병행 프로세서라 하고 서로 협력 하며 동시에 실행 되는 것을 협동적 병행 프로세스라고 합니다.

= 임계구역(Critical Section)

다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유 장원을 의미 합니다. 임계 구역에는 하나의 프로세스만 접근 할 수 있으며, 해단 프로세스가 자원을 반납한 후에만 다른 프로세스가 자원이나 데이터를 사용 할수 있습니다. 임계 구역은 특정 프로세스가 독점 할수 없으며 프로세스가 임계구역에 대한 진입을 요청하면 일정 시간내에 진입을 허락해야 합니다.

= 상호 배제 기법(Mutual Exculsion)

공유자원을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며, 다른 프로세스가 공유자원에 대하여 접근하지 못하게 제어하는 기법으로, 여러 프로세스가 동시에 공유 자원을 사용할 때 각 프로세스가 번갈아 가며 공유 자원을 사용하도록 하는 것으로 임계 구역을 유지하는 기법입니다. 상호배제 기법의 대표적인 방법으로는 데커 알고리즘이 있습니다. 데커 알고리즘은 두개의 프로세서의 상호 배제 문제를 하드웨어의 도움 없이 소프트웨어로 해결한 방법입니다. 이 알고리즘은 의사소통을 위해 공유 메모리를 사용하여 두 프로스세가 하나의 자원을 혼란 없이 공유할 수 있게 합니다.

= 동기화 기법(Synchronization)

두개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 것으로 상호 배제의 한 형태 입니다. 대표적인 동기화 방법으로는 세마포어와 모니터기법이 있습니다.

 

 

2. 교착상태(Deadlock)

= 교착상태(Deadlock)란?

교착상태는 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 말합니다. 결과적으로 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 말합니다. 예를 들어 하나의 사다리가 있고, 두 명의 사람이 각각 사다리와 위쪽과 아래쪽에 있다고 가정합시다. 이때 아래에 있는 사람은 위로 올라가려고 하고, 위에 있는 사람은 아래로 내려 오려고만 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때 까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 됩니다.

 

위 그림과 같이 Objcet2는 Thread2가 점유 하고 있는데 Thread1이 Object2를 점유 요청을 합니다. 그리고 Object1은 Thread1이 점유하고 있는데 Thread2가 Object1을 점유 요청합니다.

 

= 교착상태 발생 조건

교착상태가 발생하기 위해서는 한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야 한다는 상호 배제의 원칙이 적용 되고 프로세스가 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다는 비선점의 원칙이 적용 될때 프로세스가 이미 자원을 갖고 있으면서 다른 자원의 할당을 요구하고 프로세스는 자신이 가지고 있는 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구하면 교착상태가 발생하빈다.

 

= 교착상태 해결 방법

-예방기법 : 교착 상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로, 교착 상태 발생의 4가지 중에서 어느 하나를 제거하는 방

법입니다. 하지만 자원낭비가 가장 심하다는 단점이 있습니다.

.

ⓐ 상호 배제 조건의 부정 : 한번에 여러 개의 프로세스가 공유 자원을 사용할 수 있게 함

 

ⓑ 점유와 대기 조건의 부정 : 프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원 요구를 가능하게 함

 

ⓒ 비선점 조건의 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 함

 

ⓓ 환형 대기 조건의 부정 : 교착 상태의 예방을 위하여 각 자원 유형에 일련의 순서번호를 부여함

-회피기법 : 교착 상태가 발생할 가능성을 배제하지 않고 교착 상태가 발생하면 적절히 피해가는 방법으로 대표적으로 은행원 알고리즘이 있습니다. 은행원 알고리즘은 은행에서 모든 고객의 요구가 총족되도록 현금을 할당 하도록 사용된 데서 유래 되었습니다. 새로운 프로세스가 시스템에 들어갈 때 필요로하는 각 자원 종류에 대해 최대 수요를 정의해야 하며, 이 숫자는 시스템에 있는 모든 자원의 수를 넘지 않아야 합니다. 그리고 사용자가 자원을 요구할 때 시스템은 이 자원의 할당이 시스템을 안정 상태에 머무르게 하는가를 결정해야 합니다. 안정상태에 있다면 자원은 할당되고 그렇지 않다면 다른 프로세스가 충분한 자원을 해제 할때 까지 기다리는 것이 은행원 알고리즘입니다.

 

- 발견기법 : 시스템에 교착 상태가 발생했는지 점검하여 교착 상태에 있는 프로세스와 자원을 발견하는 방법입니다.

- 회복기법 : 교착 상태를 일으킨 프로세스를 종료하고 교착 상태의 프로세스에 할당된 자원을 회수하여 프로세스나 자원을 회복하는 방법입니다.

 

[출처] [운영체제] 4. 프로세스(상호배제/교착상태/임계구역/상호배제)|작성자 보리