Preemptive Scheduling for Distributed Systems

Penjadwalan Preemptive pada Sistem Terdistribusi
Ringkasan oleh : Nurul Huda (41508110133)

Umumnya sistem operasi multitasking menggunakan penjadwalan preemptive. Banyak sistem multiprosessor juga menggunakan penjadwalan preemptive intertask ketika melakukan komputasi paralel. Namun, penjadwalan preemptive pada sistem terdistribusi sangat jarang, bahkan hampir tidak ada.

Penjadwalan Preemptive adalah kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. Melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya.

Contoh Penjadwalan Preemptive : Penjadwalan CPU yang dijalankan ketika proses dalam keadaan:

• Berubah dari running ke ready state.
• Berubah dari waiting ke ready state.

Sedangkan Sistem Terdistribusi adalah Kumpulan komputer yang terhubung melalui sistem jaringan komputer dan dilengkapi dengan sistem software terdistribusi untuk membentuk fasilitas komputer terintegrasi.
Kendala Implementasi Penjadwalan Preemptive pada sistem terdistribusi adalah dibutuhkan proses migrasi yang tepat, panjang task yang bervariasi, kecepatan dan beban kerja prosesor bervariasi, sehingga diperlukan algoritma penjadwalan yang tepat.
Pusat implementasi dari protokol penjadwalan preemptive adalah mekanisme dari migrasi proses. Mekanisme Migrasi : Anggap sebuah worker sedang mengeksekusi task T1 pada mesin M1. Sekarang penjadwal ingin memindah T1 ke mesin M2. Untuk memperoleh keadaan ini perlu migrasi proses. Jika ada sebuah worker sudah running pada M2, hanya context pada thread aplikasi (yang mewakili context pada task yang sedang dieksekusi) yang perlu di transfer dari M1 ke M2. Jadi, migrasi task mencapai penjadwalan preemptive.
Pada contoh diatas, pertama kali, penjadwal (pada manajer) memberitahukan thread asinkron (pada worker) di M1 untuk membekukan T1. Thread asinkron kemudian memberitahukan thread kontrol, yang akan mensuspend thread aplikasi yang sedang berjalan pada T1. Thread kontrol kemudian mengambil context pada thread aplikasi dan memaketkannya dan mengirimnya ke manajer. Manajer kemudian mengirim context dari T1 ke thread kontrol pada M2. Thread kontrol pada M2 mengumpulkan context dari thread aplikasinya untuk menerima context dan me-resume-nya. Sekarang T1 di-resume pada M2.
Implementasi yang kami lakukan untuk pengujian Penjadwalan Preemptive pada Sistem Terdistribusi menggunakan :

• Pemrosesan paralel menggunakan Sistem Chime
• Tiga sistem komputer Prosesor Pentium II 266, memori 128Mbyte, terkoneksi menggunakan kartu Ethernet 100Mb/s.
• Sistem operasi : Windows NT 4.0.
• Kompiler : Visual C++ 4.0.
• Menggunakan 4 algoritma penjadwalan.
• Aplikasi yang dipakai untuk menguji algoritma : Ray Tracing dan Perkalian Matrix.

4 algoritma penjadwalan yang diujicobakan untuk menjalankan aplikasi :

1. Penjadwalan optimal : penjadwalan yang diperhitungkan sebelumnya, secara teoretis waktu runtime paling pendek, dengan jumlah penjadwalan yang paling sedikit. Setiap mesin, dan setiap task harus identik. Bekerja paling baik ketika jumlah task lebih banyak daripada jumlah mesin.
2. Penjadwalan Eager Setiap mesin m mendapat satu task n. ketika satu task selesai, mesin mendapat penugasan dari task lain. Ketika satu task selesai, mesin mendapat task lain yang belum ditugaskan. Jika semua task selesai ditugaskan, task-task yang belum selesai ditugaskan kembali ke mesin ini.
3. Penjadwalan Round Robin : dari sejumlah n task, sebanyak m task akan ditugaskan ke sejumlah m mesin. Setelah satu quantum waktu, semua m task di preempt dan kemudian m task berikutnya ditugaskan (secara berulang).
4. Task Bunching : sejumlah n task dibagi (bunched) kedalam sekumpulan m mesin. Setiap mesin menjalankan satu bunch task secara sekuensial. Ketika satu bunch task selesai, setiap bunch task dipreempt lagi, task-task tersebut dibagi-bagi lagi ke mesin-mesin dan eksekusi diulang.

Untuk menjamin perbandingan yang adil, pertama kali kami menjalankan program paralel ini secara sekuensial menggunakan C++ . Program sekuensial membutuhkan 540 detik pada single prosesor. Hasil performa ditampilkan pada gambar 1.
Program menjalankan program paralel very coarse grained, dimana perkalian matrix dikerjakan oleh 5 task. Sebuah coarse grain mengeksekusi 10 task, medium grained mengeksekusi 20 task dan very fine grain mengeksekusi 1500 task. Quantum waktu Round Robin diset 15 detik.
Ketika melibatkan perhitungan 5 task pada 3 mesin. Penjadwalan Eager bekerja sangat buruk. Namun, penjadwalan Optimal dan Round Robin berjalan dengan baik. Task bunching tidak berjalan, karena tidak ada yang bisa di bunch. Pada pengujian selanjutnya Penjadwalan Optimal tidak dipakai karena tidak sesuai untuk jumlah task yang jauh lebih besar daripada jumlah mesin.
Untuk coarse grain, digunakan 10 task. Bagus pada Round Robin dan Task Bunching namun sedikit buruk pada penjadwalan Eager karena penjadwalan Eager adalah non-preemptive dan jumlah task bukan perkalian dari jumlah mesin.
Untuk level lapangan, digunakan 21 task. Penjadwalan Eager bekerja dengan baik seperti yang lain – namun Round Robin agak sedikit buruk, karena mempunyai lebih banyak overhead preemption dibanding yang lain.

Gambar 1. Performa penjadwalan preemptive

Pada task fine grained – menggunakan 1500 task. Round Robin dan Eager menjadi sama, dimana quantum waktu tidak pernah expired. Namun, overhead dari penugasan task pada worker mendominasi waktu komputasi, sehingga performa menjadi buruk. Tetapi total waktu yang didapat masih lebih pendek daripada waktu sekuensial (540 detik). Untuk komputasi fine-grained, task bunching digunakan bersama preemption menghasilkan performa yang bagus pada beberapa range ukuran.

Kesimpulan : Optimal bekerja bagus jika informasi waktu eksekusi diketahui terlebih dahulu, dan jumlah task tidak jauh lebih banyak daripada jumlah mesin. Round Robin bagus pada jumlah task yang tidak terlalu besar. Task Bunching memberikan performa paling baik pada beberapa ukuran komputasi.