Selasa, 31 Oktober 2017

Multi level Queve Dan Multi Level Feedback Queue

     

Dalam ilmu komputer , antrian umpan balik bertingkat adalah penjadwalan algoritma. Solaris 2.6 Time-Sharing (TS) scheduler mengimplementasikan algoritma ini. Algoritma penjadwalan ini dimaksudkan untuk memenuhi persyaratan desain berikut untuk sistem multimode :

1. Berikan pilihan pekerjaan singkat.
2. Berikan pilihan pada I / O terikat proses.
3. Proses terpisah dalam kategori berdasarkan kebutuhan mereka untuk prosesor.

Tidak seperti antrian multilevel algoritma penjadwalan di mana proses secara permanen ditugaskan untuk antrian, penjadwalan antrian umpan balik multilevel memungkinkan proses untuk bergerak di antara antrian. Gerakan ini difasilitasi oleh karakteristik ledakan CPU dari proses. Jika proses menggunakan terlalu banyak waktu CPU, itu akan dipindahkan ke antrian yang lebih rendah-prioritas. Skema ini membuat I / O proses-bound dan interaktif dalam antrian prioritas yang lebih tinggi. Selain itu, proses yang menunggu terlalu lama dalam antrian yang lebih rendah-prioritas mungkin akan dipindahkan ke antrian prioritas yang lebih tinggi. Bentuk penuaan juga membantu untuk mencegah kelaparan proses prioritas yang lebih rendah tertentu.

Algoritma

Beberapa FIFO antrian yang digunakan dan operasi adalah sebagai berikut:

1. Sebuah proses baru dimasukkan di akhir (ekor) dari tingkat atas FIFO antrian.
2. Pada tahap proses mencapai kepala antrian dan diberi CPU .
3. Jika proses ini selesai dalam waktu kuantum dari antrian yang diberikan, ia meninggalkan sistem.
4. Jika proses sukarela melepaskan kontrol dari CPU, ia meninggalkan jaringan antrian, dan ketika proses menjadi siap lagi itu dimasukkan pada ekor antrian yang sama yang dilepaskan sebelumnya.
5. Jika proses menggunakan semua waktu quantum, maka pra-empted dan dimasukkan pada akhir antrian tingkat yang lebih rendah berikutnya. Ini antrian tingkat yang lebih rendah berikutnya akan memiliki waktu kuantum yang lebih daripada sebelumnya yang lebih tinggi antrian tingkat.
6. Skema ini akan berlanjut sampai proses selesai atau mencapai antrian tingkat dasar.

• Pada antrian tingkat dasar proses beredar di round robin mode sampai mereka menyelesaikan dan meninggalkan sistem. Proses dalam antrian tingkat dasar juga dapat dijadwalkan pada pertama datang pertama dilayani dasar.
• Opsional, jika blok proses I / O, itu 'dipromosikan' satu tingkat, dan ditempatkan pada akhir antrian berikutnya yang lebih tinggi. Hal ini memungkinkan I / O proses terikat untuk disukai oleh scheduler dan memungkinkan proses untuk 'melarikan diri' antrian tingkat dasar

Untuk penjadwalan, scheduler selalu mulai mengambil proses dari kepala antrian tingkat tertinggi. Jika antrian tingkat tertinggi telah menjadi kosong, maka hanya akan scheduler mengambil proses dari antrian tingkat yang lebih rendah berikutnya. Kebijakan yang sama diterapkan untuk mengambil di antrian tingkat yang lebih rendah berikutnya. Sementara itu, jika suatu proses datang ke salah satu antrian tingkat yang lebih tinggi, itu akan mendahului proses dalam antrian tingkat yang lebih rendah.

