algoritmapenjadwalanproses-190620235127.ppt

algorithm

1. DINDA PRASETIA

2. Algoritma Penjadwalan Proses
First Come First Served (FCFS) / FIFO (First In First Out)
SJF (Shortest Job First)
Priority Scheduling
Round Robin

3. First Come First Served (FCFS)
Merupakan algoritma penjadwalan CPU yang paling
sederhana
Proses yang tiba lebih dahulu akan dilayani lebih
dahulu
Kalau ada proses tiba pada waktu yang sama, maka
pelayanan mereka dilaksanakan berdasarkan
urutan dalam antrian
Proses di antrian belakang harus menunggu sampai
semua proses di depannya selesai.

4. Contoh - FCFS
Diketahui 3 buah proses sbb:

5. Gantt chart
Waiting Time
AWT

6. FCFS (2)
Contoh soal 1:
Jika diketahui terdapat 5 macam antrian proses, yaitu A-B-C-D-E
dengan waktu kedatangan semuanya 0. Lama proses berturut-
turut antara lain: 5-2-6-8-3.
Pertanyaan:
Kapan dimulainya eksekusi dari tiap-tiap antrian proses tsb?
Kapan selesai eksekusinya?
Hitung Turn Arround Time (TA)-nya?
Berata rata-rata TA?
Rumus
TA = Waktu Tunggu + Lama Eksekusi
Rata-rata TA = ∑TA / ∑Job
Waktu Tunggu = Mulai Eksekusi – Waktu Tiba

7. FCFS (3)
Jawaban:
Nama
Proses
Waktu
Tiba
Lama
Eksekusi
A 0 5
B 0 2
C 0 6
D 0 8
E 0 3

8. FCFS (4)
Nama
Proses
Waktu
Tiba
Lama
Ekseku
si
Mulai
Ekseku
si
Waktu
Tunggu
Selesai
Ekseku
si
TA
A 0 5 0 0 5 5
B 0 2 5 5 7 7
C 0 6 7 7 13 13
D 0 8 13 13 21 21
E 0 3 21 21 24 24
∑TA = 70
rata2 TA = 14

9. FCFS (5)
Contoh Soal 2:
Jika diketahui terdapat 5 macam antrian proses, yaitu
A-B-C-D-E dengan waktu kedatangan semuanya 0-1-2-
2-5. Lama proses berturut-turut antara lain: 5-2-6-8-3.
Pertanyaan:
Kapan dimulainya eksekusi dari tiap-tiap antrian
proses tsb?
Kapan selesai eksekusinya?
Hitung Turn Arround Time (TA)-nya?
Berata rerata TA?
Rumus
TA = Waktu Tunggu + Lama Eksekusi
Rerata TA = TA / Job
∑ ∑
Waktu Tunggu = Mulai Eksekusi – Waktu Tiba

10. FCFS (6)
Nama
Proses
Waktu
Tiba
Lama
Eksekusi
Mulai
Eksekusi
Selesai
Eksekusi
Waktu
Tunggu
TA
A 0 5 0 5 0 5
B 1 2 5 7 4 6
C 2 6 7 13 5 11
D 2 8 13 21 11 19
E 5 3 21 24 16 19
∑TA = 60
Rerata = 12

11. FCFS (7)
Berdasarkan kriteria penilaian penjadwalan:
Fairness
Penjadwalan FCFS adil dalam arti semantiks (dalam arti
antrian)
Efesiensi
Penjadwalan FCFS sangat efisien dalam penggunaan pemroses
Waktu Tanggap
Penjadwalan sangat tidak memuaskan, karena proses dapat
menunggu lama
Turn Arround Time
Penjadwalan FCFS tidak bagus
Throughput
Penjadwalan FCFS tidak bagus.

12. Shortest Job First
Dasar prioritas adalah pendeknya proses.
Makin pendek/singkat proses makin tinggi prioritasnya
Langkah I: tentukan urutan prioritas berdasarkan pendeknya
proses yang dilayani
Langkah II: penentuan proses mana yang dilayani oleh
pemroses

13. Setiap proses yang ada dalam ready queue akan
dieksekusi berdasarkan burst time terkecil
Hal ini mengakibatkan waiting time yang
pendek untuk setiap proses, maka rerata waiting
time (AWT) juga menjadi pendek
Algoritma ini dikatakan optimal

14. SJF (2)
Contoh Soal 1:Nama
Proses
Waktu
Tiba
Lama
Eksekusi
A 0 10
B 0 5
C 0 7
D 0 1
E 0 3

