CPU 스케줄링 알고리즘

본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다.

CPU 스케줄링 알고리즘

• CPU 스케줄러는 스케줄링 알고리즘에 따라 스레드 단위로 CPU에 할당

• CPU 스케줄링 알고리즘: 어떤 프로그램에게 CPU 소유권을 줄지 결정
• CPU 이용률은 높게, 주어진 시간에 많은 일, ready queue에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것이 목표

비선점형 방식(non-preemptive)

• 스스로 CPU 소유권을 포기하는 방식
• 강제로 프로세스를 중지하지 않음.
• 컨텍스트 스위칭에 인한 부하가 적다.

FCFS(First Come, First Served)

• 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
• 길게 수행되는 프로세스 때문에 convoy effect(ready queue에서 오래 기다리는 현상)발생

SJF(Shortest Job First)

• 실행시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
• starvation(긴 시간을 가진 프로세스가 실행되지 않는 현상) 일어남
• 평균 대기 시간이 가장 짧다.
• 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용

우선순위

• 기존 SJF 스케줄링의 경우 긴 starvation 발생
• aging(오래된 작업일수록 우선순위를 높이는 방법)을 통해 단점을 보완

선점형 방식(preemptive)

• 현대 운영체제가 쓰는 방식
• 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단하고 강제로 다른 프로세스에게 CPU소유권을 할당

라운드 로빈(Round Robbin, RR)

• 우선순위 스케줄링(priority scheduling)의 일종
• 각 프로세스는 동일한 할당시간을 주고 그 시간안에 끝나지 않으면 다시 ready queue의 뒤로 가는 알고리즘
• 할당시간이 너무 길면 FCFS가 됨.
• 너무 짧으면 context switching이 자주 일어나서 오버헤드가 커짐.
• 일반적으로 전체 작업시간은 길어지지만 평균 응답 시간은 짧아지는 특성
• 로드밸런서에서 트래픽 분산알고리즘으로도 쓰임.

SRF(Shortest Remaing First)

• 중간에 더짧은 작업이 들어오면 context switching 발생
• SJF 는 중간에 더짧아도 기존 수행하고 다음 짧은것을 수행

다단계 큐

• 우선순위에 따른 ready queue를 여러개 사용
• 큐마다 RR이나 FCFS등 다른 스케줄링 알고리즘을 적용
• 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징.