Penjadwalan

Penjadwalan adalah suatu pekerjaan yang dilakukan untuk mengalokasikan CPU time untuk tasks yang berbeda-beda dalam sistem operasi. Pada umumnya, kita berfikir penjadwalan sebagai menjalankan dan menginterupsi suatu proses, untuk linux ada aspek lain yang penting dalam penjadwalan: seperti menjalankan dengan berbagai kernel tasks . Kernel tasks meliputi task yang diminta oleh proses yang sedang dijalankan dan tasks yand dieksekusi internal menyangkut device driver yang berkepentingan.

Sinkronisasi Kernel

Cara penjadwalan kernel pada operasinya secara mendasar berbeda dengan cara penjadwalan suatu proses. Terdapat dua cara agar sebuah permintaan akan eksekusi kernel-mode dapat terjadi. Sebuah program yang berjalan dapat meminta service sistem operasi, dari system call ataupun secara implisit (untuk contoh:ketika page fault terjadi). Sebagai alternatif, device driver dapat mengirim interupsi perangkat keras yang menyebabkan CPU memulai eksekusi kernel-define handler untuk suatu interupsi.

Problem untuk kernel muncul karena berbagai tasks mungkin mencoba untuk mengakses struktur data internal yang sama. Jika hanya satu kernel task ditengah pengaksesan struktur data ketika interupsi service routine dieksekusi, maka service routine tidak dapat mengakses atau merubah data yang sama tanpa resiko mendapatkan data yang rusak. Fakta ini berkaitan dengan ide dari critical section (baca sinkronisasi proses).

Sehagai hasilnya, sinkronisasi kernel melibatkan lebih banyak dari hanya penjadwalan proses saja. sebuah framework dibutuhkan untuk memperbolehkan kernel's critical sections berjalan tanpa diinterupsi oleh critical section yang lain.

Solusi pertama yang diberikan oleh linux adalah membuat normal kernel code nonpreemptible (baca proses). Biasanya, ketika sebuah timer interrupt diterima oleh kernel, membuat penjadwalan proses, kemungkinan besar akan menunda eksekusi proses yang sedang berjalan pada saat itu dan melanjutkan menjalankan proses yang lain. Biar bagaimanapun, ketika timer interrupt diterima ketika sebuah proses mengeksekusi kernel-system service routine, penjadwalan ulang tidak dilakukan secara mendadak; cukup, kernel need_resched flag terset untuk memberitahu kernel untuk menjalankan penjadwalan kembali setelah system call selesai dan control dikembalikan ke user mode.

Sepotong kernel code mulai dijalankan, akan terjamin bahwa itu adalah satu-satunya kernel code yang dijalankan sampai salah satu dari aksi dibawah ini muncul:

Interupsi adalah suatu masalah bila mengandung critical section-nya sendiri. Timer interrupt tidak secara langsung menyebabkan terjadinya penjadwalan ulang suatu proses; hanya meminta suatu jadwal untuk dilakukan kemudian, jadi kedatangan suatu interupsi tidak mempengaruhi urutan eksekusi dari noninterrupt kernel code . Sekali interrupt service selesai, eksekusi akan menjadi lebih simpel untuk kembali ke kernel code yang sedang dijalankan ketika interupsi mengambil alih.

Page faults adalah suatu masalah yang potensial; jika sebuah kernel routine mencoba untuk membaca atau menulis ke user memory, akan menyebabkan terjadinyapage fault yang membutuhkan I/O disk untuk selesai, dan proses yang berjalan akan di tunda sampai I/O selesai. Pada kasus yang hampir sama, jika system call service routine memanggil penjadwalan ketika sedang berada di mode kernel, mungkin secara eksplisit dengan membuat direct call pada code penjadwalan atau secara implisit dengan memanggil sebuah fungsi untuk menunggu I/O selesai, setelah itu proses akan menunggu dan penjadwalan ulang akan muncul. Ketika proses jalan kembali, proses tersebut akan melanjutkan untuk mengeksekusi dengan mode kernel, melanjutkan intruksi setelah call (pemanggilan) ke penjadwalan.

Kernel code dapat terus berasumsi bahwa ia tidak akan diganggu (preemted) oleh proses lainnya dan tidak ada tindakan khusus dilakukan untuk melindungi critical section. Yang diperlukan adalah critical section tidak mengandung referensi ke user memory atau menunggu I/O selesai.

Teknik kedua yang di pakai Linux untuk critical section yang muncul pada saat interrupt service routines . Alat dasarnya adalah perangkat keras interrupt-control pada processor. Dengan meniadakan interupsi pada saat critical section, maka kernel menjamin bahwa ia dapat melakukan proses tanpa resiko terjadinya ketidak-cocokan akses dari struktur data yang di share.

