Algoritma Penjadwalan CPU Round Robin Menggunakan Bahasa Java


Nama Anggota:

1. Ainurrofiq Qurrohman ( 1210511030 )

2. Hilman Yanuar ( 1210511020 )

3. Jihan Haroki ( 1210511064 )

4. Mochammad Fariz Satyawan ( 1210511022 )

Kelas : Lokal 3 B TI


A. Dasar Teori Penjadwalan CPU Round Robin

Konsep dasar dari algoritma ini adalah dengan menggunakan time-sharing. Pada dasarnya algoritma ini sama dengan FCFS, hanya saja bersifat preemptive. Setiap proses mendapatkan waktu CPU yang disebut dengan waktu quantum (quantum time) untuk membatasi waktu proses, biasanya 1-100 milidetik. Setelah waktu habis, proses ditunda dan ditambahkan pada ready queue.
Jika suatu proses memiliki CPU burst lebih kecil dibandingkan dengan waktu  quantum, maka proses tersebut akan melepaskan CPU jika telah selesai bekerja, sehingga CPU dapat segera digunakan oleh proses selanjutnya. Sebaliknya, jika suatu proses memiliki CPU burst yang lebih besar dibandingkan dengan waktu quantum, maka proses tersebut akan dihentikan sementara jika sudah mencapai waktu quantum, dan selanjutnya mengantri kembali pada posisi ekor dari ready queue, CPU kemudian menjalankan proses berikutnya.

Menghitung Average Waiting Time dalam Algoritma Penjadwalan Round Robin

Dalam algoritma penjadwalan proses Round Robin, proses akan diberikan porsi waktu pengerjaan yang sama dari tiap-tiap prosesnya. Algoritma Round Robin ini disebut dengan algoritma yang adil. Untuk memahami dari cara kerja algoritma penjadwalan Round Robin ini, mari kita kerjakan soal berikut :



Hitunglah Average Waiting Times proses di atas dengan menggunakan algoritma penjadwalan Round Robin dengan QT = 5 ms.

Penyelesaian:

  • Seperti halnya algoritma penjadwalan sebelumnya, langkah pertama untuk mencari AWT dengan Algoritma penjadwalan Round Robin dilakukan dengan membuat Gantt Chart prosesnya. Berikut gambarnya:

Dari Gantt Chart di atas terlihat bahwa setiap proses dikerjakan menurut waktu yaitu setiap proses di proses sebesar 5. Awalnya P1 akan di kerjakan sebanyak 5 langkah, kemudian, P2 sebanyak 5 langkah, dan begitupun selanjutnya hingga P5. Proses yang sudah di proses menurut porsi waktu yang diberikan akan kembali menunggu dan berada paling belakang dari antrian proses yang ada. Contohnya P1 dikerjakan di awal, kemudian ada P2, P3,P4,dan P5 yang mengantri di belakangnya. Jika P1 selesai di proses menurut porsi waktunya maka P1 akan di pindahkan ke belakang, sehingga urutannya menjadi P2, P3, P4, P4, P1. begitupun seterusnya.

  • Setelah mendapatkan Gantt Chartnya, sekarang kita menghitung Waiting Time-nya, lihat gambar di bawah:



  •  Dari Waiting Times di atas dapat kita tentukan AWTnya yaitu dengan cara :

B. Source Code Bahasa JAVA

Untuk source code bisa di download di github atau dilihat dibawah ini.

Download Github
package tugas.SO;

import java.util.*;

public class roundrobin {

