Penjadwalan Proses

Penjadwalan CPU terjadi pada sistem operasi yang mempergunakan multiprogramming. Penjadwalan berupa kumpulan kebijakan untuk menentukan proses mana yang harus dikerjakan CPU dan berapa lama proses tersebut berjalan.

Tujuan penjadwalan adalah mengusahakan agar CPU tetap sibuk. Pada saat CPU menunggu operasi I/O, scheduler menyeleksi proses di main memory yang memiliki status ready untuk dieksekusi. Penjadwalan tipe ini disebut Short-term scheduller. Scheduler pada short-term ini dikenal dengan nama dispatcher

Tipe-tipe Penjadwalan

• Short-term scheduller : ready→ running
• Medium-term scheduller : suspended→ ready
• Long-term scheduller : batch (new)→ ready

Untuk mengukur kinerja scheduler digunakan beberapa kriteria :

• Fairness: Proses-proses diperlakukan sama yaitu setiap proses akan mendapatkan pembagian waktu secara adil
• CPU utilization: CPU dikondisikan agar tetap sibuk, yang dinyatakan dengan rasio waktu sibuk

• Throughput: Ini hanya terjadi pada saat CPU sibuk yaitu banyaknya job yang dikerjakan dalam satu satuan waktu

• Turnaround Time: Banyaknya waktu yang diperlukan untuk mengeksekusi proses sampai selesai, dari mulai menunggu untuk meminta tempat di main memory, menunggu di ready queue (waiting time), dieksekusi dan selesai. Sasaran dari scheduller adalah meminimalkan timearound time.

• Response Time: Waktu yang dibutuhkan oleh suatu proses dari minta dilayanai sampai ditanggapi.

Strategi Penjadwalan

• Penjadwalan nonpreemptive: Begitu diberi jatah waktu pemroses maka prosesor tidak dapat diambil alih oleh proses lain sampai proses itu selesai (run to completion)
• Penjadwalan Preemptive: Saat proses diberi jatah waktu pemroses maka pemroses dapat diambil alih oleh proses lain sehingga proses disela sebelum selesai dan akan dilanjutkan setelah jatah waktu pemroses kembali padanya.

Algoritma Penjadwalan

A. First Come First Served (FCFS)

Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu.

Algoritma ini termasuk non-preemptive

Average Waiting Time (AWT) tinggi. AWT adalah  total waktu menunggu dari semua proses dibagi jumlah proses 

Misal ada 3 proses : P1, P2 dan P3 yang meminta layanan CPU

Jika urutan kedatangan P1, P2, P3

Gant Chart

Waktu tunggu untuk tiap-tiap proses

AWT = (0+24+27)/3 = 17 ms

B. Short Job First Scheduling (SJF)

Proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu

Misal ada 4 proses : P1, P2, P3 dan P4

Gant Chart

Waktu tunggu untuk tiap-tiap proses

AWT=  (3+16+9+0)/4=  7 ms

Kelemahan SJF : sulitnya mengetahui CPU burst time berikutnya. Cara mengatasinya dengan memprediksi CPU Burst Time berikutnya menggunakan rata-rata eksponensial dari burst time sebelumnya.

Sebagai contoh α = 0,5

Pada awalnya t1 = 6 dan τ1 = 10 sehingga

τ2    = 0,5*6 + (1-0,5)*10 = 8

Nilai ini akan digunakan untuk mencari  τ3

τ3=(0.5)*4+ (1-0.5)*8=6

Strategi penjadwalan SJF adalah non-preemptive dan preemptive. Misal ada proses P1 yang datang pada saat P0 sedang berjalan. Pada Preemptive jika CPU burst P1 lebih kecil dari sisa waktu yang dibutuhkan P0 maka P0 akan diberhentikan dulu dan CPU dialokasikan untuk P1. 

Penjadwalan SJF secara Preemptive dikenal dengan shortest remaining time first scheduling

Contoh Preemptive penjadwalan SJF:

Misal terdapat 4 proses

Gant chart :

Proses yang lebih tiba dulu akan diproses, setelah itu lihat CPU burst paling kecil.

Waktu tunggu untuk tiap proses

AWT  = (9+0+15+2)/4 = 6,5 ms

C. Priority Scheduling
Pada strategi ini CPU akan dialokasikan untuk proses yang memiliki prioritas tertinggi. Jika beberapa proses memiliki prioritas yang sama maka akan digunakan algortima FCFS. Priority scheduling dapat bersifat preemptive maupun non preemptive
Contoh : terdapat 5 proses dengan CPU burst

Gant Chart

Waktu tunggu untuk tiap-tiap proses

AWT = (6+0+16+18+1)/5 = 8,2 ms

Prioritas biasanya menyangkut : waktu, memori yang dibutuhkan, banyaknya file   yang boleh dibuka, rasio antara rata-rata I/O burst dan rata-rata CPU/burst

D. Round-Robin Scheduling

Konsep dasar algoritma ini adalah time sharing

Digunakan quantum time untuk membatasi waktu eksekusi 

Bersifat preemptive, proses yang burst timenya melebihi quantum time akan mengantri di posisi ekor dari ready queue.

Misal quantum time 4 ms

Gant chart

AWT=(6+4+7)/3= 5.7 ms

Kelemahan Round-Robin
Semakin kecil quantum time maka switching akan sering terjadi