(CS) 데드락, 기아 상태, 스케줄링

데드락

1. 데드락의 개념

데드락(교착상태, deadlock)은 두 개 이상의 프로세스나 스레드가 서로 상대방이 필요한 자원을 점유한 채로 다른 자원을 요청하고 있기 때문에 결과적으로 무한정 기다리고 있는 상태를 의미한다.

위의 그림에서 Process1, Process2가 Resource1, Resource2를 모두 얻어야 실행된다고 가정해 보자.

 

Process1의 상황 : Resource1을 얻은 후 Lock을 하여 다른 Process가 사용할 수 없음 / Resource2를 요청 중

Process2의 상황 : Resource2를 얻은 후 Lock을 하여 다른 Process가 사용할 수 없음 / Resource1을 요청 중

 

이 상황에서 서로 원하는 자원이 상대방에게 할당되어 있기 때문에 두 프로세스는 무한정 대기할 수밖에 없다.

이런 상황을 데드락이라고 한다.

 

2. 데드락의 발생원인

데드락의 발생 원인에는 4가지가 있다.

• 상호 배제(Mutual Exclusion) : 자원은 한 번에 하나의 프로세스나 스레드만 사용할 수 있다.
• 점유 대기(Hold and Wait) : 최소 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당 중인 자원을 추가로 점유하기 위해 대기 중인 프로세스가 존재해야 한다.
• 비선점(No Preemption) : 다른 프로세스에서 사용 중인 자원은 사용이 종료될 때까지 강제로 빼앗을 수 없다.
• 순환 대기(Circular Wait) : 두 개 이상의 프로세스가 서로 다른 자원을 점유한 상태에서, 각각의 프로세스가 다른 프로세스가 점유한 자원을 요청하고, 이를 반복하여 사이클을 형성하는 상황입니다.

위의 4가지 원인 중 하나라도 성립하지 않으면 데드락은 발생하지 않는다.

 

3. 데드락의 해결방법

데드락은 크게 다음과 같은 방법들로 해결할 수 있다.

 

먼저 데드락 예방이다. 2에서 언급한 발생 원인 중 하나를 제거하는 방법을 사용한다.

• 상호 배제 부정 : 여러 프로세스나 스레드가 공유된 자원을 사용한다.
• 점유 대기 부정 : 프로세스 실행 전에 필요한 자원들을 모두 할당한다.
• 비선점 부정 : 자원을 점유 중인 프로세스가 다른 자원을 요구한다면 점유하고 있는 자원을 반납하게 한다.
• 순환 대기 부정 : 자원에 고유 번호를 할당한 후 번호 순서대로 자원을 요구하게 한다.

두 번째로 데드락 회피가 있다. 대표적인 방법으로 은행원 알고리즘을 들 수 있다.

