Algoritma Penjadwalan

ALGORITMA PENJADWALAN CPU

ALGORITMA PENJADWALAN CPU

Penjadwalan berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Algoritma Penjadwalan CPU - Penjadwalan CPU adalah permasalahan menentukan proses mana pada ready queue yang dialokasikan ke CPU. Terdapat beberapa algoritma penjadwalan CPU, diantaranya :

1. Algoritma Penjadwalan First Come First Served (FIFO). 
2.  Algoritma Penjadwalan Shortest Job First.
3.  Algoritma Penjadwalan Priority Schedulling (jadwal prioritas).
4.  Algoritma Penjadwalan Round Robin.

Setiap algoritma diukur “turnaround time” dan “waiting time” untuk membandingkan performansi dengan algoritma lain. Dan untuk mengukur turnaround time dan waiting time, digunakan “Gant Chart” . CPU time (Burst Time) membutuhkan semua proses diasumsikan diketahui. Arrival time untuk setiap proses pada ready queue diasumsikan diketahui.

• Algoritma Penjadwalan First Come First Served (FCFS)

Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan 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.

Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Dan rata-rata waktu tunggu (Average waiting time) cukup tinggi.Algoritma penjadwalan FCFS merupakan salah satu strategi penjadwalan non-Preemptive karena sekali CPU dialokasikan pada suatu proses, maka proses tersebut akan tetap memakai CPU sampai proses tersebut melepaskannya, yaitu jika proses berhenti atau meminta I/O. Kelemahan dari Algoritma penjadwalan ini adalah adanya convoy effect.

skema proses yang meminta CPU mendapat prioritas. Implementasi dari FCFS mudah diatasi dengan FIFO queue.

Contoh:
Terdapat 3 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma FCFS

Maka gantt chart kedatangan proses:

 

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

 AWT = (0+23+29)/3 = 17,3 ms

Kelemahan dari algoritma ini:

1. Waiting time rata-ratanya cukup lama.
2. 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.

•  VIDEO LINK TUTORIAL SCEDULLING PROCCES  ALGORITMA FCFS :

http://www.youtube.com/watch?v=4KK0MVFSHeE

• Algoritma Shortest Job First Scheduler (SJF/SJFS)

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.

Burst time : asumsi berapa lama sebuah proses membutuhkan CPU diantara proses menunggunya I/O. Hal ini tidak dapat diprediksi secara tepat sebelum dimulainya sebuah proses. Artinya jumlah waktu yang dibutuhkan sebuah proses dalam menggunakan CPU dalam sebuah satuan waktu.(Sebuah proses dapat menggunakan CPU selama beberapa kali selama task yang diberikan belum  diselesaikan).

Algoritma ini digunakan ketika CPU bebas proses yang mempunyai waktu terpendek untuk menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut.Prinsip algoritma penjadwalan ini adalah, proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. Oleh karena itu, algoritma ini optimal jika digunakan, tetapi sulit untuk diimplementasikan karena sulit mengetahui CPU burst selanjutnya.

CONTOH SHORTEST JOB FIRST (SJF) :

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.

Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms.

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.(SRTF)

CONTOH SJF-PREEMPTIVE:

•      LINK VIDEO TUTORIAL  SJF PREEMPTIVE (PROCES SCHEDULING) :

http://www.youtube.com/watch?v=x3EYyABe5-A

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.

CONTOH SJF-NON PREEMPTIVE :

•   LINK VIDEO TUTORIAL  SJF NON-PREEMPTIVE (PROCES SCHEDULING) :

http://www.youtube.com/watch?v=3UZGv_N7x2w

•  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:

Terdapat 5 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma PS.

Maka gantt chart kedatangan proses:

 

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (12+22+19+2)/5 = 11 ms.

•  VIDEO LINK TUTORIAL SCEDULLING PROCCES  ALGORITMA PRIORITY :

http://www.youtube.com/watch?v=L8EsfAH7B0U

•  Algoritma 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.

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

Contoh:

Terdapat 3 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma RR dengan Q=3.

