PENJADWALAN PROCESSOR
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
- 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 +
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
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.
·
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.
·
Metode
Implementasi
Metode ini bekerja dengan cara
mengamati hasil dari implementasi setiap penjadualan.
This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.
ConversionConversion EmoticonEmoticon