ALGORITMA PENJADWALAN
Abstrak
Paper ini membicarakan
tentang penjadwalan proses untuk manajemen proses yang mengelola proses-proses
yang datang. Penjadwalan proses ini akan menentukan proses mana dulu dan berapa
lama proses tersebut akan mendapatkan pelayanan dari CPU. Penjadwalan proses
dapat dilakukan dengan beberapa algoritma penjadwalan, dan setiap algoritma
memiliki kaunggulannya masing-masing. Algoritma yang dibahas dalam paper ini
adalah algoritma penjadwalan Multilevel Queue, Multilevel Feedback Queue dan
algoritma penjadwalan Guaranteed yang menerapkan strategi preemptive
berdasarkan prioritas dinamis. Selain itu akan dibahas juga algortima
penjadwalan Processor Jamak (Multiple Processor Schedulling) sebagai pembanding
dengan algoritma penjadwalan yang lain dimana pada penjadwalan ini dibutuhkan
dua processor dalam melakukan sebuah penjadwalan pada suatu proses. Dalam paper
ini juga akan dijelaskan kelemahan serta kelebihan masing – masing Algoritma
Penjadwalan.
I.
Pendahuluan
Sekarang ini, perkembangan komputer
sudah sangat pesat dan banyak digunakan dalam bidang kehidupan. Seringkali
pengguna komputer hanya menggunakan komputer untuk menyelesaikan persoalan yang
mereka hadapi tanpa tahu bagaimana computer memprosesnya. Seperti halnya
tentang sistem operasi yang merupakan interface antara pengguna dengan
perangkat keras computer sehingga kita tidak dirumitkan rincian-rincian
pengoperasian perangkat keras.
Sistem operasi melakukan beragam
tugas, salah satu tugas yang paling penting adalah manajemen proses, dimana
mengelola semua proses aktif dan mengalokasikan sumber daya ke proses-proses
itu sesuai kebijaksanaan yang diambil untuk memenuhi sasaran kinerja. Untuk
memutuskan proses yang harus berjalan, kapan dan selama berapa lama proses itu
berjalan maka diperlukan suatu teknik penjadwalan yang efektif.
Ada berbagai macam teknik penjadwalan
proses dengan keunggulannya masing-masing dan yang dibahas adalah penjadwalan
Multilevel Queue, penjadwalan Multilevel Feedback Queue, dan penjadwalan
Guaranteed yang akan dibandingkan dengan teknik penjadwalan yang paling berbeda
yaitu penjadwalan Prosessor Jamak (Multiple Processor)
Tujuan penelitian ini adalah membahas
dan menganalisis lebih rinci tentang penjadwalan Multilevel Queue, Multilevel
Feedback Queue, penjadwalan Guaranteed, penjadwalan Prosessor Jamak dan
perancangan simulasi untuk menggambarkan kinerja teknik penjadwalan tersebut
seta mengulas beberapa kelemahan dan keunggulan masing – masing algoritma
penjadwalan.
II.
Landasan
Teori
Sebagaimana
di ketahui Penjadwalan adalah fungsi dasar dari sistem operasi, semua resource
komputer di jadwalkan sebelum digunakan.
Penjadwalan
CPU adalah pemilihan proses dari Ready Queue untuk dapat di eksekusi.
Penjadwalan CPU di dasarkan pada sistem operasi yang menggunakan prinsip
Multiprogramming, yaitu beberapa proses berjalan dalam suatu waktu.
Penjadwalan
bertugas memutuskan :
a.
Proses yang
harus berjalan.
b.
Kapan dan selama
berapa lama proses itu berjalan.
Dalam penjadwalan proses, ada
pertimbangan untuk menjalankan penjadwalan diantaranya :
1.
Berpindah dari
keadaan running ke waiting
2.
Berpindah dari
keadaan running ke ready (interrupt)
3.
Berpindah dari
waiting ke ready (completion I/O)
4.
Selesai.
Pada saat CPU Idle, sistem operasi harus
memilih proses yang ada dalam memori utama (Ready Queue) dan mengalokasikan CPU
untuk mengeksekusinya. Setiap proses dalam ready queue harus mengantri sebelum mendapat
giliran eksekusi dalam CPU.
Setelah mempelajari konsep dasar
algoritma penjadwalan proses ini, mahasiswa di harapkan akan mampu :
a.
Memahami konsep
tentang dasar-dasar penjadwalan pada CPU.
b.
Memahami
kriteria apa saja yang di perlukan untuk penjadwalan pada CPU.
c.
Memahami
beberapa algoritma penjadwalan pada CPU.
III.
Pembahasan
Penjadwalan
proses adalah kumpulan kebijasanaan dan mekanisme pada sistem operasi berkenaan
dengan urutan kerja yang dilakukan sistem komputer. Penjadwalan bertugas
memutuskan proses yang harus berjalan, kapan, dan selama berapa lama proses itu
berjalan.
Kriteria
– kriteria yang dilakukan untuk mengukur dan optimasi kinerja penjadwalan
antara lain:
1. Adil
(fairness)
2. Efisiensi
3. Waktu
tanggap (response time)
4. Turn
around time
5. Through
put.
A.
Algoritma
Penjadwalan
1.
Multilevel Queue
Schedulling
Dari gambar di atas
terlihat bahwa akan terjadi pengelompokan proses-proses berdasarkan
prioritasnya. Dalam hal ini, dapat dilihat bahwa seolah-olah algoritma dengan
prioritas yang dasar adalah algoritma multilevel queue
dimana setiap queue akan berjalan
dengan algoritma First Come First Served (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.
2. Multilevel
Feedback Queue Schedulling
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:
a.
Semua proses
yang baru datang akan diletakkan pada queue 0 ( quantum= 8 ms).
b.
Jika suatu
proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan
dihentikan dan dipindahkan ke queue 1 ( quantum= 16 ms).
c.
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.
d.
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:
a. Jumlah antrian.
b. Algoritma internal tiap queue.
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.
3. Guaranteed
Schedulling
Algoritma penjadwalan ini memberikan daya pemroses yang sama
untuk membuat dan menyesuaikan kinerja. Algoritma yang memiliki kinerja yang
cukup bagus akan menjanjikan kelangsungan yang baik pula. Misalnya ada X
pemakai, maka setiap proses atau pemakai akan mendapatkan 1/X dari daya
pemroses CPU. Untuk mewujudkannya, system harus selalu menyimpan informasi
tentang jumlah waktu CPU untuk semua proses sejak login dan juga harus selalu
menyimpan informasi tentang berapa lama pemakai sedang login. System harus tahu
berapa CPU time untuk meyakinkan bahwa setiap pengguna mendapatkan jatah waktu
menggunakan CPU sesuai haknya dan juga berapa CPU time yang diperlukan oleh
setiap proses 1 pengguna serta berapa CPU time yang diperlukan oleh tiap-tiap
pengguna.
Misalkan
ada 5 pengguna, seperti pada table berikut:
Pengguna
|
CPU Time
|
A
|
5
|
B
|
4
|
C
|
8
|
D
|
1
|
E
|
2
|
Total waktu yang digunakan untuk mengakses kelima pengguna tersebut adalah
20ms, sehingga diharapkan tiap pengguna mendapatkan 20/5=4 ms. Kenyataannya,
mulai sejak login sampai saat ini tiap-tiap pengguna telah mendapatkan CPU
seperti pada table berikut. Rasio antara CPU yang diperoleh sampai saat ini
(actual) dengan CPU tang seharusnya diperoleh (4 ms) dapat dicari dengan:
Pengguna
|
CPU Aktual
|
Rasio
|
A
|
3
|
3/4=0.75
|
B
|
6
|
6/4=1.5
|
C
|
2
|
2/4=0.5
|
D
|
1
|
1/4=0.25
|
E
|
1
|
1/4=0.25
|
Dapat dilihat bahwa Pengguna A memiliki rasio 0.75, artinya
A baru mendapatkan ¾ dari jatah waktu yang seharusnya diterima. Pengguna B
memiliki rasio 1.5, artinya B mendapatkan 1.5 waktu dari jatah yang seharusnya
didapatkan. Algoritma ini menjalankan proses dengan rasio yang paling rendah
dulu sampai proses tersebut mendapatkan rasio melebihi rasio proses yang
sebelumnya mempunyai rasio satu tingkat labih tinggi darinya.
4. Multiple
Processor Schedulling
Untuk
mempertinggi kinerja, kehandalan, kemampuan komputasi, paralelisme, dan
keekonomisan dari suatu sistem, tambahan prosesor dapat diimplementasikan ke
dalam sistem tersebut. Sistem seperti ini disebut dengan sistem yang bekerja
dengan banyak prosesor (prosesor jamak atau multiprocessor).
Seperti halnya pada prosesor tunggal, prosesor jamak juga membutuhkan
penjadwalan. Namun pada prosesor jamak, penjadwalannya jauh lebih kompleks
daripada prosesor tunggal karena pada prosesor jamak memungkinkan adanya load sharing antar prosesor yang menyebabkan
penjadwalan menjadi lebih kompleks namun kemampuan sistem tersebut menjadi
lebih baik. Oleh karena itu, kita perlu mempelajari penjadwalan pada prosesor
jamak berhubung sistem dengan prosesor jamak akan semakin banyak digunakan
karena kemampuannya yang lebih baik dari sistem dengan prosesor tunggal.
Jenis
– jenis Multiple Processor Schedulling
a. Penjadwalan
Mater/Slave
Pendekatan pertama untuk penjadwalan
prosesor jamak adalah penjadwalan asymmetric multiprocessing atau bisa
disebut juga sebagai penjadwalan master/slave. Dimana pada metode ini
hanya satu prosesor( master) yang menangani semua keputusan penjadwalan,
pemrosesan M/K, dan aktivitas sistem lainnya dan prosesor lainnya ( slave)
hanya mengeksekusi proses. Metode ini sederhana karena hanya satu prosesor yang
mengakses struktur data sistem dan juga mengurangi data sharing. Dalam
teknik penjadwalan master/slave, satu prosesor menjaga status dari semua
proses dalam sistem dan menjadwalkan kinerja untuk semua prosesor slave.
Sebagai contoh, prosesor master memilih proses yang akan dieksekusi,
kemudian mencari prosesor yang available, dan memberikan instruksi Start
processor. Prosesor slave memulai eksekusi pada lokasi memori yang
dituju. Saat slave mengalami sebuah kondisi tertentu seperti meminta
M/K, prosesor slave memberi interupsi kepada prosesor master dan
berhenti untuk menunggu perintah selanjutnya. Perlu diketahui bahwa prosesor slave
yang berbeda dapat ditujukan untuk suatu proses yang sama pada waktu yang
berbeda.
Gambar 15.1. Multiprogramming
dengan multiprocessor
Gambar di atas mengilustrasikan
perilaku dari multiprocessor yang digunakan untuk multiprogramming
Beberapa proses terpisah dialokasikan di dalam memori. Ruang alamat proses
terdiri dari halaman-halaman sehingga hanya sebagian saja dari proses tersebut
yang berada dalam memori pada satu waktu. Hal ini memungkinkan banyak proses
dapat aktif dalam sistem.
b. Penjadwalan
Symmetric Multiprocessing (SMP)
Penjadwalan SMP ( Symmetric multiprocessing) adalah pendekatan
kedua untuk penjadwalan prosesor jamak. Dimana setiap prosesor menjadwalkan
dirinya sendiri ( self scheduling).
Semua proses mungkin berada pada antrian ready
yang biasa, atau mungkin setiap prosesor memiliki antrian ready tersendiri. Bagaimanapun juga,
penjadwalan terlaksana dengan menjadwalkan setiap prosesor untuk memeriksa
antrian ready dan memilih suatu proses
untuk dieksekusi. Jika suatu sistem prosesor jamak mencoba untuk mengakses dan
meng- update suatu struktur data,
penjadwal dari prosesor-prosesor tersebut harus diprogram dengan hati-hati;
kita harus yakin bahwa dua prosesor tidak memilih proses yang sama dan proses
tersebut tidak hilang dari antrian. Secara virtual, semua sistem operasi modern
mendukung SMP, termasuk Windows XP, Windows 2000, Solaris, Linux, dan Mac OS X.
c. Affinity
Data
yang paling sering diakses oleh beberapa proses akan memadati cache pada
prosesor,sehingga akses memori yang sukses biasanya terjadi di memori cache.
Namun, jika suatu proses . berpindah dari satu prosesor ke prosesor lainnya
akan mengakibatkan isi dari cache memori yang dituju menjadi tidak
valid, sedangkan cache memori dari prosesor asal harus disusun kembali
populasi datanya. Karena mahalnya invalidating dan re-populating
dari cache, kebanyakan sistem SMP mencoba untuk mencegah migrasi proses antar
prosesor sehingga menjaga proses tersebut untuk berjalan di prosesor yang sama.
Hal ini disebut afinitas prosesor ( processor affinity). Ada dua jenis
afinitas prosesor, yakni:
·
Soft affinity yang memungkinkan proses berpindah dari satu prosesor ke
prosesor yang lain, dan
·
Hard affinity yang menjamin bahwa suatu proses akan berjalan pada
prosesor yang sama dan tidak berpindah. Contoh sistem yang menyediakan system
calls yang mendukung hard affinity adalah Linux.
d. Load Balancing
Dalam
sistem SMP, sangat penting untuk menjaga keseimbangan workload antara
semua prosesor untuk memaksimalkan keuntungan memiliki multiprocessor.
Jika tidak, mungkin satu atau lebih prosesor idle disaat prosesor lain
harus bekerja keras dengan workload yang tinggi. Load balancing
adalah usaha untuk menjaga workload terdistribusi sama rata untuk semua
prosesor dalam sistem SMP. Perlu diperhatikan bahwa load balancing hanya
perlu dilakukan pada sistem dimana setiap prosesor memiliki antrian tersendiri(
private queue) untuk proses-proses yang berstatus ready. Pada
sistem dengan antrian yang biasa ( common queue), load balancing
tidak diperlukan karena sekali prosesor menjadi idle, prosesor tersebut
segera mengerjakan proses yang dapat dilaksanakan dari antrian biasa tersebut.
Perlu juga diperhatikan bahwa pada sebagian besar sistem operasi kontemporer
mendukung SMP, jadi setiap prosesor bisa memiliki private queue. Ada dua
jenis load balancing, yakni:
·
Push migration, pada kondisi ini ada suatu task spesifik yang
secara berkala memeriksa load dari tiap-tiap prosesor. Jika terdapat
ketidakseimbangan, maka dilakukan perataan dengan memindahkan( pushing)
proses dari yang kelebihan muatan ke prosesor yang idle atau yang
memiliki muatan lebih sedikit.
·
Pull migration, kondisi ini terjadi saat prosesor yang idle
menarik( pulling) proses yang sedang menunggu dari prosesor yang sibuk.
Kedua pendekatan tersebut tidak
harus mutually exclusive dan dalam kenyataannya sering diimplementasikan
secara paralel pada sistem load-balancing.
Keuntungan dari affinity
berlawanan dengan keuntungan dari load balancing, yaitu keuntungan
menjaga suatu proses berjalan pada satu prosesor yang sama dimana proses dapat
memanfaatkan data yang sudah ada pada memori cache prosesor tersebut
berkebalikan dengan keuntungan menarik atau memindahkan proses dari satu
prosesor ke prosesor lain. Dalam kasus system engineering, tidak ada
aturan tetap keuntungan yang mana yang lebih baik. Walaupun pada beberapa
sistem, prosesor idle selalu menarik proses dari prosesor non-idle
sedangkan pada sistem yang lain, proses dipindahkan hanya jika terjadi
ketidakseimbangan yang besar antara prosesor.
e.
Symetric Multithreading
Ide dari SMT adalah untuk
menciptakan banyak logical processor
dalam suatu physical processor
yang sama dan mempresentasikan beberapa prosesor kepada sistem operasi. Setiap logical processor mempunyai state
arsitekturnya sendiri yang mencangkup general purpose
dan machine state register.
Lebih jauh lagi, setiap logical prosesor
bertanggung jawab pada penanganan interupsinya sendiri, yang berarti bahwa
interupsi cenderung dikirimkan ke logical processor
dan ditangani oleh logical processor
bukan physical processor.
Dengan kata lain, setiap logical processor
men- share resource
dari physical processor-nya,
seperti chace dan bus.
Gambar 15.2. Symetric Multithreading
Gambar di atas
mengilustrasikan suatu tipe arsitektur SMT dengan dua physical processor dengan masing-masing
punya dua logical processor.
Dari sudut pandang sistem operasi, pada sistem ini terdapat empat prosesor. Perlu
diketahui bahwa SMT adalah fitur yang disediakan dalam hardware, bukan
software, sehingga hardware harus menyediakan representasi state arsitektur
dari setiap logical processor
sebagaimana representasi dari penanganan interupsinya. Sistem operasi tidak
perlu didesain khusus jika berjalan pada sistem SMT, akan tetapi performa yang
diharapkan tidak selalu terjadi pada sistem operasi yang berjalan pada SMT.
Misalnya, suatu sistem memiliki 2 physical processor,
keduanya idle, penjadwal pertama
kali akan lebih memilih untuk membagi thread ke physical processor daripada membaginya ke
logical processor
dalam physical processor
yang sama, sehingga logical processor
pada satu physical processor
bisa menjadi sibuk sedangkan physical processor
yang lain menjadi idle.
f.
Multicore
Multiprocessor
Multicore microprocessor adalah kombinasi dua atau lebih prosesor independen kedalam
sebuah integrated circuit(IC). Umumnya, multicore mengizinkan perangkat
komputasi untuk memeragakan suatu bentuk thread level paralelism(TLP)
tanpa mengikutsertakan banyak prosesor terpisah. TLP lebih dikenal sebagai chip-level
multiprocessing.
Gambar 15.3. Chip CPU dual-core
Keuntungan:
·
Meningkatkan performa dari operasi cache snoop (bus
snooping). Bus snooping adalah suatu teknik yang digunakan dalam
sistem pembagian memori terdistribusi dan multiprocessor yang ditujukan
untuk mendapatkan koherensi pada cache. Hal ini dikarenakan sinyal antara
CPU yang berbeda mengalir pada jarak yang lebih dekat, sehingga kekuatan sinyal
hanya berkurang sedikit. Sinyal dengan kualitas baik ini memungkinkan lebih
banyak data yang dikirimkan dalam satu periode waktu dan tidak perlu sering di-
repeat.
·
Secara fisik, desain CPU multicore menggunakan ruang
yang lebih kecil pada PCB ( Printed Circuit Board) dibanding dengan
desain multichip SMP.
·
Prosesor dual-core menggunakan sumber daya lebih
kecil dibanding sepasang prosesor dual-core.
·
Desain multicore memiliki resiko design error
yang lebih rendah daripada desain single-core.
Kerugian:
·
Dalam hal sistem operasi, butuh penyesuaian kepada software
yang ada untuk memaksimalkan kegunaan dari sumberdaya komputasi yang disediakan
oleh prosesor multicore. Kemampuan prosesor multicore untuk
meningkatkan performa aplikasi juga bergantung pada penggunaan banyaknya thread
dalam aplikasi tersebut.
·
Dari sudut pandang arsitektur, pemanfaatan daerah permukaan silikon dari desain single-core lebih
baik daripada desain multicore.
·
Pengembangan chip multicore membuat produksinya
menjadi menurun karena semakin sulitnya pengaturan suhu pada chip yang padat.
B. Evaluasi
Algoritma Penjadwalan CPU
a.
Model
deterministik (analisis langsung)
·
SJF à kurang dari
setengah waktu tunggu rata algoritma FCFS
·
RR à nilai
tengah-tengah
b.
Model
pengantrian (Queueing model)
c.
Implementasi
(simulasi) : biaya tinggi
IV.
Kesimpulan
Dari pembahasan di atas kita dapat
menarik sebuah kesimpulan tentang beberapa algoritma yang sudah dibahas, yaitu:
1. Multilevel Queue.
Algoritma ini membagi beberapa antrian yang akan diberi prioritas berdasarkan
tingkatan. Tingkatan lebih tinggi menjadi prioritas utama.
2. Multilevel Feedback Queue.
Pada dasarnya sama dengan Multilevel Queue,
yang membedakannya adalah pada algoritma ini diizinkan untuk pindah antrian.
3. Guaranted Schedulling. Algoritma ini akan menjalankan
proses dengan rasio terendah sampai dengan rasio proses di atas pesaingnya.
4. Multiple Processing. Pada algoritma ini
dibutuhkan dua prosessor yang digunakan untuk melakukan proses penjadwalan.
V.
Referensi
2.
Hariyanto, Bambang, Ir, “Sistem Operasi”, Edisi
Kedua, Informatika, Bandung, 1997.
3.
Hariningsih, SP, “Sistem Operasi”, Graha Ilmu,
Yogyakarta, 2003.
4.
Stalling, William, “Operating System”, 2nd Edition, Prenticell Hall
International Editions, USA, 1995.