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 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

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

Pranala Menarik

• Linux
• Ubuntu
• Buku Sistem Operasi

Secara Umum

• 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