[OS] Scheduling #2

Scheduling

 

 

이어서 Scheduling을 좀 더 알아보자

 

지난번 정리

SJF는 turnaround time을 최적화하는데 유용한 방법이다.

RR은 빈번한 context switching을 통해서 response time을 줄이는데 최적화된 방법이다.

---

사용하는 프로그램마다 제각기 다른 특성을 가지고 있다.

한 번에 끝내는게 효율이 좋거나, 여러 번 나눠서 끝내는 게 좋거나 등등

 

스케줄러가 프로그램의 특성을 파악하고 그에 따라 더 나은 결정을 할 수 있다면 얼마나 좋을까

 

MLFQ (Multi-Level Feedback Queue)

MLFQ는 여러개의 구별된 queue로 구성되고 각각 다른 우선순위를 가진다.

 

규칙 1 : A의 우선순위 > B의 우선순위 , A를 실행한다.
규칙 2 : A의 우선순위 == B의 우선순위 , A와 B를 RR방식으로 실행한다.

 

작업 별 MLFQ의 특징

• Interactive jobs
  • 짧은 수행시간을 가진 프로그램은 빠른 response time이 중요하다.
  • 따라서 우선순위를 유지한다.
• CPU-intensive jobs
  • 프로그램이 CPU를 오래 사용해야 한다.
  • response time이 중요하지 않다.
  • 우선순위를 감소시킨다.

 

규칙 3 : 작업이 queue에 들어오면 가장 우선순위가 높은 queue에 먼저 배치한다
규칙 4a : 작업이 time slice이내에 완료되지 못하면 우선순위를 감소시킨다.
규칙 4b : 작업이 time slice 이내에 완료되면 우선순위를 유지한다.

 

예를 들어서 알아보자

 

EX 1 ) 하나의 긴 작업 + 3개의 queue를 가진 스케줄러 (time slice : 10ms)

 

작업이 수행되고 10ms이후에도 작업이 남아있기 때문에 우선순위가 하향된다.

두 번째 queue에서도 10ms 간 작업이 수행되지만 작업이 남아있기 때문에 결국 가장 낮은 우선순위 queue까지 하향된다. 이제 Q0에서 계속 실행을 하게 된다,

 

 

EX 2 ) 하나의 긴 작업 + 짧은 작업 + 3개의 queue를 가진 스케줄러 (time slice : 10ms)

 

A는 EX1에서 보았듯이 Q0까지 내려가게 된다.

중간에 B가 queue에 들어오면 새로 들어왔기 때문에 가장 높은 우선순위를 가지게 되어 B를 실행하게 된다.

B작업이 첫 번째 time slice내에 완료되지 않았기 때문에 Q1으로 우선순위가 이동하게 된다.

Q1은 Q0보다 우선순위가 높기 때문에 그대로 B를 실행하고 B작업을 종료하게 된다.

 

EX 3 ) 하나의 긴 작업 + 매우 짧은 I/O interactive작업 3개의 queue를 가진 스케줄러 (time slice : 10ms)

 

 

매우 짧은 작업(B)은 1ms 만에 작업이 종료된다고 가정하자.

그럼 B는 항상 우선순위가 높은 queue에 머무르게 되고, A는 항상 우선순위가 낮은 queue에 머무르게 되면서 RR방식으로 프로그램을 수행하게 된다,

 

 

지금까지 Basic MLFQ를 알아보았다.

 

Basic MLFQ는 여러 문제점을 가지고 있다.

1. Starvation 
   • 짧은 수행 시간을 가진 interactive job이 너무 많아진다면 우선순위가 낮은 queue에 배치된 작업은 작업(오래 걸리는 작업)은 수행할 수 없게 된다.
2. Game the scheduler
   • 만약 time slice의 99%를 I/O 작업이 가져가 버린다면 오래걸리는 job들은 오히려 CPU를 거의 사용하지 못하게 될 수도 있다.
3. 프로그램의 동작 특성 변화
   • 프로그램을 처음 실행할 때는 CPU bound 작업이었는데 실행하고 보니 I/O bound 작업인 경우에 이미 낮아져 버린 우선순위로 인해서 I/O 작업을 원활히 수행할 수 없다.

 

 

12일에는 Basic MLFQ의 문제점을 개선해보자!