Untuk meniadakan interupsi terdapat sebuah pinalti. Pada arsitektur perangkat keras kebanyakan, pengadaan dan peniadaan suatu interupsi adalah sesuatu yang mahal. Pada prakteknya, saat interupsi ditiadakan, semua I/O ditunda, dan device yang menunggu untuk dilayani akan menunggu sampai interupsi diadakan kembali, sehingga kinerja meningkat. Kernel Linux menggunakan synchronization architecture yang mengijinkan critical section yang panjang dijalankan untuk seluruh durasinya tanpa mendapatkan peniadaan interupsi. Kemampuan secara spesial berguna pada networking code : Sebuah interupsi pada network device driver dapat memberikan sinyal kedatangan dari keseluruhan paket network, dimana akan menghasilkan code yang baik dieksekusi untuk disassemble, route, dan forward paket ditengah interrupt service routine.

Linux mengimplementasikan arsitektur ini dengan memisahkan interrupt service routine menjadi dua seksi: the top half dan the bottom half. The top half adalah interupsi yang normal, dan berjalan dengan rekursif interupt ditiadakan ( interupsi dengan prioritas yang lebih tinggi dapat menginterupsi routine, tetapi interupsi dengan prioritas yang sama atau lebih rendah ditiadakan). The bottom half service routine berjalan dengan semua interupsi diadakan, oleh miniatur penjadwalan yang menjamin bahwa bottom halves tidak akan menginterupsi dirinya sendiri. The bottom half scheduler dilakukan secara otomatis pada saat interupt service routine ada.

Pemisahan itu berarti bahwa kegiatan proses yang komplek dan harus selesai diberi tanggapan untuk suatu interupsi dapat diselesaikan oleh kernel tanpa kecemasan tentang diinterupsi oleh interupsi itu sendiri. Jika interupsi lain muncul ketika bottom half dieksekusi, maka interupsi dapat meminta kepada bottom half yang sama untuk dieksekusi, tetapi eksekusinya akan dilakukan setelah proses yang sedang berjalan selesai. Setiap eksekusi dari bottom half dapat di interupsi oleh top half tetapi tidak dapat diinterupsi dengan bottom half yang mirip.

Arsitektur Top-half bottom-half komplit dengan mekanisme untuk meniadakan bottom halver yang dipilih ketika dieksekusi secara normal, foreground kernel code. Kernel dapat meng-codekan critical section secara mudah dengan mengunakan sistem ini: penanganan interupsi dapat meng-codekan critical section-nya sebagai bottom halves, dan ketika foreground kernel ingin masuk ke critical section , setiap bottom halves ditiadakan untuk mencegah critical section yang lain diinterupsi. Pada akhir dari critical section, kernel dapat kembali mengadakan bottom halves dan menjalankan bottom half tasks yang telah di masukkan kedalam queue oleh top half interrupt service routine pada saat critical section .

Penjadwalan Proses

Ketika kernel telah mencapai titik penjadwalan ulang, entah karena terjadi interupsi penjadwalan ulang maupun karena proses kernel yang sedang berjalan telah diblokir untuk menunggu beberapa signal bangun, harus memutuskan proses selanjutnya yang akan dijalankan. Linux telah memiliki dua algoritma penjadwalan proses yang terpisah satu sama lain. Algoritma yang pertama adalah algoritma time-sharing untuk penjadwalan preemptive yang adil diantara sekian banyak proses. Sedangkan algoritma yang kedua didesain untuk tugas real-time dimana proritas mutlak lebih utama daripada keadilan mendapatkan suatu pelayanan.

Bagian dari tiap identitas proses adalah kelas penjadwalan, yang akan menentukan algoritma yang digunakan untuk tiap proses. Kelas penjadwalan yang digunakan oleh Linux, terdapat dalam standar perluasan POSIX untuk sistem komputer waktu nyata.

Untuk proses time-sharing, Linux menggunakan teknik prioritas, sebuah algoritma yang berdasarkan pada kupon. Tiap proses memiliki sejumlah kupon penjadwalan; dimana ketika ada kesempatan untuk menjalankan sebuah tugas, maka proses dengan kupon terbanyaklah yang mendapat giliran. Setiap kali terjadi interupsi waktu, proses yang sedang berjalan akan kehilangan satu kupon; dan ketika kupon yang dimiliki sudah habis maka proses itu akan ditunda dan proses yang lain akan diberikan kesempatan untuk masuk.

