RSS

Algoritma Penjadwalan

10 Okt

1. MFQ (Multiple Feedback Queue)

Multilevel Queue (MQ)

Ide dasar dari algoritma ini berdasarkan pada sistem prioritas proses. Prinsipnya, jika setiap proses dapat dikelompokkan berdasarkan prioritasnya, maka akan didapati queue seperti pada gambar berikut:

Dari gambar tersebut terlihat bahwa akan terjadi pengelompokan proses-proses 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.

Dalam hal ini, dapat dilihat bahwa seolah-olah algoritma dengan prioritas yang dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dengan algoritma 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.

MFQ (Multiple 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. Hal 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 terutilisasi penuh dan M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

Algoritma ini didefinisikan melalui beberapa parameter, antara lain:

  1. Jumlah antrian.
  2. Algoritma penjadwalan tiap antrian.
  3. Kapan menaikkan proses ke antrian yang lebih tinggi.
  4. Kapan menurunkan proses ke antrian yang lebih rendah.
  5. 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 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.

  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.

Contoh:

Terdapat tiga antrian; Q1=10 ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam 40 ms tidak selesai, maka dipindahkan lagi ke Q3. 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.

2. RR (Round Robin)

Penjadwalan Round-Robin merupakan:

  • Penjadwalan preemptive, namun proses tidak di-preempt secara langsung oleh proses lain namun oleh penjadwal berdasarkan lama waktu berjalannya suatu proses maka penjadwalan ini disebut preempt-by-time.
  • Penjadwalan tanpa prioritas.

Semua proses dianggap penting dan diberi sejumlah waktu pemroses yang disebut kwanta (quantum) atau time-slice tempat proses itu berkalan. Proses berjalannya selama 1 kwanta, kemudian penjadwal akan mengalihkan kepada proses berikutnya, juga untuk berjalan satu kwanta, begitu seterusnya sampai kembali pada proses pertama dan berulang.

Ketentuan dari algoritma Round-Robin

  1. Jika kwanta habis dan proses belum selesai maka proses Running itu menjadi Ready (Runnable) dan pemroses dialihkan ke proses lain.
  2. Jika kwanta belum habis dan proses menunggu suatu kejadian (misalnya menunggu selesainya suatu sistem operasi I/O), maka proses Running itu menjadi Blocked dan pemroses dialihkan ke proses lain.
  3. Jika kwanta belum habis tapi proses telah selesai maka proses Running itu diakhiri dan pemroses dialihkan ke proses lain.

Algoritma penjadwalan itu dapat diimplementasikan sbb,

  • Sistem mengelola senarai proses Ready (Runnable) sesuai urutan kedatangan.
  • Sistem mengambil proses yang beraa di ujung depan antrian Ready menjadi Running.
  • Bila kwanta belum habis dan proses selesai maka sistem mengambil proses di ujung depan antrian proses ready.
  • Jika kwanta habis dan proses belum selesai maka tempatkan proses Running ke ekor antrian proses Ready dan sistem mengambil proses di ujung depan antrian proses Ready.

Masalah penjadwalan ini adalah dalam hal menentukan besar kwanta, yaitu:

  • Kwanta terlalu besar menyebabkan waktu tanggap besar dan turn arround time rendah.
  • Kwanta terlalu kecil mengakibatkan peralihan proses terlalu banyak sehingga menurunkan efisiensi pemroses.

Harus ditetapkan besar kwanta waktu yang optimal berdasarkan kebutuhan sistem terutama dari hasil percobaan atau data historis dari sistem. Besar kwanta waktu beragam yang bergantung beban sistem.

3. SRF (Shortest Remaining First)

Penjadwalan ini merupakan:

  • Penjadwalan preemptive
  • Penjadwalan berprioritas dinamis

Penjadwalan SRF merupakan perbaikan dari SJF. SJF merupakan penjadwalan nonpreemptive sedang SRF adalah preemptive yang dapat digunakan untuk sistem timesharing.

Ketentuan:

Pada SRT, proses dengan sisa waktu jalan diestimasi terendah dijalankan, termasuk proses-proses yang baru tiba.

Perbedaan SRF dengan SJF

  • Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai.
  • Pada SRT proses sedang berjalan (Running) dapat diambil alih oleh proses baru dengan sisa waktu jalan yang diestimasi lebih rendah.

Kelemahan:

SRT mempunyai overhead yang lebih besar dibandingkan SJF. SRT memerlukan penyimpanan waktu layanan yang telah dihabiskan proses dan kadang-kadang harus menangani peralihan.

  • Tibanya proses-proses kecil akan segera dijalankan.
  • Proses-proses lebih lama berarti dengan lama dan variasi waktu tunggu lebih lama dibandingkan pada SJF.

Secara teoritis SRT memberi waktu tunggu minimum tapi karena adanya overhead peralihan maka pada situasi tertentu SJF bisa memberi kinerja yang lebih baik dibanding SRT.

4. HRN (Highest Ratio Next)

Penjadwalan HRN merupakan:

  • Penjadwalan non-preemptive
  • Penjadwalan berprioritas dinamis

Penjadwalan ini juga untuk mengkoreksi kelemahan SJF. HRN adalah strategi penjadwalan nonpreemptive dengan prioritas proses tidak hanya merupakan fungsi dari waktu layanan tapi juga jumlah waktu tunggu proses.

Prioritas dinamis HRN dihitung berdasarkan rumus:

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

Karena waktu layanan muncul sebagai pembagi maka proses yang lebih pendek mempunyai prioritas yang lebih baik. Karena waktu tunggu sebagai pembilang maka proses yang telah menunggu lebih lama juga mempunya kesempatan lebih bagus untuk memperoleh layanan pemrosesan.

Disebut HRN (High Response Next) karena (waktu tanggap adalah waktu tunggu + waktu layanan). Ketentuan HRN berarti agar memperoleh waktu tanggap tertinggi yang harus dilayani.

5. PS (Priority Schedulling)

Gagasan penjadwalan adalah masing-masing proses diberi prioritas dan proses berprioritas tertinggi menjadi Running (yaitu mendapat jatah waktu pemroses).

Prioritas dapat diberikan secara:

  • Prioritas statis (static priorities)
  • Prioritas dinamis (dynamic priorities)

Prioritas statis, prioritas statis berarti proiritas tak berubah.

Keunggulan

  • Mudah diimplementasikan
  • Mudah overhead relatif kecil

Kelemahan

Implementasi mekanisme prioritas dinamis lebih kempleks dan mempunyai overhead yang lenih besar dibanding mekanisme proiritas statik.

Contoh penjadwalan berprioritas

Proses-proses yang sangat banyak operasi masukan/ keluaran dan menghabiskan kebanyakan waktu proses untuk menunggu selesainya operasi masukan/ keluaran. Proses demikian disebut I/O bound process. Proses-proses ini dapat diberi prioritas sangat tinggi sehingga begitu proses-proses memerlukan pemrosesan segera saja diberikan dan proses akan segera memulai permintaan masukan/ keluaran berikutnya sehingga menyebabkab proses Blocked menunggu selesainya operasi masukan/ keluaran. Dengan demikian pemroses segera dialihkan, dapat dipergunakan oleh proses-proses lain tanpa mengganggu proses I/O bound. Proses-proses I/O bound berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses.

Proses-proses yang sangat banyak operasi masukan/ keluaran kalau harus menunggu lama untuk memakai pemroses (karena diberi proiritas rendah) hanya akan membebani mamori karena tidak selesai-selesai menunggu operasi masukan/ keluaran dan menunggu jatah pemroses.

Algoritma Prioritas Dinamis

Algoritma ini dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu yang menjadi tujuan sistem komputer.

Algoritma sederhana yang memberi layanan bagus adalah dengan menge-set proses dengan prioritas berdasarkan rumus nilai 1/f dengan f adalah rasio kwanta terakhir yang digunakan proses.

  • Proses yang menggunakan 2 milidetik kwanta 100 ms maka proiritasnya 50
  • Proses yang berjalan selama 50 milidetik sebelum Blocked berprioritas 2.
  • Proses yang menggunakan seluruh kwanta berprioritas 1.

Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layanan yang adil dari pemroses dalam arti jumlah waktu pemroses yang sama untuk masing-masing pemroses pada satu waktu.

Keunggulan Algoritma Penjadwalan Berprioritas

Biasanya memenuhi kebijaksanaan yang ingi mencapai level maksimal berdasarkan suatu kriteria tertentu di sistem.

Kombinasi

Algoritma penjadwalan berprioritas dapat dikombinasikan yaitu dengan mengelompokkan proses-proses menjadi kelas-kelas prioritas. Penjadwalan berprioritas diterapkan antar kelas-kelas proses-proses itu. Penjadwalan round-robin atau penjadwalan FIFO diterapkan pada proses-proses di dalam satu kelas.

6.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 naikketingkat lebih tinggi diatas pesaing terdekatnya. Ide sederhana ini dapat diimplementasikan ke sistem real-time dan memiliki penjadwalan berprioritas dinamis.

Oleh:

Nama: Zulfa Ulinnuha

Kelas: D

NIM : 08650066

 
Tinggalkan komentar

Ditulis oleh pada 10 Oktober 2010 in Kuliah

 

Tag: ,

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

 
%d blogger menyukai ini: