ALOGRITMA PENJADWALAN NON-PREEMPTIVE

Algoritma Penjadwalan First In First Out (FIFO)

Merupakan penjadwalan Non Preemptive dan tidak berprioritas.  Algoritma ini jarang digunakan secara mandiri, biasanya dikombinasikan dengan skema lain.

Ketentuan yang dipakai ialah :

• Proses-proses diberi jatah waktu processor berdasarkan waktu kedatangan.
• Saat proses mendapat jatah waktu processor, proses dijalankan sampai selesai.

Contoh :

Table berikut menggambarkan dari beberapa proses yang akan dilayani oleh satu prosesor.

Proses	Arrival Time	Burst Time
P1	0	15
P2	1	8
P3	3	10
P4	4	3

Gantt chartnya adalah:

Proses	Waiting Time
P1	0 – 0 = 0
P2	15 – 1 = 14
P3	(15 + 8) – 3 = 20
P4	(15 + 8 + 10) – 4 = 29

  

Average Waiting Time(AWT) : (0 + 14 + 20 + 29) / 4 = 15,75 ms

Algoritma Penjadwalan Shortest Job First (SJF)

Merupakan penjadwalan Non Preemptive dan tidak berprioritas, jarang digunakan, menggunakan asumsi waktu jalan proses sudah diketahui, menjadwalkan proses dengan waktu terpendek dijalankan lebih dahulu, efisiensi tinggi dan time around time rendah. Masalah yang terjadi : tidak dapat mengetahui ukuran job saat job masuk dan untuk proses yang datang tidak bersamaan menggunakan penetapan dinamis.

Contoh :

Table berikut menggambarkan dari beberapa proses yang akan dilayani oleh satu prosesor. 

Proses	Arrival Time	Burst Time
P1	0	10
P2	1	15
P3	1	12
P4	4	8
P5	6	5

Gantt chartnya adalah:

Proses	Waiting Time
P1	0 – 0 = 0
P2	35 – 1 = 34
P3	23 – 1 = 22
P4	15 – 4 = 11
P5	10 – 6 = 4

Average Waiting Time(AWT) : (0 + 34 + 22 + 11 + 4) / 5 = 14,2 ms

Algoritma Penjadwalan HighestRatio Next

Merupakan penjadwalan Non Preemptive dan berprioritas dinamis. Algoritma ini untuk mengkoreksi kelemahan SJF, dan prioritas proses merupakan fungsi waktu layanan dan jumlah waktu tunggu proses.

Prioritas dinamis HRN dihitung berdasarkan rumus :

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

Dari rumus diatas dapat diambil kesimpulan : job lebih pendek berprioritas lebih baik dan proses yang telah menunggu lebih lama mempunyai kesempatan lebih bagus.

Algoritma Penjadwalan Multiple Feedback Queue

Merupakan penjadwalan Non Preemptive dan berprioritas dinamis. Algoritma ini untuk mencegah banyaknya swapping dengan proses-proses yang sangat banyak menggunakan processor diberi jatah waktu lebih banyak dalam satu waktu.

Ketentuan yang dipakai ialah :

• Jalankan proses pada kelas tertinggi
• Jika proses menggunakan seluruh kwanta yang dialokasikan, maka prioritasnya diturunkan
• Proses yang masuk untuk pertama kali ke system langsung diberi kelas tertinggi

B. SJF (Shortest Job First)

Penjadwalan ini mengasumsikan waktu jalan proses sampai selesai diketahui sebelumnya. mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

Contoh :

Terdapat empat proses (job) yaitu A,B,C,D dengan waktu jalannya masing-masing adalah 8,4,4 dan 4 menit. Apabila proses-proses tersebut dijalankan, maka turn around time untuk A adalah 8 menit, untuk B adalah 12, untuk C adalah 16 dan untuk D adalah 20. Untuk menghitung rata-rata turn around time seluruh proses adalah dengan menggunakan rumus :
( 4a + 3b + 2c + 1d ) / 4

Dengan menggunakan rumus, maka dapat dihitung turn around time-nya sebagai berikut (belum memperhatikan shortest job first, lihat gambar a) :
= ( 4a + 3b + 2c + 1d ) / 4
= ( 4x8 + 3x4 + 2x4 + 1x4 ) / 4
= ( 32 + 12 + 8 + 4 ) / 4
= 56 / 4
= 14 menit

Apabila keempat proses tersebut menggunakan penjadwalan shortest job fisrt (lihat gambar b), maka turn around time untuk B adalah 4, untuk C adalah 8, untuk D adalah 12 dan untuk A adalah 20, sehingga rata-rata turn around timenya adalah sebagai berikut :

