[운영체제] 교착 상태, 기억장치 관리 전략

■ 교착 상태 : 예측 못한 다운

 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상. 영어로는 Dead Lock이라고 한다.

 

[교착상태 발생 4가지 필요충분 조건]

명칭	설명
상호 배제 (Mutual Exclusion)	한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야함.
점유와 대기 (Hold & Wait)	최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야한다.
비선점 (Nonpreemption)	프로세스에 할당된 자원은 사용이 끝날 떄 까지 강제로 빼앗을 수 없다. (비양보)
환형대기 (Circular Wait)	공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서도 앞이나 뒤에 있는 프로세스의 자원을 요구해야함.

예시 이미지

=> Process1이 자원2를 점유 하고있는 와중에 자원1을  요청하고있다. 반면에, Process2가 자원1를 점유 하고있는 와중에 자원2를 요청하고있다. 이로 인해 서로 무한히 기다리는 상태를 교착 상태(Dead Lock)이라고 한다.

 

[(번외) 주기억장치 할당기법]

명칭	설명
Swapping (스와핑)	하나의 프로그램 전체를 주기억장치에 할당하여 사용하다 필요에 따라 다른 프로그램과 교체하는 기법.
Overlay (오버레이)	프로그램이 커서 주기억장치에 적재할 수 업을 때, 하나의 프로그램을 여러 개의 영역으로 분할하여 보조기억장치에 수용하고, 처리 흐름에 필요한 영역을 주기억 장치에 수용하는 방식.

■ 기억장치 관리 전략

명칭	설명
반입전략 (Fetch)	보조기억장치의 프로그램이나 데이터를 '언제' 주기억장치로 적재할 것인지를 결정하는 전략. 요구할 때 적재하는 (1)요구반입과 미리 예상하여 적재하는 (2)예상반입이 있다.
배치전략 (Placement)	주기억장치의 어디에 위치시킬 것인지를 결정한다. 크게 세 가지로 나뉜다. * 최초적합 (First Fit) : 첫 번째로 가능한 영역에 배치시키는 방법 * 최적적합 (Best Fit) : 단편화를 가장 작게 남기는 분할 영역에 배치시키는 방법 * 최악적합 (Worst Fit) : 단편화를 가장 많이 남기는 분할 영역에 배치 시키는 방법.
* 단편화 (Fragmentation) 기억 장치의 빈 공간 또는 자료가 여러 개의 조각으로 나뉘는 현상. - 내부 단편화 : 할당 후 남은 공간. 위 예시 이미지에서 영역2(5k), 3(0k), 4(20k)가 된다. - : 외부 단편화 : 할당하지 못한 공간. 위 예시 이미지에서 영역1의 빈공간(9k)가 된다.
교체전략 (Replacement)	페이지 대체 알고리즘. 주기억 장치의 모든 영역이 이미 사용 중인 상태에서 주기억장치에 배치할려고 할 때, 이미 사용되고 있는 영역 중에서 어느 영역을 교체하여 사용할 것인지를 결정하는 전략이다.  * 페이지(Page) : 프로그램을 쪼갠 단위라고 생각하면 된다.

 

■ 교체 알고리즘 종류

종류	설명
FIFO (First In First Out)	(★) 가장 먼저 들여온 페이지를 먼저 교체시키는 방법 (= 주기억장치 내에 가장 오래 있었던 페이지를 교체한다는 뜻이다. )
* 페이지 부재(Page Fault) CPU가 주기억장치에 페이지를 참고할려고 했을 때 존재하지않아서 보조프로그램에서 가져와 주기억장치에 적재후 사용하는 것. 페이지 부재가 몇 회 발생했냐라는 문제를 낼 수 도있다.
LRU (Least Recently Used)	(★) 최근에 가장 오랫동안 사용(참조)하지 않은 페이지를 교체하는 기법 - 각 페이지마다 계수기를 두어 현 시점에서 볼 때 가장 오래 전에 사용된 페이지를 교체
LFU (Least Frequently Used)	사용 빈도가 가장 낮은 페이지[사용 횟수가 가장 적은 페이지]를 교체하는 기법
MRU (Most Recently Used), MFU (Most Frequently Used)	사용 횟수가 가장 많은 페이지를 교체하는 기법
NUR (Not Used Recently)	최근에 사용하지 않은 페이지를 교체하는 기법
OPT (OPTimal replacement)	최적 교체, 앞으로 가장 오랫동안 사용하지 않을 페이지를 예측해서 교체하는 기법. (이론상 존재하지만 실현 가능성이 매우 낮은 기법)

 

■ 용어 정리

용어	설명
파이프라이닝 (Pipelining)	여러 개의 명령을 동시에 병렬 처리 하는 장치. -한 명령어의 수행이 끝나기 전에 다른 명령어의 수행을 시작하는 연산 방법 -고성능 컴퓨터에서만 사용 하였으나 현재 대부분의 컴퓨터에서 수행 속도를 빠르게 하기 위해 사용되어진다.
오퍼랜드	메모리의 주소를 뜻함. 파이프라이닝의 4단계 중 오퍼랜드 인출은 명령어를 가져온 뒤 해독 후 해당 주소에 있는 데이터를 가져온다는 뜻이다.
클럭	CPU가 하나의 작업을 수행할 때 발생하는 신호. 즉, 클럭 하나가 발생한다면 하나의  작업을 수행한다.
(예시) 파이프라이닝
세마포어 (Semaphore)	각 프로세스에 제어 신호를 전달하여 순차적으로 작업을 수행하도록 하는 기법
가비지 수집 (Garbage Collection)	주기억장치 내에 분산되어있는 단편화된 빈 공간을 결합하여 하나의 큰 가용 공간으로 만드는 작업.
임계 영역 (Critical Section)	하나의 프로세스만 자원을 이용할 수 있도록 보호된 영역
코루틴 (Coroutine)	상호(Co)연계 프로그램(Routine) - 루틴과 서브 루틴은 서로 비대칭적인 관계이지만, 코루틴들은 완전히 대칭적인, 즉 서로가 서로를 호출하는 관계이다.