IF Notes

Algoritma Penjadwalan Klasik

3 min read

Back to IF2130 Sistem Operasi

Algoritma Penjadwalan Klasik

Questions/Cues

  • Bagaimana cara kerja FCFS?

  • Apa itu convoy effect?

  • Bagaimana cara kerja SJF?

  • Beda SJF preemptive vs non-preemptive?

  • Bagaimana memprediksi CPU burst berikutnya?

  • Bagaimana cara kerja Round Robin (RR)?

  • Apa peran time quantum?

  • Bagaimana cara kerja Priority Scheduling?

  • Apa masalah starvation dan solusinya?

Reference Points

  • PDF: 4. IF2130-05-2025-Scheduling.pdf

  • Slides: 12-27

First-Come, First-Served (FCFS)

  • Cara Kerja: Proses yang datang pertama akan dilayani pertama (seperti antrian di bank). Sangat sederhana untuk diimplementasikan dengan antrian FIFO.

  • Sifat: Non-preemptive.

  • Kelemahan: Average waiting time seringkali sangat buruk. Sangat sensitif terhadap urutan kedatangan proses.

  • Convoy Effect: Masalah di mana beberapa proses pendek harus menunggu di belakang satu proses yang sangat panjang, menyebabkan utilisasi perangkat I/O menjadi rendah.

Shortest-Job-First (SJF)

  • Cara Kerja: CPU dialokasikan ke proses yang memiliki durasi CPU burst berikutnya yang paling pendek.

  • Optimalitas: Terbukti optimal dalam memberikan average waiting time minimum.

  • Variasi:

    1. Non-Preemptive SJF: Jika sebuah proses mulai berjalan, ia akan berjalan sampai CPU burst-nya selesai.

    2. Preemptive SJF (Shortest-Remaining-Time-First, SRTF): Jika proses baru datang dengan burst yang lebih pendek dari sisa waktu proses yang sedang berjalan, OS akan melakukan preempt dan menjalankan proses baru tersebut.

  • Kelemahan Utama: Tidak mungkin mengetahui panjang CPU burst berikutnya secara pasti. Solusinya adalah dengan memprediksi berdasarkan histori burst sebelumnya menggunakan exponential averaging.

Priority Scheduling

  • Cara Kerja: Setiap proses diberi sebuah nilai prioritas (integer). CPU dialokasikan ke proses dengan prioritas tertinggi.

  • Sifat: Bisa preemptive atau non-preemptive.

  • Hubungan dengan SJF: SJF bisa dianggap sebagai priority scheduling di mana prioritas adalah invers dari prediksi panjang CPU burst berikutnya.

  • Masalah Utama: Starvation atau indefinite blocking, di mana proses berprioritas rendah mungkin tidak akan pernah mendapat giliran CPU.

  • Solusi Starvation: Aging, yaitu secara bertahap menaikkan prioritas proses yang telah menunggu terlalu lama.

Round Robin (RR)

  • Cara Kerja: Mirip FCFS, tetapi bersifat preemptive. Setiap proses diberi jatah waktu CPU yang kecil, disebut time quantum atau time slice (biasanya 10-100 ms).

  • Proses berjalan selama time quantum-nya. Jika belum selesai, ia akan di-preempt dan dipindahkan ke belakang ready queue.

  • Performa:

    • Jika quantum sangat besar, RR menjadi FCFS.

    • Jika quantum sangat kecil, overhead dari context switching menjadi sangat tinggi.

  • RR memberikan response time yang jauh lebih baik daripada FCFS, tetapi average turnaround time-nya cenderung lebih buruk daripada SJF.

Summary

Algoritma penjadwalan klasik menawarkan trade-off antara kesederhanaan, keadilan, dan performa. FCFS adalah yang paling sederhana namun rentan terhadap convoy effect. SJF terbukti optimal untuk average waiting time namun sulit diimplementasikan karena harus memprediksi masa depan. Priority Scheduling memungkinkan penentuan kepentingan proses namun berisiko menyebabkan starvation, yang bisa diatasi dengan aging. Round Robin menggunakan time quantum untuk memberikan response time yang baik dan mencegah starvation, menjadikannya pilihan umum untuk sistem interaktif.

Graph View

Backlinks