[운영체제/OS] 병행 프로세스 동기화 유형

6 분 소요

<h1 id="임계-구역critical-section">임계 구역(Critical Section)</h1>
다중 프로그래밍 운영체제에서 한순간에 여러 개의 프로세스에 의하여 공유되는 데이터 및 자원에 대하여 반드시 하나의 프로세스에 의해서만 자원 또는 데이터가 사용되도록하는 것으로 자원이 프로세스에 의하여 반납된 후, 비로소 다른 프로세스에서 자원을 이용하거나 데이터를 접근할 수 있도록 지정된 영역이다.

하나의 컴퓨터 시스템에서 여러 개의 프로세스가 운영되고 있을 때 각 프로세스는 동시에 접근해서는 안 되는 공유 자원을 임계 구역이라 할 수 있으며 여기에는 메모리, 프린터, 디스크, CD-ROM이 있다

<ul>
 <li>두 개 이상의 프로세스가 동시에 사용할 수 없다</li>
 <li>순서를 지키면서 신속하게 사용</li>
 <li>하나의 프로세스가 독점하게 해서는 안된다</li>
 <li>사용 중에 중단, 무한 반복되어서는 안된다</li>
 <li>인터럽트가 불가능한 상태로 만들어야 한다</li>
</ul>

<h1 id="상호-배제mutual-exclusion">상호 배제(Mutual Exclusion)</h1>
임계 구역을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며, 다른 프로세스가 현재 사용 중인 임계 구역에 대하여 접근하려고 할 때 금지하는 행위를 <code class="language-plaintext highlighter-rouge">상호배제</code>라고 한다. 상호배제 알고리즘은 인터럽트 불능 처리, 잠금, 엄격한 교대, TSL, 세마포어 등이 있다

<h2 id="상호-배제-알고리즘">상호 배제 알고리즘</h2>
<h3 id="인터럽트-불능-처리">인터럽트 불능 처리</h3>
하나의 프로세스가 하나의 공유 자원을 점유하게 되면 인터럽트를 발생하지 않도록 봉쇄한다.

인터럽트를 봉쇄한다는 것은 현시점에서 어떠한 프로세스도 새롭게 자원을 점유하기 위한 시도를 할 수 없게 된다는 의미히며 즉, 현재 공유 자원을 점유한 프로세스는 아무런 제약 없이 공유 자원을 사용하게 되므로 완벽한 상호배제를 할 수 있다.

하지만 하나의 프로세스가 공유 자원을 점유하고 있는 동안 다른 프로세스는 아무런 작업을 할수 없는 상태이므로 시스템 효율이 매우 낮아진다.

<h3 id="잠금lock">잠금(Lock)</h3>
공유 자원을 점유하게 되는 경우 그 자원을 어떠한 프로세스도 접근하지 못하도록 하는 방법

공유 자원을 점유하는 프로세스는 사용을 시작하면서 공유 자원에 접근하려는 모든 프로세스가 사용할 수 없도록 표시를 하게 된다. 이 때 이미 점유되어 있는 공유자원을 사용하기 위해 접근하고 있는 임의의 프로세스들은 표시를 계속 확인하게 되는데 이를 바쁜 대기(Busy Wait) 상태라고 한다

<h3 id="엄격한-교대dekker-알고리즘">엄격한 교대(Dekker 알고리즘)</h3>
두 개 이상의 프로세스가 교대로 공유 자원을 점유하는 방식

프로세스 A가 공유 자원을 점유하고 나면 프로세스 B는 프로세스 A가 사용 해제를 통보하길 기다렸다가 사용한다

한쪽 프로세스가 점유 시간이 길어지면 나머지 프로세스는 사용 가능한가를 계속 감지하는 작업을 반복해야한다. 즉, 바쁜 대기 현상은 계속 발생한다.

하나의 프로세스가 우선권을 갖게 해야 하며, 한쪽이 작업량이 많아서 빈번해져도 반드시 교대로 점유해야한다(하나의 프로세스를 연속적으로 재사용 불가)

