CFS:Penjadwalan proses yang benar-benar adil di Linux

Linux menggunakan pendekatan modular untuk penjadwalan prosesor di mana algoritme yang berbeda dapat digunakan untuk menjadwalkan jenis proses yang berbeda. Kelas penjadwalan menentukan kebijakan penjadwalan mana yang berlaku untuk jenis proses mana. Penjadwalan yang benar-benar adil (CFS), yang menjadi bagian dari kernel Linux 2.6.23 pada tahun 2007, adalah kelas penjadwalan untuk proses normal (bukan real-time) dan oleh karena itu diberi nama SCHED_NORMAL .

CFS ditujukan untuk aplikasi interaktif yang khas di lingkungan desktop, tetapi dapat dikonfigurasi sebagai SCHED_BATCH untuk mendukung beban kerja batch yang umum, misalnya, pada server web volume tinggi. Bagaimanapun, CFS rusak secara dramatis dengan apa yang mungkin disebut "penjadwalan preemptive klasik." Juga, klaim "benar-benar adil" harus dilihat dengan mata teknis; jika tidak, klaim tersebut mungkin tampak seperti bualan kosong.

Mari gali lebih dalam tentang apa yang membedakan CFS dari—bahkan, di atas—penjadwal proses lainnya. Mari kita mulai dengan tinjauan singkat beberapa istilah teknis inti.

Beberapa konsep inti

Linux mewarisi tampilan Unix dari proses sebagai program yang sedang dieksekusi. Dengan demikian, suatu proses harus bersaing dengan proses lain untuk sumber daya sistem bersama:memori untuk menyimpan instruksi dan data, setidaknya satu prosesor untuk menjalankan instruksi, dan perangkat I/O untuk berinteraksi dengan dunia luar. Penjadwalan proses adalah bagaimana sistem operasi (OS) memberikan tugas (misalnya, mengolah beberapa angka, menyalin file) ke prosesor—proses yang berjalan kemudian melakukan tugas tersebut. Sebuah proses memiliki satu atau lebih utas eksekusi , yang merupakan urutan instruksi tingkat mesin. Menjadwalkan suatu proses berarti menjadwalkan salah satu utasnya pada prosesor.

Terminal Linux

• 7 emulator terminal teratas untuk Linux
• 10 alat baris perintah untuk analisis data di Linux
• Unduh Sekarang:lembar contekan SSH
• Lembar contekan perintah Linux tingkat lanjut
• Tutorial baris perintah Linux

Dalam langkah penyederhanaan, Linux mengubah penjadwalan proses menjadi penjadwalan thread dengan memperlakukan proses terjadwal seolah-olah itu adalah single-threaded. Jika suatu proses multi-threaded dengan N utas, lalu N tindakan penjadwalan akan diperlukan untuk menutupi utas. Utas dalam proses multi-utas tetap terkait karena berbagi sumber daya seperti ruang alamat memori. Utas Linux terkadang digambarkan sebagai proses yang ringan, dengan ringan menggarisbawahi pembagian sumber daya di antara utas dalam suatu proses.

Meskipun suatu proses dapat berada di berbagai keadaan, dua hal yang menarik dalam penjadwalan. Sebuah diblokir proses sedang menunggu penyelesaian beberapa acara seperti acara I/O. Proses dapat melanjutkan eksekusi hanya setelah acara selesai. Sebuah dapat dijalankan proses adalah salah satu yang saat ini tidak diblokir.

Sebuah proses terikat prosesor (alias terikat dengan komputer ) jika menggunakan sebagian besar prosesor dibandingkan dengan sumber daya I/O, dan I/O-terikat dalam kasus sebaliknya; oleh karena itu, proses yang terikat prosesor sebagian besar dapat dijalankan, sedangkan proses yang terikat I/O sebagian besar diblokir. Sebagai contoh, mengolah angka terikat prosesor, dan mengakses file terikat I/O. Meskipun seluruh proses mungkin dicirikan sebagai terikat prosesor atau terikat I/O, proses yang diberikan mungkin satu atau yang lain selama tahapan eksekusi yang berbeda. Aplikasi desktop interaktif, seperti browser, cenderung terikat I/O.

