Difference between revisions of "OS: Kernel Scheduler"

From OnnoWiki
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 8: Line 8:
 
* MAX_TIMESLICE (maximun 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)
 
* 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.
+
* 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.
 
* 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.
+
* 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.
 
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.
Line 49: Line 49:
  
 
* 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.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 : 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.
+
* 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 :
 
        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.
+
O(1) algorithm :
        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.
+
* 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.
        WaitQueues : are essentially a list of tasks waiting for some event or condition to occur(waiting for I/O etc).
+
* Hanya 1 task yang dapat memodifikasi CPU runqueue pada satu waktu.
        Schedule() : is the main scheduler function. You cannot preempt the Schedule() function when it is running
+
* Task dengan prioritas tertinggi di sistem selalu di jadwalkan pertama dan jika ada beberapa task dengan prioritas yang sama, maka akan digunakan round robin.
        On SMP machines, ther are migration threads that run with high priority and they make sure that runqueues across all CPU's are balanced.
+
* 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.
  
==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.
+
* 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.
* 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.  
+
* 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 75: Line 78:
 
* [[Linux]]
 
* [[Linux]]
 
* [[Ubuntu]]
 
* [[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]]
 
* [[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]]
 
* [[OS: Parameter Kernel Default]]
 +
 +
====Tuning Kernel Scheduler====
 +
 
* [[OS: Kernel Scheduler]]
 
* [[OS: Kernel Scheduler]]
 +
* [[OS: Tuning Kernel Scheduler]]
 +
* [[OS: Tuning Completely Fair scheduler CFS]]
 
* [[OS: Complete Teori Tuning Kernel Scheduler]]
 
* [[OS: Complete Teori Tuning Kernel Scheduler]]
* [[OS: Tuning Kernel Scheduler]]
+
 
 +
====Tuning I/O Scheduler====
 +
 
 
* [[OS: Tuning Completely Fair Queueing CFQ I/O scheduler]]
 
* [[OS: Tuning Completely Fair Queueing CFQ I/O scheduler]]
* [[OS: Tuning Completely Fair scheduler CFS]]
+
* [[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]]
 
* [[OS: Build in Monitoring Tool]]
 
* [[Linux Benchmarking]]
 
* [[Linux Benchmarking]]
 
* [[OS: Benchmarking menggunakan UnixBench]]
 
* [[OS: Benchmarking menggunakan UnixBench]]
 
* [[OS: Benchmarking menggunakan LLCBench]]
 
* [[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