05 Penjadwalan CPU.pdf

1

Bab 5: Penjadwalan CPU

� Konsep Dasar� Kriteria Penjadwalan� Algoritma Penjadwalan : FCFS, SJF, Priority, RR� Algoritma Penjadwalan : FCFS, SJF, Priority, RR� Penjadwalan Multiple-Processor� Penjadwalan Real-Time� Evaluasi Algoritma

6.1

Konsep Dasar

� Dengan sistem multiprogramming akan diperoleh utilitas CPU yang maksimal

� Pada saat proses dieksekusi, terdiri dari siklus eksekusi � Pada saat proses dieksekusi, terdiri dari siklus eksekusi CPU dan menunggu I/O (CPU–I/O Burst Cycle)

6.2

2

Urutan CPU dan I/O Bursts

6.3

Histogram waktu CPU-burst

6.4

3

CPU Scheduler

� Memilih diantara proses yang ada di memori yang siap dieksekusi (ready) dan mengalokasikan CPU untuk satu diantara proses-proses tersebutdiantara proses-proses tersebut

� Keputusan penjadwalan CPU diambil pada saat proses:1. Berpindah dari state running ke waiting.2. Berpindah dari state running ke ready.3. Berpindah dari state waiting ke ready.4. Diterminasi.

� Penjadwalan nomor 1 dan 4 tidak dapat ditunda (nonpreemptive).

6.5

(nonpreemptive).� Penjadwalan nomor 2 dan 3 dapat ditunda (preemptive).

Dispatcher

� Modul dispatcher module memberi kontrol ke CPU untuk memilih proses dengan short-term scheduler; yang melibatkan:melibatkan:� switching context� switching ke user mode� Melompat ke lokasi yang tepat pada user program untuk

restart progra

� Dispatch latency – waktu yang dibutuhkan dispatcher untuk menghentikan satu proses dan memulai proses lain yang sedang berjalan

6.6

4

Kriteria Penjadwalan

� Utilitas CPU – membuat CPU sesibuk mungkin� Throughput – jumlah proses yang menyelesaikan � Throughput – jumlah proses yang menyelesaikan

eksekusi pada satu unit waktu� Waktu Turnaround – jumlah waktu untuk mengeksekusi

proses tertentu� Waktu Tunggu – jumlah waktu suatu proses menunggu

dalam ready queue� Waktu Respon – jumlah waktu yang dibutuhkan dari

sebuah permintaan dikirim sampai mendapatkan respon

6.7

sebuah permintaan dikirim sampai mendapatkan respon pertama, bukan output (untuk lingkungan time-sharing)

Kriteria Optimal

� Untilitas CPU maksimal� Throughput maksimal� Waktu turnaround minimal� Waktu turnaround minimal� Waktu tunggu minimal� Waktu respon minimal

6.8

5

Penjadwalan First-Come, First-Served (FCFS) Proses Burst Time

P1 24P2 3P3 3P3 3

� Diasumsikan proses dapat dengan urutan: P1 , P2 , P3

Gantt Chart untuk penjadwalan diatas adalah:

P1 P2 P3

6.9

� Waktu Tunggu untuk P1 = 0; P2 = 24; P3 = 27� Rata-rata waktu tunggu: (0 + 24 + 27)/3 = 17� Waktu Turnaround untuk P1 = 24; P2 = 27; P3 = 30� Rata-rata waktu turnarount: (24+27+30)/3=27� Bersifat Non preemptive (tidak dapat ditunda)

24 27 300

Penjadwalan FCFS (Cont.)

Diasumsikan proses dapat dengan urutan P2 , P3 , P1 .

� Gantt chart untuk penjadwalah tersebut:� Gantt chart untuk penjadwalah tersebut:

� Waktu tunggu untuk P1 = 6; P2 = 0; P3 = 3� Rata-rata waktu tunggu: (6 + 0 + 3)/3 = 3� Waktu turnaround untuk P1 = 30; P2 = 3; P3 = 6

P1P3P2

63 300

6.10

� Waktu turnaround untuk P1 = 30; P2 = 3; P3 = 6� Rata-rata waktu turnarount: (30+3+6)/3 = 13� Hasilnya lebih baik dari sebelumnya, dimana proses

sebelumnya terjadi convoy effect dimana proses kecil berada di belakang proses besar

6

Penjadwalan Shortest-Job-First (SJF)

� Hubungan antar proses berdasarkan panjang CPU burst berikutnya. CPU dialokasikan untuk proses yang mempunyai waktu terpendek terlebih dahulumempunyai waktu terpendek terlebih dahulu

� Terdapat 2 skema: � nonpreemptive – ketika CPU diberikan ke proses, maka

proses tidak dapat ditunda sampai menyelesaikan CPU burst nya

