Senin, 13 Juli 2009

Algoritma Penjadwalan

0 komentar

Penjadwalan Highest Ratio Next

Algoritma ini termasuk penjadwalan nonpreemptive (run to completion), yaitu proses yang tidak dapat dapat disela, maksudnya proses tidak dapat diambil alih dan proses tersebut harus dikerjakan sampai selesai dulu. Algoritma ini merupakan penjadwalan berprioritas dinamis serta perbaikan dari algoritma penjadwalan SJF atau Shortest Job First yang ada kemungkinan proses yang memiliki waktu layanan yang lama akan menunggu lama untuk dieksekusi. Pada algoritma ini prioritas proses tidak hanya merupakan fungsi waktu layanan tetapi juga jumlah waktu tunggu proses.

Prioritas dinamis Highest Ratio Next dihitung berdasarkan rumus:

Prioritas = (waktu tunggu + waktu layanan) / waktu layanan

Proses dengan prioritas tertinggi akan dipilih untuk dieksekusi selanjutnya. Karena waktu tunggu sebagai pembilang, maka proses yang telah menunggu lama akan memiliki kesempatan yang lebih bagus.

Disebut Highest Ratio Level karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, berarti waktu tanggap tertinggi harus dilayani.

Penjadwalan Guaranteed Schedulling (GS)

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.

Penjadwalan Lottery Sheduling

Algoritma ini termasuk Algoritma Penjadwalan Interaktif, biasanya preemptive. Waktu eksekusi dibagi dalan kuantum (interval waktu) dan keputusan penjadwalan dibuat pada awal setiap kuantum. Dalam performnya memiliki waktu respon minimum. Dan penjadwalan Lottery ini lebih umum digunakan.

Berdasarkan probabilitasnya tiap proses diberikan tiket undian, pada saat penjadwalan tiket dipilih secara acak dan proses yang memiliki tiket akan dialokasiakn CPU duluan. Proses yang memiliki prioritas lebih tinggi akan memiliki banyak tiket pula.

Keuntungan dari algoritma penjadwalan ini antara lain, sederhana, sangat responsive, dapat mendukung kerjasama antarproses dan mudah untuk mendukung kebutuhan prioritas dan proporsionalitas seperti yang kita tahu algoritma ini memiliki proporsional terbaik.

Penjadwalan Fair-Share Scheduling

Algoritma ini juga termasuk Algoritma Penjadwalan Interaktif yang bersifat preemptive yang dalam performnya memiliki proporsional terbaik dan waktu respon yang minimum. Waktu eksekusi dibagi dalam kuantum (interval waktu) dan keputusan penjadwalan dibuat pada awal setiap kuantum.

Pada algoritma penjadwalan Round Robin cukup adil dari sudut pandang proses tapi mungkin tidak dari sudut pandang user. Oleh karena itu, algoritma penjadwalan Fair-Share Scheduling tiap user mendapatkan jatah secara adil karena Fair-Share berbasis user. Misalnya: X memiliki 4 proses yaitu A1, A2, A3 dan A4 sadangkan Y hanya memiliki proses B1. Maka berdasarkan algoritma ini, A1, A2, A3 dan A4 berempat berhak mendapatkan 50% atas waktu CPU. Begitupula dengan B1, berhak mendapatkan 50% atas waktu CPU.