Tuesday, October 24, 2017

Algoritma Multilevel Queue

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

Multilevel Queue | Stimik Eresha
Multilevel Queue

Dari gambar diatas tersebut terlihat bahwa akan terjadi pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk menganggap kelompok-kelompok tersebut sebagai sebuah antrian-antrian kecil yang merupakan bagian dari antrian keseluruhan proses, inilah 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 yang bisa dipelajari diartikel sebelumnya " Pembahasan Algoritma 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.

Selengkapnya tentang kelemahan Algoritma Shcheduling bisa dibaca dimasing-masing algoritma:
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.

Pelajari selengkapnya tentang Tiga Algoritma Scheduling Pada Memury CPU.

Monday, October 23, 2017

Pengertian Lengkap Algoritma Round Robin

Round Robin → Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time quantum. 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 yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.

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.

Setelah mengamati beberapa proses algoritma termasuk Model Algoritma Round Robin bisa diamati pula bebera kekurangan dan keunggulan dari masing masing Algoritma
  1. FCFS (First Come First Served) → Baca Selengkapnya ....
  2. SJF (Shortes Job First) → Baca Selengkapnya ....
  3. Priority Scheduling → Baca Selengkapnya ....


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 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 servedTime quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

Urutan Kejadian Algoritma Round Robin
Penggunaan Waktu Quantum

Pengertian Lengkap Algoritma 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 burst M/K 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 yang menunggu dalam queue dinaikkan satu tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21 jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang tertinggi (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi).

Pengertian Lengkap Algoritma SJF (Shortes Job First)

SJF (Shortes Job First)

Pada algoritma ini 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. lalu apa perbedaan dengan algorima FCFS (First Come First Served) → Baca Selengkapnya ...

Contoh Shortest Job First

Contoh

Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time 4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4 dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF (Shortes Job First). Setelah memperoleh gambaran cara kerja algoritma SJF lalu apa keuntungan  dan kekurangan menggunakan algoritma type ini → Silahkan Baca Selengkapnya ...
Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms.


Shortest Job First (Non-Preemptive)

Average waiting time rata-rata untuk ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms.
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 dua 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.
Keuntungan dan keukurangan tiga metode penjadwalan CPU / Memory

Tiga Algoritma Penjadwalan

Dalam proses pengalokasian memori terbagi menjadi 3 pengalokasian, diantaranya :

  1. FCFS (First Come First Served)
  2. SJF (Shortes Job First)
  3. Round Robin

A. FCFS (First Come First Served)
Adalah Algoritma penjadwalan komputer paling sederhana → Baca selengkapnya .. FCFS (First Come First Served)
  • Kelebihan dari pengalokasian memori FCFS: 
      Memperkecil rata-rata lama tanggap
      Algoritma yang paling sederhana, dengan skema proses yang meminta CPU mendapat prioritas.
  • Kelemahan dari pengalokasian memori FCFS:
      Layanan terhadap proses panjang bisa tidak terlayani jika proses pendek datang terus.
      Terjadi convoy effect dimana seandainya ada sebuah proses yang kecil tetapi mengantri dengan proses yang membutuhkan waktu yang lama mengakibatkan proses tersebut akan lama juga untuk dieksekusi.
B. SJF (Shortes Job First) → Baca Selengkapnya ....

~Kelebihan dari pengalokasian memori SJF :
paling optimal, karena algoritma ini memberikan minimum waiting time untuk kumpulan proses yang mengantri

~Kelemahan dari pengalokasian memori SJF :
tidak bisa digunakan untuk penjadwalan CPU short term.


C. ROUND ROBIN → Baca Selengkapnya ....

~Kelebihan dari pengalokasian memori ROUND ROBIN :
mempunyai response lebih cepat terhadap user.

~Kelemahan dari pengalokasian memori ROUND ROBIN :
mempunyai waktu lebih lama dalam turnaround dibandingkan dengan SJF (Shortes Job First)

dari 3 pengalokasian diatas yang paling utama atau yang lebih optimal kinerjanya yaitu SJF (Shortes Job First), karena algoritma ini memberikan minimum waiting time untuk kumpulan proses yang mengantri sebelum masuk memori. Dengan mengeksekusi waktu yang paling pendek baru yang paling lama. Akibatnya rata-rata waktu menunggu menjadi menurun.

