Rangkum ” teknik penjadwalan prosessor “
5 Votes
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:
Fairness
Efficiency
Response Time
Turnaround Time
Throughput
Penjadwalan Proses
– Antrian
– Prioritas
– Preempsi
Jangka penjadwalan
– pendek
– madya
– panjang
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)
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
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 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
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
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
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 prioritas baru 1 => prioritas baru > lama
3. Penjadwalan Multitingkat
v Proses dibedakan tingkatnya berdasarkan kepentingannya.
v Penjadualan pada tiap tingkat dapat bermacam-macam.
v Pada antrian multitingkat berbalikan, tingkat satu dan lainnya saling berhubungan.
Antrian Multitingkat (Multilevel queue)
Antrian Multitingkat Berbalikan
Feedback multilevel queue
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.
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:
Fairness
Efficiency
Response Time
Turnaround Time
Throughput
Penjadwalan Proses
– Antrian
– Prioritas
– Preempsi
Jangka penjadwalan
– pendek
– madya
– panjang
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)
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
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 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
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
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
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 prioritas baru 1 => prioritas baru > lama
3. Penjadwalan Multitingkat
v Proses dibedakan tingkatnya berdasarkan kepentingannya.
v Penjadualan pada tiap tingkat dapat bermacam-macam.
v Pada antrian multitingkat berbalikan, tingkat satu dan lainnya saling berhubungan.
Antrian Multitingkat (Multilevel queue)
Antrian Multitingkat Berbalikan
Feedback multilevel queue
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.