하나의 프로세스가 사용 중에 중단되면 다른 프로세스는 영원히 사용할 수 없는 교착상태에 빠지게 된다

<h3 id="tsltest--set-lock-명령어-기법">TSL(Test & Set Lock) 명령어 기법</h3>
엄격한 교대의 문제점을 해결하는 방법으로 특수한 하드웨어 자원을 필요로 하지만, 바쁜 대기 상태는 완벽히 해결하지는 못한다

<ol>
 <li>프로세스 A,B 모두 각자의 변수 x,y를 갖게 되며 각 프로세스는 x,y값이 모두 0일 때 공유 자원을 사용할 수 있다</li>
 <li>프로세스 A가 공유 자원을 사용하기 위해서는 y값이 0인가를 확인한다. y값이 1이라면 프로세스 B가 사용 중이다</li>
 <li>프로세스 B가 공유 자원을 사용하기 위해서는 x값이 0인가를 확인한다. x값이 1이라면 프로세스 A가 사용 중이다</li>
 <li>상대 프로세스가 가진 변수 값이 0인 경우에만 공유 자원을 점유할 수 있게 되고 점유하자마자 변수를 1로 변경하고 사용 후에는 0으로 변경한다</li>
</ol>

<ul>
 <li>
 Sleep() / Wakeup() 
TSL의 교착 상태와 바쁜 대기 현상의 단점 중 바쁜 대기의 문제점을 보완한 방법

하나의 공유 자원을 점유하기 위한 시도를 반복하지 않고 사용하려는 공유 자원이 이미 사용 중이라면 프로세스를 잠시 중단하게 한다(<code class="language-plaintext highlighter-rouge">Sleep</code>, Wait, P, Down), 이후 어느 정도의 시간이 지나서 공유 자원이 사용 가능하다면 잠시 중단하고 있던 프로세스를 활성화(<code class="language-plaintext highlighter-rouge">Wakeup</code>, Signal, V, Up)하여 바쁜 대기 현상을 방지하는 방법
 </li>
</ul>

<h1 id="세마포어semaphore">세마포어(Semaphore)</h1>
프로세스 간의 상호배제 및 동기화 문제 해결 방법

P(S), V(S) 연산을 통해서 프로세스 사이의 동기를 유지하고 상호배제의 원리 보장

<ul>
 <li>이진 세마포어
 <ul>
 <li>세마포어 변수가 오직 0과 1값을 가지며 하나의 임계 구역만을 상호배제하기 위한 알고리즘</li>
 <li>잠금, 엄격한 교대, TSL</li>
 </ul>
 </li>
 <li>산술(계수형 세마포어)
 <ul>
 <li>세마포어 변수가 0과 양의 정수를 값으로 가지며 임계 구역을 여러 개 관리하기 위한 상호배제 알고리즘</li>
 </ul>
 </li>
</ul>

<ul>
 <li>여러 개의 프로세스가 동시에 그값을 수정하지 못한다</li>
 <li>세마포어에 대한 연산은 처리 중에 인터럽트 되어서는 안된다</li>
 <li>세마포어데 대한 연산은 소프트웨어나 하드웨어로 구현 가능</li>
 <li><code class="language-plaintext highlighter-rouge">V</code> 조작은 블록 큐에 대기 중인 프로세스를 깨우는 신호로서, 흔히 Signal 동작이라 한다</li>
 <li><code class="language-plaintext highlighter-rouge">P</code> 조작은 임계 영역을 사용하려는 프로세서들의 진입 여부를 결정하는 것으로, 흔히 Wait 동작이라 한다</li>
</ul>

<h1 id="모니터monitor">모니터(Monitor)</h1>
상호배제를 위한 데이터 및 프로그램 모듈로 운영체제 내부의 프로그램을 모니터라고 한다. 공유 자원을 사용하기 위해 기다리는 프로세스들은 모니터에 진입해도 좋다는 허가를 기다리며 모니터에서는 프로세스들의 공유 자원 점유 순서를 제어한다

