Pertemuan V Penjadwalan Proses

Sistem Operasi Komputer

Pertemuan V – Penjadwalan Proses

Konsep dasar Kriteria penjadwalan Algoritma penjadwalan Implementasi penjadwalan Evaluasi algoritma penjadwalan Case: Windows 2000 dan Linux

Universitas Kristen Maranatha -- IT Department

1


Multiprogramming beberapa proses berjalan dalam suatu waktu CPU – I/O burst cycle – Eksekusi proses terdiri atas cycle eksekusi CPU dan waktu tunggu I/O CPU burst distribution – CPU dialihkan ke proses yang lain pada saat suatu proses sedang dalam status wait I/O bound program – banyak CPU burst yang singkat CPU bound program – sedikit CPU burst yang sangat lama

PROCESS STATE ready running read( ) waiting ready ready running write ( ) waiting ready ready running read ( )

waiting ready


2


Pada saat CPU nganggur, seleksi ready queue dalam memori utama short term scheduler Setiap proses dalam ready queue harus mengantri sebelum mendapat giliran eksekusi dalam CPU Pertimbangan penjadwalan:

1. 2. 3. 4.

Nomor 1 dan 4 – nonpreemptive (CPU digunakan terus sampai proses selesai atau waiting) Nomor 2 dan 3 – preemptive (CPU beralih ke proses lain atau I/O / Context Switch

Kontrol terhadap seleksi short term scheduling:

Berpindah dari keadaan running ke waiting Berpindah dari keadaan running ke ready (interrupt) Berpindah dari waiting ke ready (completion I/O) Selesai

Context switching Switching ke user mode Melompat ke lokasi tertentu pada user program untuk memulai program tersebut

Dispatch latency – waktu yang diperlukan untuk menghentikan suatu proses dan memulai menjalankan proses terpilih


3


Max. CPU utilization – usahakan CPU sesibuk mungkin (40% - 90%) Max. Throughput – banyak eksekusi proses dalam satu satuan waktu Max. Fairness – pembagian waktu yang adil di antara proses Min. Turnaround time – waktu total eksekusi satu proses tertentu (siklus proses: memori, ready queue, ekesekusi, penyelesaian I/O) Min. Waiting time – waktu menunggu total di ready queue Min. Response time – waktu mulai dari permohonan sampai respons pertama suatu proses


4


Dikenal juga dengan istilah First In, First Out (FIFO) Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan mendapat prioritas Mudah diimplementasikan Average Waiting Time (AWT) cukup besar Problem: convoy effect, AWT membengkak jika proses yang terlebih dahulu membutuhkan CPU burst yang besar Non preemptive

Process P1 P2 P3

Burst Time 24 3 3

P1 0

P2 24

P3 27

30

Urutan proses: P1, P2, P3 Gantt Chart untuk penjadwalan ini: Waiting time untuk P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17


5


Jika urutan proses adalah:

P2 , P3 , P1 . Gantt chart untuk penjadwalan ini:

P2 0

P3 3

P1 6

30

Waiting time untuk P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Lebih baik dari kasus sebelumnya

Proses yang memiliki CPU burst paling kecil akan dilayani terlebih dahulu Non preemptive: proses yang sedang berlangsung tidak dapat digantikan dengan proses yang baru Preemptive: jika proses yang masuk dengan CPU burst lebih kecil daripada sisa CPU burst proses yang sedang berjalan, akan dilakukan pergantian proses dalam CPU, dikenal dengan istilah Shortest-Remaining-Time-First (SRTF) SJF dapat dinilai optimal karena memberikan minimum AWT untuk sejumlah proses yang ada dalam CPU


6


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

P4

P2 8

12

16

Average waiting time = (0 + 6 + 3 + 7)/4 = 4

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


7


SJF optimal namun sulit diimplementasikan Estimasi CPU burst yang akan datang: menggunakan perhitungan rata-rata exponensial dari lama CPU burst yang sudah lewat

τ n+1 = α tn + (1 − α )τn 1. t n = actual lenght of n th CPU burst 2. τ n +1 = predicted value for the next CPU burst 3. α , 0 ≤ α ≤ 1

α = 0.5; t1 = 6; τ1 = 10


8


Nomor prioritas (integer) diberikan untuk setiap proses CPU dialokasikan untuk proses dengan prioritas terbesar (nomor terkecil), bisa preemptive dan bisa pula non-preemptive SJF adalah bentuk khusus priority scheduling, dengan prioritas dihitung dari perkiraan CPU burst berikutnya Problem: starvation proses dengan prioritas rendah mungkin saja tidak pernah diproses di CPU Solusi: aging menaikkan prioritas setiap kali suatu proses dijalankan

Time sharing: setiap proses mendapat quantum waktu CPU, antara 10-100 ms Setelah quantum selesai, CPU diserahkan ke proses berikutnya (preemptive), dan proses yang sedang berlangsung ditaruh pada akhir ready queue Jika ada n proses dalam ready queue dan waktu quantum q, maka setiap proses mendapat 1/n waktu CPU dengan nilai q setiap kalinya Waktu tunggu proses tidak lebih dari (n-1)*q Performance:

q besar FCFS q kecil turnaround time besar (banyak terjadi context switching)


9


Process Burst Time P1 53 P2 17 P3 68 P4 24 Gantt chart penjadwalan P1 0

P2 20

P3 37

P4 57

P1 77

P3 97

117

P4

P1 121 134

P3

P3 154 162

Biasanya, rata-rata turnaround time lebih tinggi daripada SJF, namun dengan responsi yang lebih baik


10


Membagi proses dalam grup-grup Tiap grup dikerjakan dengan algoritma penjadwalan yang berbeda

Ready queue dibagi menjadi beberapa queue secara terpisah

Foreground RR Background FCFS

Foreground (interactive) Background (batch)

Prioritas yang tetap (foreground ke background), mungkin terjadi starvation

Time-slice setiap queue memiliki CPU time yang tetap, yang kemudian akan dijadwalkan di antara proses yang ada, misalnya: 80% untuk foreground (RR) dan 20% untuk background (FCFS)


11


Proses yang ada pada suatu queue dapat pindah ke queue lain Aging dapat pula diimplementasikan Parameter:

Jumlah queue Algoritma penjadwalan untuk setiap queue Metode untuk menentukan suatu proses akan diupgrade Metode untuk menentukan suatu proses akan diturunkan Metode untuk menentukan letak queue, jika ada proses yang akan dilayani


12


Tiga queue:

Q0 = time quantum 8 ms Q1 = time quantum 16 ms Q2 = FCFS

Scheduling:

Proses baru memasuki queue Q0 dengan layanan FCFS. Ketika mendapat CPU dan jika tidak selesai dalam waktu 8 ms, akan turun ke Q1 Di Q1, proses mendapat layanan FCFS, dan mendapat 16 ms CPU tambahan. Jika tidak selesai proses dipreempted dan turun ke Q2


13


Jaminan kinerja dan kelangsungan yang baik Contoh: n user login tiap user 1/n CPU time Jumlah CPU total time = 20 ms, tiap user 4 ms Menjalankan proses dengan rasio yang paling rendah hingga proses tersebut mendapat rasio yang melebihi rasio proses yang sebelumnya (satu tingkat lebih tinggi) User

CPU time (ms)

CPU actual (ms)

rasio

A

5

3

¾

B

4

6

6/4

C

8

2

2/4

D

1

1

¼

E

2

1

¼

Waktu terbuang untuk switching (swapping proses di memori utama dan disk) Solusi:

Two level scheduling himpunan bagian proses yang siap dieksekusi diload ke memori utama Scheduler memilih proses pada himpunan bagian ini Secara periodis, higher level scheduler mengganti proses yang telah lama tinggal di memori utama dengan proses yang telah cukup lama menunggu di disk


14


a, b, c, d

Proses di memori utama

e, f, g, h

b, c, f, g

e, f, g, h

Proses di disk

a, b, c, d

a, d, e, h

Time slice

Proses melahirkan proses lainnya (children/ fork) Tiap child memiliki permintaan yang berbeda (fungsi yang berbeda) Semua diputuskan oleh scheduler Solusi:

Policy user diijinkan memberi kebijakan kontrol dan prioritas pada suatu child Mechanism pelaksanaan policy, dilaksanakan oleh kernel


15


Procedure A( ) { while (true) { ; write(x); ; read(y); } }

// p11 // p12 // p13 // p14

Procedure B( ) { while (true) { read(x); ; write(y); ; } }

// p21 // p22 // p23 // p24

• x dan y adalah shared-variables • Dikerjakan serial (1 prosesor) atau paralel (2 prosesor) • problem: prosedur mana yang terlebih dahulu ? • solusi: procedure of processes (precedence graph)

P = { pi | 1 <= i <= n }

himpunan proses

<. = { (pi, pj) | 1 <= i, j <= n }

pasangan berurutan pada p

Π = ( P, <. )

komputasi

(pi, pj): pj tidak dapat dikerjakan sebelum pi selesai Tidak boleh ada looping


16


p11 p12

p13

p21 p22 p23

p14

Komputasi pada Precedence Graph Π= [ (p11, p12, p13, p14, p21, p22, p23, p24), { (p11, p12), (p12, p13), (p12, p 21), (p21, p22), (p22, p23), (p23, p14), (p13, p14), (p23, p24)} ]

p24

Fork (labelX) membangun proses baru dan mengerjakannya mulai dari statement yang diberi labelX

Join(Cacah) menggabungkan kembali beberapa proses menjadi proses tunggal. Variabel cacah menunjukkan berapa kalo JOIN dikerjakan. Setiap kali join dikerjakan secara otomatis nilai cacah berkurang satu

QUIT( ) keluar dari ekseskusi


17


Procedure A&B while (true) { cacah = 1; < hitung p11 >; < hitung p12 >; FORK ( L1 ); < hitung p13 >; L2: JOIN (cacah); < hitung p14>; QUIT( ); L1: < hitung p21 >; < hitung p22 >; < hitung p23 >; FORK ( L3); GOTO (L2); L3: < hitung p24 >; QUIT ( );

Model deterministik (analisis langsung) SJF kurang dari setengah waktu tunggu rata algoritma FCFS RR nilai tengah-tengah Model pengantrian (queueing model) Implementasi (simulasi): biaya tinggi


18


Penentuan prioritas setiap proses (thread) tergantung pada: Relative priority

Priority classes

1.

2.

3.

Tunjukkan perbedaan antara preemptive scheduling dengan non-preemptive scheduling Sebutkan hal-hal apa saja yang perlu diperhatikan dalam melakukan penjadwalan proses pada sistem multiprogramming Diketahui 4 proses P1, P2, P3 dan P4 dengan arrival time (waktu tiba) dan burst time (waktu eksekusi) sebagai berikut:


19


•

Proses

Arrival time (ms)

Burst time (ms)

P1

0

6

P2

1

8

P3

2

10

P4

3

5

Gambar gantt-chart dan hitung AWT, dengan algoritma penjadwalan: FCFS, preemptive SJF, RR (dengan QT = 2 ms)

Buatlah precedence graph untuk prosedur XX berikut ini:

4.

Procedure XX ( ) { while (true) { x = 10; y = 3; a = y * 2; b = 2 * x – 25; c = 3 * a + x; d = 2 * c – a; e = b – 2 * d; z = e + 1; } } 5.

//p1 //p2 //p3 // p4 // p5 // p6 // p7 // p8

Pada Prosedur XX di atas, buatlah urutan proses dengan menggunakan FORK-JOIN-QUIT !


20

Pertemuan V Penjadwalan Proses

Recommend Documents