23

BAB IV

PENJADWALAN CPU

Penjadwalan CPU merupakan tugas untuk menyeleksi sebuah proses

tunggu dari antrian siaga dan mengalokasikan CPU ke dalamnya. CPU

dialokasikan pada proses terpilih oleh dispatcher.

Setidaknya terdapat 4 (empat) algoritma penjadwalan CPU, yaitu

Penjadwalan Pertama-Datang Pertama-Terlayani (First-Come First-Served/

FCFS); Penjadwalan Tugas-Terpendek-Lebih Dulu (Shortest-Job-First/SJF);

Penjadwalan Prioritas; dan Penjadwalan Round-Robin. Keempat algoritma

tersebut dibahas satu per satu berikut ini.

A. ALGORITMA PENJADWALAN PERTAMA-DATANG PERTA-

MA-TERLAYANI (FIRST-COME FIRST-SERVED/FCFS)

Algoritma Penjadwalan Pertama-Datang Pertama-Terlayani (First-Come

First-Served/ FCFS) merupakan penjadwalan CPU yang paling sederhana. Contoh

berikut menggambarkan algoritma FCFS bekerja.

Contoh 1.

Proses Burst time (dalam ms)

P1 24

P2 3

P3 3

Jika proses-proses datang dengan urutan P1, P2, P3, dan terlayani dengan

aturan FCFS, diperoleh bagan Gantt (Gantt chart) sebagai berikut.

P1 P2 P3

0 24 27 30

24

Waktu tunggu untuk proses P1 adalah 0 milidetik, waktu tunggu untuk

proses P2 adalah 24 milidetik, sedangkan waktu tunggu untuk proses P3 adalah 27

milidetik, sehingga rata-rata waktu tunggu dari ketiga proses tersebut adalah:

(0 + 24 + 27)/3 = 51/3 = 17 milidetik.

Namun, jika proses-proses datang dengan urutan P2, P3, P1, dan terlayani

dengan aturan FCFS, diperoleh bagan Gantt sebagai berikut.

P2 P3 P1

0 3 6 30

Waktu tunggu untuk proses P1 adalah 6 milidetik, waktu tunggu untuk

proses P2 adalah 0 milidetik, sedangkan waktu tunggu untuk proses P3 adalah 3

milidetik, sehingga rata-rata waktu tunggu dari ketiga proses tersebut adalah:

(6 + 0 + 3)/3 = 9/3 = 3 milidetik.

B. ALGORITMA PENJADWALAN TUGAS-TERPENDEK-LEBIH

DULU (SHORTEST-JOB-FIRST/SJF)

Algoritma Penjadwalan Tugas-Terpendek-Lebih Dulu (Shortest-Job-First/

SJF) telah terbukti optimal, dengan memberikan waktu tunggu rerata terpendek.

Implementasi penjadwalan SJF sulit karena memprediksi panjang dari waktu

burst CPU berikutnya adalah sulit. Algoritma SJF merupakan kasus khusus pada

algoritma penjadwalan prioritas umum, yang secara sederhana mengalokasikan

CPU pada proses dengan prioritas tertinggi. Contoh berikut menggambarkan

algoritma SJF bekerja.

Contoh 2.

Proses Burst time (dalam ms)

P1 6

P2 8

P3 7

P4 3

25

Dengan algoritma SJF, maka terlihat bahwa urutan proses dari yang paling

pendek adalah: P4, P1, P3, P2, sehingga diperoleh bagan Gantt sebagai berikut.

P4 P1 P3 P2

0 3 9 16 24

Waktu tunggu untuk proses P1 adalah 3 milidetik, waktu tunggu untuk

proses P2 adalah 16 milidetik, waktu tunggu untuk proses P3 adalah 9 milidetik,

sedangkan waktu tunggu untuk proses P4 adalah 0 milidetik, sehingga rata-rata

waktu tunggu dari ketiga proses tersebut adalah:

(3 + 16 + 9 + 0)/4 = 28/4 = 7 milidetik.

Sebagai perbandingan, jika untuk kasus yang sama digunakan algoritma

penjadwalan FCFS, akan diperoleh waktu tunggu rerata = 10,25 milidetik

(mahasiswa dapat membuktikannya sebagai latihan; PR no. 1). Waktu Burst

secara umum diprediksi sebagai suatu rerata eksponensial atas panjang terukur

burst-burst CPU sebelumnya. Jika tn merupakan panjang burst CPU ke-n, dan n+1

merupakan nilai prediksi atas burst CPU berikutnya, maka untuk suatu bobot ,

0≤≤1, didefinisikan:

