<운영체제> CPU SCHEDULING - Multilevel Queue, FSS Scheduling
HONG CHANGSUB -
본 게시물은 영남대학교 곽종욱 교수님의 강의를 기반으로 작성됨
Multilevel Queue Scheduling이란?
커널내의 레디큐를 여러개의 큐로 분리하여 큐들 사이에서도 우선순위를 부여하는 스케쥴링 정책이다.
각각의 레디큐들은 각기다른 CPU 스케쥴링 정책을 선택한다.
예를 들면, foreground는 RR, background는 FCFS처럼 각기 상이하게 설정이 가능하다.
어떠한 프로세스가 한번 특정 레디큐에 할당되면 그 프로세스는 다른 레디큐에 할당 되어질 수 없다.
레디큐들 사이의 스케쥴링 정책의 예시
Fixed priority scheduling : foreground의 큐를 먼저 실행하고, background의 큐는 그 이후에 실행한다. 이는 starvation을 유발할 확률이 상당히 높다
Time-Slice : 예를 들어 3가지 종류의 큐가 존재하는 Multilevel Queue라고 가정하자. 이러한 상황에서 첫번째 큐에는 60%, 두번째와 세번째 큐에는 각각 20%씩 시간을 할당하는 방식이다. 즉, 10초라는 시간 중 6초는 첫번째 큐의 프로세스 실행, 그후는 순서대로 2초씩 나머지 큐들에 시간을 할당하는 방식이다. 이러한 방식의 경우, starvation에 대한 solution 이 될수 있다.
Multilevel Queue Scheduling의 예시 그림
Multilevel Feedback Queue Scheduling이란?
Multilevel Queue Scheduling에서 발전된 형태로써, 레디큐들 사이를 프로세스가 갈아 탈 수 있다는 점이 기존과 다르다.
아래의 그림처럼 프로세스가 아래로 이동 및 하나의 프로세스 입구를 가진 구조도 있고, 사용자의 설계 방식에 따라 위로 거슬러 오르는 구조, 각각의 큐마다 입구를 가지는 구조 등 굉장히 설계 선택 옵션을 다양하게 가져갈 수 있다.
아래의 구조의 경우, 8 time-quantum 만큼 지나고 해당 프로세스가 종료되지 않으면 아래쪽의 16 time-quantum을 가진 큐로 하강하게 되며, 무조건 16 time-quantum만큼의 시간을 두번째 큐의 프로세스에게 할당시킨다. 이러한 방식은 마찬가지로 starvation에 대한 해결법이다.
Multilevel Queue Scheduling의 예시 그림
FSS Scheduling이란?
Fair Share Scheduling의 약자로써, 사용자 그룹을 상대적으로 중요한 사용자 그룹과 덜 중요한 사용자 그룹으로 나눈 후, 차등적으로 CPU 실행 시간을 할당하는 정책이다.
이러한 정책의 목적은 상대적으로 덜 중요한 그룹의 CPU 독점 현상을 방지하기 위함이다. 예를 들어 SJF 정책하에서 덜 중요한 그룹이 계속 Burst-Time 이 짧은 프로세스를 Dispatch 한다면 중요한 그룹의 Burst-Time이 긴 프로세스의 경우 상당히 늦게 실행이 된다. 이러한 문제점을 해결하기 위한 정책이 FSS이다.
아래 그림의 경우, 중요도에 따라 차등적으로 2:1:1 비율로 각각의 사용자 그룹에 CPU 할당량(System Resource)을 할당하였으며, 각각의 그룹 내에서의 CPU Scheduling 정책의 경우 각각의 그룹마다 상이할 수도 있고 동일 할 수도 있다.