비례배분(Proportional Share) 스케줄러
공정배분(fair share)이라고도 불리는 비례배분 스케줄러는 프로세스별로 CPU에 대한 지분을 나눠 배분하고, 각자의 지분에 맞게 자원을 할당해줘 작업을 처리시키는 스케줄러이다.
비례배분 스케줄링에서 가장 기본적이고 근간이 되는 개념은 결국 프로세스별로 지니고 있는 CPU 지분률(추첨권-ticket)이다.
스케줄러는 이 지분이라는 개념을 이용해 다음으로 작업할 프로세스를 결정하는 것뿐만 아니라, 더 나아가 전체 작업의 흐름을 조절하기도하는등 여러가지 응용 기법들을 발휘하기도 한다.
지분을 이용하는 대표적인 응용 기법은 3가지 정도 존재한다.
이 응용기법에 대해서 간단히 한 번 알아보자면 먼저 추첨권 화폐(Ticket Currency)라는 기법이 있다.
이 기법은 프로세스가 자신이 가진 지분을 새로운 시드로하여 자신만의 개별적인 지분영역을 만들고, 이 영역안에 포함된 하위 프로세스(자식)들에게 지분을 다시 나누어주는 식의 행위를 가능케하는 기법이다.
두번째로는 추첨권 양도 기법(Ticket Transfer)이 존재한다. 이 기법은 특정 프로세스의 작업을 밀어주기 위해 프로세스가 아예 자신의 지분을 다른 프로세스에게 대여해주는 식의 행위같은 것을 가능케 하는 기법이다.
이러한 추첨권 양도의 방식은 클라이언트/서버 식으로 설계된 환경에서 특히 유효한데, 주기적으로 서버의 응답(리턴값)을 기다리면서 자신의 작업을 진행해 나가야하는 클라이언트 프로세스는 기다리는 동안 자신이 지니고 있는 지분권을 서버 프로세스에게 넘겨주어 더 빠르게 응답을 받고자 하는식으로 행동한다.
추첨권 팽창(Ticket Inflation) 이라는 기법도 있다. 해당 기법에서는 심지어 특정 프로세스가 자신의 지분을 독단적으로 팽창시키고 임의적으로 CPU의 할당을 가로채는 식의 행위를 벌인다.
이와 같이 비례배분 스케줄링은 지분이라는 개념을 이용하여 스케줄 정책을 실시한다.
이러한 비례배분 스케줄러는 정확히 어떠한 방법으로 다음 작업 프로세스를 결정할 것인지(정확히 어떠한 방법을 이용해 지분에 비례한 작업분배를 이뤄낼 것인지), 그 구체적인 방법에 따라 비결정론식 방법과 결정론식 방법 크게 2가지 방식으로 구분 지어 볼 수 있다.
비결정론식 방법
비결정론식 방법은 스케줄러가 다음으로 실행할 프로세스를 직접 결정짓지 않고 랜덤으로 뽑은 난수를 통해 선택을 결정하는 방법이다.
결국 확률에 의존하여 다음 프로세스를 실행하겠다는 것인데, 지분을 많이 가지고 있는 프로세스는 그렇지 않은 프로세스에 비해 더 많은 기회를 부여해 더 자주 뽑히게끔 하는 방식이다.
이러한 무작위 추첨방식은 결정론적 방법에 비하여 다음 프로세스를 결정하는데 있어 관리해야 할 정보가 매우 적기때문에 상대적으로 가볍게 구현이 가능하다는 장점이 있다.
하지만 무작위 추첨의 특성때문에 각 프로세스들이 보유하고 있는 지분만큼 완벽하게 비례된 작업을 할당해 주는 것을 보장할 수 없다는 단점 또한 존재한다.
(이같은 할당 오차는 전체 스케줄 시간이 충분하지 않은 상황이라면 더욱 더 커지게 된다. 하지만 스케줄 작업 시간을 충분히 확보한다면 점점 지분에 비례하는 방향으로 오차가 적어진다)
결정론식 방법
결정론식 방법을 이용하는 비례 배분 스케줄러는 다음으로 진행할 작업 프로세스를 정해진 규칙에 따라 선택한다.
무작위 추첨방식과는 다르게 확실하게 정해진 규칙이 존재한다는 것은 다음으로 실행할 프로세스가 분명히 결정되어 있다는 것을 뜻한다. (정해진 상황에서 늘 정해진 프로세스만 실행된다)
코드로 보는 결정론적 방법의 진행과정 (보폭 스케줄링)
curr = select_min(queue); // pass값이 최소인 프로세스를 큐에서 선택한다 schedule(curr); // 선택한 프로세스의 작업을 정해진 타임 퀀텀만큼 진행시킨다 curr->pass += curr->stride; // 해당 프로세스의 pass 값을 보폭만큼 증가시킨다 insert(queue, curr); // 작업이 완료된 프로세스를 다시 큐에 넣는다
결정론적 비례 배분 스케줄링의 대표적인 예인 보폭 스케줄링(stride scheduling)은 다음 작업을 결정하는데 있어 보폭(stride)과 Pass라는 개념을 이용한다.
보폭은 프로세스의 지분비율과 반비례적인 관계를 갖는 값으로, 모든 프로세스가 자신이 지닌 지분비율에 따라 제각기의 보폭을 갖는다. 그리고 Pass는 모든 프로세스가 지니고 있는 상태 정보로 초기값은 0이다.
보폭 스케줄링의 기본 원리는, 스케줄에 등록된 프로세스들 중에 Pass 값이 가장 작은 것을 뽑아 다음 작업으로 선택하는 것인데, 이 Pass 값은 작업이 한번 완료될때마다 프로세스가 지닌 보폭의 크기만큼 증가된다.
결국 지분이 커서 역으로 적은 양의 보폭 값이 설정된 프로세스들은 작업 이후 Pass값 변동률이 상대적으로 작기때문에 자연스럽게 스케줄러에게 더 많은 선택을 받게 된다는 로직이다.
이렇게 결정론식 방식을 따르는 스케줄러는 Pass와 같은 상태정보 값을 프로세스 별로 유지하며 관리해야하기 때문에 무작위 추첨방식보다는 좀 더 많은 자원을 소모하게 된다.
게다가 작업 도중 새롭게 추가되는 신생 프로세스들의 Pass값을 처리해주어야한다는 골치 아픈 문제도 존재한다.
만약 새로 태어난 프로세스의 Pass값을 그냥 0으로 두게 된다면 당분간 이 신생 프로세스가 CPU를 독점해버리는 식으로 스케줄링이 돌아갈 것이기 때문에 결국 이에 대한 세부적인 정책도 생각해주어야 한다.
리눅스의 CFS(Completely Fair Scheduler)
리눅스에서 기본 스케줄러로 채용하고 있는 CFS는 비례배분(공정배분)으로 설계된 스케줄러이다.
CFS는 독특하게도 지금까지 본 일반적인 스케줄러와 달리 고정된 타임 슬라이스값을 사용하지 않는다.
그 대신 sched_latency와 min_granularity와 같은 내부시스템변수를 사용하여 상황에 맞게 동적으로 타임슬라이스 값을 조정한다.
(타임슬라이스 값이 너무 잘게 쪼개지면 빈번한 컨텍스트 스위칭으로 인한 오버헤드가 성능저하 이슈를 일으키게 되고 그렇다고 너무 늘리면 전체 작업의 공정성이 악화된다. 따라서 CFS는 현재 스케줄에 등록된 전체 프로세스의 양을 바탕으로 적절한 타임슬라이스 값을 계산한다)
CFS가 스케줄을 처리하는 그 원리는 결정론식 비례 배분 스케줄러인 보폭 스케줄링과 그 느낌이 얼추 비슷하다.
보폭 스케줄링이 Pass값을 계산하여 다음 작업 프로세스를 결정했듯이 CFS도 vruntime이라는 것을 이용해 작업 프로세스를 결정한다. (결국 CFS도 결정론식이다)
vruntime은 프로세스가 지금까지 CPU를 이용한 그 시간을 기록하여 보관하고 있는 상태정보 값으로 이 vruntime이 가장 낮은 프로세스가 다음 작업대상으로 스케줄러에게 채택되는 방식이다.
CFS는 각 프로세스를 vruntime 값을 key로하여 이진탐색트리(Red-Black Tree)에 저장해놓았는데, 이것은 이진탐색을 이용해 가장 낮은 프로세스를 O(lonN)의 시간복잡도로 빠르게 찾아내겠다는 것을 의미한다.
(이때 sleep 상태의 프로세스들은 트리에서 제거되어 다른 곳에 따로 보관된다. 이것은 불필요한 프로세스들이 트리에서 자리를 차지하는 것을 방지해 효율적인 자료검색을 가능케 한다)
또한 보폭 스케줄러가 가지고 있던 문제점중 하나였던 신규 프로세스의 Pass값 처리 문제같은 경우, CFS는 신규 프로세스는 현재 트리에서 가장 낮은 vruntime값을 가지고 태어나게하는 식으로 문제를 해결하였다.
더 알아둘만한 것
CFS의 가중치 -> CFS도 가중치(Niceness)라는 개념을 이용하여 사용자나 관리자가 프로세스의 우선 순위를 조정할 수 있도록 하는 지분 배분 기능을 구현해 놓았다. nice값에 설정된 가중치를 sched_latency와 연산하면 프로세스에게 할당될 실질적인 타임 슬라이스 값이 결정되어진다. 이때 vruntime 또한 nice값에 맞게 적절히 동기화되어 계산되는데 지분이 높은(가중치가 높은) 프로세스의 vruntime은 그렇지 못한 프로세브보다 느리게 흘러가는 구조이다.
