#18 스케줄링 알고리즘 - MLFQ(Multi Level Feedback Queue)
- MLFQ과 연관이 있는 내용이니 먼저 읽어보자
2023.03.19 - [운영체제] - #17 스케줄링 알고리즘 - RR(Round Robin Scheduling)
#17 스케줄링 알고리즘 - RR(Round Robin Scheduling)
● 도입 - FIFO 알고리즘은 일괄처리 시스템에 적절하기에 시분할 처리 시스템에서는 쓰기가 힘들고 SJF 알고리즘은 프로세스 종료시간을 예측할 수 없기에 구현이 힘들다. - FIFO 알고리즘은 먼저
radderveloper.tistory.com
● MLFQ이 나온 계기
- MLFQ은 Round Robin Scheduling의 업그레이드 버전이다.
- 오늘날 쓰이는 CPU 스케줄링 알고리즘의 대부분은 MLFQ이다.
- 아래의 예시를 통해 MLFQ이 나온 계기를 알아보자
P1 프로세스
- P1 프로세스는 I/O 작업 없이 CPU 연산만 하는 프로세스이다.
- P1 프로세스는 CPU 연산을 주로 하기에 CPU Bound Process라고 한다.
- CPU Bound Process에서 가장 중요한 것은 CPU 사용률과 처리량이다.
P2 프로세스
- P2 프로세스는 1초 CPU 연산을 한 후 10초 동안 I/O 작업을 하는 프로세스이다.
- P2 프로세스는 I/O 작업을 주로 하기에 I/O Bound Process라고 한다.
- I/O Bound Process에서 가장 중요한 것은 응답 속도이다.(키보드나 마우스는 즉각적으로 반응을 해야 한다.)
- P1 프로세스와 P2 프로세스를 2가지 상황에서 실행시켜보자
P1 프로세스 : I/O 작업 없이 CPU 연산만 하는 프로세스
P2 프로세스 : 1초 CPU 연산을 한 후 10초 동안 I/O 작업을 하는 프로세스1. Time Slice(Time Quantum)이 100초인 경우(P2가 먼저 실행된다고 가정)
- P2가 1초 동안 실행된 후 I/O 작업을 요청한 후 기다린다.
- 이제 P1이 Time Slice(= 100초)만큼 실행될 예정이다.
- P1이 실행되는 도중 10초가 됐을 때 P2가 요청한 I/O 작업이 완료되어 인터럽트가 발생했다.
- 이로 인해 P2는 다시 Queue에 들어가 CPU를 할당 받을 준비가 된다.(P1의 CPU를 도중에 뺏는게 아니다.)
- P1은 100초 실행되면 CPU를 뺏기게 되고 Queue에 있던 P2가 다시 1초 실행 되고 또 다시 I/O 요청을 한 후 기다린다.
- 이러한 과정이 모든 프로세스가 완료될 때까지 반복된다.
2. Time Slice(Time Quantum)이 1초인 경우(P2가 먼저 실행된다고 가정)
- P2가 1초 동안 실행된 후 I/O 작업을 요청한 후 기다린다.
- 이제 P1이 Time Slice(= 1초)만큼 실행됐다.
- 현재 P2는 I/O 작업이 완료되지 않았기에 계속 기다리는 상태이다.
- 따라서 P1은 종료 후 바로 Queue에 들어가는데 현재 Queue가 아무것도 없이 비어있기 때문에 곧 바로 다시 실행된다.
- 이렇게 P1이 10번(10초 동안) 실행되면 P2의 I/O 작업이 끝나 인터럽트가 발생되고 P2는 Queue에 들어간다.
- 그러면 Queue에 있던 P2가 다시 1초 실행 되고 또 다시 I/O 요청을 한 후 기다린다.
- 이러한 작업이 모든 프로세스들이 완료 될 때까지 계속 반복된다.
- 위의 2가지 상황을 비교해보자
1번 상황
- CPU는 쉬지 않고 계속 일하기 때문에 (CPU 사용률 = 100%)이다.
- I/O 사용률은 10%이다.
2번 상황
- CPU는 쉬지 않고 계속 일하기 때문에 (CPU 사용률 = 100%)이다.
- I/O 사용률은 90%이다.
● MLFQ 탄생
- CPU 사용률과 I/O 사용률 모두 Time Slice가 적은 경우가 더 좋다는 것을 확인할 수 있다.
- Time Slice가 100초 → 1초로 작아질 때 P1은 손해를, P2는 이득을 보게 된다.
- CPU Bound Process인 P1은 Time Slice가 1초로 줄었지만 연속으로 실행되기 때문에 손해가 없는 것처럼 보인다.
- 하지만 Context switching을 하기 때문에 오버헤드가 생겨 손해를 보게 된다.(100초에 한 번 실행하는 것 보다 손해)
- I/O Bound Process인 P2는 I/O 사용률이 높아졌기에 이득이다.
- 어떻게 하면 프로세스 모두에 손해가 발생하지 않을까 고민해서 나온 것이 바로 MLFQ이다.
- MLFQ은 기본적으로 CPU 사용률과 I/O 사용률 모두 좋게 나오는 작은 크기의 Time Slice를 선택한다.
- 하지만 P1과 같은 CPU Bound Process에게는 Time Slice를 크게 준다.
Q. 그렇다면 OS는 CPU Bound Process와 I/O Bound Process를 어떻게 구분하는 걸까?
A.
- CPU를 사용하는 프로세스가 실행 중 스스로 CPU를 반납하면 CPU 사용이 적은 것이니 I/O Bound Process일 확률이 높다.
- 반대로 CPU를 사용하는 프로세스가 Time Slice를 오버해 CPU 스케줄러에 의해 CPU를 강제로 뺏기는 상황이면 CPU Bound Process일 확율이 높다.
- 이러한 개념을 토대로 우선순위를 가진 Queue를 여러개 준비해둔다.
- 우선순위가 높으면 Time Slice가 작고 우선순위가 낮을 수록 Time Slice가 커진다.
- 만약 P1과 같이 Time Slice를 오버해 CPU를 강제로 뺏긴다면 P1은 원래 있던 Queue 보다 우선 순위가 더 낮은 Queue로 이동하게 된다.
- 다음번에 P1이 실행될 때는 Time Slice가 조금 더 커지게 되고 만약 여기서도 부족하다면 크기가 더 큰 Time Slice를 할당받는다.
- 최종적으로는 Time Slice가 무한초에 가깝게 할당되기 때문에 FIFO 처럼 연속적으로 작업을 마칠 수 있게 된다.
cf) CPU Bound Process와 I/O Bound Process 자세히 알아보기
- CPU Bound Process : 프로세스가 진행될 때 CPU 사용 기간이 I/O Wating 보다 많은 경우
- I/O Bound Process : 프로세스가 진행될 때, I/O Wating 시간이 많은 경우
https://velog.io/@carrykim/%EB%B6%84%EC%82%B0-%EC%8B%9C%EC%8A%A4%ED%85%9C-2-3.-CPU-Bound-IO-Bound
[분산 시스템] 2-3. CPU Bound & I/O Bound
CPU Bound는 프로세스가 진행될 때, CPU 사용 기간이 I/O Wating 보다 많은 경우다. 주로 행렬 곱이나 고속 연산을 할 때 나타나며 CPU 성능에 의해 작업 속도가 결정된다.반면 I/O Bound는 프로세스가 진행
velog.io