Penjadwal proses yang baik harus menyeimbangkan kebutuhan tugas yang terikat prosesor dan yang terikat I/O, terutama dalam sistem operasi seperti Linux yang berkembang pesat di banyak platform perangkat keras:mesin desktop, perangkat tertanam, perangkat seluler, kluster server, superkomputer , dan banyak lagi.

Penjadwalan preemptive klasik versus CFS

Unix mempopulerkan penjadwalan preemptive klasik, yang kemudian diadopsi oleh sistem operasi lain termasuk VAX/VMS, Windows NT, dan Linux. Di tengah model penjadwalan ini adalah batas waktu tetap , jumlah waktu (misalnya, 50 md) yang diizinkan untuk dipegang oleh suatu tugas oleh prosesor hingga didahului oleh tugas lain. Jika proses yang didahului belum menyelesaikan pekerjaannya, proses tersebut harus dijadwal ulang. Model ini kuat karena mendukung multitasking (konkurensi) melalui pembagian waktu prosesor, bahkan pada mesin CPU tunggal sebelumnya.

Model klasik biasanya mencakup beberapa antrean penjadwalan, satu per prioritas proses:Setiap proses dalam antrean dengan prioritas lebih tinggi dijadwalkan sebelum proses apa pun dalam antrean dengan prioritas lebih rendah. Sebagai contoh, VAX/VMS menggunakan 32 antrian prioritas untuk penjadwalan.

CFS membagi-bagikan dengan timelices tetap dan prioritas eksplisit. Jumlah waktu untuk tugas tertentu pada prosesor dihitung secara dinamis saat konteks penjadwalan berubah selama masa pakai sistem. Berikut adalah sketsa ide motivasi dan detail teknis:

• Bayangkan sebuah prosesor, P, yang ideal karena dapat menjalankan banyak tugas secara bersamaan . Misalnya, tugas T1 dan T2 dapat dijalankan pada P secara bersamaan, dengan masing-masing menerima 50% kekuatan pemrosesan magis P. Idealisasi ini menggambarkan multitasking yang sempurna , yang berusaha dicapai CFS secara aktual sebagai lawan dari prosesor ideal. CFS dirancang untuk mendekati multitasking yang sempurna.

• Penjadwal CFS memiliki latensi target , yang merupakan jumlah waktu minimum—diidealkan untuk durasi yang sangat kecil—yang diperlukan untuk setiap tugas yang dapat dijalankan untuk mengaktifkan setidaknya satu pengaktifan prosesor. Jika durasi seperti itu bisa sangat kecil, maka setiap tugas yang dapat dijalankan akan menyalakan prosesor selama rentang waktu tertentu, betapapun kecilnya (mis., 10ms, 5ns, dll.). Tentu saja, durasi ideal yang sangat kecil harus diperkirakan di dunia nyata, dan perkiraan default adalah 20 ms. Setiap tugas yang dapat dijalankan kemudian mendapat 1/N potongan latensi target, di mana N adalah jumlah tugas. Misalnya, jika latensi target adalah 20 md dan ada empat tugas yang bersaing, maka setiap tugas mendapat bagian waktu 5 md. Omong-omong, jika hanya ada satu tugas selama acara penjadwalan, tugas yang beruntung ini mendapatkan seluruh latensi target sebagai bagiannya. adil di CFS muncul ke permukaan di 1/N slice yang diberikan untuk setiap tugas yang memperebutkan prosesor.

