Soal dan Jawaban Algoritma Penjadwalan Proses CPU

Penjadwalan CPU terkait dengan bagaimana proses dikelola . Banyak algoritma yang digunakan  untuk penjadwalan proses. Beberapa algoritma yang digunakan antara lain :

1. First-Come First- Serve (FCFS)

Merupakan algoritma yang paling sederhana dalam penjadwalan proses. Proses yang melakukan request terhadap CPU akan diproses oleh CPU. Implementasinya dengan menggunakan algoritma First In First Out – FIFO.  FCFS bersifat non-preemptive yaitu proses yang dikerjakan oleh CPU tidak dapat diinterupsi oleh proses yang lainnya.

Sebagai contoh :

Proses	Burst
P1	10
P2	1
P3	2
P4	1
P5	5

Gant Chart :

Proses diasumsikan datang bersamaan dan masuk dalam antrian penggunaan CPU. Proses akan dikerjakan berdasarkan nomor urutan proses, sedangkan yang lainnya menunggu sampai proses diatasnya selesai dikerjakan.

Dari Gant Chart dapat diperoleh waktu tunggu proses dari CPU yang dapat diambil waktu rata-ratanya.

Waiting Time P1 = 0, Waiting Time P2 = 10, Waiting Time P3 = 11, Waiting Time P4 = 13, Waiting Time P5 = 14.

Avarage Waiting Time (AWT) =  (WT P1 + WT P2 + WT P3 + WT P4 + WT P5)/5

Avarage Waiting Time (AWT) =  (0 + 10 + 11 + 13 + 14)/5 = 9.6 ms

FCFS  dapat juga bekerja dengan adanya prioritas terhadap proses, prioritas dengan nilai terkecil akan diberi status sebagai prioritas tinggi dan akan dikerjakan terlebih dahulu.

Proses	Burst	Prioritas
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

Gant Chart :

Avarage Waiting Time (AWT) =  (0 + 1 + 6 + 16 + 18)/4 = 8.2 ms

Masalah utama pada FCFS adalah adanya antrian dari proses yang menjadi panjang karena waiting time yang rata-rata panjang. Proses-proses yang telah  berada dalam posisi ready akan tetapi CPU belum dapat memprosesnya. Hal ini yang disebut dengan starvation.

2. Shortest Job First (SJF)

Pendekatan  SJF berbeda dengan FCFS, algoritma SJF tergantung dengan panjang proses yang ada pada queue. Ketika CPU akan melakukan  proses, CPU akan memilik proses dengan CPU burst paling kecil. SJF dapat bekerja dengan mode preemptive maupun non-preemptive.

1. Non-preemptive

Proses	Burst
P1	6
P2	8
P3	7
P4	3

Gant chat :Waiting Time P1 = 3

Waiting Time P2 = 16

Waiting Time P3 = 9

Waiting Time P4 = 0

Avarage Waiting Time = (3 + 16 + 9 + 0)/4 = 7 ms

b. Preemptive

SJF dengan waktu kedatangan (arrival time) berbeda.

Proses	Arrival	Burst
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Proses akan di-preemptive jika ada proses masuk, dah penjadwalan dilakukan ulang dengan membandingkan proses yang masuk dengna proses yang sedang dijalankan. Sebaga contoh pada tabel ketika P1 dijalankan dengna membutuhkan 8 ms, akan tetapi datang burst dari proses P2 dengan burst time 4 ms pada deti ke-1. Proses akan berhenti pada detik 1 kemudian membandingkan proses P1 dengan P2. Karena P2 < P1 maka proses P1 akan dikembalikan ke ready queue dengan P1 = 7 dan memproses P2. Demikian seterusnya.

Gant chart :

Waiting Time P1 = 0 + (10-1) = 9

Waiting Time P2 = 1-1 = 0

Waiting Time P3 = 17-2 = 15

Waiting Time P4 =  5-3 = 2

Average Waiting Time = (9 + 0 + 15 + 2 )/4 =  6.5 ms

3. Round Robin (RR)

Round Robin hampir mirip dengan FCFS akan tetapi terdapat proses perpindahan antar proses dimana satu proses melakukan interupsi terhadap proses yang lainnya atau disebut juga dengan preemptive. Proses preemptivedengan menggunakan time quantum atau time slice.

Sebagai contoh :

Proses	Burst
P1	24
P2	3
P3	3

Dengan time slice sebesar 4 ms, penjadwalan yang terjadi adalah sebagai berikut:

P1 mendapatkan kesempatan pada 4 ms (time slice) pertama, karena P1 > time slice maka P1 hanya akan diproses selama time slice, sisa P1 sebesar P1 – time slice akan di preemptive-kan. Selanjutnya penjadwalan akan beralih ke P2, karena P2 < time slice maka P2 diproses hingga selesai, setelah itu penjadwalan beralih ke P3 dan seterusnya.

Waiting Time P1 = 0 + (10 – 4) = 6

Waiting Time P2 = 4

Waiting Time P3 = 7

Average Waiting Time = (6 + 4 + 7 )/3 = 5.66 ms

Pada algoritma RR, tidak ada proses yang dikerjakan dalam satu waktu lebih dari time slice yang disediakan. Jika terdapat n proses pada queue dengan time slice sebesar q, maka setiap proses akan mendapatkan waktu 1/n dengan masing-masing proses sebesar q .Setiap proses akan menunggu setidaknya sebanyak (n-1)x q untuk proses selanjutnya. Sebagai contoh terdapat 5 proses dengan time slice sebesar 20 ms maka masing-masing proses akan mendapatkan waktu sebanyak 20 ms setiap 100 ms.

Performance dari RR tergantung pada ukuran time slice. Jika time slice terlalu besar maka RR akan sama atau mendekati performance FCFS. Akan tetapi jika time slice kecil maka muncul problem context switch yang terlalu banyak, yaitu proses perpindahan dari satu proses ke proses lain yang akan menimbulkan permasalahan. Hal ini terjadi karena perbedaan kecepatan processor dan memori, dengan terjadinya perpindahan yang terlalu sering proses pembacaan CPU ke memori dan sebaliknya akan membebani sistem.