[xv6] 실습1 : Lottery scheduler 설계

---

실습 목표:

xv6운영체제에 Lottery scheduler를 추가하고, 3개의 프로세스를 실행하여 스케줄링 상태를 체크한다. 

xv6운영체제는 기본적으로 round robin 스케줄링 방식을 갖는다. 

 

---

lottery scheduler란?

랜덤의 티켓 번호를 뽑고, 그 티켓을 갖고있는 프로세스가 time slice를 갖고 실행되게 된다.

각 프로세스가 갖는 티켓의 배분의 양으로 그 프로세스가 갖는 priority를 정할 수 있다.

 

즉 랜덤으로 프로세스의 실행시간을 정해주는 공정한(?) 스케줄러라고 할 수 있다. 

기

 

---

실습 :

기본으로 주어진 

핵심적인 수정사항은 아래와 같다.

 

 proc.c 수정

 

1. settickets와 getpinfo 함수 설정

 

 

- 두가지 함수를 proc.c 소스에 추가시켜준다.  - setticket 함수는 각 프로세스가 티켓을 할당 받게해주는 함수로 단순히 매개변수로 받은 number를 프로세스 구조체의 티켓에 할당해준다.  - getpinfo 함수는 프로세스의 정보들을 불러오는 함수이다. 프로세스들의 정보를 저장하는 pstat에 for문을 이용해 ptable에 존재하는 모든 프로세스의 사용여부, process id, tickets 수, 그리고 ticks를 불러와 저장한다

 

2. scheduler함수 수정 

random 함수는 커스텀 함수로, 모든 프로세스의 ticket의 합을 나타낸다. 그리고, 총합 이하의 랜덤수를 우승자 값으로 뽑는다.

count는 각 티켓값을 더하면서 Winner가 있는 구간을 찾는다. 시나리오를 설명하자면 만약 A,B 프로세스가 있고, 각각 티켓을 100, 100씩 할당받았다면 sumticket은 200이된다. winner값은 0~200 값중하나가 되고, 만약 50이 됬다고 한다. 각 프로세스별로 for문을 돌며, count에 티켓값을 더한다.  A가 돌때는 100이된다. 근데 winner는 50이므로 count값보다 작으므로 우승자가 된다.  이때의 프로세스가 스케줄링 되어 Running 상태가 되고 진행한 ticks값을 저장한다.

 

테스트 코드의 일부는 아래와 같다. 

3개의 프로세스를 fork 함수를 통해 만들고(두개의 자식 프로세스) settickets함수를 통해 각 프로세스에게 200, 100, 300의 티켓을 배분한다.  이럼 계산상 당첨확률이 3:2:1이 되므로 예측상 실행시간이 3:2:1이 될것이다. 확인해보자

 

결과는 위처럼 나왔으며, 위 결과를 계산기를 통해 비율로 계산해보면

3.04 : 1.99 : 1 비율로 나눠준 티켓비율과 거의 일치함을 확인할 수 있었다.

 

---

고찰:

스케줄링는 보통 비례배분 /  공정배분으로 나눠질 수 있는데

우리가 잘알고, 수정전의 xv6에서의 스케줄러인 라운드로빈은 공정배분의 대표적인 예시이다. 

공정배분 스케줄링은 모든 프로세스나 작업이 동일한 자원을 받을 수 있도록 하는 것을 목표로 한다.

 

비례배분의 경우, 프로세스나 작업이 더 많은 자원을 요구할 때, 그 요구에 비례하여 자원을 할당하는 방식이다.

우리가 더 중요시한 프로세스에게 티켓수를 더 주어 그에 비례해 스케줄링한것을 예시로 들면 될것이다. 

 

 

추가 공부 : 리눅스 스케줄링 CFS

리눅스의 스케줄링 방식은 CFS(Completely Fair Scheduler)는 CFS는 공정성을 극대화하기 위해 설계된 스케줄러로, 각 프로세스가 동일한 CPU 시간을 받도록 하는 것을 목표로 한다. 이 스케줄러는 각 프로세스가 실행된 시간을 기록하고, 이를 기준으로 프로세스가 '공정하게' CPU를 사용할 수 있도록 조정한다.  

즉 공정배분 스케줄링이라고 보면 될듯하다. 

 

그렇지만 모든 프로세스가 동일한 것은 아니고 프로세스 우선순위도 고려하여, 우선순위가 높은 프로세스가 더 자주 CPU를 사용할 수 있다.

 

몇가지 특징은:

1. 선점형이라 현재 실행중인거 강제로 종료 가능

2. 가상 런타임: 실제로 사용한 CPU시간 기반 런타임을 기록해, 가장 적은 프로세스 선택해 할당해 주는 방식