Metode & Algoritma | List Tutorials | Source Code | About | Sitemap
Konsultan Tesis
Bimbingan dan Konsultasi Tesis Informatika bersama team Project Graduate Indonesia. Konsultasi hanya untuk yang sudah me-Like FB kami (Silahkan LIKE tombol ini jika belum).
. Scroll kebawah untuk memasukan kode AntiSpam Protection. Hasil konsultasi akan kami kirimkan ke email Anda.

ALGORITMA PENJADWALAN




.


Metode dan Algoritma | ALGORITMA PENJADWALAN . Anda bisa melakukan konsultasi tentang ALGORITMA PENJADWALAN melalui form di samping kanan !!!

Artikel 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.

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.

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.

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.

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

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

 
Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini seiap proses yang berada pada status ready dimasukkan ke dalam FIFO queue sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.

contoh:

Ada 3 buah proses yang datang secara bersamaan yaitu pada 0 ms,P1 memiliki burst time 24 ms, P2 memiliki burst time 5 ms, P3 memiliki burst time 3 ms. Hitunglah wating time rata-rata dan turnaround time (burst time + waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS.

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

Kelemahan dari algoritma ini:

1. Waiting time rata-ratanya cukup lama
2. Terjadinya convoy effect, yaitu proses-proses menunggu lama
untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU

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

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

Algoritma ini mempunyai cara penjadwalan yang berbeda dengan FCFS.Dengan algoritma ini maka setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek,sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.

Ada beberapa kekurangan dari algoritma ini yaitu:
1. Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya
2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil

Algoritma ini dapat dibagi menjadi 2 bagian yaitu:

1. Preemptive

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

2. Non-preemptive

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

Contoh:

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

Waiting time rata-rata untuk 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 untuk 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 yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing.
Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain:

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

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

Contoh:

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

4. Round Robin


Algoritma penjadwalan ini mirip dengan algoritma First Come FirstServed, tetapi proses ini memberi suatu batasan waktu untuk setiap proses yang disebut dengan time quantum. Time quantum adalah suatu satuan waktu yang kecil.Jika proses yang sedang dieksekusi selesai dalam 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 yang berikutnya. Proses yang 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 yang ditentukan terlalu kecil,maka sebagian besar proses tidak akan selesai dalam 1 time quantum.Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

5. Multilevel Queue


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

6. Multilevel Feedback Queue


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

1. Semua proses yang baru datang akan diletakkan pada queue 0 (quantum = 8 ms)
2. Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke queue 1 (quantum = 16 ms)
3. 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 4. 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:

1. Jumlah antrian
2. Algoritma internal tiap queue
3. Aturan sebuah proses naik ke antrian yang lebih tinggi
4. Aturan sebuah proses turun ke antrian yang lebih rendah
5. Antrian yang akan dimasuki tiap proses yang baru datang.
 
Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem.Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.


#data diolah dari berbagai sumber

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

FIFO (First In First Out) atau 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 yang paling tua, sederhana, adil,banyak digunakan algoritmanya dan 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 yang sama, sehingga tidak   ada prioritas tertentu.
Semua proses dianggap penting sehingga diberi sejumlah waktu oleh pemroses yang disebut kwanta (quantum) atau time slice dimana proses  itu berjalan. Jika proses masih running sampai akhir quantum, maka CPU akan mempreempt proses itu dan memberikannya ke proses lain.

Algoritma yang digunakan :

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

B. Priority Schedulling (PS)

Adalah tiap proses diberi prioritas dan proses yang berprioritas tertinggi mendapat jatah waktu lebih dulu (running).  Berasumsi bahwa masing-masing proses memiliki prioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yang dimilikinya. Ilustrasi yang dapat memperjelas prioritas tersebut adalah dalam komputer militer, dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayor berprioritas 80, kapten berprioritas 70, letnan berprioritas 60 dan seterusnya. Dalam UNIX perintah untuk 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 yang mungkin menghendaki  penyesuaian prioritas.
Dinamis (dynamic priorities)
Merupakan mekanisme untuk menanggapi perubahan lingkungan sistem   beroperasi. Prioritas awal yang diberikan ke proses mungkin hanya berumur pendek setelah disesuaikan ke nilai yang lebih tepat sesuai lingkungan.
Kelemahan :
Implementasi mekanisme prioritas dinamis lebih kompleks dan mempunyai  overhead lebih besar. Overhead in diimbangi dengan peningkatan daya     tanggap sistem.
Dalam algoritma berprioritas dinamis dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu yang menjadi tujuan. Layanan yang bagus adalah menset prioritas dengan nilai 1/f, dimana f adalah ration kwanta terakhir yang digunakan proses.
Contoh :
Proses yang menggunakan 2 msec kwanta 100 ms, maka prioritasnya50.
Proses yang berjalan selama 50 ms sebelum blocked berprioritas 2.
Proses yang menggunakan seluruh kwanta berprioritas 1.

C. Multiple Feedback Queues (MFQ)

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

D. Shortest Remaining First (SRF)

Merupakan :

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

Kelemahan :

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

E. Guaranteed Scheduloing (GS)


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

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




Source Code ActionScript AS3 ASP.NET AJAX C / C++ C# Clipper COBOL ColdFusion DataFlex Delphi Emacs Lisp Fortran FoxPro Java J2ME JavaScript JScript Lingo MATLAB Perl PHP PostScript Python SQL VBScript Visual Basic 6.0 Visual Basic .NET Flash MySQL Oracle Android
Related Post :


Project-G
Judul: ALGORITMA PENJADWALAN
Rating: 100% based on 99998 ratings. 5 user reviews.
Ditulis Oleh hank2

Anda sedang membaca artikel tentang ALGORITMA PENJADWALAN, Semoga artikel tentang ALGORITMA PENJADWALAN ini sangat bermanfaat bagi teman-teman semua, jangan lupa untuk mengunjungi lagi melalui link ALGORITMA PENJADWALAN.


Posted by: Metode Algoritma Updated at: 05.55

Label

3 Variabel Adaptive Resonance Theory Algorirma RSA Algoritma Algoritma Clonal Selection Algoritma Djikstra Android ANN Annaeling Aritmetika Modulo ART Artificial Neural Network Backpropagation Biometrik Blowfish Brute Force Buble Sort Business Process Management C++ C-Means Caesar Cipher CISM Contoh Contoh Kode Contoh Penerapan contoh program Contoh Soal Corporate Information System Management CRC Cyclic Redundancy Code Deteksi Wajah Dijkstra Djikstra Eigenface Enterprise Resource Planning ERP Expectation Maximization Face Detection Face Extractor Face Recognition Facebook FCFS FCM Filterbank First Come First Server Fisherface FP-Growth Fuzzy ART Fuzzy C-Means Gaussian Generate & Test Genetika greedy Green Computing Huffman image processing Implementasi Information System Risk Management iOS 5 Iris Recognition IS Strategic Planning Jaringan Jaringan Saraf Tiruan jaringan syaraf tiruan Jasa Pembuatan Tesis Skripsi TA Informatika Komputer Java JST K-means knowledge management konsultan tesis informatika kriptografi Kruskal Kruskall Linear Programming list judul informatika LOKI LOOK Low Bit Coding LSB Manajamen Proses Bisnis Manajemen Perubahan MANET Masalah Rute Kendaraan Mass Transport Vehicle Routing Problem Metode Grafik metode LSB Minimum Spanning Tree mobile Mobile Ad hoc Network MTVRP negascout Online Learning Open Shortest Path First OpenCV OSPF PCA Pemrograman Linear Pencarian Akar Pencarian Linear Pencocokan Pengenalan Iris Mata Pengenalan Suara Pengenalan Wajah Pengolahan Citra Pengolahan Citra Digital Pengukuran Garis-Garis Telapak Tangan Penjadwalan Persamaan Linier Pewarnaan Graf Pewarnaan Graph Prim Project and Change Management Quantum Random Waypoint real time tracking Recognition Recursive Large First RLF RMSE Root Mean square Error RSA RWP Sandi Sidik Jari Simulated Annaeling SISP Sistem Verifikasi Biometrik skripsi sorting Source Code Spanning Tree Speech Speech Recognition Steganography Strategic Information Systems Planning Stream Cipher Technopreneurship Traveling Salesman Problem Travelling Salesman problem Tree TSP Voice Recognition Watermaking Web Service Welch dan Powell