Pekerjaan Terpendek Pertama (SJF): Contoh Preemptive, Non-Preemptive

Apa yang dimaksud dengan Penjadwalan Pekerjaan Pertama Terpendek?

Pekerjaan Terpendek Pertama (SJF) adalah algoritma dimana proses yang memiliki waktu eksekusi terkecil dipilih untuk eksekusi berikutnya. Metode penjadwalan ini bisa bersifat preemptive atau non-preemptive. Ini secara signifikan mengurangi waktu tunggu rata-rata untuk proses lain yang menunggu eksekusi. Bentuk lengkap SJF adalah Pekerjaan Terpendek Pertama.

Pada dasarnya ada dua jenis metode SJF:

• SJF Non-Preemptif
• SJF pencegahan

Karakteristik Penjadwalan SJF

• Ini dikaitkan dengan setiap pekerjaan sebagai satuan waktu yang harus diselesaikan.
• Metode algoritme ini berguna untuk pemrosesan tipe batch, di mana menunggu pekerjaan selesai bukanlah hal yang penting.
• Hal ini dapat meningkatkan efisiensi proses dengan memastikan bahwa pekerjaan yang lebih singkat dieksekusi terlebih dahulu, sehingga berpotensi memiliki waktu penyelesaian yang lebih singkat.
• Hal ini meningkatkan produktivitas pekerjaan dengan menawarkan pekerjaan yang lebih singkat, yang sebaiknya dieksekusi terlebih dahulu, dan yang sebagian besar memiliki waktu penyelesaian yang lebih pendek.

SJF Non-Preemptif

Dalam penjadwalan non-preemptif, begitu siklus CPU dialokasikan ke suatu proses, proses tersebut akan memegangnya hingga mencapai keadaan menunggu atau dihentikan.

Perhatikan lima proses berikut, yang masing-masing memiliki waktu ledakan dan waktu kedatangan yang unik.

antrian proses	Waktu meledak	Jam kedatangan
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Langkah 0) Pada waktu = 0, P4 tiba dan memulai eksekusi.

Langkah 1) Pada waktu = 1, Proses P3 tiba. Namun P4 masih membutuhkan 2 unit eksekusi untuk selesai. Proses ini akan melanjutkan eksekusinya.

Langkah 2) Pada waktu = 2, proses P1 tiba dan ditambahkan ke antrian tunggu. P4 akan melanjutkan eksekusi.

Langkah 3) Pada waktu = 3, proses P4 akan menyelesaikan eksekusinya. Waktu burst P3 dan P1 dibandingkan. Proses P1 dijalankan karena waktu burstnya lebih sedikit dibandingkan dengan P3.

Langkah 4) Pada waktu = 4, proses P5 tiba dan ditambahkan ke antrian tunggu. P1 akan melanjutkan eksekusi.

Langkah 5) Pada waktu = 5, proses P2 tiba dan ditambahkan ke antrian tunggu. P1 akan melanjutkan eksekusi.

Langkah 6) Pada waktu = 9, proses P1 akan menyelesaikan eksekusinya. Waktu burst P3, P5, dan P2 dibandingkan. Proses P2 dijalankan karena waktu burstnya paling rendah.

Langkah 7) Pada waktu = 10, P2 sedang dieksekusi dan P3 serta P5 berada dalam antrian tunggu.

Langkah 8) Pada waktu = 11, proses P2 akan menyelesaikan eksekusinya. Waktu burst P3 dan P5 dibandingkan. Proses P5 dijalankan karena waktu burstnya lebih rendah.

Langkah 9) Pada waktu = 15, proses P5 akan menyelesaikan eksekusinya.

Langkah 10) Pada waktu = 23, proses P3 akan menyelesaikan eksekusinya.

Langkah 11) Mari kita hitung waktu tunggu rata-rata untuk contoh di atas.

Wait time
P4 = 0 - 0 = 0
P1 = 3 - 2 = 1
P2 = 9 - 5 = 4
P5 = 11 - 4 = 7
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2

SJF pencegahan

Dalam penjadwalan SJF preemptif, pekerjaan dimasukkan ke dalam antrian siap saat tiba. Proses dengan waktu burst terpendek memulai eksekusi. Jika proses dengan waktu burst yang lebih pendek tiba, proses saat ini dihapus atau dihentikan sementara dari eksekusi, dan pekerjaan yang lebih pendek dialokasikan siklus CPU.

Pertimbangkan lima proses berikut:

antrian proses	Waktu meledak	Jam kedatangan
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Langkah 0) Pada waktu = 0, P4 tiba dan memulai eksekusi.

