Algoritma Penjadwalan Proses

Algoritma-Algoritma Penjadwalan Proses

Terdapat banyak algoritma penjadwalan, baik algoritma penjadwalan nonpreemptive maupun penjadwalan preemptive.
Algoritma-algoritma yang menerapkan strategi nonpreemptive diantaranya :

 FIFO (First-In, First-Out) atau FCFS (First-Come, First-Serve)

SJF (Shortest Job First)

Algoritma-algoritma yang menerapkan strategi preemptive diantaranya :

RR (Round-Robin)

MFQ (Multiple Feedback Queues)

SRF (Shortest-Remaining-First)

HRN (Highest-Remaining-Next)

PS (Priority Schedulling)

GS (Guaranteed Schedulling)

Klasifikasi lain selain berdasarkan dapat/tidaknya suatu proses diambil alih secara paksa adalah klasifikasi yang berdasarkan adanya prioritas diproses-proses, yaitu :

Algoritma penjadwalan tanpa berprioritas

Algoritma penjadwalan berprioritas, terdiri dari :

Algoritma penjadwalan berprioritas statis

Algoritma penjadwalan berprioritas dinamis

Algoritma-Algoritma Penjadwalan Proses

Penjadwalan Round-Robin (RR)

Penjadwalan FIFO (FIFO)

Penjadwalan Berprioritas (PS)

Penjadwalan yang Terpendek yang Lebih Dahulu (SJF)

Penjadwalan dengan Banyak Antrian (MFQ)

Penjadwalan dengan Sisa Waktu Terpendek, Lebih Dahulu (SRF)

Penjadwalan Rasio Tanggapan Tertinggi, Lebih Dahulu(HRN)

Penjadwalan Terjamin (GS)

Penjadwalan Round Robin
Penjadwalan Round Robin merupakan

Penjadwalan Preemptive, namun proses tidak di-preempt secara langsung oleh proses lain, namun oleh penjadwal berdasarkan lama waktu berjalannya suatu proses. Maka penjadwalan ini disebut preempt-by-time

Penjadwalan tanpa prioritas

Semua proses dianggap penting dan diberi jumlah waktu pemroses yang disebut kwanta (quantum) atau time-slice tempat proses tsb berjalan. Proses berjalan selama 1 kwanta, kemudian penjadwal akan mengalihkan kepada proses berikutnya juga untuk berjalan satu kwanta, begitu seterusnya sampai kembali pada proses pertama dan berulang.

Ketentuan algoritma round robin adalah sbb :

Jika kwanta habis dan proses belum selesai maka proses Runing menjadi Ready dan pemroses dialihkan ke proses lain

Jika kwanta belum habis dan proses menunggu suatu kejadian (misalnya menunggu selesainya suatu operasi I/O), maka proses Running menjadi Blocked dan pemroses dialihkan ke proses lain.

Jika kwanta belum habis tapi proses telah selesai maka proses Running itu diakhiri dan pemroses dialihkan ke proses lain

Algoritma penjadwalan ini dapat diimplementasi sbb :

Sistem mengelola senarai proses Ready sesuai urutan kedatangannya

Sistem mengambil proses yang berada di ujung depan antrian Ready menjadi Running

Bila kwanta belum habis dan proses selesai maka sistem mengambil proses di ujung depan antrian proses Ready

Jika kwanta habis dan proses belum selesai maka ditempatkan proses Running ke ekor antrian proses Ready dan sistem mengambil proses di ujung depan antrian proses Ready

Masalah penjadwalan ini adalah dalam hal menentukan besar kwanta, yaitu :

Kwanta terlalu besar menyebabkan waktu tanggap besar dan turn arround time rendah

Kwanta terlalu kecil mengakibatkan peralihan proses terlalu banyak sehingga menurunkan efisiensi pemroses

Harus diterapkan besar kwanta waktu yang optimal berdasarkan kebutuhan sistem, terutama dari hasil percobaan atau data historis dari sistem. Besar kwanta waktu beragam yang bergantung beban sistem.
Berdasarkan kriteria penilaian penjadwalan

Fairness, penjadwalan RR adil bila dipandang dari persamaan pelayanan oleh pemroses

Efisiensi, penjadwalan ini cenderung efisien pada sistem interatif

Respons Time(waktu tanggap), penjadwalan ini memuaskan untuk sistem interaktif, tidak memadai untuk sistem waktu nyata.Turn arround Time, penjadwalan RR cukup bagus

 Throughput, penjadwlan RR cukup bagus

Penjadwalan FIFO
Penjadwalan FIFO merupakan :

