Penjadwalan CPU

FCFS, SJF, SRTF, Round Robin, dan Priority, cara menggambar Gantt chart, serta menghitung waiting & turnaround time.

Pada sistem multiprogramming, banyak proses siap dijalankan sementara CPU hanya bisa mengerjakan satu proses dalam satu waktu (per core). CPU scheduler memilih proses mana dari ready queue yang mendapat CPU berikutnya.

Istilah penting

Arrival time: kapan proses masuk ready queue.
Burst time: berapa lama proses butuh CPU.
Completion time: kapan proses selesai.
Turnaround time = completion − arrival (total waktu di sistem).
Waiting time = turnaround − burst (waktu menunggu di ready queue).
Response time = pertama kali dapat CPU − arrival (penting untuk sistem interaktif).
Preemptive: proses yang sedang berjalan bisa direbut CPU-nya. Non-preemptive: berjalan sampai selesai/blok.

Simulasi

Ubah arrival, burst, dan prioritas, lalu bandingkan rata-rata waiting time tiap algoritma.

proses	selesai	turnaround	waiting	response
P1	7	7	0	0
P2	11	9	5	5
P3	12	8	7	7
P4	16	11	7	7

Gantt chart

07111216

Rata-rata waiting time 4.75 · turnaround 8.75 · response 4.75

Turnaround = selesai − arrival · Waiting = turnaround − burst · Response = pertama kali jalan − arrival. Prioritas: angka kecil = lebih penting.

Algoritmanya

FCFS (First Come First Served): yang datang duluan dilayani duluan. Sederhana, tapi menderita convoy effect: satu proses panjang di depan membuat semua proses pendek menunggu lama.

SJF (Shortest Job First): pilih burst terpendek dari proses yang sudah datang. Terbukti optimal untuk rata-rata waiting time (non-preemptive). Masalahnya, burst time sebenarnya tidak diketahui di muka, sehingga dalam praktik diprediksi, misalnya dengan exponential averaging.

SRTF (Shortest Remaining Time First): versi preemptive SJF. Setiap ada proses baru datang, bandingkan sisa waktu.

Round Robin: setiap proses mendapat jatah time quantum $q$ . Jika belum selesai, ia kembali ke belakang antrean. Adil dan responsif. Jika $q$ terlalu besar, RR menjadi FCFS; jika terlalu kecil, overhead context switch mendominasi.

Priority: pilih prioritas tertinggi (di sini angka kecil = prioritas tinggi). Risikonya starvation: proses berprioritas rendah tidak pernah jalan. Solusinya aging: naikkan prioritas proses yang sudah lama menunggu.

Highest Response Ratio Next (HRN)

HRN memilih proses siap dengan rasio tertinggi, yaitu (waktu tunggu + durasi layanan) / durasi layanan. Hitung ulang saat CPU memilih pekerjaan berikutnya. HRN standar berjalan nonpreemptif, sedangkan SRF atau SRTF dapat menyela proses jika ada sisa durasi yang lebih pendek.

Misal A sudah menunggu 6 unit dan memerlukan 3 unit layanan. B menunggu 1 unit dan memerlukan 2 unit. Rasio A = 3, rasio B = 1,5. HRN memilih A karena waktu tunggunya lebih besar relatif terhadap durasi layanan. Bandingkan dengan SRF yang akan memilih B jika kedua proses belum pernah berjalan.