programer skripsi tesis tugas akhir
-

Contoh Program Source Code   /

Algoritma Penjadwalan CPU

Posted on 05.55
Join with us

ALGORITMA PENJADWALAN CPU

Artikel ini membicarakan ttg penjadwalan proses unt manajemen proses yg mengelola proses-proses yg datang. Penjadwalan proses ini akan menentukan proses mana dulu & berapa lama proses tersebut akan mendapatkan pelayanan dari CPU. Penjadwalan proses dpt dilakukan dg beberapa algoritma penjadwalan, & setiap algoritma memiliki kaunggulannya masing-masing. Algoritma yg dibahas dlm paper ini adalah algoritma penjadwalan Multilevel Queue, Multilevel Feedback Queue & algoritma penjadwalan Guaranteed yg menerapkan strategi preemptive berdasarkan prioritas dinamis.

Penjadwalan CPU dpt bersifat preemptive / nonpreemptive. Pada penjadwalan preemptive, CPU yg dialokasikan ke suatu proses dpt ditarik kembali oleh sistem operasi & dialihkan ke proses lainnya dg kata lain sistem operasi memberhentikan sementara proses yg sedang berjalan unt memberi ruang kepada proses yg prioritasnya lebih tinggi. Sedangkan pada penjadwalan nonpreemptive bersifat sebaliknya, sekali CPU dialokasikan ke sebuah proses, maka proses akan menggunakan CPU tersebut sampai proses melepaskannya krn proses telah terminate / proses beralih ke waiting state.

Selain itu akan dibahas juga algortima penjadwalan Processor Jamak (Multiple Processor Schedulling) sebagai pembanding dg algoritma penjadwalan yg lain dimana pada penjadwalan ini dibutuhkan dua processor dlm melakukan sebuah penjadwalan pada suatu proses. dlm paper ini juga akan dijelaskan kelemahan serta kelebihan masing – masing Algoritma Penjadwalan.

Pendahuluan

Sekarang ini, perkembangan komputer sudah sangat pesat & banyak dipakai dlm bidang kehidupan. Seringkali pengguna komputer hanya menggunakan komputer unt menyelesaikan persoalan yg mereka hadapi tanpa tahu bagaimana computer memprosesnya. Seperti halnya ttg sistem operasi yg merupakan interface antara pengguna dg perangkat keras computer sehingga kita tidak dirumitkan rincian-rincian pengoperasian perangkat keras.

Sistem operasi melakukan beragam tugas, salah satu tugas yg paling penting adalah manajemen proses, dimana mengelola semua proses aktif & mengalokasikan sumber daya ke proses-proses itu sesuai kebijaksanaan yg diambil unt memenuhi sasaran kinerja. unt memutuskan proses yg harus berjalan, kapan & selama berapa lama proses itu berjalan maka diperlukan suatu teknik penjadwalan yg efektif.

Ada berbagai macam teknik penjadwalan proses dg keunggulannya masing-masing & yg dibahas adalah penjadwalan Multilevel Queue, penjadwalan Multilevel Feedback Queue, & penjadwalan Guaranteed yg akan dibandingkan dg teknik penjadwalan yg paling berbeda yaitu penjadwalan Prosessor Jamak (Multiple Processor)

Tujuan penelitian ini adalah membahas & menganalisis lebih rinci ttg penjadwalan Multilevel Queue, Multilevel Feedback Queue, penjadwalan Guaranteed, penjadwalan Prosessor Jamak & perancangan simulasi unt menggambarkan kinerja teknik penjadwalan tersebut seta mengulas beberapa kelemahan & keunggulan masing – masing algoritma penjadwalan.

Landasan Teori

Sebagaimana di ketahui Penjadwalan adalah fungsi dasar dari sistem operasi, semua resource komputer di jadwalkan sebelum dipakai.

Penjadwalan CPU adalah pemilihan proses dari Ready Queue unt dpt di eksekusi. Penjadwalan CPU di dasarkan pada sistem operasi yg menggunakan prinsip Multiprogramming, yaitu beberapa proses berjalan dlm suatu waktu.

Penjadwalan bertugas memutuskan :

a.       Proses yg harus berjalan.
b.      Kapan & selama berapa lama proses itu berjalan.

Dalam penjadwalan proses, ada pertimbangan unt 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 yg ada dlm memori utama (Ready Queue) & mengalokasikan CPU unt mengeksekusinya. Setiap proses dlm ready queue harus mengantri sebelum mendapat giliran eksekusi dlm CPU.

Setelah mempelajari konsep dasar algoritma penjadwalan proses ini, mahasiswa di harapkan akan mampu :
a.       Memahami konsep ttg dasar-dasar penjadwalan pada CPU.
b.      Memahami kriteria apa saja yg di perlukan unt penjadwalan pada CPU.
c.       Memahami beberapa algoritma penjadwalan pada CPU.

Pembahasan

Penjadwalan proses adalah kumpulan kebijasanaan & mekanisme pada sistem operasi berkenaan dg urutan kerja yg dilakukan sistem komputer. Penjadwalan bertugas memutuskan proses yg harus berjalan, kapan, & selama berapa lama proses itu berjalan.

Kriteria – kriteria yg dilakukan unt mengukur & optimasi kinerja penjadwalan antara lain:

1.      Adil (fairness)
2.      Efisiensi
3.      Waktu tanggap (response time)
4.      Turn around time
5.      Through put.

Algoritma Penjadwalan

1.         Multilevel Queue Schedulling

Dari gambar di atas terlihat bahwa akan terjadi pengelompokan proses-proses berdasarkan prioritasnya. dlm hal ini, dpt dilihat bahwa seolah-olah algoritma dg prioritas yg dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dg algoritma First Come First Served (FCFS) yg memiliki banyak kelemahan. Oleh krn itu, dlm prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dlm masing-masing sub-antriannya, yg bisa memiliki algoritma internal yg berbeda unt meningkatkan kinerjanya.

Berawal dari priority scheduling, algoritma ini pun memiliki kelemahan yg sama dg priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dg prioritas rendah bisa saja tidak mendapat jatah CPU. unt mengatasi hal tersebut, salah satu caranya adalah dg memodifikasi algoritma ini dg adanya jatah waktu maksimal unt tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan & digantikan oleh antrian dibawahnya, & tentu saja batas waktu unt tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

2.      Multilevel Feedback Queue Schedulling

Multilevel feedback queue adalah salah satu algoritma yg berdasar pada algoritma multilevel queue. Perbedaan mendasar yg membedakan multilevel feedback queue dg multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dg prioritas yg lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut:

a.      Semua proses yg baru datang akan diletakkan pada queue 0 ( quantum= 8 ms).
b.      Jika suatu proses tidak dpt diselesaikan dlm 8 ms, maka proses tersebut akan dihentikan & dipindahkan ke queue 1 ( quantum= 16 ms).
c.       Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, & jika suatu proses di queue 1 tidak selesai dlm 16 ms, maka proses tersebut akan dipindahkan ke queue 2.
d.      Queue 2 akan dikerjakan bila queue 0 & 1 kosong, & akan berjalan dg algoritma FCFS.

Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dlm hal ini ditentukan oleh time quantum, namun dlm prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dg mendefinisikan terlebih dahulu parameter-parameternya, yaitu:

a.      Jumlah antrian.
b.      Algoritma internal tiap queue.
c.       Aturan sebuah proses naik ke antrian yg lebih tinggi.
d.      Aturan sebuah proses turun ke antrian yg lebih rendah.
e.      Antrian yg akan dimasuki tiap proses yg baru datang.

3.      Guaranteed Schedulling

Algoritma penjadwalan ini memberikan daya pemroses yg sama unt membuat & menyesuaikan kinerja. Algoritma yg memiliki kinerja yg cukup bagus akan menjanjikan kelangsungan yg baik pula. Misalnya ada X pemakai, maka setiap proses / pemakai akan mendapatkan 1/X dari daya pemroses CPU. unt mewujudkannya, system harus selalu menyimpan informasi ttg jumlah waktu CPU unt semua proses sejak login & juga harus selalu menyimpan informasi ttg berapa lama pemakai sedang login.

System harus tahu berapa CPU time unt meyakinkan bahwa setiap pengguna mendapatkan jatah waktu menggunakan CPU sesuai haknya & juga berapa CPU time yg diperlukan oleh setiap proses 1 pengguna serta berapa CPU time yg 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 yg dipakai unt 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 yg diperoleh sampai saat ini (actual) dg CPU tang seharusnya diperoleh (4 ms) dpt 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 yg seharusnya diterima. Pengguna B memiliki rasio 1.5, artinya B mendapatkan 1.5 waktu dari jatah yg seharusnya didapatkan. Algoritma ini menjalankan proses dg rasio yg paling rendah dulu sampai proses tersebut mendapatkan rasio melebihi rasio proses yg sebelumnya mempunyai rasio satu tingkat labih tinggi darinya.

4.      Multiple Processor Schedulling

