Berbagi Ilmu: Algoritma Penjadwalan CPU Round Robin Menggunakan Bahasa C++

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.

Ketentuan

Ketentuan algoritma round robin adalah sebagai berikut:

Jika quantum dan proses belum selesai maka proses menjadi runnable dan pemroses dialihkan ke proses lain.
Jika quantum belum habis dan proses menunggu suatu kejadian (selesainya operasi I/O), maka proses menjadi blocked dan pemroses dialihkan ke proses lain.
Jika quantum belum habis tapi proses telah selesai, maka proses diakhiri dan pemroses dialihkan ke proses lain.

Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first come first served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang. Algoritma penjadwalan ini dapat diimplementasi sebagai berikut: – Mengelola senarai proses read (runnable) sesuai urutan kedatangan. – Ambil proses yang berada di ujung depan antrian menjadi running. – Bila quantum belum habis dan proses selesai maka ambil proses di ujung depan antrian proses ready. – Jika quantum habis dan proses belum selesai maka tempatkan proses running ke ekor antrian proses ready dan ambil proses di ujung depan antrian proses ready.

B. Bentuk Algoritma

Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time quantum. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, 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. Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first come first served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang.

Permasalahan utama pada round robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 quantum. Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma first come first served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

Urutan Event dalam algoritma Round Robin

Penggunaan Waktu Quantum

Berikut adalah algoritma penjadwalan Round Robin secara Keseluruhan :

Setiap proses mendapat jatah waktu CPU (time slice/quantum) tertentu Time slice/quantum umumnya ntara 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.

Performance 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 context switch sebaliknya akan memerlukan ongkos yang besar.

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 :

C. Contoh :

D. Atau Bisa Di Lihat Hasilnya Di Nota

Adapun untuk melihat Sounce Code-nya bisa di lihat dengan cara Klik Disini

File Lengkapnya Silahkan Klik Disini

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.