Algoritma Penjadwalan Dalam Sistem Operasi

Oktober 07, 2016

Algoritma Penjadwalan Dalam Sistem Operasi

Dalam Sistem Operasi (Operating System) tentunya banyak sekali proses yang harus dieksekusi. Maka muncul permasalahan untuk memutuskan proses mana yang akan dilaksanakan dalam suatu sistem. untuk itu diperlukan kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer.

Untuk menyikapi hal tersebut maka dirumuskanlah sebuah Algoritma penjadwalan yang berfungsi sebagai penentu proses manakah yang akan di eksekusi terlebih dahulu oleh CPU.

Proses yang belum mendapat jatah alokasi dari CPU, akan mengantri di ready queue.

Dan kemudian dilakukan proses eksekusi.

Algoritma penjadwalan tersebut pun ada beberapa cara, tergantung kebutuhan kita untuk menggunakan cara yang mana.

Berikut beberapa ilustrasi Algoritma Penjadwalan, antara lain:

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 gambar urutan kejadian proses dalam Algoritma Round Robin.

Contoh urutan suatu proses dengan menggunakan Algoritma Round Robin.

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.

2. 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 atau antrian dengan prinsip first in first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.

Contoh Permasalahan :

Ada empat buah proses yang datang secara bersamaan yaitu pada 0 ms,

P1 memiliki burst time 8 ms,

P2 memiliki burst time 7 ms,

P3 memiliki burst time 10 ms,

Dan P4 memiliki burst time 6 ms.

Apabila kita gunakan Algoritma FCFS ini maka analisisnya akan dijelaskan dalam gantt chart sebagai berikut:

Ketika CPU tidak mengerjakan sesuatu atau dalam posisi 0 datang sebuah proses yang dinamakan P1 yang membutuhkan waktu penyelesaian yang berjumlah 8. Karena FCFS ini melakukan proses menurut kapan proses itu datang atau yang bisa kita katakan sebagai proses antrian, maka proses selanjutnya akan di kerjakan setelah proses yang berada di depannya selesai untuk di kerjakan. Tadi proses P1 selesai di kerjakan di 8, sementara itu ada P2,P3,dan P4 yang sedang menunggu untuk di kerjakan selanjutnya.

Ketika P1 selesai dikerjakan di 8, maka akan di lanjutkan dengan pengerjaan P2 yang memiliki waktu pengerjaan sebesar 7, sehingga proses P2 akan selesai di kerjakan pada posisi 15. P1 dan P2 sudah selesai pengerjaannya, tinggal menunggu pengerjaan daripada P3 dan P4. Dan begitupun selanjutnya sampai P4 selesai untuk di proses.

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:

· Waiting time rata-ratanya cukup lama

· Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU

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

Berikut contoh analisis Algoritma Priority Scheduling :

Sudah dijelaskan pada gambar di atas bahwa proses dengan Algorima Priority Scheduling yang dieksekusi terlebih dahulu yakni P2 dengan priority tertinggi dan dengan waktu penyelesaian 8. Setelah P2 selesai maka akan dilanjutkan dengan P4 yang memiliki prioritas tertinggi berikutnya dengan durasi pengerjaan sebesar 3. Kemudian disusul dengan pengerjaan P3 dengan waktu 7. Dan yang terakhir pengerjaan P1 dengan durasi 6.

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.

4. 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 :

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

Dapat dilihat pada contoh gambar di atas P1 datang di awal dengan burst time 7 dan tetap berlanjut sampai akhir proses P1. Baru kemudian di lanjut oleh P3 dengan burst time terkecil yaitu 1, baru kemudian dilanjutkan dengan P2 dengan time arrival lebih dulu dengan burst time 4, dan diikuti oleg P4 yang memiliki burst time sama namun masuk di queue pada arrival time terakhir.

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

Jika kita perhatikan gambar di atas sedikit berbeda dari Shortest Job Scheduling First Non-Preempetive, Shortest Job Scheduling First Preempetive ini mendahulukan P1 namun sampai di waktu ke 2, karna disebabkan Muncul P2 ke queue maka P1 dihentikan di waktu ke 2 dan dilanjutkan oleh P2 yang memiliki burst time lebih rendah daripada P1. Kemudian dilanjutkan oleh P3 karna memiliki burst time Lebih rendah, kemudian disusul dengan P4 dan kembali lagi ke P1.

Walaupun algoritma ini dapat disebut algoritma yang cukup optimal, 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

5. Multilevel Queue

Ide dasar dari algoritma ini berdasarkan pada sistem prioritas proses. Prinsipnya, jika setiap proses dapat dikelompokkan berdasarkan prioritasnya, maka akan didapati queue seperti pada gambar berikut:

hal ini dapat dilihat bahwa seolah-olah algoritma dengan prioritas yang dasar membentuk suatu queueberdasarkan prioritas proses, dimana setiap queue akan berjalan dengan algoritma FCFS dan dapat diketahui bahwa algoritma FCFS memiliki banyak kelemahan, dan 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.

Berawal dari priority scheduling, 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.

Untuk mengatasi hal tersebut, salah satu caranya adalah dengan memodifikasi algoritma ini dengan adanya jatah waktu maksimal untuk tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan dan digantikan oleh antrian dibawahnya, dan tentu saja batas waktu untuk tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

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

Semua proses yang baru datang akan diletakkan pada queue 0 (quantum = 8 ms).

Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke queue 1 (quantum = 16 ms)

Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, dan jika suatu proses di queue 1 tidak selesai dalam 16 ms, maka proses tersebut akan dipindahkan ke queue 2 4. Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan berjalan dengan algoritma FCFS.