CPU 스케줄러 전략 (FCFS, SJF, HRN, SRT, Round Robin, Multi-Level Queue)

CPU 스케줄링

• 메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 것이다.
• Ready Queue에 있는 프로세스들 중에 누구에게 CPU를 할당해 줄 것인지 정한다.

 

왜 필요할까?

• CPU는 한번에 하나의 프로세스만 실행시킬 수 있다.
  • 특정 프로세스가 I/O 요청에 의해 대기해야할 경우 CPU는 그저 놀고 있게 된다.
  • 다중 프로그래밍에서는 이러한 시간을 생산적으로 활용하고자 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다. (Context Switching)
• CPU 이용률 증가 : 프로세스 실행 과정에서 주 기억장치를 액세스한다든지, 입출력 명령실행 등의 원인에 의해 발생할 수 있는 CPU의 낭비 시간을 줄이고, CPU가 프로세스를 실행하는데 사용되는 시간 비율을 증가시킵니다.

.

---

비선점 스케줄링

• 어떤 프로세스가 CPU를 점유하고 있다면 해당 프로세스의 작업이 완료될 때까지 다른 프로세스가 강제로 CPU를 빼앗아 사용할 수 없는 스케줄링 기법이다.
• 종류 : FCFS, SJF, 우선순위, HRN, 기한부 알고리즘

 

선점 스케줄링

• 하나의 프로세스가 CPU를 점유하고 있을 때, 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다. 
• 종류 : Round Robin, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 알고리즘

 

---

비선점 스케줄링

1) FCFS (First Come First Served)

• 프로세스가 Ready Queue에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다.
• 모든 프로세스의 우선순위가 동일하고, 프로세스의 CPU 처리 시간을 따로 고려하지 않기 때문에 매우 단순하고 공평한 방법이다.
• 작업 완료 시간을 예측하기 용이하다.
• CPU 처리 시간이 길지만 덜 중요한 작업이, CPU 처리 시간이 짧고 더 중요한 작업을 기다리게 할 수도 있다.
  → 이를 콘보이 효과라고 한다.

• 콘보이 효과 : CPU를 매우 오래 사용하는 프로세스가 도착하게 되면, 다른 프로세스가 CPU를 사용하는 데 기다리는 대기 시간이 매우 커지는 현상
  
  

2) SJF (Shortest Job First)

• Ready Queue에 있는 프로세스 중 CPU 처리 시간이 짧은 순서대로 CPU를 할당하는 비선점형 방식이다.
• 늦게 도착하더라도 CPU 처리 시간이 앞에 대기중인 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있다. → 콘보이 효과 완화
• 모든 방식을 통틀어 평균 대기 시간을 가장 짧게 만드는 방식으로 알려져 있다.
• CPU 처리 시간이 긴 프로세스의 경우 처리 시간이 짧은 프로세스가 계속해서 들어오면 Ready Queue에서 무한정 CPU를 기다려야 하는 상황이 발생할 수 있다.
  → 이를 기아(starvation) 현상이라고 한다.

• 기아(starvation) 현상 : 자신보다 우선순위가 높은 프로세스 때문에 오랫동안 CPU 할당을 받지 못하고 무한정 기다리는 현상
  
  
  

3) HRN(Highest Response ratio Next)

• SJF 스케줄링 방식에서 발생할 수 있는 기아 상태를 해결하기 위해 고안된 방식이다.
• 우선순위를 단순히 CPU 처리 시간으로 결정하지 않고, Ready Queue에서 대기한 시간까지 고려하여 결정한다. --> aging 기법

• aging(노화) 기법 : 기아현상을 해결하기 위한 기법으로 오랫동안 기다린 프로세스에게 기다린 시간에 비례하여 우선순위를 높여주는 기법
  
  

HRN 스케줄링 방식이 선점일 경우엔 우선순위가 높은 다른 프로세스들이 너무 자주 생기기 때문에 Context Switching이 너무 자주 발생한다. 이에 따라 스케줄러의 일이 너무 늘어나기 때문에 HRN 스케줄링 방식은 비선점 방식으로 이루어진다.