<ul>
 <li>두 개 이상의 프로세스가 특정 공유 자원을 순차적으로 할당하는 데 필요한 데이터 및 프로시저를 포함하는 병행성 구조(Concurrency Construct)이다</li>
 <li>모니터 내의 자원을 원하는 프로세스는 반드시 해당 모니터의 진입부를 호출해야 한다</li>
 <li>모니터 외부의 프로세스는 모니터 내부의 데이터를 직접 접근 불가</li>
 <li>자료 추상화와 정보 은폐의 개념을 기초적으로 사용</li>
 <li>스위치 개념을 사용하여 한순간에 하나의 프로세스만이 모니터에 진입 가능</li>
 <li>모니터에서 사용되는 연산은 Wait와 Signal이 있다</li>
 <li>모니터의 경계에서 상호배제가 시행</li>
</ul>

두 개 이상의 프로세스가 하나의 자원을 공유하여 사용하고 있을 때 서로가 사용 중인 자원을 요구하지만 요구를 영원히 들어줄 수 없는 상태를 의미

<h2 id="교착상태-발생-필수-4대-요소">교착상태 발생 필수 4대 요소</h2>
<h3 id="상호배제mutual-exclusion">상호배제(Mutual Exclusion)</h3>
여러 개의 프로세스를 동시에 운영하는 다중 프로그래밍 방식에서는 제한된 자원을 서로 공유하면서 효율적으로 사용해야 하기 때문에 상호배제를 해야 한다. 이러한 상호배제는 여러 개의 프로세스를 동시에 처리하기 위하여 공유 자원을 순차적 처리하면서, 동시에 접근하지 못하도록 해야 한다.

하지만, 이러한 상호배제가 실패하게 되면 교착상태가 발생할 수 있기 때문에 상호배제는 교착상태 발생의 필수 조건 중 하나가 된다

<h3 id="점유와-대기hold--wait">점유와 대기(Hold & Wait)</h3>
시스템의 성능을 높이기 위해서는 여러 개의 프로세스를 동시에 운영하면서 사용 중이거나 사용 중이 아닌 공유 자원들을 순차적으로 배분해 주어야 시스템 성능이 향상될 것이다

따라서 점유와 대기는 존재할 수 밖에 없고 이는 교착상태 발생의 필수 조건 중 하나가 된다

<h3 id="비선점non-preemption">비선점(Non-Preemption)</h3>
비선점이란, 이미 사용 중인 공유 자원들을 빼앗을 수 없다는 의미

하나의 프로세스가 특정 공유 자원을 사용하다가 프로그램 루틴의 문제로 임계 구역 내부에서 중단되었을 때 만약 이 자원을 빼앗을 수 없다면 이 자원을 사용하기 위해 대기 중이던 프로세스는 영원히 원하는 자원을 빼앗을 수 없다는 것은 비선점이고 이는 교착상태 발생의 필수 조건 중에 하나가 된다

<h3 id="순환-대기circular-wait-환형-대기">순환 대기(Circular Wait, 환형 대기)</h3>
공유 자원들을 프로세스에게 분배할 때 입력 순으로 순차적으로 분배한다면 시간이 오래 걸려 성능이 떨어질 뿐 교착상태는 발생하지 않을 것이다. 순차적으로 분배하지 않고 당장 사용하지 않는 자원은 다른 프로세스가 사용하게 한다면 자원을 효율적으로 사용하게 될 것이다.

이처럼 모든 프로세스와 자원을 순차적으로 사용하지 않고 사용 시기와 순서를 융통성있게 조절하게 될 때 프로세스의 자원의 점유와 대기 상태는 환형 상태가 될 수 있다.

