Catatan Kuliah: CPU Scheduling (Penjadwalan CPU)

1. Apa itu CPU Scheduling? (Analogi Sederhana)

Bayangkan CPU (prosesor) komputer Anda adalah seorang Kasir di Supermarket, dan program yang sedang berjalan (seperti Chrome, Word, Game) adalah Pelanggan yang mengantre.

Karena kasir hanya punya satu pasang tangan, dia hanya bisa melayani satu pelanggan dalam satu waktu. Tugas CPU Scheduling adalah menentukan siapa pelanggan berikutnya yang boleh maju ke kasir agar antrean berjalan cepat, adil, dan tidak ada pelanggan yang menunggu terlalu lama hingga "kelaparan" (starvation).

Dalam sistem operasi, tujuan utamanya adalah Multiprogramming: menjaga agar CPU selalu bekerja (sibuk) dan tidak menganggur, sehingga performa komputer terasa cepat dan lancar.

2. Siklus Hidup Proses: CPU Burst vs I/O Burst

Setiap program atau proses di komputer selalu bergantian melakukan dua hal ini:

1. CPU Burst: Saat proses menggunakan otak CPU untuk menghitung (misal: merender video, memproses rumus matematika).
2. I/O Burst: Saat proses menunggu perangkat input/output (misal: menunggu Anda mengetik keyboard, membaca data dari harddisk, atau mendownload file).

CPU Scheduling terjadi ketika sebuah proses selesai melakukan CPU Burst dan harus menunggu I/O, atau ketika ada proses baru yang datang.

3. Kapan CPU Mengambil Keputusan? (Preemptive vs Non-Preemptive)

Ada dua tipe "sifat" penjadwalan dalam sistem operasi:

A. Non-Preemptive (Suka Rela / Kooperatif)

Sekali sebuah proses diizinkan menggunakan CPU, proses tersebut tidak bisa diganggu gugat sampai dia selesai atau secara sukarela melepaskan CPU karena ingin menunggu I/O.

• Analogi: Pelanggan di kasir tidak boleh diusir sampai semua belanjaannya selesai dipindai, meskipun belanjaannya satu gerobak penuh dan antrean di belakangnya sudah mengular.

B. Preemptive (Bisa Diinterupsi / Dipotong)

Sistem operasi punya hak penuh untuk menghentikan proses yang sedang berjalan di tengah jalan jika ada proses lain yang dianggap lebih penting atau waktunya sudah habis.

• Analogi: Kasir berhak menyuruh pelanggan yang sedang dilayani untuk minggir dulu karena ada pelanggan VIP yang datang, atau karena batas waktu layanannya habis. Hampir semua OS modern (Windows, Linux, macOS) menggunakan tipe ini.

4. Kriteria Penjadwalan (Indikator Kasir yang Bagus)

Bagaimana kita tahu sebuah algoritma penjadwalan itu bagus? Buku Silberschatz menyebutkan 5 kriteria utama:

1. CPU Utilization (Kesibukan CPU): Kita ingin CPU bekerja sekeras mungkin (idealnya 40% s.d 90%). Jangan biarkan kasir menganggur.
2. Throughput (Jumlah Kerja): Jumlah proses yang berhasil diselesaikan dalam satu satuan waktu (misal: berapa pelanggan yang selesai dilayani per jam).
3. Turnaround Time (Waktu Total): Total waktu yang dihabiskan sebuah proses sejak dia pertama kali masuk antrean sampai dia selesai total.
4. Waiting Time (Waktu Tunggu): Durasi waktu yang dihabiskan proses hanya untuk mengantre di Ready Queue (antrean siap).
5. Response Time (Waktu Respons): Waktu dari pertama kali proses masuk antrean sampai CPU mulai memberikan respons pertama kali (bukan sampai selesai). Ini sangat penting untuk sistem interaktif seperti game atau aplikasi chat.

5. Algoritma Penjadwalan CPU yang Sering Keluar di Ujian

Berikut adalah 4 algoritma dasar yang dibahas di Bab 6:

A. First-Come, First-Served (FCFS)

• Prinsip: Siapa yang datang duluan, dia yang dilayani duluan. (Non-Preemptive).
• Kelemahan: Memiliki masalah bernama Convoy Effect. Jika proses yang datang duluan berukuran sangat besar (CPU burst lama), proses-proses kecil di belakangnya harus menunggu sangat lama. Ini membuat rata-rata Waiting Time menjadi buruk.

B. Shortest-Job-First (SJF)

• Prinsip: Cari proses yang waktu kerjanya paling pendek/cepat, lalu layani dia duluan.
• Kelebihan: Algoritma ini terbukti secara matematis menghasilkan rata-rata waktu tunggu (Average Waiting Time) paling minimum.
• Kelemahan: Sulit diterapkan di dunia nyata karena sistem operasi tidak bisa meramal masa depan (tidak tahu pasti berapa lama sebuah proses baru akan berjalan).

C. Priority Scheduling

• Prinsip: Setiap proses diberi nomor prioritas. CPU akan memilih proses dengan prioritas tertinggi (biasanya angka terkecil berarti prioritas tertinggi).
• Kelemahan: Bisa terjadi Starvation (Kelaparan). Proses dengan prioritas rendah mungkin tidak akan pernah dilayani jika ada proses prioritas tinggi yang terus-menerus datang.
• Solusi: Menggunakan teknik Aging (Penuaan). Semakin lama sebuah proses menunggu di antrean, prioritasnya secara bertahap dinaikkan oleh sistem agar suatu saat dia pasti akan dilayani.

D. Round-Robin (RR)

