Perjalanan panjang untuk mewujudkan “preemption malas” di scheduler CPU Linux

• Kernel Linux selama ini mempertahankan beberapa mode preemption sebagai kompromi antara throughput dan waktu respons, dan dengan rangkaian patch baru dari Peter Zijlstra, pembahasan preemption malas (PREEMPT_LAZY) kembali bergerak serius
• PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL, dan PREEMPT_RT yang ada saat ini berbeda dalam cakupan kapan preemption diizinkan; makin sering preemption terjadi, responsivitas bisa membaik tetapi beban pada throughput dan kontensi lock juga meningkat
• PREEMPT_LAZY memakai flag TIF_NEED_RESCHED_LAZY untuk menandai bahwa “penjadwalan ulang diperlukan, tetapi tidak harus segera”, lalu menunda sebagian besar preemption hingga timer tick
• Dalam jangka panjang, tujuannya adalah mengurangi mode preemption non-real-time menjadi PREEMPT_LAZY dan PREEMPT_FULL, serta menghapus sebagian besar pemanggilan cond_resched() di berbagai bagian kernel
• Rangkaian patch saat ini masih memerlukan stabilisasi, peninjauan titik pemanggilan, dan pengujian performa lebih lanjut; pada pengujian awal, throughput PREEMPT_LAZY sedikit di bawah PREEMPT_VOLUNTARY

---

Mode preemption Linux kernel yang ada saat ini

• Kernel saat ini menyediakan beberapa mode preemption yang mengatur kapan task yang sedang berjalan bisa dipreempt oleh task lain
  • PREEMPT_NONE: mode paling sederhana yang hanya mengizinkan preemption saat task yang sedang berjalan telah menghabiskan time slice-nya
  • PREEMPT_VOLUNTARY: mode yang menambahkan banyak titik di dalam kernel tempat preemption bisa dilakukan bila diperlukan
  • PREEMPT_FULL: mode yang mengizinkan preemption di hampir semua titik, kecuali pada bagian yang diblokir kernel seperti saat memegang spinlock
  • PREEMPT_RT: mode yang lebih memprioritaskan preemption daripada hampir segalanya, dan membuat sebagian besar kode yang memegang spinlock juga bisa dipreempt
• Tingkat preemption yang lebih tinggi memungkinkan respons lebih cepat terhadap event seperti pergerakan mouse atau sinyal anomali yang akan segera terjadi di reaktor nuklir
• Sebaliknya, jika preemption terlalu sering, throughput keseluruhan dari pekerjaan intensif CPU yang berjalan lama bisa menurun dan kontensi lock juga dapat meningkat
• Banyak distribusi membangun kernel dengan mode semu PREEMPT_DYNAMIC
  • Saat boot, salah satu dari tiga mode non-real-time di atas bisa dipilih
  • Nilai default-nya adalah PREEMPT_VOLUNTARY
  • Pada sistem dengan debugfs yang ter-mount, mode saat ini bisa diperiksa di /sys/kernel/debug/sched/preempt

Mengapa cond_resched() diperlukan

• PREEMPT_NONE dan PREEMPT_VOLUNTARY tidak mengizinkan preemption arbitrer selama kode kernel sedang berjalan
• Jika pekerjaan panjang terus berlangsung di dalam kernel, latensi berlebihan bisa muncul bahkan pada sistem yang tidak memprioritaskan latensi minimum
• Untuk menghindari hal ini, pemanggilan cond_resched() ditambahkan di berbagai loop yang berjalan lama
  • Setiap pemanggilan adalah titik preemption sukarela tambahan
  • Ini juga bekerja dalam mode PREEMPT_NONE
  • Ada ratusan pemanggilan seperti ini di kernel
• Pendekatan ini adalah heuristik yang hanya bekerja pada lokasi yang ditambahkan oleh pengembang
  • Bisa ada pemanggilan yang tidak perlu
  • Bisa juga ada lokasi yang seharusnya memiliki pemanggilan tetapi terlewat
  • Akibatnya, logika pengambilan keputusan scheduling menyebar ke seluruh kode kernel

Cara kerja inti preemption malas

