Linux CFS: Bagaimana untuk mencapai keadilan lengkap dalam penjadualan proses

Penjadualan proses ialah salah satu fungsi teras sistem pengendalian Ia menentukan proses yang boleh mendapatkan masa pelaksanaan CPU dan berapa banyak masa yang mereka dapat. Dalam sistem Linux, terdapat banyak algoritma penjadualan proses, yang paling penting dan biasa digunakan ialah Completely Fair Scheduling Algorithm (CFS), yang diperkenalkan daripada Linux versi 2.6.23. Matlamat CFS adalah untuk membolehkan setiap proses memperoleh peruntukan masa CPU yang munasabah dan saksama mengikut berat dan keperluannya sendiri, dengan itu meningkatkan prestasi keseluruhan dan kelajuan tindak balas sistem. Artikel ini akan memperkenalkan prinsip asas, struktur data, butiran pelaksanaan, kelebihan dan keburukan CFS, dan membantu anda memahami dengan mendalam keadilan lengkap penjadualan proses Linux.

Sejarah ringkas penjadual Linux

Penjadual Linux awal menggunakan reka bentuk minimalis yang jelas tidak tertumpu pada seni bina besar dengan banyak pemproses, apatah lagi hyper-threading. 1.2 Penjadual Linux menggunakan baris gilir cincin untuk pengurusan tugas boleh dijalankan dan menggunakan strategi penjadualan round-robin. Penjadual ini menambah dan mengalih keluar proses dengan sangat cekap (dengan kunci melindungi struktur). Pendek kata, penjadual tidak kompleks tetapi mudah dan cepat.
Linux versi 2.2 memperkenalkan konsep penjadualan kelas, membenarkan strategi penjadualan untuk tugas masa nyata, tugas bukan preemptif dan tugasan bukan masa nyata. Penjadual 2.2 juga termasuk sokongan berbilang pemprosesan (SMP) simetri.
Kernel 2.4 termasuk penjadual yang agak mudah yang berjalan pada selang O(N) (ia berulang pada setiap tugas semasa acara penjadualan). 2.4 Penjadual membahagikan masa kepada zaman Dalam setiap zaman, setiap tugasan dibenarkan untuk dilaksanakan sehingga bahagian masanya habis. Jika tugasan tidak menggunakan semua kepingan masanya, maka separuh daripada kepingan masa yang tinggal akan ditambahkan pada kepingan masa baharu supaya ia boleh melaksanakan lebih lama dalam zaman seterusnya. Penjadual hanya mengulangi tugas dan menggunakan fungsi kebaikan (metrik) untuk memutuskan tugasan yang akan dilaksanakan seterusnya. Walaupun kaedah ini agak mudah, ia agak tidak cekap, tidak berskala dan tidak sesuai digunakan dalam sistem masa nyata. Ia juga tidak mempunyai keupayaan untuk memanfaatkan seni bina perkakasan baharu, seperti pemproses berbilang teras.
Penjadual 2.6 awal, dipanggil penjadual O(1), telah direka bentuk untuk menyelesaikan masalah dengan penjadual 2.4 - penjadual tidak perlu mengulangi keseluruhan senarai tugas untuk menentukan tugas seterusnya untuk dijadualkan (oleh itu dinamakan O( 1) , yang bermaksud ia lebih cekap dan berskala). Penjadual O(1) menjejaki tugas yang boleh dijalankan dalam baris gilir larian (sebenarnya, terdapat dua baris gilir larian bagi setiap tahap keutamaan - satu untuk tugasan aktif dan satu untuk tugas tamat tempoh), yang bermaksud menentukan tugasan yang akan dilaksanakan tugas seterusnya, penjadual hanya mengambil tugas seterusnya dari baris gilir larian aktiviti tertentu mengikut keutamaan). Penjadual O(1) berskala lebih baik dan termasuk interaktiviti, memberikan banyak cerapan untuk menentukan sama ada tugas terikat I/O atau terikat pemproses. Tetapi penjadual O(1) kekok dalam kernel. Pendedahan pengkomputeran memerlukan banyak kod, sukar untuk diurus, dan bagi pemurni gagal menangkap intipati algoritma.

