Algoritma Penjadwalan Proses Shortest Job First (SJF)
Penjadwalan ini mengasumsikan waktu berjalannya proses sampai selesaitelah diketahui sebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu 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. 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.
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. Prosesnya tidak datang bersamaan, sehingga penetapannya harus dinamis. Penjadwalan ini jarang digunakan karena merupakan kajian teoritis untuk pembandingan turn around time.
Algoritma Penjadwalan Proses Shortest Job First (SJF)
Dalam Sistem Operasi dikenal istilah multiprograming, yang bertujuan untuk memaksimalkan penggunaan CPU dengan cara mengatur alokasi waktu yang digunakan oleh CPU, sehingga proses berjalan sepanjang waktu dan memperkecil waktu idle. Oleh karena itu perlu adanya penjadwalan proses-proses yang ada pada sistem. Untuk sistem yang hanya mempunyai prosesor tunggal (uniprosesor), hanya ada satu proses yang dapat berjalan setiap waktunya. Jika ada proses lebih dari satu maka proses yang lain harus menunggu sampai CPU bebas dan siap untuk dijadwalkan kembali.
Penjadwalan berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan dieksekusi oleh CPU. Bagian berikut ini akan memberikan ilustrasi algoritma penjadwalan Shortest Job First.
Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.
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. 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.
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. Prosesnya tidak datang bersamaan, sehingga penetapannya harus dinamis. Penjadwalan ini jarang digunakan karena merupakan kajian teoritis untuk pembandingan turn around time.
Algoritma Penjadwalan Proses Shortest Job First (SJF)
Dalam Sistem Operasi dikenal istilah multiprograming, yang bertujuan untuk memaksimalkan penggunaan CPU dengan cara mengatur alokasi waktu yang digunakan oleh CPU, sehingga proses berjalan sepanjang waktu dan memperkecil waktu idle. Oleh karena itu perlu adanya penjadwalan proses-proses yang ada pada sistem. Untuk sistem yang hanya mempunyai prosesor tunggal (uniprosesor), hanya ada satu proses yang dapat berjalan setiap waktunya. Jika ada proses lebih dari satu maka proses yang lain harus menunggu sampai CPU bebas dan siap untuk dijadwalkan kembali.
Penjadwalan berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan dieksekusi oleh CPU. Bagian berikut ini akan memberikan ilustrasi algoritma penjadwalan Shortest Job First.
Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.
Contoh:
Contoh: Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 s, P2 dengan arrival time pada 2.0 s dan burst time 4 s, P3 dengan arrival time pada 4.0 s dan burst time 1 s, P4 dengan arrival time pada 5.0 s dan burst time 4 s. Hitunglah waiting time rata-rata dan turn around time dari keempat proses tersebut dengan mengunakan algoritma SJF.
Average waiting time untuk ketiga proses tersebut adalah sebesar :
(0 +6+3+7)/4=4 s.
Gambar 14.3. Shortest Job First (Non-Preemptive)
Average waiting time untuk ketiga porses tersebut adalah sebesar :
(9+1+0+2)/4=3 s.
Tampak di sini bahwa SJF ini menyebabkan rata-rata lama tanggap semua proses itu menjadi 11.2 satuan waktu. Rata-rata ini akan lebih singkat jika dibandingkan dengan rata-rata lama tanggap untuk penjadwalan FIFO.
Dari tabel di atas terlihat bahwa proses job A dimulai eksekusi pada angka 0 dan selesai eksekusi pada angka 1. Job B tiba pada antrian proses pada angka 2 dengan lama eksekusi pada 3. Job B ini akan dieksekusi pada angka 2, tetap bukan pada angka 1, yaitu waktu selesainya job A, karena pada angka 1, yaitu selesainya job A, job B belum tiba pada antrian proses. Ini berarti prosesor harus menunggu sampai job-job tiba pada antrian proses. Begitu juga pada proses job D (kasus sama dengan job B).
Algoritma ini dapat dibagi menjadi dua bagian yaitu :
1. Preemptive
Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi.
Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining- Time-First scheduling.
2. Non-preemptive
Penjadwalan Non Preemptive ialah salah satu jenis penjadwalan dimana sistem operasi tidak pernah melakukan context switch dari proses yang sedang berjalan ke proses yang lain. Dengan kata lain, proses yang sedang berjalan tidak bisa di- interupt.
Contoh: Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 s, P2 dengan arrival time pada 2.0 s dan burst time 4 s, P3 dengan arrival time pada 4.0 s dan burst time 1 s, P4 dengan arrival time pada 5.0 s dan burst time 4 s. Hitunglah waiting time rata-rata dan turn around time dari keempat proses tersebut dengan mengunakan algoritma SJF.
Average waiting time untuk ketiga proses tersebut adalah sebesar :
(0 +6+3+7)/4=4 s.
Gambar 14.3. Shortest Job First (Non-Preemptive)
Average waiting time untuk ketiga porses tersebut adalah sebesar :
(9+1+0+2)/4=3 s.
Tampak di sini bahwa SJF ini menyebabkan rata-rata lama tanggap semua proses itu menjadi 11.2 satuan waktu. Rata-rata ini akan lebih singkat jika dibandingkan dengan rata-rata lama tanggap untuk penjadwalan FIFO.
Dari tabel di atas terlihat bahwa proses job A dimulai eksekusi pada angka 0 dan selesai eksekusi pada angka 1. Job B tiba pada antrian proses pada angka 2 dengan lama eksekusi pada 3. Job B ini akan dieksekusi pada angka 2, tetap bukan pada angka 1, yaitu waktu selesainya job A, karena pada angka 1, yaitu selesainya job A, job B belum tiba pada antrian proses. Ini berarti prosesor harus menunggu sampai job-job tiba pada antrian proses. Begitu juga pada proses job D (kasus sama dengan job B).Algoritma ini dapat dibagi menjadi dua bagian yaitu :
1. Preemptive
Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi.
Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining- Time-First scheduling.
2. Non-preemptive
Penjadwalan Non Preemptive ialah salah satu jenis penjadwalan dimana sistem operasi tidak pernah melakukan context switch dari proses yang sedang berjalan ke proses yang lain. Dengan kata lain, proses yang sedang berjalan tidak bisa di- interupt.
CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil.
Ada beberapa kekurangan dari algoritma ini yaitu:
1. Susahnya untuk memprediksi burst time (lama eksekusi) proses yang akan dieksekusi selanjutnya.
2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.
Ada beberapa kekurangan dari algoritma ini yaitu:
1. Susahnya untuk memprediksi burst time (lama eksekusi) proses yang akan dieksekusi selanjutnya.
2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.
sama sama gan
BalasHapus