= ( 4a + 3b + 2c + 1d ) / 4
= ( 4x4 + 3x4 + 2x4 + 1x8 ) / 4
= ( 16 + 12 + 8 + 8 ) / 4
= 44 / 4
= 11 menit



Jelas bahwa a memberikan nilai kontribusi yang besar, kemudian b, c dan d. Karena SJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untuk proses interaktif. Umumnya proses interaktif memiliki pola, yaitu menunggu perintah, menjalankan perintah, menunggu perintah dan menjalankan perintah, begitu seterusnya.


Masalah yang muncul adalah :
· Tidak mengetahui ukuran job saat job masuk.

Untuk mengetahui ukuran job adalah dengan membuat estimasi berdasarkan kelakukan sebelumnya.
· Proses yang tidak datang bersamaan, sehingga penetapannya harus dinamis. Penjadwalan ini jarang digunakan, karena merupakan kajian teoritis untuk pembandingan turn around time.


C. HRN (Highest Ratio Next)

Merupakan :

- Penjadwalan berprioritas dinamis.
- Penjadwalan untuk mengoreksi kelemahan SJF.
- Adalah strategi penjadwalan dengan prioritas proses tidak hanya merupakan fungsi waktu layanan tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, proses berjalan sampai selesai.

Prioritas dinamis HRN dihitung berdasarkan rumus :

Prioritas = (waktu tunggu + waktu layanan ) / waktu layanan Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek berprioritas lebih baik, karena waktu tunggu sebagai pembilang maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus. Disebut HRN, karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani.

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

SJF (Shortest 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.

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 (SRF).
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:
Terdapat 4 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma SRF.

Maka gantt chart kedatangan proses:

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

AWT = (4+0+13+5)/4 = 5,5 ms

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.

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.

KESIMPULAN

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

Postingan saya kali ini mengenai bagaimana cara menghitung average waiting time daripada kriteria penjadwalan FCFS yang saya dapatkan di sekolah. Untuk lebih jelasnya saya berikan contoh kasus dan penyelesaiannya.

Dari tabel di atas, tentukan average waiting time dengan menggunakan prinsip FCFS!

Saya jelaskan sedikit disini, Arrival Times adalah waktu ketika proses berada di memori utama, sebelum proses tersebut mulai dikerjakan oleh CPU. Burst Times adalah waktu yang dibutuhkan untuk menyelesaikan keseluruhan proses.

Nah.. setelah mengetahui apa maksud daripada tabel di atas, barulah kita mulai mengerjakan soalnya.

• Hal pertama yang harus dilakukan yaitu menggambarkan kronologi eksekusi proses di atas dengan Gantt Chart. Berikut gambarnya:

Penjelasan:

Mengenai penjelasan dari Gantt Chart di atas akan saya bahas satu per satu di bagian ini. Ketika CPU tidak mengerjakan sesuatu atau dalam posisi 0 datang sebuah proses yang dinamakan P1 yang membutuhkan waktu penyelesaian yang berjumlah 8. Karena FCFS ini melakukan proses menurut kapan proses itu datang atau yang bisa kita katakan sebagai proses antrian, maka proses selanjutnya akan di kerjakan setelah proses yang berada di depannya selesai untuk di kerjakan. Tadi proses P1 selesai di kerjakan di 8, sementara itu ada P2,P3,dan P4 yang sedang menunggu untuk di kerjakan selanjutnya.

Ketika  P1 selesai dikerjakan di 8, maka akan di lanjutkan dengan pengerjaan P2 yang memiliki waktu pengerjaan sebesar 7, sehingga proses P2 akan selesai di kerjakan pada posisi 15. P1 dan P2 sudah selesai pengerjaannya, tinggal menunggu pengerjaan daripada P3 dan P4. Dan begitupun selanjutnya sampai P4 selesai untuk di proses. Saya ingatkan di sini, FCFS dalam prosesnya tidak mengizinkan sebuah penyelaan dari segi apapun, walaupun proses yang menunggu memiliki prioritas yang lebih tinggi.

• Hal kedua yang dilakukan untuk menghitung average waiting time yaitu dengan menghitung berapa lama waktu tunggu yang dihasilkan oleh proses tersebut. Untuk menhitungnya dapat dilakukan dengan cara mengurangkan waktu eksekusi dengan waktu datang.

 Jadi lama waktu tunggu dari keseluruhan proses tersebut berjumlah 28.

• Hal ketiga dan juga hal yang terakhir yang harus dilakukan yaitu menghitung Average Waiting Time dari semua proses tersebut, yaitu dengan cara sebagai berikut:

Nah.. begitulah cara menghitung Average Waiting Time dari Algoritma penjadwalan FCFS, semoga postingan ini dapat bermanfaat bagi teman-teman semua dan terimakasih atas kunjungannya.