<h2 id="교착상태-해결-방안">교착상태 해결 방안</h2>
<h3 id="예방prevention">예방(Prevention)</h3>
교착상태가 절대 발생하지 않도록 사전에 조치를 취하는 방안이지만, 성능은 낮아질 수 밖에 없다. 교착상태 발생의 네 가지 조건 중에서 하나를 제거함으로서 처리

<ul>
 <li>
 상호배제 부정
단일 프로그램을 운영하거나, 자원을 독립적으로 사용하여 임계 구역을 없애고 상호배제를 하지 않는다면 교착상태는 절대 발생하지 않는다. 하지만 자원의 낭비나 신뢰성이 낮아지기 때문에 사용하기에 적절하지 않은 방법
 </li>
 <li>
 점유와 대기 부정
각 프로세스는 한 번에 자신에게 필요한 모든 자원을 요구해야 하며, 이 요구가 만족되지 않으면 작업을 진행할 수 없다. 또한 어떤 자원을 갖고 있는 프로세스가 더 이상 요구가 수용되지 않으면 원래 갖고 있던 자원을 일단 반납하고 필요하다면 다시 그 자원이나 다른 자원을 요구해야 한다
 </li>
 <li>
 비선점 부정
프로세스가 점유하고 있는 자원들을 언제든 빼앗을 수 있도록 한다
 </li>
 <li>
 순환 대기 부정
한 프로세스가 주어진 유형의 자원을 할당받았으면 그 프로세스는 순서에 따라 나중에 위치하는 유형의 자원말을 요구할 수 있게 한다

<h3 id="회피avoidance">회피(Avoidance)</h3>
프로세스가 자원을 요구할 때 시스템이 안전(교착상태가 발생하지 않는 범위 내) 상태를 유지할 수 있는 프로세스의 자원 요구만을 할당해주는 방안

<h4 id="은행원-알고리즘bankers-algorithm">은행원 알고리즘(Banker’s Algorithm)</h4>

Dijkstra가 제안한 방식으로 불안전 상태와 안전 상태로 구분한다. 안전 상태에서는 교착상태가 발생하지 않으며, 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자의 수가 일정해야 한다. 또한 모든 요구를 정해진 시간 안에 할당하는 것을 보장해야 한다.

하지만, 은행원 알고리즘은 응답 시간이 보장되어야 하는 대화식 시스템에 적용하기 어렵다

<ul>
 <li>은행원 : 운영체제</li>
 <li>대출자 : 프로세스</li>
 <li>은행 보유 금액 : 자원 수</li>
 <li>현재 대출 금액 : 각 프로세스가 점유하고 잇는 자원 수</li>
 <li>대출 한도 금액 : 프로세스가 완료할 때까지 필요한 총 자원 수</li>
</ul>

<h3 id="발견detection">발견(Detection)</h3>
자원 할당 그래프는 시스템이 주된 이유가 교착상태인가를 발견하는 기법. 교착상태임이 발견되면 해당 프로세스와 자원을 선점하거나 중단 시켜 교착상태 해결

<h3 id="회복recovery">회복(Recovery)</h3>
실행 중인 모든 프로세스가 정상적으로 작업을 완료할 수 없기 때문에 발생한 교착상태이므로 어느 정도의 희생은 감수해야 한다. 즉, 실행을 중단하거나 점유 중인 자원을 빼앗을 프로세스를 찾는 일로 가능한 손실이 적은 쪽을 선택해야 한다