Untuk mempertinggi kinerja, kehandalan, kemampuan komputasi, paralelisme, & keekonomisan dari suatu sistem, tambahan prosesor dpt diimplementasikan ke dlm sistem tersebut. Sistem seperti ini disebut dg sistem yg bekerja dg banyak prosesor (prosesor jamak / multiprocessor). Seperti halnya pada prosesor tunggal, prosesor jamak juga membutuhkan penjadwalan. Namun pada prosesor jamak, penjadwalannya jauh lebih kompleks daripada prosesor tunggal krn pada prosesor jamak memungkinkan adanya load sharing antar prosesor yg menyebabkan penjadwalan menjadi lebih kompleks namun kemampuan sistem tersebut menjadi lebih baik. Oleh krn itu, kita perlu mempelajari penjadwalan pada prosesor jamak berhubung sistem dg prosesor jamak akan semakin banyak dipakai krn kemampuannya yg lebih baik dari sistem dg prosesor tunggal.

Jenis – jenis Multiple Processor Schedulling

a.       Penjadwalan Mater/Slave

Pendekatan pertama unt penjadwalan prosesor jamak adalah penjadwalan asymmetric multiprocessing / bisa disebut juga sebagai penjadwalan master/slave. Dimana pada metode ini hanya satu prosesor( master) yg menangani semua keputusan penjadwalan, pemrosesan M/K, & aktivitas sistem lainnya & prosesor lainnya ( slave) hanya mengeksekusi proses. Metode ini sederhana krn hanya satu prosesor yg mengakses struktur data sistem & juga mengurangi data sharing. dlm teknik penjadwalan master/slave, satu prosesor menjaga status dari semua proses dlm sistem & menjadwalkan kinerja unt semua prosesor slave. Sebagai contoh, prosesor master memilih proses yg akan dieksekusi, kemudian mencari prosesor yg available, & memberikan instruksi Start processor. Prosesor slave memulai eksekusi pada lokasi memori yg dituju. Saat slave mengalami sebuah kondisi tertentu seperti meminta M/K, prosesor slave memberi interupsi kepada prosesor master & berhenti unt menunggu perintah selanjutnya. Perlu diketahui bahwa prosesor slave yg berbeda dpt ditujukan unt suatu proses yg sama pada waktu yg berbeda.

Gambar 15.1. Multiprogramming dg multiprocessor

Gambar di atas mengilustrasikan perilaku dari multiprocessor yg dipakai unt multiprogramming Beberapa proses terpisah dialokasikan di dlm memori. Ruang alamat proses terdiri dari halaman-halaman sehingga hanya sebagian saja dari proses tersebut yg berada dlm memori pada satu waktu. Hal ini memungkinkan banyak proses dpt aktif dlm sistem.

b.      Penjadwalan Symmetric Multiprocessing (SMP)

Penjadwalan SMP ( Symmetric multiprocessing) adalah pendekatan kedua unt penjadwalan prosesor jamak. Dimana setiap prosesor menjadwalkan dirinya sendiri ( self scheduling). Semua proses mungkin berada pada antrian ready yg biasa, / mungkin setiap prosesor memiliki antrian ready tersendiri. Bagaimanapun juga, penjadwalan terlaksana dg menjadwalkan setiap prosesor unt memeriksa antrian ready & memilih suatu proses unt dieksekusi. Jika suatu sistem prosesor jamak mencoba unt mengakses & meng- update suatu struktur data, penjadwal dari prosesor-prosesor tersebut harus diprogram dg hati-hati; kita harus yakin bahwa dua prosesor tidak memilih proses yg sama & proses tersebut tidak hilang dari antrian. Secara virtual, semua sistem operasi modern mendukung SMP, termasuk Windows XP, Windows 2000, Solaris, Linux, & Mac OS X.

c.       Affinity

Data yg paling sering diakses oleh beberapa proses akan memadati cache pada prosesor,sehingga akses memori yg sukses biasanya terjadi di memori cache. Namun, jika suatu proses . berpindah dari satu prosesor ke prosesor lainnya akan mengakibatkan isi dari cache memori yg dituju menjadi tidak valid, sedangkan cache memori dari prosesor asal harus disusun kembali populasi datanya. krn mahalnya invalidating & re-populating dari cache, kebanyakan sistem SMP mencoba unt mencegah migrasi proses antar prosesor sehingga menjaga proses tersebut unt berjalan di prosesor yg sama. Hal ini disebut afinitas prosesor ( processor affinity). Ada dua jenis afinitas prosesor, yakni:
·         Soft affinity yg memungkinkan proses berpindah dari satu prosesor ke prosesor yg lain, dan
·         Hard affinity yg menjamin bahwa suatu proses akan berjalan pada prosesor yg sama & tidak berpindah. Contoh sistem yg menyediakan system calls yg mendukung hard affinity adalah Linux.

d.      Load Balancing

Dalam sistem SMP, sangat penting unt menjaga keseimbangan workload antara semua prosesor unt memaksimalkan keuntungan memiliki multiprocessor. Jika tidak, mungkin satu / lebih prosesor idle disaat prosesor lain harus bekerja keras dg workload yg tinggi. Load balancing adalah usaha unt menjaga workload terdistribusi sama rata unt semua prosesor dlm sistem SMP. Perlu diperhatikan bahwa load balancing hanya perlu dilakukan pada sistem dimana setiap prosesor memiliki antrian tersendiri( private queue) unt proses-proses yg berstatus ready. Pada sistem dg antrian yg biasa ( common queue), load balancing tidak diperlukan krn sekali prosesor menjadi idle, prosesor tersebut segera mengerjakan proses yg dpt 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 yg secara berkala memeriksa load dari tiap-tiap prosesor. Jika terdapat ketidakseimbangan, maka dilakukan perataan dg memindahkan( pushing) proses dari yg kelebihan muatan ke prosesor yg idle / yg memiliki muatan lebih sedikit.
·         Pull migration, kondisi ini terjadi saat prosesor yg idle menarik( pulling) proses yg sedang menunggu dari prosesor yg sibuk.
Kedua pendekatan tersebut tidak harus mutually exclusive & dlm kenyataannya sering diimplementasikan secara paralel pada sistem load-balancing.
Keuntungan dari affinity berlawanan dg keuntungan dari load balancing, yaitu keuntungan menjaga suatu proses berjalan pada satu prosesor yg sama dimana proses dpt memanfaatkan data yg sudah ada pada memori cache prosesor tersebut berkebalikan dg keuntungan menarik / memindahkan proses dari satu prosesor ke prosesor lain. dlm kasus system engineering, tidak ada aturan tetap keuntungan yg mana yg lebih baik. Walaupun pada beberapa sistem, prosesor idle selalu menarik proses dari prosesor non-idle sedangkan pada sistem yg lain, proses dipindahkan hanya jika terjadi ketidakseimbangan yg besar antara prosesor.

e.      Symetric Multithreading

Ide dari SMT adalah unt menciptakan banyak logical processor dlm suatu physical processor yg sama & mempresentasikan beberapa prosesor kepada sistem operasi. Setiap logical processor mempunyai state arsitekturnya sendiri yg mencangkup general purpose & machine state register. Lebih jauh lagi, setiap logical prosesor bertanggung jawab pada penanganan interupsinya sendiri, yg berarti bahwa interupsi cenderung dikirimkan ke logical processor & ditangani oleh logical processor bukan physical processor. dg kata lain, setiap logical processor men- share resource dari physical processor-nya, seperti chace & bus.

Gambar 15.2. Symetric Multithreading

Gambar di atas mengilustrasikan suatu tipe arsitektur SMT dg dua physical processor dg masing-masing punya dua logical processor. Dari sudut pandang sistem operasi, pada sistem ini terdapat empat prosesor. Perlu diketahui bahwa SMT adalah fitur yg disediakan dlm 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 yg diharapkan tidak selalu terjadi pada sistem operasi yg berjalan pada SMT. Misalnya, suatu sistem memiliki 2 physical processor, keduanya idle, penjadwal pertama kali akan lebih memilih unt membagi thread ke physical processor daripada membaginya ke logical processor dlm physical processor yg sama, sehingga logical processor pada satu physical processor bisa menjadi sibuk sedangkan physical processor yg lain menjadi idle.

f.        Multicore Multiprocessor

Multicore microprocessor adalah kombinasi dua / lebih prosesor independen kedalam sebuah integrated circuit(IC). Umumnya, multicore mengizinkan perangkat komputasi unt 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 yg dipakai dlm sistem pembagian memori terdistribusi & multiprocessor yg ditujukan unt mendapatkan koherensi pada cache. Hal ini dikarenakan sinyal antara CPU yg berbeda mengalir pada jarak yg lebih dekat, sehingga kekuatan sinyal hanya berkurang sedikit. Sinyal dg kualitas baik ini memungkinkan lebih banyak data yg dikirimkan dlm satu periode waktu & tidak perlu sering di- repeat.
·         Secara fisik, desain CPU multicore menggunakan ruang yg lebih kecil pada PCB ( Printed Circuit Board) dibanding dg desain multichip SMP.
·         Prosesor dual-core menggunakan sumber daya lebih kecil dibanding sepasang prosesor dual-core.
·         Desain multicore memiliki resiko design error yg lebih rendah daripada desain single-core.
Kerugian:
·         dlm hal sistem operasi, butuh penyesuaian kepada software yg ada unt memaksimalkan kegunaan dari sumberdaya komputasi yg disediakan oleh prosesor multicore. Kemampuan prosesor multicore unt meningkatkan performa aplikasi juga bergantung pada penggunaan banyaknya thread dlm 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 krn semakin sulitnya pengaturan suhu pada chip yg 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

