완전 균등화 스케줄러

Completely Fair Scheduler
완전 균등화 스케줄러
원저작자잉고 몰나르
개발자Linux 커널 개발자
기입처C
운영 체제Linux 커널
유형프로세스 스케줄러
면허증.GPL-2.0
웹 사이트kernel.org
Linux 커널의 단순화된 구조에서 "완전 균등화 스케줄러"(프로세스 스케줄러)의 위치.

Complete Fair Scheduler(CFS; 완전 균등화 스케줄러)는 Linux 커널의 2.6.23(2007년 10월) 릴리스에 병합된 프로세스스케줄러로, 의 태스크의 디폴트스케줄러입니다SCHED_NORMAL클래스(즉, 실시간 실행 제약이 없는 태스크)프로세스 실행을 위한 CPU 리소스 할당을 처리하고 전체 CPU 사용률을 극대화하는 동시에 대화형 성능을 극대화하는 것을 목표로 합니다.

CFS 스케줄러의 실장은 액티브태스크와 유효기간이 지난 태스크의 실행 큐를 유지 및 스위칭하는 오래된 Linux 2.6 커널에서 사용되는 이전 O(1) 스케줄러와 달리 CPU별 실행 큐를 기반으로 합니다.CPU별 실행 큐의 노드는 빨간색-검은색 트리로 정렬되어 있는 시간순서대로 스케줄러 가능한 엔티티티입니다.CFS는 priority별 고정 타임슬라이스라는 오래된 개념을 폐지하고 대신 작업(또는 보다 나은 스케줄링 가능한 [1][2]엔티티)에 CPU 시간을 공평하게 할당하는 것을 목표로 합니다.

알고리즘.

태스크(스레드의 동의어)는 Linux에서 예약할 수 있는 최소 엔티티입니다.그러나 스레드 그룹, 전체 멀티 스레드 프로세스 및 특정 사용자의 모든 프로세스를 관리할 수도 있습니다.이 설계는 스케줄링 가능한 엔티티의 개념으로 이어지며, 여기서 작업은 스케줄러에 의해 전체적으로 그룹화되고 관리됩니다.이 설계가 작동하려면task_struct작업 설명자에 유형 필드가 포함되어 있습니다.sched_entity태스크가 속한 엔티티 집합을 나타냅니다.

타입의 각 CPU별 실행 큐cfs_rq분류하다sched_entityred-black tree(또는 Linux 언어에서는 rbtree)로 시간 순서대로 구조화됩니다.여기서 맨 왼쪽 노드는 최소의 슬라이스 실행 시간을 받은 엔티티에 의해 점유됩니다(이러한 방법은 에 저장됩니다).vruntime엔티티의 필드).노드는 프로세서 실행 시간(나노초)[3]에 의해 인덱싱됩니다.

또, 각 프로세스의 「최대 실행 시간」도 계산되어 프로세스가 「이상적인 프로세서」상에서 실행될 것으로 예상되는 시간을 나타냅니다.이는 프로세스가 실행 대기 중인 시간을 총 프로세스 수로 나눈 값입니다.

새 프로세스를 실행하기 위해 스케줄러가 호출될 때:

  1. 스케줄링 트리의 맨 왼쪽 노드가 선택되어(실행 시간이 가장 짧기 때문에) 실행을 위해 전송됩니다.
  2. 프로세스가 단순히 실행을 완료하면 시스템 및 스케줄링 트리에서 제거됩니다.
  3. 프로세스가 최대 실행 시간에 도달하거나 중단(자발적 또는 인터럽트를 통해)된 경우 새로 사용한 실행 시간에 따라 스케줄링 트리에 다시 삽입됩니다.
  4. 그런 다음 트리에서 왼쪽 끝에 있는 새 노드가 선택되고 반복이 반복됩니다.

프로세스가 많은 시간을 sleep 상태로 보내면 소비된 시간 값은 낮아지고 최종적으로 프로세스가 필요할 때 자동으로 우선 순위가 상승합니다.따라서 이러한 태스크는 지속적으로 실행되는 태스크보다 프로세서 시간이 짧지 않습니다.

