Penjadwalan proses merupakan kumpulan kebijaksanaan dan mekanisme di sistemoperasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer.Adapun penjadwalan bertugas memutuskan :a. Proses yang harus berjalanb. Kapan dan selama berapa lama proses itu berjalan.Algoritma-algoritma Penjadwalan Berikut adalah jenis-jenis algoritma berdasarkan penjadwalan :
1. First In First Out (FIFO)
Merupakan Penjadwalan tidak berprioritas. FIFO adalah penjadwalan paling sederhana, yaitu :· Proses-proses diberi jatah waktu pemroses berdasarkan waktu kedatangan.· Pada saat proses mendapat jatah waktu pemroses, proses dijalankan sampaiselesai.Penilian penjadwalan ini berdasarkan kriteria optimasi :
· Adil
Adil dalam arti resmi (proses yang datang duluan akan dilayani lebih dulu), tapidinyatakan tidak adil karena job-job yang perlu waktu lama membuat job-jobpendek menunggu. Job-job yang tidak penting dapat membuat job-job pentingmenunggu lama.
· Efisiensi
Sangat efisien.
· Waktu tanggap
Sangat jelek, tidak cocok untuk sistem interaktif apalagi untuk sistem waktu nyata.
· Turn around time
Jelek.
· Throughtput
Jelek.FIFO jarang digunakan secara mandiri, tetapi dikombinasikan dengan skema lain,misalnya : Keputusan berdasarkan prioritas proses. Untuk proses-pross berprioritassama diputuskan berdasarkan FIFO.
Penjadwalan ini :
a) Baik untuk sistem batch yang sangat jarang berinteraksi dengan pemakai.Contoh : aplikasi analisis numerik, maupun pembuatan tabel.
b) Sangat tidak baik (tidak berguna) untuk sistem interaktif, karena tidak memberiwaktu tanggap yang baik.
c) Tidak dapat digunakan untuk sistem waktu nyata (real-time applications)
2. Shortest Job First (SJF)
Penjadwalan ini mengasumsikan waktu jalan proses sampai selesai diketahuisebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu jalanterpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi danturn around time rendah dan penjadwalannya tak berprioritas.
Contoh :Terdapat empat proses (job) yaitu A,B,C,D dengan waktu jalannya masing-masingadalah 8,4,4 dan 4 menit. Apabila proses-proses tersebut dijalankan, maka turnaround time untuk A adalah 8 menit, untuk B adalah 12, untuk C adalah 16 danuntuk D adalah 20. Untuk menghitung rata-rata turn around time seluruh prosesadalah dengan menggunakan rumus :
( 4a + 3b + 2c + 1d ) / 4
Dengan menggunakan rumus, maka dapat dihitung turn around time-nya sebagaiberikut
= ( 4a + 3b + 2c + 1d ) / 4= ( 4x8 + 3x4 + 2x4 + 1x4 ) / 4= ( 32 + 12 + 8 + 4 ) / 4= 56 / 4= 14 menit
Apabila keempat proses tersebut menggunakan penjadwalan shortest job fisrt , maka turn around time untuk B adalah 4, untuk C adalah 8, untuk D
adalah 12 dan untuk A adalah 20, sehingga rata-rata turn around timenya adalahsebagai berikut :
= ( 4a + 3b + 2c + 1d ) / 4= ( 4x4 + 3x4 + 2x4 + 1x8 ) / 4= ( 16 + 12 + 8 + 8 ) / 4= 44 / 4= 11 menit
Tidak memperhatikan SJF Memperhatikan SJF
Posisi : a b c d a b c d
Priority : 4 3 2 1 4 3 2 1
Job : A B C D A B C D A
---------------------------------------------------------------------------------------------------
: 8 : 4 : 4 : 4 : : 4 : 4 : 4 : 8 :
----------------------------------------------------------------------------------------------------
(a) (b)
Jelas bahwa a memberikan nilai kontribusi yang besar, kemudian b, c dan d. KarenaSJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untukproses interaktif. Umumnya proses interaktif memiliki pola, yaitu menungguperintah, menjalankan perintah, menunggu perintah dan menjalankan perintah,begitu seterusnya.Masalah yang muncul adalah :· Tidak mengetahui ukuran job saat job masuk.Untuk mengetahui ukuran job adalah dengan membuat estimasi berdasarkankelakukan sebelumnya.· Proses yang tidak datang bersamaan, sehingga penetapannya harus dinamis.Penjadwalan ini jarang digunakan, karena merupakan kajian teoritis untukpembandingan turn around time.
Algoritma Preemptive
1. Round Robin (RR)
Merupakan :
Ø Penjadwalan yang paling tua, sederhana, adil,banyak digunakan algoritmanyadan mudah diimplementasikan.
Ø Penjadwalan ini bukan dipreempt oleh proses lain tetapi oleh penjadwalberdasarkan lama waktu berjalannya proses (preempt by time).
Ø Penjadwalan tanpa prioritas.
Berasumsi bahwa semua proses memiliki kepentingan yang sama, sehinggatidak ada prioritas tertentu.
Semua proses dianggap penting sehingga diberi sejumlah waktu oleh pemrosesyang disebut kwanta (quantum) atau time slice dimana proses itu berjalan. Jikaproses masih running sampai akhir quantum, maka CPU akan mempreempt prosesitu dan memberikannya ke proses lain.
Penjadwal membutuhkannya dengan memelihara daftar proses dari runnable.Ketika quantum habis untuk satu proses tertentu, maka proses tersebut akandiletakkan diakhir daftar (list), seperti nampak dalam gambar berikut ini :
Algoritma yang digunakan :
1. Jika kwanta habis dan proses belum selesai, maka proses menjadi runnabledan pemroses dialihkan ke proses lain.
2. Jika kwanta belum habis dan proses menunggu suatu kejadian (selesainyaoperasi I/O), maka proses menjadi blocked dan pemroses dialihkan ke proses lain.
Jika kwanta belum habis tetapi proses telah selesai, maka proses diakhiri danpemroses dialihkan ke proses lain.
2. Priority Schedulling (PS)
Adalah tiap proses diberi prioritas dan proses yang berprioritas tertinggi mendapat jatah waktu lebih dulu (running). Berasumsi bahwa masing-masing proses memilikiprioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yang dimilikinya.Ilustrasi yang dapat memperjelas prioritas tersebut adalah dalam komputer militer,dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayorberprioritas 80, kapten berprioritas 70, letnan berprioritas 60 dan seterusnya. DalamUNIX perintah untuk mengubah prioritas menggunakan perintah nice.Pemberian prioritas diberikan secara :
a. Statis (static priorities)Berarti prioritas tidak berubah.
Keunggulan :
1. Mudah diimplementasikan.
2. Mempunyai overhead relatif kecil.
Kelemahan :
1. Tidak tanggap terhadap perubahan lingkungan yang mungkin menghendaki
penyesuaian prioritas.
b. Dinamis (dynamic priorities)
Merupakan mekanisme untuk menanggapi perubahan lingkungan sistemberoperasi. Prioritas awal yang diberikan ke proses mungkin hanya berumurpendek setelah disesuaikan ke nilai yang lebih tepat sesuai lingkungan.
Kelemahan :
· Implementasi mekanisme prioritas dinamis lebih kompleks dan mempunyaioverhead lebih besar. Overhead in diimbangi dengan peningkatan dayatanggap sistem.
Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layananadil dari pemroses dalam arti jumlahwaktu pemroses yang sama.Keunggulannya penjadwalan berpriorita adalah memenuhi kebijaksanaan yangingin mencapai maksimasi suatu kriteria diterapkan. Algoritma ini dapatdikombinasikan, yaitu dengan mengelompokkan proses-proses menjadi kelas-kelas prioritas.
Penjadwalan berprioritas diterapkan antar kelas-kelas proses itu.Algoritma penjadwal akan menjalankan : proses runnable untuk prioritas 4 lebihdulu secara round robin, apabila kelas 4 semua sudah diproses, selanjutnya akanmenjalankan proses runnable untuk prioritas 3 secara round robin, apabila kelas3 semua sudah diproses (habis), selanjutnya akan menjalankan proses runnableuntuk prioritas 2 secara round robin, dan seterusnya, seperti dalam gambarberikut :
3. Multiple Feedback Queues (MFQ)
Merupakan :
Penjadwalan berprioritas dinamisPenjadwalan ini untuk mencegah (mengurangi) banyaknya swapping denganproses-proses yang sangat banyak menggunakan pemroses (karenamenyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlahkwanta) lebih banyak dalam satu waktu. Penjadwalan ini juga menghendakikelas-kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalanselama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelasberikutnya berjalan empat kwanta, dan seterusnya.
Ketentuan yang berlaku adalah sebagai berikut
1. Jalankan proses pada kelas tertinggi.
2. Jika proses menggunakan seluruh kwanta yang dialokasikan, maka diturunkankelas prioritasnya.
3. Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi.Mekanisme ini mencegah proses yang perlu berjalan lama swapping berkali-kalidan mencegah proses-proses interaktif yang singkat harus menunggu lama.
4. Shortest Remaining First (SRF)
Merupakan :
Penjadwalan berprioritas.dinamis.
Adalah preemptive untuk timesharing
Melengkapi SJFPada SRF, proses dengan sisa waktu jalan diestimasi terendah dijalankan,termasuk proses-proses yang baru tiba.
Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai.
Pada SRF, proses yang sedang berjalan (running) dapat diambil alih prosesbaru dengan sisa waktu jalan yang diestimasi lebih rendah.Kelemahan :
Mempunyai overhead lebih besar dibanding SJF. SRF perlu penyimpanan waktulayanan yang telah dihabiskan job dan kadang-kadang harus menanganiperalihan.
Tibanya proses-proses kecil akan segera dijalankan.
Job-job lebih lama berarti dengan lama dan variasi waktu tunggu lebih lamadibanding pada SJF.SRF perlu menyimpan waktu layanan yang telah dihabiskan , menambah overhead.Secara teoritis, SRF memberi waktu tunggu minimum tetapi karena overheadperalihan, maka pada situasi tertentu SFJ bisa memberi kinerja lebih baik dibanding SRF
5. Guaranteed Scheduloing (GS)
Penjadwalan ini memberikan janji yang realistis (memberi daya pemroses yangsama) untuk membuat dan menyesuaikan performance adalah jika ada N pemakai,sehingga setiap proses (pemakai) akan mendapatkan 1/N dari daya pemroses CPU.Untuk mewujudkannya, sistem harus selalu menyimpan informasi tentang jumlahwaktu CPU untuk semua proses sejak login dan juga berapa lama pemakai sedanglogin. Kemudian jumlah waktu CPU, yaitu waktu mulai login dibagi dengan n,sehingga lebih mudah menghitung rasio waktu CPU. Karena jumlah waktupemrosestiap pemakai dapat diketahui, maka dapat dihitung rasio antara waktu pemrosesyang sesungguhnya harus diperoleh, yaitu 1/N waktu pemroses seluruhnya danwaktu pemroses yang telah diperuntukkan proses itu