• Prinsip: Dirancang khusus untuk sistem Time-Sharing (berbagi waktu). Setiap proses diberikan jatah waktu kecil yang sama yang disebut Time Quantum (misalnya 10 milidetik). Jika waktunya habis dan proses belum selesai, dia harus mundur ke antrean paling belakang, dan CPU ganti melayani proses berikutnya. (Preemptive).
• Kelebihan: Sangat adil, tidak ada proses yang merasa diabaikan.
• Kunci Sukses: Penentuan ukuran Time Quantum. Jika terlalu besar, RR akan berubah sifat menjadi FCFS. Jika terlalu kecil, CPU akan lelah karena terlalu sering ganti-ganti tugas (Context Switch Overhead).

Berikut adalah visualisasi dan simulasi perhitungan untuk 4 algoritma penjadwalan CPU di atas. Agar mudah dipahami, kita gunakan sebuah studi kasus yang sama untuk keempat algoritma.

Studi Kasus Antrean Proses

Misalkan ada 4 proses yang masuk ke dalam antrean (Ready Queue) pada waktu yang sama (Arrival Time = 0), dengan durasi kerja (CPU Burst Time) masing-masing sebagai berikut:

Kita akan menghitung Waiting Time (Waktu Tunggu) untuk masing-masing proses dan mencari Average Waiting Time (Rata-rata Waktu Tunggu) menggunakan Gantt Chart.

1. Perhitungan First-Come, First-Served (FCFS)

Asumsi urutan kedatangan: P1, P2, P3, lalu P4.

Gantt Chart:

|       P1       | P2  |  P3  |    P4    |
0               24    27     31         38

• Waiting Time (Waktu Tunggu):
  • P1 = 0 ms (langsung dieksekusi)
  • P2 = 24 ms (menunggu P1 selesai)
  • P3 = 27 ms (menunggu P1 & P2 selesai)
  • P4 = 31 ms (menunggu P1, P2, & P3 selesai)
• Average Waiting Time: (0 + 24 + 27 + 31)/4 = 82/4 = 20.5

Catatan Kasus (Convoy Effect): Terlihat di sini, karena P1 yang berukuran besar (24 ms) berjalan duluan, proses kecil seperti P2 dan P3 harus menunggu sangat lama.

2. Perhitungan Shortest-Job-First (SJF)

Prinsip: Ambil Burst Time yang paling kecil duluan (Urutan: P2, P3, P4, P1).

Gantt Chart:

| P2  |  P3  |    P4    |       P1       |
0     3      7         14               38

• Waiting Time (Waktu Tunggu):
  • P2 = 0 ms (paling kecil, jalan duluan)
  • P3 = 3 ms (menunggu P2)
  • P4 = 3 + 4 = 7 ms (menunggu P2 & P3)
  • P1 = 3 + 4 + 7 = 14 ms (menunggu semua selesai)
• Average Waiting Time: (14 + 0 + 3 + 7)/4 = 24/4 = 6

Catatan Kasus: Terbukti secara matematis bahwa SJF menghasilkan rata-rata waktu tunggu yang jauh lebih kecil (hanya 6 ms) dibanding FCFS.

3. Perhitungan Priority Scheduling

Prinsip: Ambil berdasarkan angka prioritas terkecil (Urutan: P2, P4, P1, P3).

Gantt Chart:

| P2  |    P4    |       P1       |  P3  |
0     3         10               34     38

• Waiting Time (Waktu Tunggu):
  • P2 = 0 ms (Prioritas 1)
  • P4 = 3 ms (Prioritas 2)
  • P1 = 3 + 7 = 10 ms (Prioritas 3)
  • P3 = 3 + 7 + 24 = 34 ms (Prioritas 4)
• Average Waiting Time: (10 + 0 + 34 + 3)/4 = 47/4 = 11.75

4. Perhitungan Round-Robin (RR)

Asumsi ketentuan: Time Quantum = 4 ms. Urutan antrean awal: P1, P2, P3, P4. Setiap proses hanya boleh berjalan maksimal 4 ms, lalu digantikan proses berikutnya.

• Siklus 1:
  • P1 berjalan 4 ms (sisa 20 ms), antre ke belakang.
  • P2 berjalan 3 ms (Selesai di milidetik ke-7).
  • P3 berjalan 4 ms (Selesai di milidetik ke-11).
  • P4 berjalan 4 ms (sisa 3 ms), antre ke belakang.
• Siklus 2 dst: Hanya tersisa P1 dan P4 yang bergantian.

Gantt Chart:

| P1  | P2  | P3  | P4  | P1  | P4  | P1  | P1  | P1  | P1  |
0     4     7    11    15    19    22    26    30    34    38

• Waiting Time (Waktu Tunggu) dihitung dari Waktu Selesai - Burst Time:
  • P1 selesai pada ms ke-38. WT = 38 - 24 = 14
  • P2 selesai pada ms ke-7. WT = 7 - 3 = 4
  • P3 selesai pada ms ke-11. WT = 11 - 4 = 7
  • P4 selesai pada ms ke-22. WT = 22 - 7 = 15
• Average Waiting Time: (14 + 4 + 7 + 15)/4 = 40/4 = 10

Dari keempat algoritma di atas, berikut perbandingannya:

Ringkasan:

• CPU Scheduling adalah cara OS membagi waktu CPU ke proses-proses yang mengantre.
• Preemptive artinya bisa dipotong di tengah jalan, Non-preemptive artinya harus tunggu sampai selesai.
• SJF adalah yang paling efisien untuk waktu tunggu, tetapi Round-Robin adalah yang paling adil untuk kenyamanan pengguna sehari-hari.

Referensi:

1. Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Ninth Edition ", Chapter 6