Algoritma Penjadwalan CPU

a.      Priority Scheduling

Terdapat Lima Proses yang datang secara berurutan dalam CPU burst dalam milidetik.

1.                     Process                        Burst Time                  Priority

                            P₁                                    6                                3

                            P₂                                    1                                1

                            P₃                                    3                                3

                            P₄                                    1                                4

                            P₅                                    4                                2

P2

P5

P1

P3

P4

  0    1              5                     11           14     15

Waktu Tunggu adalah P₁ = 5,  P₂ = 0, P₃ = 11, P ₄ = 14, dan  P ₅ = 1

Rata – rata Waktu Tunggu adalah ( 5 + 0 + 11 + 14 + 1 ) / 5 = 6,2

2.                     Process                        Burst Time                  Priority

                            P₁                                    5                                2

                            P₂                                    2                                1

                            P₃                                    1                                4

                            P₄                                    2                                2

                            P₅                                    3                                2

P2

P5

P1

P3

P4

  0    2              5                     10           11     13

Waktu Tunggu adalah P₁ = 5,  P₂ = 0, P₃ = 10, P ₄ = 11, dan  P ₅ = 2

Rata – rata Waktu Tunggu adalah ( 5 + 0 + 10 + 11 + 2 ) / 5 = 5,6

3.                     Process                        Burst Time                  Priority

                            P₂                                    20                              3

                            P₁                                    2                                1

                            P₃                                    4                                3

                            P₄                                    3                                4

                            P₅                                    4                                2

P1

P5

P2

P3

P4

  0    2              6                     26           30     33

Waktu Tunggu adalah P₁ = 0,  P₂ = 6, P₃ = 26, P ₄ = 30, dan  P ₅ = 2

Rata – rata Waktu Tunggu adalah ( 0 + 6 + 26 + 30 + 2 ) / 5 = 12,8

4.                     Process                        Burst Time                  Priority

                            P₁                                    6                                3

                            P₂                                    0                                1

                            P₃                                    3                                3

                            P₄                                    12                              4

                            P₅                                    20                              2

P2

P5

P1

P3

P4

  0    0              20                   26           29     41

Waktu Tunggu adalah P₁ = 20,  P₂ = 0, P₃ = 26, P ₄ = 29, dan  P ₅ = 0

Rata – rata Waktu Tunggu adalah ( 20 + 0 + 26 + 29 + 0 ) / 5 = 15

5.                     Process                        Burst Time                  Priority

                            P₁                                    21                              3

                            P₂                                    4                                1

                            P₃                                    41                              3

                            P₄                                    9                                4

                            P₅                                    30                              2

P2

P5

P1

P3

P4

  0    4              34                   55           96     105

Waktu Tunggu adalah P₁ = 34,  P₂ = 0, P₃ = 55, P ₄ = 96, dan  P ₅ = 4

Rata – rata Waktu Tunggu adalah ( 34 + 0 + 55 + 96 + 4 ) / 5 = 37,8

 

Algoritma Shortest Job First Scheduler

Algoritma ini digunakan ketika CPU bebas proses yang mempunyai waktu terpendek untuk menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut. Prinsip algoritma penjadwalan ini adalah, proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. Oleh karena itu, algoritma ini optimal jika digunakan, tetapi sulit untuk diimplementasikan karena sulit mengetahui CPU burst selanjutnya. Ada dua skema dalam SJFS ini yaitu:

1. Non premptive— ketika CPU memberikan kepada proses itu tidak bisa ditunda hingga selesai.
2. premptive— bila sebuah proses datang dengan waktu proses lebih rendah dibandingkan dengan waktu proses yang sedang dieksekusi oleh CPU maka proses yang waktunya lebih rendah mendapatkan prioritas. Skema ini disebut juga Short – Remaining Time First (SRTF). Contoh :

Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Contoh SJF Primtive SJF algoritma mungkin adalah yang paling optimal, karena ia memberikan rata-rata minimum waiting untuk kumpulan dari proses yang mengantri.


Average waiting time = (9 + 1 + 0 +2)/4 = 3
https://muhaiminsi11.wordpress.com/algoritmapenjadwalancpu/

Algoritma Penjadwalan CPU yang tdk berurutan

Soal 1.

Process | Arrival Time | Burst Time

P1                0.0                       7

P2                2.0                       4

P3                4.0                       1

P4                5.0                       4

**** SJF (non-preemptive) ****

P1

P3

P2

P4

