Penjadwalan CPU Algoritma Round Robin pada Program Java

A.  Dasar Teori Penjadwalan CPU

Penjadwalan CPU adalah pemilihan proses dari antrian ready untuk dapat dieksekusi. Penjadwalan CPU merupakan konsep dari multiprogramming, dimana CPU digunakan secara bergantian untuk proses yang berbeda. Suatu proses terdiri dari dua siklus yaituBurst I/O dan Burst CPU yang dilakukan bergantian hingga proses selesai. Penjadwalan CPU mungkin dijalankan ketika proses:

1.             running ke waiting time

2.             running ke ready state

3.             waiting ke ready state

4.             terminates

Proses 1 dan 4 adalah proses Non Preemptive, dimana proses tersebut tidak bisa di-interrupt, sedangkan 2 dan 3 adalah proses Preemptive, dimana proses boleh di interrupt. Pada saat CPU menganggur, maka sistem operasi harus menyeleksi proses-proses yang ada di memori utama (ready queue) untuk dieksekusi dan mengalokasikan CPU untuk salah satu dari proses tersebut. Seleksi semacam ini disebut dengan shortterm scheduler (CPU scheduler). Komponen yang lain dalam penjadwalan CPU adalah dispatcher, Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian proses yang dilakukan selama short-term scheduling . Waktu yang diperlukan oleh dispatcher untuk menghentikan suatu proses dan memulai proses yang lain disebut dengan dispatch latency. Jika dalam suatu proses Burst CPU jauh lebih besar daripada Burst I/O maka disebutCPU Bound. Demikian juga sebaliknya disebut dengn I/O Bound.

B. Kriteria Penjadwalan

Algoritma penjadual CPU yang berbeda mempunyai property yang berbeda. Dalam memilih algoritma yang digunakan untuk situasi tertentu, kita harus memikirkan properti yang berbeda untuk algoritma yang berbeda. Banyak kriteria yang dianjurkan utnuk membandingkan penjadual CPU algoritma. Kritria yang biasanya digunakan dalam memilih adalah:

1. CPU utilization: kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0 ke 100 persen. Di sistem yang sebenarnya seharusnya ia mempunyai range dari 40 persen samapi 90 persen.
2. Throughput: jika CPU sibuk mengeksekusi proses, jika begitu kerja telah dilaksanakan. Salah satu ukuran kerja adalah banyak proses yang diselesaikan per unit waktu, disebut througput. Untuk proses yang lama mungkin 1 proses per jam; untuk proses yang sebentar mungkin 10 proses perdetik.
3. Turnaround time: dari sudur pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut. Interval dari waktu yang diizinkan dengan waktu yang dibutuhkan untuk menyelesaikan sebuah prose disebut turn-around time. Trun around time adalah jumlah periode untuk menunggu untuk bisa ke memori, menunggu di ready queue, eksekusi di CPU, dan melakukan I/O.
4. Waiting time: algoritma penjadual CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut atau I/O; itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian ready. Waiting time adalah jumlah periode menghabiskan di antrian ready.
5. Response time: di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria. Sering sebuah proses bisa memproduksi output diawal, dan bisa meneruskan hasil yang baru sementara hasil yang sebelumnya telah diberikan ke user. Ukuran yang lain adalah waktu dari pengiriamn permintaan sampai respon yang pertama di berikan. Ini disebut response time, yaitu waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output untu respon tersebut.

C. Algoritma Round Robin

Round Robin merupakan algoritma yang eksekusi proses diatur berdasarkan alokasi waktu tertentu (slot waktu ) yang di atur dengan clock interrupt, clock interrupt mengatur waktu secara periodik. Bila terjadi clock interrupt maka proses yang seddang running dimasukkan ke dalam antrian ready dan proses di antrian ready paling depan di eksekusi

kekurangan dari round robin

• performansi lebih buruk dibanding FCFS jika ukuran slot lebih besar daripada ukuran proses terbesar
• dapat terjadi overhead berlebihan jika ukuran setiap slot terlalu kecil
• proses I/O bound mendapatkan waktu layanan lebih sedikit

Solusi dari kekurangan round robin

round robin dimodifikasi menjadi virtual round robin(VRR)  dengan menambahkan sebuah antrian yang disebut memory antrian auxiliary

Kelebihan dari round robin

• dapat menghindari ketidak adilan layanan terhadap proses kecil seperti yang terjadi pada FCFS
• respone time lebih cepat untuk proses berukuran kecil
• dapat mencegah starvation
• overhead kecil, jika ukuran proses rata rata lebih kecil dibanding ukuran quantum/slot

D. Flowchart

E. Source Code Java

import java.util.Scanner;

public class RoundRobin