은행원 알고리즘(Banker's Algorithm) : 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한다.

프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피한다. 안정 상태면 요청받은 자원들을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기한다.

 

세 번째는 데드락 탐지와 회복이다.

프로세스가 요청하는 모든 자원을 줌으로써 데드락이 발생하는 것을 허용하되, 데드락이 발생하는지 주기적으로 확인하고 발생하게 되면 원인을 알아내어 해결하는 방법이다.

데드락이 탐지가 되면 다음에 알아볼 데드락 회복을 통해 데드락 발생 전으로 회복함으로써 이를 해결한다.

 

4. 데드락 회복

데드락을 일으킨 프로세스를 종료하거나 할당된 자원들을 해제시켜서 데드락 상태에서 회복할 수 있다.

교착 상태의 프로세스를 모두 중지하거나 또는 교착 상태가 해결될 때까지 프로세스를 하나씩 종료시킨다.

기아 상태

기아 상태(Starvation)는 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속해서 할당받지 못하는 상태를 말한다.

해당 프로세스나 스레드는 실행이 불가능한 상태가 되어 작업을 완료할 수 없게 되고, 결과적으로 전체 시스템의 처리량이 감소하게 된다.

 

위에서 말했던 교착 상태는 여러 프로세스나 스레드가 동일한 자원 점유를 요청할 때 발생했지만, 기아 상태는 여러 프로세스나 스레드가 부족한 자원을 점유하기 위해 경쟁할 때 발생한다.

 

기아 상태는 우선순위에 따른 문제이기 때문에 다음과 같은 방법들로 해결할 수 있다.

• 프로세스 우선순위 수시 변경을 통해 각 프로세스 높은 우선순위를 가지도록 기회를 부여한다.
• 오래 기다린 프로세스의 우선순위를 높인다. (Aging 기법)
• 우선순위가 아닌 요청 순서대로 처리하기 위해 요청 큐를 사용한다.

스케줄링

1. 스케줄링이란?

스케줄링(Scheduling)은 운영체제에서 CPU를 어떤 프로세스에게 할당할지에 대한 방법을 결정하는 것을 의미한다.

CPU는 여러 개의 프로세스에 의해 공유되므로, 스케줄링은 여러 프로세스가 CPU를 사용하는 순서와 시간을 결정하는 중요한 역할을 한다.

 

스케줄링의 목적은 다음과 같다.

• CPU 이용률 최대화 : CPU가 항상 사용되도록 스케줄링을 수행하여, CPU가 일을 하지 않는 시간을 최소화한다.
• 응답시간 최소화 : 사용자가 시스템과 상호작용할 때, 시스템은 즉각적인 응답을 제공해야 한다. 스케줄링은 이러한 사용자의 요청에 대한 응답시간을 최소화하는 것을 목적으로 한다.
• 처리율 최대화 : 시스템이 단위 시간당 처리할 수 있는 프로세스의 개수를 최대화하여, 처리율을 높인다.
• 우선순위 적용 : 우선순위가 높은 프로세스에게 CPU를 우선적으로 할당하여, 중요한 작업이 먼저 처리될 수 있도록 한다.

2. 비선점형 스케줄링 vs 선점형 스케줄링

비선점형 스케줄링

한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식을 말한다.
짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기해야 할 수도 있다. (콘베이 현상)
처리시간 편차가 적은 프로세스 환경에서 유용하다.

ex) FCFS, Prioirty Scheduling, SJF 등

 

선점형 스케줄링

하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식을 말한다.
비교적 응답이 빠르다는 장점이 있지만, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드를 초래한다.
실시간 응답환경, Deadline 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리해야 할 경우 등에 유용하다.

ex) RR, SRT(Shortest Remaining Time first) 등

 

3. 장기, 단기, 중기 스케줄러

 

디스크에서 하나의 프로그램을 가져와 커널(준비 큐)에 등록하면 프로세스가 되는데 이때 장기 스케줄러가 디스크에서 어떤 프로그램을 가져와 커널에 등록할지를 결정한다. 메모리와 디스크 사이의 스케줄링을 담당한다.

 

단기 스케줄러는 CPU 스케줄러라고도 하며 준비 상태의 프로세스 중에서 어떤 프로세스에게 CPU를 할당할지 결정한다. CPU와 메모리 사이의 스케줄링을 담당한다. 위에서 언급한 비선점형 스케줄링과 선점형 스케줄링 방식 중 하나를 선택해야 한다.

 

마지막으로 중기 스케줄러는 너무 많은 프로세스에게 메모리를 할당해 시스템의 성능이 저하되는 경우 이를 해결하기 위해 메모리에 적재된 프로세스의 수를 동적으로 조절하기 위해 추가된 스케줄러이다.

 

4. 스케줄링 알고리즘

• FCFS(First-Come First-Served) : 준비 큐에 도착한 순서대로 프로세스를 처리한다.
• RR(Round-Robin) : 각 프로세스는 CPU를 연속적으로 사용할 수 있는 시간이 제한되며, 사용 시간이 경과하면 CPU를 회수해 준비 큐의 다음 프로세스에게 CPU를 할당한다. 그러고 나서 이 프로세스는 준비 큐의 제일 뒤에 들어가서 다음번 차례가 오기를 기다린다.
• SJF(Shortest-Job-First) : CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 평균 대기시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다.
• LJF(Longest-Job-First) : CPU 버스트가 가장 긴 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 평균 대기 시간과 평균 처리 시간이 매우 높은 알고리즘이다. 
• Priority Scheduling : 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말한다. 기아 상태 문제가 발생할 수 있다.

출처

데드락 (DeadLock, 교착 상태) | 👨🏻‍💻 Tech Interview

[운영체제]교착상태 처리방법(Handling deadlocks) 예방법, 해결방안

OS #24 교착상태와 기아상태

[운영체제] CPU 스케줄링 (선점 & 비선점)

[운영체제]프로세스 스케줄러(장기,단기,중기)/스케줄링 알고리즘

CPU Scheduling in Operating Systems - GeeksforGeeks