Juga, proses baru selalu disisipkan di ekor antrian tingkat atas dengan asumsi bahwa itu akan menjadi proses yang memakan waktu yang singkat. Proses panjang akan otomatis tenggelam ke antrian tingkat yang lebih rendah berdasarkan konsumsi waktu dan tingkat interaktivitas. Dalam antrian umpan balik bertingkat, proses diberikan hanya satu kesempatan untuk menyelesaikan pada tingkat antrian yang diberikan sebelum dipaksa turun ke antrian tingkat yang lebih rendah.
Parameter penjadwalan

Secara umum, sebuah multilevel antrian umpan balik scheduler didefinisikan oleh parameter berikut:

• Jumlah antrian.
• Algoritma penjadwalan untuk setiap antrian yang dapat berbeda dari FIFO.
• Metode yang digunakan untuk menentukan kapan untuk mempromosikan proses untuk antrian prioritas yang lebih tinggi.
• Metode yang digunakan untuk menentukan kapan untuk menurunkan proses ke antrian prioritas yang lebih rendah.
• Metode yang digunakan untuk menentukan antrian proses akan masuk ketika proses yang membutuhkan layanan.

Algoritma penjadwalan antrian multilevel partisi antrian siap dalam beberapa antrian yang terpisah, misalnya
Dalam antrian multilevel proses penjadwalan secara permanen ditugaskan ke salah satu antrian.
Proses secara permanen ditugaskan untuk satu sama lain, didasarkan pada beberapa properti dari proses, seperti
• Ukuran memori
• Prioritas proses
• Jenis proses

Algoritma memilih proses dari antrian ditempati yang memiliki prioritas tertinggi, dan menjalankan proses yang baik
• Memesan Efek Terlebih Dahulu atau
• Non-Terlebih Dahulu

Setiap antrian memiliki algoritma penjadwalan sendiri atau kebijakan.

Kemungkinan I

Jika setiap antrian memiliki prioritas mutlak atas antrian prioritas rendah maka tidak ada proses dalam antrian bisa berjalan kecuali antrian untuk proses dengan prioritas tertinggi semua kosong.
Sebagai contoh, pada gambar di atas ada proses dalam antrian batch dapat dijalankan kecuali antrian untuk proses sistem, proses interaktif, dan proses editing interaktif semua kosong akan.

Kemungkinan II

Jika ada sepotong waktu antara antrian maka setiap antrian mendapat sejumlah kali CPU, yang kemudian dapat menjadwalkan proses-proses dalam antrian tersebut. Misalnya;
• 80% dari waktu CPU untuk latar depan antrian menggunakan RR.
• 20% dari waktu CPU latar belakang antrian menggunakan FCFS.
Karena proses tidak bergerak antara antrian begitu, kebijakan ini memiliki keuntungan overhead penjadwalan rendah, tetapi tidak fleksibel.



sumber

Naga. D.S. 1995. Sistem Operasi Komputer. Penerbit Gunadarma. Jakarta.
Dyan. (2011). Algoritma Penjadwalan. [Online]. Tersedia: http://pioniezez.wordpress.com/2011/04/12/algoritma-penjadwalan/ [23 maret 2013].
Andrian Dwi Putra. (2011). Struktur Sistem Operasi. [Online]. Tersedia: http://marikitangulik.blogspot.com/2011_05_01_archive.html [23 maret 2013].


  


Multilevel Feedback Queue Scheduling

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:
a. Jumlah antrian.
b. Algoritma penjadualan tiap antrian.
c. Kapan menaikkan proses ke antrian yang lebih tinggi.
d. Kapan menurunkan proses ke antrian yang lebih rendah.
e. 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. Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.

Penjadwalan dengan menggunakan algoritma multilevel feedback queue sama dengan algoritma pada penjadwalan multilevel queue, pada penjadwalan feedback queue suatu proses yang dapat berpindah antar berbagai queue; aging dapat diterapkan dengan cara ini. Multilevel-Feedback Queue Scheduler digambarkan oleh parameter berikut:

• Jumlah queue
• Scheduling algoritma untuk tiap queue
• Metode yang digunakan untuk memutuskan ketika upgrade suatu proses
• Metode yang digunakan untuk memutuskan ketika menurunkan suatu proses
• Metode yang digunakan untuk menentukan queue mana yang akan diproses ketika proses membutuhkan service

