2/1/2015
Tahun Akademik 2014/2015 Semester II
DIG1I3 - Instalasi dan Penggunaan Sistem Operasi Penjadualan Proses Bag. 1 Mohamad Dani (MHM) Alamat E-mail:
[email protected]
Hanya dipergunakan untuk kepentingan pengajaran di lingkungan Telkom Applied Science School
Penjadualan Process Bagian 1
1
2/1/2015
Tujuan Pembelajaran
Mahasiswa mampu menjelaskan perbedaan penjadualan proses jangka pendek, menengah dan panjang. Mahasiswa mampu menjelaskan cara kerja algoritma-algoritma penjadualan proses dan kinerja dari masing-masing algoritma penjadualan proses yang preemptive dan Nonpreemptive. Mahasiswa mampu menggunakan algoritma penjadualan proses yang sesuai dengan permasalahan yang berkaitan dengan penjadualan proses.
Pendahuluan
Pada sistem multiprogramming, banyak proses yang berada secara terus-menerus di memori utama. Tiap proses dieksekusi oleh proses secara bergantian dan menunggu beberapa event terjadi misal menunggu operasi I/O selesai. Prosesor dibuat sibuk dengan mengeksekusi sebuah proses dan proses lainnya menunggu giliran untuk dieksekusi oleh prosesor.
2
2/1/2015
Tipe Penjadualan Proses Agar proses-proses tersebut dapat dieksekusi dengan baik, maka dibuatlah 4 tipe-tipe penjadualan berdasarkan waktu yaitu: 1. Long-term scheduling : Keputusan untuk menambahkan ke pool proses-proses yang akan dieksekusi. 2. Medium-term scheduling : Keputusan untuk menambahkan ke sejumlah proses yang secara penuh atau sebagian yang ada di memori utama. 3. Short-term scheduling : Keputusan proses yang tersedia yang akan dieksekusi oleh prosesor.
Transisi Process State dan Penjadualan
3
2/1/2015
Model Process
Level Penjadualan
Diagram Antrian Penjadualan
4
2/1/2015
Kriteria Penjadualan Utilisasi CPU: menjadikan CPU terus menerus sibuk (menggunakan CPU semaksimal mungkin). Throughput: maksimalkan jumlah proses yang selesai dijalankan (per satuan waktu). Turn around time: minimalkan waktu selesai eksekusi suatu proses (sejak di submit sampai selesai). Waiting time: minimalkan waktu tunggu proses (jumlah waktu yang dihabiskan menunggu di ready queue). Response time: minimalkan waktu response dari sistim terhadap user (interaktif, time-sharing system), sehingga interaksi dapat berlangsung dengan cepat.
9
Kriteria Penjadualan yang Optimal
Memaksimumkan utilisasi CPU Memaksimumkan throughput Meminimukan turnaround time Meminimumkan waiting time Meminimumkan response time
10
5
2/1/2015
Algoritma Penjadualan Mode keputusan: 1. Nonpreemptive : Pada saat sebuah proses berada dalam Running state, proses terus dieksekusi sampai (a) prosesnya selesai (b) prosesnya memblok diri sendiri untuk menunggu I/O atau meminta beberapa layanan OS. 2. Preemptive : Proses yang sedang berjalan dapat disela atau dipindahkan ke Ready state oleh OS.
Algoritma Penjadualan
First-come, first-served (FCFS) Non preemptive Shortest-Job-First (SJF) Preemptive Shortest-Job-First (SJF) aka ShortestRemaining-Time-First (SRTF). Priority scheduling Round-Robin (RR) Feedback Scheduling
12
6
2/1/2015
First-Come, First-Served (FCFS)
Algoritma:
Proses yang request CPU pertama kali akan mendapatkan jatah CPU. Sederhana – algoritma maupun struktur data: menggunakan FIFO queue (ready queue).
FCFS: Non preemptive
Timbul masalah “waktu menunggu” terlalu lama jika didahului oleh proses yang waktu selesainya lama. Tidak cocok untuk time-sharing systems. Digunakan pada OS dengan orientasi batch job.
13
Contoh 1 : FCFS/FIFO
Process Burst Time (waktu layanan) (ms) P1 24 P2 3 P3 3 Diketahui proses yang tiba adalah P1, P2, P3. dan arrival timenya dianggap sama. Gant chart-nya adalah :
Waktu menunggu untuk P1 = 0 ms; P2 = 24 ms; P3 = 27 ms Waktu menunggu total untuk semua proses = (0 + 24 + 27) ms = 51 ms Waktu menunggu rerata : (0 + 24 + 27)/3 = 17 ms Turnaround time (TAT) : Waktu menunggu total + waktu total layanan = 51 ms + 30 ms = 81 ms. 14
7
2/1/2015
Latihan 1: FCFS/FIFO Process Burst Time (waktu layanan) (ms) P1 24 P2 3 P3 3
Diketahui proses yang tiba adalah P2, P3, P1. Gant chart-nya adalah : Pertanyaan: Buatlah Gant Chartnya! Hitunglah Waktu menunggu P2, P3, P1! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)!
15
Latihan 2: FCFS/FIFO
Process Burst Time (waktu layanan) (ms) P1 24 P2 3 P3 3 Diketahui proses yang tiba adalah P2, P3, P1. dan arrival timenya dianggap sama. Gant chart-nya adalah :
Waktu menunggu untuk P1 = 6 ms; P2 = 0 ms; P3 = 3 ms Waktu menunggu total untuk semua proses = (6 + 0 + 3) ms = 9 ms Waktu menunggu rerata : (6 + 0 + 3)/3 = 3 ms Turnaround time (TAT) : Waktu menunggu total + waktu total layanan = 9 ms + 30 ms = 39 ms. 16
8
2/1/2015
Contoh 2 : FCFS/FIFO
Diketahui proses yang tiba digambarkan pada gambar di atas. Pertanyaan: Buatlah Chartnya! Hitunglah Waktu menunggu A, B, C, D, E! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)! Hitunglah Turnaround time (TAT) reratanya! 17
Contoh 2 : FCFS/FIFO
Chartnya! A B C D E
A B C D E 0
Waktu menunggu
20 1 Kotak = 1
Waktu menunggu A = 0, B = 1, C = 5, D = 7 , E = 10! Waktu menunggu total untuk semua proses = 0 + 1 + 5 + 7 + 10 = 23 Waktu menunggu reratanya = 23/5 = 4,6 Turnaround time (TAT) = 23 + 20 = 43 Turnaround time (TAT) reratanya = 43/5 = 8,6 18
9
2/1/2015
Latihan 2 : FCFS/FIFO
Diketahui proses yang tiba digambarkan pada gambar di atas. Pertanyaan: Buatlah Chartnya! Hitunglah Waktu menunggu A, B, C, D, E! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)! Hitunglah Turnaround time (TAT) reratanya! 19
Latihan 2 : FCFS/FIFO
Chartnya! A B C D E
A B C D E 0
Waktu menunggu
20 1 Kotak = 1
Waktu menunggu A = 0, B = 2, C = 5, D = 1 , E = 3! Waktu menunggu total untuk semua proses = 0 + 2 + 5 + 1 + 3 = 11 Waktu menunggu reratanya = 11/5 = 2,2 Turnaround time (TAT) = 11 + 20 = 31 Turnaround time (TAT) reratanya = 31/5 = 6,2 20
10
2/1/2015
Shortest-Job-First (SJF)
Penggabungan setiap proses merupakan panjang dari burst CPU berikutnya. Panjang tersebut digunakan untuk penjadualan proses pada waktu terpendek
Terdapat 2 skema : nonpreemptive – CPU hanya satu kali diberikan pada suatu proses, maka proses tersebut tetap akan memakai CPU hingga proses tersebut melepaskannya. Dikenal juga sebagai non preemptive SJF. preemptive –jika suatu proses tiba dengan panjang CPU burst lebih kecil dari waktu yang tersisa pada ekseksusi proses yang sedang berlangsung, maka dijalankan preemptive. Skema ini dikenal dengan ShortestRemaining-Time-First (SRTF).
SJF akan optimal, ketika rata-rata waktu tunggu minimum untuk set proses yang diberikan
21
Contoh 3: Non-Preemptive SJF Process A B C D
Arrival Time (ms) Burst Time (ms) 0.0 7 2.0 4 4.0 1 5.0 4
Pertanyaan: Buatlah Chartnya! Hitunglah Waktu menunggu A, B, C, D, E! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)! Hitunglah Turnaround time (TAT) reratanya!
22
11
2/1/2015
Contoh 3 : Non-Preemptive SJF
Chartnya! A B C D
A B c D 0
Waktu menunggu
16 1 Kotak = 1
Waktu menunggu A = 0 ms, B = 6 ms, C = 3 ms, D = 7 ms! Waktu menunggu total untuk semua proses = 0 ms + 6 ms + 3 ms + 7 ms = 16 ms Waktu menunggu reratanya = 16 ms /4 = 4 ms Turnaround time (TAT) = 16 ms + 16 ms = 32 ms Turnaround time (TAT) reratanya = 32 ms /4 = 8 ms 23
Contoh 4: Preemptive SJF (SRT) Process A B C D
Arrival Time (ms) Burst Time (ms) 0.0 7 2.0 4 4.0 1 5.0 4
Pertanyaan: Buatlah Chartnya! Hitunglah Waktu menunggu A, B, C, D, E! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)! Hitunglah Turnaround time (TAT) reratanya!
24
12
2/1/2015
Contoh 4 : Preemptive SJF (SRTF)
Chartnya! A B C D
A
A B C D
0 Waktu menunggu
16 1 Kotak = 1
Waktu menunggu A = 9 ms, B = 0 ms, C = 2 ms, D = 2 ms! Waktu menunggu total untuk semua proses = 9 ms + 0 ms + 2 ms + 2 ms = 13 ms Waktu menunggu reratanya = 13 ms /4 = 3,25 ms Turnaround time (TAT) = 13ms + 16 ms = 29 ms Turnaround time (TAT) reratanya = 29 ms /4 = 7,25 ms 25
Latihan 3 : Non-Preemptive SJF
Diketahui proses yang tiba digambarkan pada gambar di atas. Pertanyaan: Buatlah Chartnya! Hitunglah Waktu menunggu A, B, C, D, E! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)! Hitunglah Turnaround time (TAT) reratanya! 26
13
2/1/2015
Latihan 4 : Preemptive SJF (SRTF)
Diketahui proses yang tiba digambarkan pada gambar di atas. Pertanyaan: Buatlah Chartnya! Hitunglah Waktu menunggu A, B, C, D, E! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)! Hitunglah Turnaround time (TAT) reratanya! 27
Tugas 2 : Penjadualan Proses-1 1. 2. 3. 4.
Jelaskan 3 tipe penjadualan prosesor! Apa perbedaan antara turnaround time dan response time? Apa perbedaan antara penjadualan preemptive dan nonpreemptive? Jelaskan algoritma penjadualan prosesor berikut: a) First-come, first-served (FCFS) b) Non preemptive Shortest-Job-First (SJF) c) Preemptive Shortest-Job-First (SJF)/ShortestRemaining-Time-First (SRTF).
14
2/1/2015
Tugas 2 : Penjadualan Proses-1 5.
Diketahui proses yang tiba digambarkan pada gambar di bawah:
Tugas Anda: Buatlah Chartnya! Hitunglah Waktu menunggu P1, P2, P3, P4! Hitunglah Waktu menunggu total untuk semua proses ! Hitunglah Waktu menunggu reratanya! Hitunglah Turnaround time (TAT)! Hitunglah Turnaround time (TAT) reratanya! Menggunakan algoritma: a. FCFS, b. Non-Preemptive SJF, c. Preemptive SJF (SRTF)
Pertemuan Selanjutnya
Priority Scheduling Round-Robin (RR) Feedback Scheduling Latihan soal Algoritma penjadualan CPU/Proses
15
2/1/2015
Daftar Pustaka
William Stallings(2012). Operating Systems 7th Edition. Prentice Hall. New Jersey halaman 395 – 426. Avi Silberschatz, Peter Galvin, dan Grag Gagne (2013). Operating Systems CONCEPTS ninth Edition. John Wiley & Sons. USA Halaman 261 – 312.
Danke
32
16