<ul>
 <li>선점을 통한 회복
 <ul>
 <li>보유하고 있는 자원을 빼앗아 교착상태를 해결하고 시스템을 정상으로 회복하는 방법</li>
 <li>우선순위가 낮은, 진행 상태가 적은, 자원을 적게 사용하고 있는 프로세스의 자원을 선점하여 프로세스를 일시 중단</li>
 </ul>
 </li>
 <li>복귀(Rollback)를 통한 회복
 <ul>
 <li>교착상태가 발생하기 이전 상태로 복귀하여 다시 실행하는 방법</li>
 <li>현재 실행 중인 전체 프로세스를 대상으로 할 수 있지만 더욱 효과적인 방법은 교착상태를 해결할 만큼의 프로세스들만을 선택하여 처음부터 다시 실행하는 것</li>
 <li>현재까지 실행되고 있는 프로세스와 중단된 프로세스의 정보를 재구성해야하는 어려움이 존재</li>
 </ul>
 </li>
 <li>제거(Kill)를 통한 회복
 <ul>
 <li>우선순위가 낮은, 진행 상태가 적은, 자원을 적게 사용하고 있는 프로세스를 선택하여 제거</li>
 <li>기아 상태나 문제가 있는 프로세스 제거</li>
 <li>정상 수행이 불가능한 모든 프로세스를 제거하고 다시 시작</li>
 </ul>
 </li>
 <li>사용자의 조치 경로(Routing) 선택
 <ul>
 <li>Window OS : Ctrl + Alt + Delete를 입력하면 현재 작동 중인 프로세스 리스트가 나오게 되는데 이 때 문제가 있는 프로세스를 선택하여 제거</li>
 <li>Unix OS : ps 명령을 입력하면 현재 프로세스들의 리스트가 출력되는데 이 때 문제가 있는 프로세스들을 kill/killall 명령으로 제거</li>
 </ul>
 </li>
</ul>

임계 구역(Critical Section)

다중 프로그래밍 운영체제에서 한순간에 여러 개의 프로세스에 의하여 공유되는 데이터 및 자원에 대하여 반드시 하나의 프로세스에 의해서만 자원 또는 데이터가 사용되도록하는 것으로 자원이 프로세스에 의하여 반납된 후, 비로소 다른 프로세스에서 자원을 이용하거나 데이터를 접근할 수 있도록 지정된 영역이다.

하나의 컴퓨터 시스템에서 여러 개의 프로세스가 운영되고 있을 때 각 프로세스는 동시에 접근해서는 안 되는 공유 자원을 임계 구역이라 할 수 있으며 여기에는 메모리, 프린터, 디스크, CD-ROM이 있다

두 개 이상의 프로세스가 동시에 사용할 수 없다
순서를 지키면서 신속하게 사용
하나의 프로세스가 독점하게 해서는 안된다
사용 중에 중단, 무한 반복되어서는 안된다
인터럽트가 불가능한 상태로 만들어야 한다

상호 배제(Mutual Exclusion)

임계 구역을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며, 다른 프로세스가 현재 사용 중인 임계 구역에 대하여 접근하려고 할 때 금지하는 행위를 상호배제라고 한다. 상호배제 알고리즘은 인터럽트 불능 처리, 잠금, 엄격한 교대, TSL, 세마포어 등이 있다

상호 배제 알고리즘

인터럽트 불능 처리

하나의 프로세스가 하나의 공유 자원을 점유하게 되면 인터럽트를 발생하지 않도록 봉쇄한다.

인터럽트를 봉쇄한다는 것은 현시점에서 어떠한 프로세스도 새롭게 자원을 점유하기 위한 시도를 할 수 없게 된다는 의미히며 즉, 현재 공유 자원을 점유한 프로세스는 아무런 제약 없이 공유 자원을 사용하게 되므로 완벽한 상호배제를 할 수 있다.

하지만 하나의 프로세스가 공유 자원을 점유하고 있는 동안 다른 프로세스는 아무런 작업을 할수 없는 상태이므로 시스템 효율이 매우 낮아진다.

잠금(Lock)

공유 자원을 점유하게 되는 경우 그 자원을 어떠한 프로세스도 접근하지 못하도록 하는 방법

공유 자원을 점유하는 프로세스는 사용을 시작하면서 공유 자원에 접근하려는 모든 프로세스가 사용할 수 없도록 표시를 하게 된다. 이 때 이미 점유되어 있는 공유자원을 사용하기 위해 접근하고 있는 임의의 프로세스들은 표시를 계속 확인하게 되는데 이를 바쁜 대기(Busy Wait) 상태라고 한다