Penjadwalan non preemptive (run-to-completion)

Penjadwalan tidak berprioritas

Penjadwal FIFO adalah penjadwalan dengan ketentuan-ketentuan paling sederhana, yaitu :

Proses-proses diberi jatah waktu pemroses diurutkan berdasarkan waktu kedatangan proses-proses itu ke sistem.

Begitu proses mendapat jatah waktu pemroses, proses dijalankan sampai selesai

Penjadwalan ini dikatakan adil dalam arti resmi, tapi dikatakan tidak adil karena proses yang memerlukan waktu lama membuat proses pendek menunggu. Proses tidak penting dapat membuat proses penting menjadi menunggu.
FIFO jarang digunakan secara mandiri tapi dikombinasikan dengan skema lain, misalnya keputusan berdasarkan prioritas proses, sedangkan untuk proses berprioritas sama diputuskan berdasarkan FIFO.

Berdasarkan kriteria penilaian penjadwalan :

Fairness, penjadwalan FIFO adil dalam arti resmi

Efisiensi, FIFO sangat efisien dalam penggunaan pemroses

Waktu tanggap, penjadwalan sangat tidak memuaskan karena proses dapat menunggu lama. Tidak cocok untuk sistem interaktifTurn arround time, penjadwalan FIFO tidak bagus

 Throughput, penjadwalan FIFO tidak bagus.

Penjadwalan Berprioritas
Gagasan penjadwalan adalah masing-masing proses diberi prioritas dan proses berprioritas tertinggi menjadi Running (yaitu mendapat jatah waktu pemroses).
Prioritas dapat diberikan secara

Prioritas statis (static priorities), prioritas tak berubah.

keunggulan : Mudah diimplementasikan dan mempunyai overhead relatif kecil
kelemahan : penjadwalan prioritas statis tidak tanggap perubahan lingkungan yang mungkin menghendaki penyesuaian prioritas

Prioritas dinamis (dynamic priorities), mekanisme menanggapi perubahan lingkungan sistem saat beroperasi di lingkungan nyata. Prioritas awal yang diberikan ke proses mungkin hanya berumur pendek. Dalam hal ini sistem dapat menyesuaikan nilai prioritasnya ke nilai yang lebih tepat sesuai lingkungan.

keunggulan : waktu tanggap sistem yang bagus
kelemahan : implementsi mekanisme prioritas dinamis lebih kompleks dan mempunyai overhead yang lebih besar dibanding mekanisme prioritas statik.

Contoh penjadwalan berprioritas
Proses-proses yang sangat banyak operasi masukan/keluaran dan menghabiskan kebanyakan waktu proses untuk menunggu selesainya operasi masukan/ keluaran. Proses demikian disebut I/O bound process. Proses-proses ini dapat diberi prioritas sangat tinggi sehingga begitu proses-proses memerlukan pemroses, segera saja diberikan dan proses akan segera memulai permintaaan masukan/keluaran berikutnya sehingga menyebabkan proses Blocked menunggu selesainya operasi masukan/keluaran. Dengan demikian pemroses segera dialihkan, dapat dipergunakan oleh proses lain tanpa mengganggu proses I/O bound. Proses I/O bound berjalan paralel bersama proses lain yang benar-benar memerlukan pemroses.

Proses-proses yang sangat banyak operasi masukan/keluaran jika harus menunggu lama untuk memakai pemroses(karena diberi prioritas rendah) hanya akan membebani memori, karena sistem harus menyimpan tanpa perlu proses-proses itu di memori karena tidak selesai-selesai menunggu operasi masukan/keluaran dan menunggu jatah pemroses.

Algoritma Prioritas Dinamis
Algoritma ini dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu yang menjadi tujuan sistem komputer.
Algoritma sederhana yang memberi layanan yang baik adalah dengan menge-set proses dengan prioritas berdasarkan rumus nilai 1/f bahwa f adalah rasio kwanta terakhir yang digunakan proses.

Proses yang menggunakan 2 milidetik, kwanta 100 ms maka prioritasnya 50

Proses yang berjalan selama 50 milidetik sebelum Blocked berprioritas 2

Proses yang menggunakan seluruh kwanta berprioritas 1

Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layanan yang adil dari pemroses dalam arti jumlah waktu pemroses yang sama untuk masing-masing pemroses pada satu waktu.
Biasanya memenuhi kebijaksanaan yang ingin mencapai level maksimal berdasarkan suatu kriteria tertentu di sistem.