n+1 = tn + (1- n

Rumus tersebut mendefinisikan rerata eksponensial. Nilai tn terdiri atas informasi

terkini (most recent); n menyimpan histori masa lalu. Parameter mengendali-

kan bobot rerata atas masa kini dan histori masa lalu pada prediksi yang

dilakukan. Jika = 0, maka n+1 = n , dan histori masa kini tidak memiliki

dampak (kondisi sekarang diasumsikan transien). Jika = 1, maka n+1 = tn , dan

prediksi hanya merupakan materi burst terkini (histori dianggap kadaluwarsa dan

tak-relevan). Secara umum = ½, sehingga histori kini dan histori masa-lalu

berbobot seimbang. Notasi 0 awal dapat didefinisikan sebagai suatu konstanta

atau suatu rerata sistem secara keseluruhan. Gambar 4.1 menunjukkan rerata

eksponensial untuk = ½ dan 0 = 10.

26

i Waktu burst CPU (ti) ‘Perkiraan’ (i)

0 6 0 = 10 (diketahui)

1 4 1 = t0 + (1- 0 = (½)(6) + (1 – ½)(10) = 8

2 6 2 = t1 + (1- 1 = (½)(4) + (1 – ½)(8) = 6

3 4 3 = t2 + (1- 2 = (½)(6) + (1 – ½)(6) = 6

4 13 4 = t3 + (1- 3 = (½)(4) + (1 – ½)(6) = 5

5 13 5 = t4 + (1- 4 = (½)(13) + (1 – ½)(5) = 9

6 13 6 = t5 + (1- 5 = (½)(13) + (1 – ½)(9) = 11

7. ? 7 = t6 + (1- 6 = (½)(13) + (1 – ½)(11) = 12

dst. Dst. Dst.

Gambar 4.1 Contoh cara memprediksi waktu burst CPU berikutnya, n+1.

Algoritma SJF dapat berupa preemptive ataupun nonpreemptive. Pilihan

diambil jika sebuah proses-baru datang pada antrian siaga, sementara sebuah

proses lain sebelumnya sedang dieksekusi. Proses-baru dapat memiliki burst CPU

27

berikut yang lebih pendek daripa burst yang tersisa pada proses eksekusi yang

sedang berlangsung. Algoritma SJF peemptive akan mengosongkan dulu (to

preempt) proses eksekusi yang sedang berlangsung, sementara algoritma SJF

nonpremptive) akan membiarkan proses running yang sedang berlangsung sampai

ia menyelesaikan burst CPU-nya. Penjadwalan SJF preemptive seringkali disebut

sebagai penjadwalan waktu-sisa-terpendek-dulu (shortest-remaining-time-first).

Contoh 3. Perhatikan empat proses berikut, dengan panjang waktu burst CPU

dalam milidetik.

Proses Waktu kedatangan Burst time (dalam ms)

P1 0 8

P2 1 4

P3 2 9

P4 3 5

Dengan algoritma SJF premptive dengan waktu kedatangan dan waktu

burst seperti terindikasi, maka diperoleh bagan Gantt sebagai berikut.

P1 P2 P4 P1 P3

0 1 5 10 17 26

Penjelasan: Proses P1 dimulai pada waktu ke-0, karena ia merupakan satu-

satunya proses pada antrian. Proses P2 datang pada waktu ke-1. Waktu sisa dari

proses P1 (7 ms) lebih besar daripada waktu yang dibutuhkan oleh P2 (4 ms),

sehingga proses P1 dikosongkan dulu, dan proses P2 dijadwalkan. Waktu tunggu

rerata untuk contoh ini adalah:

P1 P2 P3 P4

((10-1) + (1-1) + (17-2) + (5-3))/4 = 26/4 = 6,5 milidetik.

28

Sedangkan algoritma SJF nonpreemptive untuk kasus yang sama akan

memberikan waktu tunggu rerata 7,75 milidetik (mahasiswa dapat

membuktikannya sebagai latihan PR no. 2).

C. PENJADWALAN PRIORITAS

Pada pembahasan ini, angka terendah dalam tabel Prioritas mewakili

prioritas yang lebih tinggi daripada angka yang lebih besar. Perhatikan contoh

berikut ini.

Contoh 4. Perhatikan lima proses berikut.

Proses Burst time (dalam ms) Prioritas

P1 10 3

P2 1 1

P3 2 3

P4 1 4

P5 5 2

Menggunakan penjadwalan prioritas, maka diperoleh bagan Gantt sebagai

berikut.

P2 P5 P1 P3 P4

0 1 6 16 18 19

Penjelasan: Proses P1 pada bagan Gantt di atas dilaksanakan lebih dulu

dibandingkan dengan Proses P3 dengan asumsi bahwa proses P1 memiliki waktu

kedatangan lebih awal dibandingkan dengan P3. Juga, waktu antarkedatangan

masing-masing proses adalah cukup kecil, mendekati nol sehingga, seakan-akan,

proses-proses tersebut memiliki waktu kedatangan yang sama. Waktu tunggu

rerata untuk contoh ini adalah:

29

P1 P2 P3 P4 P5

( 6 + 0 + 16 + 18 + 1 )/5 = 41/5 = 8,2 milidetik.

Namun, jika diasumsikan P3 datang lebih dulu dibandingkan P1, bagan

Gantt-nya dapat dibuat sebagai berikut.

P2 P5 P3 P1 P4

0 1 6 8 18 19

Waktu tunggu rerata untuk contoh ini adalah:

P1 P2 P3 P4 P5

( 8 + 0 + 6 + 18 + 1 )/5 = 33/5 = 6,6 milidetik.

D. PENJADWALAN ROUND-ROBIN

Penjadwalan Round-Robin (RR) lebih cocok digunakan untuk sistem

berbagi waktu (interaktif). Penjadwalan RR mengalokasikan CPU ke proses

pertama pada antrian siaga untuk q satuan waktu, dengan q merupakan waktu

(quantum time, waktu maksimum untuk tiap-tiap proses diberi jatah untuk masuk

pada CPU). Setelah q satua waktu, jika proses tidak di-relinquish oleh CPU, ia

dikosongkan dulu dan proses diletakkan pada ekor antrian siaga. Masalah utama

adalah memilih kuantum waktunya. Jika kuantum terlalu lebar, penjadwalan RR

mendegenerasikan menjadi FCFS. Jika kuantum terlalu kecil, penjadwalan yang

mubazir dalam bentuk waktu context-switch menjadi sangat mahal. Perhatikan

contoh berikut.

Contoh 5. Perhatikan tiga proses berikut.

Proses Burst time (dalam ms)

P1 24

P2 3

P3 3

30

Jika kuantum waktu 4 ms, proses P1 memperoleh 4 ms pertama. Karena ia

memerlukan 20 ms lainnya, ia di-preempt setelah kuantum untuk waktu pertama,

dan CPU diberikan pada proses berikutnya pada antrian, yaitu proses P2. Karena

P2 tidak membutuhkan 4 ms, ia keluar sebelum kuantum waktunya habis. CPU

kemudian diberikan kepada proses berikutnya, yaitu P3. Karena setiap proses telah

menerima satu kuantum waktu, CPU dikembalikan pada proses P1 untuk kuantum

waktu tambahan. Jadwal Round-Robin sebagai hasilnya adalah sebagai berikut.

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

Waktu tunggu rerata untuk contoh ini adalah:

P1 P2 P3

( (10-4) + 4 + 7 )/3 = 17/3 = 5,667 milidetik.

E. EVALUASI ALGORITMA

Terdapat beberapa cara untuk mengevaluasi algoritma-algoritma penjadwalan

CPU, tiga di antaranya adalah sebagai berikut.

1. Pemodelan Deterministik

Pemodelan deterministik mengambil beban-kerja (workload) khusus yang

telah ditentukan sebelumnya, dan menentukan kinerja dari masing-masing

algoritma untuk beban kerja tersebut.

Contoh 6. Pertimbangkan algoritma-algoritma penjadwalan FCFS, SJF, dan

Round-Robin (kuantum = 10 ms). Pemodelan deterministik akan

menyimpulkan kinerja yang paling optimal dari ketiga algoritma tersebut,

dengan menilai, misalnya, waktu rerata tunggu minimum. Mahasiswa bisa

melakukan evaluasi menggunakan pemodelan deterministik sebagai latihan

(PR no. 3).

31

Proses

Burst time (dalam ms) Waktu Kedatangan

(arrival time) ms

P1 10 0

P2 29 9

P3 3 30

P4 7 35

P5 12 45

2. SIMULASI

Metode simulasi menentukan kinerja dengan meniru algoritma penjadwalan

pada sebuah contoh yang representatif atas proses-proses, dan menghitung

kinerja hasilnya.

Contoh 7. Gambar berikut adalah contoh evaluasi penjadwal-penjadwal CPU

(dalam hal ini adalah FCFS, SJF dan RR (kuantum 14 ms)) menggunakan

simulasi, yang didasarkan pada eksekusi proses aktual pada berbagai jenis

CPU maupun I/O.

32

3. IMPLEMENTASI

Metode implementasi menentukan kinerja dengan langsung meletakkan

algoritma aktual pada sistem nyata untuk mengevaluasi pada kondisi operasi

yang nyata.