Jika proses yang sedang berjalan tidak meiliki kupon sama sekali, linux akan melakukan operasi pemberian kupon, memberikan kupon kepada tiap proses dalam sistem, dengan aturan main: kupon = kupon / 2 + prioritas Algoritma ini cenderung untuk menggabungkan dua faktor yang ada: sejarah proses dan prioritas dari proses itu sendiri. Satu setengah dari kupon yang dimiliki sejak operasi pembagian kupon terakhir akan tetap dijaga setelah algoritma telah dijalankan, menjaga beberapa sejarah sikap proses. Proses yang berjalan sepanjang waktu akan cenderung untuk menghabiskan kupon yang dimilikinya dengan cepat, tapi proses yang lebih banyak menunggu dapat mengakumulasi kuponnya dari. Sistem pembagian kupon ini, akan secara otomatis memberikan proritas yang tinggi ke proses I/O bound ataupun interaktif, dimana respon yang cepat sangat diperlukan.

Kegunaan dari proses pemberian prioritas dalam menghitung kupon baru, membuat prioritas dari suatu proses dapat ditingkatkan. Pekerjaan background batch dapat diberikan prioritas yang rendah; proses tersebut akan secara otomatis menerima kupon yang lebih sedikit dibandingkan dengan pekerjaan yang interaktif, dan juga akan menerima persentase waktu CPU yang lebih sedikit dibandingan dengan tugas yang sama dengan prioritas yang lebih tinggi. Linux menggunakan sistem prioritas ini untuk menerapkan mekanisme standar pembagian prioritas proses yang lebih baik.

Penjadwalan waktu nyata Linux masih tetap lebih sederhana. Linux, menerapkan dua kelas penjadwalan waktu nyata yang dibutuhkan oleh POSIX 1.b: First In First Out dan round-robin. Pada keduanya, tiap proses memiliki prioritas sebagai tambahan kelas penjadwalannya. Dalam penjadwalan time-sharing , bagaimanapun juga proses dengan prioritas yang berbeda dapat bersaing dengan beberapa pelebaran; dalam penjadwalan waktu nyata, si pembuat jadwal selalu menjalankan proses dengan prioritas yang tinggi. Diantara proses dengan prioritas yang sama, maka proses yang sudah menunggu lama, akan dijalankan. Perbedaan satu - satunya antara penjadwalan FIFO dan round-robin adalah proses FIFO akan melanjutkan prosesnya sampai keluar ataupun diblokir, sedangkan proses round-robin akan dipreemptivekan setelah beberapa saat dan akan dipindahkan ke akhir antrian, jadi proses round-robin dengan prioritas yang sama akan secara otomatis membagi waktu jalan antar mereka sendiri.

Perlu diingat bahwa penjadwalan waktu nyata di Linux memiliki sifat yang lunak. Pembuat jadwal Linux menawarkan jaminan yang tegas mengenai prioritas relatif dari proses waktu nyata, tapi kernel tidak menjamin seberapa cepat penjadwalan proses waktu-nyata akan dijalankan pada saat proses siap dijalankan. Ingat bahwa kode kernel Linux tidak akan pernah bisa dipreemptive oleh kode mode pengguna. Apabila terjadi interupsi yang membangunkan proses waktu nyata, sementara kernel siap untuk mengeksekusi sebuah sistem call sebagai bagian proses lain, proses waktu nyata harus menunggu sampai sistem call yang sedang dijalankan selesai atau diblokir.

Symmetric Multiprocessing

Kernel Linux 2.0 adalah kernel Linux pertama yang stabil untuk mendukung perangkat keras symmetric multiprocessor (SMP). Proses maupun thread yang berbeda dapat dieksekusi secara paralel dengan processor yang berbeda. Tapi bagaimana pun juga untuk menjaga kelangsungan kebutuhan sinkronisasi yang tidak dapat dipreemptive dari kernel, penerapan SMP ini menerapkan aturan dimana hanya satu processor yang dapat dieksekusi dengan kode mode kernel pada suatu saat. SMP menggunakan kernel spinlock tunggal untuk menjalankan aturan ini. Spinlock ini tidak memunculkan permasalahan untuk pekerjaan yang banyak menghabiskan waktu untuk menunggu proses komputasi, tapi untuk pekerjaan yang melibatkan banyak aktifitas kernel, spinlock dapat menjadi sangat mengkhawatirkan.

Sebuah proyek yang besar dalam pengembangan kernel Linux 2.1 adalah untuk menciptakan penerapan SMP yang lebih masuk akal, dengan membagi kernel spinlock tunggal menjadi banyak kunci yang masing - masing melindungi terhadap masuknya kembali sebagian kecil data struktur kernel. Dengan menggunakan teknik ini, pengembangan kernel yang terbaru mengijinkan banyak processor untuk dieksekusi oleh kode mode kernel secara bersamaan.