<운영체제> CPU SCHEDULING - Multilevel Queue, FSS Scheduling
본 게시물은 영남대학교 곽종욱 교수님의 강의를 기반으로 작성됨
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 정책의 경우 각각의 그룹마다 상이할 수도 있고 동일 할 수도 있다.
FSS Scheduling의 예시 그림
