프로세스 쓰레드의 적응형 파티셔닝을 이용하는 프로세스스케쥴러 document_id A220623014975

본 출원은 2005년 3월 14일자로 출원된 미국 가특허출원 제60/662,070호, 2005년 12월 22일자로 출원된 미국 특허출원 제11/317,468호, 및 2005년 8월 31일자로 출원된 미국 특허출원 제11/216,795호를 우선권 주장한다. 본 발명은 오퍼레이팅 시스템이 쓰레드 등의 실행을 스케쥴링하는 방식에 관한 것이다. 보다 상세하게는, 본 발명은 프로세스 쓰레드에 대한 적응형 파티션 스케쥴링을 갖는 오퍼레이팅 시스템에 관한 것이다. 오퍼레이팅 시스템의 커널은 시스템에서 활성 상태에 있는 각각의 쓰레드가 대응하는 프로세스를 적절히 실행하기 위해 적당한 양의 CPU 시간을 획득하도록 CPU 리소스를 분배할 수 있어야만 한다. 이를 위해, 커널은 이용가능한 CPU 시간이 다수의 쓰레드 간에 어떻게 할당되는지를 결정하는 스케쥴링 시스템을 구현할 수 있다. 적어도 3가지 유형의 프로세스 스케쥴링 시스템, 즉 FIFO 스케쥴링 시스템, 라운드-로빈(round-robin) 스케쥴링 시스템 및 산발적(sporadic) 스케쥴링 시스템이 있다. 각각의 시스템에서, 우선순위 값이 CPU에 의해 실행되는 프로세스의 각 쓰레드에 할당된다. 전체적인 시스템의 동작에 중요할 수 있는 쓰레드에는 높은 우선순위 값이 할당되는 반면, 시스템의 동작에 덜 중요할 수 있는 쓰레드는 보다 낮은 우선순위 값을 갖는다. 스케쥴링 시스템이 쓰레드에 CPU에의 액세스를 제공하는지 여부도 또한 쓰레드의 상태에 의존한다. 예를 들어, 쓰레드는 준비된 상태에 있거나 블로킹된 상태에 있을 수 있다(그렇지만, 다른 상태들도 또한 사용될 수 있음). 쓰레드가 실행되기 위한 모든 조건이 충족되어 있다는 점에서 쓰레드가 실행될 수 있을 때, 그 쓰레드는 준비된 상태에 있다. 이와 반대로, 쓰레드가 즉각 완료될 수 없는 동작을 개시하려고 시도하고 또 쓰레드의 실행이 계속될 수 있기 이전에 어떤 이벤트의 완료를 기다려야만 할 때, 그 쓰레드는 블로킹된 상태에 있다. FIFO 스케쥴링 시스템에서, 현재 실행 중인 쓰레드는 쓰레드가 블로킹에 의해 CPU를 포기할 때까지, 쓰레드가 실행을 완료할 때까지, 또는 쓰레드가 더 높은 우선순위 쓰레드에 의해 대체(preempt)될 때까지 CPU 시간 전부를 계속하여 사용한다. 이들 기준 중 하나가 만족되면, FIFO 스케쥴링 시스템은 CPU를 준비된 상태에 있는 최고 우선순위 프로세스/쓰레드에 할당한다. 일반적으로, 각각의 우선순위 레벨에 대해 하나의 준비된 큐가 있다. 라운드-로빈 스케쥴링 시스템은 CPU 시간을 쓰레드에 할당하기 위해 부가의 파라미터, 즉 타임슬라이스(timeslice)를 사용한다. 타임슬라이스는 쓰레드가 CPU에 액세스할 수 있는 동안인 시간의 양이다. 라운드-로빈 스케쥴링 시스템에서, 현재 실행 중인 쓰레드는 이하의 이벤트, 즉 1) 현재 실행 중인 프로세스가 블로킹됨, 2) 현재 실행 중인 프로세스가 완료됨, 3) 현재 실행 중인 프로세스가 더 높은 우선순위 쓰레드에 의해 대체됨, 또는 4) 현재 실행 중인 프로세스가 그의 타임슬라이스를 다 소모함 중 하나가 발생할 때까지 CPU 시간 전부를 계속하여 사용한다. 현재 실행 중인 프로세스가 블로킹되거나 그의 타임슬라이스를 다 소모하면, 그 프로세스는 그의 우선순위 레벨에 대한 준비된 큐의 뒤쪽에 배치된다. 산발적 스케쥴링은 라운드-로빈 스케쥴링과 얼마간 유사하다. 산발적 스케쥴링 시스템에서, 현재 실행 중인 프로세스는 이하의 이벤트, 1) 현재 실행 중인 프로세스가 블로킹됨, 2) 현재 실행 중인 프로세스가 완료됨, 3) 현재 실행 중인 프로세스가 더 높은 우선순위 쓰레드에 의해 대체됨, 또는 4) 현재 실행 중인 프로세스가 주어진 기간 내에서 쓰레드에 할당된 실행 시간에 관한 최고 한도(capped limit)를 다 소모함 중 하나가 발생할 때까지 CPU 시간 전부를 계속하여 사용한다. 이 최고 한도는 버짓(budget)이라고 하고, 이 버짓이 사용될 수 있는 주어진 기간은 보충 기간(replenishment period)이라고 한다. 동작을 설명하면, 쓰레드에 대한 버짓은 보충 기간의 만료 시에 보충된다. 현재 실행 중인 프로세스가 블로킹되면, 그 프로세스는 그의 우선순위 레벨에 대한 준비된 큐의 뒤쪽에 배치된다. 그렇지만, 현재 실행 중인 프로세스가 보충 기간 내에 그의 버짓을 다 소모하는 경우, 그의 우선순위 레벨은 미리 정해진 값만큼 감소되고, 그 프로세스는 이 더 낮은 우선순위 레벨에 대한 준비된 큐의 뒤쪽에 배치된다. 프로세스/쓰레드의 우선순위 레벨은 다수의 서로 다른 조건에 응답하여 그의 원래의 값으로 복귀될 수 있다. 미국 온타리오주 카나타 소재의 QNX Software Systems로부터 입수가능한 것 등의 어떤 오퍼레이팅 시스템에서, 시스템에서의 각각의 쓰레드는 전술한 스케쥴링 시스템 중 임의의 것을 사용하여 실행될 수 있다. 따라서, 이들 스케쥴링 시스템은 노드 상의 모든 쓰레드 및 프로세스에 대해 개개의 쓰레드마다 효과적이다. 각각의 쓰레드는 프로세스/쓰레드 자체의 동작을 통해 특정의 스케쥴링 시스템 유형에 할당된다. 이것은 소프트웨어 설계자에게 상당한 정도의 설계 유연성을 제공하지만 또한 동일한 시스템에 대한 코드를 구현하는 소프트웨어 설계자들 간의 조정(coordination)도 필요로 한다. 이러한 조정은 서로 다른 쓰레드에 대한 우선순위의 할당은 물론 각각의 쓰레드에 할당되는 스케쥴링 시스템 유형을 포함한다. 어떤 이용가능한 오퍼레이팅 시스템은 스케쥴링을 전반적으로 적용한다. 한가지 이러한 전반적인 스케쥴링 시스템은 공평-분배 스케쥴링(fair-share scheduling)이라고 한다. 공평-분배 스케쥴링 시스템에서, CPU 사용은 시스템 사용자, 그룹 또는 프로세스 간에 똑같이 분배될 수 있다. 예를 들어, 4명의 사용자(A, B, C, D)가 각각 하나의 프로세스를 동시에 실행하고 있는 경우, 공평-분배 스케쥴러는 각각의 사용자가 전체의 25%(100% / 4 = 25%)를 받도록 이용가능한 CPU 사이클을 논리적으로 분배하게 된다. 사용자 B가 제1 프로세스를 시작하는 경우, 각각의 사용자는 여전히 전체 사이클의 25%를 받게 되지만, 사용자 B의 프로세스 둘다는 각각 전체 이용가능한 CPU 시간의 12.5%를 받게 된다. 반면에, 새로운 사용자가 시스템 상에서 프로세스를 시작하는 경우, 스케쥴러는 각각의 사용자가 전체의 20%(100% / 5 = 20%)를 받도록 이용가능한 CPU 사이클을 재분배하게 된다. 또 하나의 추상화 계층은 사용자들을 그룹으로 분할하는 것 및 공평 분배 시스템을 이 그룹에도 역시 적용하는 것을 가능하게 해준다. 이 경우에, 이용가능한 CPU 사이클은 먼저 그룹들 간에 분배되고, 이어서 그룹들 내의 사용자들 간에 분배되며, 이어서 그 사용자에 대한 프로세스들 간에 분배된다. 예를 들어, 3명, 2명 및 4명의 사용자를 각각 포함하는 3개의 그룹(1, 2, 3)이 있는 경우, 이용가능한 CPU 사이클은 다음과 같이 분배될 수 있다. 그룹마다 100% / 3 = 33.3%, 그룹 1: 사용자마다 (33.3% / 3명의 사용자) = 11.1%, 그룹 2: (33.3% / 2명의 사용자) = 16.7%, 및 그룹 3: (33.3% / 4명의 사용자) = 8.3%. 그룹들 간에 다른 퍼센트 분배도 역시 사용될 수 있다. 공평-분배 스케쥴링 전략을 논리적으로 구현하는 다른 방식은 각각의 추상화 레벨(프로세스, 사용자, 그룹, 기타 등등)에서 라운드-로빈 스케쥴링 전략을 재귀적으로 적용하는 것이다. 라운드-로빈 스케쥴링에서, 똑같은 중요도 또는 우선순위의 쓰레드는 차례대로 실행된다. 이들 각각은 각각의 쓰레드 또는 쓰레드의 그룹의 재산인 구간(interval) 또는 타임슬라이스 동안 실행된다. 상기한 스케쥴링 시스템들이 서로 다른 응용에서 이점을 갖지만, 이들은 어떤 시스템 응용에서 사용될 때 결점이 있을 수 있다. 예를 들어, 프로세스/쓰레드의 대기 시간이 우선순위 레벨의 할당을 통해서만 계획되는 쓰레드별 스케쥴링 시스템이 실시간 시스템에서 사용될 때, 낮은 우선순위 쓰레드에 대해 아주 긴 대기 시간이 일어날 수 있다. 악의적인 소프트웨어 프로세스는 높은 우선순위 실행을 위해 그 자신을 구성하고 그에 따라 더 낮은 우선순위 쓰레드의 적절한 스케쥴링을 대체할 수 있다. 이러한 문제는 또한 예를 들어 시스템 개발 동안에 높은 우선순위 쓰레드가 오작동하여 무한 루프에 들어갈 때에도 일어날 수 있다. 전반적인 공평-분배 스케쥴링 시스템은 이러한 문제를 회피할 수 있지만, 실시간 시스템에서 사용하는 데 필요한 응답성이 부족하다. 따라서, 높은 우선순위 쓰레드가 실시간으로 동작하는 것을 효과적으로 가능하게 해주면서 그와 동시에 모든 쓰레드에 어떤 종류의 공평-분배 CPU 액세스를 제공하는 스케쥴링 시스템이 필요하다.