1. First-Come, First-Served Scheduling (FCFS)


Algoritma ini merupakan algoritma penjadwalan yg paling sederhana yg dipakai CPU. dg menggunakan algoritma ini seiap proses yg berada pada status ready dimasukkan ke dlm FIFO queue sesuai dg waktu kedatangannya. Proses yg tiba terlebih dahulu yg akan dieksekusi.

contoh:

Ada 3 buah proses yg 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 & turnaround time (burst time + waiting time) dari ketiga proses tersebut dg menggunakan algoritma FCFS.

Waiting time unt p1 adalah 0 ms (p1 tidak perlu menunggu),sedangkan unt p2 adalah sebesar 24 ms (menunggu p1 selesai) & unt p3 sebesar 29 ms (menunggu p1 & p2 selesai). Waiting time rata-ratanya adalah sebesar (0+24+29)/3 = 17,6 ms.
Turnaround time unt p1 sebesar 24 ms, sedangkan unt p2 sebesar 29 ms (dihitung dari awal kedatangan p2 hingga selesai dieksekusi),untuk p3 sebesar 32 ms. Turnaround time rata-rata unt ketiga proses tersebut adalah (24+29+32)/3 = 28,3 ms.

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 yg sedang dieksekusi oleh CPU

Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yg sedang dieksekusi oleh CPU tidak dpt di-interrupt oleh proses yg lain.

 2. Shortest-Job-First-Scheduling (SJF)  

Algoritma ini mempunyai cara penjadwalan yg berbeda dg FCFS.Dengan algoritma ini maka setiap proses yg ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yg pendek unt setiap proses & krn hal tersebut maka waiting time rata-ratanya juga menjadi pendek,sehingga dpt dikatakan bahwa algoritma ini adalah algoritma yg optimal.

Ada beberapa kekurangan dari algoritma ini yaitu:
1. Susahnya unt memprediksi burst time proses yg akan dieksekusi selanjutnya
2. Proses yg mempunyai burst time yg besar akan memiliki waiting time yg besar pula krn yg dieksekusi terlebih dahulu adalah proses dg burst time yg lebih kecil

Algoritma ini dpt dibagi menjadi 2 bagian yaitu:

1. Preemptive

Jika ada proses yg sedang dieksekusi oleh CPU & terdapat proses di ready queue dg burst time yg lebih kecil daripada proses yg sedang dieksekusi tersebut, maka proses yg sedang dieksekusi oleh CPU akan digantikan oleh proses yg berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining-Time-First scheduling.

2. Non-preemptive

CPU tidak memperbolehkan proses yg ada di ready queue unt menggeser proses yg sedang dieksekusi oleh CPU meskipun proses yg baru tersebut mempunyai burst time yg lebih kecil.

Contoh:

Ada 3 buah proses yg datang berurutan yaitu p1 dg arrival time pada 0 ms dg burst time 4 ms, p2 dg arrival time pada 0 ms dg burst time 5 ms, p3 dg arrival time pada 1 ms dg burst time 2 ms. Hitunglah waiting time rata-rata & turnaround time dari ketiga proses tersebut dg mengunakan algoritma SJF.

Waiting time rata-rata unt ketiga proses tersebut adalah sebesar ((3-1)+(6-0)+(1-1))/3 = 2,6 ms. Turnaround time dari ketiga proses tersebut adalah sebesar (6+11+(3-1))/3 = 6,3 ms.

Waiting time rata-rata unt ketiga prses tersebut adalah sebesar (0+6+(4-1))/3 = 3 ms Turnaround time dari ketiga proses tersebut adalah sebesar (4+11+(6-1))/3 = 6,6 ms


3. Priority Scheduling


Priority Scheduling merupakan algoritma penjadwalan yg mendahulukan proses yg memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing.
Prioritas suatu proses dpt ditentukan melalui beberapa karakteristik antara lain:

1. Time limit
2. Memory requirement
3. Akses file
4. Perbandingan antara I/O Burst dg CPU Burst
5. Tingkat kepentingan proses

Priority Scheduling juga dpt dijalankan secara preemptive maupun non-preemptive.
Pada preemptive, jika ada suatu proses yg baru datang memiliki prioritas yg lebih tinggi daripada proses yg sedang dijalankan, maka proses yg sedang berjalan tersebut dihentikan, lalu CPU dialihkan unt proses yg baru datang tersebut.Sementara itu, pada non-preemptive, proses yg baru datang tidak dpt menganggu proses yg sedang berjalan, tetapi hanya diletakkan di depan queue. Kelemahan pada priority scheduling adalah dpt terjadinya indefinite blocking (starvation). Suatu proses dg prioritas yg rendah memiliki kemungkinan unt tidak dieksekusi jika terdapat proses lain yg memiliki prioritas lebih tinggi darinya.Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yg menunggu dlm queue secara bertahap.

Contoh:

Setiap 10 menit, prioritas dari masing-masing proses yangmenunggu dlm queue dinaikkan satu tingkat.Maka, suatu proses yg memiliki prioritas 127, setidaknya dalam21 jam 20 menit, proses tersebut akan memiliki prioritas 0,yaitu prioritas yg tertinggi. (semakin kecil angka menunjukkanbahwa prioritasnya semakin tinggi)

4. Round Robin