Algoritma penjadwalan berprioritas dapat dikombinasikan yaitu dengan mengelompokkan proses-proses menjadi kelas-kelas prioritas. Penjadwalan berprioritas diterapkan antar kelas- kelas proses itu. Penjadwlan round-robin atau penjadwalan FIFO diterapkan pada proses-proses di dalam satu kelas.

Penjadwalan yang Terpendek yang Lebih Dahulu (SJF)
Penjadwalan SJF ini merupakan

Penjadwalan non preemptive

Penjadwalan dapat dikatakan sebagai berprioritas. Di SJF, prioritas diasosiasikan dengan masing-masing proses dan pemroses dialokasikan ke proses dengan prioritas tertinggi. Proses-proses dengan prioritas yang sama akan dijadwalkan secara FIFO.

Penjadwalan ini mengasumsikan waktu jalan proses (sampai selesai) atau waktu lamanya proses diketahui sebelumnya. Mekanisme penjadwlan SJF adalah lebih dulu menjadwalkan proses dengan waktu jalan terpendek sampai selesai. Setelah proses itu selesai, maka proses dengan waktu jalan terpendek berikutnya dijadwalkan. Demikian seterusnya.
Keunggulan : penjadwalan SJF mempunyai efisiensi tinggi dan turn arround time rendah.

Contoh : Terdapat 4 proses A,B,C,D dengan waktu jalan selama 8,7,6,5 kwanta.
Gambar (a) menunjukkan penjadwalan cara I, dengan proses-proses dijadwalkan berurutan sebagai A,B,C,D. Gambar (b) menujukkan bila proses dijadwalkan secara SJF yaitu berurutan D,C,B,A.

Kedua cara menghasilkan turn arround time yang ditunjukkan pada gambar (c). Cara I turn arround time rata-rata adalah 17,5 kwanta, sedangkan cara II adalah 15 kwanta
Walaupun mempunyai turn arround yang bagus, SJF mempunyai masalah, yaitu

Tidak dapat mengetahui ukuran proses saat proses masuk

Proses tidak datang bersamaan sehingga penetapannya harus dinamis

Untuk mengetahui ukuran lama proses agar dapat ditetapkan yang terpendek, biasanya dilakukan dengan cara pendekatan. Pendekatan yang biasa dilakukan adalah dengan membuat estimasi berdasarkan perilaku historis sistem. Merupakan kajian teoritis untuk pembandingan dalam pembandingan turn arround time.

Penjadwal dengan Banyak Antrian (MFQ)
Penjadwalan MFQ ini merupakan

Penjadwalan preemptive

Penjadwalan berprioritas dinamis

Sasaran penjadwalan ini adalah untuk mencegah banyaknya aktivitas swapping. Cara yang dilakukan adalah dengan

Proses-proses yang sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu yang lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu waktu.

Penjadwalan ini menghendaki kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya lagi berjalan empat kwanta, kelas berikutnya-berikutnya lagi berjalan delapan kwanta dan seterusnya.

Ketentuan yang berlaku adalah sebagai berikut :

Jalankan proses-proses yang berada pada kelas prioritas tertinggi

Jika proses telah menggunakan seluruh kwanta yang dialokasikan maka proses itu diturunkan kelas prioritasnya

Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi

Penjadwalan dengan Sisa Waktu Terpendek, Lebih Dahulu (SRF)
Penjadwalan ini merupakan

Penjadwalan preemptive

Penjadwalan berprioritas dinamis

Penjadwalan SRF merupakan perbaikan dari SJF, SJF merupakan penjadwalan nonpreemptive sedang SRF adalah preemptive yang dapat digunakan untuk sistem timesharing.
Pada SRF, proses dengan sisa waktu jalan diestimasi terendah dijalankan, termasuk proses-proses yang baru tiba.

Perbedaan SRF dengan SJF

Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai

Pada SRF proses yang sedang berjalan (Running) dapat diambil alih oleh proses baru dengan sisa waktu jalan yang diestimasi lebih rendah

SRF mempunyai overhead yang lebih besar dibanding SJF. SRF memerlukan penyimpanan waktu layanan yang telah dihabiskan proses dan kadang-kadang harus menangani peralihan.

Tibanya proses-proses kecil akan segera dijalankan

Proses-proses lebih lama berarti dengan lama dan variasi waktu tunggu lebih lama dibanding dengan SJF

Secara teoretis, SRF memberi waktu tunggu minimum tapi karena adanya overhead peralihan, maka pada situasi tertentu SJF bisa memberi kinerja yang lebih baik dibanding SRF.

Penjadwalan Rasio Tanggapan Tertinggi, Lebih Dahulu (HRN)
Penjadwalan HRN ini merupakan :

