Algoritma Penjadwalan CPU

Algoritma Penjadwalan CPU adalah permasalahan menentukan proses mana pada ready queue yang dialokasikan ke CPU. Terdapat beberapa algoritma penjadwalan CPU, diantaranya :

1. Algoritma Penjadwalan First Come, First Served (FIFO).
2. Algoritma Penjadwalan Shortest Job First.
3. Algoritma Penjadwalan Priority Schedulling (jadwal prioritas).
4. Algoritma Penjadwalan Round Robin.

Setiap algoritma diukur “turnaround time” dan “waiting time” untuk membandingkan performansi dengan algoritma lain. Dan untuk mengukur turnaround time dan waiting time, digunakan “Gant Chart” . CPU time (Burst Time) membutuhkan semua proses diasumsikan diketahui. Arrival time untuk setiap proses pada ready queue diasumsikan diketahui.

 1. First Come First Serve (FCFS)

Adalah Proses yg meminta CPU duluan yg dialokasikan CPU duluan

·         Disebut juga FIFO

·         Non-preemptive

·         Digunakan pada sistem batch

·         Analogi dunia nyata: restoran cepat saji

·         Implementasi: antrian FIFO

.         Proses baru memasuki belakang antrian

.         Scheduler memilih dari depan antrian

·         Metrik performansi: waktu tunggu rata-rata

·         Parameter:Burst time (dlm ms), waktu dan urutan kedatangan

FCFS : Masalah

·         Non-preemptive

·         AWT tidak optimal

·         Tidak bisa menggunakan sumberdaya secara paralel:

.  Asumsi: 1 proses CPU-bounded dan banyak proses I/O-bounded

.  Hasil: Convoy effect, utilisasi CPU dan perangkat I/O sangat rendah

link video simulasi nya : http://www.youtube.com/watch?v=FiGKndlvO8I

2. Shortest Job First (SJF)

·         Dahulukan job dengan waktu eksekusi tersingkat

·         Digunakan pada sistem batch

·         Ada 2 tipe:

.  Non-preemptive

.   Preemptive

·         Kebutuhan: waktu eksekusi harus diketahui terlebih dahulu

·         Optimal jika semua job tersedia pada waktu yg sama

·         Memberikan waktu tunggu rata-rata terbaik

Masalah pada SJF

·         Starvation

·         Pada kondisi tertentu, suatu job mungkin tidak pernah menyelesaikan eksekusinya

·         Contoh:

·         Proses A dgn elapse time 1 jam tiba pd waktu 0. Namun, pd waktu yg sama dan setiap 1 menit berikutnya tiba proses singkat dgn elapse time 2 menit.

·          Hasilnya: A tidak pernah mendapat jataheksekusi

Link Video : http://www.youtube.com/watch?v=u9VOokHuXIA

3. Penjadwalan Prioritas

·         Tiap proses diberi prioritas

·         Penjadwalan FCFS within each priority level.

·         Proses dgn prioritas lebih tinggi dijadwalkan duluan

.  Preemptive

.  Non-preemptive

·         Masalah:

.  Mungkin tidak menghasilkan waktu tunggu ratarata yg baik

.  Dpt menyebabkan infinite blocking atau starvation pd proses dgn prioritas rendah

Penentuan Prioritas

·         Ada 2 pendekatan:

.  Statis (untuk sistem dgn perilaku aplikasi yg teratur dan telah diketahui)

.  Dinamis (sebaliknya)

·         Prioritas dpt ditentukan berdasarkan:

.  Biaya terhadap user

.  Tingkat kepentingan user

.  Umur proses (aging)

.   % waktu CPU yg telah digunakan pd x jam terakhir

Link video : http://www.youtube.com/watch?v=c-DuS9iYkWc 

 4. Round Robin

·         Tiap proses memperoleh alokasi waktu CPU dlm kuantum waktu, biasanya 10-100 ms

·         Setelah kuantum waktu lewat, proses dipreempted dan dimasukkan ke belakang antrian ready

·         Jika ada n proses pd antrian ready dan kuantum waktu=q, maka:

.  Pada gilirannya tiap proses memperoleh 1/n waktu CPU selama q

.  Tidak ada proses yg menunuggu lebih dari (n-1)q unit waktu

·         Performansi:

.  q besar FIFO

.  q kecil overhead utk context switch sangat besar

Link Video : http://www.youtube.com/watch?v=GjrxO-PDPdk

SUMBER