10/17/2012
SISTEM OPERASI PENJADWALAN PROSES
[email protected]
http://blogriki.wordpress.com
Pembahasan • Konsep Dasar • Kriteria Scheduling • Algoritma Scheduling
1
10/17/2012
CPU Scheduling • Merupakan basis dari OS yang multiprogramming, sementara multiprogramming untuk meningkatkan produktifitas sistem • Topik pembahasan : – Konsep dasar CPU Scheduling – Algoritma-algoritma CPU Scheduling
CPU Scheduling
2
10/17/2012
Konsep Dasar CPU Scheduling • Dalam multiprogramming – Suatu proses dieksekusi s.d proses tunggu untuk I/O, setelah itu CPU diberikan ke proses lain, dst. – Membentuk siklus yang terdiri atas • Sequence eksekusi CPU (CPU burst time) • Sequence dalam service I/O (I/O burst time)
– Pola distribusi CPU burst time adalah eksponensial atau bahkan hipereksponensial
Contoh CPU - I/O Burst • scanf n, a, b for (i=1; i<=n; i++) x = x + a*b; printf x for (i=1; i<=n; i++) for (j=1; j<=n; j++) x = x + a*b; printf x
/* I/O wait */ /* CPU burst */ /* I/O wait */ /* CPU burst */
/* I/O wait */
3
10/17/2012
Pola Distribusi CPU Burst Time
Keputusan Scheduling • Scheduler memilih dari antara proses-proses dalam memori yang ready dan mengalokasi CPU untuk proses yang terpilih • Terjadinya keputusan scheduler saat : – (1) status proses berubah dari run ke wait – (2) status proses berubah dari run ke ready – (3) status proses berubah dari wait ke ready – (4) status proses menjadi terminate
4
10/17/2012
Non-preemptive • Scheduler dalam situasi (1) dan (4) disebut non-preemptive – Sekali CPU ditetapkan untuk suatu proses maka proses tidak akan melepaskannya hingga terminate atau untuk melakukan I/O – Untuk hardware tertentu skema ini merupakan satu-satunya pilihan (misalnya tidak ada timer) – Digunakan oleh MS Windows
Status Proses - Scheduler
Preemptive
Non--preemptive Non
5
10/17/2012
Preemptive • Scheduler dalam situasi (2) dan (3) disebut preemptive – CPU dapat dialihkan ke proses lain oleh OS misalnya karena interrupt, timer, dsb. – Perlu penanganan masalah data sharing antara sebelum dan sesudah – Perlu blocking CPU saat struktur data kernel berada pada status yang inkonsisten
Dispatcher • Modul yang memberikan kontrol CPU bagi proses yang terpilih untuk mendapat giliran meliputi : – Context switching – Set operasi sistem ke user-mode – Jump ke lokasi untuk meneruskan proses yang mendapat giliran dan run
6
10/17/2012
Dispatcher
Dispatcher
7
10/17/2012
Dispatch Latency • Waktu yang diperlukan oleh dispatcher untuk menghentikan proses yang sedang running hingga proses yang didispatch berikutnya running
CPU Scheduling Algorithms • • • • • •
FCFS Queue SJF Queue Priority Queue Round Robin Multi-Level Queue Multi-Level Feedback Queue
8
10/17/2012
Kriteria Scheduling (1) • CPU utilization : persentase jumlah waktu CPU sibuk dari total waktu
Kriteria Scheduling (1) • Throughput : Jumlah proses yang selesai dieksekusi per satuan waktu
9
10/17/2012
Kriteria Scheduling (1) • Turnaround time : selang waktu sejak submit (mulai) proses hingga terminate (selesai)
Kriteria Scheduling (2) • Waiting time : jumlah waktu suatu proses menunggu dalam ready queue • Response time : panjang waktu sejak submit hingga respons pertama muncul • Predictability respons : variansi (ketersebaran) waktu respons • Fairness : Pembagian waktu penggunaan CPU secara adil
10
10/17/2012
Obyektif • Pemilihan algoritma untuk optimisasi : – Memaksimalkan CPU utilization – Memaksimalkan throughput – Meminimumkan turnaround time – Meminimumkan waiting time – Meminimumkan response time – Meminimumkan response time variance – Mendapatkan pembagian yang Fairness
First Come, First-Served (FCFS) • Proses yang merequest CPU lebih dulu adalah yang dilayani terlebih dahulu • Jika suatu proses running menjadi ready maka ia antri lagi dibelakang • Performance : waktu tunggu rata-rata lama serta akan bervariasi jika burst time amat bervariasi
11
10/17/2012
First Come, First-Served (FCFS)
(1)
•
(2)
Contoh FCFS • P1 : 24 ms, P2 : 3 ms, P3 : 3 ms. • Datang dalam urutan P1, P2, P3 – Gantt Chart
P1
P2
0
24
P3 27
30
– Waktu tunggu : P1 = 0 ms, P2 = 24 ms, dan P3 = 27 ms – Average waiting time = (0 + 24 + 27)/3 = 17 ms
• Jika urutannya : P2, P3, P1 maka : – Gantt Chart P2 0
P3 3
P1 6
– Average waiting time = (6 + 0 + 3)/3 = 3
30
12
10/17/2012
Masalah FCFS : “Convoy Effect” • Kondisi terdapat suatu proses yang memiliki CPU-burst time besar (CPU bound) dan sejumlah proses lain dengan I/O burst time yang besar (I/O bound) – Proses CPU bound sedang hold CPU proses I/O bound menunggu, I/O device idle – Proses I/O bound sedang melakukan I/O, proses CPU bound menunggu, CPU idle
Shortest Job First (SJF) • Tepatnya “shortest CPU burst-time first” • Bila CPU burst time tiap proses diketahui sebelumnya maka proses dengan CPU burst time terkecil yang dilayani terlebih dahulu – Preemptive scheme : proses running P1 bisa dihentikan di tengah saat muncul proses P2 yang lebih pendek – Nonpreemptive scheme : proses running akan terus sampai terminate atau I/O wait
13
10/17/2012
Contoh SJF - Non-Preemptive Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (non-preemptive) P1 0
P3
3
7
P2 8
P4 12
16
• Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Contoh SJF - Preemptive Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (preemptive) P1 0
P2 2
P3 4
P2 5
P4 7
P1 11
16
• Average waiting time = (9 + 1 + 0 +2)/4 = 3
14
10/17/2012
Masalah SJF : informasi CPU burst time • Algoritma memberikan performance yang optimal, tapi bagaimana caranya mendapatkan informasi CPU burst time ? – Untuk long-term schedule dalam batch system, dapat digunakan panjang time limit yang dispesifikasikan user pada saat submit job. – Untuk short-term scheduling tidak mungkin. Tidak ada cara untuk mengetahui secara pasti CPU burst berikutnya, hanya dapat diaproksimasi secara stokastik (prediksi).
Priority Scheduling • Proses dengan prioritas lebih tinggi akan dilayani lebih dulu – Preemptive scheme : proses running P1 bisa dihentikan di tengah saat muncul proses P2 yang lebih tinggi prioritasnya – Non-preemptive scheme : proses yang running akan diteruskan sampai terminate atau I/O wait
15
10/17/2012
Contoh Priority Scheduling Process P1 P2 P3
Priority 2 1 3
P1
P2 0
Burst Time 8 1 1
1
P3 9
10
• Average waiting time = (1 + 0 + 9)/3 = 3.3
Pendefinisian Prioritas • Internal – Bila mungkin, ditentukan berdasarkan indikator terukur atau estimasinya • Time limit, memori requirement, jumlah file open, ratio I/O burst terhadap CPU burst
• External – Ditentukan berdasarkan kriteria yang eksternal bagi OS • Tingkat kepentingan proses, charging, superuser (root), dll
16
10/17/2012
Masalah Priority Scheduling • Indefinite blocking (starvation) pada proses-proses berprioritas rendah terutama jika sistemnya heavilyloaded – Rumor : ketika IBM 7093 di MIT dishutdown tahun 1973, ditemukan adanya proses-proses low priority yang di-submit tahun 1967 dalam status wait
Solusi dari Starvation • Solusi : “aging” (peningkatan prioritas pada proses-proses yang sudah menunggu cukup lama) – Misalnya setiap 15 menit dinaikkan 1 tingkat
17
10/17/2012
Round Robin (RR) • Masing-masing proses diberikan interval waktu tertentu yang disebut time quantum • Mengikuti FCFS & setelah kuantum waktu tertentu proses yang running di-preempt & kembali ke ready queue • Mekanisme kuantum waktu menggunakan timer, jika proses sudah terminate atau melakukan I/O wait sementara timer belum habis, timer di-reset untuk giliran proses berikutnya
Contoh : RR • Contoh : dengan time quantum = 20 ms Process Burst Time P1 53 P2 17 P3 68 P4 24 • Gantt chart :
P1 0
P2 20
37
P3
P4 57
P1 77
P3 97 117
P4
P1
P3
P3
121 134 154 162
• Khususnya, rata-rata turn around lebih tinggi daripada SJF, tetapi lebih baik untuk respons.
18
10/17/2012
Masalah RR : Penentuan Kuantum Waktu • Menentukan performance sistem : – Jika terlalu besar sistem menjadi FCFS murni – Jika terlalu kecil terjadi “processor sharing” • Pada n proses yang running pada prosesor dengan kecepatan K, bagi setiap proses terasa masing-masing memiliki prosesor sendiri dengan kecepatan K/n (misalnya respons interaksi jadi lambat)
– Jika terlalu kecil overhead untuk context switching jadi besar
Time Quantum dan Context Switch Time
19
10/17/2012
Multi-Level Queue (MLQ) • Proses diklasifikasi ke dalam sejumlah kelas & masing-masing kelas memiliki antrian sendiri dengan aturan berbeda – Contoh kelas-kelas dalam beberapa OS • Proses sistem • Proses interaktif • Proses editing interaktif • Proses batch • Proses student
Diagram Contoh MLQ
20
10/17/2012
MLQ pada Uniprocessor • Kelas-kelas perlu diantrikan juga – Dengan prioritas berbeda secara fixed dan preemptive; proses dari kelas yang lebih rendah harus menunggu proses dari kelas yang lebih tinggi selesai – Dengan menerapkan time sharing dengan kuota waktu yang berbeda (misalnya foreground 80% dan background 20%)
Multi-Level Feedback Queue • MLQ overhead rendah tetapi tidak fleksibel • MLFQ memungkinkan perpindahan antara level antrian untuk meng-aproksimasi SJF : – Proses mula-mula masuk ke level pertama, jika dalam batas waktu proses belum berakhir maka ia di-preempt dan dimasukkan ke antrian level berikutnya yang prioritasnya lebih rendah – Proses yang menunggu terlalu lama bisa naik ke antrian ber-prioritas lebih tinggi
21
10/17/2012
Contoh MLFQ • Contoh MLFQ dengan 3 antrian : Q0, Q1, dan Q2. Kuantum Q0 = 8 ms, kuantum Q1 = 16 ms dan Q2 menggunakan skema FCFS – Awalnya proses P masuk ke Q0, apabila saat running belum selesai saat timer habis (8 ms) maka P di-preempt dan dipindahkan ke Q1 – Jika Q0 sudah kosong, Q1 baru dilayani; saat P belum selesai juga saat timer habis (16 ms) maka P masuk dalam skema FCFS Q3
Diagram Contoh MLFQ
22
10/17/2012
Parameter Menentukan MLFQ • Jumlah Queue (level) • Algoritma scheduling untuk tiap queue • Metode penentuan kapan upgrade prioritas proses ke queue yang lebih tinggi • Metode penentuan kapan menurunkan prioritas proses ke queue yang lebih rendah • Metode penentuan queue mana yang dimasuki proses
23