Contoh dari Multivel Feedback Queue

• Tiga queue:
• Q0- time quantum 8 miliseconds
• Q1- time quantum 16 miliseconds
• Q2- FCFS
Scheduling

• Pekerjaan baru masuk queue Q0 yang dilayani FCFS. Ketika memperoleh CPU, pekerjaan menerima 8 seperseribu detik. Jika tidak selesai dalam 8 seperseribu detik, pekerjaan dipindah ke queue Q1.

• Pada Q1 pekerjaan dilayani FCFS dan menerima 16 seperseribu detik tambahan . Jika masih belum lengkap, maka di-preempted dulu dan dipindah ke queue Q2.
Proses multilevel feedback queue scheduling juga bisa dilakukan dengan cara lebih adil, dengan menggunakan tiga metode:
• Menggunakan algoritma RR dengan quantum 5
• Menggunakan algoritma RR dengan quantum 10
• Menggunakan algoritma FCFS

Seluruh proses dikerjakan dengan algoritma RR dengan quantum 5, jika proses tidak selesai, proses dikembalikan ke ready queue dan urutan proses diletakkan di bagian terakhir dari proses yang ada untuk diproses. Setelah proses dengan waktu kedatangan proses lain selesai, baru diproses kembali dengan algoritma RR dengan quantum 10. Jika masih belum selesai, maka proses akan dikerjakan dengan algoritma FCFS sampai semua proses selesai.

Sumber:
http://thedarchangel.blogspot.com/2012/06/multilevel-feedback-queue-scheduling.html
http://candra-zulisman.blogspot.com/2013/03/multilevel-feedback-queue-scheduling.html



Soal.
1. Apa definisi algoritma dan contohnya .!

2. Apa definisi Pseudo Code dan contohnya .!

3. Apa definisi flowchart dan contohnya .!

4. Jelaskan dengan contoh kasus algoritma yang memiliki struktur runtunan.!


Jawaban:

1. Definisi Algoritma. 
    “Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara   sistematis dan logis”. Kata logis merupakan kata kunci dalam algoritma. Langkah-langkah dalam algoritma harus logis dan harus dapat ditentukan bernilai salah atau benar. Dalam beberapa konteks, algoritma adalah spesifikasi urutan langkah untuk melakukan pekerjaan tertentu. Pertimbangan dalam pemilihan algoritma adalah, pertama, algoritma haruslah benar. Artinya algoritma akan memberikan keluaran yang dikehendaki dari sejumlah masukan yang diberikan. Tidak peduli sebagus apapun algoritma, kalau memberikan keluaran yang salah, pastilah algoritma tersebut bukanlah algoritma yang baik.

Contoh:
Algoritma mendapatkan minyak dengan volume 4 liter. 


  1. Isi penuh ember 3 liter dengan minyak. {ember 3 liter berisi minyak 3 liter}
  2. Tuangkan minyak dari ember 3 liter ke dalam ember 5 liter. {ember 5 liter berisi minyak 3 liter}.
  3. Isi penuh ember 3 liter dengan minyak. {ember 3 liter berisi minyak 3 liter}
  4. Tuang minyak dari ember 3 liter ke ember 5 liter hingga ember 5 liter penuh. {di dalam ember 3 liter sekarang berisi minyak sebanyak 1 liter}
  5. Kembalikan minyak dari ember 5 liter ke dalam drumnya. {ember 5 liter kosong}
  6. Tuangkan minyak dari ember 3 liter ke ember 5 liter. {ember 3 liter kosong, ember 5 liter berisi minyak 1 liter}
  7. Isi penuh ember 3 liter dengan minyak, lalu tuang ke dalam ember 5 liter. Maka akan diperoleh minyak sebanyak 4 liter {1 + 3 = 4 liter minyak }.