0                      7     8          12       16

Waiting time

P1 = 0

P3 = 7 - 4 = 3 (dilihat arrival time)

P2 = 8 - 2 = 6 (dieksekusi mulai waktu ke-8 tapi datang pada waktu ke-2)

P4 = 12 - 5 = 7 (dieksekusi mulai waktu ke-12 tapi datang waktu ke-5)

Average waiting time 0 + 6 + 3 + 7 / 4 = 16/4 = 4

**** SJF (Preemptive) ****

P1

P2

P3

P2

P4

P1

0       2       4      5          7                   11               16

pada waktu 0 P1 dieksekusi, burst time = 7

pada waktu 2 P2 datang, burst time 4; P1 masih sisa 5 >> di run yg kecil dulu (P2)

pada waktu 4 P3 datang, burst time 1; P2 masih sisa 2 >> di run yg kecil dulu (P3)

waiting time

P1 = 0 + 9 (9 berasal P1 di run 11 datang 2) = 9

P2 = 0 + 1 (1 berasal P2 di run 5 datang 4) = 1

P3 = 0 (datang wktu 4 dieksekusi waktu 4)

P4 = 7 - 5 (datang waktu 5 dieksekusi 7)
Average waiting time 9 + 1 + 0 + 2 / 4 = 12/4 = 3

Soal 2.

Process | Arrival Time | Burst Time

P1                0.0                       6

P2                2.0                       5

P3                2.0                       2

P4                3.0                       5

**** SJF (non-preemptive) ****

P1

P3

P2

P4

0                      6     8          13       18

Waiting time

P1 = 0

P3 = 6 - 2 = 4 (dilihat arrival time)

P2 = 8 - 2 = 6 (dieksekusi mulai waktu ke-8 tapi datang pada waktu ke-2)

P4 = 13 - 3 = 10 (dieksekusi mulai waktu ke-13 tapi datang waktu ke-3)

Average waiting time 0 + 6 + 4 + 10 / 4 = 20/4 = 5

Soal 3.

Process | Arrival Time | Burst Time

P1                0.0                       9

P2                3.0                       5

P3                6.0                       3

P4                7.0                       6

**** SJF (non-preemptive) ****

P1

P3

P2

P4

0                      9     14        17       23

Waiting time

P1 = 0

P3 = 9 - 6 = 3 (dilihat arrival time)

P2 = 14 – 3 = 6 (dieksekusi mulai waktu ke-14 tapi datang pada waktu ke-3)

P4 = 17 - 7 = 10 (dieksekusi mulai waktu ke-17 tapi datang waktu ke-7)

Average waiting time 0 + 6 + 3 + 7 / 4 = 16/4 = 4

Soal 4.

Process | Arrival Time | Burst Time

P1                0.0                       10

P2                2.0                       3

P3                4.0                       4

P4                6.0                       8

**** SJF (non-preemptive) ****

P1

P3

P2

P4

0                      10     13        17       25

Waiting time

P1 = 0

P3 = 10 - 4 = 6

P2 = 13 – 2 = 11

P4 = 17 - 6 = 11

Average waiting time 0 + 11 + 6 + 11 / 4 = 28/4 = 7

Soal 5.

Process | Arrival Time | Burst Time

P1                0.0                       5

P2                2.0                       2

P3                3.0                       1

P4                4.0                       2

**** SJF (non-preemptive) ****

P1

P3

P2

P4

0                      5     6        8       10

Waiting time

P1 = 0

P3 = 5 - 3 = 2

P2 = 6 – 2 = 4

P4 = 8 - 4 = 4

Average waiting time 0 + 4 + 2 + 4 / 4 = 10/4 = 2,5

Algoritma Penjadwalan Round Robin.

Algoritma Round Robin (RR) 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 :

• Tipikal: lebih lama waktu rata-rata turnaround dibandingkan SJF, tapi mempunyai response terhadap user lebih cepat

Ada Tiga proses : P₁,  P_2,  dan  P₃ yang meminta pelayanan CPU dengan quantum-time sebesar 4 milidet.

1.                     Process                        Burst Time                 

                            P₁                                    24                             

                            P₂                                    3                               

                            P₃                                    3                               

P1

P2

P3

P1

P1

P1

P1

P1

 0              4        7                 10               14            18           22            26         30

Waktu Tunggu adalah P₁ = 6,  P₂ = 4, P₃ = 7

