 |
| Algoritma Penjadwalan (Schedulling Algorithm) |
Substansi:
- Apa itu Schedulling?
- Mengapa harus ada Schedulling?
- Apa saja kategori scheduling?
- Apa saja penjadwalan alternatif itu?
- First come, first served (fcfs) atau First In, First Out (FIFO)
- Shorted Job First Scheduller (SJF)
- Penjadwalan Berprioritas
- Multiple Feedback Queue (MFQ)
- Shortest Remaining First (SRF)
- Penjadwalan Round Robin
- Highest Response Ratio Next (HRN)
- Contoh Pembahasan Soal Penjadwalan Alternatif
1. Apa itu Schedulling?
Dalam sistem komputer scheduling merupakan pengaturan penggunaan waktu prosesor bagi sejumlah proses yang saling berkompetisi untuk mendapatkan resource yang dibutuhkan.
2. Mengapa harus ada Schedulling?
- Agar setiap proses dapat dilayani secara seimbang / adil.
- Agar tidak terjadi starvation.
- Agar efisien dalam penggunaan waktu prosesor
- Agar dapat meminimalkan terjadinya overhead
- Supaya response time dapat terpenuhi
- Supaya dapat memaksimalkan throughput
- Untuk menghindari terjadinya deadlock
3. Apa saja kategori scheduling?
- Penjadwalan Jangka Panjang (Long-Term), yaitu adalah keputusan untuk menambah suatu proses kedalam kelompok proses yang akan dieksekusi.
- Penjadwalan Jangka Menengah (Medium-Term), adalah suatu keputusan untuk menambahkan sejumlah proses (sebagian atau seluruhnya) kedalam main memory.
- Penjadwalan Jangka Pendek (Short-Term), adalah suatu keputusan untuk memilih proses mana yang akan dieksekusi diantara sejumlah proses yang sudah siap dieksekusi.
- Penjadwalan I/O, adalah suatu keputusan untuk memilih proses mana yang akan diberi kesempatan untuk menggunakan I/O device diantar sejumlah proses yang sama-sama akan menggunakan I/O device tersebut.
4. Apa saja penjadwalan alternatif itu?
Terdapat beberapa jenis penjadwalan alternatif, diantaranya adalah:- First Come First Serve (FCFS)
- Round Robin (RR)
- Shortest Process Next (SPN)
- Shortest Remaining Time (SRT)
- Highest Response Ratio Next (HRRN)
- Feedback (FB)
5. First come, first served (fcfs) atau First In, First Out (FIFO)
Mempunyai ciri-ciri sebagai berikut :- Penjadwalan nonpreemptive
- Penjadwalan tanpa prioritas
- Proses diberi jatah waktu proses berdasarkan waktu kedatangan
- Begitu proses mendapat jatah waktu pemroses, proses dijalankan sampai selesai
- Average Waiting Time (AWT, rata-rata waktu tunggu) cukup besar
Contoh 1:
Nama proses | Saat Tiba | Burst Time |
P1 | 0 | 22 |
P2 | 1 | 4 |
P3 | 2 | 3 |
Gantt Chart
P1 | P2 | P3 |
Tabel Proses
Nama Proses | Saat Tiba | Burst Time | Saat Mulai | Saat selesai | Waktu Tunggu | Waktu Tanggap |
P1 | 0 | 22 | 0 | 22 | 0 | 22 |
P2 | 1 | 4 | 22 | 26 | 21 | 25 |
P3 | 2 | 3 | 26 | 29 | 24 | 27 |
45 | 74 | |||||
Rata-rata waktu tunggu : 45/3 = 15
Rata-rata waktu tanggap = 74/3 = 24,7
Hal ini akan lain hasilnya jika waktu kedatangannya berbeda
Contoh 2:
Nama proses | Saat Tiba | Burst Time |
P1 | 0 | 5 |
P2 | 2 | 4 |
P3 | 4 | 3 |
Gantt Chart
Nama Proses | Saat Tiba | Burst Time | Saat Mulai | Saat selesai | Waktu Tunggu | Waktu Tanggap |
P1 | 0 | 5 | 0 | 5 | 0 | 5 |
P2 | 2 | 4 | 5 | 9 | 3 | 7 |
P3 | 4 | 3 | 9 | 12 | 5 | 8 |
8 | 20 | |||||
Rata-rata waktu tunggu : 8/3 = 2,6
Rata-rata waktu tanggap = 20/3 = 6,6
6. Shorted Job First Scheduller (SJF)
- Proses yang mempunyai cpu burst paling kecil dilayani lebih dahulu
- Nonpreemptive
- Dengan prioritas, dasar prioritasnya adalah pendeknya proses
7. Penjadwalan Berprioritas
Mempunyai ciri-ciri :
- Tiap-tiap proses diberi prioritas dan proses dengan prioritas tertinggi akan mendapat jatah waktu pemroses lebih dulu
- Prioritas biasanya menyangkut masalah waktu, memori yang dibutuhkan,banyaknya file yang boleh dibuka, perbandingan rata-rata I/O burst dengan rata-rata cpu burst.
- Bisa bersifat preemptive maupun nonpreemptive, Jika proses P1 yang datang pada saat p0 sedang berjalan, maka akan dilihat prioritas P1, seandainya P1 > P0 pada nonpreemptive, P0 akan diselesaikan, pada preemptive P0 akan dihentikan sedang cpu ganti dialokasikan untuk P1.
8. Multiple Feedback Queue (MFQ)
Atau disebut juga Penjadwalan Banyak Antrian, mempunyai ciri-ciri :
- Digunakan untuk mencegah banyaknya swapping dengan proses-proses yang sangat banyak menggunakan pemroses diberi waktu lebih banyak dalam satu waktu
- Penjadwalan preemptive (by time)
- Penjadwalan dengan prioritas
- Menghendaki kelas-kelas prioritas bagi proses-proses yang ada
Ketentuan yang berlaku :
- Jalankan proses pada kelas tertinggi
- Jika proses menggunakan seluruh kwanta yang dialokasikan maka diturunkan kelas prioritasnya
- Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi
9. Shortest Remaining First (SRF)
Atau disebut juga Sisa Waktu Terpendek Diutamakan, mempunyai ciri- ciri :- Penjadwalan preemptive
- Penjadwalan dengan prioritas
- Prioritas didasarkan pada pendeknya sisa proses, makin pendek sisa proses makin tinggi prioritasnya.
- Harus selalu memperhatikan saat proses tiba atau proses selesai
- Dihitung 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 dikerjakan, maka atas dasar preemptive, proses dihentikan diganti oleh proses dengan sisa proses yang terpendek
10. Penjadwalan Round Robin
Mempunyai ciri- ciri :- Penjadwalan preemptive, bukan diprempt oleh proses lain tetapi oleh penjadwal berdasarkan lama waktu berjalannya proses (preempt by time)
- Penjadwalan tanpa prioritas
- Semua proses dianggap penting dan diberi sejumlah waktu pemroses yang disebut kwanta (kuantum)
Ketentuan algoritma round robin
- Jika kwanta habis dan proses belum selesai maka proses ready dan pemroses dialihkan ke proses lain
- Jika kwanta belum habis dan proses menunggu suatu event, maka proses menjadi blocked dan pemroses dialihkan ke proses lain
- Jika kwanta belum habis tapi proses telah selesai, maka proses diakhiri dan pemroses dialihkan ke proses lain.
Permasalahan yang terjadi adalah dalam nentukan kwanta,
- Jika kwanta terlalu besar menyebabkan waktu tanggap besar dan turn arround time rendah
- Jika kwanta terlalu kecil menyebabkan peralihan proses terlalu banyak sehingga menurunkan efisiensi pemroses
11. Highest Response Ratio Next (HRN)
Atau disebut juga Rasio Tanggapan Tertinggi Diutamakan, mempunyai ciri-ciri :- Penjadwalan nonpreemptive
- Penjadwalan dengan prioritas,dasar prioritas adalah besarnya ratio tanggapan, waktu tanggap tertinggi dilayani lebih dulu
- Prioritas dihitung berdasarkan rumus
Prioritas = (waktu tunggu + waktu layanan) / waktu layanan
- Begitu proses mendapat jatah pemroses, proses berjalan sampai selesai