� preemptive – jika proses baru datang dengan CPU burst lebih kecil dibandingkan sisa waktu proses yang sedang dieksekusi, maka proses ditunda dan diganti dengan proses baru. Skema ini disebut juga dengan Shortest-Remaining-

6.11

baru. Skema ini disebut juga dengan Shortest-Remaining-Time-First (SRTF).

� SJF optimal – menghasilkan rata-rata waktu tunggu minimal pada sekumpulan proses

Process Arrival Time Burst TimeP1 0.0 7P 2.0 4

Contoh SJF Non-Preemptive

P2 2.0 4P3 4.0 1P4 5.0 4

� SJF (non-preemptive)

P1 P3 P2

73 160

P4

8 12

6.12

� Waktu tunggu untuk P1 = 0; P2 = 6; P3 = 3; P4 = 7� Rata-rata waktu tunggu = (0 + 6 + 3 + 7)/4 = 4� Waktu turnaround untuk P1 = 7; P2 = 10; P3 = 4; P4 = 11� Rata-rata waktu tunggu = (7 + 10 + 4 +11)/4 = 8

73 160 8 12

7

Contoh SJF Preemptive

Process Arrival Time Burst TimeP1 0.0 7P 2.0 4P2 2.0 4P3 4.0 1P4 5.0 4

� SJF (preemptive)

P1 P3P2

11

P4P2 P1

16

6.13

� Waktu tunggu untuk P1 = 9; P2 = 1; P3 = 0; P4 = 2� Rata-rata waktu tunggu = (9 + 1 + 0 + 2)/4 = 3� Waktu turnaround untuk P1 = 16; P2 = 5; P3 = 1; P4 = 6� Rata-rata waktu tunggu = (16 + 5 + 1 + 6)/4 = 7

42 110 5 7 16

Menentukan Panjang CPU Burst berikutnya

� Hanya mengestimasi panjang CPU burst.� Dapat dilakukan menggunakan panjang CPU burst

sebelumnya, menggunakan exponential averaging.sebelumnya, menggunakan exponential averaging.

:Tentukan 4.10 , 3.

berikutnyaburst CPUuntuk prediksi nilai 2.

keburst CPU dari aktual panjang 1.

1

≤≤=

=

+

αατ n

n nt

( ) .t nnn ταατ −+== 11

6.14

( ) .t nnn ταατ −+== 11

8

Prediksi Panjang CPU Burst berikutnya

6.15

Contoh Exponential Averaging

� α =0� τn+1 = τn

� Histori saat ini tidak dihitung.� Histori saat ini tidak dihitung.

� α =1� τn+1 = tn� Hanya menghitung CPU burst aktual terakhir.

� Jika kita menurunkan formula, didapatkan:τn+1 = α tn+(1 - α) α tn -1 + …

+(1 - α )j α tn -1 + …+(1 - α )n=1 t τ

6.16

+(1 - α )n=1 tn τ0

� Karena baik α dan (1 - α) kurang dari atau sama dengan 1, setiap successor mempunyai nilai yang lebih rendah dari predecessor.

9

Penjadwalan Priority

� Setiap proses mempunyai nilai prioritas (integer)� CPU dialokasikan untuk proses dengan prioritas tertinggi

(nilai integer terkecil = prioritas tertinggi).(nilai integer terkecil = prioritas tertinggi).� Preemptive� nonpreemptive

� SJF adalah penjadwalan prioritas dimana prioritasnya adalah berdasarkan hasil prediksi waktu CPU burst berikutnya.

� Problem ≡ Starvation – proses prioritas rendah tidak pernah dieksekusi

6.17

pernah dieksekusi� Solution ≡ Aging – seiring waktu berjalan meningkatkan

prioritas proses.

Process Arrival Time Burst Time PriorityP1 0.0 7 3P 2.0 4 1

Contoh Priority Non-Preemptive

P2 2.0 4 1P3 4.0 1 3P4 5.0 4 2

� Priority (non-preemptive)

P1 P2 P4

7 160

P3

11 15

6.18

� Waktu tunggu untuk P1 = 0; P2 = 5; P3 = 11; P4 =6� Rata-rata waktu tunggu = (0 + 5 + 11 + 6)/4 = 4.5� Waktu turnaround untuk P1 = 7; P2 = 9; P3 = 12; P4 = 10� Rata-rata waktu tunggu = (7 + 9 + 12 +10)/4 = 9.5

7 160 11 15

10

Process Arrival Time Burst Time PriorityP1 0.0 7 3P 2.0 4 1

Contoh Priority Preemptive

P2 2.0 4 1P3 4.0 1 3P4 5.0 4 2

� Priority (non-preemptive), asumsi apabila prioritas sama, diambil yang datang lebih dahulu

P1 P2 P4 P1 P3

6.19

