Algoritma Penjadwalan Shortest Job First

Nama Proses	Saat Tiba	Lama Proses
A B C D E	0 0 0 0 0	7 10 2 4 8

Gambar Kasus I – antrian lima proses dengan saat tiba = 0

Nama Proses	Saat Tiba	Lama Proses
A B C D E	0 1 8 2 5	7 10 2 4 8

Gambar Kasus II – antrian lima proses saat tiba berbeda

Disebut juga sebagai teknik Proses Terpendek Dipertamakan (PTD). SJF merupakan penjadwalan dengan prioritas tanpa preempsi. Dasar prioritas adalah pendeknya proses. Makin pendek proses makin tinggi prioritasnya.

Pada algoritma ini di ditempuh dua langkah. Langkah pertama: menentukan urutan prioritas berdasarkan pendeknya proses yang dilayani. Langkah kedua: menentukan pada saat tertentu, proses mana yang perlu dilayani oleh prosesor.

Sekalipun urutan prioritas proses sudah ditentukan pada langkah pertama, namun masih ada masalah yang dapat menghambat pelaksanaan proses menurut urutan itu. masalah itu adalah masalah saat tiba dari setiap proses. Kalau pada saat prosesor siap menerima proses, serta proses terpendek sudah tiba, maka proses terpendek itulah yang dikerjakan oleh prosesor sesuai dengan pengaturan pada langkah pertama. Tetapi kalau pada saat prosesor sudah siap menerima proses. Sedangkan proses yang memperoleh giliran pada saat itu belum juga tiba, maka kita perlu mempunyai ketentuan tentang proses mana yang akan dikerjakan oleh prosesor.

Ketentuan itu adalah: pada saat prosesor siap menerima proses sedangkan proses terpendek yang memperoleh giliran pada saat itu belum juga tiba, maka lihat semua proses yang sudah tiba pada saat itu. Proses yang sudah rampung diabaikan. Dari proses yang sudah tiba tapi belum diproses itu dipilih proses terpendek, dan proses terpendek itulah yang pada saat itu dikerjakan oleh prosesor.

Kalau dalam penentuan urutan proses ini, ditemukan dua atau lebih proses yang memiliki prioritas sama, maka pelayanan dilakukan berdasarkan urutan antrian diantara proses berprioritas sama itu.

Lihat contoh kasus I pada bagian atas postingan ini yang menunjukkan sekumpulan proses A, B, C, D, dan E yang mempunyai saat tiba yang sama yaitu 0. Namun lama proses mereka berbeda. Berdasarkan lama proses yang berbeda ini, pada langkah pertama, kita menyusun prioritas berdasarkan pendeknya proses, maka urutan proses berubah menjadi C, D, A, E, dan B. Karena semua proses sudah tiba, maka langkah kedua tidak mengalami kesulitan. Seperti tampak pada Gambar dibawah ini urutan antriannya berubah sehingga sesuai dengan urutan prioritas.

Tampak disini bahwa algoritma SJF menyebabkan rerata lama tanggap semua proses itu menjadi 14,6 satuan waktu. Rerata ini menjadi lebih singkat jika dibandingkan dengan rerata lama tanggap untuk penjadwalan FCFS.

Nama Proses	Saat Tiba	Lama Proses	Saat Mulai	Saat Rampung	Waktu Sia-Sia	Lama Tanggap
C D A E B	0 0 0 0 0	2 4 7 8 10	0 2 6 13 21	2 6 13 21 31	0 2 6 13 21	2 6 13 21 31
				Jumlah Rerata	42 8,4	73 14,6

Gambar Ujuk kerja prosesor dengan algoritma SJF untuk kasus I

Selanjutnya lihat contoh II untuk sekumpulan proses dengan saat tiba tidak sama seperti pada Gambar paling atas posting ini (kasus II) mula-mula kita menyusun urutan proses itu berdasarkan prioritas.

Dalam pelaksanaannya, kita mulai dari saat = 0. Pada saat = 0 ini, proses terpendek C belum tiba. Bahkan proses satu-satunya yang sudah tiba adalah proses A. Karena itu pada saat = 0, proses A yang dikerjakan. Untuk lebih jelasnya perhatikan barisan saat dibawah. Proses A selesai ketika saat = 7. Ketika itu proses yang telah tiba adalah proses B, D, dan E, dan yang terpendek dari keduanya adalah D, sehingga proses berikutnya adalah D. Ketika D selesai saat = 11, dan proses yang telah tiba dalam ready queue adalah B, C dan E. Dan yang terpendek dari ketiganya adalah C, maka C dikerjakan dahulu. Ketika C telah selesai diproses oleh CPU, saat = 13 berarti sisa proses yang menunggu adalah B dan E, dan yang terpendek dari keduanya adalah E, maka E didahulukan, setelah selesai barulah B diproses. Inilah perbedaan yang terjadi jika algoritma SJF diterapkan pada beberapa proses yang memiliki waktu tiba tidak sama.

Dengan demikian didapatkan bahwa A diproses mulai saat = 0 hingga 7, D mulai saat = 7 hingga 11, C mulai saat = 11 hingga 13, E mulai saat = 13 hingga 21, dan B mulai saat = 21 hingga 31.

Nama Proses	Saat Tiba	Lama Proses	Saat Mulai	Saat Rampung	Waktu Sia-Sia	Lama Tanggap
A D C E B	0 2 8 5 1	7 4 2 8 10	0 7 11 13 21	7 11 13 21 31	0 5 3 8 20	7 9 5 16 30
				Jumlah Rerata	36 7,2	67 13,4

Gambar Ujuk kerja prosesor dengan algoritma SJF untuk kasus II

Gambar Barisan Saat Algoritma Shortest Job First

Popularity: 6% [?]