[스터디] 4-2. CPU 스케줄링 알고리즘

7가지의 CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링

2. 최단 작업 우선 스케줄링

3. 라운드 로빈 스케줄링

4. 최소 잔여 시간 우선 스케줄링

5. 우선순위 스케줄링

6. 다단계 큐 스케줄링

7. 다단계 피드백 큐 스케줄링

 

 

1. 선입 선처리 스케줄링

= FCFS(First Come First Serverd) 스케줄링

 

단순하게 준비 큐에 먼저 들어온 프로세스부터 처리하는 '비선점' 스케줄링이다. 이게 가장 직관적이고 공정해보이지만 굉장히 큰 부작용을 야기하는 알고리즘이다. 그 부작용은 프로세스들이 CPU를 할당받는 시간이 매우 길어질 수 있다는 것이다. 

 

예를 들어 17ms의 실행 시간을 가진 프로세스 A, 실행 시간 5ms를 가진 프로세스 B가 차례대로 들어왔을 때 프로세스 B는 더 짧은 실행 시간을 가졌음에도 순서에 밀려 17ms를 더 기다렸다가 CPU 자원의 할당을 받을 수 있다. 즉, 앞에 실행시간이 긴 프로세스가 처리되면 처리될 수록 뒤에 대기하는 프로세스들이 대기하는 시간이 점점 더 길어진다. 이를 호위 효과라고 한다. 그럼 이런 호위 효과를 방지하려면 어떻게 해야할까?

 

단순하게 실행 시간이 짧은 프로세스 먼저 CPU에 할당하고 긴 프로세스는 나중에 할당하는 것이다. 이를 '최단 작업 우선 스케줄링'이라고 한다.

 

 

2. 최단 작업 우선 스케줄링

= SJF (Shortest Job First) 스케줄링

 

이 알고리즘은 호위 효과를 방지하기 위한 알고리즘으로 기본적으로 '비선점형' 알고리즘이다. 하지만, 선점형으로도 구현될 수 있다.

 

 

3. 라운드 로빈 스케줄링

= RR (Round Robin) 스케줄링

 

라운드 로빈, 차례대로 무엇을 한다라고 할 때 사용되는 단어이다. 이 알고리즘은 기본적으로 '선점형' 선입 선처리 스케줄링이지만 여기에 시간이라는 개념(=타임 슬라이스)을 도입해서 일정 시간이 지나면 다음 프로세스에게 CPU 할당 기회를 주는 것이다. 즉, 선입 선처리 방식으로 프로세스들을 실행하되 타임 슬라이스의 일정한 시간이 지나면 해당 프로세스를 준비 큐 맨 뒤에 놓고 다음 프로세스를 실행하는 방식이다. 

 

그래서 이 알고리즘은 타임 슬라이스의 크기가 매우 중요하다. 타임 슬라이스의 크기가 극단적으로 커졌다고 가정해보자. 그러면 앞서 언급했던 1번 선입 선처리 스케줄링과 별반 다를게 없어진다. 그래서 호위 효과가 생길 수 있다. 하지만, 그렇다고 너무 작게 설정해버리면 문맥 교환이 그만큼 자주일어나 오버헤드가 발생해 CPU에 부담이 커질 수 있다.

 

 

4. 최소 잔여 시간 우선 스케줄링

= SRT (Shortest Remaining Time) 스케줄링

 

해당 알고리즘은 최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합친 알고리즘이다.

 

즉, 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 작은 프로세스를 선택하는 것이다.

 

 

5. 우선순위 스케줄링

 

프로세스들에게 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 알고리즘이다. 우선순위가 같으면 선입 선처리 스케줄링 방식으로 동작한다. 최단 작업 우선 스케줄링과 최소 잔여 시간 스케줄링은 크게보면 해당 스케줄링에 포함된다고 볼 수 있다. 해당 스케줄링도 큰 부작용을 가지고 있는데 바로 '기아(starvation)' 현상이다.

 

기아 현상?

우선순위가 높은 프로세스만 주구장창 실행되어 우선순위가 낮은 프로세스들이 먼저 준비 큐에 삽입되었음에도 실행되지 못하고 대기하는 현상

 

이 현상을 해결하려면, '에이징(aging)' 기법을 사용할 수 있다.

 

에이징?

준비 큐에 삽입되어 오랫동안 대기한 프로세스들의 우선순위를 점차 높이는 방식

 

 

6. 다단계 큐 스케줄링

= Multilevel Queue 스케줄링

 

우선순위 스케줄링의 발전된 형태로 볼 수 있는 알고리즘이다. 우선순위 별로 여러 개의 준비 큐를 사용한다. 우선순위가 가장 높은 큐부터 처리하고, 비어있다면 다음 우선순위 큐를 처리하는 방식이다. 이렇게 큐를 여러 개 사용하면 프로세스 유형별로 우선순위를 구분하는 것이 쉬워진다.

 

가령, IO-Bound 프로세스와 CPU-Bound 프로세스들을 한 곳에 모을 수 있고 어떤 큐에는 타임 슬라이스를 적게 지정하거나 크게 지정할 수 있다. 심지어는 큐마다 스케줄링을 달리 적용할 수도 있다. 이처럼 유형별로 처리하는 것이 되게 쉬워진다.

 

단점으로는 큐 간의 이동이 불가하기 때문에 우선순위가 낮은 프로세스들은 우선순위가 낮은 큐에만 머물 수밖에 없어서 '기아현상'이 또 발생할 수 있다는 것이다. 이를 해결하기 위한 마지막 스케줄링 방식이 바로 '다단계 피드백 큐 스케줄링'이다.

 

 

7. 다단계 피드백 큐 스케줄링

= Multilevel Feedback Queue 스케줄링

 

다단계 큐 스케줄링의 문제를 해결하기 위한 발전된 스케줄링 방식이다. 앞서 다단계 큐 스케줄링에서는 큐 간의 이동이 불가능해서 우선순위가 낮은 프로세스들이 실행되지 못하고 대기하는 기아 현상이 발생할 수 있다고 했다. 하지만, 다단계 피드백 큐 스케줄링에서는 큐 간의 이동이 가능하다.

 

이 큐 간의 이동이 어떤 방식으로 동작되냐면, 일단 새롭게 준비 상태에 돌입한 프로세스가 있다면 이를 우선순위가 가장 높은 준비 큐에 먼저 넣는다. 그리고 일정 시간동안 CPU에 할당을 하고 시간이 지나고 실행이 끝나지 않았다면 해당 프로세스를 다음 우선순위 준비 큐에 할당한다. 이를 반복하는 스케줄링이다. 그럼 자연스럽게 CPU를 많이 쓰는 프로세스의 우선순위가 상대적으로 낮아지고, IO-Bound 프로세스들의 우선순위가 상대적으로 높아진다.

 

하지만, 이 스케줄링 방식도 결국 우선순위가 점점 낮아지면 나중에 기아 현상이 발생할 수 있다. 그렇기에 에이징 기법을 적용할 수 있다. 일정이상 낮은 우선순위 준비 큐에 대기한 프로세스가 있으면 이 프로세스의 우선순위를 점차 높여 기아 현상을 해결할 수 있다.