• 1/N slice memang merupakan timelice—tetapi tidak tetap karena slice seperti itu bergantung pada N , jumlah tugas yang saat ini diperebutkan untuk prosesor. Sistem berubah dari waktu ke waktu. Beberapa proses berhenti dan yang baru muncul; proses yang dapat dijalankan memblokir dan proses yang diblokir menjadi dapat dijalankan. Nilai N dinamis dan oleh karena itu, adalah 1/N timeslice dihitung untuk setiap tugas runnable bersaing untuk prosesor. Tradisional bagus nilai digunakan untuk menimbang 1/N slice:bagus . prioritas rendah nilai berarti bahwa hanya sebagian kecil dari 1/N slice diberikan untuk tugas, sedangkan bagus . prioritas tinggi nilai berarti bahwa fraksi yang lebih besar secara proporsional dari 1/N slice diberikan untuk tugas. Singkatnya, bagus nilai tidak menentukan irisan, tetapi hanya mengubah 1/N irisan yang mewakili keadilan di antara tugas-tugas yang bersaing.

• Sistem operasi mengeluarkan overhead setiap kali konteks beralih terjadi; yaitu, ketika satu proses mendahului yang lain. Untuk menjaga agar overhead ini tidak menjadi terlalu besar, ada jumlah waktu minimum (dengan pengaturan tipikal 1 md hingga 4 md) bahwa setiap proses terjadwal harus dijalankan sebelum didahului. Minimum ini dikenal sebagai perincian minimum . Jika banyak tugas (misalnya, 20) bersaing untuk prosesor, maka granularitas minimum (anggap 4 md) mungkin lebih daripada 1/N slice (dalam hal ini, 1ms). Jika perincian minimum ternyata lebih besar dari 1/N iris, sistem kelebihan beban karena ada terlalu banyak tugas yang harus diselesaikan oleh prosesor—dan keadilan tidak berlaku.

• Kapan preemption terjadi? CFS mencoba meminimalkan sakelar konteks, mengingat overhead mereka:waktu yang dihabiskan untuk sakelar konteks adalah waktu yang tidak tersedia untuk tugas-tugas lain. Oleh karena itu, begitu tugas mendapatkan prosesor, tugas itu berjalan untuk seluruh bobotnya 1/N slice sebelum didahului demi beberapa tugas lain. Misalkan tugas T1 telah dijalankan untuk bobotnya 1/N slice, dan tugas yang dapat dijalankan T2 saat ini memiliki runtime virtual terendah (vruntime) di antara tugas-tugas yang bersaing untuk prosesor. Catatan vruntime, dalam nanodetik, berapa lama tugas telah berjalan pada prosesor. Dalam hal ini, T1 akan didahulukan untuk mendukung T2.

• Penjadwal melacak vruntime untuk semua tugas, dapat dijalankan dan diblokir. Semakin rendah vruntime tugas, semakin layak tugas tersebut untuk waktu pada prosesor. Oleh karena itu, CFS memindahkan tugas-tugas vruntime rendah ke depan garis penjadwalan. Detail akan datang karena baris diimplementasikan sebagai pohon, bukan daftar.

• Seberapa sering penjadwal CFS harus menjadwal ulang? Ada cara sederhana untuk menentukan periode penjadwalan . Misalkan latensi target (TL) adalah 20 md dan perincian minimum (MG) adalah 4 md:

  TL / MG = (20 / 4) = 5 ## five or fewer tasks are ok

  Dalam hal ini, lima atau lebih sedikit tugas akan memungkinkan setiap tugas menyalakan prosesor selama latensi target. Misalnya, jika nomor tugas adalah lima, setiap tugas yang dapat dijalankan memiliki 1/N irisan 4ms, yang kebetulan sama dengan granularitas minimum; jika nomor tugas tiga, setiap tugas mendapat 1/N irisan hampir 7ms. Dalam kedua kasus tersebut, penjadwal akan menjadwal ulang dalam 20 md, durasi latensi target.

  Masalah terjadi jika jumlah tugas (mis., 10) melebihi TL / MG karena sekarang setiap tugas harus mendapatkan waktu minimum 4 ms, bukan 1/N yang dihitung irisan, yaitu 2 ms. Dalam hal ini, penjadwal akan menjadwal ulang dalam 40 md:

  (number of tasks) * MG = (10 * 4) = 40ms ## period = 40ms