엄격한 교대(Dekker 알고리즘)

두 개 이상의 프로세스가 교대로 공유 자원을 점유하는 방식

프로세스 A가 공유 자원을 점유하고 나면 프로세스 B는 프로세스 A가 사용 해제를 통보하길 기다렸다가 사용한다

한쪽 프로세스가 점유 시간이 길어지면 나머지 프로세스는 사용 가능한가를 계속 감지하는 작업을 반복해야한다. 즉, 바쁜 대기 현상은 계속 발생한다.

하나의 프로세스가 우선권을 갖게 해야 하며, 한쪽이 작업량이 많아서 빈번해져도 반드시 교대로 점유해야한다(하나의 프로세스를 연속적으로 재사용 불가)

하나의 프로세스가 사용 중에 중단되면 다른 프로세스는 영원히 사용할 수 없는 교착상태에 빠지게 된다

TSL(Test & Set Lock) 명령어 기법

엄격한 교대의 문제점을 해결하는 방법으로 특수한 하드웨어 자원을 필요로 하지만, 바쁜 대기 상태는 완벽히 해결하지는 못한다

프로세스 A,B 모두 각자의 변수 x,y를 갖게 되며 각 프로세스는 x,y값이 모두 0일 때 공유 자원을 사용할 수 있다
프로세스 A가 공유 자원을 사용하기 위해서는 y값이 0인가를 확인한다. y값이 1이라면 프로세스 B가 사용 중이다
프로세스 B가 공유 자원을 사용하기 위해서는 x값이 0인가를 확인한다. x값이 1이라면 프로세스 A가 사용 중이다
상대 프로세스가 가진 변수 값이 0인 경우에만 공유 자원을 점유할 수 있게 되고 점유하자마자 변수를 1로 변경하고 사용 후에는 0으로 변경한다

Sleep() / Wakeup()
TSL의 교착 상태와 바쁜 대기 현상의 단점 중 바쁜 대기의 문제점을 보완한 방법

하나의 공유 자원을 점유하기 위한 시도를 반복하지 않고 사용하려는 공유 자원이 이미 사용 중이라면 프로세스를 잠시 중단하게 한다(Sleep, Wait, P, Down), 이후 어느 정도의 시간이 지나서 공유 자원이 사용 가능하다면 잠시 중단하고 있던 프로세스를 활성화(Wakeup, Signal, V, Up)하여 바쁜 대기 현상을 방지하는 방법

세마포어(Semaphore)

프로세스 간의 상호배제 및 동기화 문제 해결 방법

P(S), V(S) 연산을 통해서 프로세스 사이의 동기를 유지하고 상호배제의 원리 보장

이진 세마포어
- 세마포어 변수가 오직 0과 1값을 가지며 하나의 임계 구역만을 상호배제하기 위한 알고리즘
- 잠금, 엄격한 교대, TSL
산술(계수형 세마포어)
- 세마포어 변수가 0과 양의 정수를 값으로 가지며 임계 구역을 여러 개 관리하기 위한 상호배제 알고리즘

여러 개의 프로세스가 동시에 그값을 수정하지 못한다
세마포어에 대한 연산은 처리 중에 인터럽트 되어서는 안된다
세마포어데 대한 연산은 소프트웨어나 하드웨어로 구현 가능
V 조작은 블록 큐에 대기 중인 프로세스를 깨우는 신호로서, 흔히 Signal 동작이라 한다
P 조작은 임계 영역을 사용하려는 프로세서들의 진입 여부를 결정하는 것으로, 흔히 Wait 동작이라 한다

모니터(Monitor)

상호배제를 위한 데이터 및 프로그램 모듈로 운영체제 내부의 프로그램을 모니터라고 한다. 공유 자원을 사용하기 위해 기다리는 프로세스들은 모니터에 진입해도 좋다는 허가를 기다리며 모니터에서는 프로세스들의 공유 자원 점유 순서를 제어한다