Algoritma penjadwalan ini mirip dg algoritma First Come FirstServed, tetapi proses ini memberi suatu batasan waktu unt setiap proses yg disebut dg time quantum. Time quantum adalah suatu satuan waktu yg kecil.Jika proses yg sedang dieksekusi selesai dlm waktu kurang dari 1 time quantum, tidak ada masalah. Tetapi jika proses berjalan melebihi 1 time quantum, maka proses tersebut akan dihentikan,lalu digantikan oleh proses yg berikutnya. Proses yg ihentikan tersebut akan diletakkan di queue di urutan paling belakang.(Perhatikan gambar 15-4).Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yg ditentukan terlalu kecil,maka sebagian besar proses tidak akan selesai dlm 1 time quantum.Hal ini tidak baik krn akan terjadi banyak switch, padahal CPU memerlukan waktu unt beralih dari suatu proses ke proses lain (disebut dg context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served. Time quantum yg ideal adalah jika 80% dari total proses memiliki CPU burst time yg lebih kecil dari 1 time quantum.

5. Multilevel Queue


Ide dasar dari algoritma ini adalah berdasarkan pada sistem prioritas proses. Prinsipnya adalah, jika setiap proses dpt dikelompokkan berdasarkan prioritasnya, kemudian muncul ide unt menganggap kelompok-kelompok tersbut sebagai sebuah antrian-antrian kecil yg merupakan bagian dari antrian keseluruhan proses, yg sering disebut dg algoritma multilevel queue.hal ini dpt dilihat bahwa seolah-olah algoritma dg prioritas yg dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dg algoritma FCFS & dpt diketahui bahwa algoritma FCFS memiliki banyak kelemahan, & oleh krn itu maka dlm prakteknya, algoritma multilevel queue memungkinkan
adanya penerapan algoritma internal dlm masing-masing sub- antriannya unt meningkatkan kinerjanya, dimana setiap sub-antrian bisa memiliki algoritma internal yg berbeda.Berawal dari priority scheduling, algoritma ini pun memiliki kelemahan yg sama dg priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dg prioritas rendah bisa saja tidak mendapat jatah CPU. unt mengatasi hal tersebut,salah satu caranya adalah dg memodifikasi algoritma ini dg adanya jatah waktu maksimal unt tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan & digantikan oleh antrian dibawahnya, & tentu saja batas waktu unt tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

6. Multilevel Feedback Queue


Multilevel feedback queue adalah salah satu algoritma yg berdasar pada algoritma mulilevel queue. Perbedaan mendasar yg membedakan multilevel feedback queue dg multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dg prioritas yg lebih rendah ataupun lebih tinggi,

1. Semua proses yg baru datang akan diletakkan pada queue 0 (quantum = 8 ms)
2. Jika suatu proses tidak dpt diselesaikan dlm 8 ms, maka proses tersebut akan dihentikan & dipindahkan ke queue 1 (quantum = 16 ms)
3. Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, & jika suatu proses di queue 1 tidak selesai dlm 16 ms, maka proses tersebut akan dipindahkan ke queue 2 4. Queue 2 akan dikerjakan bila queue 0 & 1 kosong, & akan berjalan dg algoritma FCFS
 
Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dlm hal ini ditentukan oleh time quantum, namun dlm prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dg mendefinisikan terlebih dahulu parameter- parameternya, yaitu:

1. Jumlah antrian
2. Algoritma internal tiap queue
3. Aturan sebuah proses naik ke antrian yg lebih tinggi
4. Aturan sebuah proses turun ke antrian yg lebih rendah
5. Antrian yg akan dimasuki tiap proses yg baru datang.

Berdasarkan hal-hal di atas maka algoritma ini dpt dipakai secara fleksibel & diterapkan sesuai dg kebutuhan sistem.Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yg paling banyak dipakai.


#data diolah dari berbagai sumber

Berikut jenis-jenis algoritma berdasarkan penjadwalan :
Nonpre-emptive, menggunakan konsep :

FIFO (First In First Out) / FCFS (First Come First Serve)
SJF (Shortest Job First)
HRN (Highest Ratio Next)
MFQ (Multiple Feedback Queues)
Pre-emptive, menggunakan konsep :
RR (Round Robin)
SRF (Shortest Remaining First)
PS (Priority Schedulling)
GS (Guaranteed Schedulling)
Algoritma Pre-emptive

A. Round Robin (RR)

Merupakan :

Penjadwalan yg paling tua, sederhana, adil,banyak dipakai algoritmanya & mudah diimplementasikan.
Penjadwalan ini bukan dipreempt oleh proses lain tetapi oleh penjadwal berdasarkan lama waktu berjalannya proses (preempt by time).

Penjadwalan tanpa prioritas.

Berasumsi bahwa semua proses memiliki kepentingan yg sama, sehingga tidak   ada prioritas tertentu.
Semua proses dianggap penting sehingga diberi sejumlah waktu oleh pemroses yg disebut kwanta (quantum) / time slice dimana proses  itu berjalan. Jika proses masih running sampai akhir quantum, maka CPU akan mempreempt proses itu & memberikannya ke proses lain.

Algoritma yg dipakai :

Jika kwanta habis & proses belum selesai, maka proses menjadi runnable & pemroses dialihkan ke proses lain.
Jika kwanta belum habis & proses menunggu suatu kejadian (selesainya operasi I/O), maka proses menjadi blocked & pemroses dialihkan ke proses lain.
Jika kwanta belum habis tetapi proses telah selesai, maka proses diakhiri & pemroses dialihkan ke proses lain.
Diimplementasikan dg :
Mengelola senarai proses ready (runnable) sesuai urutan kedatangan.
proses yg berada di ujung depan antrian menjadi running.
Bila kwanta belum habis & proses selesai, maka ambil proses di ujung depan antrian proses ready.
Jika kwanta habis & proses belum selesai, maka tempatkan proses running ke ekor antrian proses ready & ambil proses di ujung depan antrian proses ready.
Masalah yg timbul adalah menentukan besar kwanta, yaitu :
Kwanta terlalu besar menyebabkan waktu tanggap besar & turn arround time rendah.
Kwanta terlalu kecil menyebabkan peralihan proses terlalu banyak sehingga  menurunkan efisiensi proses.
Penjadwalan ini :
Baik unt sistem interactive-time sharing dimana kebanyakan waktu dipergunakan menunggu kejadian eksternal.
Contoh : text editor, kebanyakan waktu program adalah unt menunggu keyboard, sehingga dpt dijalankan proses-proses lain.
Tidak cocok unt sistem waktu nyata apalagi hard-real-time applications.

B. Priority Schedulling (PS)

Adalah tiap proses diberi prioritas & proses yg berprioritas tertinggi mendapat jatah waktu lebih dulu (running).  Berasumsi bahwa masing-masing proses memiliki prioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yg dimilikinya. Ilustrasi yg dpt memperjelas prioritas tersebut adalah dlm komputer militer, dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayor berprioritas 80, kapten berprioritas 70, letnan berprioritas 60 & seterusnya. dlm UNIX perintah unt mengubah prioritas menggunakan perintah nice.
Pemberian prioritas diberikan secara :
Statis (static priorities)
Berarti prioritas tidak berubah.
Keunggulan :
Mudah diimplementasikan.
Mempunyai overhead relatif kecil.
Kelemahan :
Tidak tanggap terhadap perubahan lingkungan yg mungkin menghendaki  penyesuaian prioritas.
Dinamis (dynamic priorities)
Merupakan mekanisme unt menanggapi perubahan lingkungan sistem   beroperasi. Prioritas awal yg diberikan ke proses mungkin hanya berumur pendek setelah disesuaikan ke nilai yg lebih tepat sesuai lingkungan.
Kelemahan :
Implementasi mekanisme prioritas dinamis lebih kompleks & mempunyai  overhead lebih besar. Overhead in diimbangi dg peningkatan daya     tanggap sistem.
Dalam algoritma berprioritas dinamis dituntun oleh keputusan unt memenuhi kebijaksanaan tertentu yg menjadi tujuan. Layanan yg bagus adalah menset prioritas dg nilai 1/f, dimana f adalah ration kwanta terakhir yg dipakai proses.
Contoh :
Proses yg menggunakan 2 msec kwanta 100 ms, maka prioritasnya50.
Proses yg berjalan selama 50 ms sebelum blocked berprioritas 2.
Proses yg menggunakan seluruh kwanta berprioritas 1.

C. Multiple Feedback Queues (MFQ)

Merupakan :
Penjadwalan berprioritas dinamis.
Penjadwalan ini unt mencegah (mengurangi) banyaknya swapping dg proses-proses yg sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta) lebih banyak dlm satu waktu. Penjadwalan ini juga menghendaki kelas-kelas prioritas bagi proses-proses yg ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya berjalan empat kwanta, & seterusnya.
Ketentuan yg berlaku adalah sebagai berikut  :
Jalankan proses pada kelas tertinggi.
Jika proses menggunakan seluruh kwanta yg dialokasikan, maka diturunkan kelas prioritasnya.
Proses yg masuk unt pertama kali ke sistem langsung diberi kelas tertinggi.
Mekanisme ini mencegah proses yg perlu berjalan lama swapping berkali-kali  dan mencegah proses-proses interaktif yg singkat harus menunggu lama.

D. Shortest Remaining First (SRF)

Merupakan :

Penjadwalan berprioritas dinamis.
Adalah preemptive unt timesharing.
Melengkapi SJF.
Pada SRF, proses dg sisa waktu jalan diestimasi terendah dijalankan, termasuk proses-proses yg baru tiba.
Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai.
Pada SRF, proses yg sedang berjalan (running) dpt diambil alih proses baru dg sisa waktu jalan yg diestimasi lebih rendah.

Kelemahan :

Mempunyai overhead lebih besar dibanding SJF. SRF perlu penyimpanan waktu  layanan yg telah dihabiskan job & kadang-kadang harus menangani peralihan.
Tibanya proses-proses kecil akan segera dijalankan.
Job-job lebih lama berarti dg lama & variasi waktu tunggu lebih lama   dibanding pada SJF.
SRF perlu menyimpan waktu layanan yg telah dihabiskan , menambah overhead.  Secara teoritis, SRF memberi waktu tunggu minimum tetapi krn overhead peralihan, maka pada situasi tertentu SFJ bisa memberi kinerja lebih baik dibanding SRF.

E. Guaranteed Scheduloing (GS)


Penjadwalan ini memberikan janji yg realistis (memberi daya pemroses yg sama) unt membuat & menyesuaikan performance adalah jika ada N pemakai, sehingga setiap proses (pemakai) akan mendapatkan 1/N dari daya pemroses CPU. unt mewujudkannya, sistem harus selalu menyimpan informasi ttg jumlah waktu CPU unt semua proses sejak login & juga berapa lama pemakai sedang login. Kemudian jumlah waktu CPU, yaitu waktu mulai login dibagi dg n, sehingga lebih mudah menghitung rasio waktu CPU. krn jumlah waktu pemroses tiap pemakai dpt diketahui, maka dpt dihitung rasio antara waktu pemroses yg sesungguhnya harus diperoleh, yaitu 1/N waktu pemroses seluruhnya & waktu pemroses yg telah diperuntukkan proses itu.

Rasio 0,5 berarti sebuah proses hanya punya 0,5 dari apa yg waktu CPU miliki & rasio 2,0  berarti sebuah proses hanya punya 2,0 dari apa yg waktu CPU miliki. Algoritma akan menjalankan proses dg rasio paling rendah hingga naik ketingkat lebih tinggi diatas pesaing terdekatnya. Ide sederhana ini dpt diimplementasikan ke sistem real-time  dan memiliki penjadwalan berprioritas dinamis.


ALGORITMA PENJADWALAN CPU

Artikel ini membicarakan ttg penjadwalan proses unt manajemen proses yg mengelola proses-proses yg datang. Penjadwalan proses ini akan menentukan proses mana dulu & berapa lama proses tersebut akan mendapatkan pelayanan dari CPU. Penjadwalan proses dpt dilakukan dg beberapa algoritma penjadwalan, & setiap algoritma memiliki kaunggulannya masing-masing. Algoritma yg dibahas dlm paper ini adalah algoritma penjadwalan Multilevel Queue, Multilevel Feedback Queue & algoritma penjadwalan Guaranteed yg menerapkan strategi preemptive berdasarkan prioritas dinamis.