antrian proses	Waktu meledak	Jam kedatangan
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Langkah 1) Pada waktu = 1, Proses P3 tiba. Tetapi P4 memiliki waktu eksekusi yang lebih singkat. Proses ini akan melanjutkan eksekusinya.

Langkah 2) Pada waktu = 2, proses P1 tiba dengan waktu burst = 6. Waktu burst lebih lama dari pada P4. Oleh karena itu, P4 akan melanjutkan eksekusi.

Langkah 3) Pada waktu = 3, proses P4 akan menyelesaikan eksekusinya. Waktu burst P3 dan P1 dibandingkan. Proses P1 dijalankan karena waktu burstnya lebih rendah.

Langkah 4) Pada waktu = 4, proses P5 akan tiba. Waktu burst P3, P5, dan P1 dibandingkan. Proses P5 dijalankan karena waktu burstnya paling rendah. Proses P1 didahului.

antrian proses	Waktu meledak	Jam kedatangan
P1	5 dari 6 tersisa	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Langkah 5) Pada waktu = 5, proses P2 akan tiba. Waktu eksekusi (burst time) dari P1, P2, P3, dan P5 dibandingkan. Proses P2 dieksekusi karena waktu eksekusinya paling singkat. Proses P5 dihentikan sementara (preempted).

antrian proses	Waktu meledak	Jam kedatangan
P1	5 dari 6 tersisa	2
P2	2	5
P3	8	1
P4	3	0
P5	3 dari 4 tersisa	4

Langkah 6) Pada waktu = 6, P2 sedang dieksekusi.

Langkah 7) Pada waktu = 7, P2 menyelesaikan eksekusinya. Waktu eksekusi (burst time) P1, P3, dan P5 dibandingkan. Proses P5 dieksekusi karena waktu eksekusinya lebih singkat.

antrian proses	Waktu meledak	Jam kedatangan
P1	5 dari 6 tersisa	2
P2	2	5
P3	8	1
P4	3	0
P5	3 dari 4 tersisa	4

Langkah 8) Pada waktu = 10, P5 akan menyelesaikan eksekusinya. Waktu eksekusi (burst time) P1 dan P3 dibandingkan. Proses P1 dieksekusi karena waktu eksekusinya lebih singkat.

Langkah 9) Pada waktu = 15, P1 menyelesaikan eksekusinya. P3 adalah satu-satunya proses yang tersisa. Proses ini akan mulai dieksekusi.

Langkah 10) Pada waktu = 23, P3 menyelesaikan eksekusinya.

Langkah 11) Mari kita hitung waktu tunggu rata-rata untuk contoh di atas.

Wait time
P4 = 0 - 0 = 0
P1 = (3 - 2) + 6 = 7
P2 = 5 - 5 = 0
P5 = 4 - 4 + 2 = 2
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6

Kelebihan SJF

Berikut adalah manfaat/keuntungan menggunakan metode SJF:

• SJF sering digunakan untuk penjadwalan jangka panjang.
• Algoritma ini mengurangi waktu tunggu rata-rata dibandingkan dengan algoritma FIFO (First In First Out).
• Metode SJF memberikan waktu tunggu rata-rata terendah untuk sekumpulan proses tertentu.
• Hal ini sesuai untuk pekerjaan yang dijalankan secara batch, dimana waktu pengoperasian telah diketahui sebelumnya.
• Untuk sistem batch penjadwalan jangka panjang, perkiraan waktu burst dapat diperoleh dari deskripsi pekerjaan.
• Untuk Penjadwalan Jangka Pendek, kita perlu memprediksi nilai waktu burst berikutnya.
• Ini mungkin merupakan solusi optimal jika dilihat dari waktu penyelesaian rata-rata.

Kekurangan/Kekurangan SJF

Berikut beberapa kekurangan/kelemahan algoritma SJF:

• Waktu penyelesaian pekerjaan memang harus diketahui lebih awal, namun sulit diprediksi.
• Ini sering digunakan dalam sistem batch untuk penjadwalan jangka panjang.
• SJF tidak dapat diimplementasikan untuk penjadwalan CPU untuk jangka pendek. Hal ini karena tidak ada metode khusus untuk memprediksi lamanya CPU burst yang akan datang.
• Algoritme ini dapat menyebabkan waktu penyelesaian yang sangat lama atau kelaparan.
• Membutuhkan pengetahuan tentang berapa lama suatu proses atau pekerjaan akan berjalan.
• Hal ini menyebabkan kelaparan yang tidak mengurangi waktu penyelesaian rata-rata.
• Sulit untuk mengetahui lamanya permintaan CPU yang akan datang.
• Waktu yang berlalu harus dicatat, yang mengakibatkan beban kerja prosesor yang lebih besar.

Pertanyaan Umum Demo Slot