15. SJF (3)
Nama Proses Waktu Tiba Lama
Eksekusi
D 0 1
E 0 3
B 0 5
C 0 7
A 0 10

16. SJF (4)
Nama
Proses
Waktu
Tiba
Lama
Eksekusi
Mulai
Eksekusi
Selesai
Eksekusi
TA
D 0 1 0 1 1
E 0 3 1 4 4
B 0 5 4 9 9
C 0 7 9 16 16
A 0 10 16 26 26
∑TA = 56
rata2 TA = 11,2

17. SJF (5)
Nama Proses Lama
Eksekusi
Waktu Tiba
D 1 0
E 3 2
B 5 5
C 7 7
A 10 9

18. SJF (6)
Nama
Proses
Waktu
Tiba
Lama
Eksekusi
Mulai
Eksekusi
Selesai
Eksekusi
Waktu
Tunggu
TA
D 0 1 0 1 0 1
E 2 3 2 5 0 3
B 5 5 5 10 0 5
C 7 7 10 17 3 10
A 9 10 17 27 8 18
∑TA = 37
Rerata = 7,4

19. Priority Scheduling
Merupakan algoritma yang mendahulukan
proses yang memiliki prioritas tertinggi
Prioritas proses ditentukan berdasar:
Time limit
Memory requirement
File access
Perbandingan antara burst proses dengan CPU
Tingkat kepentinagn proses

20. PS (2)
Priority scheduling dapat dijalankan secara
preemptive dan non-preemptive
Preemptive  jika ada proses yang baru datang
memiliki prioritas lebih tinggi dari proses yang
sedang berjalan, maka proses yang sedang
berjalan tsb dihentikan, lalu CPU dialihkan untuk
proses yang baru datang tersebut
Non preemptive  proses yang baru datang tidak
dapat menganggu proses yang sedang berjalan,
tapi hanya diletakkan di depan queue

21. PS (3)
Kelemahan PS adalah terjadinya infinite
blocking (starvation), yaitu suatu proses dengan
prioritas yang rendah memiliki kemungkinan
tidak pernah dieksekusi jika terdapat proses lain
yang memiliki prioritas lebih tinggi
Solusi dari starvation adalah aging, yaitu
meningkatkan prioritas dari setiap proses yang
menunggu dalam queue secara bertahap

22. PS (4)
Contoh : setiap 10 menit, prioritas dari masing-
masing proses yang menunggu dalam queue
dinaikkan 1 tingkat.
Maka proses yang memiliki prioritas 127,
setidaknya dalam 21 jam 20 menit, proses tsb
akan memiliki prioritas 0, yaitu prioritas yang
tertinggi

23. Contoh 2 - PS
Diketahui 5 proses dengan urutan proses sbb:

24. Gantt chart
Waiting Time AWT

25. ROUND ROBIN
Algoritma ini menggilir proses yang ada di antrian.
Proses akan mendapat jatah sebesar time quantum.
Jika time quantum-nya habis atau proses sudah
selesai, CPU akan dialokasikan ke proses
berikutnya
Proses ini cukup adil, karena tidak ada proses yang
diprioritaskan
Semua proses mendapat jatah waktu yang sama
dari CPU yaitu 1/n, dan tidak akan menunggu lebih
lama dari (n-1)q; dimana q adalah lama 1 quantum

26. Algoritma RR sepenuhnya bergantung besarnya
time quantum (TQ).
Jika TQ terlalu besar, algoritma ini akan sama
saja dengan algoritma FCFS
Jika TQ terlalu kecil, akan semakin banyak
peralihan proses sehingga banyak waktu yang
terbuang

27. Permasalahan algoritma RR
Permasalahan utamanya adalah menentukan
besarnya TQ. Jika TQ yang ditentukan terlalu kecil,
maka sebagian besar proses tidak akan selesai dalam
1 quantum.
Akibatnya akan terjadi banyak switch, padahal CPU
memerlukan waktu untuk beralih dari satu proses ke
proses yang lain (= context switches time)
Sebaliknya, jika TQ yang ditentukan terlalu besar,
algoritma RR akan berjalan seperti FCFS
TQ ideal adalah jika 80% dari total proses memiliki
CPU burst time yang lebih kecil dari 1 TQ

28. Urutan Kejadian RR

29. Penggunaan TQ

30. Contoh sederhana

31. Contoh 2
Diketahui 3 proses sbb:
TQ = 3