Penjadwalan CPU dpt bersifat preemptive / nonpreemptive. Pada penjadwalan preemptive, CPU yg dialokasikan ke suatu proses dpt ditarik kembali oleh sistem operasi & dialihkan ke proses lainnya dg kata lain sistem operasi memberhentikan sementara proses yg sedang berjalan unt memberi ruang kepada proses yg prioritasnya lebih tinggi. Sedangkan pada penjadwalan nonpreemptive bersifat sebaliknya, sekali CPU dialokasikan ke sebuah proses, maka proses akan menggunakan CPU tersebut sampai proses melepaskannya krn proses telah terminate / proses beralih ke waiting state.

Selain itu akan dibahas juga algortima penjadwalan Processor Jamak (Multiple Processor Schedulling) sebagai pembanding dg algoritma penjadwalan yg lain dimana pada penjadwalan ini dibutuhkan dua processor dlm melakukan sebuah penjadwalan pada suatu proses. dlm paper ini juga akan dijelaskan kelemahan serta kelebihan masing – masing Algoritma Penjadwalan.

Pendahuluan

Sekarang ini, perkembangan komputer sudah sangat pesat & banyak dipakai dlm bidang kehidupan. Seringkali pengguna komputer hanya menggunakan komputer unt menyelesaikan persoalan yg mereka hadapi tanpa tahu bagaimana computer memprosesnya. Seperti halnya ttg sistem operasi yg merupakan interface antara pengguna dg perangkat keras computer sehingga kita tidak dirumitkan rincian-rincian pengoperasian perangkat keras.

Sistem operasi melakukan beragam tugas, salah satu tugas yg paling penting adalah manajemen proses, dimana mengelola semua proses aktif & mengalokasikan sumber daya ke proses-proses itu sesuai kebijaksanaan yg diambil unt memenuhi sasaran kinerja. unt memutuskan proses yg harus berjalan, kapan & selama berapa lama proses itu berjalan maka diperlukan suatu teknik penjadwalan yg efektif.

Ada berbagai macam teknik penjadwalan proses dg keunggulannya masing-masing & yg dibahas adalah penjadwalan Multilevel Queue, penjadwalan Multilevel Feedback Queue, & penjadwalan Guaranteed yg akan dibandingkan dg teknik penjadwalan yg paling berbeda yaitu penjadwalan Prosessor Jamak (Multiple Processor)

Tujuan penelitian ini adalah membahas & menganalisis lebih rinci ttg penjadwalan Multilevel Queue, Multilevel Feedback Queue, penjadwalan Guaranteed, penjadwalan Prosessor Jamak & perancangan simulasi unt menggambarkan kinerja teknik penjadwalan tersebut seta mengulas beberapa kelemahan & keunggulan masing – masing algoritma penjadwalan.

Landasan Teori

Sebagaimana di ketahui Penjadwalan adalah fungsi dasar dari sistem operasi, semua resource komputer di jadwalkan sebelum dipakai.

Penjadwalan CPU adalah pemilihan proses dari Ready Queue unt dpt di eksekusi. Penjadwalan CPU di dasarkan pada sistem operasi yg menggunakan prinsip Multiprogramming, yaitu beberapa proses berjalan dlm suatu waktu.

Penjadwalan bertugas memutuskan :

a.       Proses yg harus berjalan.
b.      Kapan & selama berapa lama proses itu berjalan.

Dalam penjadwalan proses, ada pertimbangan unt 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 yg ada dlm memori utama (Ready Queue) & mengalokasikan CPU unt mengeksekusinya. Setiap proses dlm ready queue harus mengantri sebelum mendapat giliran eksekusi dlm CPU.

Setelah mempelajari konsep dasar algoritma penjadwalan proses ini, mahasiswa di harapkan akan mampu :
a.       Memahami konsep ttg dasar-dasar penjadwalan pada CPU.
b.      Memahami kriteria apa saja yg di perlukan unt penjadwalan pada CPU.
c.       Memahami beberapa algoritma penjadwalan pada CPU.

Pembahasan

Penjadwalan proses adalah kumpulan kebijasanaan & mekanisme pada sistem operasi berkenaan dg urutan kerja yg dilakukan sistem komputer. Penjadwalan bertugas memutuskan proses yg harus berjalan, kapan, & selama berapa lama proses itu berjalan.

Kriteria – kriteria yg dilakukan unt mengukur & optimasi kinerja penjadwalan antara lain:

1.      Adil (fairness)
2.      Efisiensi
3.      Waktu tanggap (response time)
4.      Turn around time
5.      Through put.

Algoritma Penjadwalan

1.         Multilevel Queue Schedulling

Dari gambar di atas terlihat bahwa akan terjadi pengelompokan proses-proses berdasarkan prioritasnya. dlm hal ini, dpt dilihat bahwa seolah-olah algoritma dg prioritas yg dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dg algoritma First Come First Served (FCFS) yg memiliki banyak kelemahan. Oleh krn itu, dlm prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dlm masing-masing sub-antriannya, yg bisa memiliki algoritma internal yg berbeda unt meningkatkan kinerjanya.

Berawal dari priority scheduling, algoritma ini pun memiliki kelemahan yg sama dg priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dg prioritas rendah bisa saja tidak mendapat jatah CPU. unt mengatasi hal tersebut, salah satu caranya adalah dg memodifikasi algoritma ini dg adanya jatah waktu maksimal unt tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan & digantikan oleh antrian dibawahnya, & tentu saja batas waktu unt tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

2.      Multilevel Feedback Queue Schedulling

Multilevel feedback queue adalah salah satu algoritma yg berdasar pada algoritma multilevel queue. Perbedaan mendasar yg membedakan multilevel feedback queue dg multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dg prioritas yg lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut:

a.      Semua proses yg baru datang akan diletakkan pada queue 0 ( quantum= 8 ms).
b.      Jika suatu proses tidak dpt diselesaikan dlm 8 ms, maka proses tersebut akan dihentikan & dipindahkan ke queue 1 ( quantum= 16 ms).
c.       Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, & jika suatu proses di queue 1 tidak selesai dlm 16 ms, maka proses tersebut akan dipindahkan ke queue 2.
d.      Queue 2 akan dikerjakan bila queue 0 & 1 kosong, & akan berjalan dg algoritma FCFS.

Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dlm hal ini ditentukan oleh time quantum, namun dlm prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dg mendefinisikan terlebih dahulu parameter-parameternya, yaitu:

a.      Jumlah antrian.
b.      Algoritma internal tiap queue.
c.       Aturan sebuah proses naik ke antrian yg lebih tinggi.
d.      Aturan sebuah proses turun ke antrian yg lebih rendah.
e.      Antrian yg akan dimasuki tiap proses yg baru datang.

3.      Guaranteed Schedulling

Algoritma penjadwalan ini memberikan daya pemroses yg sama unt membuat & menyesuaikan kinerja. Algoritma yg memiliki kinerja yg cukup bagus akan menjanjikan kelangsungan yg baik pula. Misalnya ada X pemakai, maka setiap proses / pemakai akan mendapatkan 1/X dari daya pemroses CPU. unt mewujudkannya, system harus selalu menyimpan informasi ttg jumlah waktu CPU unt semua proses sejak login & juga harus selalu menyimpan informasi ttg berapa lama pemakai sedang login.

System harus tahu berapa CPU time unt meyakinkan bahwa setiap pengguna mendapatkan jatah waktu menggunakan CPU sesuai haknya & juga berapa CPU time yg diperlukan oleh setiap proses 1 pengguna serta berapa CPU time yg 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 yg dipakai unt 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 yg diperoleh sampai saat ini (actual) dg CPU tang seharusnya diperoleh (4 ms) dpt 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 yg seharusnya diterima. Pengguna B memiliki rasio 1.5, artinya B mendapatkan 1.5 waktu dari jatah yg seharusnya didapatkan. Algoritma ini menjalankan proses dg rasio yg paling rendah dulu sampai proses tersebut mendapatkan rasio melebihi rasio proses yg sebelumnya mempunyai rasio satu tingkat labih tinggi darinya.

4.      Multiple Processor Schedulling

Untuk mempertinggi kinerja, kehandalan, kemampuan komputasi, paralelisme, & keekonomisan dari suatu sistem, tambahan prosesor dpt diimplementasikan ke dlm sistem tersebut. Sistem seperti ini disebut dg sistem yg bekerja dg banyak prosesor (prosesor jamak / multiprocessor). Seperti halnya pada prosesor tunggal, prosesor jamak juga membutuhkan penjadwalan. Namun pada prosesor jamak, penjadwalannya jauh lebih kompleks daripada prosesor tunggal krn pada prosesor jamak memungkinkan adanya load sharing antar prosesor yg menyebabkan penjadwalan menjadi lebih kompleks namun kemampuan sistem tersebut menjadi lebih baik. Oleh krn itu, kita perlu mempelajari penjadwalan pada prosesor jamak berhubung sistem dg prosesor jamak akan semakin banyak dipakai krn kemampuannya yg lebih baik dari sistem dg prosesor tunggal.

