[OS] 멀티레벨 피드백 큐 (MLFQ)

MLFQ 목적

• 짧은 작업을 먼저 실행하여 반환 시간을 최적화
• 대화형 시스템으로 사용자에게 빠른 응답을 제공하기 위해 반환 시간을 최적화

MLFQ는 동적으로 우선순위를 부여함으로써 위 목적을 달성한다.

 

 

MLFQ 특징

• 여러 개의 큐를 가지고 있다.
• 각 큐는 서로 다른 우선순위를 갖는다.
• 준비 상태인 모든 프로세스들은 특정 큐에 들어있다.

때문에 두 개의 프로세스가 서로 다른 큐에 들어있다면 우선순위가 높은 큐에 들어있는 프로세스 먼저 실행한다. 만약 동일한 우선순위인 큐에 들어있다면 라운드 로빈 스케줄링으로 수행한다.

 

 

🙋🏻‍♀️ 그러면 어떻게 동적으로 우선순위를 부여하나요?

작업 진행 과정에서 작업의 정보를 얻고, 이 정보를 통해 예측한 미래 행동을 토대로 우선순위를 부여한다.

 

예시를 들어보자.

1. 키보드 입력을 기다리며 반복해서 프로세서를 양보하는 프로세스

2. 긴 시간 동안 프로세서를 사용하는 프로세스

 

위와 같은 두 개의 프로세스가 있을 경우, MLFQ는 1번 프로세스의 우선순위를 높게 유지하고 2번 프로세스의 우선순위를 낮춘다. 즉, 프로세서 점유 시간(타임 슬라이스)에 따라 우선순위가 동적으로 변한다. 과거의 행동으로 우선순위가 결정되는 것이다.

 

 

하지만 위 두 가지 조건만으로는 아래의 문제가 발생

• 기아 문제
• 프로세스 특성 변화 문제
• 스케줄러를 속이고 우선순위 유지 문제

다행히 MLFQ는 해당 문제들에 대한 해결방안을 갖고 있다.

 

 

1. 기아 문제 및 프로세스 특성 변화 문제 해결 방안 : Priority Boost

기아 문제란, 어떤 작업이 오랫동안 수행되지 않는 상태를 말한다. 예를 들어 i/O를 발생시키는 작업이 무한히 많으면 일반 프로세스는 대화형 작업이 끝나기 전까지 수행될 수 없다.

 

 

해당 문제를 해결하기 위해서는 오랫동안 실행되지 않은 작업의 우선순위를 올려주면 된다. 즉, 일정 시간이 지난 후에 시스템의 모든 작업을 우선순위가 가장 높은 큐로 옮긴다. 사진에서는 50초마다 priority boost를 발동시켜 실행 시간이 오래 걸리는 프로세스의 우선순위를 높여주고 있다. 때문에 기아 현상을 방지할 수 있으면 프로세서를 점유할 수 있게 된다.

 

또한 일정 시간 뒤에 우선순위가 높아지기 때문에 프로세스의 특성이 바뀌어도 문제가 되지 않아 프로세스 특성 변화 문제도 함께 해결된다. 하지만 priority boost 쿨타임을 너무 길게 잡을 경우 기아 상태 지속시간이 길어지기 때문에 적절한 시간으로 잡아주는 것이 중요하다.

 

 

2. 스케줄러를 속이는 문제 해결 방안 : Better Accounting

프로세스가 스케줄러를 속일 수 있다. 타임 슬라이스가 10초일 때 프로세스가 9.9초마다 프로세서를 놓아주면 된다. 그러면 우선순위가 떨어질 일이 없다. 이런 문제는 타임 슬라이스를 우선순위마다 지정해 주면 해결된다.

 

 

9.9초만 사용하고 0.1초 뒤에 다시 프로세서를 점유하는 프로세스를 방지하기 위해 특정 큐에서 10초를 모두 소진하면 우선순위가 떨어지도록 하면 된다. 그렇게 되면 타임 슬라이스를 모두 소진함과 동시에 우선순위가 떨어지기 때문에 스케줄러를 속일 수 없다.

 

문제는 다 해결됐다. 이제 남은 질문은 하나!

 

 

🙋🏻‍♀️ 타임 슬라이스는 몇으로 설정하나요?

먼저 타임 슬라이스의 경우, 큐의 우선순위에 따라 다르게 설정한다. 높은 우선순위를 가진 큐는 짧게 설정하고, 낮은 우선순위를 가진 큐는 길게 설정한다. 우선순위가 높은 작업은 주로 I/O에 사용하는 대화형 작업이기 때문에 짧은 타임 슬라이스를 적용하여 다음 작업을 수행하는 것이 좋다.

 

 

MLFQ 정리

1. 우선순위가 높은 프로세스 먼저 실행한다.
2. 두 개 이상의 작업이 우선순위가 같은 큐에 있으면 라운드 로빈 스케줄링으로 실행한다.
3. 새로운 프로세스가 시스템에 들어가면 가장 높은 우선순위를 부여한다.
4. 큐에 주어진 타임 슬라이스를 모두 사용하면 우선순위가 낮아진다.
5. 일정 시간 후 시스템의 모든 프로세스를 우선순위가 가장 높은 큐로 옮긴다. (priority boost)