� Waktu tunggu untuk P1 = 10; P2 = 0; P3 = 11; P4 =1� Rata-rata waktu tunggu = (10 + 0 + 11 + 1)/4 = 4.5� Waktu turnaround untuk P1 = 15; P2 = 4; P3 = 12; P4 = 5� Rata-rata waktu tunggu = (15 + 4 + 12 +5)/4 = 9

6 160 10 152

Round Robin (RR)

� Setiap proses mendapatkan unit waktu tertentu dari waktu CPU (waktu quantum), biasanya 10-100 millisecond. Setelah waktu selesai, proses ditunda dan millisecond. Setelah waktu selesai, proses ditunda dan ditambahkan pada ready queue.

� Jika terdapat n proses pada ready queue dan waktu quantum q, kemudian setiap proses mendapatkan waktu CPU 1/n pada bagian waktu q tersebut. Tidak ada proses yang menunggu lebih dari (n-1)q unit waktu.

� Performansi� q besar � FIFO

6.20

� q besar � FIFO� q kecil � q harus lebih besar dari context switch, jika tidak

terjadi overhead yang tinggi.

11

Contoh RR dengan Waktu Quantum = 20

Process Burst TimeP1 53P 17P2 17P3 68P4 24

� Gantt chart :

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

6.21

� Biasanya, RR mempunyai rata-rata waktu tunggu yang lebih besar dari SJF, tetapi respon yang lebih baik

0 20 37 57 77 97 117 121 134 154 162

Waktu Quantum dan waktu Context Switch

6.22

12

Waktu Turnaround dengan Waktu Quantum yang Bervariasi

6.23

Multilevel Queue

� Ready queue dibagi ke dalam antrian yang terpisahforeground (interactive)background (batch)background (batch)

� Setiap antrian mempunyai algoritma penjadwalan masing-masingforeground – RRbackground – FCFS

� Penjadwalan yang harus dilakukan antara antrian� Penjadwalan Prioritas Tetap (Fixed priority scheduling);

(misalnya, melayani semua foreground kemudian

6.24

(misalnya, melayani semua foreground kemudian background). Kemungkinan starvation.

� Time slice – setiap antrian mendapat sejumlah waktu CPU yang dapat digunakan diantara proses-prosesnya, yaitu, 80% untuk foreground pada RR dan 20% untuk background pada FCFS

13

Penjadwalan Multilevel Queue

6.25

Multilevel Feedback Queue

� Proses dapat berpindah antar beberapa antrian; aging juga dapat diimplementasikan.

� Multilevel-feedback-queue scheduler ditentukan dengan � Multilevel-feedback-queue scheduler ditentukan dengan parameter berikut:� Jumlah queue� Algoritma penjadwalan untuk setiap antrian� Metode digunakan untuk menentukan kapan upgrade

proses� Motode digunakan untuk menentukan kapan menurunkan

proses

6.26

� Metode digunakan untuk menentukan antrian mana dari proses yang masuk ketika proses memerlukan layanan

14

Contoh Multilevel Feedback Queue

� Tiga antrian: � Q0 – time quantum 8 milliseconds� Q1 – time quantum 16 milliseconds� Q1 – time quantum 16 milliseconds� Q2 – FCFS

� Penjadwalan� Job baru masuk antrian Q0 yang melayani FCFS. Jika

mendapatkan CPU, job menerima 8 millisecond. Jika tidak selesai dalam 8 millisecond, job dipindah ke antrian Q1.

� Pada job Q1 melayani lagi FCFS dan menerima 16 millisecond tambahan. Jika masih belum selesai, ditundan dan dipindah ke antrian Q .

6.27

dan dipindah ke antrian Q2.

Multilevel Feedback Queues

6.28

15

Penjadwalan Multiple-Processor

� Penjadwalan CPU lebih kompleks ketika tersedia multiple CPU.

� Homogeneous processors dalam multiprocessor.� Homogeneous processors dalam multiprocessor.� Load sharing� Asymmetric multiprocessing – hanya satu prosessor yang

mengakses struktur data sistem, mengurangi kebutuhan data sharing

6.29

Penjadwalan Real-Time

� Hard real-time – dibutuhkan untuk menyelesaikan critical task dalam sejumlah waktu yang dijaminkan.

� Soft real-time computing – membutuhkan proses kritis � Soft real-time computing – membutuhkan proses kritis berdasarkan prioritas.

6.30

16

Dispatch Latency

6.31

Evaluasi Algoritma

� Deterministic modeling – mengambil beban kerja yang telah ditetapkan dan mendefinisikan kinerja setiap algoritma untuk beban kerja itu.algoritma untuk beban kerja itu.

� Queueing models� Implementasi

6.32

17

Evaluasi Penjadwal CPU dengan Simulasi

6.33

Penjadwalan Solaris 2

6.34

18

Prioritas Windows 2000

6.35