운영체제 7. 스케줄링 : 비례 배분 (Proportional Share) 스케줄러, 공정 배분(fair share) 스케줄러

7. 스케줄링 : 비례 배분 (Proportional Share) 스케줄러, 공정 배분(fair share) 스케줄러

• 반환 시간이나 응답시간을 최적화 하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.
• 비례 배분 스케줄링의 좋은예로 추첨 스케줄링(lottery scheduling)이 있다. 기본 아이디어는 다음 실행될 프로세스를 추첨을 통해 결정하고 더 자주 수행되어야 할 프로세스는 당첨기회를 더 많이 주는 것이다.

7.1 기본 개념 : 추첨권이 당신의 지분이다.

• 추첨권(티켓)이라는 기본적인 개념이 추첨 스케줄링의 근간을 이룬다. 추첨권은 경품권의 개념과 유사하다.
• 추첨권은 특정 자원에 대한 프로세스에게(또는 사용자 또는 그 무엇이든) 할당될 몫(지분)을 나타낸다. 프로세스가 소유한 티켓 개수와 전체 티켓 간의 비율이 자신의 몫이다.

무작위성의 이용

• 추첨권 스케줄링의 큰 장점 중 하나는 무작위성이다.
• 무작위 방식은 전통적인 결정 방식에 비해 세 가지 장점이 있다.
  • 첫째, 무작위 추첨 방식은 전통적인 방식이 잘 해결하지 못하는 특이상황을 잘 대응한다.
  • 둘째, 무작위 추첨 방식은 매우 가볍다. 관리해야 할 상태정보가 거의 없기 때문이다.
  • 셋째, 무작위 추첨 방식은 매우 빠르다. 난수 발생 시간이 빠르기만 하면 결정 역시 빠르게 되고, 따라서 속도가 요구되는 많은 경우 사용될 수 있다.
• 무작위성은 원하는 비율을 정확히 보장하지는 않는다. 하지만, 두 작업이 장시간 실행될수록, 원하는 비율을 달성하는 가능성이 높아진다.

7.2 추첨 기법

추첨권 화폐(ticket currency)

• 사용자가 추첨권을 자신의 화폐가치로 자유롭게 할당할 수 있도록 허용한다. 시스템은 자동적으로 화폐가치를 변환한다.

추첨권 양도(ticket transfer)

• 양도를 통하여 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다.

추첨권 팽창(ticket inflation)

• 프로세스는 일시적으로 자신이 추첨권의 수를 늘이거나 줄일 수 있다. 물론 서로 신뢰하지 않는 프로세스들이 상호경쟁하는 시나리오에서는 의미가 없다.

7.3 구현

• 추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 점이다. 필요한 것은 난수 발생기와 프로세스들의 집합을 표현하는 자료구조, 추첨권의 전체 개수 뿐이다.

7.4 리눅스 CFS (Completely Fair Scheduler)

• 현재 리눅스는 기존과는 다른 방식으로 공정 배분 스케줄링을 구현했다. 이 스케줄러의 장점은 효율성과 확장성이다. 효율성을 위해, CFS는 최적의 내부 설계와 자료구조 사용을 통해, 스케줄링 결정을 매우 신속히 수행한다.

기본연산

• 대부분의 기존 스케줄러들은 고정된 길이의 타임 슬라이스를 사용한다. CFS는 이 점에서 기존 스케줄러와 다르다. CFS는 모든 프로세스들에게 CPU를 공평하게 배분하는 것을 목표로 한다. virtual runtime(vruntime)이라는 간단한 counting 기반 테크닉을 사용한다.
• 프로세서가 실행되서, 스케줄러는 해당 프로세서의 vruntime값을 누적시킨다. 가장 기본적인 경우, 각 프로세스의 vruntime은 실제 시간과 같은 속도로 증가한다. 스케줄링시 CFS는 가장 낮은 vruntime을 가진 프로세스를 다음에 실행할 프로세스로 선택한다.
• CFS가 자주 실행되면, 각 프로세스가 작은 시간 간격으로 CPU를 사용하게 되어 공정성이 좋아진다. 하지만, 많은 문맥교환이 발생하여 전체 시스템 성능에 악영향을 미칠 수 있다. 드물게 CFS가 실행되면, 문맥교환 횟수가 감소하여 전체 시스템 성능은 향상되지만, 공정성은 악화된다.
• CFS는 주기적으로 발생하는 타이머 인터럽트에 근간하여 작동한다. 즉 CFS는 특정시간 간격으로만 스케줄링 결정을 내릴 수 있다. 타이머 인터럽트는 짧은 간격으로 발생하여, CFS는 현재 작업의 타임 슬라이스 소진 여부를 판단한다.

가중치(Niceness)

• CFS는 사용자나 관리자가 프로세스의 우선 순위를 조정하여 다른 프로세스들 보다 더 많은 CPU시간을 할당받게 할 수 있다. 티켓이 아닌 프로세스의 nice 레벨이라는 고전적 UNIX 메커니즘을 사용한다. nice는 0을 기본 값으로 갖고 -20부터 19까지 가능하다 nice가 양수 값이면 낮은 우선순위를 의미하고 음수 값이면 높은 우선순위를 의미한다. 너무 친절하면 관심을 많이 못 받는 것과 같은 이치이다.
• 이 가중치는 프로세스의 실질적인 타임 슬라이스를 계산하는데 사용된다. 프로세스 간의 우선순위 차이까지 고려한다.
• 가중치 표의 장점은 nice값의 차이가 유지되면, CPU의 배분 비율도 유지된다는 것이다.

Red-Black 트리의 활용

• CFS는 프로세스 관리에 red-black 트리를 사용함으로써 이 효율성 문제를 해결했다.

I/O 와 잠자는 프로세스 다루기

• 장기간 잠자고 있는 프로세스의 경우 작업이 깨어날 때, vruntime을 적절히 재설정한다. 이를 통해 CFS는 큰 오버헤드 없이 기아현상을 방지하다.