• Kernel melihat beberapa variabel sekaligus saat menentukan apakah task saat ini bisa dipreempt
• Salah satunya, TIF_NEED_RESCHED, adalah flag yang menandakan bahwa task berprioritas lebih tinggi sedang menunggu akses CPU
  • Saat task berprioritas tinggi bangun, flag ini bisa disetel pada task yang sedang berjalan
  • Jika flag ini tidak ada, kernel tidak perlu mempreempt task saat ini
• Kernel dapat memeriksa TIF_NEED_RESCHED di berbagai titik untuk mempreempt task saat ini
  • Timer tick scheduler
  • Saat kembali ke user space setelah system call
  • Saat interrupt handler selesai
  • Pemanggilan cond_resched()
• Patch preemption malas menambahkan flag baru TIF_NEED_RESCHED_LAZY
  • Artinya penjadwalan ulang memang diperlukan, tetapi tidak wajib dijalankan seketika
  • Dalam mode PREEMPT_LAZY, sebagian besar event menyetel flag baru ini alih-alih TIF_NEED_RESCHED
• Pada titik saat kernel kembali ke user space, jika salah satu dari dua flag tersebut disetel, scheduler akan dipanggil
• Pada titik preemption sukarela dan jalur kembali dari interrupt, hanya TIF_NEED_RESCHED yang diperiksa

Kompromi yang dihasilkan PREEMPT_LAZY

• Dalam PREEMPT_LAZY, sebagian besar event di dalam kernel tidak langsung mempreempt task yang sedang berjalan
• Sebagai gantinya, handler timer tick memeriksa apakah TIF_NEED_RESCHED_LAZY disetel
  • Jika ya, TIF_NEED_RESCHED juga akan disetel
  • Hasilnya, task yang sedang berjalan bisa dipreempt
• Sebuah task biasanya akan berjalan selama waktu yang mendekati time slice-nya, kecuali jika ia secara sukarela melepaskan CPU
  • Perilaku ini diharapkan menghasilkan throughput yang baik
• Dengan perubahan ini, PREEMPT_LAZY juga dapat berjalan dengan preemption kernel yang hampir selalu aktif, seperti PREEMPT_FULL
  • Jika preemption counter mengizinkan, preemption bisa terjadi kapan saja
  • Jika tidak ada kondisi lain yang menghalangi, bahkan kode kernel yang berjalan lama pun dapat dipreempt
• Jika preemption segera benar-benar diperlukan, penundaannya tidak dilakukan
  • Misalnya, jika hasil pemrosesan interrupt membuat task real-time menjadi runnable, maka TIF_NEED_RESCHED akan disetel
  • Dalam situasi ini, preemption terjadi hampir seketika tanpa menunggu timer tick
• Jika hanya TIF_NEED_RESCHED_LAZY yang disetel, preemption tidak akan terjadi
  • Karena itu, kernel PREEMPT_LAZY jauh lebih kecil kemungkinannya untuk mempreempt task yang sedang berjalan dibanding kernel PREEMPT_FULL

Pekerjaan yang masih tersisa hingga cond_resched() bisa dihapus

• Tujuan jangka panjangnya adalah mengurangi mode preemption non-real-time menjadi dua jenis
  • PREEMPT_LAZY
  • PREEMPT_FULL
• PREEMPT_LAZY akan menempati posisi di antara PREEMPT_NONE dan PREEMPT_VOLUNTARY, dan direncanakan menggantikan keduanya
• Jika preemption menjadi mungkin hampir di mana saja, kebutuhan untuk menambahkan titik preemption sukarela secara terpisah di lokasi tertentu akan berkurang
• Saat ini pemanggilan cond_resched() masih tersisa
  • Ini masih dibutuhkan selama PREEMPT_NONE dan PREEMPT_VOLUNTARY masih ada
  • Ini juga membantu agar tidak muncul masalah selama proses stabilisasi preemption malas
• Dalam rangkaian patch saat ini, cond_resched() hanya memeriksa TIF_NEED_RESCHED
  • Karena itu, dalam PREEMPT_VOLUNTARY atau PREEMPT_NONE, banyak situasi yang sebelumnya langsung dipreempt bisa menjadi tertunda