 public static void main(String [] args){
  
  //Deklarasi variabel 
  Scanner scn = new Scanner(System.in);
  int ts,tp,ip,num,qSampai,qbHabis,t,wr = 0,tps = 0,rpdT=0,sortAkhir;
  double art = 0,awt=0,att=0;
    
  // 1. Input Time slice
  System.out.print("Masukkan time slice: ");
  ts = scn.nextInt();
  
  // 2. Input Total Proses
  System.out.print("Masukkan total proses: ");
  tp = scn.nextInt();
  
  // 3. Input Proses
  Integer [][] p = new Integer [tp][8];
  LinkedList<Integer> qid = new LinkedList<Integer>();
  LinkedList<Integer> qcr = new LinkedList<Integer>();
  LinkedList<Integer> hid = new LinkedList<Integer>();
  LinkedList<Integer> hrt = new LinkedList<Integer>();
  LinkedList<Integer> hct = new LinkedList<Integer>();
  
  for(ip=0,num=1;ip<tp;ip++,num++){
   p[ip][0]=num;
   p[ip][3]=0;
   p[ip][4]=0;
   p[ip][5]=0;
   p[ip][6]=0;
   System.out.print("Masukkan Burst Time Proses ke-"+num+" :");
   p[ip][1] = scn.nextInt();
   System.out.print("Masukkan Arrival Time Proses ke-"+num+" :");
   p[ip][2] = scn.nextInt();
  }
  scn.close();
  
  //Penjadwalan
  t=0;
  while(tps<tp){
   
   // 4. Cari Proses yang sampai (AT = t) dan masukan ke queue lalu sort
   for(qSampai=0;qSampai < p.length;qSampai++){
    if(p[qSampai][2] == t){
     qid.add(p[qSampai][0]);
     qcr.add(p[qSampai][6]);
    }

   }

   // 5. Cari Proses yang belum selesai (AT < t) dan masukan ke queue lalu sort
   for (qbHabis = 0; qbHabis < p.length; qbHabis++) {
    //jika sudah pernah jalan
    if(p[qbHabis][2] < t && p[qbHabis][1] != 0){
      boolean ada =false;
      
      for(int cekQ=0;cekQ<qid.size();cekQ++){
       if(p[qbHabis][0]==qid.get(cekQ)){
        ada=true;
       }
       if(cekQ+1==qid.size()){
        if(ada==false){
         qid.add(p[qbHabis][0]);
         qcr.add(p[qbHabis][6]);
        }
       }
      }
    }
   }

   // Sort queue
   if(qid.size()>2){
    Integer[][] qSort = new Integer[qid.size()-1][2];
    for(sortAkhir=0;sortAkhir<qid.size()-1;sortAkhir++){
     qSort[sortAkhir][0] = qid.get(sortAkhir+1);
     qSort[sortAkhir][1] = qcr.get(sortAkhir+1);
    }
    
    Arrays.sort(qSort, new Comparator<Integer[]>() {
              @Override
              public int compare(final Integer[] entry1, final Integer[] entry2) {
                  final Integer time1 = entry1[1];
                  final Integer time2 = entry2[1];
                  return time1.compareTo(time2);
              }
          });
    
    for(sortAkhir=0;sortAkhir<qid.size()-1;sortAkhir++){
     qid.set(sortAkhir+1, qSort[sortAkhir][0]);
     qcr.set(sortAkhir+1, qSort[sortAkhir][1]);
    }
   }
   
   // 6. Running state & Ready state
   if(wr==0 && qid.isEmpty()==false){
    if(p[qid.get(0)-1][1] > ts){
     wr=ts;
    }else{
     wr=p[qid.get(0)-1][1];
    }
    rpdT=t;
    if(p[qid.get(0)-1][7]==null){p[qid.get(0)-1][7]=rpdT;}
   }
   t++;
   if(!qid.isEmpty()){
    //run
    p[qid.get(0)-1][1]--;
    p[qid.get(0)-1][4]++;
    wr--;
    if(wr==0){
     if(p[qid.get(0)-1][1]==0){
      tps++;
      p[qid.get(0)-1][5]=t;
      //p[qid.get(0)-1][4]=rpdT;
     }
     if(qid.size()==1){
      if(p[qid.get(0)-1][1]!=0){
       qid.add(qid.get(0));
       qcr.add(qcr.get(0));
      }
     }
     p[qid.get(0)-1][6]++;
     hid.add(qid.get(0));
     hrt.add(rpdT);
     hct.add(t);
     qid.removeFirst();
     qcr.removeFirst();
    }
   }
  }// End Penjadwalan
  
  //Tampilan
  System.out.println("\n=================Gantt Chart=================");
  for(int z=0;z<hid.size();z++){
   System.out.print("\t"+"P"+hid.get(z)+"\t");
  }
  for(int z=0;z<hid.size();z++){
   if(z==0){
    System.out.print("\n|===============|");
   }else{
    System.out.print("===============|");
   }
  }
  for(int z=0;z<hid.size();z++){
   if(z==0){
    System.out.print("\n"+hrt.get(0)+"\t\t"+hct.get(0));
   }else{
    System.out.print("\t\t"+hct.get(z));
   }
  }
  int id=0,rt=0,tt=0,wt=0;
  System.out.println("\n\n\n=================Detail Proses=================");
  System.out.println("ID\tRT\tWT\tTT");
  for(int z=0;z<p.length;z++){
   id=p[z][0];
   rt=p[z][7]-p[z][2];
   tt=p[z][5]-p[z][2];
   wt=(p[z][5]-p[z][4])-p[z][2];
   System.out.println("P"+id+"\t"+rt+"\t"+wt+"\t"+tt);
  }
  for(int i=0;i<p.length;i++){
   awt+=(p[i][5]-p[i][4])-p[i][2];
   if(i+1==p.length){
    awt=awt*1.0/tp;
   }
  }
  System.out.println("Average Waiting Time :"+awt);
  for(int i=0;i<p.length;i++){
   att+=p[i][5]-p[i][2];
   if(i+1==p.length){
    att=att*1.0/tp;
   }
  }
  System.out.println("Average Turnaround Time:"+att);
  for(int i=0;i<p.length;i++){
   art+=p[i][7]-p[i][2];
   if(i+1==p.length){
    art=art*1.0/tp;
   }
  }
  System.out.println("Average Response Time :"+art);
 }

}

