[OS] 운영체제 5.2 CPU Scheduling

CPU Scheduling 이 필요한 이유 ? 

여러 종류의 job (= process) 가 섞여 있기 때문에 스케줄링이 필요하다. CPU를 계속해서 사용하는 CPU bound job도 있고, 사용자와 인터렉션을 해야하는 I/O bound job 이 있다. 

FCFS (First-Come-First-Served) 

프로세스의 도착 순서대로 사용한다. -> 마지막으로 도착한 프로세스가 지나치게 오래 기다리게 될 것이다. 

Round Robin 

각 프로세스는 동일한 크기의 시간을 할당 받고, 할당받은 시간이 지나면 프로세스는 선덤 당하고 ready queue의 가장 뒤에 가서 줄을 선다. 프로세스가 ready queue에 n 개 있을 때, 할당 시간이 q time-unit인 경우, 각 프로세스는 최대 q time-unit단위로 CPU 시간의 1/n를 얻는다. -> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다. 

Multilevel Queue 

Ready Queue를 여러 줄로 분할하여 기다린다. 

• foreground queue : interactive 한 job 을 집어 넣는다. 즉 사용자와의 I/O가 있는 job들이 들어가게 된다. 
• background queue : 사용자와 interaction이 없는 batch 작업을 집어 넣는다. 

각 queue는 독립적인 스케줄링 알고리즘을 가진다. 

• foreground queue : Round Robin 방식 -> 즉각적으로 I/O 처리를 빨리 받아야 하므로 RR가 응답시간이 짧아질 것이다. 
• background queue : FCFS 방식 -> 계속해서 CPU를 오랫동안 사용하게 될 프로세스들. 응답시간이 빠르지 않아도 상관 없음. Context Switch 할 때 오버헤드를 줄인다. 

Queue에 대한 스케줄링이 필요하다. 

• 우선순위를 강하게 적용하는 방식 : 높은 우선순위의 queue가 비어있는 경우에만 낮은 우선순위의 queue에서 job을 실행할 수 있는 방식. 기아 현상이 발생할 수 있다. 
• Time Slice : 각 queue마다 CPU time을 적절한 비율로 할당 ex) 우선순위가 높은 큐에 80%를 주고 낮은 큐에 20%를 부여하는 방식으로 운영 

Multilevel Feedback Queue 

• process가 다른 queue로 이동하는 것을 허용한다. Multilevel Queue에서는 포그라운드와 백그라운드 특성으로 프로세스들을 구분하기 때문에 시스템 진입시에 영구적으로 큐에 할당되지만 Multilevel Feedback Queue에서는 이동할 수 있다. 
• process를 상위 큐로 보내는 기준, 하위 큐로 보내는 기준에 대한 parameter필요하다. 
• aging 을 구현함 : 우선순위가 낮은 큐에서 너무 오래 대기하는 프로세스는 우선순위가 높은 큐로 이동할 수 있다. 
• time quantum (시간 할당)을 가장 우선순위가 높은 큐에서부터 낮은 큐로 갈수록 커진다. 맨 아래 level의 큐는 FCFS로 운영한다. 

Thread Scheduling 

• Local Scheduling : User Level Thread의 경우 사용자 수준의 thread library 에 의해 어떤 thread를 스케줄할지 결정 
• Global Scheduling : kernel Level Thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정