Algoritma Penjadwalan CPU

Algoritma Penjadwalan CPU

Penggabungan setiap proses meupakan panjang dari burst CPU  berikutnya.Panjang tersebu digunakan untuk penjadwalan proses pada waktu terpendek

Terdapat 2 skema :

Nonpreemitive –CPU hanya satu kali diberikan pada suatu proses, maka proses tersebut  tetap akan memakai  CPU  hinga proses tersebut melepaskanya

Preemitive -  Jika suatu proses Tiba dengan panjang  CPU burst lebi kecil dari waktu  yang tersisa pada eksekusi proses yang sedang berlangsung ,maka dijalankan preemitive . skema ini dikenal dengan shortest – Remaining Time First (SRTF)

SJF  akan Optimal,ketika rata-rata waktu tunggu minimum untuk set proses yang diberikan.

Contoh Non-Preemptive SJF

Process Arrival Tim      Burst Time

P₁          0.0                        7

P₂          2.0                        4

P₃      4.0                        1

P₄          5.0                        4

SJF  (Non preemitive)

P1	P3	P2	P4

0          3               7        8                                              12               16

Average waiting time =(0+6+3+7)/4 =-4

Contoh Preemptive SJF

Process Arrival Tim      Burst Time

P₁          0.0                        7

P₂          2.0                        4

P₃      4.0                        1

P₄          5.0                        4

SJF  (preemitive)

P1	P2	P3	P2	P4	P1

0        2        4        5        7                 11               16

Average waiting time = (9+1+0+2)/4-3

Round Robin (RR).

Setiap proses mendapat jatah waktu  CPU (Time slince/quantum) Tertentu misalkan 10 atau 100 milidetik.

Setelah waktu tersebut maka proses akan di-preemot dan dipindahkan  ke ready queue.

Adil dan Sedrrhana.

Jika dapa diproses di ” ready queue” dan waktu kuantum q (milidetik),maka d:

Maka setiap proses akan mendapatkan  1/n dari waktu CPU.

Proses tidak akan menunggu libih lama dari ( n-1)1 time units.

Performance

Q  besar => FIFO

Q kecil => q harus lebibesar dengan mengacup pada context

Switch,jika tidak overhead akan terlalu besar.

Contoh RR (Q  = 20)

Process                 Brus time

          P₁                                          53

P₂                                          17

          P₃                                          64

          P₄                                          24

Gantt chart

P1	P2	P3	P4	P1	P3	P4	P1	P3	P3

0        20      37     57      77      97      117    121    134    154    162

Tipikal: lebih lama waktu rata-rata turnaround Dibandingkan  SJF Tapi mempunyai response terhadap user lebih cepat.

·         Algoritma Penjadwalan Priority Schedulling (jadwal prioritas)

Penjadualan SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadual Prioritas. Prioritas dapat diasosiasikan masing-masing proses dan CPU dialokasikan untuk proses dengan prioritas tertinggi. Untuk proritas yang sama dilakukan dengan FCFS. Ada pun algoritma penjadual prioritas adalah sebagai berikut: • Setiap proses akan mempunyai prioritas (bilangan integer). Beberapa sistem menggunakan integer dengan urutan kecil untuk proses dengan prioritas rendah, dan sistem lain juga bisa menggunakan integer urutan kecil untuk proses dengan prioritas tinggi. Tetapi dalam teks ini diasumsikan bahwa integer kecil merupakan prioritas tertinggi. • CPU diberikan ke proses dengan prioritas tertinggi (integer kecil adalah prioritas tertinggi). • Dalam algoritma ini ada dua skema yaitu: 1. Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU. 2. Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis. • SJF adalah contoh penjadual prioritas dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya. Permasalahan yang muncul dalam penjadualan prioritas adalah indefinite blocking atau starvation. • Kadang-kadang untuk kasus dengan prioritas rendah mungkin tidak pernah dieksekusi. Solusi untuk algoritma penjadual prioritas adalah aging. • Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU. Contoh Priority:

Algoritma Round Robin dirancang untuk sistem time sharing. Algoritma ini mirip dengan penjadual FCFS, namun preemption ditambahkan untuk switch antara proses. Antrian ready diperlakukan atau dianggap sebagai antrian sirkular. CPU mengelilingi antrian ready dan mengalokasikan masing-masing proses untuk interval waktu tertentu sampai satu time slice/ quantum. Berikut algoritma untuk penjadual Round Robin: • Setiap proses mendapat jatah waktu CPU (time slice/ quantum) tertentu Time slice/quantum umumnya antara 10 – 100 milidetik.

1.      Setelah time slice/ quantum maka proses akan di-preempt dan dipindahkan ke antrian ready.

2.      Proses ini adil dan sangat sederhana.

• Jika terdapat n proses di “antrian ready” dan waktu quantum q (milidetik), maka:

1.      Maka setiap proses akan mendapatkan 1/n dari waktu CPU.

2.      Proses tidak akan menunggu lebih lama dari: (n-1)q time units.

• Kinerja dari algoritma ini tergantung dari ukuran time quantum.

1.      Time Quantum dengan ukuran yang besar maka akan sama dengan FCFS.

2.      Time Quantum dengan ukuran yang kecil maka time quantum harus diubah ukurannya lebih besar dengan respek pada alih konteks sebaliknya akan memerlukan ongkos yang besar. Contoh :

Round Robin

Waiting Time

P1 = 0

P2 = 4

P3 = 5

P4 = 7

P5 = 8

P1=12

P5=16

P1=17

Average

Waiting Time

AVG = 0+4+5+7+8+12+16+17/8

            AVG = 11 ms