Untuk menyelesaikan masalah yang dihadapi oleh penjadual O(1) dan menangani tekanan luaran yang lain, sesuatu perlu diubah. Perubahan ini datang daripada tampung kernel Con Kolivas, yang termasuk Penjadual Tarikh Akhir Tangga Berputar (RSDL), yang menggabungkan kerja awalnya pada penjadual tangga. Hasil kerja ini ialah penjadual yang direka bentuk ringkas yang menggabungkan keadilan dan kependaman terhad. Dengan penjadual Kolivas menarik banyak perhatian (dan ramai yang meminta ia dimasukkan ke dalam kernel arus perdana 2.6.21 semasa), jelas bahawa perubahan penjadual akan datang. Ingo Molnar, pencipta penjadual O(1), kemudian membangunkan penjadual berasaskan CFS di sekitar beberapa idea Kolivas. Mari kita membedah CFS dan lihat bagaimana ia beroperasi pada tahap yang tinggi.

————————————————————————————————————————

Gambaran Keseluruhan CFS

Idea utama di sebalik CFS adalah untuk mengekalkan keseimbangan (keadilan) dari segi menyediakan masa pemproses untuk tugasan. Ini bermakna bahawa proses harus diperuntukkan sejumlah besar pemproses. Apabila masa yang diperuntukkan untuk tugas tidak seimbang (bermaksud bahawa satu atau lebih tugasan tidak diberi jumlah masa yang besar berbanding tugasan lain), tugas yang tidak seimbang harus diberi masa untuk dilaksanakan.

Untuk mencapai keseimbangan, CFS mengekalkan jumlah masa yang disediakan untuk tugasan dalam apa yang dipanggil masa jalan maya. Lebih kecil masa jalan maya sesuatu tugas, lebih pendek masa tugas itu dibenarkan untuk mengakses pelayan - semakin tinggi permintaan pada pemproses. CFS juga termasuk konsep kesaksamaan tidur untuk memastikan bahawa tugasan yang tidak sedang dijalankan (contohnya, menunggu I/O) mendapat bahagian pemproses yang saksama apabila mereka memerlukannya.

Tetapi tidak seperti penjadual Linux sebelumnya, yang tidak mengekalkan tugas dalam baris gilir larian, CFS mengekalkan pepohon merah-hitam tersusun masa (lihat Rajah 1). Pokok merah-hitam adalah pokok yang mempunyai banyak sifat menarik dan berguna. Pertama, ia adalah pengimbangan diri, bermakna tiada laluan dalam pokok itu lebih daripada dua kali lebih panjang daripada laluan lain. Kedua, berjalan pada pokok berlaku dalam masa O(log n) (di mana n ialah bilangan nod dalam pokok). Ini bermakna anda boleh memasukkan atau memadam tugasan dengan cepat dan cekap.

Rajah 1. Contoh pokok merah-hitam

Tugas disimpan dalam pokok merah-hitam tersusun masa (diwakili oleh sched_entity objek), dengan tugasan yang paling banyak menuntut pemproses (masa jalan maya terendah) disimpan di sebelah kiri pepohon dan tugas yang paling tidak memerlukan pemproses ( masa jalan maya tertinggi) masa jalan) disimpan di sebelah kanan pokok. Untuk keadilan, penjadual kemudian memilih nod paling kiri pokok merah-hitam untuk dijadualkan di sebelah untuk mengekalkan keadilan. Tugasan mengambil kira masa CPUnya dengan menambahkan masa berjalannya pada masa jalan maya, dan kemudian, jika boleh dijalankan, dimasukkan semula ke dalam pepohon. Dengan cara ini, tugasan di sebelah kiri pokok diberi masa untuk dijalankan, dan kandungan pokok itu dipindahkan dari kanan ke kiri untuk mengekalkan keadilan. Oleh itu, setiap tugas boleh dijalankan mengejar tugas lain untuk mengekalkan keseimbangan pelaksanaan merentas keseluruhan set tugasan boleh dijalankan.

————————————————————————————————————————

Prinsip dalaman CFS

