Apa itu Penjadwalan Pertama Pekerjaan Terpendek?
Shortest Job First (SJF) adalah algoritma di mana proses yang memiliki waktu eksekusi terkecil dipilih untuk eksekusi berikutnya. Metode penjadwalan ini dapat 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-Preemptive
- SJF preemptive
Dalam tutorial Sistem Operasi ini, Anda akan mempelajari:
- Apa itu Penjadwalan Pertama Pekerjaan Terpendek?
- Karakteristik Penjadwalan SJF
- SJF Non-Preemptive
- SJF preemptive
- Keuntungan SJF
- Kekurangan / Kekurangan SJF
Karakteristik Penjadwalan SJF
- Ini terkait dengan setiap pekerjaan sebagai unit waktu untuk diselesaikan.
- Metode algoritme ini berguna untuk pemrosesan tipe batch, di mana menunggu pekerjaan selesai tidak penting.
- Ini dapat meningkatkan throughput proses dengan memastikan bahwa pekerjaan yang lebih pendek dieksekusi terlebih dahulu, sehingga mungkin memiliki waktu penyelesaian yang singkat.
- Ini meningkatkan hasil pekerjaan dengan menawarkan pekerjaan yang lebih pendek, yang harus dijalankan terlebih dahulu, yang sebagian besar memiliki waktu penyelesaian yang lebih pendek.
SJF Non-Preemptive
Dalam penjadwalan non-preemptive, setelah siklus CPU dialokasikan untuk diproses, proses akan menahannya hingga mencapai status menunggu atau dihentikan.
Pertimbangkan lima proses berikut yang masing-masing memiliki waktu burst dan waktu kedatangan yang unik.
| Proses Antrian | 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 diselesaikan. Ini akan melanjutkan eksekusi.
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 dan P5 berada dalam antrian tunggu.
Langkah 8) Pada time = 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 timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
SJF preemptive
Dalam Penjadwalan SJF Preemptive, pekerjaan dimasukkan ke dalam antrian siap saat mereka datang. Proses dengan waktu burst terpendek memulai eksekusi. Jika sebuah proses dengan waktu burst yang lebih pendek tiba, proses saat ini dihapus atau dicegah dari eksekusi, dan tugas yang lebih pendek dialokasikan untuk siklus CPU.
Pertimbangkan lima proses berikut:
| Proses Antrian | 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.
| Proses Antrian | 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. Tapi, P4 memiliki waktu burst yang lebih singkat. Ini akan melanjutkan eksekusi.
Langkah 2) Pada waktu = 2, proses P1 tiba dengan waktu burst = 6. Waktu burst lebih dari P4. Karenanya, 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 lebih dulu.
| Proses Antrian | 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 burst P1, P2, P3, dan P5 dibandingkan. Proses P2 dijalankan karena waktu burstnya paling sedikit. Proses P5 lebih dulu.
| Proses Antrian | 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 saat = 6, P2 sedang dieksekusi.
Langkah 7) Pada waktu = 7, P2 menyelesaikan eksekusinya. Waktu burst P1, P3, dan P5 dibandingkan. Proses P5 dijalankan karena waktu burstnya lebih singkat.
| Proses Antrian | 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 burst P1 dan P3 dibandingkan. Proses P1 dijalankan karena waktu burstnya lebih sedikit.
Langkah 9) Pada waktu = 15, P1 menyelesaikan eksekusinya. P3 adalah satu-satunya proses yang tersisa. Ini akan memulai eksekusi.
Langkah 10) Pada waktu = 23, P3 menyelesaikan eksekusinya.
Langkah 11) Mari kita hitung waktu tunggu rata-rata untuk contoh di atas.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Keuntungan SJF
Berikut manfaat / kelebihan menggunakan metode SJF:
- SJF sering digunakan untuk penjadwalan jangka panjang.
- Ini mengurangi waktu tunggu rata-rata selama algoritma FIFO (First in First Out).
- Metode SJF memberikan waktu tunggu rata-rata terendah untuk serangkaian proses tertentu.
- Ini sesuai untuk pekerjaan yang berjalan dalam batch, di mana 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.
- Mungkin optimal sehubungan dengan waktu penyelesaian rata-rata.
Kekurangan / Kekurangan SJF
Berikut adalah beberapa kekurangan / kekurangan dari algoritma SJF:
- Waktu penyelesaian pekerjaan harus diketahui lebih awal, tetapi sulit untuk diprediksi.
- Ini sering digunakan dalam sistem batch untuk penjadwalan jangka panjang.
- SJF tidak dapat diimplementasikan untuk penjadwalan CPU untuk jangka pendek. Itu karena tidak ada metode khusus untuk memprediksi lamanya ledakan CPU 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.
- Ini mengarah pada kelaparan yang tidak mengurangi waktu penyelesaian rata-rata.
- Sulit untuk mengetahui lamanya permintaan CPU yang akan datang.
- Waktu yang berlalu harus dicatat, yang menghasilkan lebih banyak overhead pada prosesor.
Ringkasan
- SJF adalah algoritma di mana proses yang memiliki waktu eksekusi terkecil dipilih untuk eksekusi berikutnya.
- Penjadwalan SJF dikaitkan dengan setiap pekerjaan sebagai unit waktu untuk diselesaikan.
- Metode algoritme ini berguna untuk pemrosesan tipe batch, di mana menunggu pekerjaan selesai tidak penting.
- Pada dasarnya ada dua jenis metode SJF 1) SJF Non-Preemptive dan 2) SJF Preemptive.
- Dalam penjadwalan non-preemptive, setelah siklus CPU dialokasikan untuk diproses, proses akan menahannya hingga mencapai status menunggu atau dihentikan.
- Dalam Penjadwalan SJF Preemptive, pekerjaan dimasukkan ke dalam antrian siap saat mereka datang.
- Meskipun proses dengan waktu burst singkat dimulai, proses saat ini dihapus atau didahului dari eksekusi, dan pekerjaan yang lebih singkat dijalankan pertama.
- SJF sering digunakan untuk penjadwalan jangka panjang.
- Ini mengurangi waktu tunggu rata-rata selama algoritma FIFO (First in First Out).
- Dalam penjadwalan SJF, waktu penyelesaian pekerjaan harus diketahui lebih awal, namun sulit untuk diprediksi.
- SJF tidak dapat diimplementasikan untuk penjadwalan CPU untuk jangka pendek. Itu karena tidak ada metode khusus untuk memprediksi lamanya ledakan CPU yang akan datang.