운영체제 scheduling proportional share

앞에서 살펴본 mlfq 같은 경우에는 performance 와 fair 중에서 perfomance 에 집중한다고 할 수 있다.

 

이번에는 fair에 집중해 보자, 

 

fair인 공정함에 초점을 맞춘 proportional share 비례배분이 있다. 

 

이는 비율을 지켜서 그에 따라서 cpu 를 실행하는 것인데, 그러한 스케줄의 예로는 lottery scheduling 이 있다. 

 

이는 각각의 프로세스에 ticket 을 배부한 후에 랜덤으로 수를 뽑아서 그 티켓을 가지고 있는 프로세스를 실행하는 방법이다.

 

이때, 티켓을 배부 할 때에, 비율에 맞추어서 티켓의 개수를 정해서 배부한다. 

 

이 lottery scheduling 에는 여러 메커니즘이 있는데, 

 

1. ticket currency

 - 프로세스 안에서 지역 화폐를 발행하더라도 global 적으로 티켓의 분배를 해야한다.

2. ticket transfer

 - 급하게 빠르게 처리할 프로세스가 있으면 티켓을 빌려준다.

3. ticket inflation

 - 일시적으로 빠르게 처리할 일 이 있으면 티켓을 더 발행해서 실행 확률을 높인다.

(이때에는 각 프로세스 끼리릐 신뢰간계가 있어야 한다)

 

lottery 의 이점은 굉장희 유연하게 프로세스를 추가하고, 삭제할 수 있다.

 

하지만, random한 요소에 의존하기 때문에, 계속 같은 결과를 낼 수 없다. 

 

따라서 계속 일정한 결과를 낼 수 있도록 바꾼것이 stride scheduling 이다. 

 

stride 는 보폭이라는 뜻으로 얼마나 실행하였는지를 판단하여 배분한다. 이 보폭은 전체 티켓을 가지고 있는 티켓으로 나누어서 구한다. 

 

이때의 쟁점은 중간에 프로세스가 추가 되었을 때에 초기 값을 무엇을 주어야 하는지다.

 

그 이유는 만약에 0 을 주게 된다면, 초반에는 계속 새로들어온 프로세스만이 실행 될 것이기 때문이다. 

 

따라서 voo-doo 아주 잘 요령 껏 정해야 한다는 문제가 있다.

 

----------------------------------------------------------------------------------------------------------------------

 

cfs 

 

이는 linux 에서 사용하고 있는 방식으로 stride 방식에서 진화한 방식이다. 

 

여기서는 stride 방식의 pass 를 virtual run time 이라고 한다. 

 

그리고 이 방식의 특징은 프로세스를 넘길때에 time out interrupt 를 거는데, 이 시간 설정을 프로세스가 시작할 때 해준다는 것이다.

 

그런데 이 시간을 정하는 방식을 처음에는 n 등분으로 나누었었는대, 이에 가중치를 준다.

 

그리고 보폭값 또한 가중치를 주어서 설정한다. 

 

그리고 이때의 프로세스들이 저장되어있는 자료구조는 트리의 형식이다. 

 

그 이유는 삭제와 삽입을 할 때에 트리가 다른 리스트 등의 자료구조보다 빠르기 때문이다.

 

그리고 이 방식에서는 중간에 프로세스가 삽입 될 때에 그때의 값들, 다른 프로세스들의 pass 값들 중에서 가장 작은 값으로 맞추어 준다.