Semua tugas dalam Linux diatur oleh task_structperwakilan struktur tugas. Struktur ini (dan kandungan lain yang berkaitan) menerangkan sepenuhnya tugasan dan termasuk keadaan semasa tugasan, tindanannya, identiti proses, keutamaan (statik dan dinamik), dan sebagainya. Anda boleh menemui ini dan struktur berkaitan dalam ./linux/include/linux/sched.h. Tetapi oleh kerana tidak semua tugas boleh dijalankan, anda mempunyai , Menlo, monospace;color: #10f5d6c">task_struct tidak akan menemui sebarang medan berkaitan CFS. Sebaliknya, struktur baharu yang dipanggil task_struct 的任务结构表示。该结构（以及其他相关内容）完整地描述了任务并包括了任务的当前状态、其堆栈、进程标识、优先级（静态和动态）等等。您可以在 ./linux/include/linux/sched.h 中找到这些内容以及相关结构。 但是因为不是所有任务都是可运行的，您在 task_struct 中不会发现任何与 CFS 相关的字段。 相反，会创建一个名为 sched_entity dicipta untuk menjejaki maklumat penjadualan (lihat Rajah 2).

Rajah 2. Hierarki struktur tugas dan pokok merah-hitam

Hubungan antara pelbagai struktur ditunjukkan dalam Rajah 2. Akar pokok melepasi struktur rb_root 元素通过 cfs_rq 结构（在 ./kernel/sched.c 中）引用。红黑树的叶子不包含信息，但是内部节点代表一个或多个可运行的任务。红黑树的每个节点都由 rb_node 表示，它只包含子引用和父对象的颜色。 rb_node 包含在sched_entity 结构中，该结构包含 rb_node 引用、负载权重以及各种统计数据。最重要的是， sched_entity 包含 vruntime（64 位字段），它表示任务运行的时间量，并作为红黑树的索引。 最后，task_struct 位于顶端，它完整地描述任务并包含 sched_entity.

Setakat bahagian CFS, fungsi penjadualan adalah sangat mudah. Dalam ./kernel/sched.c anda akan melihat rujukan generik schedule() 函数，它会先抢占当前运行任务（除非它通过yield() 代码先抢占自己）。注意 CFS 没有真正的时间切片概念用于抢占，因为抢占时间是可变的。 当前运行任务（现在被抢占的任务）通过对 put_prev_task 调用（通过调度类）返回到红黑树。 当 schedule 函数开始确定下一个要调度的任务时，它会调用 pick_next_task函数。此函数也是通用的（在 ./kernel/sched.c 中），但它会通过调度器类调用 CFS 调度器。 CFS 中的 pick_next_task 函数可以在 ./kernel/sched_fair.c（称为 pick_next_task_fair()）中找到。 此函数只是从红黑树中获取最左端的任务并返回相关 sched_entity。通过此引用，一个简单的 task_of() 调用确定返回的 task_struct. Penjadual universal akhirnya menyediakan pemproses untuk tugas ini.

————————————————————————————————————————

Keutamaan dan CFS

CFS tidak menggunakan keutamaan secara langsung tetapi menggunakannya sebagai faktor pereputan untuk masa sesuatu tugas dibenarkan untuk dilaksanakan. Tugas keutamaan rendah mempunyai pekali pereputan yang lebih tinggi, manakala tugas keutamaan tinggi mempunyai pekali pereputan yang lebih rendah. Ini bermakna bahawa masa yang dibenarkan untuk pelaksanaan tugas menggunakan lebih cepat untuk tugas keutamaan rendah berbanding tugas keutamaan tinggi. Ini adalah penyelesaian yang kemas untuk mengelak daripada mengekalkan baris gilir larian berjadual keutamaan.

Penjadualan Kumpulan CFS

Satu lagi aspek menarik CFS ialah konsep penjadualan kumpulan (diperkenalkan dalam kernel 2.6.24). Penjadualan kumpulan ialah satu lagi cara untuk membawa keadilan kepada penjadualan, terutamanya apabila menangani tugasan yang menghasilkan banyak tugas lain. Katakan pelayan yang menghasilkan banyak tugas ingin menyelaraskan sambungan masuk (seni bina biasa untuk pelayan HTTP). Tidak semua tugas dilayan secara seragam dan adil, dan CFS memperkenalkan kumpulan untuk mengendalikan tingkah laku ini. Proses pelayan yang menghasilkan tugas berkongsi masa jalan maya mereka merentas kumpulan (dalam hierarki), manakala tugas individu mengekalkan masa jalan maya bebas mereka sendiri. Dengan cara ini tugasan individu menerima lebih kurang masa penjadualan yang sama seperti kumpulan. Anda akan mendapati bahawa antara muka /proc digunakan untuk mengurus hierarki proses, memberikan anda kawalan sepenuhnya ke atas cara kumpulan dibentuk. Menggunakan konfigurasi ini, anda boleh mengedarkan keadilan merentas pengguna, proses atau variasinya.