{

void buatGaris(int lenGrantChart)

{

for(int i=0; i < lenGrantChart; i++)

{

System.out.print("------");

}

System.out.println();

}

public RoundRobin()

{

/*inisialisasi variabel*/

Scanner scanner = new Scanner(System.in);

int readyQueue[][];

int grantChart[][];

int totalProcess = 0;

int timeSlice = 0;

int totalBurstTime = 0;

int totalQuantum = 0;

System.out.print("masukkan jumlah proses : ");

totalProcess = scanner.nextInt();

System.out.print("masukkan time slice : ");

timeSlice = scanner.nextInt();

//ini akan membuat array [Pn][name], [Pn][BT], [Pn][WT], [Pn][TO], [Pn][RT]

readyQueue = new int[totalProcess][5]; 

System.out.println();

/*masukkan burst time proses*/

for(int i=0; i < readyQueue.length; i++)

{

//set nama proses

readyQueue[i][0] = i; 

//set burst time proses

System.out.print("masukan burst time P"+ i + " : ");

readyQueue[i][1] = scanner.nextInt(); 

//hitung jumlah burst time

totalBurstTime += readyQueue[i][1]; 

//hitung jumlah quantum per proses

totalQuantum += (int) Math.ceil((double)readyQueue[i][1] / (double)timeSlice); 

//set default waiting time, turn around time, dan respon time

readyQueue[i][2] = 0; //set waiting time

readyQueue[i][3] = 0; //set turn around time

readyQueue[i][4] = 0; //set respon time

}

/*running proses*/

grantChart = new int[totalQuantum][3];

int time = 0;

int index = 0;

while (time < totalBurstTime)

{

for(int i=0; i < readyQueue.length; i++)

{

//respon time

if(index < totalProcess) readyQueue[i][4] = time; 

if(readyQueue[i][1] != 0)

{

//waiting time

readyQueue[i][3] += time; 

grantChart[index][0] = readyQueue[i][0]; //name process

grantChart[index][1] = time; //start time quantum process 

//jika burst time >= time slice

if(readyQueue[i][1] >= timeSlice)

{

grantChart[index][2] = time = time + timeSlice; //end time quantum process

readyQueue[i][1] -= timeSlice; //kurangi burst time sebanyak time slice

}

else if(readyQueue[i][1] < timeSlice && readyQueue[i][1] > 0)

{

grantChart[index][2] = time = time + readyQueue[i][1]; //end time quantum process

readyQueue[i][1] = 0; //burst time telah habis

}

//turn around time

if(readyQueue[i][1] == 0) readyQueue[i][2] = time;

index++;

}

}

}

//cetak grant chart

buatGaris(grantChart.length);

for(int i=0; i < grantChart.length; i++)

{

System.out.print("  P" + grantChart[i][0] + "  ");

}

System.out.println();

buatGaris(grantChart.length);

for(int i=0; i < grantChart.length; i++)

{

if(i == 0) System.out.print(grantChart[i][1]);

System.out.print("    " + grantChart[i][2]);

}

System.out.println();

buatGaris(grantChart.length);

System.out.println();

for(int i = 0; i < readyQueue.length; i++)

{

System.out.println("Proses P"+readyQueue[i][0] + "\n" +

"TO : " + readyQueue[i][2] + "\n" +

"WT : " + readyQueue[i][3] + "\n" +

"RT : " + readyQueue[i][4] + "\n"

);

}

}

public static void main (String[] args)

{

new RoundRobin();

}

}

F. Hasil Output

G. Analisa

Masukkan jumlah proses yang ingin di kerjakan,  jumlah prosesnya 4 yaitu P0, P1, P2, P3, lalu tentukan time slicenya yaitu 5, kemudian tentukan masing-masing burst timenya yaitu, P0 = 7, P1 = 10, P2 = 17, P3 = 24.

Hitung TO, WT, dan RT

 Gambar prosesnya :

Hitung TO pada setiap proses, contohnya TO pada P1, yaitu P1 yang nilainya terbesar sampai selesai pengeksekusian terakhir. Kemudian hitung WT pada setiap proses, contohnya WT pada P0, yaitu waktu tunggu pengeksekusian P0 pertama di jumlahkan waktu tunggu pengeksekusian P0 terakhir. Lalu hitung RT pada setiap proses, contohnya pada P2, yaitu nilai yang terkecil pada P2. Untuk mencari rata-rata pada TO hasil perhitungan TO di bagi dengan jumlah proses, begitu juga dengan WT dan RT.

H. Kesimpulan

Program ini merupakan program penjadwalan CPU dengan Round Robin, maksudnya setiap proses diberi kesempatan dieksekusi selama time slice, proses yang melampaui time slice padahal belum selesai, dipindahkan pada antrian paling belakang.