MLFQ (Multi Level Feedback Queue)
: CPU 사용 패턴에 따라 프로세스의 우선순위를 동적으로 조정하는 스케줄링 알고리즘
- 타임 슬라이스가 다른 여러 개의 큐를 사용
- CPU를 오래 쓰는(CPU Bound) 프로세스는 우선순위를 낮추고, 짧게 쓰는(I/O Bound) 프로세스는 우선순위를 유지하거나 높임
→ 이렇게 해서 I/O Bound 프로세스는 빠르게 응답하고, CPU Bound 프로세스는 공정하게 CPU를 할당받도록 함 - 오늘날 운영체제에서 가장 일반적으로 쓰이는 CPU 스케줄링 기법
- RR(Round Robin)을 업그레이드한 알고리즘
- MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋도록 작은 타임 슬라이스를 선택함
CPU Bound Process & I/O Bound Process
| CPU Bound Process | 대부분의 시간을 CPU 연산에 사용 | 가장 중요하게 생각하는 것: CPU 사용량, 처리량 |
| I/O Bound Process | 대부분의 시간을 I/O 작업에 사용 | 가장 중요하게 생각하는 것: 응답 속도 |
- 운영체제가 CPU Bound / I/O Bound 구분하는 방법
- 프로세스가 스스로 CPU를 반납하면 → I/O Bound Process (CPU 사용이 적음)
- 프로세스가 타임 슬라이스를 초과해 CPU를 강제로 뺏기면 → CPU Bound Process (CPU 사용이 많음)
예시
- P1 – I/O 작업 X, CPU 연산만 하는 프로세스
→ CPU Bound Process - P2 – I/O 작업은 10초, CPU 연산은 1초 하는 프로세스
→ I/O Bound Process
예시 1) 타임 슬라이스가 100초인 경우 (P2 우선 실행)
- P2 실행
- 1초 실행됨 → I/O 요청 발생
- P1 실행
- 타임 슬라이스 100초 동안 실행됨 → 다 실행된 이후엔 CPU 뺏김
- P2 실행
- 10초 I/O 작업 완료 → 인터럽트 발생 → 다시 큐에 들어가 CPU 할당
- P1 실행
- 타임 슬라이스만큼 100초가 실행된 후엔 CPU를 뺏김
- P2 실행
- 1초 실행 → 다시 I/O 요청
- 위 과정 반복
예시 2) 타임 슬라이스가 1초인 경우 (P2 우선 실행)
- P2 실행
- 1초 실행됨 → I/O 요청 발생
- P1 실행
- 타임 슬라이스인 1초만큼 실행
- P2의 I/O 작업이 끝나지 않아서 P1이 큐로 들어가고 다시 실행됨 → 10번(10초) 반복 실행됨
- P2 실행
- P1이 10번(10초) 실행되면, P2의 I/O 작업이 완료 → 인터럽트가 발생함 → P2는 다시 큐에 들어가 CPU 할당
- 위 과정 반복
상황 비교
| 조건 | CPU 사용률 | I/O 사용률 | 비고 |
| 타임 슬라이스 100초 | 100% | 10% (10 / (1+100)) | P1이 실행되는 동안 P2의 I/O 작업이 완료된 시점부터 기다리는 시간 발생 |
| 타임 슬라이스 1초 | 100% | 90% (10 / (1+10)) | P1의 타임 슬라이스가 작기 때문에 P2가 기다리며 낭비되는 시간이 거의 없음(1초 기다림) |
결론
→ 타임 슬라이스가 작을수록 I/O 사용률이 높아지고 효율적이다.
- 타임 슬라이스가 작아지면,
- P1은 연속으로 실행되기 때문에 손해가 없어보임
→ 실제로는 컨텍스트 스위칭 오버헤드로 인해 손해가 발생함 - P2는 I/O 사용률이 매우 높아짐 → 이득
- P1은 연속으로 실행되기 때문에 손해가 없어보임
작동 방식 요약
- 우선 순위가 다른 큐들을 여러 개 만들어서 운영
- 우선 순위 높을수록 타임 슬라이스 작고, 우선 순위가 낮을수록 큼
- CPU를 타임 슬라이스 초과해 사용하면, 낮은 우선순위 큐로 이동
→ 타임 슬라이스가 점점 커짐
→ 최종적으로는 FIFO처럼 긴 시간 동안 연속 실행 가능
- ex) P1처럼 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏긴다면, P1은 원래 있던 큐보다 우선 순위가 더 낮은 큐로 이동함
→ 다음번에 실행될 때는 타임 슬라이스가 조금 더 커짐 (여기서도 부족하면 다음엔 더 큰 타임 슬라이스를 할당 받게 됨)
→ 최종적으로는 타임 슬라이스를 무한초에 가깝게 할당받기 때문에 FIFO처럼 연속적으로 작업을 마칠 수 있게 됨
- ex) P1처럼 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏긴다면, P1은 원래 있던 큐보다 우선 순위가 더 낮은 큐로 이동함