[운영체제] MLQ & MFQ
[운영체제] MLQ & MFQ
다단계 큐 (Multi-Level Queue) 스케줄링
- FIFO + RR 스케줄링
- 각 작업들을 서로 다른 묶음으로 분류할 수 있을 때 사용하는 알고리즘
- ex) 작업을 전면 작업(대화형, Foreground Task)과 후면작업(일괄처리형, Background Task)으로 분류한다면 두 유형의 요구 반응 시간이 다르므로 서로 다르게 스케줄링해야합니다.
- 더욱이 전면 작업은 후면 작업에 비해 높은 우선순위를 갖는 경우가 많습니다.
- ex) 쇼핑몰에서 쇼핑은 빠르게 백그라운드에서는 다운로드는 느리게
다단계 큐 스케줄링 알고리즘은 준비상태 큐를 종류별로 여러 단계로 분할해 둡니다.
그리고 작업을 기억 장치의 크기나 프로세스의 형태에 따라 어느 한 큐에 지정합니다
각 큐는 자신만의 독자적인 스케줄링 알고리즘을 갖고 있습니다.
예를 들어, 전면 작업과 후면 작업이 분할된 큐에 지정되면 전면 작업 큐는 순환 할당 알고리즘에 의해 스케줄링 되고 후면 작업 큐는 선입 선처리로 스케줄링 됩니다.
또한 큐 사이에도 스케줄링이 있어야 하는데 이것은 고정된 우선순위의 선점식 스케줄링입니다.
예를 들어, 전면작업 큐는 후면작업 큐 보다 절대적인 우선순위를 가질 수 있습니다.
 |
| 큐 5개를 가진 다단계 큐 스케줄링 알고리즘 |
예를 들어, 시스템 프로세스, 대화식 프로세스, 그리고 대화식 편집 프로세스를 위한 큐들이 모두 비어 있어야 일괄처리 큐에 있는 프로세스가 실행됩니다.
일괄처리 프로세스가 실행되는 동안에 대화식 편집 프로세스가 준비 큐에 들어오면 일괄 처리 프로세스는 프로세서를 반납해야 합니다.
또한 큐들 사이에 시간을 나누어 사용할 수도 있습니다.
각 큐는 프로세서 시간의 일정량을 받아서 큐에 있는 프로세스들을 스케줄링 할 수 있습니다.
다단계 피드백 큐 (Multi-Level Feedback Queue) 스케줄링
입출력 위주의 프로세스들은 CPU를 잠시만 사용하고 입출력 요구를 발생시키지만, 연산 위주의 프로세스들은 비선점 기법 하에서 CPU를 일단 차지하면 장시간 계속 연산을 수행한다.
일반적으로 스케줄링 기법에서는 짧은 작업에 우선권을 주어야 하고 입출력 장치를 효율적으로 활용하기 위해 입출력 위주의 작업들에게 우선권을 주어야 하며, 가능한 한 빨리 작업의 성격을 파악하여 그에 맞는 전략을 세워야 한다.
MLQ스케줄링보다 좀 더 고도화된 알고리즘으로, 정확한 개념은 아니지만 쉽게 설명하자면 MLQ에서 생길 수 있는 Starvation을 보완한 스케줄링 기법이다.
MFQ는 우선순위가 높은 프로세스에게는 불이익을, 우선순위가 낮은 프로세스에게는 이익을 제공합니다.
기본적으로 MFQ에서는 가장 우선순위가 낮은 큐를 제외하고는 모두 RR스케줄링을 사용합니다.
(가장 우선순위가 낮은 큐는 FCFS, 또는 RR을 사용합니다.)
이때 우선순위가 높은 큐 일수록 짧은 Time Slice를 주게 되고 한번의 Time Slice안에 그 프로세스의 실행이 끝나지 않으면 한단계 낮은 우선순위를 가지고 있는 큐로 보내게 됩니다.
반대로 어떤 큐에서 일정시간동안 실행되지 못하고 남아 있을 경우에는 우선순위가 한단계 높은 큐로 보내주게 되는 것 입니다.
예시를 한번 보도록 하겠습니다.
프로세스 1, 2, 3, 4가 시간차를 두고 Q1에 들어옵니다. 이 때 주어진 Time Slice인 4초안에 프로세스 실행이 끝이 나지 못하자 Q2로 보내지게 되고 Q2에서 P1은 8ms동안 실행이 됩니다.
입출력 위주의 프로세스와 연산 위주 프로세스의 특성에 따라 CPU 사용시간(할당량)을 다르게 부여하는 선점 방식의 CPU 스케줄링
특징
일반적으로 스케줄링 기법에서는 짧은 작업에 우선권을 주어야 하고 입출력 장치를 효율적으로 활용하기 위해 입출력 위주의 작업들에게 우선권을 주어야 하며, 가능한 한 빨리 작업의 성격을 파악하여 그에 맞는 전략을 세워야 한다.
MLQ스케줄링보다 좀 더 고도화된 알고리즘으로, 정확한 개념은 아니지만 쉽게 설명하자면 MLQ에서 생길 수 있는 Starvation을 보완한 스케줄링 기법이다.
MFQ는 우선순위가 높은 프로세스에게는 불이익을, 우선순위가 낮은 프로세스에게는 이익을 제공합니다.
기본적으로 MFQ에서는 가장 우선순위가 낮은 큐를 제외하고는 모두 RR스케줄링을 사용합니다.
(가장 우선순위가 낮은 큐는 FCFS, 또는 RR을 사용합니다.)
이때 우선순위가 높은 큐 일수록 짧은 Time Slice를 주게 되고 한번의 Time Slice안에 그 프로세스의 실행이 끝나지 않으면 한단계 낮은 우선순위를 가지고 있는 큐로 보내게 됩니다.
반대로 어떤 큐에서 일정시간동안 실행되지 못하고 남아 있을 경우에는 우선순위가 한단계 높은 큐로 보내주게 되는 것 입니다.
프로세스 1, 2, 3, 4가 시간차를 두고 Q1에 들어옵니다. 이 때 주어진 Time Slice인 4초안에 프로세스 실행이 끝이 나지 못하자 Q2로 보내지게 되고 Q2에서 P1은 8ms동안 실행이 됩니다.
입출력 위주의 프로세스와 연산 위주 프로세스의 특성에 따라 CPU 사용시간(할당량)을 다르게 부여하는 선점 방식의 CPU 스케줄링
특징
- 프로세스 성격에 따라 적응적 스케줄링이 가능하다.
- 상위 단계 큐에서 하위 단계 큐로 갈수록 할당시간(time quantum)이 길어진다.
- CPU 위주 프로세스보다 입출력 위주 프로세스를 선호한다.
- 주로 실시간 OS에 적합하다.
출처
잘몰라서 묻습니다. 다단계 피드백 큐의 특징 첫 번째는 레벨큐 특징 아닌가요??
답글삭제