Penjadwal Linux yang mendahului CFS menggunakan heuristik untuk mempromosikan perlakuan yang adil dari tugas-tugas interaktif sehubungan dengan penjadwalan. CFS mengambil pendekatan yang sangat berbeda dengan membiarkan fakta vruntime berbicara sendiri, yang kebetulan mendukung keadilan tidur . Tugas interaktif, pada dasarnya, cenderung banyak tidur dalam arti menunggu input pengguna dan dengan demikian menjadi terikat I/O; karenanya, tugas seperti itu cenderung memiliki vruntime yang relatif rendah, yang cenderung memindahkan tugas ke depan garis penjadwalan.

Fitur khusus

CFS mendukung symmetrical multiprocessing (SMP) di mana setiap proses (baik kernel atau pengguna) dapat dijalankan pada prosesor apa pun. Namun domain penjadwalan yang dapat dikonfigurasi dapat digunakan untuk mengelompokkan prosesor untuk penyeimbangan beban atau bahkan pemisahan. Jika beberapa prosesor berbagi kebijakan penjadwalan yang sama, maka penyeimbangan beban di antara mereka adalah opsi; jika prosesor tertentu memiliki kebijakan penjadwalan yang berbeda dari yang lain, maka prosesor ini akan dipisahkan dari yang lain sehubungan dengan penjadwalan.

grup penjadwalan yang dapat dikonfigurasi adalah fitur CFS lainnya. Sebagai contoh, pertimbangkan server web Nginx yang berjalan di mesin desktop saya. Saat startup, server ini memiliki proses master dan empat proses pekerja, yang bertindak sebagai penangan permintaan HTTP. Untuk permintaan HTTP apa pun, pekerja tertentu yang menangani permintaan tidak relevan; hanya penting bahwa permintaan tersebut ditangani pada waktu yang tepat, sehingga keempat pekerja bersama-sama menyediakan kumpulan dari mana untuk menarik penangan tugas saat permintaan masuk. Dengan demikian, tampaknya adil untuk memperlakukan keempat pekerja Nginx sebagai sebuah kelompok daripada sebagai individu untuk tujuan penjadwalan, dan grup penjadwalan dapat digunakan untuk melakukan hal itu. Empat pekerja Nginx dapat dikonfigurasi untuk memiliki satu vruntime di antara mereka daripada vruntime individu. Konfigurasi dilakukan dengan cara Linux tradisional, melalui file. Untuk vruntime-sharing, file bernama cpu .berbagi , dengan detail yang diberikan melalui perintah shell yang sudah dikenal, akan dibuat.

Seperti disebutkan sebelumnya, Linux mendukung penjadwalan kelas sehingga kebijakan penjadwalan yang berbeda, bersama dengan algoritme penerapannya, dapat hidup berdampingan pada platform yang sama. Kelas penjadwalan diimplementasikan sebagai modul kode di C. CFS, kelas penjadwalan yang dijelaskan sejauh ini, adalah SCHED_NORMAL . Ada juga kelas penjadwalan khusus untuk tugas waktu nyata, SCHED_FIFO (masuk pertama, keluar pertama) dan SCHED_RR (usul). Di bawah SCHED_FIFO , tugas dijalankan sampai selesai; di bawah SCHED_RR , tugas dijalankan sampai mereka menghabiskan timelice yang tetap dan didahului.

Penerapan CFS

