Penjadwalan CPU adalah permasalahan menentukan proses mana pada ready queue
yang dialokasikan ke CPU. Terdapat beberapa algoritma penjadwalan CPU,
diantaranya :
- Algoritma Penjadwalan First
Come, First Served (FIFO).
- Algoritma Penjadwalan Shortest
Job First.
- Algoritma Penjadwalan Priority
Schedulling (jadwal prioritas).
- Algoritma Penjadwalan Round
Robin.
- Algoritma Penjadwalan First Come, First Served (FCFS)
Proses
yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani
terlebih dahulu. Dan rata-rata waktu tunggu (Average waiting time) cukup
tinggi.
Algoritma
penjadwalan FCFS merupakan salah satu strategi penjadwalan non-Preemptive
karena sekali CPU dialokasikan pada suatu proses, maka proses tersebut akan
tetap memakai CPU sampai proses tersebut melepaskannhya, yaitu jika proses
berhenti atau meminta I/O
Kelemahan
dari algoritma ini:
1.
Waiting time rata-ratanya cukup lama.
2.
Terjadinya convoy
effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses
besar yang sedang dieksekusi oleh CPU. Algoritma ini juga menerapkan konsep
non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat
di-interrupt oleh proses yang lain.
- Algoritma Shortest Job First Scheduler
Algoritma
ini digunakan ketika CPU bebas proses yang mempunyai waktu terpendek untuk
menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai
waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah
tersebut.
Prinsip
algoritma penjadwalan ini adalah, proses yang memiliki CPU burst paling kecil
dilayani terlebih dahulu. Oleh karena itu, algoritma ini optimal jika
digunakan, tetapi sulit untuk diimplementasikan karena sulit mengetahui CPU
burst selanjutnya.
Ada
dua skema dalam SJFS ini yaitu:
- Non premptive— ketika CPU
memberikan kepada proses itu tidak bisa ditunda hingga selesai.
- premptive— bila sebuah proses datang
dengan waktu proses lebih rendah dibandingkan dengan waktu proses yang
sedang dieksekusi oleh CPU maka proses yang waktunya lebih rendah
mendapatkan prioritas
- Algoritma Penjadwalan Priority
Schedulling (jadwal prioritas)
Penjadualan
SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadual
Prioritas. Prioritas dapat diasosiasikan masing-masing proses dan CPU
dialokasikan untuk proses dengan prioritas tertinggi. Untuk proritas yang sama
dilakukan dengan FCFS.
Ada
pun algoritma penjadual prioritas adalah sebagai berikut:
• Setiap
proses akan mempunyai prioritas (bilangan integer). Beberapa sistem menggunakan
integer dengan urutan kecil untuk proses dengan prioritas rendah, dan sistem
lain juga bisa menggunakan integer urutan kecil untuk proses dengan prioritas
tinggi. Tetapi dalam teks ini diasumsikan bahwa integer kecil merupakan
prioritas tertinggi.
• CPU
diberikan ke proses dengan prioritas tertinggi (integer kecil adalah prioritas
tertinggi).
• Dalam
algoritma ini ada dua skema yaitu:
1. Preemptive:
proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan
CPU.
2.
Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain
time-slice habis.
• SJF
adalah contoh penjadual prioritas dimana prioritas ditentukan oleh waktu
pemakaian CPU berikutnya. Permasalahan yang muncul dalam penjadualan prioritas
adalah indefinite blocking atau starvation.
• Kadang-kadang
untuk kasus dengan prioritas rendah mungkin tidak pernah dieksekusi.
• Prioritas
akan naik jika proses makin lama menunggu waktu jatah CPU.
- Algoritma Penjadwalan Round Robin.
Algoritma
Round Robin (RR) dirancang untuk sistem time sharing. Algoritma ini mirip
dengan penjadual FCFS, namun preemption ditambahkan untuk switch antara proses.
Antrian ready diperlakukan atau dianggap sebagai antrian sirkular. CPU
mengelilingi antrian ready dan mengalokasikan masing-masing proses untuk
interval waktu tertentu sampai satu time slice/ quantum.
Berikut
algoritma untuk penjadual Round Robin:
• Setiap
proses mendapat jatah waktu CPU (time slice/ quantum) tertentu Time
slice/quantum umumnya antara 10 – 100 milidetik.
- Setelah time slice/ quantum
maka proses akan di-preempt dan dipindahkan ke antrian ready.
- Proses ini adil dan sangat
sederhana.
• Jika
terdapat n proses di “antrian ready” dan waktu quantum q (milidetik), maka:
- Maka setiap proses akan
mendapatkan 1/n dari waktu CPU.
- Proses tidak akan menunggu
lebih lama dari: (n-1)q time units.
• Kinerja
dari algoritma ini tergantung dari ukuran time quantum.
- Time Quantum dengan ukuran yang
besar maka akan sama dengan FCFS.
- Time Quantum dengan ukuran yang
kecil maka time quantum harus diubah ukurannya lebih besar dengan respek
pada alih konteks sebaliknya akan memerlukan ongkos yang besar
Video Simulasi Algoritma
Penjadwalan
http://www.youtube.com/watch?v=e3WCqgkpk4w