Jenis – jenis Multiple Processor Schedulling

a.       Penjadwalan Mater/Slave

Pendekatan pertama unt penjadwalan prosesor jamak adalah penjadwalan asymmetric multiprocessing / bisa disebut juga sebagai penjadwalan master/slave. Dimana pada metode ini hanya satu prosesor( master) yg menangani semua keputusan penjadwalan, pemrosesan M/K, & aktivitas sistem lainnya & prosesor lainnya ( slave) hanya mengeksekusi proses. Metode ini sederhana krn hanya satu prosesor yg mengakses struktur data sistem & juga mengurangi data sharing. dlm teknik penjadwalan master/slave, satu prosesor menjaga status dari semua proses dlm sistem & menjadwalkan kinerja unt semua prosesor slave. Sebagai contoh, prosesor master memilih proses yg akan dieksekusi, kemudian mencari prosesor yg available, & memberikan instruksi Start processor. Prosesor slave memulai eksekusi pada lokasi memori yg dituju. Saat slave mengalami sebuah kondisi tertentu seperti meminta M/K, prosesor slave memberi interupsi kepada prosesor master & berhenti unt menunggu perintah selanjutnya. Perlu diketahui bahwa prosesor slave yg berbeda dpt ditujukan unt suatu proses yg sama pada waktu yg berbeda.

Gambar 15.1. Multiprogramming dg multiprocessor

Gambar di atas mengilustrasikan perilaku dari multiprocessor yg dipakai unt multiprogramming Beberapa proses terpisah dialokasikan di dlm memori. Ruang alamat proses terdiri dari halaman-halaman sehingga hanya sebagian saja dari proses tersebut yg berada dlm memori pada satu waktu. Hal ini memungkinkan banyak proses dpt aktif dlm sistem.

b.      Penjadwalan Symmetric Multiprocessing (SMP)

Penjadwalan SMP ( Symmetric multiprocessing) adalah pendekatan kedua unt penjadwalan prosesor jamak. Dimana setiap prosesor menjadwalkan dirinya sendiri ( self scheduling). Semua proses mungkin berada pada antrian ready yg biasa, / mungkin setiap prosesor memiliki antrian ready tersendiri. Bagaimanapun juga, penjadwalan terlaksana dg menjadwalkan setiap prosesor unt memeriksa antrian ready & memilih suatu proses unt dieksekusi. Jika suatu sistem prosesor jamak mencoba unt mengakses & meng- update suatu struktur data, penjadwal dari prosesor-prosesor tersebut harus diprogram dg hati-hati; kita harus yakin bahwa dua prosesor tidak memilih proses yg sama & proses tersebut tidak hilang dari antrian. Secara virtual, semua sistem operasi modern mendukung SMP, termasuk Windows XP, Windows 2000, Solaris, Linux, & Mac OS X.

c.       Affinity

Data yg paling sering diakses oleh beberapa proses akan memadati cache pada prosesor,sehingga akses memori yg sukses biasanya terjadi di memori cache. Namun, jika suatu proses . berpindah dari satu prosesor ke prosesor lainnya akan mengakibatkan isi dari cache memori yg dituju menjadi tidak valid, sedangkan cache memori dari prosesor asal harus disusun kembali populasi datanya. krn mahalnya invalidating & re-populating dari cache, kebanyakan sistem SMP mencoba unt mencegah migrasi proses antar prosesor sehingga menjaga proses tersebut unt berjalan di prosesor yg sama. Hal ini disebut afinitas prosesor ( processor affinity). Ada dua jenis afinitas prosesor, yakni:
·         Soft affinity yg memungkinkan proses berpindah dari satu prosesor ke prosesor yg lain, dan
·         Hard affinity yg menjamin bahwa suatu proses akan berjalan pada prosesor yg sama & tidak berpindah. Contoh sistem yg menyediakan system calls yg mendukung hard affinity adalah Linux.

d.      Load Balancing

Dalam sistem SMP, sangat penting unt menjaga keseimbangan workload antara semua prosesor unt memaksimalkan keuntungan memiliki multiprocessor. Jika tidak, mungkin satu / lebih prosesor idle disaat prosesor lain harus bekerja keras dg workload yg tinggi. Load balancing adalah usaha unt menjaga workload terdistribusi sama rata unt semua prosesor dlm sistem SMP. Perlu diperhatikan bahwa load balancing hanya perlu dilakukan pada sistem dimana setiap prosesor memiliki antrian tersendiri( private queue) unt proses-proses yg berstatus ready. Pada sistem dg antrian yg biasa ( common queue), load balancing tidak diperlukan krn sekali prosesor menjadi idle, prosesor tersebut segera mengerjakan proses yg dpt 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 yg secara berkala memeriksa load dari tiap-tiap prosesor. Jika terdapat ketidakseimbangan, maka dilakukan perataan dg memindahkan( pushing) proses dari yg kelebihan muatan ke prosesor yg idle / yg memiliki muatan lebih sedikit.
·         Pull migration, kondisi ini terjadi saat prosesor yg idle menarik( pulling) proses yg sedang menunggu dari prosesor yg sibuk.
Kedua pendekatan tersebut tidak harus mutually exclusive & dlm kenyataannya sering diimplementasikan secara paralel pada sistem load-balancing.
Keuntungan dari affinity berlawanan dg keuntungan dari load balancing, yaitu keuntungan menjaga suatu proses berjalan pada satu prosesor yg sama dimana proses dpt memanfaatkan data yg sudah ada pada memori cache prosesor tersebut berkebalikan dg keuntungan menarik / memindahkan proses dari satu prosesor ke prosesor lain. dlm kasus system engineering, tidak ada aturan tetap keuntungan yg mana yg lebih baik. Walaupun pada beberapa sistem, prosesor idle selalu menarik proses dari prosesor non-idle sedangkan pada sistem yg lain, proses dipindahkan hanya jika terjadi ketidakseimbangan yg besar antara prosesor.

e.      Symetric Multithreading

Ide dari SMT adalah unt menciptakan banyak logical processor dlm suatu physical processor yg sama & mempresentasikan beberapa prosesor kepada sistem operasi. Setiap logical processor mempunyai state arsitekturnya sendiri yg mencangkup general purpose & machine state register. Lebih jauh lagi, setiap logical prosesor bertanggung jawab pada penanganan interupsinya sendiri, yg berarti bahwa interupsi cenderung dikirimkan ke logical processor & ditangani oleh logical processor bukan physical processor. dg kata lain, setiap logical processor men- share resource dari physical processor-nya, seperti chace & bus.

Gambar 15.2. Symetric Multithreading

Gambar di atas mengilustrasikan suatu tipe arsitektur SMT dg dua physical processor dg masing-masing punya dua logical processor. Dari sudut pandang sistem operasi, pada sistem ini terdapat empat prosesor. Perlu diketahui bahwa SMT adalah fitur yg disediakan dlm 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 yg diharapkan tidak selalu terjadi pada sistem operasi yg berjalan pada SMT. Misalnya, suatu sistem memiliki 2 physical processor, keduanya idle, penjadwal pertama kali akan lebih memilih unt membagi thread ke physical processor daripada membaginya ke logical processor dlm physical processor yg sama, sehingga logical processor pada satu physical processor bisa menjadi sibuk sedangkan physical processor yg lain menjadi idle.

f.        Multicore Multiprocessor

Multicore microprocessor adalah kombinasi dua / lebih prosesor independen kedalam sebuah integrated circuit(IC). Umumnya, multicore mengizinkan perangkat komputasi unt 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 yg dipakai dlm sistem pembagian memori terdistribusi & multiprocessor yg ditujukan unt mendapatkan koherensi pada cache. Hal ini dikarenakan sinyal antara CPU yg berbeda mengalir pada jarak yg lebih dekat, sehingga kekuatan sinyal hanya berkurang sedikit. Sinyal dg kualitas baik ini memungkinkan lebih banyak data yg dikirimkan dlm satu periode waktu & tidak perlu sering di- repeat.
·         Secara fisik, desain CPU multicore menggunakan ruang yg lebih kecil pada PCB ( Printed Circuit Board) dibanding dg desain multichip SMP.
·         Prosesor dual-core menggunakan sumber daya lebih kecil dibanding sepasang prosesor dual-core.
·         Desain multicore memiliki resiko design error yg lebih rendah daripada desain single-core.
Kerugian:
·         dlm hal sistem operasi, butuh penyesuaian kepada software yg ada unt memaksimalkan kegunaan dari sumberdaya komputasi yg disediakan oleh prosesor multicore. Kemampuan prosesor multicore unt meningkatkan performa aplikasi juga bergantung pada penggunaan banyaknya thread dlm 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 krn semakin sulitnya pengaturan suhu pada chip yg 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

1. First-Come, First-Served Scheduling (FCFS)


Algoritma ini merupakan algoritma penjadwalan yg paling sederhana yg dipakai CPU. dg menggunakan algoritma ini seiap proses yg berada pada status ready dimasukkan ke dlm FIFO queue sesuai dg waktu kedatangannya. Proses yg tiba terlebih dahulu yg akan dieksekusi.