• Steve Rostedt secara khusus menanyakan apakah transisi akan lebih mudah jika cond_resched() tetap mempertahankan makna lamanya, terutama pada PREEMPT_VOLUNTARY
• Thomas Gleixner menilai pilihan untuk hanya memeriksa TIF_NEED_RESCHED adalah keputusan yang tepat
  • Karena itu akan memaksa peninjauan semua pemanggilan cond_resched()
  • Pemanggilan yang tidak perlu memeriksa bit lazy dapat dihapus saat PREEMPT_LAZY diterapkan
  • Pemanggilan yang memang perlu memeriksa bit lazy harus tetap dipertahankan
• Gleixner memperkirakan kurang dari 5% dari pemanggilan cond_resched() akan perlu memeriksa TIF_NEED_RESCHED_LAZY
• Sebelum transisi selesai, ratusan pemanggilan cond_resched() harus ditinjau, dan sebagian besar perlu dihapus
• Rangkaian patch terpisah dari Ankur Arora menangani sebagian detail terkait
• Pengujian performa yang luas juga masih diperlukan
  • Dalam pengujian awal Mike Galbraith, throughput preemption malas sedikit di bawah PREEMPT_VOLUNTARY

Tujuan akhir

• Hasil dari pekerjaan preemption malas ini bisa membuat kernel menjadi sedikit lebih kecil dan sederhana
• Tujuannya adalah kernel yang memberikan latensi yang dapat diprediksi tanpa harus menaburkan pemanggilan terkait scheduler ke seluruh kode
• Pendekatan saat ini tampak sebagai solusi yang lebih baik, tetapi masih diperlukan waktu untuk benar-benar sampai ke tahap itu

[GN⁺]

Opini Hacker News

• Terlihat menjanjikan. Seperti EEVDF, arahnya menyederhanakan kondisi saat ini sekaligus memperbaikinya, jadi sulit membayangkan yang lebih baik dari ini

• Saya penasaran mengapa tingkat preemption bukan mode global, melainkan bukan properti dari event tertentu. Beberapa event harus ditangani dengan latensi lebih rendah daripada event lain

  • Untuk menilai prioritas sebuah event, pertama-tama dibutuhkan waktu CPU. Penilaian itu baru bisa dilakukan setelah menginterupsi proses yang sedang berjalan di CPU saat ini
    Jadi prioritas tertinggi yang bisa dimiliki sebuah event pun dibatasi oleh seberapa pendek jatah waktu yang bisa diterima program sebelum melewati context switch. Agar dapat merespons event jenis apa pun secara andal dengan latensi rendah, semua program yang intensif CPU harus selalu membayar biaya performa, meskipun event itu sangat jarang terjadi
  • Ada dua konsep yang mudah tertukar di sini. Yang satu adalah kapan sebuah proses bisa dipreempt, dan yang lain adalah apakah proses itu benar-benar akan dipreempt
    Titik preemption potensial adalah properti scheduler, dan itulah yang dibahas di sini sebagai mode global. Semakin banyak titik preemption, tentu semakin besar kemungkinan proses dipreempt pada saat yang tidak nyaman, tetapi sekaligus semakin banyak pula kesempatan untuk mencerminkan prioritas dengan benar. Tingkat preemption yang Anda sebut dalam pertanyaan, yaitu prioritas yang diberikan scheduler, memang merupakan properti proses dan bisa dikonfigurasi. Scheduler bawaan Linux juga memberi jatah waktu lebih banyak pada proses yang memiliki prioritas dan berusaha lebih jarang mempreempt proses lain
  • PREEMPT_VOLUNTARY yang dijelaskan dalam artikel bisa dibilang merupakan upaya ke arah itu sampai batas tertentu, dan sekarang sedang dalam proses ditinggalkan
  • Patch ini sampai taraf tertentu menjalankan peran seperti itu. Menurut https://lwn.net/ml/all/[e-mail]...:
    SCHED_IDLE, SCHED_BATCH, SCHED_NORMAL/OTHER menggunakan preemption tertunda, sedangkan FIFO, RR, DEADLINE memakai perilaku Full yang lama
  • Sistem seperti itu sangat mungkin memicu perebutan antarprogram yang saling menuntut prioritas karena menganggap dirinya penting. Secara realistis, kemungkinan besar perusahaan besar akan memanfaatkannya demi pengalaman pengguna yang “lebih baik”
    Karena itu, penting untuk meminimalkan jumlah aplikasi yang berjalan, atau mengontrol secara manual momen-momen singkat yang dialami sebagian besar pengguna. Kadang pekerjaan yang intensif CPU pun lebih mungkin merupakan kode buruk daripada penggunaan sumber daya yang benar-benar efisien. Dalam game, performa harus diprioritaskan, tetapi perlu keseimbangan yang halus agar sistem tidak dibuat berhenti demi multitasking. Bagaimanapun, ini terutama untuk pekerjaan idle, jadi tampaknya tidak perlu diotomatisasi lebih jauh daripada sekadar memberi perintah sederhana agar pengguna bisa men-toggle beberapa tindakan dari skrip

