[OS/OSTEP] 07.CPU-sched : CPU 스케줄링 정책(scheduling policy) #4

07.CPU-sched

# 시작하며

앞선 06포스팅 에서는 어떻게 cpu가 가상화하여 다중작업을 수행하는지에 대해서 알아 봤다면, 어떻게 그 다음 프로세스를 결정하는지에 데해서 알아보도록 한다. 즉 스케줄링 정책(scheduling policy)에 대해서 알아본다. 처음에는 초창기에 방식부터 점점 많은 요소들을 고려해가며 현대의 접근방법에 대해서 알아본다. 그렇기 때문에 처음에는 여러 가정을 통해서 조금 특별한 요소들을 제한하고 그 요소들을 하나씩 없애는 방식으로 설명한다.

 

# 워크로드에 대한 가정 

일련의 프로세스들이 실행하는 상황을 워크로드(Workload)라고 한다. 일단 지금은 많은 특별한 케이스들을 배제하는 가정을 세워야 했다.

하나씩 지워나가며 이 포스팅이 끝날때는 마지막 5의 가정 한개만 남게 된다.

 

# 스케줄링 결과를 평가하는 두가지 요소

## 반환 시간(turnaround time)

 작업이 끝낸 시각에서 도착시간을 뺀 시간이다. 

## 응답 시간(response time)

작업이 도착하고나서부터 그 작업이 처음 시작한 시간, 즉 반응시간이다.

 

# 선입선출(First In First Out, FIFO)

 내가 편의점에서 알바하면서 선입선출이라는 단어를 처음 접했었다. 가장 먼저 들어간게 가장먼저 나오는, 가장 먼저 진열한 음식은 유통기한이 있기 때문에 항상 맨앞에 놔야했다. 이러한 FIFO방식은 CS에서 정말 많이 사용되는 방식이기도 했고 간단한 접근방식이면서 구현도 쉽다.

## 5가지 가정

 우리는 5가지의 가정을 뒀기 때문에 모두 0이라는 같은시간에 도착했다. 그렇기 때문에 A, B, C의 도착시간은 모두 0, 끝나는 시각은 각각 10, 20, 30 이다. 그렇다면 (10+20+30) / 3 을 계산하면 평균 반환시간은 20이다. 

 

## 4가지 가정

가정 중 하나를 제거한다. 실행시간이 모두 다르다는 가정이다.

 이제 선입선출에 가장 큰 문제가 보인다. 가장 먼저 실행되는 프로세스가 매우 길고 남은 프로세스가 매우 짧다면 즉 B,C를 먼저 실행하면 10과 20 시간에 끝났지만, 긴 A를 쓸때없이 기다려야 한다. convoy현상이라고도 한다.

평균반환시간은 (100+110+120) / 3 = 110이 됐다.

 

# 최단 우선 작업( Shortest Job First, SJF )

 이름 그대로 가장 짧은 작업을 가장 먼저 실행시켜버림으로써 쓸데 없는 convoy 현상을 줄이는 것이다. 

FIFO에서 발생했던 골치덩어리 A를 뒤로 미뤄버렸다. [(10 - 0 ) + ( 20 - 0 ) + (120 - 0)] / 3 = 50 으로 좋은 결과를 얻었다.

그러나 이건 가정이 존재했기 때문에 있을 수 있는 이상적인 작업이다. 가정을 하나 지우자

## 3가지 가정

 이제 모든 작업(프로세스)가 도착하는 시간은 제각각이다. 모두 0에 들어오지 않는다는 것이다. 결국 SJF도 똑같은 convoy문제를 지니게 된다. 골치덩어리 A가 맨 처음 도착하는 경우가 그렇다.

평균 반환시간 ( ( 100 - 0 ) + (110 - 10 ) + ( 120 - 10 ) ) /  3 

 

# 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF)

 이 알고리즘을 채택하기 위해서는 가정을 하나 더 완화 해야 한다. "작업은 끝날 때까지 계속 실행된다"를 말이다. 왜냐하면 가장 짧은 작업이 뒤에 있다면 실행중인 작업을 멈추고 가장 적게 남은 프로세스를 위해 끊고 중간에 작업을 바꿔줘야하기 때문이다.

 가장 긴 A가 맨처음 도착했지만 뒤에 있는 프로세스의 잔여시간을 확인하고 현재 실행중인 A보다 작기때문에 문맥교환(context switch)을 행한다. 이렇게 함으로써 SJF에서 발생했던 convoy 현상을 또 제거했다. 