두 개 이상의 프로세스가 특정 공유 자원을 순차적으로 할당하는 데 필요한 데이터 및 프로시저를 포함하는 병행성 구조(Concurrency Construct)이다
모니터 내의 자원을 원하는 프로세스는 반드시 해당 모니터의 진입부를 호출해야 한다
모니터 외부의 프로세스는 모니터 내부의 데이터를 직접 접근 불가
자료 추상화와 정보 은폐의 개념을 기초적으로 사용
스위치 개념을 사용하여 한순간에 하나의 프로세스만이 모니터에 진입 가능
모니터에서 사용되는 연산은 Wait와 Signal이 있다
모니터의 경계에서 상호배제가 시행

교착상태(Dead-Lock)

두 개 이상의 프로세스가 하나의 자원을 공유하여 사용하고 있을 때 서로가 사용 중인 자원을 요구하지만 요구를 영원히 들어줄 수 없는 상태를 의미

교착상태 발생 필수 4대 요소

상호배제(Mutual Exclusion)

여러 개의 프로세스를 동시에 운영하는 다중 프로그래밍 방식에서는 제한된 자원을 서로 공유하면서 효율적으로 사용해야 하기 때문에 상호배제를 해야 한다. 이러한 상호배제는 여러 개의 프로세스를 동시에 처리하기 위하여 공유 자원을 순차적 처리하면서, 동시에 접근하지 못하도록 해야 한다.

하지만, 이러한 상호배제가 실패하게 되면 교착상태가 발생할 수 있기 때문에 상호배제는 교착상태 발생의 필수 조건 중 하나가 된다

점유와 대기(Hold & Wait)

시스템의 성능을 높이기 위해서는 여러 개의 프로세스를 동시에 운영하면서 사용 중이거나 사용 중이 아닌 공유 자원들을 순차적으로 배분해 주어야 시스템 성능이 향상될 것이다

따라서 점유와 대기는 존재할 수 밖에 없고 이는 교착상태 발생의 필수 조건 중 하나가 된다

비선점(Non-Preemption)

비선점이란, 이미 사용 중인 공유 자원들을 빼앗을 수 없다는 의미

하나의 프로세스가 특정 공유 자원을 사용하다가 프로그램 루틴의 문제로 임계 구역 내부에서 중단되었을 때 만약 이 자원을 빼앗을 수 없다면 이 자원을 사용하기 위해 대기 중이던 프로세스는 영원히 원하는 자원을 빼앗을 수 없다는 것은 비선점이고 이는 교착상태 발생의 필수 조건 중에 하나가 된다

순환 대기(Circular Wait, 환형 대기)

공유 자원들을 프로세스에게 분배할 때 입력 순으로 순차적으로 분배한다면 시간이 오래 걸려 성능이 떨어질 뿐 교착상태는 발생하지 않을 것이다. 순차적으로 분배하지 않고 당장 사용하지 않는 자원은 다른 프로세스가 사용하게 한다면 자원을 효율적으로 사용하게 될 것이다.

이처럼 모든 프로세스와 자원을 순차적으로 사용하지 않고 사용 시기와 순서를 융통성있게 조절하게 될 때 프로세스의 자원의 점유와 대기 상태는 환형 상태가 될 수 있다.

교착상태 해결 방안

예방(Prevention)

교착상태가 절대 발생하지 않도록 사전에 조치를 취하는 방안이지만, 성능은 낮아질 수 밖에 없다. 교착상태 발생의 네 가지 조건 중에서 하나를 제거함으로서 처리

