OS: Kernel Scheduler

Scheduler Tuning

Kernel multitasking (Linux) memungkinkan lebih dari satu proses untuk berada pada satu saat dan setiap proses di mungkinkan untuk jalan seperti dia satu-satunya yang ada pada sistem. Banyak thread dari banyak proses seperti berjalan pada saat yang sama. Scheduler memungkinkan ini terjadi dan scheduler berjalan dalam thread dan dibangunkan oleh interupsi waktu, kernel thread lain, atau system call.

kernel/sched.c : di kernel source tree dapat di mengatur nilai ini untuk men-tune scheduler.

MIN_TIMESLICE (minimum timeslice yang akan di peroleh sebuah task)
MAX_TIMESLICE (maximun timeslice yang akan di peroleh sebuah task)
Nilai rata-rata timeslice di tentukan dengan cara me-rata-rata nilai MIN & MAX. Menaikan nilai MIN dan MAx akan menaikan panjang timeslice secara umum. Menaikan panjang TimeSlice akan menaikan EFFICIENCY karena akan lebih context switch (BAGUS untuk HPC dan server systems)
PRIO_BONUS_RATIO : adalah pertengahan dari total range prioritas dimana sebuah task dapat menerima sebagai bonus atau hukuman dalam kalkulasi prioritas dinamis. (Nilai default adalah 25). Jika nilai tinggi, menggunakan nice() untuk menset prioritas statik menjadi kurang effektif sedangkan jika nolai rendah, menset prioritas statik lebih effektif.
MAX_SLEEP_AVG : semakin besar nilainya, semakin lama sebuah task harus sleep sebelum diperhitungkan untuk di aktifkan. Meningkatkan nilai ini akan melukai interaktifitas, akan tetapi untuk beban non-interaktif, kesamaan antar task lebih di sukai.
STARVATION_LIMIT : Mengurangi nilai ini akan melukai interaktifitas karena task akan lebih sering memrelakan CPU time, dan menaikan nilai ini akan menaikan performance interaktif dengan mengorbankan task non-interaktif.

Schedulers : menjaga kebijakan scheduling thread, termasuk kapan, untuk berapa lama, dan untuk beberapa kasus dimana (untuk kernel SMP dimana menjadi penting) sebuah thread akan di jalankan.

