Proportional Share (비례 배분)
공정 배분 (Fair Share) 각 작업(프로세스 또는 사용자)에 사전에 정한 비율만큼 CPU 시간을 보장
특정 비율로 CPU를 배분하는 스케줄러 프로세스 A : B = 2 : 1 이렇게 비율로 CPU를 배분한다.
실행 시간, 응답성 등 보다 자원 할당 비율 보장이 중심이다.
Turnaround Time / Response Time 등을 최적화하며 CPU를 각 작업에 일정 비율로 할당 성능 최적화보다는 공정성에 중심
Lottery Scheduling
비례 배분 스케줄링
핵심 아이디어:
CPU 시간을 **복권(lottery)**처럼 배분
각 프로세스는 **티켓(ticket)**을 가짐
스케줄링 시 무작위로 티켓 하나를 뽑고, 해당 티켓을 가진 프로세스가 CPU를 획득
티켓 수 ∝ CPU 지분
→ 티켓이 많을수록 CPU를 받을 확률이 높음
기본 개념
- 티켓 : 진짜 티켓. 추첨권 프로세스가 소유한 티켓의 수와 전체 티켓에 대한 비율 : 자신의 몫
확률적 스케줄링이다.
ex) A : 75장의 티켓 : 75%의 CPU를 할당 B : 25장의 티켓 : 25%의 CPU를 할당
Lottery Scheduling : Time Quantum이 끝날 때마다 확률적으로 티켓을 선택한다.
A : 074
B : 7599
스케줄러는 티켓 (0~99)중 하나 선택
대수의 법칙에 의해 두 프로세스가 오랫동안 실행된다면, 그 비율이 75 : 25에 가까워진다.
Ticket Currency
여러 사용자가 여러 작업을 가질 때를 위한 티켓 환산 시스템
여러 사용자가 각자의 기준으로 자신들의 프로세스에 티켓을 할당함. User A : A1 프로세스, A2 프로세스에 각각 500장씩 티켓 할당
User B : B1 프로세스 한 개에 10장 티켓 할당
이때 User A, B가 자체적으로 할당한 티켓은 로컬 티켓이다. 자신의 환경 안에서 의미가 있는 수치이다.
하나의 자원을 User A,B가 사용한다면?
Ticket Currency에 위해 그 비율이 맞춰진다.
시스템은 각 사용자에게 글로벌 티켓을 할당한다. User A,B의 글로벌 티켓은 각각 100장 할당한다.
이때 시스템은, User A의 A1, A2 의 티켓은 각 500장 -> 50장 / 총 100장 User B의 B1 티켓은 10장 -> 100장
으로 로컬 티켓을 글로벌 티켓으로 조정하여 공정성을 이룬다.
Ticket Transfer
한 프로세스가 자신이 가진 ticket을 다른 프로세스에게 일시적으로 빌려주는 것
*작업 수행 중에만 임시 이전
클라이언트–서버 구조에서 유용한데,
문제 상황 (Ticket Transfer가 없을 때)
- 클라이언트가 서버에 요청
- 서버가 CPU를 잘 못 받아서 처리가 지연
- 결과적으로 우선순위 높은 클라이언트도 느려짐
Ticket Transfer 동작
- 클라이언트가 서버에 작업 요청
- 클라이언트의 ticket이 서버로 임시 전송
- 서버는 높은 ticket을 가지고 CPU를 더 많이 획득
- 작업 완료
- ticket이 다시 클라이언트에게 반환
Ticket Inflation
프로세스가 자기 ticket 수를 일시적으로 늘리거나 줄일 수 있음
특정 프로세스가 실행 구간에 따라 cpu작업을 많이 요구하는 경우가 있어서
- 평소: 100 tickets
- 특정 구간: 500 tickets
- 작업 종료 후 다시 100으로 복귀
등으로 조절에 용이하다
다만, 프로세스 간 상호 신뢰가 없으면 불가능하다.
악의적인 프로세스가 ticket을 계속 무한히 늘리면 CPU를 독점 가능하기 때문
욕심 많은 프로세스가 cpu를 점유하고자 많은 양의 ticket을 자신에게 할당하는 시스템 즉, 서로 신뢰할 수 없는 프로세스들이 경쟁하는 시스템에 적용은 불가능하다.
구현
ticket 스케줄링은 구현이 간단하다.
linked list로 각 프로세스의 티켓 보유수를 저장할 수 있고, 난수에 의해 170등의 수가 나오면, linked list의 head부터 순회하며 해당 프로세스를 찾을 수 있다.