[운영체제] 스케줄링 : 비례 배분

비례 배분이란?

공정성을 생각해서

비례 배분 스케줄러가 등장하였다.

Lottery Scheduling

프로세스가 받아야 할 자원의 지분 표시

- 전체 추첨권(ticket) 대비 자기 추첨권의 비율로 표시

그리고 추첨권을 랜덤으로 뽑아서 해당 추첨권을 가지고 있는 프로세스를 실행!

Ticket Mechanism

추첨권 화폐
- 각 사용자는 자신의 화폐 기준으로 각 작업에 추첨권 할당하고
-> 시스템은 사용자 화폐를 글로벌 화폐로 반환한다.

위 예시는 아마 UserA와 UserB 의 우선순위를 동일하게 봐서 그런거 같다

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

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

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

추첨권의 불공정성

작업의 갯수가 높아질 수록 왜 공정해지냐면
확률의 수렴과 관련있다.
갯수가 많아지면 랜덤 선택의 확률이 같아지기 때문이다.

프로세스가 너무 짧을 경우 불공정하다는 단점
그리고 비결정적이다는 점 또한 단점이다
패턴을 예측하기 어렵기 때문

이런 non deterministic 한 알고리즘은 왜 사용할까?

Lottery scheduling 은 MLFQ에 비해서 가볍고 구현이 쉽다는 장점이있다.

MLFQ 는 작업의 상태 또한 저장하고 관리해야한다.
구현도 어렵고

그래서 Lottery scheduling은 이러한 점에서 매력이 있다.

Deterministic 한 알고리즘으로?

Stride Scheduling

Lottery 와 반비례하는 보폭이라는 개념이 도입

솔직히 stride 할바엔 다르게..

잘 사용되지는 않지만

Proportional Share 의 개념은
활용될 수 있다.