SMP Scheduling (scheduling pada beberapa CPU)
SMT Scheduling (Hyper Threading atau Symetric Mult-Thread scheduling)
NUMA Scheduling(Non Uniform Memory Access yang artinya scheduler dapat berjalan di image single system yang tersebar pada beberapa node atau mesin secara fisik. (satu instance kernel pada beberapa mesin secara fisik , HPC)
Soft Real Time Scheduling : schedule task yang mempunyai kebutuhan pewaktu (timing) yang sangat ketat. Real Time task di tugaskan oleh mode khusus scheduling dan scheduler memberikan task ini prioritas di atas task lainnya di sistem. Mode Real Time (RT) scheduling termasuk FIFO (first in first out) dan Round Robin. Secara effektif akan mengabaikan task non RT di sistem.

Context Switches : adalah proses switch dari satu eksekusi thread ke yang lain.

Organisasi Source Code

arch/ : Arsitektur spesifik code
include/ :Header file
kernel/ : Main Kernel Code (non arsitektur spesifik)
mm/ : Kernel memory management code

Program & Process

Program : Sebuah kombinasi dari instruksi dan data yang bersatu untuk menjalankan sebuah tugas saat di eksekusi.
Process : Sebuah instance dari sebuah program. (Sebuah abstraksi yang merepresentasikan kondisi program saat di eksekusi). Sebuah proses dapat dilihat sebagai sebuah grup dari thread yang menggunakan apa yang disebut thread group id (TGID).
Thread : Sebuah proses dapat memiliki beberapa thread eksekusi yang saling bekerjasama untuk mencapai tujuannya. Hanya 1 thread yang dapat di eksekusi di sebuah CPU pada satu waktu. Semua thread secara sederhana adalah proses.
CPU Bound Thread : thread yang banyak menggunakan waktu untuk melakukan komputasi CPU (contoh, HPC atau proses pengolahan angka).
I/O Bound Thread : thread yang banyak menggunakan waktu untuk menunggu pada I/O yang lambat (contoh, membaca dari disk).

Tujuan Scheduling

Efficiency : scheduling harus berusaha untuk mengijinkan sebanyak mungkin pekerjaan di selesaikan dalam batasan berbagai kebutuhan yang ada (contoh, Context Switching adalah mahal dan mengijinkan proses untuk di jalankan dalam waktu yang lama akan menaikan effisiensi) Effisiensi biasanya akan kesulitan kalau kita harus mencapai goal interaktifitas yang berarti lebih banyak context switch.
Interactivitas : Contoh dari interactivitas adalah klik mouse atau tekanan pada tombol keyboard. Kejadian tersebut akan membutuhkan responds yang cepat dan lebih banyak context switch. Banyaknya context switch akan memberikan impresi akan responds yang cepat dengan mengorbankan effisiensi.
Fairness dan Starvation : Task / tugas harus ditangani dengan adil / fairness. Starvation / kelaparan akan terjadi jika sebuah thread tidak diijinkan untuk di run untuk jangka waktu yang cukup lama karena adanya prioritas dari thread lain. Keadilan / fairness berarti tidak boleh ada thread yang lapar / starve atau harus bisa mengakali scheduler untuk memberikan prioritas lebih banyak CPU daripada yang diperoleh saat itu.

Scheduler Performance Tuning

There is no universal ideal for schedule performance. There is no single goal that the scheduler can strive for. An example is the give and take of a very interactive desktop sistem that requires a high level of interactivity (context switching) and HPC systems where less context switching results increases efficiency. With perceived performance (multi tasking and interactive desktops), the current executing thread must give up the processor before it's timeslice is up so the context can switch to a mouse click or a key stroke. A server system on the other hand is less concerned with perceived performance and seeks actual performance. In HPC, systems are solving very complex and large problems (takes days on end) and context switching is not as important and hurts efficiency. Hence the art of scheduler tuning.

   Linux 2.4 O(n) algorithm :old and inefficient legacy linux scheduler. The algorithms execution time grows linearly sd the input size grows.
   Linux 2.6 O(1) Alorithm : New Linux scheduler (rewriiten by Ingo Molnar) -tries to create a constant upper bound for the running time of the algorithm or the algorithm is guaranteed to complete in a certain amount of time regardless of the size of the input.
       O(1) algorithm :
       Each CPU is assigned a primitve called a runqueue and it contains 2 priority array. All tasks begin on the active priority array and when they run out of their timeslice, they are moved to a expired priority array. When there are no more tasks on the priority array, it is swapped with the expired array.
       Only 1 task may modify a CPU runqueue at any given time.
       The highest priority task on the system is always scheduled first and if multiple tasks exist at the same priority level, it uses round robin.
       All tasks have a static priority (unix nice value).
       The 2.6 scheduler rewards I/) bound tasks and punishes CPU bound tasks by adding or subtracting from a task's static priority.
       Calculating TimeSlices :TimeSlices are calculated by simply scaling a task's static priority onto the possibile timeslice range and making sure a certain minimum and maximum timeslice is enforeced.
       WaitQueues : are essentially a list of tasks waiting for some event or condition to occur(waiting for I/O etc).
       Schedule() : is the main scheduler function. You cannot preempt the Schedule() function when it is running
       On SMP machines, ther are migration threads that run with high priority and they make sure that runqueues across all CPU's are balanced.

The Future of Linux Schedulers

Swappable Kernels : Being able to switch schedulers (more than 1 scheduler and you get to choose based the system's function.
Scheduler Mode :means breaking scheduler work loads into categories, and allowing root users to pick scheduler behavior of a system dynamically. Using sysctl and /etc/sysctl.conf to create dynamic changes to the kernel's scheduler on the fly.

Referensi

http://www.dsm.fordham.edu/~mathai/scheduler.html

OS: Kernel Scheduler

Contents