Difference between revisions of "OS: Kernel Scheduler"

From OnnoWiki
Jump to navigation Jump to search
 
(18 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
==Scheduler Tuning==
 
==Scheduler Tuning==
  
Multi tasking kernels (Linux) allow more than 1 process to exist at any given time and each process is allowed to run as if it is the only one on the system. Many threads from many processes appear to be running at the same time. A scheduler acomplishes this goal and it runs in a thread and is woken up by a timer interrupt, another kernel thread, or a system call.
+
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 : In the kernel source tree you can adjust these values to tune the scheduler.
 
  
* MIN_TIMESLICE (bare minimum timeslice that a task can receive)
+
kernel/sched.c : di kernel source tree dapat di mengatur nilai ini untuk men-tune scheduler.
* MAX_TIMESLICE (maximun timeslice that a task can receive)
 
* The average timeslice is determined by averaging the MIN & MAX Values. Increasing the value of the MIN and MAx will increase timeslice lengths in general. Increasing TimeSlice lengths will increase EFFICIENCY because there will be less context switches (GOOD for HPC and server systems)
 
* PRIO_BONUS_RATIO : is the middle percentage of the total priority range that a task can receive as a bonus or punishment in dynamic priority calculations. (Default value is 25) When the value is high, using nice() to set the static priority is less effective and when it is low, static priorities are more effective.
 
* MAX_SLEEP_AVG :the larger this value gets, the longer tasks will need to sleep in order to be considered active. Increaing this value hurts interactivity, but for non interactive workloads, equality among tasks may be desirable.
 
* STARVATION_LIMIT : Decreasing this value hurts ineractivity because the task will have to give up the CPU more often, and increasing this value will increase interactive performance at the cost of non-ineractive tasks.  
 
  
Schedulers : enforce a thread scheduling policy, including when, for how long, and in some case where (in SMP kernels-where is a question) threads can execute.
+
* 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 nilai 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 merelakan CPU time, dan menaikan nilai ini akan menaikan performance interaktif dengan mengorbankan task non-interaktif.
  
* SMP Scheduling (scheduling across CPUs)
+
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.
* SMT Scheduling (Hyper Threading or Symetric Mult-Thread scheduling)
 
* NUMA Scheduling(Non Uniform Memory Access which means the scheduler can run a single system image across multiple nodes or physical machines. (one instance of the kernel across many phyical machines , HPC) There is aconcept of a scheduler domain that contains all CPU's in the system. CPU's are divided into groups.
 
* Soft Real Time Scheduling : schedule tasks that have strict timing requirements. Real Time tasks are assigned special scheduling modes and the scheduler gives them priority over another task on the system. RT scheduling modes include FIFO (first in first out) and Round Robin. This effectively ignores non RT tasks on the system.  
 
  
Context Switches : is the process of switching from one thread of executuion to another.
+
* 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.
  
==Source Code Organization==
+
Context Switches : adalah proses switch dari satu eksekusi thread ke yang lain.
  
arch/ : Architecture specific code
+
==Organisasi Source Code==
include/ :Header files
 
kernel/ : Main Kernel Code (non architecture specific)
 
mm/ : Kernel's memory management code
 
  
==Programs & Processes==
+
* arch/ : Arsitektur spesifik code
 +
* include/ :Header file
 +
* kernel/ : Main Kernel Code (non arsitektur spesifik)
 +
* mm/ : Kernel memory management code
  
* Program : A combination of instructions and data put together to perform a task when executed.
+
==Program & Process==
* Process : An instance of a program. (An abstraction to embody the state of a program in execution) A process is simply a group of threads that share something called a thread group id (TGID).
 
* Threads : A process can have multiple threads of execution that work together to accomplish its goals. Only 1 thread can be executed on a CPU at any given time.All threads are simply processes.
 
* CPU Bound Threads : threads that spend alot of time doing cpu computations. (ie HPC or alot of number crunching)
 
* I/O Bound Threads : threads that spend time waiting on slow I/O (ie read from disk)
 
  
==Scheduling Goals==
+
* 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).
  
* Efficiency : it must try to allow as much real work as possible to be done while staying within the restraints of other requirements. (ie Context Switching is expensive and allowing processes to run for longer periods of time increases efficency) Efficency suffers for the sake of other goals such as interactivity, because interactivity typicaly imples more context switches.
+
==Tujuan Scheduling==
* Interactivity : An example of interactivity is a mouse click or a keystroke. Such events require a quick response or more context switches. Many context switches give the impression of immediate response at the cost of efficiency.
 
* Fairness and Starvation : Tasks should be treated with a certain degree of fairness, including the stipulation that no thread starves. Starvation happens when a thread is not allowed to run for an unacceptabilty long period of time due to the prioritization of other threads. Fairness does mean that every thread should ever starve or be able to trick the scheduler into giving a higher priority ot more CPU than it out have.
 
  
==Scheduler Performance Tuning==
+
* 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.
  
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.
+
==TUning Scheduler Performance==
    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==
+
Tidak ada settingan yang ideal untuk scheduler. Tidak ada satu goal yang cocok untuk sebuah scheduler. Contoh, selalu ada perebutan untuk memberikan dan mengambil pada sebuah sistem desktop yang interaktif yang membutuhkan proses interaktif yang sangat tinggi (context switchin) dengan sistem HPC yang lebih sedikit context switching-nya yang mengakibatkan peningkatkan effisiensi.
  
* Swappable Kernels : Being able to switch schedulers (more than 1 scheduler and you get to choose based the system's function.
+
Dengan objektif performance antara multi tasking dan interaktif desktop, thread yang sedang di run / di eksekusi harus melepaskan processor sebelum timeslice (waktu penggunaan CPU) habis sehingga context dapat switch ke mouse klik atau keyboard. Sebuah sistem server di sisi lain, akan lebih memfokuskan diri pada performance. Di HPC, dimana sistem biasanya bekerja untuk mencari solusi dapt perhitungan yang sangat kompleks yang membutuhkan waktu berhari-hari untuk selesai maka context switch menjadi tidak penting bahkan akan sangat merugikan effisiensi. Begitulah seni dari tuning scheduler.
* 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.  
+
 
 +
* Linux 2.4 O(n) algorithm : linux scheduler legacy yang tua dan tidak effisien. Algoritma waktu eksekusi berkembang secara linier saat input size berkembang.
 +
* Linux 2.6 O(1) Alorithm : Linux scheduler baru (ditulis oleh Ingo Molnar) - berusaha untuk membuat konstanta batas atas untuk algoritma running time juga algoritma menjamin untuk selesai pada waktu tertentu berapapun besarnya input.
 +
 
 +
O(1) algorithm :
 +
* Setiap CPU dialokasikan sebuah primitive yang disebut runqueue dan berisi 2 array priority. Semua task akan mulai di active priority array dan jika mereka selesai dengan timeslice-nya, mereka akan di pindahkan ke expired priority array. Jika tidak ada lagi task di priority array, maka isinya akan di swap / ditukar dengan expired array.
 +
* Hanya 1 task yang dapat memodifikasi CPU runqueue pada satu waktu.
 +
* Task dengan prioritas tertinggi di sistem selalu di jadwalkan pertama dan jika ada beberapa task dengan prioritas yang sama, maka akan digunakan round robin.
 +
* Semua task mempunyai prioritas statik (nilai nice unix).
 +
* Scheduler 2.6 memberikan kemudahan bagi task I/O bound dan memberikan hukuman bagi task CPU bound dengan cara menambahkan atau mengurangi dari prioritas statik task.
 +
 
 +
 
 +
* Calculating TimeSlices : TimeSlices di hitung dengan cara menskalakan prioritas statik task ke range timeslice yang mungkin dan memastikan timeslice minimum dan maximum dapat di wujudkan.
 +
* WaitQueues : pada dasarnya daftar task yang menunggu kejadian atau kondisi yang akan terjadi (contoh, menungggu I/O).
 +
* Schedule() : adalah fungsi scheduler utama. Kita tidak dapat mematikan fungsi Schedule() pada saat dia running.
 +
 
 +
Di mesin SMP, ada migrasi thread yang dijalankan dengan prioritas tinggi dan mereka akan memastikan bahwa runqueues di semua CPU terjadi dengan balans.
 +
 
 +
==Linux Scheduler Yang akan Datang==
 +
 
 +
* Swappable Kernel : Kemampuan untuk switch scheduler (lebih dari 1 scheduler dan kita dapat memilih berdasarkan fungsi sistem).
 +
* Scheduler Mode : memecah beban scheduler menjadi beberapa kategori, dan mengijinkan root untuk memilih perilaku scheduler dari sistem secara dinamis. Menggunakan sysctl dan /etc/sysctl.conf untuk membuat perubahan secara dinamis dari scheduler kernel pada saat berjalan.
  
 
==Referensi==
 
==Referensi==
Line 67: Line 75:
  
 
==Pranala Menarik==
 
==Pranala Menarik==
 +
 +
* [[Linux]]
 +
* [[Ubuntu]]
 +
* [[Buku Sistem Operasi]]
 +
 +
===Secara Umum===
  
 
* [[Sistem Operasi]]
 
* [[Sistem Operasi]]
 +
 +
===Instalasi Linux===
 +
 +
* [[Linux: CLI untuk Survival]]
 +
* [[Linux: Skema Partisi di Linux]]
 +
* [[Linux: Instalasi Sistem Operasi]]
 +
 +
===Compile Kernel===
 +
 +
* [[Kernel]]
 +
* [[OS: Linux Kernel]]
 +
* [[Kernel: Anatomi Kernel Source]]
 +
* [[Compile Kernel]]
 +
* [[Compile Kernel: Konfigurasi Kernel]]
 +
 +
===Remaster Linux===
 +
 +
* [[Cara Cepat Melakukan Remastering Ubuntu]]
 +
 +
===Sistem Operasi untuk Embedded===
 +
 +
* [[OpenWRT]]
 +
* [[OpenWRT: Download Firmware yang sudah jadi]]
 +
* [[OpenWRT: Source Repository Download]]
 +
* [[OpenWRT: Melihat Daftar Package]]
 +
 +
====Membuat Firmware Sendiri====
 +
 +
* [[OpenWRT: Build Firmware]]
 +
* [[OpenWRT: Build Firmware Buffalo WZRHPG450H]]
 +
* [[OpenWRT: Build Firmware Buffalo WZRHPG300N]]
 +
* [[OpenWRT: Build Firmware Ubiquiti NanoStation2]]
 +
* [[OpenWRT: Build Firmware Mikrotik RB433]]
 +
* [[OpenWRT: Build Firmware Linksys WRT160NL]]
 +
* [[OpenWRT: Build Firmware Linksys WRT54GL]]
 +
 +
====Flash ke Device====
 +
 +
* [[OpenWRT: Flash Linksys WRT54GL]]
 +
* [[OpenWRT: Flash Buffalo WZRHP450H]]
 +
* [[OpenWRT: Flash Buffalo WZRHP300N]]
 +
* [[OpenWRT: Flash UBNT NanoStation2]]
 +
 +
====Beberapa Tip====
 +
 +
* [[OpenWRT: Mikrotik RB433]]
 +
* [[OpenWRT: 3G modem]]
 +
* [[OpenWRT: Build Firmware dengan 3G Modem Support]]
 +
* [[OpenWRT: Setup Firewall]]
 +
* [[OpenWRT: Konfigurasi UBNT NanoStation2 tanpa WebGUI]]
 +
 +
===Tuning Kernel===
 +
 +
* [[OS: Parameter Kernel Default]]
 +
 +
====Tuning Kernel Scheduler====
 +
 +
* [[OS: Kernel Scheduler]]
 +
* [[OS: Tuning Kernel Scheduler]]
 +
* [[OS: Tuning Completely Fair scheduler CFS]]
 +
* [[OS: Complete Teori Tuning Kernel Scheduler]]
 +
 +
====Tuning I/O Scheduler====
 +
 +
* [[OS: Tuning Completely Fair Queueing CFQ I/O scheduler]]
 +
* [[OS: Complete Teori Tuning I/O Performance]]
 +
 +
====Tuning Manajemen Memory====
 +
 +
* [[OS: Tuning Manajemen Memory]]
 +
 +
===Android===
 +
 +
* [[OS: Android - Download]]
 +
 +
===Membuat Kernel Module===
 +
 +
* [[OS: Mengerti System Call]]
 +
* [[OS: Membuat Kernel Modul]]
 +
 +
===Monitoring & Benchmark===
 +
 +
* [[OS: Build in Monitoring Tool]]
 +
* [[Linux Benchmarking]]
 +
* [[OS: Benchmarking menggunakan UnixBench]]
 +
* [[OS: Benchmarking menggunakan LLCBench]]

Latest revision as of 05:45, 9 May 2013

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 nilai 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 merelakan 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.

TUning Scheduler Performance

Tidak ada settingan yang ideal untuk scheduler. Tidak ada satu goal yang cocok untuk sebuah scheduler. Contoh, selalu ada perebutan untuk memberikan dan mengambil pada sebuah sistem desktop yang interaktif yang membutuhkan proses interaktif yang sangat tinggi (context switchin) dengan sistem HPC yang lebih sedikit context switching-nya yang mengakibatkan peningkatkan effisiensi.

Dengan objektif performance antara multi tasking dan interaktif desktop, thread yang sedang di run / di eksekusi harus melepaskan processor sebelum timeslice (waktu penggunaan CPU) habis sehingga context dapat switch ke mouse klik atau keyboard. Sebuah sistem server di sisi lain, akan lebih memfokuskan diri pada performance. Di HPC, dimana sistem biasanya bekerja untuk mencari solusi dapt perhitungan yang sangat kompleks yang membutuhkan waktu berhari-hari untuk selesai maka context switch menjadi tidak penting bahkan akan sangat merugikan effisiensi. Begitulah seni dari tuning scheduler.

  • Linux 2.4 O(n) algorithm : linux scheduler legacy yang tua dan tidak effisien. Algoritma waktu eksekusi berkembang secara linier saat input size berkembang.
  • Linux 2.6 O(1) Alorithm : Linux scheduler baru (ditulis oleh Ingo Molnar) - berusaha untuk membuat konstanta batas atas untuk algoritma running time juga algoritma menjamin untuk selesai pada waktu tertentu berapapun besarnya input.

O(1) algorithm :

  • Setiap CPU dialokasikan sebuah primitive yang disebut runqueue dan berisi 2 array priority. Semua task akan mulai di active priority array dan jika mereka selesai dengan timeslice-nya, mereka akan di pindahkan ke expired priority array. Jika tidak ada lagi task di priority array, maka isinya akan di swap / ditukar dengan expired array.
  • Hanya 1 task yang dapat memodifikasi CPU runqueue pada satu waktu.
  • Task dengan prioritas tertinggi di sistem selalu di jadwalkan pertama dan jika ada beberapa task dengan prioritas yang sama, maka akan digunakan round robin.
  • Semua task mempunyai prioritas statik (nilai nice unix).
  • Scheduler 2.6 memberikan kemudahan bagi task I/O bound dan memberikan hukuman bagi task CPU bound dengan cara menambahkan atau mengurangi dari prioritas statik task.


  • Calculating TimeSlices : TimeSlices di hitung dengan cara menskalakan prioritas statik task ke range timeslice yang mungkin dan memastikan timeslice minimum dan maximum dapat di wujudkan.
  • WaitQueues : pada dasarnya daftar task yang menunggu kejadian atau kondisi yang akan terjadi (contoh, menungggu I/O).
  • Schedule() : adalah fungsi scheduler utama. Kita tidak dapat mematikan fungsi Schedule() pada saat dia running.

Di mesin SMP, ada migrasi thread yang dijalankan dengan prioritas tinggi dan mereka akan memastikan bahwa runqueues di semua CPU terjadi dengan balans.

Linux Scheduler Yang akan Datang

  • Swappable Kernel : Kemampuan untuk switch scheduler (lebih dari 1 scheduler dan kita dapat memilih berdasarkan fungsi sistem).
  • Scheduler Mode : memecah beban scheduler menjadi beberapa kategori, dan mengijinkan root untuk memilih perilaku scheduler dari sistem secara dinamis. Menggunakan sysctl dan /etc/sysctl.conf untuk membuat perubahan secara dinamis dari scheduler kernel pada saat berjalan.

Referensi

Pranala Menarik

Secara Umum

Instalasi Linux

Compile Kernel

Remaster Linux

Sistem Operasi untuk Embedded

Membuat Firmware Sendiri

Flash ke Device

Beberapa Tip

Tuning Kernel

Tuning Kernel Scheduler

Tuning I/O Scheduler

Tuning Manajemen Memory

Android

Membuat Kernel Module

Monitoring & Benchmark