Algoritma Penjadualan

Algoritma Penjadualan

1.      First-come, first-served (FCFS)

Algoritma:

a.       Proses yang request CPU pertama kali akan mendapatkan jatah CPU.

b.      algoritma maupun struktur data merupakan yang paling sederhana : menggunakan FIFO queue (ready queue).

Contoh :

Ada tiga buah proses yang datang secara bersamaan yaitu:

§    Process              Burst Time

    P1                        24

    P2                         3

    P3                         3

§  Diketahui proses yang tiba adalah P1, P2, P3. Gant chartnya  adalah :

§  Hitunglah waiting time ( burst time + waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS, Waiting time untuk P1 = 0; P2 = 24; P3 = 27

§  Average waiting time: (0 + 24 + 27)/3 = 17

Diketahui proses yang tiba adalah P2, P3, P1. Gant chart-nya adalah :

 

§  Waiting time untuk P1 = 6; P2 = 0; P3 = 3

§  Average waiting time: (6 + 0 + 3)/3 = 3  (Lebih baik dari kasus sebelumnya)

§  Convoy effect proses yang pendek diikuti proses yang panjang

2.      Shortest-Job-First (SJF)

Algoritma:

Penggabungan setiap proses merupakan panjang dari burst CPU  berikutnya. Panjang  tersebut digunakan untuk penjadualan proses pada waktu terpendek

    Shortest Job First memiliki  2 skema :

1.      nonpreemptive – CPU hanya satu kali diberikan pada suatu proses, maka proses tersebut tetap akan memakai CPU hingga proses tersebut melepaskannya

2.      preemptive –jika suatu proses tiba dengan panjang CPU burst lebih kecil dari waktu yang tersisa pada ekseksusi proses yang sedang berlangsung, maka dijalankan preemtive. Skema ini dikenal dengan Shortest-Remaining-Time-First (SRTF).

Contoh

a.       Process     Arrival Time   Burst Time

                     P1                0.0                     7

                     P2                2.0                     4

                     P3                4.0                     1

                     P4                5.0                     4

a.       SJF (non-preemptive)

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

b.      SJF (preemptive)

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

3.      Priority

Algoritma:

a.       Setiap proses akan mempunyai prioritas tertinggi  (bilangan integer).

b.      CPU diberikan ke proses dengan prioritas tertinggi (smallest integer º highest priority).

c.       Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU.

d.      Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis.

e.        SJF adalah contoh priority scheduling dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya.

Contoh permasalahan dalam sistem :

Setiap 10 menit, prioritas dari masing-masing proses yang menunggu dalam queue dinaikkan satu tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21 jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang tertinggi (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi).

4.      Round-Robin (RR)

Algoritma:

Proses akan mendapat jatah sebesar time quantum. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya. Jadi,,semua proses mendapat jatah waktu yang sama dari CPU yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.

Contoh RR (Q =20)

§  Process              Burst Time

       P1                       53

       P2                       17

      P3                        68 

      P4                        24

§  Gantt Chart

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

5.      Multilevel Queue

Algoritma:

§  proses sesuai dengan sifat dari : Interaktif (response cepat) dan Batch dll

§  Partisi “ready queue” dalam beberapa tingkat (multilevel) sesuai dengan proses:

a.       Setiap queue menggunakan algoritma schedule sendiri

b.       Foreground proses (interaktif, high prioritiy): RR

c.       Background proses (batch, low priority): FCFS

§  Setiap queue mempunyai prioritas yang fixed.

6.      Multilevel Feedback Queue

Algoritma:

§  Suatu proses dapat berpindah diantara beragam antrian

§  Perlu feedback untuk penentuan proses naik/turun prioritasnya (dinamis):

a.       Aging dapat diimplementasikan sesuai dengan lama proses pada satu queue.

b.      Suatu proses yang menggunakan CPU sampai habis (tanpa I/O wait) => CPU-bound (bukan proses interaktif) dapat dipindahk ke queue dengan prioritas lebih rendah

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.