상호배제 부정 단일 프로그램을 운영하거나, 자원을 독립적으로 사용하여 임계 구역을 없애고 상호배제를 하지 않는다면 교착상태는 절대 발생하지 않는다. 하지만 자원의 낭비나 신뢰성이 낮아지기 때문에 사용하기에 적절하지 않은 방법
점유와 대기 부정 각 프로세스는 한 번에 자신에게 필요한 모든 자원을 요구해야 하며, 이 요구가 만족되지 않으면 작업을 진행할 수 없다. 또한 어떤 자원을 갖고 있는 프로세스가 더 이상 요구가 수용되지 않으면 원래 갖고 있던 자원을 일단 반납하고 필요하다면 다시 그 자원이나 다른 자원을 요구해야 한다
비선점 부정 프로세스가 점유하고 있는 자원들을 언제든 빼앗을 수 있도록 한다
순환 대기 부정 한 프로세스가 주어진 유형의 자원을 할당받았으면 그 프로세스는 순서에 따라 나중에 위치하는 유형의 자원말을 요구할 수 있게 한다
- 모든 자원을 선형 순서로 분류

회피(Avoidance)

프로세스가 자원을 요구할 때 시스템이 안전(교착상태가 발생하지 않는 범위 내) 상태를 유지할 수 있는 프로세스의 자원 요구만을 할당해주는 방안

은행원 알고리즘(Banker’s Algorithm)

Dijkstra가 제안한 방식으로 불안전 상태와 안전 상태로 구분한다. 안전 상태에서는 교착상태가 발생하지 않으며, 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자의 수가 일정해야 한다. 또한 모든 요구를 정해진 시간 안에 할당하는 것을 보장해야 한다.

하지만, 은행원 알고리즘은 응답 시간이 보장되어야 하는 대화식 시스템에 적용하기 어렵다

은행원 : 운영체제
대출자 : 프로세스
은행 보유 금액 : 자원 수
현재 대출 금액 : 각 프로세스가 점유하고 잇는 자원 수
대출 한도 금액 : 프로세스가 완료할 때까지 필요한 총 자원 수

발견(Detection)

자원 할당 그래프는 시스템이 주된 이유가 교착상태인가를 발견하는 기법. 교착상태임이 발견되면 해당 프로세스와 자원을 선점하거나 중단 시켜 교착상태 해결

회복(Recovery)

실행 중인 모든 프로세스가 정상적으로 작업을 완료할 수 없기 때문에 발생한 교착상태이므로 어느 정도의 희생은 감수해야 한다. 즉, 실행을 중단하거나 점유 중인 자원을 빼앗을 프로세스를 찾는 일로 가능한 손실이 적은 쪽을 선택해야 한다

선점을 통한 회복
- 보유하고 있는 자원을 빼앗아 교착상태를 해결하고 시스템을 정상으로 회복하는 방법
- 우선순위가 낮은, 진행 상태가 적은, 자원을 적게 사용하고 있는 프로세스의 자원을 선점하여 프로세스를 일시 중단
복귀(Rollback)를 통한 회복
- 교착상태가 발생하기 이전 상태로 복귀하여 다시 실행하는 방법
- 현재 실행 중인 전체 프로세스를 대상으로 할 수 있지만 더욱 효과적인 방법은 교착상태를 해결할 만큼의 프로세스들만을 선택하여 처음부터 다시 실행하는 것
- 현재까지 실행되고 있는 프로세스와 중단된 프로세스의 정보를 재구성해야하는 어려움이 존재
제거(Kill)를 통한 회복
- 우선순위가 낮은, 진행 상태가 적은, 자원을 적게 사용하고 있는 프로세스를 선택하여 제거
- 기아 상태나 문제가 있는 프로세스 제거
- 정상 수행이 불가능한 모든 프로세스를 제거하고 다시 시작
사용자의 조치 경로(Routing) 선택
- Window OS : Ctrl + Alt + Delete를 입력하면 현재 작동 중인 프로세스 리스트가 나오게 되는데 이 때 문제가 있는 프로세스를 선택하여 제거
- Unix OS : ps 명령을 입력하면 현재 프로세스들의 리스트가 출력되는데 이 때 문제가 있는 프로세스들을 kill/killall 명령으로 제거

Twitter Facebook LinkedIn

SG Yoo.