Komputer - Sistem Operasi

Sistem Operasi – Teknik Penjadwalan Prosesor

TEKNIK PENJADWALAN PROSESOR
1. Istilah-istilah dan Konsep-konsep Penjadwalan
• Bagian sistem operasi yang mengatur penjadwalan
eksekusi proses-proses disebut scheduler.
• Algoritma yang digunakan disebut algoritma
penjadulan (scheduling algorithm).
• Kriteria baik tidaknya suatu algoritma penjadwalan
ditentukan oleh:
1. Fairness
2. Efficiency
3. Response Time
4. Turnaround Time
5. Throughput
• Penjadwalan Proses
– Antrian
– Prioritas
– Preempsi
• Jangka penjadwalan
– pendek
– madya
– panjang
Sistem Operasi – Teknik Penjadwalan Prosesor 2/9
• Tujuan penjadwalan:
– pelayanan yang adil untuk semua pekerjaan
– memaksimumkan throughput
– memaksimumkan pemakaian prosesor
– meminimumkan waktu tunggu (overhead)
– pemakaian sumber daya seimbang
– tidak terjadi penundaan waktu tak hingga
– kegiatan sumber daya dapat dideteksi terlebih
dahulu
• Perhitungan kerja prosesor
t = lama proses pada prosesor
T = lama tanggap pada prosesor
Waktu sia-sia (waktu antri) = T - t
Rasio tanggap Rt = t / T
Rasio Penalti Rp = T/t
Penjadwalan Prosesor
• Penjadwalan satu tingkat
– Pertama Tiba Pertama Dilayani (PTPD)
– Proses Terpendek Dipertamakan (PTD)
– Proses Terpendek Dipertamakan Preempsi
(PTDP)
– Rasio Penalti Tertinggi Dipertamakan (RPTD)
– Putar Gelang (PG)
– Putar Gelang Prioritas Berubah (PGPB)
Sistem Operasi – Teknik Penjadwalan Prosesor 3/9
• Penjadwalan multi tingkat
– Antrian multitingkat
– Antrian multitingkat berbalikan
2. Penjadwalan Satu Tingkat
• Pertama Tiba Pertama Dilayani (PTPD)
First Come First Served (FCFS)
Penjadualan ini murni antrian.
Nama
Proses
Saat
Tiba
Lama
Proses
Saat
Mulai
Saat
Rampung
Lama
Tanggap
A 0 9 0 9 9
B 0 30 9 39 39
C 0 4 39 43 43
D 0 8 43 51 51
E 0 12 51 63 63
Jumlah 205
Rerata 41
• Pertama Tiba Pertama Dilayani (PTPD)
First Come First Served (FCFS)
Nama
Proses
Saat
Tiba
Lama
Proses
Saat
Mulai
Saat
Rampung
Lama
Tanggap
A 0 4 0 4 4
B 1 7 4 11 10
C 3 3 11 14 11
D 7 8 14 22 15
Jumlah 40
Rerata 10
Sistem Operasi – Teknik Penjadwalan Prosesor 4/9
• Proses Terpendek Dipertamakan (PTD)
Shortest Job First (SJF)
Penjadualan ini adalah antrian dengan prioritas, yang
menjadi prioritas adalah proses yang terpendek
(tersingkat).
Nama
Proses
Saat
Tiba
Lama
Proses
Nama
Proses
Saat
Tiba
Lama
Proses
A 0 8 C 6 3
B 4 5 E 14 4
C 6 3 B 4 5
D 9 8 A 0 8
E 14 4 D 9 8
• Proses Terpendek Dipertamakan (PTD)
Shortest Job First (SJF)
Nama
Proses
Saat
Tiba
Lama
Proses
Lama
Mulai
Saat
Rampung
Lama
Tanggap
A 0 8 0 8 8
C 6 3 8 11 5
B 4 5 11 16 12
E 14 4 16 20 6
D 9 8 20 28 19
Jumlah 50
Rerata 10
• Proses Terpendek Dipertamakan Preempsi (PTDP)
Preemptive Shortest Job First (PSJF)
Penjadualan ini dengan prioritas dan preempsi
Proses yang terpendek bisa didahulukan dengan cara
membandingkan sisa waktu proses yang sedang
dilaksanakan dengan proses yang tiba, dan dapat
Sistem Operasi – Teknik Penjadwalan Prosesor 5/9
menyebabkan proses yang sedang berjalan terhenti
untuk melaksanakan proses yang lebih pendek/singkat.
Nama Proses Saat Tiba Lama Proses
A 0 8
B 2 5
C 4 7
D 5 1
Barisan saat
Daftar Proses
Proses Tiba Proses Mulai Rampung Tanggap
A 0 8 0 14 14
B 2 5 2 8 6
C 4 7 14 21 17
D 5 1 5 6 1
Jumlah 38
Rerata 9.5
• Rasio Penalti Tertinggi Dipertamakan (PTD)
Highest Penalti Ratio Next (HPRN)
Tetap mendahulukan proses pendek ditambah dengan
mempertimbangkan rasio penaltinya, yang ditentukan
berdasarkan lama waktu antriannya.
t = lama proses
Sistem Operasi – Teknik Penjadwalan Prosesor 6/9
T = lama tanggap
s = waktu sia sia (waktu antri)
s = (T-t)
Rp= (s+t)/t
Nama Proses Saat Tiba Lama Proses
A 0 4
B 1 2
C 2 5
D 3 8
E 4 4
Nama Proses Tiba Selama Rasio Penalti
B 4 - 1 = 3 (3 + 2) / 2 = 2,5
C 4 - 2 = 2 (2 + 5) / 5 = 1,4
D 4 - 3 = 1 (1 + 8) / 8 = 1,125
E 4 - 4 = 0 (0 + 4) / 4 = 1
Nama Proses Tiba Selama Rasio Penalti
C 6 - 2 = 4 (4 + 5) / 5 = 1,8
D 6 - 3 = 3 (3 + 8) / 8 = 1,375
E 6 - 4 = 2 (2 + 4) / 4 = 1,5
Nama Proses Tiba Selama Rasio Penalti
D 11 - 3 = 8 (8 + 8) / 8 = 2
E 11 - 4 = 7 (7 + 4) / 4 = 2,75
Sistem Operasi – Teknik Penjadwalan Prosesor 7/9
Daftar Proses
Nama
Proses
Saat
Tiba
Lama
Proses
Lama
Mulai
Saat
Rampung
Lama
Tanggap
A 0 4 0 4 4
B 1 2 4 6 5
C 2 5 6 11 9
D 3 8 15 23 20
E 4 4 11 15 11
Jumlah 49
Rerata 9.8
• Putar Gelang (PG)
Round Robin (RR)
Penjadualan ini tanpa prioritas & preempsi
Setiap proses dilayani selama quantum waktu tertentu
secara bergiliran.
Nama Proses Saat Tiba Lama Proses
A 0 5
B 1 3
C 5 7
D 6 1
E 7 6
Kuantum waktu (q) = 2
Barisan saat
Sistem Operasi – Teknik Penjadwalan Prosesor 8/9
Daftar Proses
Nama
Proses
Saat
Tiba
Lama
Proses
Lama
Mulai
Saat
Rampung
Lama
Tanggap
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 52
Rerata 10.4
• Penjadwalan dengan prioritas berubah-ubah
Putar Gelang Prioritas Berubah (PGPB)
Selfish Round Robin (RR)
Penjadualan yang menggunakan proiritas dapat
diubah-ubah menjadi prioritas lainnya.
p = prioritas a = koefisien untuk lama
s = waktu sia sia b = koefisien untuk proses baru
t = waktu proses b/a = 1 => prioritas sama
u = tarif sewa b/a = 0 => prioritas lama +
p = f ( s, t, u ) b/a < 1 => prioritas baru < lama
b/a > 1 => prioritas baru > lama
3. Penjadwalan Multitingkat
Proses dibedakan tingkatnya berdasarkan
kepentingannya.
Penjadualan pada tiap tingkat dapat bermacam-macam.
Pada antrian multitingkat berbalikan, tingkat satu dan
lainnya saling berhubungan.
Sistem Operasi – Teknik Penjadwalan Prosesor 9/9
• Antrian Multitingkat (Multilevel queue)
• Antrian Multitingkat Berbalikan
Feedback multilevel queue
FCFS
Sistem Operasi – Teknik Penjadwalan Prosesor 10/9
4. Metoda Evaluasi Penjadwalan
– evaluasi analitik
• pemodelan deterministik
• analisis model antrian
– simulasi
– implementasi
¨ Metode Pemodelan Deterministik
Pekerjaan sudah ditetapkan terlebih dahulu, menerapkan
berbagai penjadualan dan dievaluasi hasilnya.
Kelemahan: Hanya tepat untuk model yang sudah
dicoba,
untuk model yang lain belum tentu.
¨ Metode Analisis Model Antrian
Dengan menganggap sistem komputer sebagai suatu
jaringan alat layanan.
Dianalisa berdasarkan model (rumus) yang diambil
untuk tiap penjadualan.
Kelemahan: Pengambilan model cukup rumit untuk
sistem tertentu dan model tidak selalu cocok dengan
keadaan yang sebenarnya.
¨ Metode Simulasi
Metode ini berdasarkan sejumlah variabel yang
disimulasikan sistem komputer yang digunakan.
¨ Metode Implementasi
Metode ini bekerja dengan cara mengamati hasil dari
implementasi setiap penjadualan.