[운영체제] MLFQ (Multi-Level Feedback Queue) 스케줄링 알고리즘

MLFQ (Multi-Level Feedback Queue) 스케줄링 이란?

 

MLFQ (Multi-Level Feedback Queue) 스케줄링은 현대 운영 체제에서 널리 사용되는 

 

고급 CPU 스케줄링 방법 중 하나이다.

 

이 방법은 여러 우선순위를 가진 큐를 사용하고,

 

프로세스의 행동에 따라 동적으로 우선순위를 조정하여

 

CPU와 I/O 자원의 효율적 사용을 극대화합니다.

 

 

MLFQ의 기본 원리

타임 슬라이스와 우선순위

MLFQ는 각기 다른 타임 슬라이스를 가진 여러 개의 큐를 사용한다.

 

우선순위가 높은 큐에 있는 프로세스는 짧은 타임 슬라이스를 받고,

 

우선순위가 낮은 큐에 있는 프로세스는 긴 타임 슬라이스를 받는다.

 

피드백

프로세스가 할당된 타임 슬라이스 내에 작업을 마치면 (주로 I/O 요청으로 인해)

 

더 높은 우선순위 큐로 이동할 수 있다.

 

반면, 타임 슬라이스를 소진하고 작업이 완료되지 않은 프로세스는 더 낮은 우선순위의 큐로 이동한다.

 

 

 

MLFQ의 기원과 예시

 

두 프로세스, P1과 P2가 존재한다고 가정하자.

 

P1: CPU 집중적 작업 (CPU-bound) -> CPU 작업을 수행

 

P2: 주기적인 I/O 작업 수행 (I/O-bound) -> CPU 작업을 1초 수행 후 I/O 작업 10초 수행

 

 

상황 1: 큰 타임 슬라이스 (100초)

 

P2가 먼저 실행된다고 가정해 보자.

P2는 1초 실행되고 I/O 작업을 요청을 하고 기다린다. (정확히는 P2는 대기상태 Queue로 진입)

 

아래에 보이는 Queue는 준비상태 큐이다.

 

이제 P1이 실행되는데 타임 슬라이스 크기인 100초만큼 실행된다.

P1이 실행되는 도중에 10초가 지났을 때 P2가 요청한 I/O 작업이 완료되고 인터럽트가 발생된다.

그럼 P2는 다시 큐에 들어가서 CPU를 할당받을 준비를 한다.

P1는 100초 실행되면 CPU를 뺏기게 되고 

 

큐에 있던 P2는 다시 1초 실행되고 I/O 작업을 요청하고 다시 기다린다.

위의 작업이 모든 작업이 완료될 때까지 계속 반복된다.

 

 

상황 2: 작은 타임 슬라이스 (1초)

 

 

P2가 1초 실행되고 I/O 작업을 요청하고 기다린다.

 

이제 P1이 실행되는데 타임 슬라이스 크기인 1초만큼 실행된다.

 

지금 P2는 I/O 작업이 끝나지 않아서 계속 기다리는 상황이다. (대기 상태 Queue에 존재)

 

그렇기 때문에 P1은 종료되고 바로 큐에 들어가는데

큐가 비어있기 때문에 P1이 다시 실행된다. 

 

이렇게 P1이 10번 즉 10초 동안 실행되면 P2의 I/O 작업이 끝나 인터럽트가 발생되고 

P2는 큐에 들어간다. 그럼 P2는 다시 1초 실행되고 다시 I/O 작업을 요청하고 기다린다.

위와 같은 방식으로 모든 작업이 완료될 때까지 계속 반복된다.

 

 

 

첫 번째 상황을 보면 CPU 사용률을 보면 CPU는 쉬지 않고 일하기 때문에 CPU 사용률이 100%이다.

하지만 I/O 사용률을 보면 P1이 실행되는 동안 P2의 I/O 작업이 완료된 시점부터 

 

기다리는 시간이 발생하기 때문에 10 / (1 + 100)으로 대략 10% 밖에 되지 않는다.

 

 

 

두 번째 상황도 CPU 사용률을 보면 CPU는 쉬지 않고 일하기 때문에 100%이다.

하지만, I/O 사용률은 첫 번째 상황과 조금 다르다.

P1의 타임슬라이스가 작기 때문에 P2가 첫 번째 상황처럼 기다리며 

 

낭비되는 시간이 거의 없고 10 / (10 + 1)으로 대략 90% 정도의 사용률이 나오게 된다.

위의 결과를 보면 CPU 사용률 와 I/O 사용률을 보면 

 

타임슬라이스가 작은 값이 더 성능이 좋다는 결론이 나온다.

 

 

타임슬라이스가 100초에서 1초로 작아질 때 

 

P1, P2 입장에서 보면 한쪽은 손해를 보고 한쪽은 이득을 보는 구조이다.

CPU Bound Process인 P1은 100초였던 실행시간이 1초로 줄었지만 

 

연속으로 실행되기 때문에 손해가 없는 것처럼 보인다.

하지만, Context Switching을 하기 때문에 오버헤드가 생겨서 손해를 보게 된다.

반면 I/O Bound Process 인 P2는 I/O 사용률이 굉장히 높아졌기 때문에 이득을 봤다.

운영체제를 연구하는 사람들은 손해 보는 프로세스가 어떻게 하면 손해보지 않을까 고민을 하게 된다.

바로 여기서 MLFQ가 탄생한다.

 

 

 

MLFQ 운용 방법

 

MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는

 

작은 크기의 타임슬라이스를 선택한다.

그리고 P1과 같은 CPU Bound Process들에게는 타임 슬라이스를 크게 주는 것이다.

그럼 운영체제 입장에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까?

CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 

 

CPU 사용이 적은 거니 I/O Bound Process일 확률이 높다.

반대로 CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 

 

CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 

CPU 사용이 많은 것이니 CPU Bound Process 일 확률이 높다.

이러한 아이디어를 통해서 우선순위를 가진 큐를 여러 개 준비해 둔다.

우선순위가 높으면 타임 슬라이스가 작고

 

우선순위가 낮을수록 타임슬라이스의 크기가 커진다.

만약 P1처럼 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏긴다면 

 

P1은 원래 있던 큐보다 우선순위가 더 낮은 큐로 이동한다.

 

그러면 다음번에 실행될 때는 타임 슬라이스 크기가 조금 더 커지게 되고 

 

여기서도 부족하다면 다음엔 더 큰 타임 슬라이스를 할당받게 된다. (낮은 우선순위 큐로 이동함)

 

최종적으로는 타임 슬라이스가 무한초에 가깝게 할당되기 때문에 

 

FIFO처럼 연속적으로 작업을 마칠 수 있게 된다.

 

 

 

결론

MLFQ 스케줄링은 그 구조의 복잡성에도 불구하고, 

 

다양한 프로세스 요구를 효과적으로 수용하고 시스템의 성능을 최적화하는 데 크게 기여한다.

 

이러한 스케줄링 기법은 고도로 동적인 현대의 운영 체제 환경에서 특히 중요하며,

 

프로세스 우선순위와 타임 슬라이스 조정을 통해 최고의 성능을 발휘하도록 설계되었다.