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 beberapa algoritma penjadwalan.
1.
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 :
Ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1
memiliki burst time 24 ms, P2 memiliki burst time 3 ms, dan P3 memiliki burst
time 3 ms. Hitunglah waiting 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 27 ms (menunggu P1 dan P2 selesai).
Urutan kedatangan adalah P1, P2 , P3; gantt chart untuk urutan
ini adalah:
Waiting time rata-ratanya adalah sebesar(0+24+27)/3 = 17ms. Turnaround time untuk
P1 sebesar 24 ms, sedangkan untuk P2 sebesar 27 ms (dihitung dari awal
kedatangan P2 hingga selesai dieksekusi), untuk P3 sebesar 30 ms. Turnaround
time rata-rata untuk ketiga proses tersebut adalah (24+27+30)/3 = 27 ms. 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. Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.
Misalkan proses dibalik sehingga urutan kedatangan
adalah P2, P3, P1.
Waktu tunggu
sekarang untuk P1 adalah 6, P2 adalah 0 dan P3 adalah 3
sehingga ratarata waktu tunggu adalah (6 + 0 + 3)/3 = 3 milidetik. Rata-rata
waktu tunggu kasus ini jauh lebih baik dibandingkan dengan kasus sebelumnya.
2.
SJF (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:
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.
Average waiting time rata-rata untuk
ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms. Ada beberapa kekurangan
dari algoritma ini 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.
Algoritma ini dapat dibagi menjadi
dua bagian yaitu :
- 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.
- 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.
3.Priority Scheduling
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:
- Time limit.
- Memory requirement.
- Akses file.
- Perbandingan antara burst M/K dengan CPU burst.
- 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).
EmoticonEmoticon