Rata – rata Waktu Tunggu adalah ( 6 + 4+ 7 ) / 3 = 5,66 milidetik

Ada Tiga proses : P₁,  P_2,  dan  P₃ yang meminta pelayanan CPU dengan quantum-time sebesar 5 milidet.

2.                     Process                        Burst Time                 

                            P₁                                    30                             

                            P₂                                    3                               

                            P₃                                    3                               

P1

P2

P3

P1

P1

P1

P1

P1

 0              0        3                 6                 12            18           24            30         36

Waktu Tunggu adalah P₁ = 6,  P₂ = 0, P₃ = 3

Rata – rata Waktu Tunggu adalah ( 6 + 0 + 3 ) / 3 = 3 milidetik

Ada Tiga proses : P₁,  P_2,  dan  P₃ yang meminta pelayanan CPU dengan quantum-time sebesar 6 milidet.

3.                     Process                        Burst Time                 

                            P₁                                    30                             

                            P₂                                    2                               

                            P₃                                    3                               

P1

P2

P3

P1

P1

P1

P1

P1

 0              5        7                 10               15            20           25            30         35

Waktu Tunggu adalah P₁ = 6,  P₂ = 5, P₃ = 7

Rata – rata Waktu Tunggu adalah ( 6 + 5 + 7 ) / 3 = 6 milidetik

Ada Tiga proses : P₁,  P_2,  dan  P₃ yang meminta pelayanan CPU dengan quantum-time sebesar 6 milidet.

4.                     Process                        Burst Time                 

                            P₁                                    36                             

                            P₂                                    4                               

                            P₃                                    2                               

P1

P2

P3

P1

P1

P1

P1

P1

 0              6        10               12               18            24           30            36         42

Waktu Tunggu adalah P₁ = 6,  P₂ = 6, P₃ = 10

Rata – rata Waktu Tunggu adalah ( 6 + 6 + 10 ) / 3 = 7,33 milidetik

Ada Tiga proses : P₁,  P_2,  dan  P₃ yang meminta pelayanan CPU dengan quantum-time sebesar 3 milidet.

5.                     Process                        Burst Time                 

                            P₁                                    18                             

                            P₂                                    2                               

                            P₃                                    2                               

P1

P2

P3

P1

P1

P1

P1

P1

 0              3        5                 7                 10            13           16            19         22

Waktu Tunggu adalah P₁ = 6,  P₂ = 3, P₃ = 5

Rata – rata Waktu Tunggu adalah ( 6 + 3 + 5 ) / 3 = 4,66  milidetik

Multilevel Feedback Queue

Algoritma ini mirip sekali dengan algoritma multilevel queue. Perbedaannya ialah algoritma ini mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini menguntungkan proses interaksi karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi penuh dan M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

 Gambar Multilevel Feedback Queue

Algoritma ini didefinisikan melalui beberapa parameter, antara lain:

1. Jumlah antrian.
2. Algoritma penjadwalan tiap antrian.
3. Kapan menaikkan proses ke antrian yang lebih tinggi.
4. Kapan menurunkan proses ke antrian yang lebih rendah.
5. Antrian mana yang akan dimasuki proses yang membutuhkan.

Dengan pendefinisian seperti tadi membuat algoritma ini sering dipakai, karena algoritma ini mudah dikonfigurasi ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik, kita harus mengetahui nilai parameter tersebut.

Multilevel feedback queue adalah salah satu algoritma yang berdasar pada algoritma multilevel queue. Perbedaan mendasar yang membedakan multilevel feedback queue dengan multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dengan prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut :

1. Semua proses yang baru datang akan diletakkan pada queue 0 ( quantum= 8 ms).
2. Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke queue 1 ( quantum= 16 ms).
3. Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, dan jika suatu proses di queue 1 tidak selesai dalam 16 ms, maka proses tersebut akan dipindahkan ke queue 2.
4. Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan berjalan dengan algoritma FCFS.

Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dalam hal ini ditentukan oleh time quantum, namun dalam prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih dahulu parameter-parameternya, yaitu:

1. Jumlah antrian.
2. Algoritma internal tiap queue.
3. Aturan sebuah proses naik ke antrian yang lebih tinggi.
4. Aturan sebuah proses turun ke antrian yang lebih rendah.
5. Antrian yang akan dimasuki tiap proses yang baru datang.

Contoh: Terdapat tiga antrian; Q1=10 ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam 40 ms tidak selesai, maka dipindahkan lagi ke Q3. Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.