C. Hasil Output


D. Analisa

Input time slice
Input total proses
Input Proses
-loop hingga total proses
Simulasi
-loop hingga semua proses selesai
 *Ambil proses yang sampai pada saat t lalu queue
 *Ambil proses yang belum habis burst timenya lalu queue
 *Sort queue proses
 *Proses pada urutan queue pertama masuk Running state
 *Proses pada urutan queue selai urutan pertama masuk Waiting/Ready state
Tampilkan Data
-Gantt Chart
-Detail Proses

E. Kesimpulan 

Penjadwalan proses adalah urutan kerja yang dilakukan oleh system operasi,ini sangat diperlukan untuk kelangsungan system operasi dalam menentukan proses yang akan dieksekusi.

Berdasarkan segi waktu penyelesaian proses, penjadwalan proses preemptive dinilai lebih efektif, karena dalam penjadwalan metode ini proses-proses dengan waktu proses yang lebih pendek akan selesai lebih dulu, karena walaupun terdapat proses dengan waktu proses yang lama berada pada antrian pertama, sedangkan ada proses di antrian kedua dengan waktu proses lebih pendek, maka proses pada antrian pertama dapat disela untuk mengerjakan proses diantrian kedua terlebih dahulu hingga selesai, dengan asumsi penjadwalan preemptive tersebut tidak berprioritas. Beberapa penjadwalan proses yang telah divisualisasikan mempunyai kesamaan dalam menyelesaikan sebuah proses yang berada di dalam antrian. Proses dengan waktu proses terpendek akan diselesaikan terlebih dahulu, setelah itu baru proses-proses lainnya yang mempunyai waktu proses lebih lama.

Sumber Referensi:

1. http://mahadisuta.blogspot.com/2012/12/menghitung-average-waiting-time-dalam_12.html

2. http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/2002/riene101/produk/Simulasi_Penjadwalan_CPU/index.html

3. http://www.setiadyfajar.blogspot.com/ 

4. http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/2002/riene101/produk/Simulasi_Penjadwalan_CPU/Simulasi_Round_Robin.html

Komentar

Posting Komentar

Postingan populer dari blog ini

Membuat Syntax Highlighter di BLOG

Gambar
S yntax Highlighter adalah suatu fitur biasanya dari text editor khususnya editor source code bahasa pemrograman tertentu untuk menampilkan text tersebut dalam berbagai warna agar dapat memudahkan programmer dalam membaca dan menganalisa source code tersebut. Bagi Anda yang sering posting source code pada Web/Blog tentu fitur Syntax Highlighter akan sangat membantu agar source code yang kita posting mudah dibedakan sebagai source code dan tentunya lebih menarik bagi pengunjung. Nah, sekarang masalahnya bagaimana cara kita menggunakan Syntax Highlighter ini pada blog khususnya di blogger.com? Jika di blogspot kita biasa menampilkan kode supaya lebih menarik dengan adanya Blockquote. Sebenarnya hampir sama dengan Blockquote , Syntax Highlighter ini tampilannya membedakan dari tulisan yang lainnya, namuan Syntax Highlighter ini mempunyai kelebihan yaitu dengan adanya fitur-fitur yang didukung oleh jQuery. Kode untuk Syntax Highlighter ini sendiri dibuat
Baca selengkapnya