CFS memerlukan struktur data yang efisien untuk melacak informasi tugas dan kode berperforma tinggi untuk menghasilkan jadwal. Mari kita mulai dengan istilah sentral dalam penjadwalan, runqueue . Ini adalah struktur data yang mewakili garis waktu untuk tugas terjadwal. Terlepas dari namanya, runqueue tidak perlu diimplementasikan dengan cara tradisional, seperti daftar FIFO. CFS melanggar tradisi dengan menggunakan pohon merah-hitam yang diatur waktu sebagai runqueue. Struktur data sangat cocok untuk pekerjaan itu karena merupakan pohon pencarian biner yang menyeimbangkan diri, dengan insert yang efisien dan hapus operasi yang dijalankan di O(log N) waktu, di mana N adalah jumlah node dalam pohon. Juga, pohon adalah struktur data yang sangat baik untuk mengatur entitas ke dalam hierarki berdasarkan properti tertentu, dalam hal ini vruntime.

Di CFS, simpul internal pohon mewakili tugas yang akan dijadwalkan, dan pohon secara keseluruhan, seperti runqueue apa pun, mewakili garis waktu untuk eksekusi tugas. Pohon merah-hitam digunakan secara luas di luar penjadwalan; misalnya, Java menggunakan struktur data ini untuk mengimplementasikan TreeMap .

Di bawah CFS, setiap prosesor memiliki runqueue tugas tertentu, dan tidak ada tugas yang terjadi secara bersamaan di lebih dari satu runqueue. Setiap runqueue adalah pohon merah-hitam. Node internal pohon mewakili tugas atau grup tugas, dan node ini diindeks oleh nilai vruntime mereka sehingga (di pohon secara keseluruhan atau di setiap subpohon) node internal di sebelah kiri memiliki nilai vruntime lebih rendah daripada yang di sebelah kanan:

    25     ## 25 is a task vruntime

    /\

  17  29   ## 17 roots the left subtree, 29 the right one

  /\  ...

 5  19     ## and so on

...  \

     nil   ## leaf nodes are nil

Singkatnya, tugas dengan vruntime terendah—dan, oleh karena itu, kebutuhan terbesar akan prosesor—berada di suatu tempat di subpohon kiri; tugas dengan vruntime yang relatif tinggi berkumpul di subpohon kanan. Tugas yang didahulukan akan masuk ke subpohon kanan, sehingga memberi tugas lain kesempatan untuk bergerak ke kiri di pohon. Tugas dengan vruntime terkecil berakhir di node paling kiri (internal) pohon, yang dengan demikian merupakan bagian depan runqueue.

Penjadwal CFS memiliki instance, C task_struct , untuk melacak informasi mendetail tentang setiap tugas yang akan dijadwalkan. Struktur ini menyematkan sched_entity struktur, yang pada gilirannya memiliki informasi spesifik penjadwalan, khususnya, vruntime per tugas atau grup tugas:

struct task_struct {       /** info on a task **/

  ...

  struct sched_entity se;  /** vruntime, etc. **/

  ...

};

Pohon merah-hitam diimplementasikan dalam mode C yang sudah dikenal, dengan premium pada pointer untuk efisiensi. Sebuah cfs_rq contoh struktur menyematkan rb_root bidang bernama tasks_timeline , yang menunjuk ke akar pohon merah-hitam. Setiap simpul internal pohon memiliki penunjuk ke induk dan dua simpul anak; simpul daun memiliki nil sebagai nilai mereka.

CFS mengilustrasikan bagaimana ide yang lugas—memberikan setiap tugas bagian yang adil dari sumber daya prosesor—dapat diimplementasikan dengan cara yang sederhana namun sangat efisien. Perlu diulang bahwa CFS mencapai penjadwalan yang adil dan efisien tanpa artefak tradisional seperti timelices tetap dan prioritas tugas eksplisit. Pengejaran penjadwal yang lebih baik terus berlanjut, tentu saja; untuk saat ini, bagaimanapun, CFS sebaik yang didapat untuk penjadwalan prosesor tujuan umum.