Sistem Operasi - Algoritma Penjadwalan

Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Di sini
algoritma diperlukan untuk mengatur giliran proses-proses tersebut. Berikut ini adalah
algoritmanya. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di
ready queue yang akan dieksekusi oleh CPU. Bagian berikut ini akan memberikan ilustrasi beberapa
algoritma penjadwalan.

1.FCFS: First-Come, First-Served
Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU.
Dengan menggunakan algoritma ini seiap proses yang berada pada status ready dimasukkan ke
dalam FIFO queue sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan
dieksekusi.

Contoh: Ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki burst
time 24 ms, P2 memiliki burst time 5 ms, P3 memiliki burst time 3 ms. Hitunglah wating time
rata-rata dan turnaround time (burst time + waiting time) dari ketiga proses tersebut dengan
menggunakan algoritma FCFS.
Waiting time untuk p1 adalah 0 ms (P1 tidak perlu menunggu), sedangkan untuk p2 adalah sebesar
24 ms (menunggu P1 selesai) dan untuk p3 sebesar 29 ms (menunggu P1 dan P2 selesai). Waiting
time rata-ratanya adalah sebesar (0+24+29)/3 = 17,6 ms.
Turnaround time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 29 ms (dihitung dari awal
kedatangan P2 hingga selesai dieksekusi), untuk p3 sebesar 32 ms. Turnaround time rata-rata untuk
ketiga proses tersebut adalah (24+29+32)/3 = 28,3 ms.
Kelemahan dari algoritma ini:
1. Waiting time rata-ratanya cukup lama.
2. Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar
yang sedang dieksekusi oleh CPU.
Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi
oleh CPU tidak dapat di-interrupt oleh proses yang lain.


2. SJF: Shortest-Job First

Algoritma ini mempunyai cara penjadwalan yang berbeda dengan FCFS. Dengan algoritma ini
maka 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.

Ada beberapa kekurangan dari algoritma ini yaitu:
1. Susahnya untuk memprediksi burst time 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.
Algoritma ini dapat dibagi menjadi dua bagian yaitu:
1. 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.
2. 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.
Contoh: Ada 3 buah proses yang datang berurutan yaitu p1 dengan arrival time pada 0 ms dengan
burst time 4 ms, p2 dengan arrival time pada 0 ms dengan burst time 5 ms, p3 dengan arrival time
pada 1 ms dengan burst time 2 ms. Hitunglah waiting time rata-rata dan turnaround time dari ketiga
proses tersebut dengan mengunakan algoritma SJF.
Waiting time rata-rata untuk ketiga proses tersebut adalah sebesar ((3-1)+(6-0)+(1-1))/3 = 2,6 ms.
Turnaround time dari ketiga proses tersebut adalah sebesar (6+11+(3-1))/3 = 6,3 ms.

3.Prioritas
Priority Scheduling merupakan algoritma penjadwalan yang mendahulukan proses yang memiliki
prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing.
Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain:
1. Time limit.
2. Memory requirement.
3. Akses file.
4. Perbandingan antara M/K Burst dengan CPU Burst.
5. Tingkat kepentingan proses.

Priority Scheduling juga dapat dijalankan secara preemptive maupun non-preemptive. Pada
preemptive, jika ada suatu proses yang baru datang memiliki prioritas yang lebih tinggi daripada
proses yang sedang dijalankan, maka proses yang sedang berjalan tersebut dihentikan, lalu CPU
dialihkan untuk proses yang baru datang tersebut.
Sementara itu, pada non-preemptive, proses yang baru datang tidak dapat menganggu proses yang
sedang berjalan, tetapi hanya diletakkan di depan queue.
Kelemahan pada priority scheduling adalah dapat terjadinya indefinite blocking (starvation). Suatu
proses dengan prioritas yang rendah memiliki kemungkinan untuk tidak dieksekusi jika terdapat
proses lain yang memiliki prioritas lebih tinggi darinya.
Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yang
menunggu dalam queue secara bertahap.
Contoh: Setiap 10 menit, prioritas dari masing-masing proses yang menunggu dalam queue
dinaikkan satu tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21 jam 20
menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang tertinggi. (semakin kecil angka
menunjukkan bahwa prioritasnya semakin tinggi)

4.Round-Robin
Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time
quantum. Jika time quantum-nya habis atau proses sudah selesai CPU akan dialokasikan ke proses
berikutnya. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua proses
mendapat jatah waktu yang sama dari CPU (1/n), dan tak akan menunggu lebih lama dari (n-1)/q.

Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan
sama saja dengan algoritma first-come first-served. Jika terlalu kecil, akan semakin banyak
peralihan proses sehingga banyak waktu terbuang.
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.