Linux Schedule Load Balance

오전 10:42 2006-09-14
조경민 bro@shinbiro.com
Linux Schedule load balance
=======================================================

multi-processor 상에서 한 cpu만 열심히 task 수행하고 다른 cpu는
놀고 있으면 안된다. 따라서 os는 적절히 task를 공정히 각 cpu에
분배해야한다.
이때 multi-processor 상황은 다음과 같을 수 있다.

- SMT( or hyper-threaded cpus) : 하나의 cpu지만 안에 논리적 cpu들이 들어 있다.
  (리눅스는 shared cpu라고 표현함)
  이경우 cache를 공유하고, 메모리도 공유된다.
  따라서 이 경우 task migrate 오버헤드가 없으므로 1-2ms 마다 자주 imbalance 한 task를 이주시킬 수 있다.

- physical processor or SMP(symmetric multi processor) : 하나의 물리적 프로세서 패키징 안에 하나 또는 여러 core가 들어 있다. 프로세서 안의 각 core는 각자의 cache를 갖고 있을 수 있다.. smp는 모두 메모리를 공유한다.
  정책에 따라서 가끔씩 이주시켜야한다.

- NUMA : 각 NUMA Node는 cpu에 메모리와 cache로 구성되며, 각 노드마다 메모리를 갖고 있으므로, cache affinity뿐 아니라 memory affinity도 중요하게 다뤄져야 한다. (SGI에서 512개의 processor를 묶기도 했다.)
  역시 정책에 따라서 가끔씩 이주시켜야한다.

위와 같은 multi-processor 상황이 어떻게 될지 모르기 때문에 리눅스는
여러 상황에서도 절적히 맞을 수 있는 scheduling domain 개념을 두었다.


Linux Schedule load balance
--------------------------------------------------------
Scheduling domains
http://lwn.net/Articles/80911/

Proceedings of the Linux Symposium
https://ols2006.108.redhat.com/reprints/siddha-reprint.pdf

Scheduling domains and Load Balancing        in linux – 2.6.10
http://140.114.71.71/kerneltracing/slides/scheduling_domain.ppt


A Flexible Thread Scheduler for A Flexible Thread Scheduler for
Hierarchical Multiprocessor Hierarchical Multiprocessor Machines
http://coset.irisa.fr/coset-2slides/BULLES.PDF

Understanding the Linux 2.6.8.1 CPU Scheduler
http://josh.trancesoftware.com/linux/linux_cpu_scheduler.pdf

Using Hierarchical Scheduling to Support
Soft Real-Time Applications in General-Purpose Operating Systems
http://www.cs.utah.edu/~regehr/papers/diss/doc-www.html

Linux SMP Scheduler and System Calls related to Scheduling
http://i30www.ira.uka.de/teaching/coursedocuments/88/5.4_Scholl_SMP-Scheduling.pdf


schedule load balance
-------------------------------------------------

Load Balancing, Scheduling, & Termination Detection
http://www.cs.hmc.edu/courses/mostRecent/cs156/html10/slides10.pdf



논문 어떻게??
RTOS Scheduler Implementation in Hardware and Software for Real Time Applications
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/proceedings/&toc=comp/proceedings/rsp/2006/2580/00/2580toc.xml&DOI=10.1109/RSP.2006.34