32. Gantt chart
Burst Time

33. Contoh 3 - RR
Sebuah CPU dengan quantum 4 mendapat
beberapa proses yang kedatangannya
sebagai berikut:
ProsesBurst Time
P1 4
P2 9
P3 6
P4 5
P5 3
Burst time  waktu
proses

34. Gantt Chart
P1P2P3P4P5P2P3P4P2
0 4 8 12 16 19 23 25 26 27

35. AWT (average waiting time)
Waktu tunggu untuk tiap-tiap proses :
AWT yang terjadi adalah:
( 0 + 18 + 19 + 21 + 16 ) / 5 = 74 / 5 = 14,8
Proses Waiting Time
P1 0
P2 4 + (19 - 8) + (26 - 23) = 18
P3 8 + (23 - 12) = 19
P4 12 + (25 - 16) = 21
P5 16

36. ATR (average turn around)
ProsesSaat
Tiba
Lama
Proses
Saat
Mulai
Saat
Selesai
Turn Around
Time
P1 0 4 0 4 4
P2 0 9 4 27 27
P3 0 6 8 25 25
P4 0 5 12 26 26
P5 0 3 16 19 19
Jumlah
Rata-rata
101
20,2

37. Round Robin dengan Waktu Tiba
berbeda
Nama ProsesSaat TibaLama Proses
A 0 5
B 1 3
C 5 7
D 6 1
E 7 6
Jml 22
Quantum =
1

38. Gantt Chart
AABBAABCCDA
EECCEECCEEC
01 32 45678 9 10
111213141516171819202122

39. AWT
Nama
Proses
Saat
Tiba
Lama
Proses
Waiting Time
A 0 5 0+(4-2)+(10-6)=6
B 1 3 (2-1)+(6-4)=3
C 5 7 (7-5)+(13-9)+(17-15)+(21-19) =10
D 6 1 (9-6)=3
E 7 6 (11-7)+(15-13)+(19-17)=8
AWT = (6+3+10+3+8)/5 = 30/5 = 6

40. Turn Around
Nama
Proses
Saat
Tiba
Lama
Proses
Saat MulaiSaat SelesaiLama
Proses
A 0 5 0 11 11
B 1 3 2 7 6
C 5 7 7 22 17
D 6 1 9 10 4
E 7 6 11 21 14
Jumlah
Rata-rata
52
10,4

41. Contoh 4
Untuk memahami dari cara kerja algoritma
penjadwalan Round Robin ini,mari kita kerjakan
soal berikut 

42. Penyelesaian :
Seperti halnya algoritma penjadwalan sebelumnya, langkah
pertama untuk mencari AWT dengan Algoritma penjadwalan
Round Robin dilakukan dengan membuat Gantt Chart
prosesnya.

43. Dari Gantt Chart terlihat bahwa setiap proses
dikerjakan menurut waktu yaitu setiap proses di
proses sebesar 5 langkah.
Awalnya P1 akan di kerjakan sebanyak 5 langkah,
kemudian, P2 sebanyak 5 langkah, dan begitupun
selanjutnya hingga P5.
Proses yang sudah di proses menurut porsi waktu
yang diberikan akan kembali menunggu dan berada
paling belakang dari antrian proses yang ada.

44. Contohnya P1 dikerjakan di awal, kemudian
ada P2, P3,P4,dan P5 yang mengantri di
belakangnya.
Jika P1 selesai di proses menurut porsi
waktunya maka P1 akan di pindahkan ke
belakang, sehingga urutannya menjadi P2,
P3, P4, P4, P1. begitupun seterusnya.

45. Waiting Time
AWT

46. Latihan 1
Terdapat 5 job yang datang hampir pada saat
yang bersamaan. Estimasi waktu eksekusi
(burst time) masing-masing 10, 6, 2, 4 dan 8
menit dengan prioritas masing-masing 3, 5, 2, 1
dan 4, dimana 5 merupakan prioritas tertinggi.
Tentukan rata-rata waktu turn around untuk
penjadwalan CPU dengan menggunakan
algoritma
a. FCFS / FIFO
b. Round Robin (quantum time = 2)
c. Priority
d. Shortest job first

47. Latihan 2
Diketahui quantum = 5, dengan menggunakan
alogoritma Round Robin, carilah AWT dan Turn
Around jika terdapat proses sebagai berikut:
Nama Proses Saat Tiba Lama Proses
A 0 5
B 2 3
C 7 8
D 11 2
E 14 6