Algoritma Penjadwalan Proses

Jenis – Jenis Algoritma Penjadwalan

1. Nonpreemptive

Non-preemptive algoritma didesain agar setelah proses yang sedang berjalan memasuki negara (adalah proses diperbolehkan), tidak dihapus dari prosesor sampai selesai dengan waktu layanan (secara eksplisit atau hasil prosesor).  Nonpreemptive , menggunakan konsep :

– FIFO (First in first out) atau FCFS (First come first serve)

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.

FIFO jarang digunakan secara mandiri, tetapi dikombinasikan dengan skema lain,misalnya : Keputusan berdasarkan prioritas proses. Untuk proses-pross berprioritassama diputuskan berdasarkan FIFO.

Penjadwalan ini :

• Baik untuk sistem batch yang sangat jarang berinteraksi dengan pemakai. Contoh : aplikasi analisis numerik,  maupun pembuatan tabel.
• Sangat tidak baik (tidak berguna) untuk sistem interaktif, karena tidak memberi waktu tanggap yang baik.
• Tidak dapat digunakan untuk sistem waktu nyata (real-time applications)

Contoh : Ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki burst time 24 ms, P2 memiliki burst time 3 ms, dan P3 memiliki burst time 3 ms. Hitunglah waiting time rata-rata dan turnaround time( burst time + waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS. Waiting time untuk P1 adalah 0 ms (P1 tidak perlu menunggu), sedangkan untuk P2 adalah sebesar 24 ms (menunggu P1 selesai), dan untuk P3 sebesar 27 ms (menunggu P1 dan P2 selesai).
Urutan kedatangan adalah P1, P2 , P3; gantt chart untuk urutan ini adalah:

Waiting time rata-ratanya adalah sebesar(0+24+27)/3 = 17ms. Turnaround time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 27 ms (dihitung dari awal kedatangan P2 hingga selesai dieksekusi), untuk P3 sebesar 30 ms. Turnaround time rata-rata untuk ketiga proses tersebut adalah (24+27+30)/3 = 27 ms.

– SJF (Shortets Job First)

Penjadwalan ini mengasumsikan waktu berjalannya proses sampai selesai telah diketahui sebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

*Burst time : asumsi berapa lama sebuah proses membutuhkan CPU diantara proses menunggunya I/O.

~ Kelebihan : Karena SJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untuk proses interaktif

~ Kekurangan : Masalah yang muncul adalah tidak mengetahui ukuran job saat job masuk. Untuk mengetahui ukuran job adalah dengan membuat estimasi berdasarkan kelakukan sebelumnya. Prosesnya tidak dating bersamaan, sehingga penetapannya harus dinamis.

Contoh: Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time 4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4 dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF.

Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms.

Average waiting time rata-rata untuk ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms.

– HRN (Highest Ratio Next)

Merupakan strategi penjadwalan dengan prioritas proses tidak hanya berdasarkan fungsi waktu layanan tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemproses, proses berjalan sampai selesai.

Penjadwalan HRN merupakan:

• Penjadwalan non-preemptive
• Penjadwalan berprioritas dinamis

Penjadwalan ini juga untuk mengkoreksi kelemahan SJF. HRN adalah strategi penjadwalan nonpreemptive dengan prioritas proses tidak hanya merupakan fungsi dari waktu layanan tapi juga jumlah waktu tunggu proses.

Prioritas dinamis HRN dihitung berdasarkan rumus:Prioritas = (Waktu tunggu + waktu layanan) / waktu layanan. Karena waktu layanan muncul sebagai pembagi maka proses yang lebih pendek mempunyai prioritas yang lebih baik. Karena waktu tunggu sebagai pembilang maka proses yang telah menunggu lebih lama juga mempunya kesempatan lebih bagus untuk memperoleh layanan pemrosesan. Disebut HRN (High Response Next) karena (waktu tanggap adalah waktu tunggu + waktu layanan). Ketentuan HRN berarti agar memperoleh waktu tanggap tertinggi yang harus dilayani.

– MFQ ( Multiple Feedback Queues )

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 M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

Algoritma ini didefinisikan melalui beberapa parameter, antara lain:

1. Jumlah antrian.
2. Algoritma penjadwalan tiap antrian.
3. Kapan menaikkan proses ke antrian yang lebih tinggi.
4. Kapan menurunkan proses ke antrian yang lebih rendah.
5. Antrian mana yang akan dimasuki proses yang membutuhkan.

~ Kelebihan : Dengan pendefinisian seperti tadi membuat algoritma ini sering dipakai, karena algoritma ini mudah dikonfigurasi ulang supaya cocok dengan sistem.

~ Kekurangan :  Untuk mengatahui mana penjadwal terbaik, kita harus mengetahui nilai parameter tersebut.

Contoh : Terdapat tiga antrian; Q1=10 ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam 40 ms tidak selesai, maka dipindahkan lagi ke Q3. Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.

2. Preemptive

Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi.

Penjadwalan Preemptive memungkinkan sistem untuk lebih bisa menjamin bahwa setiap proses mendapat sebuah slice waktu operasi. Dan juga membuat sistem lebih cepat merespon terhadap event dari luar (contohnya seperti ada data yang masuk) yang membutuhkan reaksi cepat dari satu atau beberapa proses.

Membuat penjadwalan yang Preemptive mempunyai keuntungan yaitu sistem lebih responsif daripada sistem yang memakai penjadwalan NonPreemptive.

Penjadwalan Preemptive melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya. Preemptive, menggunakan konsep:

– RR ( Round Robin )

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.

Penjadwalan Round Robin merupakan

• Penjadwalan Preemptive, namun proses tidak di-preempt secara langsung oleh proses lain, namun oleh penjadwal berdasarkan lama waktu berjalannya suatu proses. Maka penjadwalan ini disebut preempt-by-time
• Penjadwalan tanpa prioritasAlgoritma 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.

Contoh:

Berikut adalah contoh kasus seperti pada FCFS namun diselesaikan dengan metode Round-Robin dengan quantum = 1

Process	A	B	C	D	E	Mean
Finsih Time	4	18	17	20	15
Arival Time	0	2	4	6	8
TAT	4	16	13	14	7	10.80
Service Time	3	6	4	5	2
NTAT	1.33	2.67	3.25	2.80	3.50	2.71

– SRF (Shortest Remaining First)

Pada algoritma ini, proses dengan waktu pemrosesan terendah yang akan dijalankan terlebih dahulu, walau pun proses tersebut baru tiba di antrean proses. Selain itu, jika da proses yang sedang berjalan, dapat diambil alih oleh proses yang memiliki waktu pemrosesan lebih sedikit.

Proses ini merupakan Penjadwalan berprioritas.dinamis. Yaitu untuk timesharing melengkapi SJF Pada SRF, proses dengan sisa waktu jalan diestimasi terendah dijalankan,termasuk proses-proses yang baru tiba.

Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai. Pada SRF, proses yang sedang berjalan (running) dapat diambil alih prosesbaru dengan sisa waktu jalan yang diestimasi lebih rendah

Kelemahan:
SRF mempunyai overhead yang lebih besar dibandingkan SJF. SRF memerlukan penyimpanan waktu layanan yang telah dihabiskan proses dan kadang-kadang harus menangani peralihan.
~ Tibanya proses-proses kecil akan segera dijalankan.
~ Proses-proses lebih lama berarti dengan lama dan variasi waktu tunggu lebih lama dibandingkan pada SJF.

Secara teoritis SRF memberi waktu tunggu minimum tapi karena adanya overhead peralihan maka pada situasi tertentu SJF bisa memberi kinerja yang lebih baik dibanding SRF

Contoh:

Contoh: Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time 4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4 dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF. Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms.

– PS (Priority Schedulling)

Priority scheduling juga dapat dijalankan secara preemptive maupun non-preemptive.

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 depan queue.

Contoh: Setiap 10 menit, prioritas dari masing-masing proses yang menunggu dalam queue dinaikkan satu tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21 jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang tertinggi. (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi.

– GS (Guaranteed Schedulling)

Penjadwalan ini berupaya memberi tiap pemakai daya pemroses yang sama. untuk membuat dan menyesuaikan performance adalah jika ada terdapat N pemakai, tiap pemakai mendapat 1/N dari daya pemroses CPU.Untuk mewujudkannya  Sistem merekam banyak waktu pemroses yang telah digunakan proses sejak login.dan juga berapa lama pemakai sedang login.

Kemudian jumlah waktu CPU, yaitu waktu mulai login dibagi dengan n,sehingga lebih mudah menghitung rasio waktu CPU. Karena jumlah waktu pemroses tiap pemakai dapat diketahui, maka dapat dihitung rasio antara waktu pemroses yang sesungguhnya harus diperoleh, yaitu 1/N waktu pemroses seluruhnya dan waktu pemroses yang telah diperuntukkan proses itu

Klarifikasi lain berdasarkan dapat/tidaknya suatu proses diambil secara paksa.

1. Algoritma Penjadwalan tanpa berprioritas

Semua proses dianggap penting dan diberi sejumlah waktu pemroses yang disebut kwanta (quantum) atau time-slice tempat proses itu berkalan. Proses berjalannya selama 1 kwanta, kemudian penjadwal akan mengalihkan kepada proses berikutnya, juga untuk berjalan satu kwanta, begitu seterusnya sampai kembali pada proses pertama dan berulang.

Contoh algoritma penjadwalan tanpa berprioritas adalah :
a. Round Robin (RR)
b. FIFO (First in fisrt out)

2. Algoritma penjadwalan berprioritas

Gagasan penjadwalan adalah masing-masing proses diberi prioritas dan proses berprioritas tertinggi menjadi Running (yaitu mendapat jatah waktu pemroses). Prioritas dapat diberikan secara:

• Prioritas statis (static priorities), prioritas tak berubah.

– Keunggulan : Mudah diimplementasikan dan mempunyai overhead relatif
kecil
– Kelemahan : Penjadwalan prioritas statis tidak tanggap perubahan
lingkungan yang mungkin menghendaki penyesuaian prioritas

• Prioritas dinamis (dynamic priorities), mekanisme menanggapi perubahan lingkungan sistem saat beroperasi di lingkungan nyata. Prioritas awal yang diberikan ke proses mungkin hanya berumur pendek. Dalam hal ini sistem dapat menyesuaikan nilai prioritasnya ke nilai yang lebih tepat sesuai lingkungan.

– Keunggulan : waktu tanggap sistem yang bagus
– Kelemahan : implementsi mekanisme prioritas dinamis lebih kompleks dan mempunyai overhead yang lebih besar dibanding mekanisme prioritas statik.