대딩/운영체제

스케줄링_Multilevel (Feedback) Queue Scheduling

경아ㅏ 2022. 6. 13. 17:39

Combining Algorithms

 

일반적으로, 현 운영체제에서는 FCFS, SJF, Round Robin과 같은 여러가지 스케줄링 알고리즘을 결합하여 사용합니다.

Multilevel Queue Scheduling과 Multilevel Feedback Queue Scheduling은 여러개의 ready queue를 두어 각 queue마다 다른 스케줄링 알고리즘을 적용하는 방식입니다. 

 

 

Multilevel Queue Scheduling

 

프로세스의 목적과 특성에 따른 여러개의 ready queue를 두어 각 queue마다 다른 스케줄링 알고리즘을 적용합니다. 그렇다면, 각 ready queue 는 어떻게 스케줄링 되어야 할까요? 일반적으로, 각 ready queue는 우선순위 알고리즘에 따라 스케줄링 된다고 합니다.

 

그러니까, ready queue 덩어리들은 우선순위 알고리즘으로 스케줄링이 되고, 각각의 ready queue 내부에서는 저마다의 다른 스케줄링 알고리즘을 두어 사용한다는 이야기입니다.

 

 

 

Example

하나의 예시로, ready queue를 foreground(interactive), background(batch)로 나눌 수 있습니다.

 

1) Foreground queue에는 사용자들과의 상호작용이 빈번한 I/O bound  process들을 담으며, time quantum이 짧은 Round Robin 알고리즘을 사용하여 reponse time을 향상시킬 수 있습니다. 

2) Background queue에는 CPU bound process들을 담으며, FCFS 알고리즘을 사용하여 Cpu utilization을 향상시킬 수 있습니다.

 

일반적으로, Foreground queue를 Backgournd queue보다 높은 우선순위로 스케줄링합니다.

그런데, 계속 Foreground queue에 있는 프로세스들만 스케줄링 한다면 starvation이 발생할 수 있기 때문에 각각의 Queue에 일정량의 CPU time을 미리 할당하여 starvation을 방지합니다. 이를 Time slice라고 하며, 일반적으로 foreground는 80%, background는 20%의 CPU time을 할당받습니다.

 

 

Multilevel Queue Scheduling은 언뜻 보기에 꽤 합리적인 것 같습니다. 하지만, 프로세스를 어떠한 ready queue로 넣어야 하는지에 대한 기준이 모호할 수 있습니다. 예를 들어, IDE(VSCode, Xcode)의 경우 코드를 편집할 때는 interactive process로 분류될 수 있지만, 컴파일 할 때는 batch process로 분류될 수도 있기 때문입니다.

 

 

Multilevel Feedback Queue Scheduling

 

스케줄링 알고리즘 중 Round Robin Algorithm은 프로세스가 한번 스케줄링이 되었을 때 CPU를 사용할 수 있는 최대시간(time quantum)을 지정하여 해당 시간보다 오래 수행되는 경우 time interrupt를 발생시키는 방식입니다.

 

Multilevel Feedback Queue Scheduling은 각 ready queue가 Round Robin Algorithm을 사용하도록 하며(+FCFS), time quantum이 짧을 수록 높은 우선 순위를 가지도록 셋팅합니다.

 

 

프로세스가 만들어지면, 우선순위가 가장 높은 ready queue에 들어가 실행되는데 이 때 두가지 경우가 발생할 수 있습니다.

1) Running 중이던 프로세스가 중간에 I/O 요청을 받아 정해진 time quantum을 모두 사용하지 못하고 CPU에서 내려가는 경우

2) 아무런 방해 없이 쭉 수행되어 timer interrupt에 의해 CPU에서 내려가는 경우 

 

1번의 경우, 해당 프로세스는 I/O bound process에 가깝다고 판단되어 다음에 ready queue에 들어갈 때도 우선순위가 가장 높은 queue에 들어가게 됩니다.

2번의 경우, 현재의 time quantum보다는 CPU burst time이 길다고 판단되어 다음에 ready queue에 들어갈 때 time quantum이 조금 더 긴 프로세스에 들어가게 됩니다.

 

Multilevel Queue Scheduling에서는 프로세스의 특성을 임의로 확정하고 분류해야 했습니다. 그러나 Multilevel Feedback Queue에서는 프로세스를 실행시키며 동적으로 그 특성을 파악할 수 있다는 장점이 있습니다. 

저작자표시