Algoritma Penjadwalan mana yang digunakan di Linux?

Baru-baru ini dalam sebuah wawancara saya ditanya tentang algoritma Penjadwalan yang digunakan oleh sistem Operasi Linux. Apa algoritma yang digunakan mengapa?

Juga, algoritma apa yang digunakan dalam sistem operasi waktu-nyata dan mengapa?

Penjadwal tugas Linux saat ini disebut Penjadwal Sepenuhnya Adil (CFS). Anda harus melihat http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt untuk rincian lebih lanjut. Desainnya cukup kompleks dan menurut saya tidak cocok untuk RTOS.

Teknik umum dalam sistem realtime adalah penjadwalan rate-monoton, karena memiliki jaminan yang kuat jika asumsi tertentu berlaku (misalnya prioritas tugas statis dan waktu dan laju eksekusi tetap). Ada banyak algoritma lain dan telah banyak penelitian. Jadi pada dasarnya ini semua tentang properti yang Anda butuhkan dan apa yang Anda ketahui tentang tugas Anda dan apa yang diperbaiki.

Saya tidak yakin, apakah Anda mempertimbangkan penjadwalan I / O Kernel. Jika Anda tidak: Abaikan jawaban ini.

Wikipedia menyatakan, bahwa CFG (sepenuhnya Antrian Cukup) adalah default sejak Kernel 2.6.18.

Di openSUSE saya (menjalankan Kernel 2.6.37) saya dapat beralih antara CFG, NOOP , dan Tenggat .

Algoritma Round Robin umumnya digunakan dalam lingkungan berbagi waktu.

Algoritme yang digunakan oleh penjadwal Linux adalah skema yang kompleks dengan kombinasi prioritas preemptif dan pemotongan waktu yang bias. Ini menetapkan kuantum waktu yang lebih lama untuk tugas-tugas prioritas yang lebih tinggi dan kuantum waktu yang lebih pendek untuk tugas-tugas prioritas yang lebih rendah.

Ini mengidentifikasi setiap proses baik sebagai proses waktu nyata atau proses normal (lainnya). Tugas waktu nyata diberikan prioritas statis dalam kisaran [0,99], di mana angka yang lebih rendah menunjukkan prioritas yang lebih tinggi.

Semua tugas lain memiliki prioritas dinamis dalam kisaran [100.139], berdasarkan pada interaktivitas tugas yang didasarkan pada nilai bagusnya plus atau minus nilai 5. Tugas yang lebih interaktif biasanya memiliki waktu tidur lebih lama dan oleh karena itu lebih mungkin untuk memiliki penyesuaian lebih dekat ke −5, karena penjadwal menyukai tugas-tugas interaktif. (Interaktivitas tugas ditentukan oleh berapa lama ia telah tidur sambil menunggu I / O.) Interaktivitas tugas menentukan apakah nilai 5 akan ditambahkan ke atau dikurangi dari nilai bagus. Hasil penyesuaian tersebut akan menjadi prioritas yang lebih tinggi untuk tugas-tugas ini. Sebaliknya, tugas-tugas dengan waktu tidur yang lebih singkat seringkali lebih terikat CPU dan karenanya akan menurunkan prioritasnya.

Kernel menyimpan daftar semua tugas yang bisa dijalankan dalam struktur data runqueue. Runqueue berisi dua array prioritas: aktif dan kedaluwarsa. Array aktif berisi semua tugas dengan sisa waktu dalam irisan waktu mereka, dan array yang kadaluarsa berisi semua tugas yang kadaluwarsa. Masing-masing array prioritas ini berisi daftar tugas yang diindeks berdasarkan prioritas. Penjadwal memilih tugas dengan prioritas tertinggi dari array aktif untuk dieksekusi pada CPU. Ketika semua tugas telah menghabiskan irisan waktu mereka (yaitu, array aktif kosong), dua array prioritas dipertukarkan: array kadaluarsa menjadi array aktif, dan sebaliknya.

Prioritas dinamis tugas dihitung ulang ketika tugas tersebut telah menghabiskan kuantum waktunya dan akan dipindahkan ke array yang sudah kadaluwarsa. Jadi, ketika dua array dipertukarkan, semua tugas dalam array aktif baru telah diberi prioritas baru dan irisan waktu yang sesuai. (Catatan: Ini adalah kutipan dari buku tentang Konsep Sistem Operasi (edisi ke-9) oleh Abraham Silberschatz, dkk. Untuk perinciannya silakan baca bagian 5.6.3 dari buku ini)

Ini adalah jawaban untuk pertanyaan Anda yang lain. Sistem waktu nyata (RTS) terdiri dari dua jenis, keras dan lunak. Algoritma penjadwalan CPU untuk hard RTS adalah algoritma preemptive berbasis prioritas dan untuk soft RTS adalah prioritas non-preemptive.