Preemptive Shortest
Job First (PSJF)
Nama Proses Saat Tiba Lama Proses A
B
C
D
E0
0
0
0
07
10
2
4
8Gambar Kasus I – antrian lima proses dengan saat tiba = 0
Nama Proses Saat Tiba Lama Proses A
B
C
D
E0
1
8
2
57
10
2
4
8Gambar Kasus II – antrian lima proses saat tiba berbeda
Preemptive Shortest Job First (PSJF) disebut juga sebagai teknik Proses Terpendek Dipertamakan Preempsi (PTDP). PSJF merupakan penjadwalan dengan prioritas dan dengan preempsi. Prioritas didasarkan kepada pendeknya sisa proses. Makin pendek sisa proses makin tinggi prioritasnya. Selanjutnya dengan ketentuan ini, ketika tiba, proses terpendek di bagian belakang antrian tidak saja berpindah ke bagian depan antrian, melainkan juga melalui preempsi, mengeluarkan proses yang pada saat itu berada di dalam proses (jika ada).
Digunakan dua langkah untuk melihat pelaksanaan penjadwalan ini. Langkah pertama: setiap kali, perhatikan saat proses tiba atau saat proses rampung. Langkah kedua: hitung lama sisa proses dari semua proses yang ada pada saat itu. Kalau ada proses dengan sisa proses yang lebih pendek dari sisa proses pada proses yang sedang dikerjakan, maka atas dasar preempsi, proses yang sedang dikerjakan itu dikeluarkan dari prosesor. Dan sebagai gantinya, proses dengan sisa terpendek itulah yang dikerjakan oleh prosesor.
Di sini muncul pertanyaan. Bagaimana jika proses yang tiba berikut itu memiliki lama proses yang sama dengan sisa proses pada proses yang sudah ada. Apakah preempsi terjadi juga? Jika lama proses atau sisa proses adalah sama, maka perlakuan diatur berdasarkan urutan antrian yang ada.
Agar lebih jelas, mari melihat contoh pada kasus II kita menemukan sekumpulan proses dengan tiba berbeda seperti tampak pada Gambar berikut.
| Nama | Saat | Lama | Saat | Saat | Waktu | Lama |
| A | 0 | 7 | 0 | 7 | 0 | 7 |
|
|
|
|
| Jumlah Rerata | 36 | 67 |
Gambar Unjuk kerja prosesor dengan algoritma PSJF untuk kasus II
Gambar Barisan saat algoritma PSJF untuk kasus II
Algoritma Penjadwalan
Shortest Job First
Nama Proses Saat Tiba Lama Proses A
B
C
D
E0
0
0
0
07
10
2
4
8Gambar Kasus I – antrian lima proses dengan saat tiba = 0
Nama Proses Saat Tiba Lama Proses A
B
C
D
E0
1
8
2
57
10
2
4
8Gambar 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
Algotima Penjadwalan
First Come First Served
Nama Proses Saat Tiba Lama Proses A
B
C
D
E0
0
0
0
07
10
2
4
8Gambar Kasus I – antrian lima proses dengan saat tiba = 0
Nama Proses Saat Tiba Lama Proses A
B
C
D
E0
1
8
2
57
10
2
4
8Gambar Kasus II – antrian lima proses saat tiba berbeda
Algoritma First Come First Served (FCFS) disebut juga sebagai teknik Pertama Tiba Pertama Dilayani (PTPD). FCFS merupakan penjadwalan tanpa prioritas dan tanpa preempsi (lihat posting penjadwalan cpu). Karena itu, proses ini serentak tersusun dalam antrian murni.
Pada FCFS, proses yang tiba lebih dahulu akan dilayani lebih dahulu. Kalau proses itu tiba pada waktu yang sama, maka pelayanan dilakukan berdasarkan urutan mereka pada antrian. Tidak menjadi soal apakah waktu proses mereka singkat atau lama. Untuk dapat dilayani oleh prosesor, proses di antrian belakang harus menunggu sampai semua proses di depannya rampung dilaksanakan.
Kita dapat langsung memasukkan proses ini ke dalam tabel proses pada kerja prosesor. Pada contoh kasus I, proses B hanya dapat dilaksanakan setelah proses A rampung dilaksanakan. Proses C hanya dapat dilaksanakan setelah proses B rampung dilaksanakan. Demikian seterusnya sehingga didapatkan nilai seperti pada tabel Gambar berikut.
| Nama Proses | Saat Tiba | Lama Proses | Saat Mulai | Saat Rampung | Waktu Sia-Sia | Lama Tanggap |
| A B C D E | 0 0 0 0 0 | 7 10 2 4 8 | 0 7 17 19 23 | 7 17 19 23 31 | 0 7 17 19 23 | 7 17 19 23 31 |
| Jumlah Rerata | 66 13,2 | 97 19,4 |
Gambar Ujuk kerja prosesor dengan algoritma FCFS untuk kasus I
Tampak di sini bahwa rerata lama tanggap adalah 19,4 satuan waktu. Nilai ini cukup besar dibandingkan dengan lama proses dari masing-masing proses itu. Berikut ilustrasi untuk contoh kasus kedua .
| Nama Proses | Saat Tiba | Lama Proses | Saat Mulai | Saat Rampung | Waktu Sia-Sia | Lama Tanggap |
| A B D E C | 0 1 2 5 8 | 7 10 4 8 2 | 0 7 17 21 29 | 7 17 21 29 31 | 0 6 15 16 21 | 7 16 19 24 23 |
| Jumlah Rerata | 58 11,6 | 89 17,8 |
Gambar Ujuk kerja prosesor dengan algoritma FCFS untuk kasus II
Pada Gambar Contoh kasus di bagian atas postingan ini, proses belum terurut sesuai waktu tibanya, oleh karena itu setelah diurut berdasarkan waktu tibanya, maka antrian menjadi A, B, D, E, dan C. Tampak di sini bahwa rerata lama tanggap adalah 17,8 satuan waktu. Nilai ini masih cukup besar dibandingkan dengan lama proses dari masing-masing proses tetapi masih lebih kecil dari rerata lama tanggap untuk kasus I. Perbedaan dengan contoh pertama terletak pada perhitungan lama tanggap. Kalau pada contoh pertama, lama tanggap sama dengan saat rampung, maka di sini mereka tidak sama karena saat tiba proses tidaklah sama.
Kedua contoh ini menunjukkan bahwa lama tanggap sangat dipengaruhi oleh lama proses pada proses yang terletak di bagian depan antrian. Jika lama proses pada proses di bagian depan antrian itu besar, maka proses dengan lama proses yang singkat di bagian belakang antrian, tetap harus lama menunggu, sebelum mereka dapat dilayani oleh prosesor. Itu sebabnya penjadwalan FCFS ini kurang menguntungkan bagi keseluruhan pelayanan.
Salah satu cara untuk mengatasi hal itu adalah melalui prioritas. Proses dengan lama proses yang singkat memperoleh prioritas untuk didahulukan ke prosesor. Makin singkat masa prosesnya, makin cepat proses itu dilayani oleh prosesor. Penjadwalan ini dikenal sebagai Proses Terpendek Dipertamakan (PTD)
Tidak ada komentar:
Posting Komentar