Penjadwalan CPU
Penjadwalan CPU adalah pemilihan proses dari antrian ready untuk dapat dieksekusi. Penjadwalan CPU merupakan konsep dari multiprogramming, CPU digunakan secara bergantian untuk proses yang berbeda. proses terdiri dari dua siklus yaitu Burst I/O dan Burst CPU yang dilakukan bergantian hingga proses selesai.
Penjadwalan CPU dijalankan ketika proses:
- running ke waiting time
- running ke ready state
- waiting ke ready state
- terminates
Proses
1 dan 4 adalah proses Non Preemptive, proses tersebut tidak bisa di- interrupt.
Proses 2 dan 3 adalah proses Preemptive, proses boleh di interrupt. sistem
operasi harus di seleksi proses-proses yang ada di memori utama (ready queue)
untuk di eksekusi dan mengalokasikan CPU untuk salah satu dari proses tersebut.
Seleksi tersebut disebut dengan shortterm scheduler (CPU scheduler).
Komponen yang lain dalam penjadwalan CPU adalah dispatcher, Dispatcher
adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penseleksian
proses yang dilakukan selama short-term scheduling . Waktu yang diperlukan oleh
dispatcher untuk menghentikan suatu proses dan memulai proses yang lain disebut
dengan dispatch latency. dalam suatu proses Burst CPU jauh lebih besar dari pada
Burst I/O maka disebut CPU Bound. Demikian juga sebaliknya disebut dengn I/O
Bound.
1. Penjadwalan
Preemptive
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 I/O.
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 disebut CPU 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 di hindari.
penjadwalan Preemptive
melibatkan mekanisme interupsi yang mensela proses yang sedang berjalan dan
memaksa sistem untuk menentukan proses mana yang akan di eksekusi selanjutnya. 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.
2. 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- interrupt, Penjadwalan
Non Preemptive terjadi ketika proses hanya :
- Berjalan dari running state sampai waiting
state.
-
Dihentikan.
CPU menjaga
proses sampai proses itu pindah ke waiting state ataupun di hentikan (proses
tidak di ganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh.
adalah metode yang dapat di gunakan untuk platforms hardware tertentu, karena
tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk
meng interupt pada metode penjadwalan Preemptive).
Algoritma
Penjadwalan CPU
Penjadwalan
CPU terkait dengan bagaimana proses dikelola . Banyak algoritma yang
digunakan untuk penjadwalan proses. Beberapa algoritma yang digunakan
antara lain :
1. First-Come First- Serve (FCFS)
Merupakan algoritma yang paling sederhana dalam penjadwalan proses. Proses yang melakukan request terhadap CPU akan di proses oleh CPU. Implementasinya dengan menggunakan algoritma First In First Out – FIFO. FCFS bersifat non-preemptive yaitu proses yang dikerjakan oleh CPU tidak dapat diinterupsi oleh proses yang lainnya, Sebagai contoh :
Proses
|
Burst
|
P1
|
10
|
P2
|
1
|
P3
|
2
|
P4
|
1
|
P5
|
5
|
Proses di asumsikan datang bersamaan dan masuk
dalam antrian penggunaan CPU. Proses akan di kerjakan berdasarkan nomor urutan
proses, sedangkan yang lainnya menunggu sampai proses diatasnya selesai
dikerjakan. Dari Gant Chart dapat diperoleh waktu tunggu proses dari CPU yang
dapat diambil waktu rata-ratanya.
Waiting Time P1
= 0
Waiting Time P2 = 10
Waiting Time P3 = 11
Waiting Time P4 = 13
Waiting Time P5
= 14.
Avarage Waiting Time (AWT) = (WT P1 + WT P2 + WT P3 + WT P4 + WT P5)/5
Avarage Waiting Time (AWT) = (0 + 10 + 11 + 13 + 14)/5 = 9.6 ms
FCFS dapat juga bekerja dengan adanya prioritas terhadap proses, prioritas dengan nilai terkecil akan diberi status sebagai prioritas tinggi dan akan dikerjakan terlebih dahulu.
Avarage Waiting Time (AWT) = (WT P1 + WT P2 + WT P3 + WT P4 + WT P5)/5
Avarage Waiting Time (AWT) = (0 + 10 + 11 + 13 + 14)/5 = 9.6 ms
FCFS dapat juga bekerja dengan adanya prioritas terhadap proses, prioritas dengan nilai terkecil akan diberi status sebagai prioritas tinggi dan akan dikerjakan terlebih dahulu.
Proses
|
Burst
|
Prioritas
|
P1
|
10
|
3
|
P2
|
1
|
1
|
P3
|
2
|
4
|
P4
|
1
|
5
|
P5
|
5
|
2
|
Gant Chart :
Avarage Waiting Time (AWT) = (0 + 1 + 6 +
16 + 18)/4 = 8.2 ms
FCFS adalah adanya antrian dari proses yang menjadi panjang karena waiting time yang rata-rata panjang. Proses-proses yang telah berada dalam posisi ready akan tetapi CPU belum dapat memprosesnya. Hal ini disebut dengan starvation.
FCFS adalah adanya antrian dari proses yang menjadi panjang karena waiting time yang rata-rata panjang. Proses-proses yang telah berada dalam posisi ready akan tetapi CPU belum dapat memprosesnya. Hal ini disebut dengan starvation.
2. Shortest Job First (SJF)
Pendekatan SJF berbeda dengan FCFS, algoritma SJF tergantung dengan panjang proses yang ada pada queue. Ketika CPU akan melakukan proses, CPU akan memilik proses dengan CPU burst paling kecil. SJF dapat bekerja dengan mode preemptive maupun non-preemptive.
- Non-preemptive
Proses
|
Burst
|
P1
|
6
|
P2
|
8
|
P3
|
7
|
P4
|
3
|
Gant chat :
Waiting Time P1
= 3
Waiting Time P2 = 16
Waiting Time P3 = 9
Waiting Time P4 = 0
Avarage Waiting Time = (3 + 16 + 9 + 0)/4 = 7 ms
Waiting Time P2 = 16
Waiting Time P3 = 9
Waiting Time P4 = 0
Avarage Waiting Time = (3 + 16 + 9 + 0)/4 = 7 ms
2 . Preemptive
SJF dengan waktu kedatangan (arrival time) berbeda.
Proses
|
Arrival
|
Burst
|
P1
|
0
|
8
|
P2
|
1
|
4
|
P3
|
2
|
9
|
P4
|
3
|
5
|
Proses akan di-preemptive jika ada proses
masuk, penjadwalan di lakukan ulang dengan membandingkan proses yang masuk dengan
proses yang sedang di jalankan.
Sebagai contoh :
tabel ketika P1 dijalankan dengna membutuhkan 8
ms, akan tetapi datang burst dari proses P2 dengan burst time 4 ms pada deti
ke-1. Proses akan berhenti pada detik 1 kemudian membandingkan proses P1 dengan
P2. Karena P2 < P1 maka proses P1 akan di kembalikan ke ready queue dengan
P1 = 7 dan memproses P2. Demikian seterusnya.
Gant chart :
Waiting Time P1 = 0 + (10-1) = 9
Waiting Time P2 = 1-1 = 0
Waiting Time P3 = 17-2 = 15
Waiting Time P4 = 5-3 = 2
Average Waiting Time = (9 + 0 + 15 + 2 )/4 = 6.5 ms
3. Round Robin (RR)
Round Robin hampir mirip dengan FCFS akan tetapi terdapat proses
perpindahan antar proses dimana satu proses melakukan interupsi terhadap proses
yang lainnya atau disebut juga dengan preemptive. Proses preemptive dengan
menggunakan time quantum atau time slice.
Sebagai contoh :
Sebagai contoh :
Proses
|
Burst
|
P1
|
24
|
P2
|
3
|
P3
|
3
|
Dengan time slice sebesar 4 ms, penjadwalan
yang terjadi adalah sebagai berikut:
P1 mendapatkan kesempatan pada 4 ms (time slice) pertama, karena P1 > time slice maka P1 hanya akan diproses selama time slice, sisa P1 sebesar P1 – time slice akan di preemptive-kan. Selanjutnya penjadwalan akan beralih ke P2, karena P2 < time slice maka P2 diproses hingga selesai, setelah itu penjadwalan beralih ke P3 dan seterusnya.
P1 mendapatkan kesempatan pada 4 ms (time slice) pertama, karena P1 > time slice maka P1 hanya akan diproses selama time slice, sisa P1 sebesar P1 – time slice akan di preemptive-kan. Selanjutnya penjadwalan akan beralih ke P2, karena P2 < time slice maka P2 diproses hingga selesai, setelah itu penjadwalan beralih ke P3 dan seterusnya.
Waiting Time P1
= 0 + (10 – 4) = 6
Waiting Time P2 = 4
Waiting Time P3 = 7
Average Waiting Time = (6 + 4 + 7 )/3 = 5.66 ms
Waiting Time P2 = 4
Waiting Time P3 = 7
Average Waiting Time = (6 + 4 + 7 )/3 = 5.66 ms
Pada algoritma RR, tidak ada proses yang dikerjakan dalam satu waktu lebih dari time slice yang disediakan. Jika terdapat n proses pada queue dengan time slice sebesar q, maka setiap proses akan mendapatkan waktu 1/n dengan masing-masing proses sebesar q .Setiap proses akan menunggu setidaknya sebanyak (n-1)x q untuk proses selanjutnya. Sebagai contoh terdapat 5 proses dengan time slice sebesar 20 ms maka masing-masing proses akan mendapatkan waktu sebanyak 20 ms setiap 100 ms.
Performance
dari RR tergantung pada ukuran time slice. Jika time slice terlalu besar maka
RR akan sama atau mendekati performance FCFS. Akan tetapi jika time slice kecil
maka muncul problem context switch yang terlalu banyak, yaitu proses
perpindahan dari satu proses ke proses lain yang akan menimbulkan permasalahan.
Hal ini terjadi karena perbedaan kecepatan processor dan memori, dengan
terjadinya perpindahan yang terlalu sering proses pembacaan CPU ke memori dan
sebaliknya akan membebani sistem.
Tidak ada komentar:
Posting Komentar