노드를 삽입하는 알고리즘의 복잡성cfs_rqCFS 스케줄러의 runqueue는 O(log N)입니다.N은 엔티티의 총수입니다.맨 왼쪽 노드가 항상 캐시되기 때문에 실행할 다음 엔티티를 선택하는 작업은 일정 시간 내에 이루어집니다.

역사

Con Kolivas의 스케줄링에 관한 작업, 특히 Rotating Staircade Deadline이라는 이름의 "공정한 스케줄링"의 구현은 Ingo Molnarr가 초기 O(1) 스케줄러를 대체하는 CFS를 개발하도록 영감을 주었고,[4] 그의 발표에서 Kolivas를 신뢰했다.CFS는 Weighted [5]Fair Queuing이라고 불리는 잘 연구된 고전적인 스케줄링 알고리즘의 구현입니다.원래 패킷 네트워크용으로 개발된 페어 큐잉은 이전에는 스트라이드 스케줄링이라는 이름으로 CPU 스케줄링에 적용되어 있었습니다.CFS는 범용 운영 [5]체제에서 널리 사용되는 공정 큐잉 프로세스 스케줄러의 첫 번째 구현입니다.

Linux 커널은 2010년 11월에 2.6.38 커널용 패치를 받았습니다.이것에 의해, 스케줄러는 데스크탑과 워크스테이션에서 사용하는 「fairer」가 되었습니다.Mike Galbraith가 Linus Torvalds가 제안한 아이디어를 사용하여 개발한 이 패치는 인터랙티브 데스크톱 [6]성능을 대폭 향상시키는 자동 그룹화 기능을 구현합니다.알고리즘은 부모 프로세스를 자녀 [7]프로세스와 같은 태스크그룹에 배치합니다(태스크 그룹은 시스템콜을 통해 작성된 세션에 연결됩니다).[8]이것에 의해, 멀티 코어 및 멀티 CPU(SMP) 시스템이 CPU 부하가 높은 스레드를 많이 사용하는 그 외의 태스크를 실행하고 있을 때에, 인터랙티브한 응답 시간이 늦어지는 문제가 해결되었습니다.간단하게 설명하면, 이 패치를 적용하면, Linux 커널을 컴파일 하거나 비디오를 인코딩 하는 동안에도, 비디오의 시청, E-메일 읽기, 및 그 외의 일반적인 데스크탑 액티비티를 글리치나 끊기는 일 없이 실행할 수 있습니다.

2016년에 Linux 스케줄러는 "Linux Scheduler: A Decade of Wasted Cores"[9]라는 문서에 설명된 제안을 바탕으로 더 나은 멀티코어 성능을 위해 패치를 적용했습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Love, Robert (2010). Linux Kernel Development (3rd ed.). United States of America: Addison Wesley. pp. 41–61. ISBN 9780672329463.
  2. ^ "Linux: The Completely Fair Scheduler KernelTrap". 2007-04-19. Archived from the original on 2007-04-19. Retrieved 2021-05-16.
  3. ^ CFS의 설명(ibm.com )
  4. ^ Molnár, Ingo (2007-04-13). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel (Mailing list).
  5. ^ a b Li, T.; Baumberger, D.; Hahn, S. (2009). "Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin" (PDF). ACM SIGPLAN Notices. 44 (4): 65. CiteSeerX 10.1.1.567.2170. doi:10.1145/1594835.1504188.
  6. ^ 놀라운 기능을 발휘하는 최대 200라인 Linux 커널 패치
  7. ^ Galbraith, Mike (2010-11-15). "[RFC/RFT PATCH v3] Re: [RFC/RFT PATCH v3] sched: automated per tty task groups [CFS]". linux-kernel (Mailing list).
  8. ^ Galbraith, Mike (2010-11-20). "[PATCH v4] sched: automated per session task groups". linux-kernel (Mailing list).
  9. ^ Lozi, Jean-Pierre; Lepers, Baptiste; Funston, Justin; Gaud, Fabien; Quema, Vivian; Fedorova, Alexandra. "The Linux Scheduler: A Decade of Wasted Cores" (PDF). EuroSys 2016. Retrieved 15 June 2019.

외부 링크