contoh:

Ada 3 buah proses yg 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 & turnaround time (burst time + waiting time) dari ketiga proses tersebut dg menggunakan algoritma FCFS.

Waiting time unt p1 adalah 0 ms (p1 tidak perlu menunggu),sedangkan unt p2 adalah sebesar 24 ms (menunggu p1 selesai) & unt p3 sebesar 29 ms (menunggu p1 & p2 selesai). Waiting time rata-ratanya adalah sebesar (0+24+29)/3 = 17,6 ms.
Turnaround time unt p1 sebesar 24 ms, sedangkan unt p2 sebesar 29 ms (dihitung dari awal kedatangan p2 hingga selesai dieksekusi),untuk p3 sebesar 32 ms. Turnaround time rata-rata unt ketiga proses tersebut adalah (24+29+32)/3 = 28,3 ms.

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 yg sedang dieksekusi oleh CPU

Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yg sedang dieksekusi oleh CPU tidak dpt di-interrupt oleh proses yg lain.

 2. Shortest-Job-First-Scheduling (SJF)  

Algoritma ini mempunyai cara penjadwalan yg berbeda dg FCFS.Dengan algoritma ini maka setiap proses yg ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yg pendek unt setiap proses & krn hal tersebut maka waiting time rata-ratanya juga menjadi pendek,sehingga dpt dikatakan bahwa algoritma ini adalah algoritma yg optimal.

Ada beberapa kekurangan dari algoritma ini yaitu:
1. Susahnya unt memprediksi burst time proses yg akan dieksekusi selanjutnya
2. Proses yg mempunyai burst time yg besar akan memiliki waiting time yg besar pula krn yg dieksekusi terlebih dahulu adalah proses dg burst time yg lebih kecil

Algoritma ini dpt dibagi menjadi 2 bagian yaitu:

1. Preemptive

Jika ada proses yg sedang dieksekusi oleh CPU & terdapat proses di ready queue dg burst time yg lebih kecil daripada proses yg sedang dieksekusi tersebut, maka proses yg sedang dieksekusi oleh CPU akan digantikan oleh proses yg berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining-Time-First scheduling.

2. Non-preemptive

CPU tidak memperbolehkan proses yg ada di ready queue unt menggeser proses yg sedang dieksekusi oleh CPU meskipun proses yg baru tersebut mempunyai burst time yg lebih kecil.

Contoh:

Ada 3 buah proses yg datang berurutan yaitu p1 dg arrival time pada 0 ms dg burst time 4 ms, p2 dg arrival time pada 0 ms dg burst time 5 ms, p3 dg arrival time pada 1 ms dg burst time 2 ms. Hitunglah waiting time rata-rata & turnaround time dari ketiga proses tersebut dg mengunakan algoritma SJF.

Waiting time rata-rata unt ketiga proses tersebut adalah sebesar ((3-1)+(6-0)+(1-1))/3 = 2,6 ms. Turnaround time dari ketiga proses tersebut adalah sebesar (6+11+(3-1))/3 = 6,3 ms.

Waiting time rata-rata unt ketiga prses tersebut adalah sebesar (0+6+(4-1))/3 = 3 ms Turnaround time dari ketiga proses tersebut adalah sebesar (4+11+(6-1))/3 = 6,6 ms


3. Priority Scheduling


Priority Scheduling merupakan algoritma penjadwalan yg mendahulukan proses yg memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing.
Prioritas suatu proses dpt ditentukan melalui beberapa karakteristik antara lain:

1. Time limit
2. Memory requirement
3. Akses file
4. Perbandingan antara I/O Burst dg CPU Burst
5. Tingkat kepentingan proses

Priority Scheduling juga dpt dijalankan secara preemptive maupun non-preemptive.
Pada preemptive, jika ada suatu proses yg baru datang memiliki prioritas yg lebih tinggi daripada proses yg sedang dijalankan, maka proses yg sedang berjalan tersebut dihentikan, lalu CPU dialihkan unt proses yg baru datang tersebut.Sementara itu, pada non-preemptive, proses yg baru datang tidak dpt menganggu proses yg sedang berjalan, tetapi hanya diletakkan di depan queue. Kelemahan pada priority scheduling adalah dpt terjadinya indefinite blocking (starvation). Suatu proses dg prioritas yg rendah memiliki kemungkinan unt tidak dieksekusi jika terdapat proses lain yg memiliki prioritas lebih tinggi darinya.Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yg menunggu dlm queue secara bertahap.

Contoh:

Setiap 10 menit, prioritas dari masing-masing proses yangmenunggu dlm queue dinaikkan satu tingkat.Maka, suatu proses yg memiliki prioritas 127, setidaknya dalam21 jam 20 menit, proses tersebut akan memiliki prioritas 0,yaitu prioritas yg tertinggi. (semakin kecil angka menunjukkanbahwa prioritasnya semakin tinggi)

4. Round Robin