2. Definisi Pseudo code.

    Pseudo Code adalah urutan baris algoritma seperti kode pemrograman dan tidak memiliki sintak yang baku. Pseudo Code lebih umum digunakan oleh programmer yang berpengalaman. Akan tetapi, flowchart lebih mudah dimengerti oleh programmer pemula, pseudo code sangat mudah diimplementasikan ke dalam kode program dibandingkan dengan flowchart. Kita bisa bebas menulis pseudo code selama itu mudah dimengerti bagi orang lain. Tetapi disarankan untuk menggunakan keyword yang umum digunakan seperti : if, then, else, while, do, repeat, for, dan lainnya. Dan ikuti gaya penulisan pemrograman seperti Pascal, C++, dll.

Contoh:
Pseudocode dari luas Persegi adalah:
 
read(panjang, lebar) 

    Luas = panjang * lebar

    write(Luas)
end





3. Definisi Flowchart.
    flowchart adalah suatu representasi secara diagram yang mengilustrasikan urutan dari operasi yang dilakukan untuk mendapatkan suatu hasil. Dengan kata lain, flowchart membantu kita untuk mengerti dan melihat bentuk algoritma dengan menampilkan algoritma dalam simbol-simbol gambar.

Contoh:




4. Contoh algoritma yang memiliki struktur runtutan:

    Dibaca waktu tempuh seorang pelari marathon dalam jam-menit-detik (hh:mm:ss). Diminta mengkonversi waktu tempuh tersebut ke dalam detik. Tuliskan algoritmanya.
Ingatlah 
        1 menit = 60 detik
        1 jam = 3600 detik
Misalnya waktu tempuh seorang pelari marathon adalah 1 jam, 5 menit, 40 detik. Dalam detik, waktu tempuh seluruhnya adalah ( 1 x 3600 ) + ( 5 x 60 ) + 40 = 3940 detik.

Penyelesaian :
Algoritma KONVERSI_JAM_KE_DETIK
{ dibaca jam-menit-detik (hh:mm:ss). Nilai jam-menit-detik dikonversi ke dalam detik, lalu ditampilkan ke piranti keluaran }

DEKLARASI
Type jam : record <hh : integer    {0..23},    {jam}
              mm : integer    {0..59},    {menit}
              ss : integer    {0..59},    {detik}
             >
J : jam
TotalDetik : integer

DESKRIPSI
read(J.hh,J.mm,J.ss))
TotalDetik ← (J.hh*3600) + (J.mm*60) + J.ss
write(TotalDetik)

Jika anda mentranslasikan algoritma KONVERSI_JAM_KE_DETIK ke dalam bahasa pascal, anda harus memperhatikan tipe bilangan bulat yang digunakan. Karena ranah nilai tipe integer terbatas, maka ada kemungkinan hasil pengubahan jam-menit-detik ke total detik bernilai negatif, sebab nilai (J.hh*3600) + (J.mm*60) + J.ss berada di luar rentang tipe integer. Tipe longint yang mempunyai ranah yang lebih besar dapat dipakai untuk masalah ini. 
Jadi, program KONVERSI_JAM_KE_DETIK dalam bahasa pascal adalah sebagai berikut :
program KONVERSI_JAM_KE_DETIK;
{ dibaca jam-menit-detik (hh:mm:ss). Nilai jam-menit-detik dikonversi ke dalam detik, lalu ditampilkan ke piranti keluaran.}

uses wincrt;

(* DEKLARASI *)
type Jam = record
        hh : longint;        {jam}
        mm : longint;        {menit}
        ss : longint;        {detik}
         end;

var
  J : Jam;
  TotalDetik : longint;

(* deskripsi *)
begin
   write(‘Jam  :’); readln(J.hh);
   write(‘Menit:’); readln(J.mm);
   write(‘Detik:’); readln(J.ss);
   TotalDetik:= (J.hh*3600) + (J.mm*60) + J.ss;
   writeln(‘Total detik = ‘, TotalDetik);
end.