Penjadwalan non preemptive

Penjadwalan berprioritas dinamis

Penjadwalan ini juga untuk mengkoreksi kelemahan SJF. HRN adalah strategi penjadwalan non preemptive dengan prioritas proses tidak hanya merupakan fungsi dari waktu layanan, tapi juga jumlah waktu tunggu proses. Prioritas dinamis HRN dihitung berdasarkan rumus berikut :

Prioritas = (waktu tunggu + waktu layanan) / waktu layanan

Karena waktu layanan muncul sebagai pembagi maka proses yang lebih pendek mempunyai prioritas yang lebih baik. Karena waktu tunggu sebagai pembilang maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus untuk memperoleh layanan pemroses.
Disebut HRN (High respons next) karena waktu tanggap adalah (waktu tunggu + waktu layanan). Ketentuan HRN berarti agar memperoleh waktu tanggap tertinggi yang harus dilayani.

Penjadwalan Terjamin (GS)
Penjadwal GS ini adalah

Penjadwalan preemptive

Penjadwalan berprioritas dinamis

Penjadwalan ini berupaya memberi masing-masing pemakai daya pemroses yang sama. Jika terdapat N pemakai maka tiap pemakai diupayakan mendapat 1/N daya pemroses. Sistem merekam banyak waktu pemroses yang telah digunakan proses sejak login dan jumlah waktu proses yang digunakan seluruh proses.

Karena jumlah waktu pemroses tiap pemakai dapat diketahui, maka dapat dihitung rasio antara waktu pemroses yang sesungguhnya harus diperoleh yaitu 1/N waktu pemroses seluruhnya dan waktu pemroses telah diperuntukkan proses itu.
Penjadwal akan menjalankan proses dengan rasio terendah sampai rasio proses diatas pesaing terdekatnya.

Evaluasi Algoritma
Bagaimana memilih algoritma penjadwalan untuk sistem tertentu? Masing-masing algoritma mempunyai parameter-parameter tersendiri. Pemilihan algoritma penjadwalan merupakan hal yang sulit. Persoalan pertama adalah mendefinisikan kriteria untuk pemilihan algoritma.
Kriteria-kriteria yang sering digunakan adalah fairness (keadilan), efisiensi, waktu tanggap, turn arround time dan throughput. Kriteria kemudian dapat menjadi :

Memaksimumkan utilisasi pemroses dengan konstrain waktu tanggap maksimum adalah 500 milidetik, atau

Memaksimumkan throughput bahwa turn arround time adalah berbanding linier dengan waktu eksekusi total.

Begitu kriteria pemilihan telah didefinisikan, kita dapat mengeveluasi beragam algoritma. Terdapat sejumlah metode evaluasi untuk melakukan hal ini, yaitu :

Pemodelan deterministis, merupakan evaluasi analitis. Evaluasi analitis menggunakan algoritma dan beban kerja sistem untuk menghasilkan satu rumus atau angka yang menunjukkan kinerja algoritma untuk beban kerja itu. Pemodelan deterministik menggunakan suatu beban kerja tertentu yang telah ditentukan dan mendefinisikan kinerja algoritma untuk beban kerja itu.

Pemodelan antrian, sistem komputer dipandang sebagai satu jaringan pelayanan (server). Masing-masing pelayan mempunyai satu antrian dari proses-proses yang menunggu layanan. Pemroses adalah satu pelayan dengan satu antrian proses yang siap menerima layanan, begitu juga perangkat I/O adalah antrian perangkat. Dengan mengetahui rate kedatangan dan rate layanan, maka kita dapat mengkomputasi utilisasi, panjang antrian rata-rata, waktu tunggu rata-rata dsb. Bidang studi ini adalah analisis jaringan antrian (queueing network analys).

Simulasi, simulasi dapat memberikan evaluasi algoritma penjadwalan dengan lebih akurat. Simulasi melibatkan pemrograman model sistem komputer. Dengan simulasi akan diperoleh statistik yang menyatakan kinerja algoritma.

Implementasi, simulasi pun hanya memberikan akurasi yang terbatas. Satu-satunya cara paling akurat dalam mengevaluasi algoritma penjadwalan adalah mengimplementasikannya, menjalankannya pada sistem nyata dan melihatnya bekerja. Pendekatan ini adalah menjalankan algoritma nyata di sistem nyata untuk keperluan evaluasi pada beban atau kondisi operasi yang nyata.

Masing-masing cara evaluasi algoritma penjadwalan mempunyai kelebihan dan kelemahan.