[ OS ] 04. CPU Scheduler

[ CPU 스케쥴러 ]

여러 프로세스를 concurrent하게 쓰는게 멀티프로그래밍과 멀티쓰레딩이었고, 그 전제조건으로 바로 CPU Scheduling이 필요하다.

스케줄링 대상은 Ready Queue 에 있는 프로세스들이다.

(이 Ready Queue는 LinkedList or Binary Tree or FIFO Queue or PriorityQueue를 사용하여 만들어진다.)

들어가기 전에 먼저 용어 정리 부터 하겠다.

선점(preemptive) : 우선순위가 높은 작업이 오거나, 해당 작업이 더 우선되어야 한다고 판단되면 해당 작업에게서 CPU를 빼앗을 수 있다.
비선점(non-preemptive) : 일단 CPU를 할당받으면 해당 프로세스가 끝날때까지 CPU를 빼앗기지 않는다.

스케쥴링 알고리즘에 대한 성능 척도

• 프로세서 이용율 (CPU Utilization)

  • 시간당 CPU를 사용한 시간의 비율
  • 프로세서를 실행상태로 항상 유지하여 유휴상태가 되지 않도록 한다. 가능하면 입출력(I/O) 중심의 작업보다 프로세서 중심의 작업을 실행해야 한다.

• 처리율 (Throughput)

  • 시간당 처리한 작업의 비율
  • 단위 시간당 완료되는 작업수가 많도록 짧은 작업을 우선 처리하거나 인터럽트 없이 작업을 실행한다.

• 반환시간 또는 소요시간 (Turnaround Time)

  • CPU burst time(쓰고 나갈때까지의 시간, 누적되지 않음)
  • 작업이 시스템에 맡겨져서 메인 메모리에 들어가기까지의 시간, 준비 큐에 있는 시간, 실행시간, 입출력시간 등 작업 제출 후 완료되는 순간까지의 소요시간이 최소화되도록 일괄 처리 작업을 우선 처리한다.

• 대기시간 (Waiting Time)

  • 대기열에 들어와 CPU를 할당받기까지 기다린 시간
  • 작업의 실행시간이나 입출력시간에는 실제적인 영향을 미치지 못하므로 준비 큐애서 기다리는 시간이 최소화되도록 사용자 수를 제한한다.

• 반응시간 또는 응답시간 (Response Time)

  • 대기열에서 처음으로 CPU를 얻을때까지 걸린시간
  • 반응시간은 의뢰한 시간에서부터 반응이 시작되는 시간까지의 간격으로 대화형 시스템에서 중요한 사항이다. 따라서 대화식 작업을 우선 처리하고 일괄 처리 작업은 대화식 작업의 요구가 없을때까지 처리한다.

FCFS

First Come First Served

특징

• 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
• 비선점형(Non-Preemptive) 스케줄링
  일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.

문제점

• convoy effect(똥차 효과)
  소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.

SJF

Shortest - Job - First

특징

• 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 우선 할당한다
• 일종의 우선순위 기법이라고 볼 수 있고, 비선점형(SJF)과 선점형(SRTF) 방식 모두 있다.
• 최소 평균 대기 시간을 보장한다.
• 이론적으로 다른 알고리즘과 비교하기 위한 최적의 알고리즘일뿐, 직접 구현해서 쓰진 않는다.

문제점

• starvation
  효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.

SRTF

Shortest Remaining Time First

특징

• SJF의 선점형 스케쥴링 방식
• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형 (Preemptive) 스케줄링
  현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.

문제점

• starvation
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 정확히 예측하기 어렵다.

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
• 선점형 스케줄링(Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
• 비선점형 스케줄링(Non-Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.

문제점

• starvation
• 무기한 봉쇄(Indefinite blocking)
  실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태

해결책

• aging
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

Round Robin

특징

• 현대적인 CPU 스케줄링으로 시분할 시스템을 위해 설계되었다.
• 선점형 스케줄링(Preemptive) 방식
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다. -> 이 time slice를 어떻게 하느냐에 따라 성능 차이가 난다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
• 어떠한 프로세스도 q time unit 이상 기다리지 않는다. -> 공정한 알고리즘!
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
• RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.

장점

• Response time이 빨라진다.
  n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.

주의할 점

설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead(dispatcher latency) 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.

MLQ

Multi Level Queue

특징

• 선점형 스케쥴링
• 작업들을 여러 종류의 그룹으로 분할 (ex. 데이터, 사운드, 화면, 전화, 카톡, ...)
• 여러 개의 레디큐를 이용해 상위 단계 작업에 의해 하위 단계 작업이 선점된다.
• Ready Queue를 여러 종류로 분할한다.(작업 분류별 묶음) -> 각각의 priority를 따로 배정한다.
• 다른 큐로 작업 이동이 불가
• 각각의 Ready Queue는 자신만의 독자적인 스케쥴링을 가진다.
• 상위 우선순위의 큐가 Empty이면 하위 우선순의 큐의 프로세스가 수행된다.

MLFQ

Multi Level FeedBack Queue

특징

• 선점형 스케쥴링
• 입출력 위주와 CPU위주인 프로세스의 특성에 따라 큐 마다 서로 다른 CPU Time Slice(Time Quantum)을 부여한다.
• 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동한다.
• 제일 마지막 단계에서는 RR/FCFS로 처리한다.
• 우선순위가 높은 프로세스에게는 불이익을, 우선순위가 낮은 프로세스에게는 이익을 제공한다.
• 기본적으로 가장 우선순위가 낮은 큐를 제외 하고는 모두 RR 스케쥴링을 사용한다.
• 하위 단계일 수록 할당 시간은 증가(공평성 부여)
• 기아(stravation) 상태를 예방하기 위해 Aging처리를 이용한다.
• 현대 OS에서 RR방식과 함께 가장 많이 사용되는 스케쥴링 기법이다.

마무리

실제로는 쓰레드 스케쥴링을 하는데 쓰레드 스케쥴링은 어려워 프로세스에서 배운 것(CPU Scheduling)이다.

유저쓰레드는 일반적으로 Thread 라이브러리로 관리하게 되고 OS는 many to many model로 유저 쓰레드에게 이를 서비스한다.

++

soft RTOS : 아주 조금의 오차정도는 허용된다.

hard RTOS : 어떤 오차도 허용되면 안되고, 반드시 허용된 시간안에 task가 수행되어야 한다. (우선순위가 역전되면 안되!)