Bagian ini akan membahas bagaimana scheduler melakukan permilihan proses. Ada berbagai macam algoritma pemilihan atau penjadwalan. Beberapa yang akan dibahas adalah FIFO (First in First Out) atau disebut juga FCFS (First Come First Serve), SJF (Shortest Job First) dan HRRN (Highest Response Ratio Next). Ketiga algoritma ini merupakan algoritma penjadwalan non-preemptive. Namun untuk SJF dan HRRN dimungkinkan membuat versi preemptive-nya.

Selain itu akan dibahas sejumlah algoritma penjadwalan preemptive lainnya seperti RR (Round Robin), SRT (Shortest Remaining Time), GS (Guaranteed Schedulling), MLQ (Multi Level Queueing), MFQ (Multi Level Feedback Queueing). Algoritma RR tidak menggunakan prioritas dalam penjadwalannya, sedangkan algoritma lainnya memberikan nilai prioritas yang dinamis pada proses setiap kali terjadi penjadwalan.

Algoritma Penjadwalan Non-Preemptive

FIFO (First in First Out) / FCFS (First Come First Serve), merupakan algoritma penjadwalan non-preemptive, tidak berprioritas. Setiap proses diberi jadwal eksekusi berdasarkan jatah eksekusi maka proses akan dijalankan sampai selesai. FIFO jarang digunakan secara tersendiri tetapi dikombinasikan dengan algoritma lain karena dapat menyebabkan job yang pendek harus menunggu selasainya job panjang, atau job yang penting harus menunggu job yang kurang penting. FIFO cocok untuk sistem batch yang sangat jarang berinteraksi dengan pengguna, tetapi sangat buruk untuk sistem interaktif dan sistem real-time, karena cenderung memberikan response time yang buruk.

Sebagai contoh, ada tiga proses, yaitu P1, P2, P3 yang sedang menunggu dijadwal dengan prediksi burst time (waktu eksekusi) 24ms (milisecond atau milidetik), 3ms dan 3ms secara berturut-turut. Diasumsikan ketika proses masuk pada saat yang hampir bersamaan, yaitu detik ke 0.

Tabel Penjadwalan

Misalnya urutan masuknya proses P1,P2,P3 maka Gantt Chart untuk penjadwalanya adalah :

Gantt Chart

Secara umum , untuk menghitung waiting time suatu proses, rumusnya adalah waktu selesai – waktu mulai – burst time atau :

twaiting = tend – tstart – tburst-time

Waiting Time untuk P1 = 0ms; P2= 24ms; P3=27ms, sehingga

Rerata Waiting Time : (0+24+27)/3 = 17ms

Sementara jika urutan masuknya proses : P2, P3, P1 , maka Gantt Chart untuk penjadwalnya adalah :

Gantt Chat

Waiting Time untuk P1 = 6ms; P2= 0; P3= 3ms , sehingga

Rerata Waiting Time : (6+0+3)/3 = 3ms

Nilai rerata waiting time ini lebih baik dari sebelumnya sekalipun burst time setiap proses adalah sama. Perbedaannya disini adalah proses yang lebih pendek ditaruh didepan antrian. Ini merupakan ide dari algoritma penjadwalan berikutnya SJF.