Apakah Penjadualan Pertama Pekerjaan Terpendek?
Shortest Job First (SJF) adalah algoritma di mana proses yang mempunyai masa pelaksanaan terkecil dipilih untuk pelaksanaan berikutnya. Kaedah penjadualan ini boleh bersifat preemptive atau non-preemptive. Ini secara signifikan mengurangkan purata masa menunggu proses lain yang menunggu pelaksanaan. Bentuk penuh SJF adalah Pekerjaan Terpendek Pertama.
Terdapat dua jenis kaedah SJF:
- SJF Bukan Preprive
- SJF Preemptive
Dalam tutorial Sistem Operasi ini, anda akan belajar:
- Apakah Penjadualan Pertama Pekerjaan Terpendek?
- Ciri Penjadualan SJF
- SJF Bukan Preprive
- SJF Preemptive
- Kelebihan SJF
- Kekurangan / Kekurangan SJF
Ciri Penjadualan SJF
- Ia dikaitkan dengan setiap pekerjaan sebagai satu unit masa untuk diselesaikan.
- Kaedah algoritma ini berguna untuk pemprosesan jenis kumpulan, di mana menunggu pekerjaan selesai tidak begitu penting.
- Ini dapat meningkatkan proses proses dengan memastikan bahawa pekerjaan yang lebih pendek dilaksanakan terlebih dahulu, oleh itu mungkin mempunyai waktu pemulihan yang singkat.
- Ini meningkatkan output pekerjaan dengan menawarkan pekerjaan yang lebih pendek, yang harus dilaksanakan terlebih dahulu, yang kebanyakannya mempunyai waktu perputaran yang lebih pendek.
SJF Bukan Preprive
Dalam penjadwalan bukan preemptive, setelah siklus CPU diperuntukkan untuk diproses, prosesnya menahannya hingga mencapai keadaan menunggu atau dihentikan.
Pertimbangkan lima proses berikut yang masing-masing mempunyai waktu pecah dan waktu ketibaannya yang tersendiri.
| Baris Proses | Masa pecah | Masa ketibaan |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Langkah 0) Pada masa = 0, P4 tiba dan memulakan pelaksanaan.
Langkah 1) Pada masa = 1, Proses P3 tiba. Tetapi, P4 masih memerlukan 2 unit pelaksanaan untuk diselesaikan. Ia akan terus dilaksanakan.
Langkah 2) Pada masa = 2, proses P1 tiba dan ditambahkan ke barisan menunggu. P4 akan meneruskan pelaksanaan.
Langkah 3) Pada masa = 3, proses P4 akan selesai pelaksanaannya. Masa pecah P3 dan P1 dibandingkan. Proses P1 dijalankan kerana masa pecahnya kurang berbanding P3.
Langkah 4) Pada masa = 4, proses P5 tiba dan ditambahkan ke barisan menunggu. P1 akan meneruskan pelaksanaan.
Langkah 5) Pada masa = 5, proses P2 tiba dan ditambahkan ke barisan menunggu. P1 akan meneruskan pelaksanaan.
Langkah 6) Pada masa = 9, proses P1 akan menyelesaikan pelaksanaannya. Masa pecah P3, P5, dan P2 dibandingkan. Proses P2 dijalankan kerana masa pecahnya adalah yang paling rendah.
Langkah 7) Pada masa = 10, P2 sedang dijalankan dan P3 dan P5 berada dalam barisan menunggu.
Langkah 8) Pada masa = 11, proses P2 akan menyelesaikan pelaksanaannya. Masa pecah P3 dan P5 dibandingkan. Proses P5 dijalankan kerana masa pecahnya lebih rendah.
Langkah 9) Pada masa = 15, proses P5 akan menyelesaikan pelaksanaannya.
Langkah 10) Pada masa = 23, proses P3 akan menyelesaikan pelaksanaannya.
Langkah 11) Mari kita mengira purata masa menunggu 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 Penjadualan SJF Preemptive, pekerjaan dimasukkan ke dalam barisan siap ketika mereka datang. Proses dengan waktu pecah terpendek bermula pelaksanaan. Sekiranya proses dengan waktu pecah lebih pendek tiba, proses semasa dikeluarkan atau diprioritaskan dari pelaksanaan, dan pekerjaan yang lebih pendek diperuntukkan kitaran CPU.
Pertimbangkan lima proses berikut:
| Baris Proses | Masa pecah | Masa ketibaan |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Langkah 0) Pada masa = 0, P4 tiba dan memulakan pelaksanaan.
| Baris Proses | Masa pecah | Masa ketibaan |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Langkah 1) Pada masa = 1, Proses P3 tiba. Tetapi, P4 mempunyai masa pecah yang lebih pendek. Ia akan terus dilaksanakan.
Langkah 2) Pada masa = 2, proses P1 tiba dengan masa pecah = 6. Waktu pecah lebih banyak daripada masa P4. Oleh itu, P4 akan meneruskan pelaksanaan.
Langkah 3) Pada masa = 3, proses P4 akan selesai pelaksanaannya. Masa pecah P3 dan P1 dibandingkan. Proses P1 dijalankan kerana masa pecahnya lebih rendah.
Langkah 4) Pada masa = 4, proses P5 akan tiba. Masa pecah P3, P5, dan P1 dibandingkan. Proses P5 dijalankan kerana masa pecahnya paling rendah. Proses P1 diutamakan.
| Baris Proses | Masa pecah | Masa ketibaan |
| P1 | 5 daripada 6 masih ada | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Langkah 5) Pada masa = 5, proses P2 akan tiba. Masa pecah P1, P2, P3, dan P5 dibandingkan. Proses P2 dijalankan kerana masa pecahnya paling sedikit. Proses P5 dipratentukan.
| Baris Proses | Masa pecah | Masa ketibaan |
| P1 | 5 daripada 6 masih ada | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 daripada 4 masih ada | 4 |
Langkah 6) Pada masa = 6, P2 sedang dijalankan.
Langkah 7) Pada masa = 7, P2 menyelesaikan pelaksanaannya. Masa pecah P1, P3, dan P5 dibandingkan. Proses P5 dijalankan kerana masa pecahnya lebih sedikit.
| Baris Proses | Masa pecah | Masa ketibaan |
| P1 | 5 daripada 6 masih ada | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 daripada 4 masih ada | 4 |
Langkah 8) Pada masa = 10, P5 akan menyelesaikan pelaksanaannya. Masa pecah P1 dan P3 dibandingkan. Proses P1 dijalankan kerana masa pecahnya kurang.
Langkah 9) Pada masa = 15, P1 menyelesaikan pelaksanaannya. P3 adalah satu-satunya proses yang tinggal. Ia akan mula dilaksanakan.
Langkah 10) Pada masa = 23, P3 menyelesaikan pelaksanaannya.
Langkah 11) Mari kita mengira purata masa menunggu 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
Kelebihan SJF
Berikut adalah kebaikan / kebaikan menggunakan kaedah SJF:
- SJF sering digunakan untuk penjadualan jangka panjang.
- Ini mengurangkan purata masa menunggu berbanding algoritma FIFO (First in First Out).
- Kaedah SJF memberikan masa menunggu purata terendah untuk satu set proses tertentu.
- Sangat sesuai untuk pekerjaan yang dijalankan secara berkelompok, di mana masa berjalan diketahui sebelumnya.
- Untuk sistem penjadualan jangka panjang, anggaran masa pecah boleh didapati dari keterangan pekerjaan.
- Untuk Penjadualan Jangka Pendek, kita perlu meramalkan nilai masa pecah berikutnya.
- Mungkin optimum dengan mengambil kira masa pemulihan.
Kekurangan / Kekurangan SJF
Berikut adalah beberapa kekurangan / kekurangan algoritma SJF:
- Masa penyelesaian pekerjaan mesti diketahui lebih awal, tetapi sukar untuk diramalkan.
- Ia sering digunakan dalam sistem kumpulan untuk penjadualan jangka panjang.
- SJF tidak dapat dilaksanakan untuk penjadualan CPU untuk jangka pendek. Ini kerana tidak ada kaedah khusus untuk meramalkan jangka masa pecah CPU yang akan datang.
- Algoritma ini boleh menyebabkan waktu putaran atau kelaparan yang sangat lama.
- Memerlukan pengetahuan tentang berapa lama proses atau pekerjaan akan dijalankan.
- Ia membawa kepada kebuluran yang tidak mengurangkan masa pemulihan purata.
- Sukar untuk mengetahui panjang permintaan CPU yang akan datang.
- Masa yang berlalu harus dicatat, yang menghasilkan lebih banyak overhead pada pemproses.
Ringkasan
- SJF adalah algoritma di mana proses yang mempunyai masa pelaksanaan terkecil dipilih untuk pelaksanaan berikutnya.
- Penjadualan SJF dikaitkan dengan setiap pekerjaan sebagai satu unit masa untuk diselesaikan.
- Kaedah algoritma ini berguna untuk pemprosesan jenis kumpulan, di mana menunggu pekerjaan selesai tidak begitu penting.
- Pada dasarnya terdapat dua jenis kaedah SJF 1) SJF Bukan Preemptive dan 2) SJF Preemptive.
- Dalam penjadwalan bukan preemptive, setelah siklus CPU diperuntukkan untuk diproses, prosesnya menahannya hingga mencapai keadaan menunggu atau dihentikan.
- Dalam Penjadualan SJF Preemptive, pekerjaan dimasukkan ke dalam barisan siap ketika mereka datang.
- Walaupun proses dengan waktu ledakan pendek bermula, proses saat ini dikeluarkan atau diprioritaskan dari pelaksanaan, dan pekerjaan yang lebih pendek dilaksanakan 1.
- SJF sering digunakan untuk penjadualan jangka panjang.
- Ini mengurangkan purata masa menunggu berbanding algoritma FIFO (First in First Out).
- Dalam penjadualan SJF, masa penyelesaian pekerjaan mesti diketahui lebih awal, tetapi sukar untuk diramalkan.
- SJF tidak dapat dilaksanakan untuk penjadualan CPU untuk jangka pendek. Ini kerana tidak ada kaedah khusus untuk meramalkan jangka masa pecah CPU yang akan datang.