Menjadualkan kelas dan domain

Diperkenalkan bersama CFS ialah konsep kelas penjadualan (ingat Gambar 2). Setiap tugasan tergolong dalam kelas penjadualan, yang menentukan cara tugasan itu akan dijadualkan. Kelas penjadualan mentakrifkan set umum fungsi (melalui sched_class），函数集定义调度器的行为。例如，每个调度器提供一种方式， 添加要调度的任务、调出要运行的下一个任务、提供给调度器等等。每个调度器类都在一对一连接的列表中彼此相连，使类可以迭代（例如， 要启用给定处理器的禁用）。一般结构如图 3 所示。注意，将任务函数加入队列或脱离队列只需从特定调度结构中加入或移除任务。 函数 pick_next_task untuk memilih tugas seterusnya untuk dilaksanakan (bergantung pada strategi khusus kelas penjadualan).

Rajah 3. Menjadualkan paparan grafik

Tetapi jangan lupa bahawa kelas penjadualan adalah sebahagian daripada struktur tugas itu sendiri (lihat Rajah 2). Ini memudahkan pengendalian tugas tanpa mengira kelas penjadualan mereka. Contohnya, fungsi berikut mendahului tugas yang sedang dijalankan (di mana curr 定义了当前运行任务， rq 代表 CFS 红黑树而 p ialah tugas seterusnya yang akan dijadualkan) dengan tugasan baharu dalam ./kernel/sched.c:

static inline void check_preempt( struct rq *rq, struct task_struct *p )
{
  rq->curr->sched_class->check_preempt_curr( rq, p );
}

Jika tugas ini menggunakan kelas penjadualan adil, maka check_preempt_curr() 将解析为 check_preempt_wakeup(). Anda boleh melihat perhubungan ini dalam ./kernel/sched_rt.c, ./kernel/sched_fair.c dan ./kernel/sched_idle.c.

Penjadualan kelas ialah satu lagi tempat yang menarik di mana penjadualan berubah, tetapi apabila domain penjadualan meningkat, begitu juga fungsinya. Domain ini membolehkan anda mengumpulkan satu atau lebih pemproses secara hierarki untuk tujuan pengimbangan beban dan pengasingan. Satu atau lebih pemproses boleh berkongsi dasar penjadualan (dan mengekalkan pengimbangan beban antara mereka) atau melaksanakan dasar penjadualan bebas untuk mengasingkan tugas dengan sengaja.

Penjadual lain

Teruskan mempelajari penjadualan dan anda akan menemui penjadual dalam pembangunan yang akan menolak sempadan prestasi dan skalabiliti. Tidak terpengaruh dengan pengalaman Linuxnya, Con Kolivas membangunkan satu lagi penjadual Linux, disingkatkan sebagai: BFS. Penjadual itu dikatakan mempunyai prestasi yang lebih baik pada sistem NUMA dan peranti mudah alih, dan telah diperkenalkan dalam terbitan sistem pengendalian Android.

Melalui artikel ini, anda harus mempunyai pemahaman asas tentang CFS Ia adalah salah satu algoritma penjadualan proses yang paling maju dan cekap dalam sistem Linux Ia menggunakan pokok merah-hitam untuk menyimpan baris gilir proses dan mengira masa berjalan maya keadilan proses, kelajuan tindak balas proses interaktif dipertingkatkan dengan melaksanakan ciri awalan bangun, dengan itu mencapai keadilan lengkap dalam penjadualan proses. Sudah tentu, CFS tidak sempurna Ia mempunyai beberapa masalah dan batasan yang berpotensi, seperti pampasan berlebihan proses tidur aktif, sokongan yang tidak mencukupi untuk proses masa nyata, kurang penggunaan pemproses berbilang teras, dan lain-lain, yang perlu ditangani dalam. versi masa hadapan. Ringkasnya, CFS adalah komponen yang sangat diperlukan dalam sistem Linux dan layak untuk kajian dan penguasaan mendalam anda.

Atas ialah kandungan terperinci Linux CFS: Bagaimana untuk mencapai keadilan lengkap dalam penjadualan proses. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!