한 번 배정한 예산을 계속 똑같이 쓰면 순차 읽기 애플리케이션과 산발적인 애플리케이션을 구분할 수 없어요. 그래서 BFQ는 B-WF2Q+가 순서를 정하는 동안 뒤에서 계속 예산 값 자체를 다시 계산하는 피드백-루프를 돌려요. 그런데 이 재계산 로직을 논문은 왜 굳이 “덧셈”에서 “곱셈”으로 바꿨을까요?
피드백-루프 알고리즘이란
BFQ의 예산 계산은 애플리케이션이 비활성화될 때마다 다음 예산 값을 그 애플리케이션이 다음번에 요청할 것으로 예상되는 섹터 수에 가깝게 수렴시키려는 피드백-루프 알고리즘이에요. 다만 아무리 예측이 잘 맞아도 예산이 무한정 커질 수는 없고, 디스크 전역에서 정해지는 최대 예산 Bmax를 넘을 수 없어요. BFQ는 이 Bmax 값 자체도 고정하지 않고 동적으로 갱신하는데, 디스크 피크 처리율을 자주 샘플링한 뒤, 사용자가 설정할 수 있는 최대 시간 슬라이스 Tmax(기본값 125ms) 동안 그 추정 피크 속도로 읽을 수 있는 섹터 수를 Bmax로 잡아요.
왜 순차 애플리케이션에는 큰 예산이 필요한가
높은 처리량을 내려면 순차적인 요청이 많이 이어져야 하는데, 문제는 새로 서비스 대상으로 선택된 애플리케이션의 첫 요청이 직전 애플리케이션의 마지막 요청과는 거의 무관한 위치라 랜덤 접근처럼 처리된다는 점이에요. 하드웨어에 따라 이 첫 요청의 접근 시간은 0.1ms에서 20ms까지 벌어질 수 있고, 그 시간 동안은 처리량이 사실상 0이기 때문에 애플리케이션이 충분히 오래 서비스를 받아야 평균 처리량이 피크치에 가까워져요. 논문은 최악의 경우인 20ms 접근 시간을 가정해도 150ms 동안 연속 서비스를 받으면 평균 처리량이 피크의 약 90%에 도달한다고 계산했어요. 결국 순차 애플리케이션에는 넉넉한 예산을, 그 반대는 작은 예산을 줘야 처리량과 지연 시간을 동시에 잡을 수 있다는 게 이 절의 핵심 결론이에요.
초기 예산을 절반으로 낮춘 이유
원래 BFQ는 새로 생성된 애플리케이션에 무조건 최대 예산 Bmax를 배정했어요. 이렇게 하면 그 애플리케이션이 순차적이고 디스크 위주 작업일 경우 곧바로 높은 처리량을 낼 수 있지만, 대신 그 애플리케이션이 보내는 첫 요청들의 최악 지연 시간을 늘려버리는 부작용이 있어요. 인터랙티브하거나 소프트 실시간 애플리케이션에는 이게 꽤 치명적이라, 논문은 초기 예산 값을 Bmax의 절반으로 낮추는 대신, 나머지 규칙을 곱셈 증가/선형 감소 방식으로 다시 튜닝해서 처리량 손실을 만회했어요.
세 가지 상황별 새 규칙
논문은 애플리케이션이 비활성화되는 세 가지 이유별로 각각 다른 규칙을 정의해요. 첫째, 백로그가 더 없을 때는 원래 소비한 섹터 수만큼만 다음 예산을 잡는 게 원칙이었는데, 아직 디스크에 전달됐지만 완료되지 않은 요청이 남아있다면 그 애플리케이션의 실제 필요량이 아직 불확실하다고 보고 오히려 예산을 두 배로 늘려요. 완료되지 않은 요청이 전혀 없을 때만 예산을 Bmax의 1/8만큼 선형으로 줄이는데, 이게 유일하게 예산이 줄어드는 경우예요.
둘째, 예산 타임아웃이 발생했을 때는 원래 곧바로 최대 예산 Bmax로 점프시켰지만, 실험 결과 이 방식이 산발적이고 짧은 I/O를 수행하는 애플리케이션의 지연을 오히려 늘린다는 게 확인돼서 논문은 대신 예산을 딱 두 배로만 늘리는 규칙으로 바꿨어요. 셋째, 예산을 완전히 소진했는데도 백로그가 남아있다면 이건 순차적이고 디스크 위주인 애플리케이션일 가능성이 가장 높은 경우라, 원래 일정량을 더하던 규칙 대신 예산을 네 배로 늘리는 훨씬 공격적인 규칙을 적용해요.
곱셈 증가가 만든 실제 차이
이 세 규칙을 종합하면 결론은 명확해요. 디스크 위주로 계속 순차 접근을 하는 애플리케이션일수록 예산이 두 배, 네 배씩 빠르게 불어나 금세 최대치에 도달하고, 그렇지 않은 애플리케이션은 예산이 천천히 줄어들며 자연스럽게 짧은 슬라이스로 수렴해요. 논문의 짧은 벤치마크 결과를 보면 이 차이가 실측으로도 드러나는데, 원래 BFQ는 초기 예산이 이미 Bmax라서 시작부터 최대 처리량을 내는 반면, 초기 예산을 절반으로 낮춘 BFQ+는 H-throughput과 H-fairness 휴리스틱 덕분에 1~2초 안에 같은 최대 처리량에 도달했고, 반면 CFQ는 첫 15초 동안 평균 처리량이 59.6MB/s에 그쳤어요. 다음으로 살펴볼 문제는 애플리케이션이 랜덤 패턴을 보일 때 이 예산 계산이 어떻게 공정성을 지키느냐인데, 이건 예산 타임아웃이라는 별도의 시간 제약과 맞물려 있어요.
자주 묻는 질문
Q1. BFQ의 최대 예산(Bmax)은 어떻게 정해지나요?
BFQ는 디스크 피크 처리율을 추정한 뒤, 그 추정치로 사용자가 설정한 최대 시간 슬라이스(Tmax, 기본값 125ms) 동안 읽을 수 있는 섹터 수를 계산해서 Bmax로 정해요.
Q2. 새로 생성된 애플리케이션의 초기 예산은 얼마인가요?
원래 BFQ는 최대 예산 Bmax를 그대로 부여했지만, 논문에서 제안한 개선판(BFQ+)은 지연 시간을 줄이기 위해 초기 예산을 Bmax의 절반으로 낮췄어요.
Q3. 예산이 다 소진되지 않고 남았는데 백로그가 없어지면 어떻게 되나요?
아직 완료되지 않은 요청이 남아있다면 새 규칙은 예산을 오히려 두 배로 늘려요. 반대로 남은 요청이 전혀 없다면 최대 예산의 1/8만큼 예산을 선형으로 줄여요.
Q4. 예산 타임아웃이 발생하면 다음 예산은 어떻게 바뀌나요?
원래 규칙은 곧바로 최대 예산으로 점프시켰지만, 논문은 이 방식이 산발적인 I/O를 수행하는 애플리케이션의 지연을 늘린다는 걸 확인하고 대신 예산을 두 배로만 늘리는 규칙으로 바꿨어요.
Q5. 예산을 다 써버린 경우(budget exhaustion)는 어떻게 처리되나요?
아직 백로그가 남아있는데 예산까지 소진했다면 순차적이고 디스크 위주 작업일 가능성이 높다고 보고, 원래는 일정량을 더하던 것을 논문은 예산을 네 배로 늘리는 훨씬 공격적인 규칙으로 바꿨어요.
Q6. 예산을 자주 재계산하면 오버헤드가 크지 않나요?
예산 재계산은 애플리케이션이 비활성화되는 시점(예산 소진, 유휴, 타임아웃)에만 일어나기 때문에 매 요청마다 계산이 발생하지 않아 오버헤드가 크지 않아요.
BFQ 비디오 재생 벤치마크: 반응성을 높인 대가로 프레임이 얼마나 떨어졌나
BFQ+의 low-latency 휴리스틱이 반응성을 높이는 대신 소프트 실시간 애플리케이션에 어떤 지연 시간 대가를 요구하는지 논문의 비디오 재생 벤치마크로 확인합니다.
NCQ가 켜지면 디스크 스케줄러 보장이 무너지는 이유 (BFQ 논문 실측)
Native Command Queueing이 활성화되면 BFQ, CFQ 같은 OS 스케줄러의 공정성·지연 보장이 어떻게 무력화되는지 논문의 실측 데이터로 설명합니다.
BFQ+ vs BFQ vs CFQ 실측 벤치마크: 처리량과 앱 기동 시간 비교
BFQ 논문이 세 대의 리눅스 시스템에서 실측한 집계 처리량과 bash·konsole 기동 시간 벤치마크 결과를 수치 그대로 정리합니다.