스케줄링: 비례 배분 (Proportional Share Scheduling)
비례 배분 스케줄링은 CPU 시간을 여러 프로세스에 정해진 비율로 공정하게 나누어 주는 것을 목표로 합니다. 기존 알고리즘들이 응답 시간이나 반환 시간 최적화에 초점을 맞췄다면, 비례 배분은 각 프로세스가 지정된 비율만큼의 CPU 시간을 확보하도록 설계됩니다.
1. 기본 개념: 추첨권(Ticket)
각 프로세스는 자신이 받을 CPU 점유율만큼 추첨권(ticket)을 부여받습니다. 스케줄러는 매번 하나의 추첨권을 무작위로 뽑고, 해당 추첨권을 가진 프로세스에 CPU를 할당합니다.
예시:
- 프로세스 A: 추첨권 80장 → CPU 시간 80%
- 프로세스 B: 추첨권 20장 → CPU 시간 20%
장기적으로는 A가 80%, B가 20%의 CPU를 점유하게 됩니다.
추첨권 = CPU 시간 배분 비율을 나타내는 화폐 같은 개념
2. Lottery Scheduling (추첨 스케줄링)
가장 대표적인 비례 배분 알고리즘으로, 무작위성(Randomness)을 활용해 간단하고 공정한 배분을 실현합니다.
특징
- 공평성: 추첨권 수에 비례해 공정하게 CPU를 할당.
- 유연성: 추첨권 수를 조정해 우선순위를 쉽게 변경 가능.
- 확장성: 새로운 프로세스가 추가되어도 추첨권만 추가하면 됨.
장점
- 구현이 간단하고 직관적.
- 새로운 작업 추가가 쉽다.
- 특정 패턴의 작업 부하에서 좋은 성능을 보일 수 있다.
단점
- 무작위성으로 인해 단기적으로는 불균형 가능.
- 추첨 수행에 따른 연산 오버헤드.
동작 단계
- 각 프로세스에 추첨권 할당 (중요도 비례)
- 총 추첨권 수 합계 계산
- 무작위 번호 추첨 (0 ~ 총합-1)
- 당첨된 프로세스에 CPU 할당
- 반복
예시
| 프로세스 | 티켓 수 | CPU 시간 |
|---|---|---|
| A | 4 | 200ms |
| B | 2 | 100ms |
| C | 1 | 50ms |
총 티켓 수 = 7
0~3 → A 선택, 4~5 → B 선택, 6 → C 선택
3. Stride Scheduling (보폭 스케줄링)
Lottery Scheduling의 무작위성 한계를 극복하기 위해 등장한 결정론적(Deterministic) 알고리즘입니다.
동작 방식
- 각 프로세스는 Stride(보폭) 값을 가짐 → CPU 점유율의 역수에 비례.
- CPU 사용 시 Pass 값을 Stride만큼 증가.
- 가장 작은 Pass 값을 가진 프로세스가 다음에 실행.
즉, 무작위가 아닌 정확한 비율로 CPU를 배분합니다.
비교
| Lottery | Stride | |
|---|---|---|
| 무작위성 | O | X (결정론적) |
| 구현 난이도 | 간단 | 복잡 |
| 정확성 | 근사적 공정성 | 정확한 비례 배분 |
4. Lottery vs Stride
- Lottery Scheduling → 무작위성으로 단기 불균형 가능하지만 구현 간단, 새 작업 추가 쉬움.
- Stride Scheduling → 완벽한 비례 배분 보장하지만 새 작업 도착 시 Pass 초기값 관리가 까다로움, 매우 작은 비율을 표현하려면 BIG_NUMBER가 커져야 하므로 오버플로우 가능성이 있음
5. 정리
- 비례 배분 스케줄링 = 자원을 비율대로 공정하게 분배
- Lottery Scheduling → 무작위성 기반, 간단하고 유연함
- Stride Scheduling → 정확하고 결정론적이지만 구현 복잡
- 네트워크, 디스크 I/O 등 다양한 자원 관리에 확장 가능
"무작위성이 항상 완벽하지는 않지만, 장기적으로는 공정성과 간단함을 제공한다."