Pengertian dan Contoh Algortima Penjadwalan FCFS, SJF dan Round Robin

A. FCFS (First Come First Served)

Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini setiap proses yang berada pada status ready dimasukkan kedalam FIFO queue atau antrian dengan prinsip first in first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.

Contoh Permasalahan :

Pengertian dan Contoh Algortima Penjadwalan FCFS, SJF dan Round Robin

Ada empat buah proses yang datang secara bersamaan yaitu pada 0 ms,

P1 memiliki burst time 8 ms,
P2 memiliki burst time 7 ms,
P3 memiliki burst time 10 ms,
Dan P4 memiliki burst time 6 ms.

Apabila kita gunakan Algoritma FCFS ini maka analisisnya akan dijelaskan dalam gantt chart sebagai berikut:

Ketika CPU tidak mengerjakan sesuatu atau dalam posisi 0 datang sebuah proses yang dinamakan P1 yang membutuhkan waktu penyelesaian yang berjumlah 8.

Karena FCFS ini melakukan proses menurut kapan proses itu datang atau yang bisa kita katakan sebagai proses antrian, maka proses selanjutnya akan di kerjakan setelah proses yang berada di depannya selesai untuk di kerjakan.

Tadi proses P1 selesai di kerjakan di 8, sementara itu ada P2,P3,dan P4 yang sedang menunggu untuk di kerjakan selanjutnya. Ketika P1 selesai dikerjakan di 8, maka akan di lanjutkan dengan pengerjaan P2 yang memiliki waktu pengerjaan sebesar 7, sehingga proses P2 akan selesai di kerjakan pada posisi 15.

P1 dan P2 sudah selesai pengerjaannya, tinggal menunggu pengerjaan daripada P3 dan P4. Dan begitupun selanjutnya sampai P4 selesai untuk di proses.

Algoritma FCFS dalam prosesnya tidak mengizinkan sebuah penyelaan dari segi apapun, dengan kata lain Algoritma FCFS ini bersifat non-preempetive atau tidak dapat dilakukan interrupt oleh proses lain. walaupun proses yang menunggu memiliki prioritas yang lebih tinggi.

Kelemahan dari algoritma ini:

Waiting time rata-ratanya cukup lama
Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU

B. Shortest-Job-First-Scheduling (SJF)

Algoritma Shortest Job First Scheduling (SJF) ini memungkinkan setiap proses yang memiliki burst time (waktu pengerjaan) terkecil yang akan dikerjakan terlebih dahulu.

Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan otomatis waiting time rata-ratanya juga menjadi pendek pula, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal. Algoritma Shortest Job First Scheduling (SJF) ini memiliki 2 jenis, yaitu :

a. Shortest Job First Scheduling Non-preemptive

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.

Dapat dilihat pada contoh gambar di atas P1 datang di awal dengan burst time 7 dan tetap berlanjut sampai akhir proses P1.

Baru kemudian di lanjut oleh P3 dengan burst time terkecil yaitu 1, baru kemudian dilanjutkan dengan P2 dengan time arrival lebih dulu dengan burst time 4, dan diikuti oleg P4 yang memiliki burst time sama namun masuk di queue pada arrival time terakhir.

b. Shortest Job First Scheduling Preemptive

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. Jika kita perhatikan gambar di atas sedikit berbeda dari Shortest Job Scheduling First Non-Preempetive, Shortest Job Scheduling First Preempetive ini mendahulukan P1 namun sampai di waktu ke 2, karna disebabkan Muncul P2 ke queue maka P1 dihentikan di waktu ke 2 dan dilanjutkan oleh P2 yang memiliki burst time lebih rendah daripada P1.

Kemudian dilanjutkan oleh P3 karna memiliki burst time Lebih rendah, kemudian disusul dengan P4 dan kembali lagi ke P1. Walaupun algoritma ini dapat disebut algoritma yang cukup optimal, algoritma ini masih memiliki beberapa kekurangan yaitu:

Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya
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

C. Round Robin.

Yaitu salah satu Algoritma penjadwalan yang menggilir proses secara berurutan. Dalam algoritma ini setiap proses akan mendapatkan waktu dari CPU yang kita kita sebut dengan time quantum. Time quantum adalah suatu satuan waktu.

Time quantum inilah yang menentukan proses mana yang akan dikerjakan terlebih dahulu oleh CPU dan kemudian proses mana yang akan dilakukan berikutnya. Biasanya suatu proses mendapat jatah time quantum yang sama dari CPU yakni 1-100 milidetik atau (1/n).

Jika proses yang sedang dieksekusi selesai dalam waktu kurang dari 1 time quantum, tidak ada masalah. Tetapi jika proses berjalan melebihi 1 time quantum, maka proses tersebut akan dihentikan,lalu digantikan oleh proses yang berikutnya.

Proses yang dihentikan tersebut akan diletakkan di queue di urutan paling belakang. Berikut gambar urutan kejadian proses dalam Algoritma Round Robin.

Contoh urutan suatu proses dengan menggunakan Algoritma Round Robin.

Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 time quantum.

Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, Algoritma Round Robin akan berjalan seperti algoritma First Come First Served.

Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

Location: Indonesia