Selfish Round Robin 스케줄링의 이중 큐와 에이징 방식
Selfish Round Robin의 Holding Queue·Active Queue 구조와 에이징 기반 우선순위, 파라미터 조정 방식을 정리합니다.
2026-08-14 · 최초 발행 2025-12-28
새 작업을 즉시 경쟁시키지 않는 라운드로빈
Round Robin은 선점형 CPU 스케줄링에서 공평성과 응답성을 제공하지만, 새로 들어온 프로세스도 곧바로 같은 우선순위로 경쟁한다. 이미 대기한 프로세스의 상태나 완료 가능성을 반영하기 어렵고, 전체 처리량이나 완료 시간의 예측도 쉽지 않다.
Selfish Round Robin(SRR)은 Round Robin에 에이징을 더한 방식이다. 새 프로세스보다 기존 프로세스에 우선권을 주기 때문에 이런 이름이 붙었다. 핵심은 프로세스를 두 큐로 나누고, 대기 시간을 우선순위에 반영하는 데 있다.
Holding Queue에서 기다리고 Active Queue에서 실행한다
SRR은 보류 상태와 실행 대기 상태를 분리한다. 새 프로세스, 퀀텀이 끝난 프로세스, I/O를 마치고 돌아온 프로세스는 Holding Queue에 들어간다. 이곳에서 우선순위가 올라가며, 조건을 충족한 프로세스만 Active Queue로 이동한다.
Holding Queue는 에이징이 일어나는 영역이다. 일정 시간마다 우선순위가 높아지고, 오래 머무른 프로세스일수록 Active Queue에 들어갈 가능성이 커진다. 증가율 a는 시스템 파라미터로 조절한다.
Priority(t) = Priority(0) + a × WaitingTime
Priority(t): 시간 t에서의 우선순위Priority(0): 초기 우선순위 (일반적으로 0)a: 우선순위 증가율WaitingTime: Holding Queue에서 대기한 시간
Active Queue는 실제 CPU 할당 대상이 모이는 곳이다. 이 큐 안에서는 Round Robin 방식으로 실행 순서를 돌린다. CPU 스케줄러는 Active Queue에서만 프로세스를 선택하며, 진입 조건은 다음과 같다.
Holding Queue의 프로세스 우선순위 ≥ Active Queue의 최소 우선순위
시간 할당량이 만료되면 실행 중이던 프로세스는 다시 Holding Queue로 돌아간다. Active Queue에는 높은 우선순위를 확보한 프로세스만 남는다.
프로세스가 이동하는 경로
새 프로세스는 초기 우선순위 0으로 Holding Queue에 들어가 에이징을 시작한다. 우선순위가 조건에 닿으면 Active Queue로 옮겨지고 CPU 할당을 기다린다.
CPU를 받은 뒤에는 완료, I/O 요청, 퀀텀 만료 중 하나가 발생한다. 퀀텀이 끝난 프로세스는 Holding Queue로 복귀하며, 우선순위는 일반적으로 0으로 재설정된다. 이후 다시 에이징 과정을 거친다.
증가율과 시간 할당량이 바꾸는 동작
증가율 a는 새 프로세스가 Active Queue에 들어오는 속도를 결정한다. 값이 높으면 프로세스가 빠르게 성숙해 SRR은 Round Robin과 비슷한 성격을 띠고 공평성이 커진다. 값이 낮으면 Active Queue 진입이 느려지고, 기존 프로세스가 더 우대되어 처리량이 증가한다. 적절한 값은 워크로드 특성에 따라 달라진다.
시간 할당량도 함께 조정해야 한다. 큰 값은 문맥 교환을 줄이는 대신 응답시간을 늘리고, 작은 값은 응답성을 높이는 대신 오버헤드를 키운다. 일반적 범위는 10~100ms다.
초기 우선순위가 높으면 새 프로세스가 더 빨리 실행 기회를 얻고, 낮으면 기존 프로세스를 보호한다. 일반적으로는 0 또는 최소값을 사용한다.
대화형 시스템을 위한 설정 예시는 다음과 같다.
증가율(a) = 2.0
시간 할당량 = 20ms
임계값 = 10
이 설정은 빠른 응답성과 새 프로세스의 신속한 처리를 중시한다.
배치 시스템에서는 다음처럼 둘 수 있다.
증가율(a) = 0.5
시간 할당량 = 100ms
임계값 = 20
이 경우에는 처리량과 기존 프로세스의 완료를 우선한다.
실행 흐름으로 보는 SRR
다음 조건에서 P1, P2, P3의 실행을 살펴본다.
- 시간 할당량: 4ms
- 증가율(a): 1.0 (1ms당 우선순위 +1)
- Active Queue 진입 조건: 우선순위 ≥ 4
| 프로세스 | 도착시간 | 버스트시간 |
|---|---|---|
| P1 | 0 | 10 |
| P2 | 2 | 4 |
| P3 | 4 | 6 |
T=0ms에 P1이 도착해 Holding Queue에 들어간다. P1의 우선순위는 0이고, Active Queue는 비어 있다.
T=4ms에는 P1의 우선순위가 4에 도달해 Active Queue로 이동한다. P1은 첫 퀀텀을 실행한다.
T=8ms에는 P1의 퀀텀이 끝나 Holding Queue로 돌아간다. P2는 도착 후 6ms를 대기해 우선순위 6이 되었고 Active Queue로 들어가 실행된다. 이때 Holding Queue에는 우선순위 0으로 재설정된 P1이 있고, Active Queue에는 P2가 있다.
T=12ms에 P2가 끝난다. P1은 우선순위 4에 도달해 다시 Active Queue로 이동하고, 2ms 뒤 실행을 마친다.
T=14ms에는 P3의 우선순위가 10이 되어 Active Queue에 들어간다. P3는 실행을 시작하고 T=20ms에 완료된다. 이 시점에 모든 프로세스가 종료된다.
| 프로세스 | 반환시간 | 대기시간 | 응답시간 |
|---|---|---|---|
| P1 | 14 | 4 | 4 |
| P2 | 10 | 6 | 6 |
| P3 | 16 | 10 | 10 |
| 평균 | 13.3 | 6.7 | 6.7 |
같은 예제에서 Traditional RR과 비교하면 평균 대기시간은 SRR이 6.7, Traditional RR이 7.3이며, 평균 반환시간은 각각 13.3과 14.0이다.
| 지표 | SRR | Traditional RR |
|---|---|---|
| 평균 대기 | 6.7 | 7.3 |
| 평균 반환 | 13.3 | 14.0 |
효율성과 복잡성 사이의 선택
SRR은 오래 실행 중인 기존 프로세스의 완료를 우선해 문맥 교환 횟수를 줄이고 전체 처리량을 높일 수 있다. 에이징으로 모든 프로세스가 결국 실행 기회를 얻으므로 무한 대기를 막고 공평성도 유지한다. 대기시간을 기준으로 우선순위가 정해져 완료 시간의 추정과 시스템 동작 분석에도 도움이 된다.
대신 구현은 단순하지 않다. 두 큐를 관리해야 하고, 우선순위 계산과 관련 자료구조가 추가된다. 증가율 선택에 따라 성능이 크게 달라지며, 워크로드가 바뀌면 재조정이 필요하다.
새 프로세스는 즉시 실행되기 어렵다는 점도 고려해야 한다. 짧은 프로세스도 대기해야 하므로 대화형 시스템에서는 응답성이 문제가 될 수 있다.
변형할 수 있는 지점
Active Queue를 여러 우선순위 레벨로 나누고, 각 레벨에 다른 시간 할당량을 둘 수 있다. 이렇게 하면 스케줄링을 더 세밀하게 제어할 수 있다.
증가율을 시스템 부하에 맞춰 바꾸는 방식도 가능하다.
a(t) = base_rate × (1 + system_load)
이 방식에서는 시스템 부하에 따라 증가율을 동적으로 조정한다. 높은 부하에서는 더 빠른 진입을 유도해 효율성과 응답성의 균형을 맞춘다.
I/O 중심 프로세스에는 I/O 완료 뒤 높은 초기 우선순위를 주는 방법도 있다. CPU 버스트가 짧은 프로세스가 빠르게 진입하도록 하여 시스템 전체 처리량 향상을 노린다.
적용 환경을 가르는 조건
혼합 워크로드, 다양한 실행 시간 분포, 예측 가능한 성능이 필요한 중간 규모 시스템은 SRR을 고려할 수 있다. CPU 중심 프로세스와 I/O 중심 프로세스가 공존하고, 큐 관리 오버헤드와 파라미터 튜닝을 감당할 수 있는 환경이 해당한다. 장시간 작업의 완료와 처리량을 우선하는 배치 처리 시스템도 대상이 된다.
반대로 실시간 시스템은 데드라인 보장이 어렵고 예측 가능성이 부족해 우선순위 스케줄링이 더 적합하다. 새 프로세스의 즉각적인 응답이 중요한 대화형 시스템은 전통적 RR이 나을 수 있다. 초고부하 환경에서는 큐 관리 오버헤드와 확장성 문제가 생길 수 있어 더 단순한 알고리즘을 검토해야 한다.