Pertemuan - 4 PENJADWALAN PROSES Haryono Setiadi, ST, M.Eng D3 Ilmu Komputer UNS
OBJEK PEMBELAJARAN • • • • •
Definisi Sasaran Penjadwalan Tipe-tipe penjadwalan Strategi Penjadwalan Algoritma Penjadwalan
DEFINISI w Penjadwalan merupakan kumpulan kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer. w Penjadwalan bertugas memutuskan proses yang harus berjalan dan kapan atau berapa lama proses itu berjalan. w Sasaran utama penjadwalan proses adalah optimasi kinerja menurut kriteria tertentu, yaitu : Î Î Î Î Î
adil efisiensi waktu tanggap (response time) turn arround time throughput
SASARAN PENJADWALAN (1) Adil Proses-proses diperlakukan sama yaitu mendapat jatah waktu pemroses yang sama dan tak ada proses yang tidak kebagian layanan pemroses. Efisiensi - Efisiensi atau utilisasi pemroses dihitung dengan perbandingan (rasio) waktu sibuk pemroses. - Sasaran penjadwalan Æ menjaga agar pemroses tetap dalam keadaan sibuk sehingga efisiensi mencapai maksimum. - Sibuk Æ pemroses tidak menganggur, termasuk waktu yang dihabiskan untuk mengeksekusi program pemakai dan SO
SASARAN PENJADWALAN (2) Waktu tanggap (response time) Waktu tanggap pada sistem interaktif Adalah waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan sampai hasil pertama muncul di layar (terminal) Æ disebut terminal response time Waktu tanggap pada sistem waktu nyata (real-time) Adalah waktu dari saat kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan yang dimaksud dieksekusi Æ disebut event response time
SASARAN PENJADWALAN (3) Turn arround time - Adalah waktu yang dihabiskan dari saat program atau job mulai masuk ke sistem sampai proses diselesaikan sistem. - Waktu yang dimaksud adalah waktu yang dihabiskan di dalam sistem. Turn Arround Time = waktu eksekusi + waktu menunggu Sasaran penjadwalan adalah meminimalkan turn arround time.
SASARAN PENJADWALAN (4) Throughput - Adalah jumlah kerja atau jumlah job yang dapat diselesaikan dalam satu unit waktu. - Sasaran penjadwalan adalah memaksimalkan jumlah job yang diproses per satu interval waktu. - Lebih tinggi angka throughput Æ lebih banyak kerja yang dilakukan sistem.
STRATEGI PENJADWALAN Ada 2 strategi penjadwalan : • Penjadwalan nonpreemptive • Penjadwalan preemptive Penjadwalan nonpreemptive : Proses yang sedang berjalan tidak dapat disela. Sekali proses berada di status running (sedang berjalan), maka proses tersebut akan dieksekusi terus sampai proses berhenti dan CPU tidak dapat diambil alih oleh proses yang lain. Penjadwalan preemptive : Proses yang sedang berjalan dapat diinterupsi dan dipindah ke status ready oleh sistem operasi sehingga CPU dapat diambil alih proses yang lain.
ALGORITMA PENJADWALAN Terdapat banyak algoritma, diantaranya : Algoritma menggunakan strategi nonpreemptive √ FIFO (First-in, First-out) atau FCFS (First-come, First-serve) √ SJF (Shortest Job First) √ HRN (Highest – Ratio Next)
b. Algoritma menggunakan strategi preemptive 9 9 9 9 9
MFQ (Multiple Feedback Queues) RR (Round Robin) SRF (Shortest Remaining First) PS (Priority Schedulling) GS (Guaranteed Schedulling)
NONPREEMPTIVE Penjadwalan FIFO (First in, First Out) (1) -
Penjadwalan nonpreemptive & penjadwalan tidak berprioritas.
-
Penjadwalan paling sederhana, yaitu : Î Proses-proses diberi jatah waktu pemroses berdasarkan waktu kedatangan Î Saat proses mendapat jatah waktu pemroses, proses dijalankan sampai selesai Penjadwalan ini adil yaitu proses yang datang duluan, dilayani duluan juga. Dikatakan tidak adil karena job-job yang perlu waktu lama membuat job-job pendek menunggu. Job-job tak penting dapat membuat job-job penting menunggu.
-
NONPREEMPTIVE Penjadwalan FIFO (First in, First Out) (2) Contoh : Misal ada tiga proses P1, P2, P3 yang datang dengan lama waktu kerja CPU (CPU Burst-time) masing-masing sbb :
NONPREEMPTIVE Penjadwalan FIFO (First in, First Out) (3)
NONPREEMPTIVE Penjadwalan SJF (Shortest Job First) (1) Æ jarang digunakan -
Merupakan penjadwalan nonpreemptive dan penjadwalan tidak berprioritas. Penjadwalan ini mengasumsikan waktu jalan proses (sampai selesai) diketahui sebelumnya. Mekanisme penjadwalan adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai.
NONPREEMPTIVE Penjadwalan SJF (Shortest Job First) (2)
NONPREEMPTIVE Penjadwalan SJF (Shortest Job First) (3)
PREEMPTIVE Penjadwalan PS (Priority Schedulling) (1) Tiap proses dilengkapi dengan prioritas. CPU dialokasikan untuk proses yang memiliki prioritas paling tinggi. Jika beberapa proses memiliki prioritas yang sama, maka akan digunakan algoritma FIFO. Contoh :
PREEMPTIVE Penjadwalan PS (Priority Schedulling) (2)
PREEMPTIVE Penjadwalan RR (Round Robin) (1) Merupakan penjadwalan preemptive, penjadwalan tanpa prioritas. Semua proses dianggap penting dan diberi sejumlah waktu pemroses yang disebut kwanta (quantum) atau time-slice dimana proses itu berjalan.
PREEMPTIVE Penjadwalan RR (Round Robin) (2) Ketentuan algoritma RR : - Jika quantum habis dan proses belum selesai maka proses menjadi runnable dan pemroses dialihkan ke proses lain - Jika quantum belum habis dan proses menunggu suatu kejadian (selesainya I/O), maka proses menjadi blocked dan pemroses dialihkan ke proses lain. - Jika quantum belum habis tapi proses telah selesai maka proses diakhiri dan pemroses dialihkan ke proses lain.
PREEMPTIVE Penjadwalan RR (Round Robin) (3)
PREEMPTIVE Penjadwalan RR (Round Robin) (4)
PREEMPTIVE Penjadwalan RR (Round Robin) (5)
PREEMPTIVE Penjadwalan RR (Round Robin) (6)
Nama Proses A B C D
Saat Tiba 0 0 0 0
Lama Proses 4 3 2 1
Jika digunakan penjadualan Putar Gelang (Round Robin), dengan kuantum waktu sebesar 2 satuan waktu, tentukan AWT dan rata2 TAT?
PREEMPTIVE
Penjadwalan GS (Guaranteed Schedulling) (1) Penjadwalan ini harus menjamin bahwa algoritma tersebut mempunyai kinerja yang cukup bagus dan menjanjikan kelangsungan hidup yang baik. Contoh : Î misal
ada n user yang sedang login, maka tiap-tiap user dijanjikan akan menerima 1/n dari kemampuan CPU. Î Untuk meyakinkan bahwa setiap user mendapatkan jatah waktu menggunakan CPU sesuai dengan haknya maka sistem harus tahu berapa CPU time yang diperlukan oleh setiap proses dalam 1 user. Dan juga CPU time yang diperlukan oleh tiap-tiap user
PREEMPTIVE
Penjadwalan GS (Guaranteed Schedulling) (2)
PREEMPTIVE
Penjadwalan GS (Guaranteed Schedulling) (3)
END CHAPTER CHAPTER BERIKUTNYA : 5. KONGKURENSI (KEBERSAMAAN)
NONPREEMPTIVE Penjadwalan HRN (Highest – Ratio Next) -
Merupakan penjadwalan non-preemptive & penjadwalan berprioritas dinamis Æ merupakan perbaikan dari algoritma SJF, karena pada SJF ada kemungkinan proses dengan waktu layanan lama akan menunggu lama untuk dieksekusi.
-
Hal ini disebabkan adanya proses-proses lain yang waktu layanannya selalu lebih pendek dari proses tersebut. Prioritas = (waktu tunggu + waktu layanan) / waktu layanan Proses dengan prioritas yang tertinggi akan dipilih untuk dieksekusi selanjutnya.
PREEMPTIVE Penjadwalan MFQ (Multiple Feedback Queues) -
Merupakan penjadwalan dengan banyak antrian, merupakan penjadwalan preemptive (by-time), penjadwalan berprioritas dinamis. Penjadwalan ini untuk mencegah banyaknya swapping dengan prosesproses yang sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta/jumlah quantum) lebih banyak dalam satu waktu. Penjadwalan ini menghendaki kelas-kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama 2 kwanta,kelas berikutnya berjalan 4 kwanta, dst. 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.
PREEMPTIVE Penjadwalan SRF (Shortest Remaining First) sisa waktu terpendek, duluan
-
-
Penjadwalan
Merupakan penjadwalan preemptive, berprioritas dinamis. Pada SRF, proses dengan sisa waktu jalan diestimasi terendah dijalankan, termasuk proses-proses yang baru tiba. Pada SJF begitu proses dieksekusi, proses dijalankan sampai selesai Pada SRF proses yang sedang berjalan (running) dapat diambil alih proses baru dengan sisa jalan yang diestimasi lebih rendah.