지금까지 설명만 읽어봤다면 FCFS 스케줄링 방식을 사용할 하등의 이유가 없는 것처럼 보인다. HRN 스케줄링 방식이 다른 비선점 스케줄링 방식에 비해 이상적으로 훨씬 우월해 보이기 때문이다. 그러나 실제로 SJF, HRN 등의 방식을 사용하기 어려운 이유가 있는데, 현실적인 상황에서는 프로세스마다 CPU 처리 시간이 얼마나 걸릴지 알 수 있는 방법이 없기 때문이다. 이는 SRT 스케줄링 방식에서도 동일하게 적용되는 부분이다.

 

4) 우선순위 (Priority)

• 대기중인 프로세스들에게 우선순위를 부여해 우선순위가 높은 프로세스에게 CPU를 먼저 할당한다.
  • 우선순위가 같은 프로세스들은 보통 FCFS 순서로 스케줄 된다.
• 우선순위가 낮은 프로세스는 오랫동안 CPU 할당을 받지 못하고 무한정 기다릴 수 있다. (기아 현상)
• 대기시간이 늘어날수록 프로세스들의 우선순위를 증가시킨다. → aging 기법으로 기아 상태 방지
• 선점형이거나 또는 비선점형이 될 수 있다.

 

 

---

선점 스케줄링

 

1) SRT(Shortest Remaining Time)

• SJF 방식을 선점 스케줄링 방식으로 변경한 기법이다.
• CPU를 점유중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 Ready Queue에 들어올 경우 새로 들어온 프로세스가 CPU를 점유할 수 있다.
• 어떤 알고리즘보다 평균 대기 시간이 가장 짧은 알고리즘이지만, 기본적으로 선점형 방식이기 때문에 잦은 Context Switching이 일어나고 그에 따른 오버헤드가 커진다.
• starvation 현상이 더 심각하게 발생할 수 있다.
• CPU 처리 시간은 예측하기가 힘들기 때문에 실제로 사용되기 어렵다.

 

2) 우선순위 (Priority)

SJF와 SRT의 관계와 마찬가지로 비선점 우선순위 스케줄링, 선점 우선순위 스케줄링이 있다.

 

3) 라운드 로빈(Round Robin)

• FCFS 스케줄링 방식에 선점 스케줄링 방식과 Time Quantum 개념을 추가한 방식이다.
• 프로세스에게 각각 동일한 CPU 할당 시간(타임 슬라이스, quantum)을 부여해서 그 시간 동안만 CPU를 이용하게 한다.
• 어떤 프로세스가 CPU를 사용한 시간이 Time Quantum만큼 지나면 이 프로세스로부터 CPU 자원을 회수하고, 이 프로세스를 Ready Queue의 가장 뒤로 보내는 것이다.
• 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다는 큰 장점이 있다.
  자연스럽게 콘보이 효과 역시 줄어든다.
• 적당한 Time Quantum을 설정하는 것이 중요하다.
  • 크면 CPU 처리 시간이 긴 프로세스가 CPU를 오래 점유하며 정작 다른 프로세스들은 이 프로세스의 작업이 끝날 때까지 기다려야 하기 때문에 결국 FCFS 스케줄링 방식에서 발생하던 콘보이 효과가 또 발생한다.
  • 작으면 잦은 Context Switching으로 오버헤드가 상당히 커진다.
  • 보통 10-100ms로 설정한다.

 

4) 다단계 큐(Multi-Level Queue)

• 프로세스를 어떤 프로세스냐에 따라 여러 종류의 그룹으로 나누고, 그룹마다 Queue를 두는 방식이다. 한 마디로 Ready Queue를 여러 개로 나누어 사용하는 방식이다.
• 각각의 Queue마다 서로 다른 스케줄링 방식을 적용할 수도 있다.
• 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되어야 다음 우선순위 큐가 실행될 수 있다.
• 한 번 우선순위가 매겨져 준비 큐에 들어가면 이 우선순위는 바뀌지 않는다. 즉, 큐들 사이를 이동할 수 없다.
• starvation 현상과 공평성 문제가 있다.

이 방식에 대해 이해하려면 먼저 Foreground Queue와 Background Queue에 대해 알고가야 한다.

