ALGORITMA PENJADWALAN CPU
08.29 | 
Diposting oleh
Unknown
Penjadwalan CPU menyangkut penentuan
proses-proses yang ada dalam ready queue yang akan dialokasikan pada CPU.
Terdapat beberapa algoritma penjadwalan CPU seperti dijelaskan di
bawah ini.
First-Come First-Served Scheduling (FCFS)
Proses yang pertama kali meminta jatah
waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Pada skema ini,
proses yang meminta CPU pertama kali akan dialokasikan ke CPU pertama kali.
Misalnya terdapat tiga proses yang dapat
dengan urutan P1, P2, dan P3 dengan waktu
CPU-burst alam milidetik yang diberikan sebagai berikut :
Process Burst Time
P1 24
P2 3
P3 3
Gant Chart dengan penjadwalan FCFS
adalah sebagai berikut :
Waktu tunggu untuk P1 adalah 0, P2 adalah 24 dan P3 adalah 27
sehingga rata-rata waktu tunggu adalah (0 + 24 + 27)/3 = 17 milidetik.
Sedangkan apabila proses datang dengan urutan P2, P3, dan P1, hasil
penjadwalan CPU dapat dilihat pada gant chart berikut :
Waktu tunggu untuk P1 adalah 0, P2 adalah 24 dan P3 adalah 27
sehingga rata-rata waktu tunggu adalah (0 + 24 + 27)/3 = 17 milidetik.
Sedangkan apabila proses datang dengan urutan P2, P3, dan P1, hasil
penjadwalan CPU dapat dilihat pada gant chart berikut :
Waktu tunggu sekarang untuk P1 adalah 6, P2 adalah 0 dan P3 adalah 3
sehingga rata-rata waktu tunggu adalah (6 + 0 + 3)/3 = 3 milidetik. Rata-rata
waktu tunggu kasus ini jauh lebih baik dibandingkan dengan kasus sebelumnya.
Pada penjadwalan CPU dimungkinkan terjadi Convoy effect apabila proses
yang pendek berada pada proses yang panjang.
Algoritma FCFS termasuk non-preemptive.
karena, sekali CPU dialokasikan pada suatu proses, maka proses tersebut tetap
akan memakai CPU sampai proses tersebut melepaskannya, yaitu jika proses
tersebut berhenti atau meminta I/O.
Shortest Job First Scheduler (SJF)
Pada penjadwalan SJF, proses yang
memiliki CPU burst paling kecil dilayani terlebih dahulu. Terdapat dua skema :
1. Non preemptive, bila CPU diberikan
pada proses, maka tidak bisa ditunda sampai CPU burst selesai.
2. Preemptive, jika proses baru datang
dengan panjang CPU burst lebih pendek dari sisa waktu proses yang saat itu
sedang dieksekusi, proses ini ditunda dan
diganti dengan proses baru. Skema ini
disebut dengan Shortest-Remaining-Time-First (SRTF).
SJF adalah algoritma penjadwalan yang
optimal dengan rata-rata waktu tunggu yang minimal. Misalnya terdapat empat
proses dengan panjang CPU burst dalam
milidetik.
Process Arrival
Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Penjadwalan proses dengan algoritma SJF
(non-preemptive) dapat dilihat pada gantchart berikut :
Waktu tunggu untuk P1 adalah 0, P2 adalah 26, P3 adalah 3 dan P4 adalah 7
sehingga rata-rata waktu tunggu adalah (0 + 6 + 3 + 7)/4 = 4 milidetik.
Sedangkan Penjadwalan proses dengan algoritma RTF (preemptive) dapat dilihat
pada gant chart berikut :
Waktu tunggu untuk P1 adalah 9, P2 adalah 1, P3 adalah 0 dan P4 adalah 4
sehingga
rata-rata waktu tunggu adalah (9 + 1 + 0
+ 4)/4 = 3 milidetik.
Meskipun algoritma ini optimal, namun
pada kenyataannya sulit untuk diimplementasikan karena sulit untuk mengetahui
panjang CPU burst berikutnya. Namun nilai ini dapat diprediksi. CPU
burst berikutnya biasanya diprediksi sebagai suatu rata-rata eksponensial
yang ditentukan dari CPU burst sebelumnya atau “Exponential Average”.
dengan:
τ n+1 = panjang CPU
burst yang diperkirakan
τ 0 = panjang CPU
burst sebelumnya
τ n = panjang CPU
burst yang ke-n (yang sedang berlangsung)
α = ukuran
pembanding antara τ n+1 dengan τ n (0 sampai 1)
Grafik hasil prediksi CPU burst dapat
dilihat pada Gambar .
Gambar ini: Prediksi panjang CPU burst berikutnya
CPU burst (τ n ) = 6 4 6 4 13
13 13 . . .
τ n = 10 8 6 6 5 9
11 12 . . .
Pada awalnya τ 0 = 6 dan τ n = 10, sehingga :
τ 2 = 0,5 * 6 + (1 -
0,5) * 10 = 8
Nilai yang dapat digunakan untuk mencari
τ 3
τ 3 = 0,5 * 4 + (1 -
0,5) * 8 = 6
Priority Scheduling
Algoritma SJF adalah suatu kasus khusus
dari penjadwalan berprioritas. Tiap-tiap proses dilengkapi dengan nomor
prioritas (integer). CPU dialokasikan untuk proses yang memiliki prioritas
paling tinggi (nilai integer terkecil biasanya merupakan prioritas terbesar).
Jika beberapa proses memiliki prioritas yang sama, maka akan digunakan
algoritma FCFS. Penjadwalan berprioritas terdiri dari dua skema yaitu non
preemptive dan preemptive. Jika ada proses P1 yang datang pada
saat P0
sedang
berjalan, maka akan dilihat prioritas P1. Seandainya
prioritas P1
lebih
besar dibanding dengan prioritas P0, maka pada non-preemptive,
algoritma tetap akan menyelesaikan P0 sampai habis
CPU burst-nya, dan meletakkan
P1
pada
posisi head queue. Sedangkan pada preemptive, P0 akan dihentikan
dulu, dan CPU ganti dialokasikan untuk P1. Misalnya
terdapat lima proses P1, P2, P3, P4 dan P5 yang datang
secara
berurutan dengan CPU burst dalam
milidetik.
Process Burst
Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
Penjadwalan proses dengan algoritma
priority dapat dilihat pada gant chart berikut :
Waktu tunggu untuk P1 adalah 6, P2 adalah 0, P3 adalah 16, P4 adalah 18 dan P5 adalah1 sehingga
rata-rata waktu tunggu adalah (6 + 0 +16 + 18 + 1)/5 = 8.2 milidetik.
Round-Robin Scheduling
Konsep dasar dari algoritma ini adalah
dengan menggunakan time-sharing. Pada dasarnya algoritma ini sama dengan FCFS,
hanya saja bersifat preemptive. Setiap proses mendapatkan waktu CPU yang
disebut dengan waktu quantum (quantum time) untuk membatasi waktu
proses, biasanya 1-100 milidetik. Setelah waktu habis, proses ditunda dan
ditambahkan pada ready queue.
Jika suatu proses memiliki CPU burst
lebih kecil dibandingkan dengan waktu quantum, maka proses tersebut akan
melepaskan CPU jika telah selesai bekerja, sehingga CPU dapat segera digunakan
oleh proses selanjutnya. Sebaliknya, jika suatu proses memiliki CPU burst yang
lebih besar dibandingkan dengan waktu quantum, maka proses tersebut akan
dihentikan sementara jika sudah mencapai waktu quantum, dan selanjutnya
mengantri kembali pada posisi ekor dari ready queue, CPU kemudian
menjalankan proses berikutnya.
Jika terdapat n proses pada ready
queue dan waktu quantum q, maka setiap proses mendapatkan 1/n dari
waktu CPU paling banyak q unit waktu pada sekali penjadwalan CPU. Tidak
ada proses yang menunggu lebih dari (n-1)q unit waktu.
Performansi algoritma round robin dapat dijelaskan sebagai berikut, jika q
besar, maka yang digunakan adalah algoritma FIFO, tetapi jika q kecil maka
sering terjadi context switch.
Misalkan ada 3 proses: P1, P2, dan P3 yang meminta
pelayanan CPU dengan quantum-time sebesar 4 milidetik.
Process Burst
Time
P1 24
P2 3
P3 3
Penjadwalan proses dengan algoritma
round robin dapat dilihat pada gant chart berikut :
Waktu tunggu untuk P1 adalah 6, P2 adalah 4, dan P3 adalah 7
sehingga rata-rata waktu tunggu adalah (6 + 4 + 7)/3 = 5.66 milidetik.
Algoritma Round-Robin ini di satu sisi memiliki keuntungan, yaitu adanya
keseragaman waktu. Namun di sisi lain, algoritma ini akan terlalu sering
melakukan switching seperti yang terlihat pada
Gambar . Semakin besar quantum-timenya maka switching yang terjadi akan semakin
sedikit.
Gambar ini: Menunjukkan waktu kuantum yang lebih
kecil meningkatkan
context switch
Waktu turnaround juga tergantung ukuran
waktu quantum. Seperti pada Gambar , rata-rata waktu turnaround tidak meningkat
bila waktu quantum dinaikkan. Secara umum, rata-rata waktu turnaround dapat
ditingkatkan jika banyak proses menyelesaikan CPU burst berikutnya sebagai satu
waktu quantum. Sebagai contoh, terdapat tiga proses masing-masing 10 unit waktu
dan waktu quantum 1 unit waktu, rata-rata waktu turnaround adalah 29. Jika
waktu quantum 10, sebaliknya, rata-rata waktu turn around turun menjadi 20.
Gambar ini: Menunjukkan waktu turnaround berbeda
pada waktu quantum
yang berbeda
Langganan:
Posting Komentar (Atom)
0 komentar:
Posting Komentar