Maka gantt chart kedatangan proses:

 

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (12+9+12)/3 = 11 ms.

•      LINK VIDEO TUTORIAL ROUND ROBIN :

http://www.youtube.com/watch?v=GHNXNMS1bfY

PROSES  KEJADIAN ALGORITMA ROUND ROBIN :

Urutan Kejadian Algoritma Round Robin

 Penggunaan Waktu Quantum 

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:Multilevel Queue

Gambar Multilevel Queue

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.

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. 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.

 Gambar Multilevel Feedback Queue

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.

KESIMPULAN

Dari beberapa contoh diatas, algoritma yang paling efisien untuk menyelesaikan proses adalah SJF karena memiliki AWT yang kecil.

Algoritma penjadwalan

Penjadwalan CPU berurusan dengan permasalahan memutuskan proses mana yang akan dillaksanakan, oleh karena itu banyak bermacam algoritma penjadual, di seksi ini kitaakan mendiskripsikan beberapa algoritma.

1.      First Come First Served

Ini merupakan algoritma yang paling sederhana, dengan skema proses yangmeminta CPU mendapat prioritas. Implementasi dari FCFS mudah diatasi denganFIFO queue.

2.      Shortest Job First

Salah satu algoritma yang lain adalah Shortest Job First. Algoritma ini berkaitandengan waktu setiap proses. Ketika CPU bebas proses yang mempunyai waktuterpendek untuk menyelesaikannya mendapatprioritas. Seandainya dua proses

atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut.

Ada dua skema dalam SJFS ini yaitu:

                                                                     ·                     Non premptive ketika CPU memberikan kepada proses itu tidak bisa ditunda hingga selesai.

                                   ·          Preemptive bila sebuah proses datang dengan waktu prose lebih rendah dibandingkandengan waktu proses yang sedang dieksekusi oleh CPU maka proses yangwaktunya lebih rendah mendapatkan prioritas. Skema ini disebut juga Short ± R emaining Time First (SRTF).

3.      Prioritas

Penjadwalan SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadwalan Prioritas. Prioritas dapat diasosiasikan masing-masing proses dan CPU dialokasikan untuk proses dengan prioritas tertinggi.

Ada pun algoritma penjadwalan prioritas adalah sebagai berikut:

Setiap proses akan mempunyai prioritas mengganti pada saat pemakain time-slice habis.SJF adalah contoh penjadual prioritas dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya.Permasalahan yang muncul dalam penjadualan prioritas adalah indefinite blocking atau starvation.

4.      Round Robin

Algoritma Round Robin (RR) dirancang untuk sistem time sharing. Algoritma ini mirip dengan penjadwal FCFS, namun preemption ditambahkan untuk switch antara proses. Antrian ready diperlakukan atau dianggap sebagai antrian sirkular.CPU menglilingi antrian ready dan mengalokasikan masing-masing proses untuk interval waktu tertentu sampai satu time slice/quantum.Berikut algoritma untuk penjadwalan Rund Robin:

•     Setiap proses mendapat jatah waktu CPU (time slice/quantum) tertentuTime slice/quantum umumnya antara 10 ± 100 milidetik.Setelah timeslice/quantum (bilangan integer). Beberapa sistemmenggunakan integerdengan urutan kecil untuk proses dengan prioritasrendah, dan sistem lain juga bisa menggunakaninteger urutan kecil untuk  proses dengan prioritas tinggi. Tetapi dalam teks ini diasumsikan bahwainteger kecil merupakan prioritas tertinggi.

•  CPU diberikan ke proses dengan prioritas tertinggi (integer kecil adalah prioritas tertinggi).Dalam algoritma ini ada dua skema yaitu:

1. Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yangmemerlukan CPU. 
2.  Nonpreemptive: proses dengan prioritas tinggi akan maka proses akan di-preempt dan dipindahkan ke antrianready.Proses ini adil dan sangat sederhana. 
3. Referensi http://pandutrilaksono.blogspot.co.id/2014/05/algoritma-penjadwalan-cpu.html

Posted in: Sistem Operasi