Algoritma Penjadwalan Nonpreemptive

Algoritma Penjadwalan Nonpreemptive

A. FIFO (First In First Out) atau FCFS (First Come First Serve)

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 sampai selesai.


Penilian penjadwalan ini berdasarkan kriteria optimasi :

· Adil
Adil dalam arti resmi (proses yang datang duluan akan dilayani lebih dulu), tapi dinyatakan tidak adil karena job-job yang perlu waktu lama membuat job-job pendek menunggu. Job-job yang tidak penting dapat membuat job-job penting menunggu 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 berprioritas sama 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 memberi waktu tanggap yang baik.

c. Tidak dapat digunakan untuk sistem waktu nyata (real-time applications).



B. SJF (Shortest Job First)

Penjadwalan ini mengasumsikan waktu jalan proses sampai selesai diketahui sebelumnya. mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

Contoh :

Terdapat empat proses (job) yaitu A,B,C,D dengan waktu jalannya masing-masing adalah 8,4,4 dan 4 menit. Apabila proses-proses tersebut dijalankan, maka turn around time untuk A adalah 8 menit, untuk B adalah 12, untuk C adalah 16 dan untuk D adalah 20. Untuk menghitung rata-rata turn around time seluruh proses adalah dengan menggunakan rumus :
( 4a + 3b + 2c + 1d ) / 4

Dengan menggunakan rumus, maka dapat dihitung turn around time-nya sebagai berikut (belum memperhatikan shortest job first, lihat gambar a) :
= ( 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 (lihat gambar b), 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 adalah sebagai berikut :

= ( 4a + 3b + 2c + 1d ) / 4
= ( 4x4 + 3x4 + 2x4 + 1x8 ) / 4
= ( 16 + 12 + 8 + 8 ) / 4
= 44 / 4
= 11 menit



Jelas bahwa a memberikan nilai kontribusi yang besar, kemudian b, c dan d. Karena SJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untuk proses interaktif. Umumnya proses interaktif memiliki pola, yaitu menunggu perintah, 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 berdasarkan kelakukan sebelumnya.
· Proses yang tidak datang bersamaan, sehingga penetapannya harus dinamis. Penjadwalan ini jarang digunakan, karena merupakan kajian teoritis untuk pembandingan turn around time.


C. HRN (Highest Ratio Next)

Merupakan :

- Penjadwalan berprioritas dinamis.
- Penjadwalan untuk mengoreksi kelemahan SJF.
- Adalah strategi penjadwalan dengan prioritas proses tidak hanya merupakan fungsi waktu layanan tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, proses berjalan sampai selesai.

Prioritas dinamis HRN dihitung berdasarkan rumus :

Prioritas = (waktu tunggu + waktu layanan ) / waktu layanan Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek berprioritas lebih baik, karena waktu tunggu sebagai pembilang maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus. Disebut HRN, karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani.

D. MFQ (Multiple Feedback Queues)

Merupakan :

- Penjadwalan berprioritas dinamis
Penjadwalan ini untuk mencegah (mengurangi) banyaknya swapping dengan proses-proses yang sangat
banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu waktu. Penjadwalan ini juga menghendaki kelas-kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya berjalan empat kwanta, dan seterusnya.

Ketentuan yang berlaku adalah sebagai berikut
- Jalankan proses pada kelas tertinggi.
- Jika proses menggunakan seluruh kwanta yang dialokasikan, maka diturunkan kelas prioritasnya.
- Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi. Mekanisme ini mencegah proses yang perlu berjalan lama swapping berkali-kali dan mencegah proses-proses interaktif yang singkat harus menunggu lama.