Algoritma penjadwalan ini mirip dg algoritma First Come FirstServed, tetapi proses ini memberi suatu batasan waktu unt setiap proses yg disebut dg time quantum. Time quantum adalah suatu satuan waktu yg kecil.Jika proses yg sedang dieksekusi selesai dlm waktu kurang dari 1 time quantum, tidak ada masalah. Tetapi jika proses berjalan melebihi 1 time quantum, maka proses tersebut akan dihentikan,lalu digantikan oleh proses yg berikutnya. Proses yg ihentikan tersebut akan diletakkan di queue di urutan paling belakang.(Perhatikan gambar 15-4).Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yg ditentukan terlalu kecil,maka sebagian besar proses tidak akan selesai dlm 1 time quantum.Hal ini tidak baik krn akan terjadi banyak switch, padahal CPU memerlukan waktu unt beralih dari suatu proses ke proses lain (disebut dg context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served. Time quantum yg ideal adalah jika 80% dari total proses memiliki CPU burst time yg lebih kecil dari 1 time quantum.

5. Multilevel Queue


Ide dasar dari algoritma ini adalah berdasarkan pada sistem prioritas proses. Prinsipnya adalah, jika setiap proses dpt dikelompokkan berdasarkan prioritasnya, kemudian muncul ide unt menganggap kelompok-kelompok tersbut sebagai sebuah antrian-antrian kecil yg merupakan bagian dari antrian keseluruhan proses, yg sering disebut dg algoritma multilevel queue.hal ini dpt dilihat bahwa seolah-olah algoritma dg prioritas yg dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dg algoritma FCFS & dpt diketahui bahwa algoritma FCFS memiliki banyak kelemahan, & oleh krn itu maka dlm prakteknya, algoritma multilevel queue memungkinkan
adanya penerapan algoritma internal dlm masing-masing sub- antriannya unt meningkatkan kinerjanya, dimana setiap sub-antrian bisa memiliki algoritma internal yg berbeda.Berawal dari priority scheduling, algoritma ini pun memiliki kelemahan yg sama dg priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dg prioritas rendah bisa saja tidak mendapat jatah CPU. unt mengatasi hal tersebut,salah satu caranya adalah dg memodifikasi algoritma ini dg adanya jatah waktu maksimal unt tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan & digantikan oleh antrian dibawahnya, & tentu saja batas waktu unt tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

6. Multilevel Feedback Queue


Multilevel feedback queue adalah salah satu algoritma yg berdasar pada algoritma mulilevel queue. Perbedaan mendasar yg membedakan multilevel feedback queue dg multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dg prioritas yg lebih rendah ataupun lebih tinggi,

1. Semua proses yg baru datang akan diletakkan pada queue 0 (quantum = 8 ms)
2. Jika suatu proses tidak dpt diselesaikan dlm 8 ms, maka proses tersebut akan dihentikan & dipindahkan ke queue 1 (quantum = 16 ms)
3. Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, & jika suatu proses di queue 1 tidak selesai dlm 16 ms, maka proses tersebut akan dipindahkan ke queue 2 4. Queue 2 akan dikerjakan bila queue 0 & 1 kosong, & akan berjalan dg algoritma FCFS
 
Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dlm hal ini ditentukan oleh time quantum, namun dlm prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dg mendefinisikan terlebih dahulu parameter- parameternya, yaitu:

1. Jumlah antrian
2. Algoritma internal tiap queue
3. Aturan sebuah proses naik ke antrian yg lebih tinggi
4. Aturan sebuah proses turun ke antrian yg lebih rendah
5. Antrian yg akan dimasuki tiap proses yg baru datang.

Berdasarkan hal-hal di atas maka algoritma ini dpt dipakai secara fleksibel & diterapkan sesuai dg kebutuhan sistem.Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yg paling banyak dipakai.


#data diolah dari berbagai sumber

Berikut jenis-jenis algoritma berdasarkan penjadwalan :
Nonpre-emptive, menggunakan konsep :

FIFO (First In First Out) / FCFS (First Come First Serve)
SJF (Shortest Job First)
HRN (Highest Ratio Next)
MFQ (Multiple Feedback Queues)
Pre-emptive, menggunakan konsep :
RR (Round Robin)
SRF (Shortest Remaining First)
PS (Priority Schedulling)
GS (Guaranteed Schedulling)
Algoritma Pre-emptive

A. Round Robin (RR)

Merupakan :

Penjadwalan yg paling tua, sederhana, adil,banyak dipakai algoritmanya & mudah diimplementasikan.
Penjadwalan ini bukan dipreempt oleh proses lain tetapi oleh penjadwal berdasarkan lama waktu berjalannya proses (preempt by time).

Penjadwalan tanpa prioritas.

Berasumsi bahwa semua proses memiliki kepentingan yg sama, sehingga tidak   ada prioritas tertentu.
Semua proses dianggap penting sehingga diberi sejumlah waktu oleh pemroses yg disebut kwanta (quantum) / time slice dimana proses  itu berjalan. Jika proses masih running sampai akhir quantum, maka CPU akan mempreempt proses itu & memberikannya ke proses lain.

Algoritma yg dipakai :

Jika kwanta habis & proses belum selesai, maka proses menjadi runnable & pemroses dialihkan ke proses lain.
Jika kwanta belum habis & proses menunggu suatu kejadian (selesainya operasi I/O), maka proses menjadi blocked & pemroses dialihkan ke proses lain.
Jika kwanta belum habis tetapi proses telah selesai, maka proses diakhiri & pemroses dialihkan ke proses lain.
Diimplementasikan dg :
Mengelola senarai proses ready (runnable) sesuai urutan kedatangan.
proses yg berada di ujung depan antrian menjadi running.
Bila kwanta belum habis & proses selesai, maka ambil proses di ujung depan antrian proses ready.
Jika kwanta habis & proses belum selesai, maka tempatkan proses running ke ekor antrian proses ready & ambil proses di ujung depan antrian proses ready.
Masalah yg timbul adalah menentukan besar kwanta, yaitu :
Kwanta terlalu besar menyebabkan waktu tanggap besar & turn arround time rendah.
Kwanta terlalu kecil menyebabkan peralihan proses terlalu banyak sehingga  menurunkan efisiensi proses.
Penjadwalan ini :
Baik unt sistem interactive-time sharing dimana kebanyakan waktu dipergunakan menunggu kejadian eksternal.
Contoh : text editor, kebanyakan waktu program adalah unt menunggu keyboard, sehingga dpt dijalankan proses-proses lain.
Tidak cocok unt sistem waktu nyata apalagi hard-real-time applications.

B. Priority Schedulling (PS)

Adalah tiap proses diberi prioritas & proses yg berprioritas tertinggi mendapat jatah waktu lebih dulu (running).  Berasumsi bahwa masing-masing proses memiliki prioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yg dimilikinya. Ilustrasi yg dpt memperjelas prioritas tersebut adalah dlm komputer militer, dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayor berprioritas 80, kapten berprioritas 70, letnan berprioritas 60 & seterusnya. dlm UNIX perintah unt mengubah prioritas menggunakan perintah nice.
Pemberian prioritas diberikan secara :
Statis (static priorities)
Berarti prioritas tidak berubah.
Keunggulan :
Mudah diimplementasikan.
Mempunyai overhead relatif kecil.
Kelemahan :
Tidak tanggap terhadap perubahan lingkungan yg mungkin menghendaki  penyesuaian prioritas.
Dinamis (dynamic priorities)
Merupakan mekanisme unt menanggapi perubahan lingkungan sistem   beroperasi. Prioritas awal yg diberikan ke proses mungkin hanya berumur pendek setelah disesuaikan ke nilai yg lebih tepat sesuai lingkungan.
Kelemahan :
Implementasi mekanisme prioritas dinamis lebih kompleks & mempunyai  overhead lebih besar. Overhead in diimbangi dg peningkatan daya     tanggap sistem.
Dalam algoritma berprioritas dinamis dituntun oleh keputusan unt memenuhi kebijaksanaan tertentu yg menjadi tujuan. Layanan yg bagus adalah menset prioritas dg nilai 1/f, dimana f adalah ration kwanta terakhir yg dipakai proses.
Contoh :
Proses yg menggunakan 2 msec kwanta 100 ms, maka prioritasnya50.
Proses yg berjalan selama 50 ms sebelum blocked berprioritas 2.
Proses yg menggunakan seluruh kwanta berprioritas 1.

C. Multiple Feedback Queues (MFQ)

Merupakan :
Penjadwalan berprioritas dinamis.
Penjadwalan ini unt mencegah (mengurangi) banyaknya swapping dg proses-proses yg sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta) lebih banyak dlm satu waktu. Penjadwalan ini juga menghendaki kelas-kelas prioritas bagi proses-proses yg ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya berjalan empat kwanta, & seterusnya.
Ketentuan yg berlaku adalah sebagai berikut  :
Jalankan proses pada kelas tertinggi.
Jika proses menggunakan seluruh kwanta yg dialokasikan, maka diturunkan kelas prioritasnya.
Proses yg masuk unt pertama kali ke sistem langsung diberi kelas tertinggi.
Mekanisme ini mencegah proses yg perlu berjalan lama swapping berkali-kali  dan mencegah proses-proses interaktif yg singkat harus menunggu lama.

D. Shortest Remaining First (SRF)

Merupakan :

Penjadwalan berprioritas dinamis.
Adalah preemptive unt timesharing.
Melengkapi SJF.
Pada SRF, proses dg sisa waktu jalan diestimasi terendah dijalankan, termasuk proses-proses yg baru tiba.
Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai.
Pada SRF, proses yg sedang berjalan (running) dpt diambil alih proses baru dg sisa waktu jalan yg diestimasi lebih rendah.

Kelemahan :

Mempunyai overhead lebih besar dibanding SJF. SRF perlu penyimpanan waktu  layanan yg telah dihabiskan job & kadang-kadang harus menangani peralihan.
Tibanya proses-proses kecil akan segera dijalankan.
Job-job lebih lama berarti dg lama & variasi waktu tunggu lebih lama   dibanding pada SJF.
SRF perlu menyimpan waktu layanan yg telah dihabiskan , menambah overhead.  Secara teoritis, SRF memberi waktu tunggu minimum tetapi krn overhead peralihan, maka pada situasi tertentu SFJ bisa memberi kinerja lebih baik dibanding SRF.

E. Guaranteed Scheduloing (GS)


Penjadwalan ini memberikan janji yg realistis (memberi daya pemroses yg sama) unt membuat & menyesuaikan performance adalah jika ada N pemakai, sehingga setiap proses (pemakai) akan mendapatkan 1/N dari daya pemroses CPU. unt mewujudkannya, sistem harus selalu menyimpan informasi ttg jumlah waktu CPU unt semua proses sejak login & juga berapa lama pemakai sedang login. Kemudian jumlah waktu CPU, yaitu waktu mulai login dibagi dg n, sehingga lebih mudah menghitung rasio waktu CPU. krn jumlah waktu pemroses tiap pemakai dpt diketahui, maka dpt dihitung rasio antara waktu pemroses yg sesungguhnya harus diperoleh, yaitu 1/N waktu pemroses seluruhnya & waktu pemroses yg telah diperuntukkan proses itu.

Rasio 0,5 berarti sebuah proses hanya punya 0,5 dari apa yg waktu CPU miliki & rasio 2,0  berarti sebuah proses hanya punya 2,0 dari apa yg waktu CPU miliki. Algoritma akan menjalankan proses dg rasio paling rendah hingga naik ketingkat lebih tinggi diatas pesaing terdekatnya. Ide sederhana ini dpt diimplementasikan ke sistem real-time  dan memiliki penjadwalan berprioritas dinamis.

Contoh Program Algoritma Penjadwalan CPU

Source Code Algoritma Penjadwalan CPU

Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman

Tutorial belajar Algoritma Penjadwalan CPU

VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic

Gratis download Algoritma Penjadwalan CPU

Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow

Penerapan implementasi Algoritma Penjadwalan CPU Algoritma Penjadwalan CPU

Posted by: Project-G Contoh Program Algoritma Penjadwalan CPU Updated at : 05.55
Jika Anda perlu source code terkait dengan artikel di atas atau ada yang ingin di tanyakan anda bisa melakukan konsultasi gratis kepada kami, melalui form di bawah. Hasil konsultasi akan di kirimkan ke email Anda. Kami mohon supportnya dengan mengklik beberapa tombol berikut :


Contoh Program Algoritma Penjadwalan CPU

perhatian

Informasi Penting Untuk Mahasiswa !

Kami menawarkan layanan jasa konsultan bimbingan pembuatan program untuk Tesis Skripsi dan Tugas Akhir Informatika, Komputer, Elektro dan Teknik lainnya yang bidang minatnya mengarah ke teknologi informasi. BASED PROJECT :Mobile Development (Java, Adobe, AS3, Android, BB, iOS, WPhone dll), Web & Desktop Development (.Net, C#, MATLAB, PHP, Delphi, Visual Basic dll). BONUS : Di bimbing untuk penguasaan materi dan coding dan revisi.
detail
Label: ,
Konsultasi gratis