평균 반환시간은 ( ( 120-0) + ( 20 -10 ) + (30 - 10 ) ) / 3 으로 B,C의 반환시간이 대폭 줄었기 때문에 더 빨라졌다.

 

# 응답시간으로 평가하기

 작업의 길이를 미리 알고, 작업이 오직 CPU만 사용할때 즉 I/O와 같은 작업이 없고, 평가기준이 반환 시간이라면 STCF는 매우 훌륭한 정책이다. 그러나 현대 컴퓨터는 멀티태스킹을 지원하고 작업이 끝나는 시간도 물론 중요하지만 반응하는 시간도 중요하다. 내가 프로그램을 실행시키기 위해 눌렀는데, 이게 아주 Long Job이라서 STCF에 의해 스케줄링이 뒤로 되버리면.. 하루종일 커서가 뺑뺑 도는것만 구경해야한다. 응답시간을 구하는 방법은 위에서도 소개 했듯이, 실행시간 - 도착시간이다.

 

# 라운드 로빈( Round-Robin, RR)

 응답시간을 줄이기 위해서 도입한 스케줄링 알고리즘이다. 작업이 끝날때 까지 기다리지 않고, 일정시간 수행 후 실행 큐에 있는 다음 작업으로 전환한다. 당연히 반응속도를 빠르게 할 수 있다. 아래 SJF와 RR을 반응속도를 생각해보자

 

 저렇게 변화되는 일정한 주기를 타임 슬라이스(time slice)라고 한다. 당연히 타이머 인터럽트 주기의 배수여야 한다. SJF의 평균 응답 속도는 ( 0 + 5 + 10 ) / 3 = 5 인 반면 RR은 ( 0 + 1 + 2 ) / 3 = 1로 매우 빠르다.

 당연히 타임 슬라이스의 비율을 최대한으로 줄일 수록 반응시간은 빨라진다. 그러나 이러한 경우 잦은 문맥교환이 발생하기 때문에 전체 성능에 영향을 미치게 된다. 그렇기 때문에 최적의 상태로 동작하는 타임 슬라이스를 골라야 한다.

 그러나  응답 시간이 아닌 반환시간이 평가 목적이라면 RR은 최악이다. 둘의 개념은 당연히 반비례 관계이다. 응답시간이 증가하면서 반환시간마저 증가 할 수는 없다.

 

## 2가지 가정, 입출력 연산의 고려 제거

 이제 프로세스들은 I/O작업도 일어난다. 점점 현실적인 프로세스가 되어 가고 있다. 입출력요청이 일어나면 대기(Blocked)상태가 되고 CPU를 낭비하지 않기 위해서는 이 시간에 다른 프로세스를 실행시킬 수 있다. 그렇다면 어떤 CPU가 선택 되어야 하는 것인가에 대한 의사결정도 이뤄져야 한다. 또한 입출력완료가 된다면 어떤 프로세스가 실행이 되어야 할지도 결정해야한다. 완료를 알려온 프로세서일까? Blocked동안 실행하고 있던 프로세스를 계속 실행해야 할까?

 만일 Blocked상태일때 아무것도 실행하지 않고 기다린다면 위와 같은 실행을 하겠지만, 

 머리를 잘 굴려 CPU가 노는시간을 활용한다면 효율적이게 스케줄링을 할 수 있다.

 

# 만병 통치약은 없다! ( No More Oracle )

 교재는 항상 이렇게 현실적으로 이야기 해준다. 아직 남은 가정 한가지가 있었는데, 지금까지 세운 알고리즘들 모두는 요청받은 작업에 대한 길이를 알 수 있었다. 하지만 어떤 프로세스도 그것이 언제까지 실행될지 모른다. 다음장에서는 이 마지막 남은 가정을 없애버리면서 정말 현실적인 상황에서 어떻게 스케줄링을 해야하는지를 알려준다. 

 멀티 레벨 피드백 큐(multi-level feedback queue)을 정리할 것이다.

 

# 끝내며

 복습하니까 안보이던것들도 보인다! 교재내용을 중점적으로 썻지만 내 생각들도 부분적으로 들어가 있어서 오개념이 있을 수 도 있다!