• Disebutkan bahwa “kernel saat ini memiliki empat mode yang mengatur kapan satu task dapat dipreempt demi task lain”; saya penasaran apakah ini tentang task kernel atau juga mencakup task pengguna

  • Ini tentang kode kernel. Kode ruang pengguna selalu bisa dipreempt

• Saya tidak menemukan angka di thread tertaut tempat patch diunggah. Saya penasaran karena seharusnya sudah ada semacam benchmark awal yang menunjukkan potensi praktis dari perubahan ini

  • Ada di paragraf kedua dari akhir artikel
    Disebutkan bahwa pengujian performa yang luas diperlukan, Mike Galbraith telah memulai pekerjaan awal, dan hasilnya menunjukkan throughput preemption tertunda sedikit lebih rendah daripada PREEMPT_VOLUNTARY
  • Saya penasaran bagaimana hal seperti ini harus dibenchmark. Apakah dengan menjalankan beberapa proses secara bersamaan lalu mengurutkan berdasarkan total waktu eksekusi, atau harus mengukur waktu tunggu masing-masing proses

• Saya penasaran seberapa kuat scheduler terikat dengan bagian kode kernel lainnya
  Misalnya, jika ingin menyederhanakan scheduler secara besar-besaran untuk aplikasi komputasi ilmiah yang sama sekali tidak peduli pada preemption, apakah itu bisa dilakukan dengan cara yang bersih dan modular? Apakah ada manfaat nyata juga

  • Jika ingin menjalankan sekumpulan proses dengan preemption serendah mungkin, misalnya di lingkungan HPC, cara paling kuat adalah menetapkan sebagian core sebagai CPU terisolasi, reboot, lalu menempatkan pekerjaan langsung ke sana dengan taskset
    Namun dengan begitu Anda benar-benar harus menetapkan pekerjaan ke CPU secara manual, dan sangat mudah juga terjadi semua pekerjaan malah ditempatkan di CPU yang salah. Cara standarnya adalah mengatur interrupt mask agar interrupt tidak masuk ke CPU “kerja”, dan menggunakan cpuset supaya hanya cgroup tertentu yang berjalan pada cpuset yang diberikan
  • Pada sistem bersih dengan hampir tanpa daemon, jika aplikasi disesuaikan menjadi satu thread sistem operasi per thread CPU dan diberi CPU pinning agar tidak berpindah, Anda bisa mencapai sekitar 95%
    Karena run list menjadi sangat pendek, apa pun yang dilakukan scheduler dampaknya akan cukup kecil. Jika aplikasi tidak banyak melakukan I/O, interrupt juga tidak banyak. Jika bisa memakai kernel tickless—saya tidak tahu sekarang masih opsi terpisah atau sudah default—bisa jadi hampir tidak ada interrupt untuk waktu yang lama
  • Terakhir kali saya melihatnya, ternyata pemisahannya cukup baik
    Namun alasan untuk menyederhanakan besar-besaran adalah menghindari bug, bukan karena akan mendapat banyak performa dibanding scheduler default yang dikonfigurasi dengan baik. Ada banyak konfigurasi, tetapi bug di area itu juga tidak banyak. Penyederhanaan yang naif biasanya lebih banyak menghilangkan performa daripada menambahnya. Jika menjalankan sistem non-interaktif, perubahan paling mudah adalah memperbesar kuota waktu proses
  • Saya akan memakai RT Linux saja. Ia punya scheduler dasar sendiri, sementara scheduler kernel berjalan sebagai pekerjaan idle, dan pekerjaan real-time mendapat prioritas di atas segalanya