Pengertian algoritma penjadwalan
Penjadwalan berkaitan dengan permasalahan memutuskan proses
mana yang akan dilaksanakan dalam suatu sistem. Proses yang belum mendapat
jatah alokasi dari CPU akan mengantri di ready queue. Algoritma penjadwalan
berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan
dieksekusi oleh CPU
Algoritma penjadwalan,baik berupa operasiannya atau contoh
pengoperasiannya
Ada beberapa algoritma dalam penjadwalan proses, algoritma-algoritma
tersebut adalah:
Round Robin
Algorima ini merupakan proses antrian, yang mana proses akan
mendapatkan jatah waktu sebesar time quantum. Jika waktu quantumnya selesai
maka prosesnya pun selesai. Proses ini merupakan proses yang adil karena tidak ada
proses yang didahulukan, semua proses mendapatkan jatah waktu yang sama yaitu
1/n.
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 yang mana yang dating dahulu
akan dilayani terlebih dahulu.Time quantum yang ideal adalah jika 80% dari
total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.
Penggunaan Waktu Quantum
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:
Dari gambar tersebut terlihat bahwa akan terjadi
pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk
menganggap kelompok-kelompok tersbut sebagai sebuah antrian-antrian kecil yang
merupakan bagian dari antrian keseluruhan proses, yang sering disebut dengan algoritma
multilevel queue.
Dalam hal ini, dapat dilihat bahwa seolah-olah algoritma
dengan prioritas yang dasar adalah algoritma multilevel queue dimana setiap queue
akan berjalan dengan algoritma FCFS yang memiliki banyak kelemahan. Oleh karena
itu, dalam prakteknya, algoritma multilevel queue memungkinkan adanya penerapan
algoritma internal dalam masing-masing sub-antriannya yang bisa memiliki
algoritma internal yang berbeda untuk meningkatkan kinerjanya.
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.
Multiple Feedback Queue (MFQ)
Algoritma ini merupakan algoritma yang mengizinkan proses
untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses
itu akan dipindahkan ke antrian yang lebih rendah. Hal ini akan sangat
menguntungkan karena akan menggunakan waktu yang sedikit dalam pengerjaan
proses-proses tersebut. Demikian pula dengan proses yang menunggu lama maka
prose ini akan dinaikkan ke tingkat yang lebih tinggi. Dengan begitu CPU akan
bekerja dengan penuh dan M/K dapat terus sibuk. Semakin rendah tingkatnya,
panjang CPU burst proses juga semakin panjang.
Multilevel Feedback Queue
Algoritma ini didefinisikan melalui beberapa parameter,
antara lain:
Jumlah antrian.
Algoritma penjadwalan tiap antrian.
Kapan menaikkan proses ke antrian yang lebih tinggi.
Kapan menurunkan proses ke antrian yang lebih rendah.
Antrian mana yang akan dimasuki proses yang membutuhkan.
Dengan pendefinisian seperti tadi membuat algoritma ini
sering dipakai, karena algoritma ini mudah dikonfigurasi ulang supaya cocok
dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik, kita harus
mengetahui nilai parameter tersebut.
Multilevel feedback queue adalah salah satu algoritma yang
berdasar pada algoritma multilevel queue. Perbedaan mendasar yang membedakan multilevel
feedback queue dengan multilevel queue biasa adalah terletak pada adanya
kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah
dengan prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh
berikut.
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.
Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan
berjalan dengan algoritma FCFS.
Disini terlihat bahwa ada kemungkinan terjadinya perpindahan
proses antar queue, dalam hal ini ditentukan oleh time quantum, namun dalam
prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dengan
mendefinisikan terlebih dahulu parameter-parameternya, yaitu:
Jumlah antrian.
Algoritma internal tiap queue.
Aturan sebuah proses naik ke antrian yang lebih tinggi.
Aturan sebuah proses turun ke antrian yang lebih rendah.
Antrian yang akan dimasuki tiap proses yang baru datang.
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.
Shortest Remaining First (SRF)
Pada algoritma ini setiap proses yang ada di ready queue
akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting
time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time
rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini
adalah algoritma yang optimal.
Contoh Shortest Job First
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.
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.
Ada beberapa kekurangan dari algoritma ini 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.
Algoritma ini dapat dibagi menjadi dua bagian yaitu :
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.
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.
Higest Ratio Next (HRN)
Higest Ratio Next (HRN) Merupakan penjadwalan untuk
mengoreksi kelemahan SJF yang berprioritas dinamis. HRN Adalah strategi
penjadwalan dengan prioritas proses tidak hanya merupakan fungsi waktu
layanan,tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah
pemroses, maka proses berjalan sampai selesai. Prioritas dinamis HRN dihitung
berdasarkan rumus berikut : Prioritas = (waktu tunggu + waktu layanan ) / waktu
layanan. Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek
berprioritas lebih baik, karena waktu tunggu sebagai pembilang, maka proses
yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus. Mengapa
algoritma ini disebut HRN karena waktu tunggu ditambah waktu layanan adalah
waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani.
Priority Schedulling (PS)
Priority Scheduling merupakan algoritma penjadwalan yang
mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses memiliki
prioritasnya masing-masing.
Prioritas suatu proses dapat ditentukan melalui beberapa
karakteristik antara lain:
1. Time limit.
2. Memory requirement.
3. Akses file.
4. Perbandingan antara burst
M/K dengan CPU burst.
5. Tingkat kepentingan
proses.
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.
Kelemahan pada priority scheduling adalah dapat terjadinya
indefinite blocking( starvation). Suatu proses dengan prioritas yang rendah
memiliki kemungkinan 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. 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).
Guaranteed Scheduling (GS)
Penjadwalan ini memberikan janji yang realistis (memberi
daya pemroses yang sama) untuk membuat dan menyesuaikan performance adalah jika
ada N pemakai, sehingga setiap proses (pemakai) akan mendapatkan 1/N dari daya
pemroses CPU. Untuk mewujudkannya, sistem harus selalu menyimpan informasi
tentang jumlah waktu CPU untuk semua 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. Rasio 0,5 berarti
sebuah proses hanya punya 0,5 dari apa yang waktu CPU miliki dan rasio 2,0
berarti sebuah proses hanya punya 2,0 dari apa yang waktu CPU miliki. Algoritma
akan menjalankan proses dengan rasio paling rendah hingga naik ketingkat lebih
tinggi diatas pesaing terdekatnya. Ide sederhana ini dapat diimplementasikan ke
sistem real-time dan memiliki penjadwalan berprioritas dinamis.
STRATEGI DASAR PENJADWALAN
Strategi penjadwalan proses secara umum dibedakan menjadi
dua kelompok besar, yaitu penjadwalan non-preemptive dan preemptive.
Non-preemptive (run-to-completion)
Pada strategi ini, begitu proses telah berjalan maka sistem
operasi maupun proses lain tidak dapat mengmabil alih eksekusi prosesor.
Pengalihan hanya dapat terjadi jika proses yang running sudah selesai, baik secara
normal maupun abnormal. Strategi ini membahayakan sistem dan proses lain, sebab
jika proses yang sedang berjalan mengalami kegagalan, crash ataupun looping tak
berhingga maka sistem operasi menjadi tidak berfungsi dan proses lain tidak
mendapatkan kesempatan untuk dieksekusi. Strategi penjadwalan non-preemptive
umumnya digunakan pada sistem batch atau sekuensial.
Preemptive
Pada strategi ini, sistem operasi dan proses lain dapat
mengambil alih eksekusi prosesor tanpa harus menunggu proses yang sedang
running menyelesaikan tugasnya. Penjadwalan preemptive merupakan fitur yang
penting, terutama pada sistem dimana proses-proses memerlukan tanggapan
prosesor secara cepat. Sebagai contoh adalah sistem real-time, dimana jika
terjadi interupsi dan tidak segera dilayani maka dapat berakibat fatal. Contoh
lain adalah sistem interaktif time-sharing, dimana pengguna sistem mengharapkan
tanggapan yang cepat dari sistem. Secara umum, sistem konkuren seperti sistem
operasi yang multitasking lebih menghendaki sistem penjadwalan preemptive.
Penjadwalan Preemptive
Berubah dari running ke waiting state.
Berubah dari running ke ready state.
Berubah dari waiting ke ready state.
Dihentikan.
Penjadwalan Preemptive mempunyai arti kemampuan
sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk
memberi ruang kepada proses yang prioritasnya lebih tinggi. Penjadwalan ini
bisa saja termasuk penjadwalan proses atau M/K. 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 Non Preemptive.
Dalam waktu-waktu tertentu, proses dapat dikelompokkan ke
dalam dua kategori: proses yang memiliki Burst M/K yang sangat lama
disebut I/O Bound, dan proses yang memiliki Burst CPU yang
sangat lama disebutCPU Bound. Terkadang juga suatu sistem mengalami kondisi
yang disebut busywait, yaitu saat dimana sistem menunggu request
input(seperti disk, keyboard, atau jaringan). Saat busywait tersebut,
proses tidak melakukan sesuatu yang produktif, tetapi tetap memakan resource dari
CPU. Dengan penjadwalan Preemptive, hal tersebut dapat dihindari.
Dengan kata lain, penjadwalan Preemptive melibatkan
mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem
untuk menentukan proses mana yang akan dieksekusi selanjutnya.
Penjadwalan nomor 1 dan 4 bersifat Non Preemptive sedangkan
lainnya Preemptive. Penjadwalan yang biasa digunakan sistem operasi dewasa
ini biasanya bersifat Preemptive. Bahkan beberapa penjadwalan sistem
operasi, contohnya Linux 2.6, mempunyai kemampuan Preemptive terhadap system
call-nya ( preemptible kernel). Windows 95, Windows XP, Linux, Unix,
AmigaOS, MacOS X, dan Windows NT adalah beberapa contoh sistem operasi
yang menerapkan penjadwalan Preemptive.
Lama waktu suatu proses diizinkan untuk dieksekusi dalam
penjadwalan Preemptive disebut time slice/quantum. Penjadwalan berjalan setiap
satu satuan time slice untuk memilih proses mana yang akan berjalan
selanjutnya. Bila time slice terlalu pendek maka penjadwal akan
memakan terlalu banyak waktu proses, tetapi bila time slice terlau
lama maka memungkinkan proses untuk tidak dapat merespon terhadap event dari
luar secepat yang diharapkan.
Penjadwalan Non Preemptive
Penjadwalan Non Preemptive ialah
salah satu jenis penjadwalan dimana sistem operasi tidak pernah melakukan context
switch dari proses yang sedang berjalan ke proses yang lain. Dengan kata
lain, proses yang sedang berjalan tidak bisa di- interupt.
Penjadwalan Non Preemptive terjadi ketika proses
hanya:
Berjalan dari running state sampai waiting
state.
Dihentikan.
Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting
state ataupun dihentikan (proses tidak diganggu). Metode ini digunakan
oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat
digunakan untuk platforms hardware tertentu, karena tidak
memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk
menginterupt pada metode penjadwalan Preemptive).
Dispatcher
Komponen penjadwalan proses lainnya adalah dispatcher.
Dispatcher adalah suatu rutin sistem operasi yang berfungsi untuk melakukan
pengalihan eksekusi dari proses yang running ke proses yang terseleksi oleh
short-term scheduler. Rutin ini memindahkan isi register prosesor, konteks
prosesor, ke PCB proses yang dihentikan, kemudian mengubah statusnya menjadi
ready, kemudian menginisiasi isi register prosesor menggunakan konteks prosesor
yang tersimpan dalam PCB proses terpilih. Durasi waktu yang diperlukan untuk
melakukan pengalihan (switching) disebut dengan dispatch latency.
Tidak ada komentar:
Posting Komentar