Algoritma Penjadwalan Proses Pada Sistem Operasi

Algoritma penjadwalan proses

A. Round Robin

Yaitu salah satu Algoritma penjadwalan yang menggilir proses secara berurutan. Dalam algoritma ini setiap proses akan mendapatkan waktu dari CPU yang kita kita sebut dengan time quantum. Time quantum adalah suatu satuan waktu. Time quantum inilah yang menentukan proses mana yang akan dikerjakan terlebih dahulu oleh CPU dan kemudian proses mana yang akan dilakukan berikutnya. Biasanya suatu proses mendapat jatah time quantum yang sama dari CPU yakni 1-100 milidetik atau (1/n). Jika proses yang sedang dieksekusi selesai dalam waktu kurang dari 1 time quantum, tidak ada masalah. Tetapi jika proses berjalan melebihi 1 time quantum, maka proses tersebut akan dihentikan,lalu digantikan oleh proses yang berikutnya. Proses yang dihentikan tersebut akan diletakkan di queue di urutan paling belakang. Berikut adalah urutan kejadian proses dalam algoritma ini :

    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 time 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.

B. FCFS (First Come First Served).

    Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini setiap proses yang berada pada status ready dimasukkan kedalam FIFO queue, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi. Algoritma FCFS dalam prosesnya tidak mengizinkan sebuah penyelaan dari segi apapun, dengan kata lain Algoritma FCFS ini bersifat non-preempetive atau tidak dapat dilakukan interrupt oleh proses lain. walaupun proses yang menunggu memiliki prioritas yang lebih tinggi. Kelemahan dari algoritma ini adalah : waiting time rata-ratanya cukup lama, terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU

C. Priority Scheduling

    Priority Scheduling merupakan algoritma penjadwalan yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing. Prioritas tersebut dapat ditentukan melalui beberapa karakteristik antara lain:

• Time limit

• Memory requirement

• Akses file

• Perbandingan antara I/O Burst dengan CPU Burst

• Tingkat kepentingan proses

    Priority scheduling juga dapat dijalankan secara preemptive maupun nonpreemptive. Pada preemptive, jika ada suatu proses yang baru datang memiliki prioritas yang lebih tinggi daripada proses yang sedang dijalankan, maka proses yang sedang berjalan tersebut dihentikan, lalu CPU dialihkan untuk proses yang baru datang tersebut. Sementara itu, pada non-preemptive, proses yang baru datang tidak dapat menganggu proses yang sedang berjalan, tetapi hanya diletakkan di dalam queue.

    Kelemahan pada priority scheduling adalah dapat terjadinya indefinite blocking (starvation). Yaitu proses dengan prioritas rendah berkemungkinan untuk tidak dieksekusi jika terdapat proses lain yang memiliki prioritas lebih tinggi darinya. Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam queue secara bertahap.

D. Shortest-Job-First-Scheduling (SJF)

    Algoritma Shortest Job First Scheduling (SJF) ini memungkinkan setiap proses yang memiliki burst time (waktu pengerjaan) terkecil yang akan dikerjakan terlebih dahulu. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan otomatis waiting time rata-ratanya juga menjadi pendek pula, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal. Algoritma Shortest Job First Scheduling (SJF) ini memiliki 2 jenis, yaitu :

1. Shortest Job First Scheduling Non-preemptive

    CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil. 

2. Shortest Job First Scheduling Preemptive

    Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining-Time-First scheduling.

    Secara keseluruhan algoritma ini masih memiliki beberapa kekurangan yaitu: Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.

E. Multilevel Queue

    Ide dasar dari algoritma ini berdasarkan pada sistem prioritas proses. Prinsipnya, jika setiap proses dapat dikelompokkan berdasarkan prioritasnya, maka akan didapati queue. hal ini dapat dilihat bahwa seolah-olah algoritma dengan prioritas yang dasar membentuk suatu queue berdasarkan prioritas proses, dimana setiap queue akan berjalan dengan algoritma FCFS dan dapat diketahui bahwa algoritma FCFS memiliki banyak kelemahan. 

    Oleh karena itu maka dalam prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dalam masing-masing sub-antriannya untuk meningkatkan kinerjanya, dimana setiap sub-antrian bisa memiliki algoritma internal yang berbeda. Algoritma ini pun memiliki kelemahan yang sama dengan priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dengan prioritas rendah bisa saja tidak mendapat jatah CPU.

F. Multilevel Feedback Queue.

    Algoritma ini mirip sekali dengan algoritma multilevel queue. Perbedaannya ialah algoritma ini mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini menguntungkan proses interaksi karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi penuh dan perangkat I/O dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar. Algoritma ini sangat bergantung pada besar kecilnya quantum masing-masing proses.