[OS] Proportional Share (비례 배분)

반응 시간과 반환시간만 중요하냐 ?
내 몫의 CPU 시간은 잘 쓰이고 있는가 ?

각 프로세스 지분(Share)에 따라 CPU 시간을 배분한다.

Lottery 스케줄링

티켓 이라는 개념이 도입됨
프로세스가 받아야 할 자원의 지분을 표시

보유한 추첨권 75/25에 따라 CPU 사용권을 확률로 추첨받음

추첨권을 다루는 기법

1. 추첨권 화폐 (Ticket Currency)
   각 사용자는 자신의 화폐 가치로, 각 작업에 추첨권을 할당
   시스템이 전역 화폐 가치로 변환됨
2. 추첨권 양도 (Ticket Transfer)
   일시적으로 다른 작업에게 추첨권을 양도함
   클라이언트-서버 환경에서 유리한 작업
3. 추첨권 팽창 (Ticket Inflaction)
   자신이 소유한 추첨권 수를 늘리거나 줄일 수 있음

💡 priority inversion 이란 : 우선순위가 낮은 프로세스가 작업을 하다가 공유변수 lock을 걸었다고 가정해보자. 이 상황에서 우선순위가 낮은 프로세스가 시간이 다 되서 unlock을 하지 않고 양도 당했다면 더 높은 우선순위가 실행중 공유변수를 사용한다면 cpu를 포기하고 대기를 해야한다. 따라서 우선순위가 그 다음으로 낮은 프로세스가 실행되는 우선권 역전의 현상이 생기게 된다.

추첨권 양도는 priority inversion을 해결하기 위해 추첨권을 lock을 걸은
프로세스에게 양도한다.
그리고 공유 변수 작업을 끝내도록 한다. 추첨권 팽창 또한 같은 원리이다.

• 추첨권 팽창은 프로세스들이 협력적인 환경 경쟁하지 않은 환경에서야 가능

구현

만약 랜덤 값이 300이 나왔다면,

1. A 패스, count += 100 (A 티켓 범위)
2. B 패스, count += 50 (B 티겟 범위, 150)
3. C 구간에 300이 위치함 C가 당첨

불공정성 (U)

U = 일찍 끝난 작업 시간 / 늦게 끝난 작업 시간

1에 수렴할 수록 공정성이 증가함

작업이 길어질 수록 공정성이 증가함

Lottery 스케줄링 장단점

장점

• 평균 성능이 우수함
• 필요 정보량은 최소
• 빠르다

단점

1. 프로세스 길이가 너무 짧은 경우
   불공정이 증가함
2. 비 결정적임 (랜덤)

비 결정적(무작위)이라면 스케줄러를 단순하게 만들 수 있지만,

정확한 비율을 보장할 수 없음

Stride 스케줄링

보폭 = 임의의 큰 수 / 각 프로세스의 추첨권 수
보폭은 CPU를 많이 쓸 권한

보폭이 작을 수록 CPU 많이 사용할 수 있게 Pass 시스템 도입

• 보폭

  : 추첨권 비율의 역수
  추첨권과 반비례

• Pass

  CPU 사용할 때마다 보폭 값이 증가함

  보폭이 작을 수록 CPU를 많이 쓸 권한을 얻음

스케줄러는 가장 작은 Pass 값을 가진 작업을 선택함

→ 자기 지분을 제일 적게 소비한 작업이 선택

티켓이 많을 수록 보폭은 작음 (반비례)

Pass 값은 CPU 사용마다 += 보폭

Pass 값이 가장 작은 작업이 스케줄러에 의해 선택됨

3개의 Pass 값이 있을 때, 스케줄러는 항상 Pass 값이 작은 애를 선택함

선택당한 Pass는 ‘+= 보폭’

만약 새로운 프로세스가 진입한다면?

D 프로세스의 Pass 값이 150이라면 ?

→ 0을 주면 안됨. 현재까지 수행된 프로세스 중 가장 작은 Pass 값 제공

정리

비례 배분

• 공정성 ?

  → 자신의 CPU 할당량을 잘 쓰자

• 비 결정적: 무작위 수에 의한 추첨 스케줄링 = 로터리 스케줄링

• 결정적: 추첨권 수에 의한 보폭 스케줄링 = Stride 스케줄링

스케줄링으로는 부적합함

→ Share 정의와 할당 방식이 불분명함