[OS] CPU Scheduling

 

핀토스 프로젝트를 하면서 크게 두 가지 스케줄러를 구현해보았다. 물론 기본적으로 구현되어있는 busy waiting 또한 스케줄링 방식 중 하나이지만 내가 구현한 것이 아니니까.. 이번 포스팅에서는 CPU 스케줄러에 대해서 조금 더 자세히 알아보고자 한다. 

 

 

CPU Scheduling Criteria

먼저 스케줄러의 성능 척도에 대해서 알아보고 가자. 크게 다섯 가지가 있는데 다음과 같다. 

 

1. CPU Utilization(프로세서 이용률) 

CPU를 사용한 시간의 비율을 나타낸다. CPU가 오랜 시간동안 바쁜 상태로 있을 때 높아진다. 대기 시간이 긴 I/O 작업이 많을수록 나빠지며, 단순 연산 작업만 많은 경우 높아진다. 

 

2. Throughput(처리율)

시간당 처리한 작업의 비율을 의미한다. malloc lab에서도 보였던 평가 지표이다. 

 

3. Turnaround Time(반환 시간)

CPU burst time 이라고도 부른다. 특정 프로세스 또는 스레드가 CPU에 들어갔을때부터 CPU에서 나올때까지 소요한 시간이다. 

 

4. Waiting Time(대기 시간)

프로세스 또는 스레드가 대기열(ready list)에 들어와 CPU를 할당받기까지 걸린 시간을 의미한다. 

 

5. Response Time(반응 시간)

프로세스 또는 스레드가 대기열에서 처음으로 CPU를 얻는데까지 걸린 시간을 의미한다. 얼핏 보기에 waiting time과 비슷해보일 수 있지만, response time은 처음으로 CPU를 할당받기까지 걸린 시간을 의미하고 waiting time은 프로세스 또는 스레드가 CPU를 사용하다가 ready list로 쫓겨난 상황에서 다시 CPU를 할당받기까지 걸린 시간도 포함한다는 점에서 다르다! 

 

이렇게 총 다섯가지의 스케줄러 성능 척도를 살펴보았는데, 1번과 2번은 CPU의 입장에서의 성능 지표이고, 3번부터 5번까지는 유저의 입장에서의 성능 지표인 것을 알 수 있을 것이다. 

 

 

CPU Scheduling Algorithm

이전 포스팅에서도 언급을 했었는데, 스케줄러는 크게 두 가지로 나뉜다. 

👉🏻 선점형 스케줄러(preemptive) : 스케줄러 알고리즘에 의해, 우선시되는 작업이 존재하면 현재 작업을 CPU에서 쫓아낼 수 있다. 

👉🏻 비선점형 스케줄러(non-preemptive) : 작업이 CPU를 할당받으면, 작업을 모두 끝낼때까지 CPU를 빼앗기지 않는다. 

 

일단 우리가 핀토스에서 구현하는 모든 스케줄러는 선점형 스케줄러이다. FCFS 스케줄러도 처음에 구현을 하긴 하는데, 기본적으로는 round robin의 방식을 취하고 있어서 선점형 스케줄러로 구분된다. 우선순위 또한 round robin 방식과 결합되어 선점형 스케줄러이다. 

 

FCFS (First Come First Served)

먼저 ready list에 들어온 작업을 먼저 처리하는 스케줄링 방식이다. 기본적으로는 비선점형 스케줄링이다. 구현하기 쉽다는 장점이 있다. 구현이 쉬운 만큼 단점도 명확한 편인데, 바로 길고 덜 중요한 작업이 CPU를 양보하지 않기 때문에 짧고 중요한 작업이 오래 기다려야 할 수도 있다. 이를 Convey effect 라고 부른다. 

 

SJF (Shortest Job First)

FCFS의 단점을 보완하기 위해 작업 시간이 짧은 작업을 우선으로 처리하는 스케줄링 방식이다. 마찬가지로 비선점형 스케줄링이며, 평균 대기 시간에 있어 좋은 효율을 보이는 알고리즘이다. 하지만 계속해서 처리 시간이 짧은 작업들이 들어오면 뒤에 대기하고 있는 처리 시간이 긴 작업이 CPU를 얻지 못하게 될 수도 있다. 이러한 현상을 Starvation이라고 부른다. 

하지만 치명적인 단점이 있는데, 바로 방금 들어온 작업이 CPU를 얼마나 써야하는 작업인지 알 수 없다는 점이다!

 

 

Priority Scheduling 

제목 그대로 우선순위가 높은 작업을 우선으로 실행시키는 스케줄링 기법이다. 위의 SJF 또한 우선순위 스케줄링의 한 종류이다. 핀토스 프로젝트에서는 우선순위 스케줄러를 선점형으로 구현한다. ready list에 현재 실행중인 작업보다 우선순위가 높은 작업이 들어온다면, 그 즉시 CPU를 우선순위가 높은 작업에게 양보하는 방식이다. 비선점형 방식에서는 우선순위가 높은 작업이 ready list에 들어와도 현재 실행중인 작업이 끝날때까지 기다린다. 

위의 SJF와 마찬가지로 starvation이 생길 가능성이 있다. 이러한 단점을 해결하기 위해 aging 기법을 활용한다. 이 방식은 따로 포스팅 할 예정이다. 

 

 

Round Robin

마지막으로 라운드 로빈 알고리즘이다. 위의 알고리즘들은 선점형으로 구현할 수도, 비선점형으로 구현할 수도 있지만 라운드 로빈은 항상 선점형 스케줄러이다. 특정 시간을 정해두고 모든 작업들이 그 시간만큼 CPU를 사용하면 쫓겨나는 방식이다. 이렇게 모든 작업들이 공평하게 CPU를 사용할 수 있다. 평균 대기 시간은 길어질 수 있지만, 응답 시간이 짧아진다는 장점이 존재한다. 

 

만약 time slice가 너무 커진다면 FCFS와 같아져 비효율적일수 있고,

반대로 time slice가 너무 작아진다면 context switching이 너무 자주 발생하여 오버헤드가 증가할 수 있다.