Algoritma Penjadwalan Proses Shortest Job First (sjf)

Abdur Rohman M Teknik Elektro Universitas Brawijaya

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 1: Process P1 P2 P3 P4

Arrival Time Burst Time 0.0 7 2.0 4 4.0 1 5.0 4

Contoh: Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time 4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4 dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF. Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms. Gambar 14.3. Shortest Job First (Non-Preemptive)

Average waiting time rata-rata untuk ketiga porses tersebut adalah sebesar (9+1+0+2)/4=3 ms.

Contoh 2 :

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. Contoh 3:

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.