[운영체제 기초]8. CPU 스케쥴링

CPU 스케쥴링

학습목표

• CPU 스케쥴링 방법들과 각각의 차이점들에 대해 설명할 수 있다.
  
  
  

1. CPU스케쥴링이란 뭘까?

Ready Queue의 프로세스를 어떤 순서로 처리할 것인지 계획을 세우는 것이다.

2. CPU스케쥴링의 방식

• 선점(Preemptive)
  처리중인 프로세스가 있어도 다른 프로세스를 처리할 수 있다.
• 비선점(Non-preemptive)
  처리중인 프로세스가 끝나기 전에는 다른 프로세스를 처리하지 않는다.
  
  
  

3. CPU스케쥴링의 기준

CPU스케쥴링의 기준으로는 다음과 같은 항목들이 있다.

• CPU Utilization(CPU 이용률)
• Throughput(처리율)
• Turnaround time(반환시간)
• Waiting time(대기시간)
• Response time(응답시간)
  
  
  

4. CPU스케쥴링 알고리즘의 종류

• First-Come, First-Served(FCFS)
  Queue에 들어오는 순서대로 프로세스를 처리하는 방식이다.
  처리방법이 가장 단순하고 공평한 방식이지만 최적화된 결과를 내지 못할 때도 있다는 단점이 있다.

• Shortest-Job-First(SJF)
  실행시간이 가장 짧은 작업을 먼저 처리하는 방식이며, 평균 대기시간을 가장 적게 만들 수 있는 방법이다.
  수학적으로 증명된 최적화 방법이기도 하지만 비현실적이기 때문에 사용되지 않는다.
  그 이유는 실행시간이 '가장 짧은' 프로세스를 한번에 찾는것이 불가능하기 때문이다.
  그래서 과거의 처리기록을 통해 프로세스의 실행시간을 어느정도 '예측'해서 처리할 수는 있다.
  그러나 이 방법도 과거의 처리기록을 탐색하고 저장해야한다는 점에서 오버헤드가 발생하기 때문에 비현실적이다.
  Preemptive SJF - 최소잔여시간 우선
  Non-preemptive SJF - 최소잔여시간 우선

• Priority
  우선순위대로 처리하는 방법이며 우선순위는 일반적으로 정수값으로 표현하고 작을수록 우선순위가 높다.
  우선순위를 정하는 방법에는 크게 내부적인 것과 외부적인 것들로 나뉘어진다.
  내부요소 : time limit(시간제한), memory requirement(메모리 사용량), i/o to CPU burst(I/O, CPU사용량) 등
  외부요소 : amount of funds being paid(금전적 요인), political factors(정치적 요인)
  우선순위 방법의 문제점으로는 기아(Starvation)이 있다.
  기아는 프로세스가 영원히 CPU의 서비스를 받을 수 없게 되는 상황을 말한다.
  컴퓨터는 Ready Queue에 계속해서 프로세스가 들어오는데, 만약 A라는 프로세스의 우선순위가 3이고 새로 들어오는 프로세스들의 우선순위가 A보다 높다고 가정한다면 A는 영원히 CPU의 서비스를 받을수 없게 된다.
  이 문제의 해결 방법으로는 에이징(Aging)이 있는데, 프로세스가 Ready Queue에서 오래 머물수록 우선순위를 점진적으로 높여서 언젠가는 CPU서비스를 받을 수 있도록하는 방식이다.

• Round-Robin(RR)
  시분할 시스템에서 사용되는 방법으로 일정한 시간, 즉 시간양자(Time Quantum)마다 프로세스를 전환(Context switching)하며 처리하는 방식이다.
  Round-Robin 방식은 시간양자 값이 얼마인가에 따라 프로세스들의 평균 대기시간에 차이가 발생하게 된다.
  일반적으로 시간양자값의 범위는 10~100msec으로 정하는 편이다.
  시간양자값이 0에 수렴하는 매우 작은 값인 경우에는 빈번한 프로세스 전환으로 인해 오버헤드가 발생하고,
  반대로 무한대에 수렴하는 매우 큰 값이라면 FCFS와 다를바가 없어진다.
  따라서 성능은 시간양자값에 매우 의존적이며 적절한 값을 찾아 최적화를 하는것이 중요하다.
  프로세스의 처리여부에 관계없이 항상 전환하므로 Non-preemptive 방식은 존재하지 않는다.

• Multilevel Queue
  프로세스의 속성별로 그룹을 나누어 여러개의 Queue를 두는 방법이다.
  프로세스는 각각의 Queue로 진입하게되며, Queue그룹별로 독립된 스케쥴링을 방식을 적용할 수 있다.

• Multilevel Feedback Queue
  복수개의 Queue를 가진다는 점에서 Multilevel Queue와 유사하지만, 하나의 프로세스가 여러 Queue를 거칠 수 있다.
  프로세스는 하나의 입구로 진입하며 너무 많은 CPU time을 사용하거나, 기아 상태에 빠질 우려가 있는 경우 Queue를 전환해가면서 프로세스를 처리한다.
  
  
  

실제로 사용되는 Windows나 Linux같은 운영체제는 스케줄링 방식중 어느 하나만을 사용하는것이 아니며, 작업의 유형이나 성질에 맞게 여러가지 스케쥴링 방법들을 혼용해서 사용한다.

Reference

• 양희재 교수님의 운영체제 강의
  https://youtu.be/_eo9cX1GpVU
  https://youtu.be/RAsFncT7QL0
  https://youtu.be/qBZXUD6Y4QE