Pengertian Lengkap Algoritma FCFS (First Come First Served)

FCFS (First Come First Served) → Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan Memory CPU. Dengan menggunakan algoritma ini setiap proses yang berada pada status ready dimasukkan kedalam FIFO queue atau antrian dengan prinsip first in first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.

Khusus untuk pembahasan kekurangan dan kelebihan menggunakan FCFS (First Come First Served)  → Baca Selengkapnya .... kekurangan dan kelebihan menggunakan FCFS

Contoh proses FCFS algoritma sederhana

Ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki burst time 24 ms, P2 memiliki burst time 3 ms, dan P3 memiliki burst time 3 ms. Hitunglah waiting 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 27 ms (menunggu P1 dan P2 selesai). Lihat dan perhatikan gambar dibawah
Gantt Chart Kedatangan Proses


Urutan kedatangan adalah P1, P2 , P3; gantt chart untuk urutan ini adalah:

  1. Waiting time rata-ratanya adalah sebesar(0+24+27)/3 = 17ms. 
  2. Turnaround time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 27 ms (dihitung dari awal kedatangan P2 hingga selesai dieksekusi), untuk P3 sebesar 30 ms. Turnaround time rata-rata untuk ketiga proses tersebut adalah (24+27+30)/3 = 27 ms. Kelemahan dari algoritma ini: Waiting time rata-ratanya cukup lama. 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. 


Misalkan proses dibalik sehingga urutan kedatangan adalah P3, P2, P1. Waiting time adalah P1=6; P2=3; P3=0. Average waiting time: (6+3+0)/3=3.

Gantt Chart Kedatangan Proses Sesudah Urutan Kedatangan Dibalik
Baca juga artikel terkait lainya :
  • SJF (Shortes Job First) → Baca Selengkapnya .... 
  • ROUND ROBIN → Baca Selengkapnya ....

Friday, October 13, 2017

Rumus Lengkap Menyusun Tabel Distribusi Frekuensi

Distribusi Frekuensi
Metode menyusun data baik yang bersifat Dikrit (Utuh) maupun data yang bersifat Contineu (Tidak Utuh) dengan cara memasukan data kedalam kelas-kelas interval guna mempermudah analisa dan penyajian informasi

Aturan Sturges dalam Tabel Distribusi

Lihat pada gambar aturan menyusun Tabel Distribusi Frekuensi

Menyusun Tabel Data Frekuensi dengan Aturan Sturges

Langkah pertama Urutkan dentum Data yang diperoleh atau data yang ada
Langkah kedua menentukan besarnya Range (R)
→ Range adalah selisih antara nilai tertinggi dengan nilai terendah dari suatu data distribusi (Raw Data)
Rumus :
[ R = a-b ]
Ket:
R adalah Range yang dicari dengan cara pengurangan data tertinggi dengan data terendah setelah dentum data diurutkan
a Adalah data dengan nilai tertinggi
b Adalah data dengan nilai terendah


Langkah ketiga menentukan banyaknya kelas interval / kelompok interval (K)
→ Kelas interval adalah jumlah kelas yang akan digunakan sebagai syarat menentukan jumlah kelas didalam interval data distribusi
Rumus :
[ K = 1+3,3 Log n ]
Ket:
K Adalah Kelas Interval yang digunakan untuk menentukan Jumlah Kelas tabel distribusi frekuensi
Log n Adalah log dari jumlah dentum data (Untuk lebih jelas tentang "variable n" bisa langsung dipelajari dalam cotoh)

Langkah keempat menentukan rentang kelas atau Interval kelas ( 'i' ada juga yang melambangkan 'p')
→ i Adalah Interval kelas
→ p Adalah Panjang kelas
Ket : i atau p adalah sama

Rumus :
[ i/p = R/K ]
Ket:
i/p Adalah Interval kelas atau Panjang kelas
R Adalah Range
K Adalah Jumlah Kelas Interval

Hanya belajar dengan teori saja tidaklah cukup , Pelajari juga contoh soal pada artikel selanjutnya:

  • Contoh soal dan cara mencari Range (R) dalam Tabel Distribusi Frekuensi
  • Contoh soal dan cara mencari Kelas Interval (K) dalam Tabel Distribusi Frekuensi
  • Contoh soal dan cara mencari Interval/Panjang kelas (i/p) dalam Tabel Distribusi Frekuensi