Unknown
Wednesday, March 7, 2012
Dalam
pemroses tunggal, hanya satu proses yang dapat dijalankan pada saat tertentu,
sedangkan yang lain harus menunggu CPU bebas dan dijadwal ulang.
Multiprogramming merupakan cara untuk menjalankan proses setiap waktu sehingga
memaksimalkan penggunaan CPU.
Penjadwalan
merupakan salah satu fungsi dasar dari sistem operasi. Hampir semua sumber daya
komputer dijadwalkan sebelum digunakan.
B.
CPU-I/O
Burst Cycle
Kesuksesan
penjadwaln CPU tergantung dari observasi proses-proses. Pengeksekusian proses
terdiri putaran ekseskusi CPU dan penungguan I/O. Eksekusi proses dimulai dari
CPU burst, yaitu diikuti oleh I/O burst kemudian diikuti CPU burst lainnya lalu
I/O burst lainnya dan begitu seterusnya.
Gambar
1 Urutan pergantian CPU Burst dengan I/O Burst
C.
Penjadwalan
CPU
Ketika
CPU mengalami waktu idle, sistem operasi harus memilih salah satu proses untuk
masuk kedalam antrian yang akan untuk dieksekusi. Pemilihan tersebut dilakukan
oleh penjadwal jangka pendek atau penjadwal CPU. [Bambang2002] Ada tiga tipe penjadwal yang
berada bersama pada sistem operasi kompleks, yaitu :
1.
Penjadwal
jangka pendek yang bertugas menjadwalkan alokasi pemroses di antara
proses-proses yang telah siap di memori utama.
2.
Penjadwal
jangka menengah akan menangani serta mengendalikan transisi dari
suspended-toready dari proses-proses swapping.
3.
Penjadwal
jangka panjang bekerja terhadap antrian batch dan memilih batch berikutnya yang
harus dieksekusi.
Gambar 2 Tipe-tipe penjadwalan
Penjadwalan memilih proses yang ada
di memori serta siap untuk dieksekusi, dan mengalokasikan CPU untuk
mengeksekusinya. Penjadwalan CPU mungkin akan dijalankan ketika proses dalam
keadaan:
1.
Berubah dari running ke waiting state.
2.
Berubah dari running ke ready state.
3.
Berubah
dari waiting ke ready.
4.
Terminates.
Penjadwalan
nomor 1 dan 4 bersifat non-preemptive atau cooperative sedangkan lainnya
preemptive. Dalam penjadwalan non-preemptive sekali CPU telah dialokasikan
untuk sebuah proses, maka tidak dapat di ganggu, penjadwalan model seperti ini
digunakan oleh Windows 3.x; Windows 95 telah menggunakan penjadwalan preemptive
yaitu saat suatu proses sedang dieksekusi, CPU dapat diambil alih oleh proses
lain sehingga proses di tunda dan dilanjutkan kembali hingga proses selesai.
D.
Kriteria
Penjadwalan
Setiap algoritma penjadwalan dapat berbeda
dengan nilai yang berbeda dan sistem komputer yang berbeda. Dalam penjadwalan CPU diperlukan
beberapa kriteria diantaranya adalah:
1.
CPU
Utilization. Kita menginginkan kerja CPU sesibuk mungkin. Konsepnya
pemanfaatan CPU mempunyai jangkauan dari 0 sampai 100 persen. Di sistem yang
sebenarnya mungkin hanya mempunyai jangakuan dari 40 (untuk pemanggilan ringan
sistem) sampai 90 persen (pemanggilan berat sistem).
2.
Throughput. Pengukuran
kinerja CPU adalah banyaknya proses yang diselesaikan per satuan waktu. Jika
kita mempunyai beberapa proses yang sama dan memiliki beberapa algoritma penjadwalan
yang berbeda, hasil kinerja bisa menjadi salah satu kriteria penilaian, dimana algoritma
yang menyelesaikan proses terbanyak mungkin yang terbaik.
3.
Turnaround
Time. Dari sudut pandang proses tertentu, kriteria yang penting adalah
berapa lama untuk mengeksekusi proses tersebut. Memang, lama pengeksekusian
sebuah proses sangat tergantung dari hardware yang dipakai, namun kontribusi
algoritma penjadwalan tetap ada dalam lama waktu yang dipakai untuk
menyelesaikan sebuah proses. Misal, kita memilki sistem komputer yang identik
dan proses-proses yang identik pula, namun kita memakai algoritma yang berbeda,
algoritma yang mampu menyelesaikan proses yang sama dengan waktu yang lebih singkat
mungkin lebih baik dari algoritma yang lain. Interval waktu yang diijinkan
dengan waktu yang dibutuhkan untuk menyelesaikan sebuah proses disebut turnaround
time.Turnaround time adalah jumlah periode tunggu untuk dapat ke memori,
menunggu di ready queue, eksekusi CPU, dan melakukan operasi I/O atau waktu
yang dihabiskan dari saat program atau job mulai masuk sistem sampai proses
diselesaikan sistem. Turnaround = waktu eksekusi + waktu menunggu
4.
Waiting
Time. Algoritma penjadwalan CPU tidak mempengaruhi waktu untuk melaksanakan
proses tersebut atau I/O, karena hanya mempengaruhi jumlah waktu yang
dibutuhkan proses diantrian ready. Waiting time adalah jumlah waktu yang
dbutuhkan proses di antrian ready.
5.
Response
time. Di sistem yang interaktif, turnaround time mungkin bukan waktu yang
terbaik untuk kriteria. Sering sebuah proses dapat memproduksi output di awal,
dan dapat meneruskan hasil yang baru sementara hasil yang sebelumnya telah
diberikan ke pengguna. ukuran lain adalah waktu dari pengiriman permintaan
sampai respon yang pertama diberikan. Hal ini disebut response time, yaitu
waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output
untuk respon tersebut. Turnround time umumnya dibatasi oleh kecepatan peralatan
keluaran. Ada dua jenis response time berdasarkan penggunaannya pada sistem
interaktif dan sistem waktu nyata (real time), yaitu:
a.
Terminal response time merupakan response time pada
sistem interaktif sebagai waktu yang dihabiskan dari saat karakter terakhir
dari perintah dimasukkan atau transaksi sampai hasil pertama muncul di layar.
b.
Event response time merupakan response time pada sistem
waktu nyata sebagai waktu dan kejadian (internal/eksternal) sampai instruksi
pertama rutin layanan yang dimaksud dieksekusi.
Sebaiknya
ketika kita akan membuat algoritma penjadwalan yang dilakukan adalah
memaksimalkan penggunaan CPU dan throughput, dan meminimalkan turnaround time,
waiting time, dan response time.
E.
Algoritma
Penjadwalan
Masalah
penjadwaln CPU adalah memutuskan proses mana yang berada di dalam antrian ready
akan dialokasikan ke CPU. Ada
beberapa algoritma penjadwalan CPU beberapa diantaranya akan di jelaskan pada
bagian berikut ini.
1.
First-Come
First-Served (FCFS)
Algoritma
ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU.
Dengan menggunakan algoritma ini seiap proses yang berada pada status ready
dimasukkan ke dalam antrian FIFO sesuai dengan waktu kedatangannya. Proses yang
tiba terlebih dahulu yang akan dieksekusi terlebih dahulu.
Misalnya
ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki
burst time 24 ms, P2 memiliki burst time 5 ms, P3 memiliki burst time 3 ms.
Hitunglah wating time rata-rata dan turnaround time (burst time + waiting time)
dari ketiga proses tersebut dengan menggunakan algoritma FCFS.
Proses Burst
time
P1 24 ms
P2 5 ms
P3 3 ms
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 29 ms (menunggu P1 dan
P2 selesai). Waiting time rata-ratanya adalah sebesar (0+24+29)/3 = 17,6 ms.
Turnaround
time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 29 ms (dihitung dari
awal kedatangan P2 hingga selesai dieksekusi), untuk p3 sebesar 32 ms.
Turnaround time rata-rata untuk ketiga proses tersebut adalah (24+29+32)/3 =
28,3 ms.
Kelemahan dari
algoritma ini:
a.
Waiting time rata-ratanya cukup lama.
b.
Terjadinya convoy effect, yaitu proses-proses menunggu
lama untuk menunggu satu 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.
2.
Shortest-Job
First (SJF)
Algoritma
ini mempunyai cara penjadwalan yang berbeda dengan FCFS. Dengan algoritma ini
maka setiap proses yang ada di antrian ready 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.
Ada beberapa
kekurangan dari algoritma ini yaitu:
a.
Kesulitan untuk memprediksi burst time proses yang akan
dieksekusi selanjutnya .
b.
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:
a.
Preemptive.
Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di antrian ready
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 antrian ready tersebut. Preemptive SJF sering disebut
juga Shortest-Remaining-Time-First scheduling.
b.
Non-preemptive.
CPU tidak memperbolehkan proses yang ada di antrian ready untuk menggeser proses
yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai
burst time yang lebih kecil.
Misalnya
ada empat buah proses dengan masing-masing waktu kedatangan burst time di
jelaskan pada tabel di bawah ini. Hitunglah waiting time rata-rata dan
turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF.
Proses Arrival time Burst Time
P1 0 ms 7 ms
P2 2 ms 4 ms
P3 4 ms 1 ms
P4 5 ms 4 ms
Solusi
Preemptive:
Rata-rata waiting
time adalah (9 + 1 + 0 +2)/4 = 3, dimana :
P1: (0-0+11-2) =
9
P2: (2-2+5-4) = 1
P3: (4-4) = 0
P4: (7-5) = 2
Rata-rata
turnaround time adalah ((9+7)+(1+4)+(0+1)+(4+2))/4 = 7
Solusi
Non-Preemptive:
Rata-rata waiting
time adalah (0 + 6 + 3 + 7)/4 = 4, dimana:
P1: (0-0) = 0
P2: (8-2) = 6
P3: (7-4) = 3
P4: (12-5) = 7
Rata-rata
turnaround time adalah ((0+7)+(6+4)+(3+1)+(7+4))/4 = 8
3.
Penjadwalan
dengan Prioritas
Priority
Scheduling merupakan algoritma penjadwalan yang mendahulukan proses dengan
nilai prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing. Prioritas suatu proses dapat
ditentukan melalui beberapa karakteristik antara lain:
a.
Batas waktu
b.
Kebutuhan Memori
c.
Akses file
d.
Perbandingan antara I/O Burst dengan CPU Burst
e.
Tingkat kepentingan proses
Penjadwalan
dengan prioritas 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 antrian.
Kelemahan
pada penjadwalan prioritas adalah dapat terjadinya indefinite blocking
(starvation) yaitu suatu proses dengan prioritas yang rendah memiliki
kemungkinan untuk tidak dieksekusi jika terdapatproses lain yang memiliki
prioritas lebih tinggi darinya. Solusi dari permasalahan ini adalah aging, yaitu
meningkatkan prioritas dari setiap proses yang menunggu dalam antrian secara
bertahap.
Misalnya:
Proses Burst time Prioritas
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Diagram Gantt
adalah sebagai berikut:
Rata-rata waiting
time adalah (6+0+16+18+1)/5 = 8.2
Rata-rata
turnaround time adalah ((6+10)+(0+1)+(16+2)+(18+1)+(1+5))/5 = 12
4.
Round Robin
Algoritma
ini didesin untuk sistem time-sharing. Proses akan mendapat jatah sebesar time
quantum dengan nilai quantum umumnya sebesar 10-100 ms. Jika time quantum-nya
habis atau proses sudah selesai CPU akan dialokasikan ke proses berikutnya.
Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua
proses mendapat jatah waktu yang sama dari CPU (1/n), dan tak akan menunggu
lebih lama dari (n-1)/q.
Algoritma
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.
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 time 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 6 quantum terlalu
besar, algoritma Round Robin akan berjalan seperti algoritma First Come First
Served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU
burst time yang lebih kecil dari 1 time quantum.
Misalnya
ada tiga proses dengan masing-masing mendapatkan waktu quantum adalah 4 ms,
maka P1 mendapatkan 4 ms pertama. Karena membutuhkan 20 ms lagi, sesudah
quantum pertama P1 di preemptive dan CPU memberikan proses berikutnya ke proses
P2 dan P2 tidak memerlukan 4 ms, P2 selesai sebelum jatah quantumnya habis,
kemudian CPU memberikan ke proses berikutnya yaitu P3. Ketika setaiap proses
meneriman satu quantum, CPU kembali ke proses P1 untuk tambahan waktu quantum.
Proses Burst time
P1 24 ms
P2 3 ms
P3 3 ms
Rata-rata waiting
time adalah (6+4+7)/3 = 5.66
Rata-rata
turnaround time adalah ((6+24)+(4+3)+(7+3))/3 = 15.67
5.
Antrian
Multilevel (Multilevel Queue)
Ide
dasar dari algoritma ini adalah berdasarkan pada sistem prioritas proses.
Prinsipnya adalah, jika setiap proses dapat dikelompokkan berdasarkan
prioritasnya, maka akan didapati queue seperti pada gambar berikut:
Gambar
3 Penjadwalan multilevel queue
Dari
gambar tersebut terlihat bahwa akan terjadi pengelompokan-pengelompokan
proses-proses berdasarkan prioritasnya. Kemudian muncul gagasan untuk
menganggap kelompok-kelompok tersebut 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 antrian akan berjalan dengan
algoritma FCFS dan dapat diketahui bahwa algoritma FCFS memiliki banyak
kelemahan, oleh karena itu dalam prakteknya, algoritma multilevel queue
memungkinkan adanya penerapan algoritma internal dalam masing-masing
subantriannya untuk meningkatkan kinerjanya, dimana setiap sub-antrian bisa memiliki
algoritma internal yang berbeda.
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.
6.
Multilevel
Feedback Queue
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. 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 dimanfaatkan penuh dan I/O dapat terus sibuk. Semakin rendah
tingkatannya, panjang CPU burst proses juga semakin besar.
Algoritma ini
didefinisikan melalui beberapa parameter, antara lain:
a.
Jumlah antrian
b.
Algoritma penjadwalan tiap antrian
c.
Kapan menaikkan proses ke antrian yang lebih tinggi
d.
Kapan
menurunkan proses ke antrian yang lebih rendah
e.
Antrian mana yang akan dimasuki proses yang membutuhkan
Gambar
4 Antrian multilevel feedback
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 mulilevel 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.
a.
Semua
proses yang baru datang akan diletakkan pada antrian 0 (quantum = 8 ms).
b.
Jika
suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan
dihentikan dan dipindahkan ke antrian pertama (quantum = 16 ms).
c.
Antrian
pertama hanya akan dikerjakan jika tidak ada lagi proses di antrian 0, dan jika
suatu proses di antrian pertama 1 tidak selesai dalam 16 ms, maka proses
tersebut akan dipindahkan ke antrian kedua.
d.
Antrian
kedua akan dikerjakan bila antrian 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:
a.
Jumlah
antrian
b.
Algoritma
internal tiap antrian
c.
Aturan sebuah proses naik ke antrian yang lebih tinggi
d.
Aturan
sebuah proses turun ke antrian yang lebih rendah
e.
Antrian
yang akan dimasuki tiap proses yang baru datang
Berdasarkan hal-hal di atas maka
algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan
kebutuhan sistem. Pada masa sekarang ini algoritma multilevel feedback queue adalah
salah satu yang paling banyak digunakan.
Nice Blog Post !
ReplyDelete