운영체제는 프로세스를 분류할 때 사용자와 직접 상호작용하는 프로세스와 백그라운드에서 돌아가는 프로세스의 중요도를 다르게 분류한다. 사용자와 직접 상호작용하는 프로세스는 빠르게 처리되어야 하고, 백그라운드에서 일괄 처리되는 프로세스의 경우 덜 빠르게 처리되어도 괜찮다고 분류하는 것이다.
사람들은 대부분 지금 내가 보고 있는 프로세스와의 상호작용이 빠르게 처리되기를 바라지 일단 켜두고 오래 방치한 프로세스와 상호작용하느라 내가 보고 있는 프로세스에 렉이 걸리는 상황을 바라지 않는다.

따라서 사용자와 직접 상호작용하는 프로세스가 모인 Foreground Queue에는 응답 시간을 줄이기 위해 라운드로빈 스케줄링 방식을 적용하고, 백그라운드에서 돌아가는 프로세스가 모인 Background Queue에는 응답 시간이 큰 의미가 없기 때문에 FCFS 스케줄링 방식을 적용하는 등 각 Queue마다 운영체제가 가장 적정하다고 판단하는 스케줄링 방식을 사용하게 된다.

위 사진을 예로 들면,
대화형 프로세스를 담기 위한 Foreground Queue에는 라운드로빈 스케줄링 방식을 적용하고, 프로세스 일괄 처리가 필요한 Background Queue에는 일괄 처리에 적합하다고 했던 비선점 방식 중 하나를 적용하면 될 것이다.

다만 다단계 큐 스케줄링 방식은 여러개의 Queue를 사용하기 때문에 고려해야 할 점이 하나 더 생긴다.
바로 어떤 Queue에 얼마나 CPU를 오래 할당할 지 결정하는 스케줄링이 필요하게 된다. 이 스케줄링은 크게 두 가지 정도를 떠올릴 수 있다.

 

Queue에 얼마나 CPU를 오래 할당할 지 결정하는 스케줄링

• 고정 우선순위 (Fixed Priority)
  Queue마다 우선순위를 두는 방식이다. 우선순위가 높은 Queue에 처리해야 할 프로세스가 남아있다면, 무조건 그 Queue에 남아있는 프로세스를 처리한 뒤에 다음 우선순위의 Queue를 서비스한다. 이 방식은 사용자가 직접 원하는 프로세스에 CPU 자원을 우선 할당하기 때문에 좋아보이지만 SJF 스케줄링 방식처럼 결국 우선순위가 낮은 Queue에 있는 프로세스는 무한정 기다려야 하는 상황 즉, 기아 현상이 발생할 수 있다.

 

• 타임 슬라이스 (Time Slice)
  고정 우선순위 스케줄링 방식에서 기아 상태가 발생할 수 있기 때문에 이를 해결하고자 생긴 스케줄링 방식이다. 운영체제가 Time Slice를 두고, 이 시간 비율에 따라 각각의 Queue를 서비스하게 된다. Queue마다 프로세스를 CPU에 할당할 수 있는 시간 비율이 다르다. 예를 들어, CPU 자원의 75%는 Foreground Queue, 25%는 Background Queue를 서비스하는 데 할당할 수 있다.

 

5) 다단계 피드백 큐(Multi-Level Feedback Queue)

• 다단계 피드백 큐 스케줄링 방식은 다단계 큐 스케줄링 방식에 aging 기법을 적용한 방식이다.
• 우선순위가 변동되기 때문에 큐 사이의 이동이 가능하다.
  • 우선순위 👍 : 우선순위가 낮은 큐에서 너무 오래 기다린 프로세스의 우선순위를 점점 올려서 우선순위가 높은 큐로 옮겨준다. -> starvation을 예방
  • 우선순위 👎 : 한 번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아져 더 낮은 큐로 이동하게 된다.
• 우선순위가 높은 큐보다 낮은 큐에 타임 슬라이스 크기를 크게 준다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용하게 해주기 위함이다.
• I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다.(통상적으로 짧은 CPU 버스트가 특징이다.)