Non-preemptive. CPU tidak memperbolehkan proses yang ada di antrian ready untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil. Misalnya ada empat buah proses dengan masing-masing waktu kedatangan burst time di jelaskan pada tabel di bawah ini. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF.
Proses Arrival time Burst Time :
P1 0 ms 7 ms
P2 2 ms 4 ms
P3 4 ms 1 ms
P4 5 ms 4 ms
1. Preemptive. Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di antrian ready dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di antrian ready tersebut. Preemptive SJF sering disebut juga Shortest-Remaining-Time-First scheduling.
Solusi Preemptive:
Rata-rata waiting time adalah (9 + 1 + 0 +2)/4 = 3, dimana :
P1: (0-0+11-2) = 9
P2: (2-2+5-4) = 1
P3: (4-4) = 0
P4: (7-5) = 2
Rata-rata turnaround time adalah ((9+7)+(1+4)+(0+1)+(4+2))/4 = 7
1. FIRST-COME FIRST-SERVED (FCFS)
Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini seiap proses yang berada pada status ready dimasukkan ke dalam antrian FIFO sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi terlebih dahulu.
Misalnya ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki burst time 24 ms, P2 memiliki burst time 5 ms, P3 memiliki burst time 3 ms. Hitunglah wating time rata-rata dan turnaround time (burst time + waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS.
Proses Burst time
P1 24 ms
P2 5 ms
P3 3 ms
Waiting time untuk p1 adalah 0 ms (P1 tidak perlu menunggu), sedangkan untuk p2 adalah sebesar 24 ms (menunggu P1 selesai) dan untuk p3 sebesar 29 ms (menunggu P1 dan P2 selesai). Waiting time rata-ratanya adalah sebesar (0+24+29)/3 = 17,6 ms.
Turnaround time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 29 ms (dihitung dari awal kedatangan P2 hingga selesai dieksekusi), untuk p3 sebesar 32 ms. Turnaround time rata-rata untuk ketiga proses tersebut adalah (24+29+32)/3 = 28,3 ms.
Kelemahan dari algoritma ini:
a. Waiting time rata-ratanya cukup lama.
b. Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu satu proses besar
yang sedang dieksekusi oleh CPU.
Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.
2. SHORTEST-JOB FIRST (SJF)
Algoritma ini mempunyai cara penjadwalan yang berbeda dengan FCFS. Dengan algoritma ini maka setiap proses yang ada di antrian ready akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.
Ada beberapa kekurangan dari algoritma ini yaitu:
• Kesulitan untuk memprediksi burst time proses yang akan dieksekusi selanjutnya .
• 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.
3. HIGHEST RATIO NEXT (HRN)
Merupakan :
· Penjadwalan berprioritas dinamis.
· Penjadwalan untuk mengoreksi kelemahan SJF.
· Adalah strategi penjadwalan dengan prioritas proses tidak hanya merupakan fungsi waktu layanan tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, proses berjalan sampai selesai.
Prioritas dinamis HRN dihitung berdasarkan rumus :
Prioritas = (waktu tunggu + waktu layanan ) / waktu layanan
Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek berprioritas lebih baik, karena waktu tunggu sebagai pembilang maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus.
Disebut HRN, karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani.
4. MULTILEVEL FEEDBACK QUEUE
Algoritma ini mirip sekali dengan algoritma Multilevel Queue. Perbedaannya ialah algoritma ini mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Ini menguntungkan proses interaksi, karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya.
Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan dimanfaatkan penuh dan I/O dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.
Algoritma ini didefinisikan melalui beberapa parameter, antara lain:
• Jumlah antrian
• Algoritma penjadwalan tiap antrian
• Kapan menaikkan proses ke antrian yang lebih tinggi
• Kapan menurunkan proses ke antrian yang lebih rendah
• Antrian mana yang akan dimasuki proses yang membutuhkan
Dengan pendefinisian seperti tadi membuat algoritma ini sering dipakai. Karena algoritma ini mudah dikonfigurasi ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik, kita harus mengetahui nilai parameter tersebut. Multilevel feedback queue adalah salah satu algoritma yang berdasar pada algoritma mulilevel queue. Perbedaan mendasar yang membedakan multilevel feedback queue dengan multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dengan prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut.
• Semua proses yang baru datang akan diletakkan pada antrian 0 (quantum = 8 ms)
• Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke antrian pertama (quantum = 16 ms)
• Antrian pertama hanya akan dikerjakan jika tidak ada lagi proses di antrian 0, dan jika suatu proses di antrian pertama 1 tidak selesai dalam 16 ms, maka proses tersebut akan dipindahkan ke antrian kedua
• Antrian kedua akan dikerjakan bila antrian 0 dan 1 kosong, dan akan berjalan dengan algoritma FCFS.
Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dalam hal ini ditentukan oleh time quantum, namun dalam prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih dahulu parameter-parameternya, yaitu :
a. Jumlah antrian
b. Algoritma internal tiap antrian
c. Aturan sebuah proses naik ke antrian yang lebih tinggi
d. Aturan sebuah proses turun ke antrian yang lebih rendah
e. Antrian yang akan dimasuki tiap proses yang baru datang
Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem. Pada masa sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan
B. PREEMPTIVE :
Preemptive Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di antrian ready dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di antrian ready tersebut. Preemptive SJF sering disebut juga Shortest-Remaining-Time-First scheduling.
Solusi Preemptive:
Rata-rata waiting time adalah (9 + 1 + 0 +2)/4 = 3, dimana :
P1: (0-0+11-2) = 9
P2: (2-2+5-4) = 1
P3: (4-4) = 0
P4: (7-5) = 2
Rata-rata turnaround time adalah ((9+7)+(1+4)+(0+1)+(4+2))/4 = 7
1. ROUND ROBIN
Algoritma ini didesin untuk sistem time-sharing. Proses akan mendapat jatah sebesar time quantum dengan nilai quantum umumnya sebesar 10-100 ms. Jika time quantum-nya habis atau proses sudah selesai CPU akan dialokasikan ke proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU (1/n), dan tak akan menunggu lebih lama dari (n-1)/q.
Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first-come first-served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang.
Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 time quantum. Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.
Misalnya ada tiga proses dengan masing-masing mendapatkan waktu quantum adalah 4 ms, maka P1 mendapatkan 4 ms pertama. Karena membutuhkan 20 ms lagi, sesudah quantum pertama P1 di preemptive dan CPU memberikan proses berikutnya ke proses P2 dan P2 tidak memerlukan 4 ms, P2 selesai sebelum jatah quantumnya habis, kemudian CPU memberikan ke proses berikutnya yaitu P3. Ketika setaiap proses meneriman satu quantum, CPU kembali ke proses P1 untuk tambahan waktu quantum.
Proses Burst time
P1 24 ms
P2 3 ms
P3 3 ms
Rata-rata waiting time adalah (6+4+7)/3 = 5.66
Rata-rata turnaround time adalah ((6+24)+(4+3)+(7+3))/3 = 15.67
2. SHORTES 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.
3. 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 :
a. 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.
b. 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.
Contoh penjadwalan berprioritas :
Proses-proses yang sangat banyak operasi masukan/keluaran menghabiskan kebanyakan waktu menunggu selesainya operasinya masukan/keluaran.
Proses-proses ini diberi prioritas sangat tinggi sehingga begitu proses memerlukan pemroses segera diberikan, proses akan segera memulai permintaan masukan/keluaran berikutnya sehingga menyebabkan proses blocked menunggu selesainya operasi masukan/keluaran. Dengan demikian pemroses dapat dipergunakan proses-proses lain. Proses-proses I/O berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses, sementara proses-proses I/O itu menunggu selesainya operasi DMA.
Proses-proses yang sangat banyak operasi I/O-nya, kalau harus menunggu lama untuk memakai pemroses (karena prioritas rendah) hanya akan membebani memori, karena harus disimpan tanpa perlu proses-proses itu dimemori karena tidak selesai-selesai menunggu operasi masukan dan menunggu jatah pemroses.
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.
Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layanan adil dari pemroses dalam arti jumlah waktu pemroses yang sama. Keunggulannya penjadwalan berpriorita adalah memenuhi kebijaksanaan yang ingin mencapai maksimasi suatu kriteria diterapkan. Algoritma ini dapat dikombinasikan, yaitu dengan mengelompokkan proses-proses menjadi kelas-kelas prioritas. Penjadwalan berprioritas diterapkan antar kelas-kelas proses itu. Algoritma penjadwal akan menjalankan : proses runnable untuk prioritas 4 lebih dulu secara round robin, apabila kelas 4 semua sudah diproses, selanjutnya akan menjalankan proses runnable untuk prioritas 3 secara round robin, apabila kelas 3 semua sudah diproses (habis), selanjutnya akan menjalankan proses runnable untuk prioritas 2 secara round robin, dan seterusnya, seperti dalam gambar berikut :
Queues header Runnable processes
|=======================================|
+------------+ +---+ +---+ +---+
: Priority 4 :------: :----: :----: : (Highest priority)
: : +---+ +---+ +---+
+------------+ +---+ +---+ +---+ +---+ +---+
: Priority 3 :------: :----: :----: :----: :----: :
: : +---+ +---+ +---+ +---+ +---+
+------------+ +---+
: Priority 2 :------: :
: : +---+
+------------+
: Priority 1 : (Lowest priority)
: :
+------------+
4. 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
Sumber: http://dianekaps.blogspot.com/2014/10/pengertian-dan-contoh-alogaritma.html
No comments:
Post a Comment