CPU 스케줄링이란 무엇일까

CPU 스케줄링이란

운영체제의 CPU는 프로세스들이 돌아가면서 사용하게 됩니다.

 

때문의 ready 상태의 프로세스들 중 누구에게 CPU를 줄 것인지 결정하는 전략이 필요합니다.

 

CPU 스케줄링은 ready 상태의 프로세스를 CPU 스케줄러가 선택하고, 

 

Dispatcher는 CPU 제어권을 스케줄러에 의해 선택된 프로세스에게 넘기게 됩니다.

 

 

 

CPU 스케줄링은 언제 일어나는가

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우입니다.

 

Nonpreemptive (자진 반납)

1. I/O 요청의 시스템 콜 발생 (running -> blocked)
2. terminate

Preemptive (강제 반납)

1. 할당 시간 만료로 timer interrupt가 발생하는 경우 (running -> ready)
2. I/O 작업 완료 후 interrupt 발생하는 경우 (blocked -> ready)

 

 

 

CPU 스케줄링 알고리즘

CPU 스케줄링을 수행하는 알고리즘은 다양하게 존재합니다.

 

CPU 스케줄링의 성능은 시스템 입장, 프로그램 입장으로 구분됩니다.

 

시스템 입장에서는 CPU가 놀지 않은 시간, 처리량을 기준으로 판단합니다.

 

사용자 입장에서는 프로세스가 CPU 를 다 쓰고 나가는 turnaround time,

 

대기 시간인 waiting time 및 처음으로 CPU를 얻기까지의 시간인 response time이 됩니다.

 

 

FCFS (First Come First Out)

선입 선출 알고리즘입니다. 큐와 같은 방식으로 작동한다고 생각하시면 될 것 같습니다.

 

짧은 시간안에 해결할 수 있는 작업이 오래 기다릴 수 있다는 단점이 존재합니다.

 

따라서 대기시간의 평균이 길어지게 됩니다.

 

 

SJF (Shortest Job First)

CPU 사용시간이 가장 짧은 프로그램에게 CPU를 주는 것을 말합니다.

 

CPU를 빠르게 사용할 수 있는 프로세스가 우선되므로 대기시간의 평균은 짧아지게 됩니다.

 

하지만 계속 자신보다 CPU를 적게 사용하는 프로세스가 들어오면, 특정 프로세스는 무한히 기다리는 Starvation 현상이 발생할 수 있다는

 

문제가 존재합니다.

 

 

Priority-Sheduling

우선순위가 높은 프로세스에게 CPU를 할당하는 것을 말합니다.

 

SJF 알고리즘의 개선 버전이라고 생각하시면 될 것 같습니다.

 

SJF 처럼 사용시간이 가장 짧은 프로세스에게 CPU 우선권을 주되,

 

우선 순위가 낮은 프로세스를 위해 Aging 기법을 도입합니다.

 

Aging 기법은 오래 기다리는 프로세스의 우선순위를 높여주는 것을 말합니다.

 

이를 통해 Starvating을 막을 수 있게 됩니다.

 

하지만 프로세스의 CPU 점유시간은 정확이 얼마나 될 것인지는 예측할 수 없습니다.

 

과거의 기록들을 통해 시간별 가중치를 두어 점화식으로 계산하게 되는 것이기 때문에 분명히 한계는 존재합니다.

 

 

RR (Round Robin)

현대적인 스케줄링은 라운드 로빈에 기반합니다.

 

선점형 스케줄링이며 CPU를 줄 때 timer로 할당시간을 주게 됩니다.

 

할당시간이 끝나면 다시 ready queue에 가서 기다리게 됩니다.

 

timer로 지정한 시간에 따라 응답시간이 빨라질 수 있다는 장점이 존재하며,

 

CPU 사용시간에 관계없이 누구든지 CPU를 공정하게 할당받을 수 있습니다.

 

다만 극단적으로 할당시간이 커지게 되면 FIFO와 유사한 형태가 되고,

 

반대로 너무 작은 경우에는 컨텍스트 스위치가 너무 빈번하게 발생하면서 오버헤드로 인하여 전체 시스템 성능이 낮아질 수 있습니다.

 

따라서 적절한 할당시간을 주는 것이 중요합니다.

 

문제점으로는 사용시간이 똑같은 프로세스들이 번갈아가며 CPU 사용하게 되면, 컨텍스트 스위치만 자주 발생하고,

 

모든 프로세스가 너무 동시에 빠져나간다는 문제가 발생할 수도 있습니다.

 

하지만 일반적으로 짧은 프로세스와 긴 프로세스가 섞여서 대기를 하기 때문에 라운드로빈은 대체로 좋은 기법이라고 할 수 있습니다.

 

 

Multilevel Queue

여러 줄로 프로세스들을 줄세워서 스케줄링하는 기법을 말합니다.

 

각 줄은 독립적인 스케줄링 알고리즘을 가지게 됩니다.

 

줄마다 우선순위가 존재하고, 우선순위가 높은 프로세스가 존재하면, 우선순위가 낮은 프로세스는 CPU를 할당받을 수 없는 구조입니다.

 

SJF처럼 영원히 기다리는 프로세스가 생길 수 있으므로, Starvation을 막기 위해 줄별로 최소한의 CPU는 할당해 주는 것을 보장합니다.

 

차별적이지만 우선순위가 높은 프로세스가 CPU를 먼저 얻어야 하기 때문에 고안된 방식입니다.

 

 

Multilevel Feedback Queue

피드백에 따라 우선순위를 바꿀 수 있는 스케줄링입니다.

 

멀티레벨 큐를 좀 더 유연하게 진행하는 알고리즘이라 생각하시면 됩니다.

 

처음에 어느 큐에 들어가는지, 상위 큐와 하위큐로 가는 기준이 중요하게 됩니다.

 

보통의 운영 방식은 처음 들어오는 프로세스는 우선순위를 높게, 라운드 로빈 할당시간을 짧게 주고,

 

밑으로는 라운드 로빈이 길게, 마지막에는 FCFS 방식으로 처리합니다,.

 

 

 

출처

KOWS 운영체제 - 반효경 교수님 - CPU Scheduling 1

http://www.kocw.net/home/search/kemView.do?kemId=1046323